CS350 :: I Sem 2018-19

Oz supports the basic numeric types available in other languages. Integers can have arbitrary magnitude. Note: Negative numbers are signified using tildes:

{Browse 1}
{Browse ~1}
{Browse 1+~1}

Floating point numbers are similar to those in other languages.

{Browse 1.1 + ~1.1}

Oz comes from the PROLOG family of languages, and it follows the PROLOG convention: any variable should start with a capital letter, followed by a finite number of ASCII letters, digits or underscores. A succinct way to describe valid variable names is using the regular expression [A-Z][A-Za-z_0-9]*.

Note: A very important feature of Oz is this: you can compute with unbound variables. That is, you can declare a variable, not bind it to any value, and still have meaningful computations based on it. Consider the following code:

declare X Y
X = Y
{Browse X==Y}

Oz also provides basic indivisible data types. One kind of an atomic data type is a literal. The other kind of atomic data types are literals - which can be either atoms or names.

Atoms can be defined in two ways:

1. start with a lowercase letter, and are followed by alphanumeric values,
2. Any string within single quotes.

Names are unforgeable constants, like unit, true or false. They can only be created, or compared for equality.

{Browse hello}
{Browse 'Hello World'}
{Browse true}
declare X
X = true
{Browse X==true}

This is a collection of associations of "features" to "values". Features must be atoms or numbers. For example, the following is a record.

Captains = worldcup(france:'Hugo Lloris' belgium:'Eden Hazard')
{Browse Captains.france}

Tuples are records where the features are numbers.

declare Tuple1 Tuple2 Tuple3
Tuple1 = message(1:'hello' 2:'World')
Tuple2 = message(1:'hello' 3:'again' 2:'World')
Tuple3 = message(1:'hello' 3:'again')
{Browse Tuple1}
{Browse Tuple2}
{Browse Tuple3}

Lists are a fundamental data type, which, in Oz are implemented as a particular kind of tuples. We will discuss them in detail when we come to the programming techniques.

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.

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.

1. 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
   

2. 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
   

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

A difference list is a pair of two lists, each possibly ending in an unbound variable, such that the second list can be obtained as a "tail" of the first. The resulting data represented by the difference list is the prefix of the first list with its tail represented by the second list removed.

declare L1 L2 L3 X Y Z
L1 = [a b c]#[c]       % represents [a b]
L2 = (a|b|c|X)#(c|X)   % represents [a b]
L3 = Y#Y               % represents nil
{Browse L1}
{Browse L2}
{Browse L3}

Note that any list can have multiple difference list representations.

Difference lists are especially useful when the two lists end in unbound variables. The simple act of binding them to a value can lead to surprisingly quick implementations.

For example, recall that appending two lists is an \(O(n)\) operation. If users agree upon the difference list representation, then append can be done in \(O(1)\) time!

declare AppendDiff D E List1 List2
fun {AppendDiff L1 L2}
    S1#E1 = L1
    S2#E2 = L2
in
    E1=S2
    S1#E2
end
List1=(a|b|c|D)#(D)
List2=(d|E)#(E)
{Browse {AppendDiff List1 List2}}
declare List3 F

The problem with difference lists is that they can be appended only once - after that, the second element in the pair is no longer an unbound variable by itself. (the second element in the pair is a list ending in an unbound variable, but this is not sufficient.) So difference lists are applicable only in special circumstances.

We now look at a programming style where "control flow" is explicitly passed as a continutation: informally, a continuation is a representation of the current state of the program. We do not intend to study the technique formally, but we will illustrate its uses with a couple of examples.