Fixed Point Combinator

From ParadoxicalCombinator:

A fixed point is a point in a function's domain which is equal to the corresponding point in its range. That is, suppose a function f which maps from a set A to a set B, that is `f: A -> B' . A fixed point of f is an x in A that equals f(x). So you get input which is exactly the same as the output.

The fixed point combinator is a HigherOrderFunction which returns a fixed point of its argument. It makes a recursive function from a non-recursive function. Say we want to define a recursive function fib by:

 fib 0 = 1
 fib 1 = 1
 fib (n+2) = (fib n) + (fib (n+1))

To remove the recursion, we rewrite it as:

 FIB fib 0 = 1
 FIB fib 1 = 1
 FIB fib (n+2) = (fib n) + (fib (n+1))

where fib has become a parameter rather than the function itself. To make the original recursive function fib, we can define

 fib = FIB fib

This is a general method, so we can define a function Y to do it:

 Y f x = f (Y f) x
 fib = Y FIB

then

 fib x = Y FIB x
       = FIB (Y FIB) x
       = FIB fib x

as desired. We can eliminate all recursion by replacing it with calls to the Y combinator. This is good, because it means your VirtualMachine no longer needs to support recursion except in its hard-coded implementation of Y. Y can be written in LambdaCalculus as:

 Y = (\y.\f. f (y y f)) (\y.\f. f (y y f))

From this it is easy to see that Y satisfies:

 Y = \f. f (Y f)

The other good thing about Y (the FixedPointCombinator) is that it produces the LeastFixedPoint? of the recursive function. That means that the function produced (Y f), does not do bizarre things like assign values to elements outside the domain for which it is specified. The LeastFixedPoint? of a recursive function happens to be the one which can be calculated by computers implementing recursion using stacks, which is convenient.

Try this:

http://okmij.org/ftp/Computation/fixed-point-combinators.html

See (or write ;-) MetacircularFixedPoint?.