Y combinator

下面这整个过程实际大部分来自 The Little Schemer¹ 这本书，沿着原书的路径，最终揭开结果的时候，有种悬疑解密的感觉，非常推荐阅读。

阶乘函数²可以通过递归方式定义：

(define fact
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

(fact 10)                               ;=> 3628800

函数体内使用 fact 这个名字进行了自指，即

define 将 lambda 函数绑定到了 fact, 且
我们在 lambda 函数中使用了 fact 这个名字，它指向这个 lamdba 函数本身

我们知道，lambda 本身就能进行名字与值的绑定：

((lambda (x) x) 42)

上面的函数调用中，在 lambda 体内, x 被绑定到其参数。那么不使用 define来进行 fact 函数的递归定义的话，我们同样可以使用参数来进行绑定：

(lambda (fact n)
  (if (zero? n)
      1
      (* n (fact (- n 1)))))

这里期望参数 fact 指代的的是这个 lambda 函数自身。注意到现在函数体内的 fact 调用只有一个参数，它的第一个参数应该是这个 lambda 函数自身，而在这个函数体内，这个函数自身可以直接使用 fact 引用：

(lambda (fact n)
  (if (zero? n)
      1
      (* n (fact fact (- n 1)))))

要求 10 的阶乘的话，得考虑其第一个参数是什么：

((lambda (fact n)
   (if (zero? n)
       1
       (* n (fact fact (- n 1)))))
 ...
 10)

上面已经说过，其第一个参数期望是这个 lambda 函数自身，不过其实更准确来说，我们期望第一个参数是这个 lambda 函数表示的那个计算就行。这样，我们拷贝一下代码就能满足要求：

((lambda (fact n)
   (if (zero? n)
       1
       (* n (fact fact (- n 1)))))
 (lambda (fact n)
   (if (zero? n)
       1
       (* n (fact fact (- n 1)))))
 10)                                    ;=> 3628800

不过对同一个东西多次引用，直接使用 lambda 参数绑定在函数体内多次使用也能达成（正如上面函数体内对 fact 的使用）：

((lambda (f)
   (f f 10))
 (lambda (fact n)
   (if (zero? n)
       1
       (* n (fact fact (- n 1))))))

上面的 fact 函数有两个参数，可以做一下转换将其变成只有一个参数：

((lambda (f)                            ;<- 3. f 是 fact 指代的 lambda 函数
   ((f f) 10))                          ;<- 4. f 的调用方式和 fact 一致
 (lambda (fact)                         ;<- 1. fact 参数指代的是这一层 lambda 函数
   (lambda (n)                          ;<- 2. (fact fact) 得到这一层 lambda 函数
     (if (zero? n)
         1
         (* n ((fact fact) (- n 1))))))) ;=> 3628800

上面这个 fact 名字已名不副实，实际 (fact fact) 才表示阶乘函数，不妨重命名一下：

((lambda (f)
   ((f f) 10))
 (lambda (make-fact)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((make-fact make-fact) (- n 1))))))) ;=> 3628800

再用 lambda 的参数绑定给出一个 fact:

((lambda (f)
   ((f f) 10))
 (lambda (make-fact)
   ((lambda (fact)
      (lambda (n)
        (if (zero? n)
            1
            (* n (fact (- n 1))))))
    (make-fact make-fact))))

到这一步，执行会发现进入了死循环。考虑下，目前这种定义方式，当计算 10 的阶乘时，在进入阶乘函数之前，需要先构造出这个函数（应用序, applicative-order 要求我们优先计算 (make-fact make-fact), 即调用函数要先计算其参数）。

可以延迟下这个函数构造的行为：

((lambda (f)
   ((f f) 10))
 (lambda (make-fact)
   ((lambda (fact)
      (lambda (n)
        (if (zero? n)
            1
            (* n (fact (- n 1))))))
    ;; 对于只有一个参数的函数 f 来说, f 和 (lambda (n) (f n)) 的行为一致
    (lambda (n) ((make-fact make-fact) n))))) ;=> 3628800

这时候，我们可以把 (lambda (fact) ...) 完整的取出来：

((lambda (h)
   ((lambda (f)
      ((f f) 10))
    (lambda (make-fact)
      (h (lambda (n) ((make-fact make-fact) n))))))
 (lambda (fact)
   (lambda (n)
     (if (zero? n)
         1
         (* n (fact (- n 1)))))))

make-fact 重命名为 f 的话：

((lambda (h)
   ((lambda (f)
      ((f f) 10))
    (lambda (f)
      (h (lambda (n) ((f f) n))))))
 (lambda (fact)
   (lambda (n)
     (if (zero? n)
         1
         (* n (fact (- n 1)))))))

注意到上面，最终的执行结果是 ((f f) 10), (f f) 正是 fact 函数，如果我们不作调用，恰可以直接返回 fact 函数：

((lambda (h)
   ((lambda (f) (f f))
    (lambda (f) (h (lambda (n) ((f f) n))))))
 (lambda (fact)
   (lambda (n)
     (if (zero? n)
         1
         (* n (fact (- n 1)))))))

其中的我们已经得到 Y-combinator³ (更准确来说 applicative-order Y-combinator):

(lambda (h)
  ((lambda (f) (f f))
   (lambda (f) (h (lambda (n) ((f f) n))))))

;; 不考虑应用序的话，它即
(lambda (h)
  ((lambda (f) (f f))
   (lambda (f) (h (f f)))))

整理，并添加一个示例的话：

(define y
  (lambda (h)
    ((lambda (f) (f f))
     (lambda (f) (h (lambda (n) ((f f) n)))))))

((y (lambda (fact)
      (lambda (n)
        (if (zero? n)
            1
            (* n (fact (- n 1)))))))
 10)                                    ;=> 3628800

;; 你可以定义任意递归函数，比如试试斐波那契函数
((y (lambda (fib)
      (lambda (n)
        (cond [(= n 1) 1]
              [(= n 2) 1]
              [else (+ (fib (- n 1)) (fib (- n 2)))]))))
 10)                                    ;=> 55

Footnotes:

https://mitpress.mit.edu/9780262560993/the-little-schemer/

https://www.wikiwand.com/en/Factorial

https://www.wikiwand.com/en/Fixed-point_combinator#Y_combinator