Y-Combinator Explained Using Javascript

We take recursion for granted in most languages.  Consider the factorial function, in Javascript:

function f(n) {
    return (n < 2) ? 1 : n * f(n-1)
}

This implementation relies on the fact that the name f being defined is the same as the f in the definition.  If you think for a minute about how a compiler would arrange this, you are likely to come up with an imperative solution.  For example, the compiler might leave a placeholder for f in the compiled definition and then update it to point to itself once the body has been compiled.

Systems like the lambda calculus, being purely functional, do not admit of such imperative solutions.  So how do you express recursion functionally?

One answer is a technical trick called the Y-combinator.  Let's start by writing a variation of the factorial function:

function f(r) {
    return function(n) {
        return (n < 2) ? 1 : n * r(n-1)
    }
}

Instead of taking an integer and returning an integer, this new f takes a function and returns a function.  The returned function can compute the factorial of an integer -- provided r was bound to a suitable function that ensures the requisite recursion.

What is the proper argument for r?  How about f?

f(f)(10)

It looks promising, but it won't work.  Look again at the definition of f.  r must accept an integer as its argument, but we have passed f which expects a function.  This is trickier than it looks.  What we need is something like:

f(f(f(f(f(f(...))))))(10)

Enter the Y-combinator. It is used like this:

Y(f)(n)

which evaluates to:

f(Y(f))(n)

that is:

f(f(f(f(f(f(...))))))(n)

That's easy to say.  But has does one write this mythical function Y?  I can't answer that, but Alonzo Church could.  Here's the definition he somehow puzzled out, in lambda notation:

λf . (λg . f (g g)) (λg . f (g g))

Applying Y to f, the evaluation sequence is as follows:

(λf . (λg . f (g g)) (λg . f (g g))) f

(λg . f (g g)) (λg . f (g g))

f ((λg . f (g g)) (λg . f (g g)))

f (f ((λg . f (g g)) (λg . f (g g))))

f (f (f ((λg . f (g g)) (λg . f (g g)))))

f (f (f (f ((λg . f (g g)) (λg . f (g g))))))

...

This has the desired property.  Here is Y expressed in Javascript, along with the almost-recursive definition of f and a test case:

function Y(f) {
   return function(g) { return function(n) { return f(g(g))(n) }}(
     function(g) { return function(n) { return f(g(g))(n) }}
   )
}

function f(r) {
   return function(n) { return n < 2 ? 1 : r(n-1) * n } }

alert(Y(f)(10))

Nifty, huh?  For those who want to play along in Scheme:

(define Y
   (lambda (f)
     ((lambda (g)
        (lambda (n)
          ((f (g g)) n) ))
      (lambda (g)
        (lambda (n)
          ((f (g g)) n) )))))

(define f
   (lambda (r)
     (lambda (n)
       (if (< n 2) 1 (* n (r (- n 1)))) )))

((Y f) 10)