Y-Combinator: 如何在匿名函数中递归调用自身
如何实现一个阶乘函数? 最简单的做法是使用递归:
1 |
|
很好. 那么如何将 factorial
函数写成一个匿名函数, 且同样递归调用自身呢? (arguments.callee
禁止)
答案略显诡异. 它是这样的:
1 |
|
其中 5 至 11 行是一个真正的匿名函数表达式; 6 至 10 行与递归版的阶乘函数完全一致, 只不过第 9 行似乎不是在递归调用自身, 而是调用了上层函数的一个参数. 理解起来暂时有点难, 大家可以打开 node 试一试, 比如说
1 |
|
就能得到 5 的阶乘为 120.
那么, 这其中诡异 Y = (F) => ((g) => g(g))((g) => F((x) => g(g)(x)))
是什么呢? 第 9 行中调用的 factorial
又是什么? 这就是本文要讨论的主角: Y-Combinator.
Lambda 演算
现代语言几乎都有匿名函数这一特性, 而匿名函数常常有另一个名字: lambda 表达式. 为什么要叫它 lambda 表达式呢? 这是因为它来自于 lambda 演算. Lambda 演算本身非常简单, 这里我们简单介绍.
Lambda 项
一个 Lambda 项可以是:
- 原子 (atom): 一个合法的标识符即是原子, 所有的原子都是 lambda 项
- 应用: 如果
和 是 lambda 项, 则 也是 lambda 项 - 抽象: 如果
是 lambda 项, 是一个合法的标识符, 则 也是 lambda 项
以下的式子都是 lambda 项:
以 lambda 项
Lambda 演算
Lambda 演算仅有如下两个规则:
变换
约束变量可随意替换, 只要不与自由变量冲突. 例如
规约
对于应用 lambda 项
再比如, 我们令 lambda 项
也就是
我们可以很自然地将抽象 lambda 项理解为函数定义, 把应用 lambda 项理解为函数调用.
Y-Combinator
我们尝试用 lambda 演算计算阶乘. 为了方便, 我们还定义了以下几个函数(lambda 项):
其中 是伪代码, 当且仅当 与 相等时值为真. 其中 是伪代码, 表示当 cond 为真时值为 否则为 . 其中 是伪代码, 表示求 与 之差.
然后我们定义出了求阶乘的函数:
其中
我们在编程语言中常常这样用, 但遗憾的是, 在 lambda 演算中, 这是不合法的. Lambda 演算只是简单的符号替换, 不是编程语言中的函数调用. 因此在定义 factorial 的时候, factorial 还没被创建, 你无法对一个不存在的符号执行
既然无法使用一个符号代替它自身, 那我们就把它自身原样写进去试试:
这样写下去就没完没了了. 不妨尝试将重复的部分提取出来, 用 lambda 演算替换:
可以看到, 递归调用的部分做成了约束变量
与 (2) 式等价. 嗯, 这比 (2) 式好看了些, 不过重复的部分还是有点多. 我们再来进一步改进:
我们把 (3) 式应用
这时可能有同学要问, 这有什么用呢? 我们不断地让
也就是我们希望
这样
我们把它展开试试:
我们惊奇地发现, 它能无限执行
虽然 (7) 式能完成递归阶乘运算, 但是
我们只需要将 (3) 式应用
我们把它展开看看:
与 (7) 式完全一致. 至此, 我们得到了完美的阶乘 lambda 项.
(8) 式被称为 Y-Combinator. 我们再回过头看来 (9) 式中传入
实际上
所以我们有
编程语言中的 Y-Combinator
OK, 现在我们来看文章开头的 Y = (F) => ((g) => g(g))((g) => F((x) => g(g)(x)))
是什么. 其实它就是 Y-Combinator 的 JavaScript 实现, 等价于 (8) 式. 我们把它写得更清楚些:
1 |
|
不过略微不同的是, F(g(g))
, 这会使 g(g)
立即求值导致无限递归. 因此我们需要将 g(g)
写作 (x) => g(g)(x)
, 让它在运行时求值. 明白了 Y-Combinator 的原理, 本文开头的代码也就不足为奇了.
延伸阅读 & 参考
笔者最近看完了 The Little Schemer , 又参阅了一些关于 lambda 演算的文章, 为之叹服. 这本书以一种自问自答的方式介绍了 Scheme 语言和函数式编程思想, 其中第九章中对 Y-Combinator 的介绍令人拍案叫绝. 这本书给我的感觉是重新学习了编程, 如果你和我一样, 学过很多命令式编程语言, 却从未接触过函数式编程语言, 那么强烈推荐 The Little Schemer , 它能极大地开阔我们的思路.
本文还参考了这篇介绍 lambda 演算的文章 https://github.com/txyyss/Lambda-Calculus . 本文着重介绍 Y-Combinator, 它只是 lambda 演算的冰山一角, lambda 演算远比本文所讲的精彩美妙. 这篇文章对 lambda 演算有一个较为全面的科普, 写得非常好. 它还附带了一个 lambda 解释器及其实现, 同样推荐大家阅读.