the-little-schemer/chapter-09-y-combinator/other-explanation.scm

;;; Source: https://www.ocf.berkeley.edu/~abhishek/ycode.html

;;; 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.