lambda calculus · β-归约单步

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

阅读本页需要对 lambda 演算的基本记法（变量 / 抽象 / 应用、β-归约）有初步了解。内容顺着 canonical 的启发式推导展开，把每个部件都拆解成可单步观察的形式： $消除名字 \to x x 自我应用 \to 组装 Y \to 可运行的 Z / 无限多组合子 \to 它有什么用$ 。全程使用一个完整的 β-归约引擎（capture-avoiding 替换 + normal-order 单步），点一次，归约一步。五节顺序阅读：消除自引用 → Omega 组合子 → 组装 Y → Z 组合子及其同类 → Y 组合子有什么用。

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

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

1.1 · 名字是怎么混进来的

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

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

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

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

2.1 · ω 与 Ω

把「自我应用」写成函数，就是 ω（小 omega）；让 ω 作用到自己身上，就是 Ω（大 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。组装 Y一节把它拼出来，单步看它如何把递归展开成 $F(F(F(\dots )))$ 。

3 · 组装 Y 组合子：看它把递归展开成 f(f(f(…)))

消除自引用与 Omega 组合子两节备齐了所有部件：把名字抽成参数(open recursion)、self(self) / x x（自我应用）、把 x x 作为参数传给 F（受控循环）。把它们组合起来，就是 Y 组合子。本节直接观察它——单步看 Y f 如何逐层展开出 $f (f (f (\dots )))$ 。

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

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

第一步 Y f 变成 $(\lambda x.f(x x))(\lambda x.f(x x))$ ；再一步就析出 $f (\dots )$ ——而括号里的部分又是 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 组合子一节用 η-展开 把它改成可正常运行的 Z 组合子，并当场算出 fact(5)=120。

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

纯 Y 在 JavaScript 里会栈溢出。一步 η-展开就能让它正常运行——这就是 Z 组合子。更进一步：能充当「不动点制造机」的组合子不止一个，而是有无限多个。本节让 Z / 图灵组合子 / Y₃ 实际运行，算出阶乘、斐波那契，并验证它们给出同一个递归函数。

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

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

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

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

组合子	分解思路	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)$ ，则 T = Y F 又是一个新的不动点组合子（因为 F 的作用恰好是「在两侧对称地多套一层 g」）。特别地，把 Curry 的 Y 代入，Y F 正好就是图灵组合子 Θ。组合子由此一个接一个地不断衍生出来。

这套不动点的工程价值，见 Y 组合子有什么用一节。

5 · Y 组合子到底有什么用？

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

5.1 · 真正有用的是 open recursion：在「递归点」插桩

当 self 不写死、而是由外部注入时，就能在每一次递归调用上做拦截——加缓存、加日志、换 base case——全程不修改原骨架。下面给指数级的 fib 骨架注入 memo，观察调用次数显著下降：

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

5.2 · 现实中：语言直接提供 letrec

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

语言	具名递归写法	等价于
JavaScript	`function f(){ … f() }`	$f = fix(self => \dots self() )$
OCaml / F#	$let rec f = \dots f \dots$	$f = fix (fun f -> \dots f \dots )$
Haskell	$f = \dots f \dots$ （惰性，直接自指）	`f = fix (\f -> … f …)`

Haskell 的 Data.Function.fix 就是一个现成的不动点算子；依靠 lazy evaluation，它甚至能写成纯 Y 的形式而不会栈溢出。

5.3 · 类型系统：为什么 Y 在 TypeScript 里无法标注类型

在 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 用 η-展开让它在严格求值语言里正常运行，而「开几次方」的任意性意味着不动点组合子有无限多个。最终结论：递归不是语言的基本能力，而是能从匿名函数中涌现出来的特性。