Fixed-Point Combinators

Question

I am new to the world of fixed-point combinators and I guess they are used to recurse on anonymous lambdas, but I haven't really got to use them, or even been able to wrap my head around them completely.

I have seen the example in Javascript for a Y-combinator but haven't been able to successfully run it.

The question here is, can some one give an intuitive answer to:

• What are Fixed-point combinators, (not just theoretically, but in context of some example, to reveal what exactly is the fixed-point in that context)?
• What are the other kinds of fixed-point combinators, apart from the Y-combinator?

Bonus Points: If the example is not just in one language, preferably in Clojure as well.

UPDATE:

I have been able to find a simple example in Clojure, but still find it difficult to understand the Y-Combinator itself:

(defn Y [r]
  ((fn [f] (f f))
   (fn [f]
     (r (fn [x] ((f f) x))))))

Though the example is concise, I find it difficult to understand what is happening within the function. Any help provided would be useful.

Answer 1

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).

Answer 2

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