What Y means to me

It's become fashionable recently for people to discuss their views on the Y-Combinator. Here are mine, which I came up with a few years ago while attempting to understand the thing after reading Essentials of Programming Languages and The Why of Y.

I view the Y-Combinator as a combination of two ideas: Self application, and handling the recursion in a different function from the one that does the computation.

I'll start with self application.

(define (fib f n)
  (cond ((= n 0) 1)
        ((= n 1) 1)
        (else (+ (f f (- n 1)) (f f (- n 2))))))

To use this function, you pass it a copy of itself. For example, (fib fib 5) => 8.

We can curry this.

(define (fib f)
  (lambda (n)
    (cond ((= n 0) 1)
          ((= n 1) 1)
          (else (+ ((f f) (- n 1)) ((f f) (- n 2)))))))

Now passing fib a copy of itself creates the Fibonacci function. You could call it with ((fib fib) 5) => 8, or you could do something like (define fibonacci (fib fib)) and then (fibonacci 5) => 8.

The second idea is a way to have the recursion handled by an entirely different function. We define fib like this.

(define (fib f)
  (lambda (n)
     (cond ((= n 0) 1)
           ((= n 1) 1)
           (else (+ (f (- n 1)) (f (- n 2)))))))

Using this technique, we don't pass fib a copy of itself. We need to give it something special, something that behaves like the result of the call to fib, even though that isn't finished yet. Gee, that sounds like recursion. Let's make a function (let's call it Y!) that calls f with the thing that this function is going to return.

(define (y f) (f (y f)))

In my mind, I view the "(y f)" here as "the thing I'm about to return."

You may notice an infinite loop here, since y calls itself directly and unconditionally. In order to break the infinite loop, we use something called eta expansion. If a function f takes one argument, then the function f, and the expression (lambda (n) (f n)) both mean the same thing. The difference is that the eta expanded version won't try to figure out what f is until it's time to call it. The dangerous part of this definition of y is the call (y f), so let's eta expand that.

(define (y f) (f (lambda (n) ((y f) n))))

Now the recursion is handled in y. Every time fib calls (lambda (n) ((y f) n)), which is called f inside fib, another call to fib happens.

We can evaluate things like ((y fib) 5) => 8, or we can (define fibonacci (y fib)) and then (fibonacci 5) => 8.

Okay, but that definition of y is directly recursive. Is there a way to get rid of the recursion entirely? Yep. Self application. First, let's change the definition so that it uses an explicit lambda.

(define y (lambda (f) (f (lambda (n) ((y f) n)))))

And then, let's add the extra parameter for self application.

(define y ((lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))
           (lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))))

Notice how (x x) replaces y in the recursive calls.

By combining these two tricks, we are now able to simulate recursion even if we don't have it. Here is a final copy of the code to play with. Notice how it contains no recursive functions in the normal sense. No definitions contain the name that they are defining, yet it is still able to perform a recursive computation.

(define y ((lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))
           (lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))))

(define (fib f)
  (lambda (n)
    (cond ((= n 0) 1)
          ((= n 1) 1)
          (else (+ (f (- n 1)) (f (- n 2)))))))

(define fibonacci (y fib))

(fibonacci 5)

Paste that into your Scheme interpreter, and you should get out "8".

For a really, really good time, we can take out all of the definitions and do it all with function calls.

((((lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))
   (lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n))))))
  (lambda (f)
    (lambda (n)
      (cond ((= n 0) 1)
            ((= n 1) 1)
            (else (+ (f (- n 1)) (f (- n 2))))))))
 5)

Again, paste that into your Scheme interpreter, and you should get out "8".