lambda calculus · β-归约单步

在没有名字的世界里，把递归「造」出来

阅读本页需要对 lambda 演算的基本记法（变量、抽象、应用、β-归约）有初步了解。内容顺着 canonical 的启发式推导展开，把每个部件都拆解成可单步观察的形式，五节依次是消除自引用、Omega 组合子、组装-Y、Z 组合子及其同类、Y 组合子的用处。全程使用一个完整的 β-归约引擎（capture-avoiding 替换加 normal-order 单步），点一次，归约一步。

1 · 递归的本质：先把「名字」拆掉

一个递归函数靠名字引用自己。可 lambda 演算里函数都是匿名的，没有名字可引用。要在匿名世界里实现递归，第一步就是想清楚：怎样在不提自己名字的前提下，还能调用到自己？答案直接，而它正是 Y 组合子里那个 x x 的来历。

1.1 · 名字是怎么混进来的

阶乘 fact 的函数体里写了 fact 自己，这就是自引用。

图 1-1 · 把名字抽成参数的过程。可单步观察 fact 如何变成一个接收 self 的骨架，以及调用时 self(self) 怎样补回缺失的那一层。

self(self) 这个形状值得记住：它是「在没有名字时仍能拿到自己」的关键手段。下一节把它单独提取出来——x => x(x) 就是 Omega 组合子，无限循环的最小编码，也是 Y 组合子的核心部件。

2 · Omega 组合子：x x 凭空造出无限

上一节得出匿名递归的核心是 self(self)。把它单独提取出来——一个函数把自己作用到自己身上——就是 lambda 演算里最有名的项 Omega。它不产出任何结果，却能无限归约下去，是「无限循环」在 lambda 演算里的最小编码。Y 组合子就是从它改造而来。

2.1 · ω 与 Ω

把自我应用写成函数，就是 $\omega$ （小 omega）；让 $\omega$ 作用到自己身上，就是 $\Omega$ （大 Omega）。

图 2-1 · Ω 的归约。可反复单步，看它每一步都回到自身、永远归约不完。

把 $\omega = \lambda x.x\,x$ 里的 $x\,x$ 换成 $F\,(x\,x)$ ，自我应用就变成「每展开一层都交给 $F$ 处理一次」。于是 $Y = \lambda F.\,(\lambda x.F(x\,x))\,(\lambda x.F(x\,x))$ ——Y 组合子就是受 $F$ 控制的 Omega。下一节把它拼出来，单步看它如何把递归展开成 $F(F(F(\dots)))$ 。

3 · 组装 Y 组合子

前两节备齐了所有部件：把名字抽成参数 (open recursion)、self(self) 自我应用、把 $x\,x$ 作为参数传给 $F$ 构成受控循环。把它们组合起来，就是 Y 组合子。

3.1 · 不动点：Y 到底在求什么

回到第 1 节那个 $fact_0 = f \mapsto n \mapsto \dots$ 。真正想要的那个阶乘函数 fact，恰好满足 $fact_0(fact) = fact$ ——输入 fact、输出仍是 fact。这种「作用一下不变」的点叫不动点 (fixed point)。

图 3-1 · Y f 的逐层展开。第一步变成 (λx.f(x x))(λx.f(x x))，再一步就析出 f (…)，而括号里的部分又是 Y f 本身。

于是 $Y f = f (Y f) = f (f (Y f)) = f(f(f(\dots)))$ ，不动点方程成立。每个 $f$ 对应递归的一层；真正计算 fact 时，base case（n < 2）会在某一层终止这条链，于是它能够停下来。

3.2 · 在 JavaScript 里直接运行会栈溢出

上面的符号归约用的是 normal order，需要时才展开。而 JavaScript 是 call-by-value：调用 f(x(x)) 前，必须先把 x(x) 求出来，而 x(x) 又触发 f(x(x))，在到达 base case 之前就抛出 RangeError。

警示 · 因此教科书里的 $Y = \lambda f.(\lambda x.f(x\,x))(\lambda x.f(x\,x))$ 在 JS 等多数严格求值语言里无法运行。下一节用 η-展开把它改成可正常运行的 Z 组合子，并当场算出 fact(5) = 120。

4 · 让它真正运行：Z 组合子及其同类

纯 Y 在 JavaScript 里会栈溢出，一步 η-展开就能让它正常运行，这就是 Z 组合子。更进一步：能充当「不动点制造机」的组合子不止一个，而是有无限多个。

4.1 · η-展开：把求值延后一下

问题出在 call-by-value 会提前求出 x(x)。解决办法是把它包进一个尚未被调用的函数里，写成 y => x(x)(y)——只要没有传入 y，x(x) 就不会提前展开。这一步在 lambda 演算里称为 η-展开，即 $f \equiv \lambda y.\,f\,y$ 。

图 4-1 · Z、图灵组合子与 Y₃ 的实际运行。可切换组合子算阶乘与斐波那契，验证三者给出同一个递归函数。

4.2 · 无限多个不动点组合子

Y 里「对无限链开平方 $f = G\,G$ 」这一步是任意的选择。换一种分解方式，就得到一个新组合子——它们全都满足 $T\,g = g\,(T\,g)$ ，因此都是合法的不动点制造机。

表 4-1 · 四个不动点组合子，差别只在如何分解那条无限链。
组合子	分解思路	lambda 形式
Y (Curry)	开平方 `f = G G`	λf.(λx.f (x x)) (λx.f (x x))
Θ (Turing)	展开两层再开方	(λt f.f (t t f)) (λt f.f (t t f))
Y₃	开立方 `f = G G G`	λf.(λx.x x x) (λx y.f (x y x))
Tromp	夹心 `f = G g G`	(λx y.x y x) (λy x.y (x y x))

同一种思路（对 $g(g(g\dots))$ 这条无限链以不同方式分解）能生成无穷无尽的不动点组合子。开几次方、是否夹心，均可自由选择。

注 · 还有一条造新组合子的通路：给定任意不动点组合子 $Y$ ，取 $F = \lambda x.\lambda y.\,y\,(x\,y)$ ，则 $Y F$ 又是一个不动点组合子。验证只需一步——由不动点性质 $Y F = F (Y F) = \lambda y.\,y\,((Y F)\,y)$ ，正是所求。反复施加就得到一列组合子（Böhm 序列）。但要当心一个常见说法：把 Curry 的 $Y$ 代进去得到的 $Y F$ ，与图灵组合子 $\Theta$ 并不是同一个项。用本页的归约引擎各自作用到变量 $g$ 上可以看到，两者展开出的确实是同一棵无限树 $g(g(g\dots))$ ，可每一步的剩余项结构不同——它们同为不动点组合子、Böhm 树相同，而非彼此的另一种写法。

5 · Y 组合子的用处

现实里写代码几乎用不到 Y，语言早就内置了具名递归 (function / let rec)。但 Y 揭示的那个结构——open recursion，把「自己」留成参数——是真有用的工程模式；而 Y 本身则是类型系统、可计算性、甚至一家创投公司名字背后的那块基石。

5.1 · 在递归点插桩

当 self 不写死、而是由外部注入时，就能在每一次递归调用上做拦截：加缓存、加日志、换 base case，全程不修改原骨架。

图 5-1 · 给指数级的 fib 骨架注入 memo。可开关装饰，观察调用次数如何显著下降。

同一个 fib0 骨架，套上不同装饰就获得了 memo 与 trace 的能力——这正是 React 的 useMemo、各种 @memoize 装饰器、可观测性插桩背后共同的思路：让递归点对外开放，行为从外部注入。Y 与 fix 只是把这一思路推到了极致。

5.2 · 语言直接提供 letrec

几乎所有语言都内置了具名递归，本质是 letrec (let-recursive)。可以把它理解为「编译器或运行时替开发者调用了 fix」：let rec f = … f … 脱糖后就是 $f = fix(\lambda f.\ \dots f \dots)$ 。

表 5-1 · 三种语言的具名递归写法与它对应的不动点形式。
语言	具名递归写法	等价于
JavaScript	`function f(){ … f() }`	`f = fix(self => … self() …)`
OCaml / F#	`let rec f = … f …`	`f = fix (fun f -> … f …)`
Haskell	`f = … f …`（惰性，直接自指）	`f = fix (\f -> … f …)`

Haskell 的 Data.Function.fix 就是一个现成的不动点算子。

警示 · 常听到「Haskell 靠惰性求值就能直接写纯 Y」，这话只说对了一半。惰性解决的是求值顺序问题（不会像 JS 那样提前展开 x x 而栈溢出），但类型问题照旧：y f = (\x -> f (x x)) (\x -> f (x x)) 在 GHC 里过不了类型检查，报的正是 occurs check，与下一节说的 $X = X \to Y$ 无解是同一回事。要写出来得先用 newtype Rec a = Rec (Rec a -> a) 把自我应用包一层。

5.3 · 类型系统为什么拒绝 Y

在 simply-typed lambda calculus（以及 TS 这类系统）里，x x 写不出合法类型——要给 x 标类型，就会得到 $X = X \to Y$ 这种无限递归的方程，无解。这不是 bug，而是定理：STLC 强规范化，任何程序都会停机，而 Y 能造出不停机的程序，所以它必然被类型系统拒之门外。

语言的解法是另设一条通路：要么允许 recursive types（type Rec = (r: Rec) => …，TS 里给 x x 显式标注这种递归类型即可通过编译），要么内置一个原语 fix（类型为 $(a \to a) \to a$ ）。换言之，递归的能力要么由类型系统明确许可，要么经由 Y 这条途径绕过类型系统获得。

5.4 · 那家叫「Y Combinator」的公司

硅谷知名的创业孵化器 Y Combinator (YC)——Dropbox、Airbnb、Stripe、Reddit 均出自其门下——名字就取自这个组合子。创始人 Paul Graham 是 Lisp 程序员，他说选这个名字是因为「Y 组合子是一个能产出其他程序的程序」，而 YC 想做的是「一家能孵化出其他公司的公司」，一个关于自我再生的双关。

6 · 整体串联

消除名字把自引用抽成参数 (open recursion)，x x 让函数自己应用自己、补回缺失的那一层，把 x x 传给 $F$ 就构成了受控的无限循环，也就是 Y，它求的是不动点 $Y g = g(Y g)$ 。Z 用 η-展开让它在严格求值语言里正常运行，而「开几次方」的任意性意味着不动点组合子有无限多个。最终结论：递归不是语言的基本能力，而是能从匿名函数中涌现出来的特性。