;;; Let's jump right in. The first form may look a little murky at ;;; first because of the extra lambda. Try to trace what happens when ;;; you evaluate ((fact1 fact1) 10); you should get ;;; (* 10 ((fact1 fact1) 9)) and so on. As you think of this, note ;;; the crucial (h h) at the end. Why is it necessary? (define fact1 (lambda (h) (lambda (n) (if (= n 1) 1 (* n ((h h) (- n 1))))))) ;;; So that works and could certainly serve as the answer to, "How do you do ;;; recursion with just lambdas?" But what if we really want to take this, (define F (lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1))))))) ;;; and turn it into a recursive function. Observe that if we already had ;;; a working factorial function 'fact' then, ;;; (F fact) ---> fact. ;;; So F is waiting for the right function to bootstrap itself! ;;; The Y combinator is the magic that takes us there. ;;; (Y F) ---> fact ;;; In other words Y provides a fixed point of F because, ;;; (F (Y F)) ---> (Y F) ;;; To frustrate the novice, we should say here, "The rest is just ;;; currying!" First go back to fact1 again and remove the troublesome ;;; (h h) by adding another lambda. (define fact2 (lambda (g) ((lambda (h) (lambda (n) (if (= n 1) 1 (* n (h (- n 1)))))) (lambda (m) ((g g) m))))) ;;; This is by no means the only natural way to proceed, but ;;; unfortunately here all roads don't lead to Rome. Next we look ;;; for the correct argument to fact2. We want, ;;; ((fact2 A) 10) = 10! ;;; or ((fact2 A) 10) ---> (* 10 ((A A) 9)) ;;; So the right A is... fact2! Indeed ((fact2 fact2) n) works. ;;; Cleaning up a little, (define fact3 (lambda (g) (F (lambda (m) ((g g) m))))) ;;; and finally, (define fact ((lambda (g) (F (lambda (m) ((g g) m)))) (lambda (g) (F (lambda (m) ((g g) m)))))) ;;; is the factorial function. Now it is clear that the Y combinator should be, (define Y (lambda (f) ((lambda (u) (f (lambda (x) ((u u) x)))) (lambda (v) (f (lambda (x) ((v v) x))))))) ;;; This is also called the Turing fixed point combinator. How ;;; pleasing and symmetric it looks! For greater obscurity, we could ;;; also compress it as, (define Yobs (lambda (f) ((lambda (f) (f f)) (lambda (u) (f (lambda (x) ((u u) x))))))) ;;; which has the effect of inducing a powerful headache.