Y 组合子与 Z 组合子：无 let 无递归环境下的函数自引用推导

在纯 lambda 演算中，没有变量绑定语句（let）、没有递归关键字，甚至连函数名都不存在 —— 只有匿名函数（λ 抽象）和函数应用。然而，正是在这种极度精简的形式系统中，递归函数却能够被表达出来。这一看似矛盾的成就，归功于 Y 组合子及其变体 Z 组合子。

问题本质：递归需要自引用

考虑阶乘函数的标准递归定义：

def fact(n):
    return 1 if n == 0 else n * fact(n - 1)

这里 fact 在定义体内直接引用了自身。但在纯 lambda 演算中，这种直接自引用是不被允许的。我们需要一种机制，让函数能够 "间接地" 获得对自身的引用。

核心洞察：通过参数传递自引用

解决这一问题的关键洞察是：让一个非递归函数通过参数接收它自己。

假设我们有一个函数 f，它接受一个参数 g。如果我们调用 f(f)，那么在 f 的执行体内，g 就指向 f 本身 —— 我们实现了自引用。

将这个思路应用到阶乘函数上，首先把递归定义改写为接受一个额外参数 rec 的形式：

fact_base = lambda rec: lambda n: \
    1 if n == 0 else n * rec(rec)(n - 1) * n

这里的 rec 是一个占位符，代表 "未来的递归调用"。真正的递归通过 rec(rec) 实现 —— 函数把自己传给自己。

从具体实现到通用组合子

现在我们有了一个可以工作的递归模式：

fact = fact_base(fact_base)

但这还不够优雅。我们需要一个通用的组合子，能够将任何 "期望递归调用" 的函数转换为真正的递归函数。

第一步：抽象外层自应用

首先，将 fact_base(fact_base) 这个模式抽象出来：

mkrec = lambda f: f(f)

fact = mkrec(lambda rec: lambda n:
    1 if n == 0 else rec(rec)(n - 1) * n)

第二步：抽象内层自应用

上述写法中，递归调用必须写成 rec(rec)(x)，非常繁琐。我们希望调用者只需写 rec(x)。

这需要引入一个适配层：将用户提供的 "简洁版" 函数转换为 "完整版" 函数。

mkrec_nice = lambda g: mkrec(lambda rec:
    g(lambda y: rec(rec)(y)))

# 现在可以这样定义阶乘
fact = mkrec_nice(lambda rec: lambda n:
    1 if n == 0 else rec(n - 1) * n)

这里的 mkrec_nice 就是 Z 组合子的工程化形态。

Z 组合子的形式化表达

将 mkrec_nice 完全展开，代入 mkrec = lambda f: f(f)，得到：

Z = lambda g: (lambda r: g(lambda y: r(r)(y))) \
              (lambda r: g(lambda y: r(r)(y)))

用 lambda 演算的标准记法写作：

Z = λg.(λr.g(λy.r r y))(λr.g(λy.r r y))

这就是 Z 组合子的标准形式。它的关键特征是：在递归调用点 r r y 外层包裹了一个 λy，这使得在 eager evaluation（严格求值）语言中，递归调用被延迟到真正需要时才执行。

Y 组合子：惰性求值版本

如果语言支持惰性求值（如 Haskell），可以进一步简化。在惰性环境中，值本身就可以是递归的，不需要显式的参数包装。

Y = lambda g: (lambda r: g(r(r))) \
              (lambda r: g(r(r)))

或标准记法：

Y = λg.(λr.g(r r))(λr.g(r r))

Y 组合子比 Z 组合子更简洁，但在 Python、JavaScript 等严格求值语言中直接使用会导致无限递归 —— 因为 r(r) 会立即被求值。

工程化理解：为什么这很重要

1. 编译器实现

理解 Y/Z 组合子有助于实现支持递归的函数式语言编译器。在编译到不原生支持递归的目标平台（如某些虚拟机或硬件描述语言）时，组合子提供了一种标准的递归编码方案。

2. 代码生成与宏系统

在宏展开或代码生成场景中，当需要生成递归函数但无法预知函数名时，组合子模式提供了一种 "匿名递归" 的解决方案。

3. 类型系统研究

Y 组合子在类型系统中是一个著名的挑战 —— 在简单类型 lambda 演算中，Y 组合子是无法被类型化的。这引出了递归类型（recursive types）的研究，对理解现代类型系统（如 Rust 的递归枚举、TypeScript 的条件类型）有深远影响。

实现检查清单

在工程实践中使用组合子模式时，注意以下要点：

• 求值策略适配：严格求值语言必须使用 Z 组合子（带 λy 包装），惰性求值语言可用 Y 组合子
• 尾递归优化：组合子实现的递归通常不是尾递归形式，在缺乏尾调用优化的语言中可能导致栈溢出
• 调试难度：组合子展开的代码难以调试，建议在开发阶段使用命名递归，仅在必要时转换为组合子形式

小结

Y 组合子和 Z 组合子展示了 lambda 演算的强大表达能力：在最小的语法基础上，通过巧妙的自应用模式，实现了看似需要语言级支持的递归特性。Z 组合子通过额外的 lambda 抽象延迟递归调用，使其能够在严格求值语言中正常工作。

这一推导过程也体现了函数式编程的核心思想 ——通过高阶函数和组合来构建复杂行为，而非依赖语言的特殊语法支持。

参考来源

• Matt Might, "Equational derivations of Church encodings and the Y Combinator in Python"
• LPTK, "The Y Combinator Explained in Python"
• Wikipedia, "Fixed-point combinator"

compilers