G6021 Comparative Programming
1 Understanding Fixpoints
Let’s begin with a little puzzle. Fill in the blanks of the following sentence with numerals (in decimal notation) so as to make it true:
“Inthissentence,thenumberofoccurrencesof0is ,of1is ,of2is ,…,of9is .”
To see why this is relevant to Comparative Programming, let’s see how we can solve this. First, define the following:
• a = [a0,a1,…,a9], where ai is a numeral in decimal.
• For each i (from 0 to 9), let Ni(a) be the number of occurrences of i in a.
• Letg(a)=[N0(a)+1,N1(a)+1,…,N9(a)+1].
A solution to this problem is when a = g(a). In other words, we are looking for a fixpoint. We can compute this by a series of approximations:
a0 = suitable first approximation a1 = g(a0)
a2 = g(a1)
.
this is continued until an = an+1. Let’s try:
a0 = [0,0,0,0,0,0,0,0,0,0] a1 = [11,1,1,1,1,1,1,1,1,1] a2 = [1,12,1,1,1,1,1,1,1,1] a3 = [1,11,2,1,1,1,1,1,1,1] a4 = [1,11,2,1,1,1,1,1,1,1]
Since a3 = a4 we have found a fixpoint. You can put the values in the original sentence to check. There are other solutions too:
a0 = [2,8,7,5,3,2,4,2,4,1] a1 = [1,2,4,2,3,2,1,2,2,1] a2 = [1,3,6,2,2,1,1,1,1,1] a3 = [1,7,3,2,1,1,2,1,1,1] a4 = [1,7,3,2,1,1,1,2,1,1] a5 = [1,7,3,2,1,1,1,2,1,1]
Since a4 = a5 we have found a fixpoint. The first solution is known as the least fixpoint. There are no other solutions (that I know of!).
A fixpoint (or fixed-point) of a function f is a value a such that a = f(a). This idea can always solve problems like the above, numerical algorithms (for example the Newton-Raphson method for finding roots of equations), feedback equations, etc., etc.
1
Exercise. Write the above as a Haskell program. Submit your answer by email and win a prize! Now let’s turn our attention back to PCF programs. Recall the PCF functional for factorial:
F = λf.λn.cond(iszero n)1(n ∗ f(pred n))
We know that fix F computes factorial, but now we want to understand how and why it works. What we need to do is find the fixpoint of F, in other words, we need to solve f = F(f), as above. In the following, we write u for undefined. Values can be undefined and functions can be too (if u is a function then it is not defined on any inputs). Let’s try to find the fixpoint of F by iteration as before. We start with undefined, and build successive approximations: f0, f1 = F(f0),
f2 = F(f1), …
f0 = u
f1 = λn.cond(iszero n)1(n ∗ f0(pred n))
f2 = λn.cond(iszero n)1(n ∗ f1(pred n))
.
Note that we have performed a β-reduction step in each line above. It’s difficult to see this function take shape, so we can write it in the following way, where we give the result of applying each approximant to the numbers. What we see is that each better approximant gives the factorial to more numbers.
0 1 2 3 … f0 uuuu… f1 1uuu… f2 11uu… f3 112u…
To make proper sense of all this, we need a theory where:
• Undefined (u) is taken very seriously as a value.
• Equations x = F (x) can be solved by iteration, where the iterates are such that x0 gives “no information”, and successive xi give more and more information. The solution is the limit of the xi.
We can now see how PCF computes the approximants:
fix f = f(fix f) = f(f(fix f)) = f(f(f(fix f)))…
Only at the limit (infinite) do we get the factorial function. I can provide references if anyone is interested in knowing more about this theory.
2