functional-programminganonymous-functionhigher-order-functionsy-combinatorfixpoint-combinators

Fixed-Point Combinators

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:

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.

Solution

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