spj’s y-combinator in scheme
Recently i bought a second-hand copy of Simon Peyton Jones’ classic The implementation of functional programming languages, and i’ve been having some very pleasant reading hours during the last week.
For instance, i’ve enjoyed Simon’s clear and to-the-point introduction to the lambda calculus and, more concretely, his really lucid explanation of the workings of recursion and the Y combinator. As a matter of fact, i’ve enjoyed it so much that i just wanted to briefly reproduce it here, paraphrased in my surely poorer style, just for the fun of it.
In the pure lambda calculus, there’s no direct way of defining a function that refers to itself: all you have is the ability to define anonymous lambda abstractions. Using Scheme’s syntax, that means that you can use lambda as much as you want, as in
((lambda (x) (+ 1 x)) 3)
but define (recursive or not) is not available. For instance, you cannot define a list-length recursive function like this:
(define list-length (lambda (lst) (if (null? lst) 0 (+ 1 (list-length (cdr lst))))))
the main problem being the appearance of list-length in the lambda expression’s body. So the general issue we want to solve is how to define a function f of the form
f = (... f ...)
without referring to f in the body. When all you have is lambda calculus, everything looks like a function: we can rewrite the right hand side of the above equation as a lambda application:
f = ((lambda (x) (... x ...)) f) := (h f)
where we’ve defined h := (lambda (x) (... x ...)). For instance, in our length example, h is the function
h = (lambda (x) (lambda (lst) (if (null? lst) 0 (+ 1 (x (cdr lst))))))
and we’re trying to solve the equation (h list-length) =
list-length. In other words, you give me h, a function taking a function as argument and returning another function, and i need to give you back an f that is its fixed point, i.e., an f satisfying f = (h f).
So all i need to do is finding a function (let’s call it Y) that takes h as its argument and returns f, that is, by definition of Y:
f = (Y h)
but, as we’ve seen f equals (h f), which in turn is (h (Y h)) which gives us the defining equation of Y:
(h (Y h)) = (Y h)
If i had that magic Y function (or combinator, since it won’t use any global variables), i could for instance immediately compute list-length as:
(Y (lambda (x) (lambda (lst) (if (null? lst) 0 (+ 1 (x (cdr lst)))))))
The nicest kind of wishful thinking is the one that comes true: we actually know of a lambda expression that satifies the Y combinator’s defining equation (Y h) = (h (Y h)), namely:
(lambda (h) ((lambda (x) (h (x x))) (lambda (y) (h (y y)))))
You can check it by yourself: (Y h) is just the body of the expression above:
(Y h) => ((lambda (x) (h (x x))) (lambda (y) (h (y y))))
and now apply the first lambda to its argument (the second lambda) to obtain:
=> (h ((lambda (y) (h (y y))) (lambda (y) (h (y y))))) => (h (Y h))
as desired! The only wrinkle left is that, as defined, our Y combinator cannot be directly coded in Scheme, because Scheme is a strict language and those pesky (x x) and (y y) applications cause an infinite recursion.
But that’s just an accidental difficulty due to Scheme’s evaluation strategy being too eager that has a standard solution: a beta abstraction. If you have a function F in Scheme, you can define a totally equivalent function G by (define G (lambda (x) (F x))). We say that G is a beta abstraction of F, or that F is a beta reduction of G. And the usual reason you would beta abstract a function in Scheme is in order to delay the evaluation of its body, just what the doctor ordered.
Remember, h is a function taking another function as an argument, so (x x) and (y y), which are used as h’s arguments, must be functions, so they’re equivalent to (lambda (a) ((x x) a)) and (lambda (a) ((y y) a)), so we can define Y, if we’re so inclined, also as:
(define Y (lambda (h) ((lambda (x) (h (lambda (a) ((x x) a)))) (lambda (x) (h (lambda (a) ((x x) a)))))))
and now
(define list-length (Y (lambda (f) (lambda (lst) (if (null? lst) 0 (+ 1 (f (cdr lst))))))))
As you see, list-length’s body doesn’t mention itself and, as you can check by yourself with your favourite interpreter, the last two definitions are valid and working scheme code.
In case you still feel a bit unsure as to how our Y is pulling its trick, you can dispel any misgivings just by seeing how the combinator transforms the given h step by step, always reproducing h in the process (it’s only the branch in h that doesn’t call its argument, the recursion’s base case, that breaks the implicit infinite loop induced by Y). Let’s do it with our list-length example, reducing its application to, say, the list ’(1 2), step by step:
(define W (lambda (f) (lambda (a) ((f f) a)))) (list-length '(1 2)) ;; definition of list-length as (Y h) => ((Y h) '(1 2)) ;; definiton of Y and W => (((lambda (f) (h (W f))) (lambda (f) (h (W f)))) '(1 2)) ;; beta-reduction of the first lambda applied to the second => ((h (W (lambda (f) (h (W f))))) '(1 2)) ;; definition of h for the case of list-length => ((lambda (lst) (if (null? lst) 0 (+ 1 ((W (lambda (f) (h (W f)))) (cdr lst))))) '(1 2)) ;; function application => (+ 1 ((W (lambda (f) (h (W f)))) '(2))) ;; definition of W => (+ 1 (((lambda (f) (h (W f))) (lambda (f) (h (W f)))) '(2)))
and notice what just happened: we started with
(((lambda (f) (h (W f))) (lambda (f) (h (W f)))) '(1 2))
and, after one iteration of the implicit recursion, reduced it to:
(+ 1 (((lambda (f) (h (W f))) (lambda (f) (h (W f)))) '(2)))
i.e., 1 plus the same form we started with but applied to the list (2) instead of the list (1). By following the exact same reduction steps, we can simplify the above to:
(+ 1 1 (((lambda (f) (h (W f))) (lambda (f) (h (W f)))) '()))
and now, when expanding the same form to the right applied to the empty list, the base case of the recursion (the true branch of the (null? lst) test in h), will kick in and reduce the above to
(+ 1 1 0) => 2
avoiding that the self-reproducing Y forms keep reappearing ad infinitum.