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