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.
