从匿名函数到 Y 组合子：一场关于递归的推导

如果函数没有名字，还能编写递归吗？在 RubyConf 2012 上，Jim Weirich 用一场现场编程回答这个问题：把阶乘的具体规则与递归机制拆开，最终从匿名函数构造出一个固定点组合子。演讲一开始就提醒听众，这不是一套推荐用于日常生产代码的 Ruby 写法；它是一次理解计算基础的练习。

Weirich 先介绍图灵机：一条可读写的纸带、一颗读写头和一组简单的状态转换规则，就可以描述复杂的计算过程。他展示了一段执行二进制计数的图灵机动画：读到一时擦除并进位，直到找到可以写入的位置。图灵的思路是把“什么能被算法计算”放进一个足够简单的模型里讨论。 观看 03:31

Alonzo Church 的 λ 演算提供了另一种计算模型：基本材料只有函数和函数应用。λx.x 是恒等函数，接收一个值，再把它原样返回。函数调用时，把参数替换到函数体中的过程称为 β 归约；实际进行替换时，需要避免变量名意外捕获。 观看 06:50

07:10查看原图

没有内建数字也能表示数字。Church 数字把数字编码成“把函数 f 应用于 x 多少次”：零是不应用，一应用一次，二应用两次。布尔值也可以是函数：true 接收两个参数并返回第一个，false 返回第二个。将 true 应用于一和零，依次替换参数后得到一。

09:00查看原图

演讲指出，λ 演算、图灵机和一般递归都具有同等的计算表达能力。问题随之出现：如果 λ 演算中的函数没有名字，函数怎么在定义内部再次调用自己？

在回答递归问题之前，Weirich 请观众从零开始反复按计算器的余弦键。数值逐渐接近约 0.739085：把这个数再次送入余弦函数，结果仍是它本身，允许计算器精度造成的近似误差。满足 f(x) = x 的 x 就是 f 的固定点。 观看 13:29

14:10查看原图

固定点不一定只有一个：平方根函数有零和一两个固定点；恒等函数的每个输入都是固定点；有些函数则没有固定点。余弦例子展示的是一种收敛现象，不意味着任意函数都能靠反复调用找到固定点。

阶乘是一个简单的递归例子：0! = 1；当 n > 0 时，n! = n × (n - 1)!。因此 5! = 120。普通写法可以用名字 fact 在函数体里调用自身，但一旦把函数直接作为匿名表达式调用，这个名字就不再自动存在。 观看 16:18

这不是说递归在匿名函数中不可能，而是说必须找到一种方法，把“下一次要调用的函数”带入当前函数。Weirich 接下来先补充高阶函数和几种重构，再返回这个问题。

高阶函数把函数当作值处理：它可以接收函数、返回函数，或者两者兼有。演讲中的 make_adder 接收一个数，返回一个把该数加到输入上的新函数。compose 则接收两个函数，返回一个按顺序应用它们的函数。 观看 17:52

例如，先给十加一，再乘三，得到三十三。把“加一”和“乘三”作为值传给组合函数后，就能得到一个执行相同步骤的新函数。之后的推导依赖同一个想法：一个函数可以接收另一段计算，并产出更完整的计算。

演讲依次展示了四种变换。它们用于把表达式改写成便于下一步操作的形状；实际应用时仍要注意变量作用域和求值时机。 观看 21:19

1. 1Tennent 对应原则：把表达式包进一个零参数函数并立即调用，可以在相应条件下保留结果。
2. 2引入绑定：给函数增加一个未使用的参数并传入值。新名字不能意外遮蔽原表达式中引用的自由变量；在严格求值语言里，传入的表达式本身也会先求值。
3. 3函数包装：把一次函数调用包进另一个函数；外层函数被调用时才执行内层调用。这给后面的递归提供了延迟求值的手段。
4. 4内联定义：把名字出现的位置换成它所代表的函数定义。演讲用它逐步去掉中间名字，回到匿名表达式。

Weirich 首先设想一个“阶乘改进器”：它接收一个部分阶乘函数，返回一个新的函数。新的函数在输入为零时返回一；否则，它用传入的部分函数计算 n - 1，再乘以 n。 观看 28:47

improve = ->(partial) {
  ->(n) { n.zero? ? 1 : n * partial.(n - 1) }
}

把一个总是报错的函数交给改进器，得到的新函数至少能计算 0!。再改进一次，就能计算 1!；继续改进，就能多处理一层。手工嵌套有限次当然不能成为通用递归，但它暴露了一个关键结构：每一层都只需知道如何调用下一层。

33:40查看原图

下一步是让函数接收自身。直接把原来的改进器传给自己会失败：改进器需要一个函数，却在下一层收到数字。Weirich 修改内部调用，让生成器通过 gen.(gen).(n - 1) 再次使用自身；此时 gen 已不是原先的部分阶乘函数，而是生成下一层的函数。这样构造出的表达式不再依赖名为 fact 的外部递归函数；演示中它能计算较大的阶乘，直到 Ruby 的调用栈耗尽。 观看 33:42

但把自应用直接搬到参数位置会遇到问题：Ruby 会在调用函数前先求值参数。若 gen.(gen) 的求值又立刻要求 gen.(gen)，程序还没检查阶乘的终止条件就不断展开，最终栈溢出。解决方法是将调用包进 ->(v) { gen.(gen).(v) }：先传递函数，只有需要处理下一个输入时才展开。

通过引入绑定、替换和内联，Weirich 把只知道阶乘规则的改进器，从负责自应用和延迟求值的部分中分离出来。后者不必知道什么是阶乘；换一个按相同方式编写的改进器，也可以用于别的递归定义，例如斐波那契数列。 观看 38:15

44:30查看原图

下面是与演讲思路等价的 Ruby 形式，fix 接收改进器，并返回递归函数：

fix = ->(f) {
  ->(x) { f.(->(v) { x.(x).(v) }) }.
    (->(x) { f.(->(v) { x.(x).(v) }) })
}

factorial = fix.(improve)
factorial.(5) # => 120

这里 f 是改进器；两个 x 代表自应用结构；内部的 ->(v) 推迟下一次展开。代码保留普通整数、条件判断和乘法以便说明，因而是用 Ruby 演示核心机制，并非把整个程序写成纯 λ 演算。

如果把已经完整的阶乘函数交给阶乘改进器，改进后的函数仍计算同一个阶乘：其行为没有改变。因此可以从函数行为的角度说，阶乘是这个改进器的固定点。固定点组合子的工作就是从这种形式的改进器构造对应的递归函数。 观看 45:04

49:20查看原图

Weirich 将演示中的构造称为适用于应用序求值的 Y 组合子，也提到它常被称为 Z 组合子。经典的普通序形式不需要同样的包装；Ruby 会先计算参数，因此直接使用那个形式会过早展开。不同资料的命名与写法可能不同，关键是检查求值策略。

演讲最后，Weirich 明确说：如果语言已有命名函数，就没有必要为了日常递归使用 Y 组合子。他更看重的是推导过程——从固定点、高阶函数和几种小变换出发，把一个看似神秘的表达式拆成可以逐步检查的部分。 观看 50:34

他还推荐 Tom Stuart 的《Programming with Nothing》，作为继续探索用 λ 函数构造程序的材料。整场演讲的核心并非背诵组合子的写法，而是理解：即使没有函数名，自应用与合适的求值时机也能建立递归。