O'Reilly logo
  • Stefan Schwetschke thinks this is interesting:

Y-combinator

From

Cover of Functional Programming in JavaScript

Note

fixpoint combinator

Let's start by specifying what Y does:

(Y f) = fixpoint-of-f
What do we know about the fixpoint of f? We know that

(f fixpoint-of-f) = fixpoint-of-f
by the definition of what a fixpoint of a function is. Therefore, we have:

(Y f) = fixpoint-of-f = (f fixpoint-of-f)
and we can substitute (Y f) for fixpoint-of-f to get:

(Y f) = (f (Y f))
Voila! We've just defined Y. If we want it to be expressed as a Scheme function, we would have to write it like this:

(define (Y f) (f (Y f)))
or, using an explicit lambda expression, as:

(define Y
(lambda (f)
(f (Y f))))

I'm going to expand out the definition of Y ...