附录D：不动点组合子与递归（进阶选读）

本附录适合与第 4 章“求值策略”、第 5 章“类型系统核心概念”配合阅读。
如果你一时忘了“不动点”“发散”“传名调用 / 传值调用”“强正规化”这些术语，也可以先回查附录A“术语表”。
阅读时也建议把它和附录E“Church 编码”对照起来看：两者共同展示了未类型化 Lambda 演算的表达能力，只是一个侧重递归与不动点，另一个侧重数据与控制结构的函数编码。

前面的章节里，我们已经看到：

Lambda 演算的核心计算规则是 β-归约；
未类型化 Lambda 演算足以表达非常丰富的计算行为；
但在最基本的语法中，并没有“函数名字定义自己”的递归构造。

于是一个自然问题出现了：

如果语言里没有内建递归，递归函数是怎么表达出来的？

这就是本附录要讨论的主题：不动点组合子（fixed-point combinator）。

这部分内容对理解第五章以后的核心类型系统并不是必需的，但它非常值得一看，因为它展示了 Lambda 演算表达能力中最令人惊讶的一面：

递归并不一定需要语言原生提供；在未类型化 Lambda 演算中，它甚至可以被“编码”出来。

如果把它放回正文主线中看，那么本附录主要回扣三件事：

第 4 章：为什么求值策略会影响一个构造“是否按预期工作”；
第 5 章：为什么简单类型系统不会直接容纳这种一般递归能力；
附录E：为什么只靠函数本身，就已经能表达比直觉上更多的数据与计算结构。

D.1 什么叫“不动点”？

先不谈程序，先看一个更一般的数学概念。

如果一个对象 $x$ 满足：

$f (x) = x$

那么就说 $x$ 是函数 $f$ 的一个不动点（fixed point）。

直觉上，不动点就是：

被函数作用一次之后，结果仍然是自己。

例如，若某个函数把输入 3 仍然映射到 3，那 3 就是它的不动点。

这个概念之所以和递归有关，是因为递归函数本身常常可以写成一种“不动点方程”。

D.2 递归函数为什么和不动点有关？

考虑一个我们熟悉的递归定义，比如阶乘：

fact(n) =
  if iszero(n)
  then 1
  else times(n, fact(pred(n)))

这个定义的问题在于：右边出现了 fact 自己。

在很多真实语言里，这没有问题，因为语言直接支持具名递归定义。但在最基本的 Lambda 演算语法里，我们只有：

变量
抽象
应用

并没有“let rec fact = ...”这样的构造。

所以直接写“函数体里引用自身名字”这件事，并不是基础语法自带的能力。

更准确地说：

基础 Lambda 演算里没有原生的具名递归绑定。

这不意味着它“完全不能表达递归”，而是说：

不能直接靠名字写出自引用定义；
需要换一种方式，把“递归”转化成别的结构。

D.3 先把“递归函数”改写成“接受自身作为参数的函数”

上面的阶乘可以先改写成一个“递归生成器”：

factGen =
  λf. λn.
    if iszero(n)
    then 1
    else times(n, f(pred(n)))

这里的 factGen 不再直接调用自己。相反：

它接收一个参数 f
这个 f 表示“递归调用时要用的那个函数”

如果某个函数 g 满足：

$g = f a c tG e n g$

那么 g 就恰好是我们想要的递归函数。因为把 g 代入进去后，得到的正是：

对 n 判断是否为零；
否则递归调用 g 自己。

这时问题就转化成了：

如何找到一个 g，使得 $g = f a c tG e n g$ ？

而这正是不动点问题。

因为“找到一个 $g$ 使得 $g = F (g)$ ”本质上就是“找到函数 $F$ 的不动点”。

D.4 不动点组合子是什么？

不动点组合子就是这样一种 Lambda 项：

给定任意函数 f，它能构造出 f 的一个不动点。

最经典的不动点组合子是 Y 组合子：

$Y = λ f . (λ x . f (x x)) (λ x . f (x x))$

它的神奇之处在于：

$Y g ⟶^{*} g (Y g)$

这说明：

Y g 归约后会变成 g (Y g)
因而 Y g 在归约意义下表现得像 g 的一个不动点

要注意这里的表述边界：

更准确地说，Y g 与 g (Y g) 是通过归约相关联的，而不是简单的字面相等。

在形式语境里，最好把它理解为：

$Y g ⟶^{*} g (Y g)$

或者说二者在适当意义下是等价的，而不是把它写成“完全相同的文本”。

D.5 验证：为什么 `Y g` 会展开成 `g (Y g)`？

下面一步步验算。

从定义开始：

$Y g = (λ f . (λ x . f (x x)) (λ x . f (x x))) g$

先对最外层做一次 β-归约：

$⟶ (λ x . g (x x)) (λ x . g (x x))$

再归约一次：

$⟶ g ((λ x . g (x x)) (λ x . g (x x)))$

观察括号里的那一部分：

$(λ x . g (x x)) (λ x . g (x x))$

它正好就是前一步中的 Y g 展开结果。因此可写成：

$g (Y g)$

于是得到：

$Y g ⟶^{*} g (Y g)$

这就是不动点的核心结构。

D.6 用 `Y` 表达递归

既然 Y g 会展开成 g (Y g)，那么对前面的 factGen，就可以定义：

$f a c t = Y f a c tG e n$

直觉上：

factGen 描述“如果已经给你一个递归调用入口 f，那该怎么计算”
Y 负责把这个“需要递归入口的函数”变成真正自引用的递归函数

因此：

$f a c t = Y f a c tG e n ⟶^{*} f a c tG e n (Y f a c tG e n)$

而 Y factGen 本身就是 fact，所以它会表现得像一个真正递归定义的函数。

这就是“不动点 = 递归”的核心联系。

D.7 为什么这件事如此惊人？

因为在基础语法里：

没有 let rec
没有 fix
没有“函数名绑定到自己”这种专门机制

但仅仅靠：

抽象
应用
替换

就已经能表达递归行为。

这说明未类型化 Lambda 演算的表达能力非常强。它不是“少功能的玩具语言”，而是一个极简但极有表现力的计算模型。

D.8 关键边界：`Y` 与求值策略有关

这里必须特别小心一个非常重要的点：

标准 Y 组合子是否“按预期工作”，取决于求值策略。

这是学习不动点组合子时最常见的误区之一。

很多资料会直接写：

$Y g ⟶^{*} g (Y g)$

然后给人一种印象：只要有 Y，递归就“自动可用”。
但实际上，这里隐含了对归约方式的假设。

D.9 为什么 `Y` 在传名调用下可用？

先回忆第四章的区分：

传名调用：先展开外层应用，再按需计算参数
传值调用：先把参数算成值，再进行函数应用

对：

$Y g = (λ f . (λ x . f (x x)) (λ x . f (x x))) g$

在传名调用下，我们可以直接做最外层 β-归约，于是逐步得到：

$Y g ⟶^{*} g (Y g)$

如果 g 在函数体里只在需要的时候才使用递归结果，那么整个程序就能像递归一样工作。

这也是为什么标准 Y 组合子通常和传名调用语境联系在一起。

D.10 为什么 `Y` 在传值调用下会出问题？

在传值调用下，函数应用前必须先把参数算成值。

观察 Y 的结构：

$Y = λ f . (λ x . f (x x)) (λ x . f (x x))$

应用到 g 后得到：

$(λ x . g (x x)) (λ x . g (x x))$

这里要特别注意一个容易说错的细节：

$(λ x . g (x x))$

本身其实已经是一个值，因为在传值调用下，Lambda 抽象就是值。
真正的问题不在于“它还不是值”，而在于：

当外层应用继续展开后，
自应用结构 x x 会不断重新暴露出来；
于是求值会被反复拉回这个自展开模式，
还没来得及把一个“可正常使用的递归入口”稳定交给 g 的主体逻辑，就已经开始无限展开。

所以，更准确的说法是：
标准 Y 在传值调用下的问题，是自应用过早、过猛地被不断展开，而不是“参数本身不是值”。

更直观地说：

传名调用：先“把递归壳子展开一层”
传值调用：却试图“先把那个无限自展开的东西算完”

而那个东西本来就不会先算完。

所以标准 Y 在传值调用下通常不会按我们期望的方式产生可用递归，而是会过早地发散。

更稳妥的总结是：

标准 Y 组合子适合传名调用语境；在传值调用下，需要改造版本。

D.11 传值调用下的变体：`Z` 组合子

为适应传值调用，常用一个改造版：Z 组合子。

一个常见写法是：

$Z = λ f . (λ x . f (λ v . x x v)) (λ x . f (λ v . x x v))$

和 Y 比较，关键变化是：

不再直接把 x x 作为递归结果传给 f
而是包了一层额外的函数： $λ v . x x v$

这层额外的 λv 非常重要，因为它起到了延迟求值的作用。

D.12 为什么多包一层 `λv` 就能延迟求值？

这是理解 Z 的关键。

在传值调用下，Lambda 抽象本身就是值。因此：

$λ v . x x v$

会被视为一个已经准备好的值，而不会立刻去展开其中的 x x。

也就是说：

Y 里把 x x 直接暴露在应用位置，导致传值调用急着去算它；
Z 把它藏进一个函数体里；
于是只有当这个递归入口真正被调用到某个参数 v 时，x x 才会继续展开。

所以 Z 的核心技巧可以概括成：

把“递归自展开”包装进一层函数，以推迟它真正发生的时机。

这正是传值调用下递归编码所需要的。

D.13 `Z` 的直觉用途

如果把递归生成器写成：

$F = λ f . λn . \dots 用 f 做递归调用 \dots$

那么在传值调用语境下，更常见的写法是：

$f i x F = Z F$

这样得到的项在行为上就更接近我们期待的递归函数。

要注意，这里的“更接近”不是一句空话，而是强调：

Z 是为了配合传值调用设计的；
它修复的是标准 Y 在严格求值下“自应用结构过早反复展开”的问题。

D.14 与真实语言中的递归有什么关系？

真实语言通常不会要求程序员手写 Y 或 Z 组合子。
更常见的做法是，语言直接提供某种递归机制，例如：

let rec
fix
递归函数定义
对象 / 方法层面的自引用机制

从理论上看，这些机制往往都可以理解成“给语言加入一个求不动点的能力”。

在很多类型理论教材里会直接把递归写成一个显式构造：

$f i x t$

并赋予规则：

$f i x t ⟶ t (f i x t)$

这可以看成是“把求不动点的能力直接作为语言构造提供出来”，而不要求程序员手写 Y 或 Z。

这和 Y / Z 组合子的思想本质上一样，只是把“不动点”从编码技巧变成了语言原生构造。

所以更准确的说法是：

Y / Z 展示了递归可以被编码；而 fix 展示了递归也可以被原生提供。

D.15 与类型系统的关系：为什么 STLC 不直接接受它？

到这里你可能会问：

既然不动点组合子这么强，为什么第五章的简单类型系统里没有它？

原因在于，简单类型 Lambda 演算（STLC）有一个非常重要的性质：

良类型项总是强正规化的。

这正好回扣第五章的主线：第五章之所以能在那个最小核心上讨论类型安全、并保持一个相对干净的元理论图景，部分原因就在于我们还没有把“一般递归”直接加入对象语言。

也就是说：

所有良类型项都会终止；
不会出现像 Ω 那样的无限展开。

而递归的本质恰恰常常依赖“不一定终止”。
阶乘当然会终止，但一个一般递归机制必须允许我们表达那些可能无限循环的程序。

因此：

若把完整不动点组合子直接加入 STLC，
就会打破强正规化。

所以在类型化语言里，递归通常需要通过更仔细的扩展方式引入，而不能简单把未类型化的 Y 原封不动搬进去。
这也解释了为什么本教程正文没有在第 5 章的 STLC 核心中直接加入一般递归：那会改变该章所依赖的重要元性质，并把讨论重心从“最小安全核心”转移到“如何控制递归带来的额外复杂性”。

这也是为什么“不动点组合子”在未类型化 Lambda 演算中极其自然，而在类型系统里会变得更微妙。

D.16 本附录小结

本附录真正想建立的是下面这条主线：

基础 Lambda 演算没有原生具名递归定义。
但递归函数可以改写成“接受自身作为参数的生成器”。
于是“递归”转化成了“求某个函数的不动点”。
Y 组合子展示了：在未类型化 Lambda 演算中，不动点可以被编码出来。
但 Y 是否按预期工作，和求值策略密切相关：
- 传名调用下，标准 Y 可自然展开；
- 传值调用下，标准 Y 会过早发散。
Z 组合子通过多包一层 Lambda，延迟自展开，从而更适合传值调用。
真实语言中的递归构造，常可视为“把求不动点的能力原生加入语言”。

如果把本附录压缩成一句话，那就是：

递归本质上可以理解为“不动点”，而不动点组合子展示了 Lambda 演算如何仅凭函数本身表达递归。

如果你想把这条线继续延伸，比较自然的回看路径是：

回到第 4 章，重新看“传名调用 / 传值调用”与求值策略差异；
回到第 5 章，重新看 STLC、类型安全与强正规化的边界；
再对照附录E，体会未类型化 Lambda 演算如何同时编码“递归能力”和“数据表示能力”。

进一步思考

为什么把递归函数改写成“接受自身作为参数的函数”后，问题就变成了不动点问题？
Y g 与 g (Y g) 为什么更适合说成“通过归约相关联”，而不是简单地“字面相等”？
为什么传值调用会让标准 Y 提前发散？
Z 组合子里的额外 \lambda v 起到了什么作用？
为什么简单类型 Lambda 演算不能直接容纳完整的不动点组合子？

Keyboard shortcuts

编程语言理论与类型系统入门