Introduction to Functional Programming in Oz

local Factorial in
   fun {Factorial N}
       if N == 0 then 1 else N*{Factorial N-1} end
   end
   {Browse {Factorial 5}}
end

Upper-case names denote variables. Recall that variables can be bound to a value only once, and afterwards they cannot be reassigned to a different value.

The local block introduces a variable Factorial, which happens to be a function. This function is the familiar recursive definition of Factorial: It consists of an if block which evaluates to the expression 1 if the input argument is 0, and evaluates to N*{Factorial N-1} otherwise.

Please note the syntax of function application - it is {function-name arg}. The first token in the curly braces is taken to be the function's name, and the remaining are the arguments to the function, if any.

The execution stack of {Factorial 4} will look as follows.

{Factorial 4} = 4 * {Factorial 3}
  {Factorial 3} = 3 * {Factorial 2}
    {Factorial 2} = 2 * {Factorial 1}
      {Factorial 1} = 1 * {Factorial 0}
        {Factorial 0} = 1

---

Typically, even though recursion is a more elegant way of expressing code, there is an overhead incurred due to the maintenance of a deep stack. In the above example, the call to {Factorial 4} resulted in an execution stack that was 5 layers deep. Note that this stack has to be maintained, since multiplication with N is done after the recursive call returns.

We will see a technique where certain kinds of iteration can be converted automatically into recursive code, which can execute without maintaining a deep stack. The technique is called Tail recursion.

Consider an iterative factorial program in C.

1:  long factorial(int n)
2:  {
3:     int product = 1;
4:     while(n >= 0){
5:         product = product*n;  
6:         n = n-1;
7:     }
8:  }

Here, we modify the variables n and product to produce the factorial. These variables are called the accumulator variables. We cannot directly adopt the style in Oz, since Oz variables can be bound only once. We will imitate this style in Oz. The two main ideas are the following:

1. Create an auxiliary function (helper function), which has the accumulator variables as additional arguments. This function is roughly the while loop in the C code.
2. Then, the main function calls this auxiliary function, initializing the accumulator variables.

 1:  declare
 2:  %==========
 3:  % Returns the factorial of N
 4:  %==========
 5:  fun {Factorial N}
 6:     local FactorialAux in
 7:         %===============
 8:         % Auxiliary function - similar to while loop
 9:         % in the C code. N is the number whose factorial
10:         % we need. Product is the cumulative product 
11:         %===============
12:         fun {FactorialAux N Product}
13:             if N == 0 
14:             then Product 
15:             else {FactorialAux N-1 N*Product}
16:         end
17:         %==============
18:         % Main function calls auxiliary with proper initial
19:         % values. Corresponds to Line 3 of the C code 
20:         %============= 
21:         {FactorialAux N 1} 
22:  end

Please note the difference of Lines 13-14 from the recursive definition of Factorial. The execution stack of {Factorial 4} now looks like

{Factorial 4} = {FactorialAux 4 1} 
              = {FactorialAux 3 4*1}
              = {FactorialAux 2 3*4*1}
              = {FactorialAux 1 2*3*4*1}
              = {FactorialAux 0 1*2*3*4*1}
              = 1*2*3*4*1

In contrast with the recursive code, there is nothing that remains to be done in the calling function, after the recursive call returns - that is, the recursive call is the "last thing" in the calling function - such calls are called tail calls.

If the call is a tail call, an intelligent compiler can just remove the calling stack immediately after the recursive call. Thus in principle, the stackframe can be just 1 layer deep while executing the above. This is called tail call optimization.

Not all recursions are tail calls - a good example is an in-order traversal on a binary tree (Why?)

---

One of the elementary data structures one encounters in FP is, the list. For an introduction to Oz Lists, please consult the introduction.

Briefly, a list is a sequence of elements. The representation of a list L in Oz is either nil or a tuple with label | (the vertical bar, or the pipe symbol) with two fields - L.1 is the first element of the list, and L.2 is itself a list.

Question: Suppose L is a list. What is the difference between {Width L} and {Length L}?

The following illustrates three valid notations for the same list in Oz.

[A B C]      = A|B|C|nil       = '|'(1:A 
                                     2:'|'(1:B
                                           2:'|'(1:C 2:nil)))

---

A list is recursively defined as either nil or a tuple, with the first element being a value, and the second being a list.

When writing programs over lists, the functions we define have to handle both these cases. We can handle this using an if...then...else expression, but Oz provides an elegant feature to deal with such situations: this is called pattern-matching, done using a case statement.

We now consider some basic functions over lists, as illustration.

• Length of a list

declare
fun {ListLength L}
   case L 
   of nil then 0
   else 1+{Length L.2}
   end
end

• k-element of a list, for a fixed k.

declare
fun {Elt L K}
   case L
   of nil then nil
   else
      if K==0 then L.1 else {Elt L.2 K-1} end
   end
end

• Concatenation of two lists

declare
fun {Concat L M}
   case L
   of nil then M
   [] H|T then H|{Concat T M}
   end
end

• (*) Cross-product of two lists

%=========
% Input E - a value, and L = [L1 L2 ... Ln], a list.
% Returns a list [[E L1] [E L2] ... [E Ln]]
%========
fun {Preface E L}
   case L
   of nil then nil
   [] H|T then [E H]|{Preface E T}
   end
end
%===========
% Input - L, M lists
% Returns the cross product of the two lists
%===========
fun {CrossProduct L M}
   case L
   of nil then nil
   [] H|T then {Concat {Preface H M}
                       {CrossProduct T M}}
   end
end

• Reverse of a List, O(n²) time

declare
fun {ReverseList_1 L}
   case L
   of nil then nil
   [] H|T then {Append {Reverse T} [H]}
   end
end
{Browse {ReverseList_1 [1 2 3]}}

• Reverse of a List, O(n)

Here we cleverly use the observation that a function call stack essentially gives the last-in-first-out behaviour we want the reverse to accomplish.

declare
fun {ReverseList2 L}
   local ReverseAux in
      fun {ReverseAux Remainder Partial}
         case Remainder
         of nil then Partial
         [] H|T then {ReverseAux T H|Partial}
         end
      end
      {ReverseAux L nil}
   end
end

• Reverse of a List, without using helper functions (exponential-time!)

declare
fun {Reverse3 L}
   if {Length L} < 2
   then L
   else
      local R = {Reverse3 L.2} in
         R.1 | {Reverse3 L.1|{Reverse3 R.2}}
      end
   end
end

For example,

{Reverse3 [a b c d]} = d|{Reverse3 a|{Reverse3 [c b]}   //R = [d c b]
                     = d|{Reverse3 a|[b c]}
                     = d|[c b a]
                     = [d c b a]

---

For recursive data-types, we can write functions which "follow" the recursive definition.

For example, a Binary Tree is either empty, or is a root with a left sub-tree and a right sub-tree, both of which are binary trees.

Then, the following is an in-order traversal of a binary-tree represented as a nested record.

declare
proc {InOrder BinTree}
   case BinTree
   of nil then skip
   else
      {InOrder BinTree.left}
      {Browse BinTree.root}
      {InOrder BinTree.right}
   end
end
%===== Example Usage ========
T = tree(root:3 
         left:tree(root:2 
                   left:tree(root:1 
                             left:nil right:nil) 
                   right:nil)
         right:tree(root:4 
                    left:nil 
                    right:tree(root:5 
                               left:nil right:nil)))
{InOrder T}

---

In functional programming, functions are first-class values. This means that functions can be used wherever a value can be given. This includes the following three conditions.

1. It is possible to assign functions as values of variables.

   local X Double in
      fun {Double Y} 2 * Y end
      X = Double
      {Browse {X 2}}
   end
   

2. It is possible to pass functions as arguments.

   local Accumulate Product in
      fun {Product X Y}
         X * Y
      end
      %==============
      % Function to calculate the cumulative result of
      % iterative application of BinOp over the list L.
      % BinOp is assumed to be right-associative.
      % Identity is the identity element of BinOp.
      %==============
      fun {Accumulate L BinOp Identity}
         case L
         of nil then Identity
         [] H|T then {BinOp H {Accumulate T BinOp Identity}}
         end
      end
      %======== Example Usage ======
      {Browse {Accumulate [1 2 3] Product 1}}
   end
   

3. Return values can be functions.

   local AddX F in
      %===========
      % Input X 
      % Returns a function which adds X to its argument
      %==========
      fun {AddX X}
         fun {$ Y}  % $ sign denotes "anonymous" function
            X+Y
         end
      end
      F = {AddX 2}
      {Browse {F 3}}
   end
   

Higher-order programming enables us to write many programs over lists using the following functions.

Map

Map is a higher-order function which takes a unary function F, and a list of elements [L1 L2 … Ln], and returns a list [F(L1) F(L2) … F(Ln)]

local Map in
   fun {Map L F}
      case L
      of nil then nil
      [] H|T then {F H}|{Map T F}
      end
   end
end

FoldR

A higher order function which takes a (right-associative) binary function B, the identity and a list [L1 … Ln] and returns the value {B L1 {B L2 {… {B Ln Identity}…}}}.

local FoldR in
   fun {FoldR L B I}
      case L
      of nil then I
      [] H|T then {B H {FoldR T B I}}
      end
   end
end

{Browse {FoldR {Map [1 2 3] fun {$ X} X*X end} 
               fun {$ X Y} X+Y end 
               0}}

An evaluation strategy where a value is evaluated only when it is needed. Note that the && and || operators in C follow a lazy evaluation strategy. We will now introduce this style of programming in Oz.

declare
fun lazy {ListOfIntsFrom N}
   N|{ListOfIntsFrom N+1}
end
{Browse {ListOfIntsFrom 0}}

fun lazy {LAppend Xs Ys}
   case Xs
   of X|Xr then X|{LAppend Xr Ys}
   [] nil then Ys
   end
end

proc {Partition Xs Pivot Left Right}
   case Xs
   of X|Xr then
      if X < Pivot
      then Ln in
         Left = X | Ln
         {Partition Xr Pivot Ln Right}
      else Rn in
         Right = X | Rn
         {Partition Xr Pivot Left Rn}
      end
   [] nil then Left=nil Right=nil
   end
end

fun lazy {LQuickSort Xs}
   case Xs of X|Xr then Left Right SortedLeft SortedRight in
      {Partition Xr X Left Right}
      {LAppend {LQuickSort Left} X|{LQuickSort Right}}
   [] nil then nil
   end
end