CS350 :: I Sem 2018-19
Table of Contents
- 1. Basic Data types
- 2. Functions in Oz
- 3. Techniques
Introduction to Functional Programming in Oz
1 Basic Data types
The following basic data types are sufficient to get you started programming using Oz.
1.1 Numeric Types
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}
1.2 Variables and Atomic Types
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:
- start with a lowercase letter, and are followed by alphanumeric values,
- 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}
1.3 Records and Tuples
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}
1.4 Lists
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.
2 Functions in Oz
Functions and Procedures in Oz are first-class values. That is to say, a function or a procedure can be treated in the same way as any other value. We can perform the following operations with values:
- Create a value and bind a variable to that value
- Pass a value as argument to a function/procedure
- Return a value from a function.
The last two operations cannot usually be done on functions in imperative langages. (For example, you cannot pass a function as an argument to a function.) Moreover, a function can be 'anonymous', i.e. a value which does not have an assigned variable name.
These features enable what is called "higher-order programming". We will utilize these features to program in Oz.
3 Techniques
This is a brief introduction to functional programming in Oz.
3.1 Recursion
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
3.2 Tail Recursion
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:
- 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. - 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?)
3.3 Lists! - nil, first, tail
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)))
3.4 Programming with Lists - Pattern-Matching
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(n2) 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]
3.5 Recursive Data Types - Follow the definition!
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}
3.6 Higher-Order Programming
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.
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
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
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
3.6.1 Programming using Map and Fold
Expression which calculates the sum of squares of the elements in a list.
{Browse {FoldR {Map [1 2 3] fun {$ X} X*X end}
fun {$ X Y} X+Y end
0}}
3.7 Lazy Evaluation
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
3.7.1 Lazy Quick Sort
Modified snippet of code taken from Peter Van Roy's site: http://www.info.ucl.ac.be/~pvr/ds/lazyQuicksort.oz
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
3.8 Advanced - Difference Lists
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.
3.9 Advanced - Continuation-Passing Style
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.
3.9.1 Sequential Programming
The following example is adapted from the Wikipedia entry for Continuation Passing Style.
Suppose we want to compute the length of the hypotenuse of a right triangle given the base and the altitude. We may write an Oz function as follows.
declare Sum Prod Hypotenuse
fun {Hypotenuse X Y}
{Sqrt {Sum {Prod X X}
{Prod Y}}}
end
At execution time, the call stack of this function has depth at least 4. Can we implement such a function with a constant-depth stack by utilising a generalization of tail recursion?
Consider a simple function written in C to compute the hypotenuse of a right triangle given the length of the base and the altitude. We write in a specific style, where all intermediate values are named.
fun hypotenuse (float a, float b)
{
float a2;
float b2;
float s;
float ret;
a2 = a*a;
b2 = b*b;
s = a2+b2;
ret = sqrt(s);
return ret;
}
We now code up the hypotenuse function in continuation passing style. Each function in our earlier version now takes a "single argument function" as an additional parameter. The single argument to this function is the result of the current function that needs to be passed down the execution sequence.
declare Sum_ Prod_ Sqrt_ Hypotenuse_
fun {Sum_ A B F}
{F A+B}
end
fun {Prod_ A B F}
{F A*B}
end
fun {Sqrt_ A F}
{F {Sqrt A}}
end
fun {Hypotenuse_ A B F}
{Prod_ A A fun {$ A2}
{Prod_ B B fun {$ B2}
{Sum_ A2 B2 fun{$ S}
{Sqrt_ S F}
end}
end}
end}
end
{Browse
{Hypotenuse_ 1.0 2.0 fun {$ X} X end}} % identity function as continutation
3.9.2 Other applications
Coroutines, making evaluation order of arguments explicit etc.