Y-Combinator——递归从哪里来

一个连名字都没有的函数，怎么调用自己？Y-Combinator 不给它取名，而是给它一个不动点。

上一篇《Lambda 演算——用函数表达一切计算》里，我们把数、布尔、条件都写成了匿名函数。但有一件事当时刻意绕开了：递归。

你写阶乘时是这样的：

(define (fact n)
 (if (zero? n)
 1
 (* n (fact (sub1 n)))))

注意函数体里出现了 fact——它自己的名字。这在普通语言里天经地义，但在纯 λ 演算里行不通：那里只有匿名函数和应用，连 define 都没有。一个没有名字的函数，怎么调用自己？

这个问题逼出来的答案叫 Y-Combinator。 递归不是语言的恩赐，是只要有函数就必然存在的东西——这一讲就来把它推导出来。

函数有名字，才能调用自己

普通语言里的递归，立在两根柱子上：函数有个名字，函数体可以引用这个名字。抽掉这两根，你就落进了 λ 演算。

为了在无名世界里谈论“一个像阶乘的东西”，我们把它写成一个吃 self 参数的函数——self 是“将来的那个递归函数”的占位符：

F ≡ λself. λn.
 IF (isZero n)
 1
 (mul n (self (pred n)))

F 还不是阶乘。它是一个生成器：给它一个行为像阶乘的 self，它就吐回阶乘函数。把真正的阶乘喂给它当 self，它就还你真正的阶乘——绕，但精确。

所以我们想要的那个 FACT，得满足：

FACT = F FACT

整个问题，就浓缩在这一行里。

把递归写成一道方程

数学里，函数 f 的不动点是一个值 X，满足 X = f X。比如 x = cos x 就有一个不动点（大约 0.739）。对我们的 F 来说，不动点是一个“等于 F 作用于自己”的函数——恰好就是那个会递归的阶乘。

要是手上有个算子 Y，吃任意 g、吐出它的不动点：

Y g = g (Y g)

那么 FACT = Y F 立刻成立，因为 Y F = F (Y F)——Y F 正是 F 的不动点。

于是问题塌缩成一件事： 构造这样一个 Y。

让表达式指向自己

我们要 X 满足 X = g X。窍门是自我应用——让一个函数作用在它自己身上。试这样一个项：

W ≡ λx. g (x x)

把 W 作用在它自己身上：

W W
= (λx. g (x x)) W
→β g (W W)

x 被绑成 W 自己，于是 x x 又重新造出了 W W，W W 又造出 g (W W)——一个无限展开的结构已经成型了。 这叫自我应用——表达式在自己内部又复制出一个自己。不动点的形状，到这里已经齐了：W W = g (W W)。

包进一个 λg，就是 Y

W 依赖 g。把它整个包进一个 λg 里参数化，就得到完整的 Y：

Y ≡ λg. (λx. g (x x)) (λx. g (x x))

一次 β-约化就能验算。把 Y 作用到某个 g 上：

Y g
= (λg. (λx. g (x x)) (λx. g (x x))) g
→β (λx. g (x x)) (λx. g (x x))
→β g ( (λx. g (x x)) (λx. g (x x)) )
= g (Y g)

Y g = g (Y g)，正是我们想要的不动点方程。（这次约化默认了一件小事：先约最外层。记住这处伏笔。）

在 Racket 里跑，却卡死了

把 Y 翻译进 Racket，试一试：

;; 教科书里的 Y，照搬到 Racket
(define Y
 (λ (g)
 ((λ (x) (g (x x)))
 (λ (x) (g (x x))))))

;; (Y g) ; 别真跑：应用序会立刻展开 (x x)，无限递归

Racket 会卡死或撑爆栈。原因是 Racket 采用应用序（call-by-value）：调用函数前，先把参数求值干净。于是算 (g (x x)) 之前，它非得先把 (x x) 求出来——而 (x x) 一展开又是 (g (x x))，又得先求 (x x)……永远不停。

正则序（normal order）则相反：最外层先约，参数用到才算。所以 g (Y g) 里的 Y g 一直挂着不求值，只有当 g 的函数体真要用到它（也就是递归那一支）时才展开；碰到 base case 直接返回，根本不碰它，递归自然终止。 正则序只在需要时才展开它，应用序一上来就展开——这就是教科书里的 Y 在 Racket 里跑不动的全部原因。

同样的坑，会绊倒所有严格求值的语言：Scheme、OCaml、Python，无一幸免。

套一层延迟，绕过应用序的陷阱

修法是把自我应用延迟一下——多套一层 λv，把 (x x) 包成一个还没求值的函数。原本的 g (x x) 改写成 g (λv. (x x) v)。这样传给 g 的参数已经是一个现成的函数值，应用序满意了；(x x) 只有在 g 真把这个函数应用到某个 v 上时才会触发。

这个包壳的手法叫 η-展开（eta-expansion），结果就是 Z 组合子：

Z ≡ λf. (λx. f (λv. (x x) v))
 (λx. f (λv. (x x) v))

这里有个最容易写错的细节。在应用序下，Z f 是这样约化的：

Z f
→β f (λv. ( (λx. f (λv. (x x) v)) (λx. f (λv. (x x) v)) ) v)
= f (λv. (Z f) v)

也就是说，严格写下来 Z f 约化到的是 f (λv. (Z f) v)，而不是 f (Z f)。 这层多出来的函数就是延迟开关：它和 f (Z f) 只差一个 η-约简，但正是这个 η 让应用序拿到的始终是一个现成的函数值，而不是还要继续展开的 (Z f)——否则就又卡死了。

让阶乘真正跑起来

有了 Z，阶乘终于能在 Racket 里跑：

#lang racket

;; Z 组合子：适用于应用序的不动点组合子
(define Z
 (λ (f)
 ((λ (x) (f (λ (v) ((x x) v))))
 (λ (x) (f (λ (v) ((x x) v)))))))

;; 阶乘生成器：吃一个 self（将来的递归函数），返回阶乘函数
(define fact-gen
 (λ (self)
 (λ (n)
 (if (zero? n)
 1
 (* n (self (sub1 n)))))))

;; 真正的阶乘 = Z 作用于生成器
(define fact (Z fact-gen))

(fact 5) ; => 120
(fact 10) ; => 3628800

追一层看清楚：(Z fact-gen) 约化成 fact-gen 作用在一个 thunk λv. ((x x) v) 上，这个 thunk 就是 self。算 (fact 5) 时走到 (* 5 (self 4))，调用 (self 4) 才把 thunk 强制求值——它重新造出 fact-gen 作用在一个崭新的 thunk 上，递归就这么一层层下去了。每一层都现造一个 self，谁也不必先认识谁。

真写 Racket 你当然不会这么干——define 和命名的 let 就是为了不必这么干而存在的。但你能这么干，这件事本身就是重点。

当你把递归看成一道不动点方程，把名字看成可有可无的语法糖，“函数自己调用自己”就不再是某门语言的恩赐，而是 λ 演算一开始就藏在兜里的东西。