Fixed-Point Combinators

Suppose you wanted to write the factorial function. Normally, you would write it as something like

function fact(n) = if n=0 then 1 else n * fact(n-1)

But that uses explicit recursion. If you wanted to use the Y-combinator instead, you could first abstract fact as something like

function factMaker(myFact) = lamba n. if n=0 then 1 else n * myFact(n-1)

This takes an argument (myFact) which it calls were the "true" fact would have called itself. I call this style of function "Y-ready", meaning it's ready to be fed to the Y-combinator.

The Y-combinator uses factMaker to build something equivalent to the "true" fact.

newFact = Y(factMaker)

Why bother? Two reasons. The first is theoretical: we don't really need recursion if we can "simulate" it using the Y-combinator.

The second is more pragmatic. Sometimes we want to wrap each function call with some extra code to do logging or profiling or memoization or a host of other things. If we try to do this to the "true" fact, the extra code will only be called for the original call to fact, not all the recursive calls. But if we want to do this for every call, including all the recursive call, we can do something like

loggingFact = LoggingY(factMaker)

where LoggingY is a modified version of the Y combinator that introduces logging. Notice that we did not need to change factMaker at all!

All this is more motivation why the Y-combinator matters than a detailed explanation from how that particular implementation of Y works (because there are many different ways to implement Y).

To answer your second question about fix-point combinators other than Y. There are countably infinitely many standard fix-point combinators, that is, combinators fix that satisfy the equation

fix f = f (fix f)

There are also contably many non-standard fix-point combinators, which satisfy the equation

fix f = f (f (fix f))

etc. Standard fix-point combinators are recursively enumerable, but non-standard are not. Please see the following web page for examples, references and discussion. http://okmij.org/ftp/Computation/fixed-point-combinators.html#many-fixes