[racket] Y combinator

For me, I didn't fully appreciate the Y combinator until I had had an
opportunity to play with and explore other combinators.

The book that made this fun for me was "To Mock a Mockingbird", a puzzle
book by Raymond Smullyan.

Chapters 9 and 10 give you all the building blocks you need to appreciate
the Y combinator, but if you can make it to chapter 13, you'll then
understand several different ways to achieve the same effect.

The combinators are described playfully in terms of birds.
M is the mockingbird, following the rule: Mx = xx
(define M (λ (x) (x x)))

L is the lark, following the rule:
Lxy = x(yy)
(define L (λ (x) (λ (y) (x (y y)))))

B is the bluebird:
Bxyz = x(yz)
(define B (λ (x) (λ (y) (λ (z) (x (y z))))))

Sage birds (θ) are birds that produce fixed points:

x(θx) = θx

All sage birds can be used to do the recursive trick that you can do with
the Y combinator.

The Y combinator basically corresponds to the following way of creating a
sage bird:
Y = BML

(define Y ((B M) L))

As others have already pointed out, this doesn't quite work unless you're
in a lazy language.  You need to redefine the lark as follows, turning (y
y) into the equivalent, but delayed (λ (z) ((y y) z)):

(define L (λ (x) (λ (y) (x (λ (z) ((y y) z))))))

Summary:
(define M (λ (x) (x x)))
(define L (λ (x) (λ (y) (x (λ (z) ((y y) z))))))
(define B (λ (x) (λ (y) (λ (z) (x (y z))))))

(define Y ((B M) L))

I find it much easier to think of the Y combinator this way, built up from
easy-to-understand components (at least the components are easy to
understand after you've played around for hours with puzzles that use them).

Definitely check out the Smullyan book, it's very enjoyable.

Mark
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140206/d261ec7b/attachment.html>