缘起#

大学时阅读《暗时间》一书，后面有很多数学相关的内容没有看懂，其中有一个 Y 组合子的概念挺感兴趣但一直没搞明白，最近意外发现一位大佬的博客，讲得非常深入浅出，于是尝试理解

十分钟速通 Y Combinator

让匿名函数实现递归

lambda 演算#

三个基本语法：

• 变量
• 抽象
• 应用

1
// 变量，符号
2
x y z ...
3

4
// 抽象，相当于函数
5
λx. M => function(x) { return M }
6

7
// 应用，调用函数
8
(λx. x) y => (function(x) { return x })(y)
9
// 自应用，x 可以是任意函数
10
x x => x(x) // x 当作参数传递给 x 函数并且调用

两个核心规约：

• alpha 等价
• beta 规约

1
// alpha 等价：变量用其他符号替换，是等价的
2
λx. x = λy. y
3

4
// beta 规约：把值代入函数
5
(λx. x) 1 => (function(x) { return x })(1) => 1

好的，现在你已经了解 lambda 演算 的基本规则了，可以尝试代入变量计算下面这个公式

代入变量 $F$

令 $W = λx. F(xx)$ ，得

因为 $Y F = W W$，所以

PS：lambda 演算 中不存在函数名，为了方便计算和理解，这里赋予了函数名 $Y$

不动点组合子#

在上面的计算中，我们得到

把等式反转，右边的 $Y F$ 替换成 $F(YF)$

我们发现它可以无限展开，也就是说对于任意函数 $F$，通过 $Y$ 都能构造出递归调用的结构

1
// 这是一个组合子，可以使用任意符号代表它，例如：C
2
function(x, y) { y(x) }
3

4
// 这不是一个组合子，因为 + 是外部定义
5
// 如果强行用符号代表它，可能是 A+，需要两个符号
6
function(x, y) { x + y }

1
// 函数柯里化，把 x 和 g(x) 交给 f
2
S = f => g => x => f(x, g(x))
3

4
// 输入 x，y 返回 x
5
K = x => y => x

为什么#

为什么需要 $Y$ 组合子？

• lambda 演算 中函数都是匿名的
• 让匿名函数实现递归

在 lambda 演算 中为什么需要递归？

• lambda 演算 是用于研究计算的模型
• 解决一个可计算的问题，需要“任意有限长度”的计算
• 递归是一种“任意有限长度”计算的通用表达（手写 n 个步骤，用一个通用公式表达更简洁）

为什么 $Y$ 组合子可以让匿名函数实现递归？

• 因为它满足不动点的特性
• 可以构造出递归调用的结构
• 但匿名函数必须满足递归模板的条件（例如：(x) => 1，通过 $Y$ 就不能构造出递归）

$Y$ 组合子是怎样构造出递归结构的？

构造#

从直觉上构造递归，需要函数自己调用自己

• 也就是自应用
• 本质上是一个不动点

但匿名函数没有名字怎么办？

• 把函数自身当作参数，传递给自己

思路有了，我们尝试构造一下，把函数自身当作函数参数

$M$ 里需要实现函数自己调用函数的参数，也就是 $x x$

我们发现它会一直复制自己，无限递归下去

这其实是一个特殊的组合子 $Ω = (λx.xx)(λx.xx)$，用于表达无限循环

还差一点，我们观察到无法终止是因为只有自应用，缺少了“计算逻辑”

如果让自应用前执行一些判断终止的逻辑，也就是说尝试把 $xx$ 代入一个 $f$ 判断终止的函数中

出现 $f$ 递归调用的结构，我们成功得到了这个神奇的函数，把 $f$ 抽象成变量，就得到

有些文章用一个匿名阶乘函数实现递归作为案例，利用 把函数自身当作参数，传递给自己 的思想，模拟 $Y$ 组合子的构造过程，思路也是差不多的，理论上把这个匿名函数实现递归的结构抽象成通用函数，也能得到 $Y$ 组合子，只是过程比较复杂

缘灭#

“计算机是数学家一次思考失败的产物”，20世纪初，数学家希望通过逻辑和符号系统解决所有数学问题，对“计算”的本质进行思考，用极简的规则构建出计算模型，这就是 lambda 演算，后来 哥德尔的不完备定理 揭示了数学系统的局限性，但反而为计算机科学奠定了理论基础——定义了计算的边界，也是函数式编程语言的理论起源，它后来被证明和图灵机是等价的，后者促进了计算机的产生（lambda 演算 是图灵的导师邱奇提出的）

$Y$ 组合子可以让任意函数构造出不动点从而让匿名函数实现递归成为可能，让 lambda 演算 拥有了“循环”的能力，解决了无法通用表达有限长度计算的问题，通过递归可以表达任意算法

递归的本质是不动点，也可以说是寻找某个函数的不动点，通过迭代逼近这个点，从计算的角度来理解也比较容易，任何有限步骤的计算，都是为了寻找一个不再变化的状态（结果），不动点是构成图灵完备的必要条件

也许读者已经产生了很多疑问，没有关系这是正常的，因为笔者也一样

什么是图灵完备？为什么它们图灵等价？

为什么递归可以表达任意算法？为什么 $S$ $K$ 组合子可以表达所有运算？

思绪仿佛回到当年第一次上 C++ 课，老教授用一口难以听清的方普在讲台上自言自语，“为什么仅用条件分支和循环就可以解决世界上大部分的问题？计算机的尽头是数学，数学的尽头是哲学，哲学的尽头是神学…”，当时的我也像现在一样一脸茫然

这些问题涉及到可计算理论，也称递归论

Extend

构造递归的核心是自指，自指也是一个很神奇的东西，它可以产生矛盾和无限，它横跨数学，逻辑学，计算机科学，生物，哲学，艺术…各种学科领域，例如：

元胞自动机，自指性可能和意识有关？

“上帝的指纹”——曼德勃罗特集

DNA 自我复制，细胞分裂

哥德尔不完备定理

莫比乌斯带

悖论

…

是否暗示着宇宙某种普遍规律？Wolfram 试图用自指的超图模型统一物理定律，通过极为简单的数学规则却可以产生无限复杂事物的能力来解释宇宙的基本结构和物理定律 【TED 演讲】Stephen Wolfram：计算万物的理论

这一连串的问题使我的大脑宕机，只想赶紧结束这篇文章，以后有空再了解，感谢 AI 的辅助，让我节省了不少查找资料和理解的时间，文章开头之所以没有介绍 lambda 演算，是因为它可能会牵连出一系列的疑问，所以我特意留到了最后

一袋米杠几楼！！！

参考资料：

• 组合子逻辑
• 十分钟速通 Y Combinator
• Y 组合子的一个启发式推导
• 以函数为中心：lambda 演算和组合子逻辑