Some worked examples for G6021 Comparative Programming
1 Fixed points of functionals
Any recursive function can be written as a fixed point (or fixpoint) of a functional. In the course we use the language PCF for this (which is the ¦Ë-calculus with a few extras).
A typical question will ask you to a write function written in Haskell as the fixed point of a functional. There are three things that you need to do:
1. Write function using the language of PCF by replacing operations of Haskell as PCF expres- sions. Example: replace n + 1 with succ n, etc.
2. Write all the parameters as ¦Ë-expressions. Example: f x y z = P should be written as f = ¦Ëxyz.P
3. Finally, remove the recursion by abstracting the recursive call. This gives the functional, and the fix operator can be used to complete the process.
Write the following as a fixed point of a functional:
1. Factorial (version with accumulating parameter):
fact(n,acc) = if n==0 then acc else fact(n-1,n*acc)
Solution:
fact = \n -> \acc -> cond (iszero n) acc (fact (pred n) (mult n acc))
F = \f -> \n -> \acc -> cond (iszero n) acc (f (pred n) (mult n acc))
fact = fix F
Let¡¯s see how this works by looking at a trace of the a computation:
fact 3 1 = fix F 3 1 -> F (fix F) 3 1
-> cond (iszero 3) 1 ((fix F)(pred 3) (mult 3 1))
-> cond false 1 ((fix F) (pred 3) (mult 3 1))
-> fix F 2 (mult 3 1)
-> F (fix F) 2 (mult 3 1)…
Try to complete this example. If you cannot follow any of the steps above, please ask.
2. power(x,y) = if y==0 then 1 else x*power(x,y-1) Solution:
1
power(x,y) = cond (iszero y) 1 (mult x (power(x,pred y)))
power = \x -> \y -> cond (iszero y) 1 (mult x (power x (pred y)))
P = \p -> \x -> \y -> cond (iszero y) 1 (mult x (p x (pred y)))
power = fix P
Note that we have assumed the existence of mult. I have written the answer using Haskell syntax for abstractions (you are free to use either). Note also that since PCF does not have pairs, I converted the single argument to two arguments as part of the process. To use this function, we can use fix P in place of power, for example: fix P 3 4.
2