The Y-Combinator

I finally found the time to grok the Y-combinator. There are already multiple examples available but I am to thick to get them and, therefore, wanted to derive it myself.

The Y-combinator is a wonderful piece of software that allows you to create self-referential programs without built-in support. That is, it allows me to create anonymous recursive functions. This is best shown by an example.

; The factorial function
(define fact
  (lambda (n)
    (if (< n 2) 1 (* n (fact (- n 1))))))

In the recursive function above the fact refers to itself by name. This relies on the name being available before it is actually defined. To avoid this we can send the function as a parameter to itself. Like so:

; Define a local variable g as the function.
; The function takes a function (itself) as an extra parameter.
; The function is called with itself as a parameter:  (g g 5)).
; This doesn't compile since the function h (that is g) requires 
; an additional parameter.
(let ((g (lambda (h n)
           (if (< n 2) 1 (* n (h  (- n 1)))))))
  (g g 5))

; The working version needs h to also call itself (h h (- n 1)).
(let ((g (lambda (h n)
           (if (< n 2) 1 (* n (h h (- n 1)))))))
  (g g 5))

We can now abstract over the h parameter with a technique reminiscent of currying.

; A new lambda is abstracted over h.
; Note that the function calls to g and h need to change ((g g) 5)) 
; and ((h h) (- n 1)) to ensure that they agree with the definitions.
(let ((g (lambda (h)
           (lambda (n)
             (if (< n 2) 1 (* n ((h h) (- n 1))))))))
  ((g g) 5))

We can now abstract over n and (h h) creating a new lambda with the parameters q and m.

; Function f is declared locally with the parameters q and m 
; and then called directly (f (h h) n).
(let ((g (lambda (h)
           (lambda (n)
             (let ((f (lambda (q m)
                        (if (< m 2) 1 (* m (q (- m 1)))))))               
               (f (h h) n)))))
      ((g g) 5)))

Notice that f is independent of it’s context and can be moved to the top level.

; f moved to the top level.
(let ((f (lambda (q m)
           (if (< m 2) 1 (* m (q (- m 1)))))))
  (let ((g (lambda (h)
             (lambda (n)
               (f (h h) n)))))
    ((g g) 5)))

I can now abstract over q to isolate the definition of fact.

; Notice that the inner function of f is the original fact function.
(let ((f (lambda (q) 
           (lambda (m)
             (if (< m 2) 1 (* m (q (- m 1))))))))
  (let ((g (lambda (h)
             (lambda (n)
               ((f (h h)) n)))))
    ((g g) 5)))

Now I abstract over the local variable f and declare a new variable Y. The call to ((g g) 5) is replaced (g g) and moved to the Y function instead.

; A new variable Y is created for the abstraction over f.
; The function call is moved to the application of Y.
(let ((Y (lambda (f)
           (let ((g (lambda (h)
                      (lambda (n)
                        ((f (h h)) n)))))
             (g g)))))
  ((Y (lambda (q) 
        (lambda (m)
          (if (< m 2) 1 (* m (q (- m 1))))))) 5))

Finally we replace the local variable Y with a the function Y, the Y-combinator.

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

Excellent!