Y-Combinator: 如何在匿名函数中递归调用自身

如何实现一个阶乘函数? 最简单的做法是使用递归:

'use strict';

function factorial(n) {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

很好. 那么如何将 factorial 函数写成一个匿名函数, 且同样递归调用自身呢? (arguments.callee 禁止)

答案略显诡异. 它是这样的:

'use strict';

const Y = (F) => ((g) => g(g))((g) => F((x) => g(g)(x)));

Y((factorial) => (n) => {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
})

其中 5 至 11 行是一个真正的匿名函数表达式; 6 至 10 行与递归版的阶乘函数完全一致, 只不过第 9 行似乎不是在递归调用自身, 而是调用了上层函数的一个参数. 理解起来暂时有点难, 大家可以打开 node 试一试, 比如说

Y((factorial) => (n) => {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
})(5);

就能得到 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 项. 例如 等价于 , 等价于 .

再比如, 我们令 lambda 项 , 这里 只是 “伪代码” (它并不符合 lambda 项的规范), 表示求 与 之积. 则如下的 规约为:

也就是 首先会求 , 规约得到一个新的抽象 lambda 项 , 然后再求 , 最后得到 .

这样的写法不太方便, 这种始终左结合的应用 lambda 项可以省略括号, 例如 实际表示的是 . 因此 可写作 .

这样的写法也不太方便, 这种始终右结合的抽象 lambda 项也可以省略括号, 例如 实际表示的是 . 因此 写作 就可以了.

我们可以很自然地将抽象 lambda 项理解为函数定义, 把应用 lambda 项理解为函数调用. 变换可理解为参数名字不重要, 可以随意替换; 规约则是将实参带入形参调用函数. 不过 lambda 演算不允许定义多参函数, 只能使用形如 的方式实现, 称为柯里化(Currying).

Y-Combinator

我们尝试用 lambda 演算计算阶乘. 为了方便, 我们还定义了以下几个函数(lambda 项):

• 其中 是伪代码, 当且仅当 与 相等时值为真.
• 其中 是伪代码, 表示当 cond 为真时值为 否则为 .
• 其中 是伪代码, 表示求 与 之差.

然后我们定义出了求阶乘的函数:

其中 应用 , 当 为 0 即 为真时值为 1; 否则为 , 即递归调用 再乘以 .

我们在编程语言中常常这样用, 但遗憾的是, 在 lambda 演算中, 这是不合法的. Lambda 演算只是简单的符号替换, 不是编程语言中的函数调用. 因此在定义 factorial 的时候, factorial 还没被创建, 你无法对一个不存在的符号执行 规约.

既然无法使用一个符号代替它自身, 那我们就把它自身原样写进去试试:

这样写下去就没完没了了. 不妨尝试将重复的部分提取出来, 用 lambda 演算替换:

可以看到, 递归调用的部分做成了约束变量 , 然后我们只需使用 规约把 替换成自己, 得到:

与 (2) 式等价. 嗯, 这比 (2) 式好看了些, 不过重复的部分还是有点多. 我们再来进一步改进:

我们把 (3) 式应用 , 让它不断地对自己执行 规约, 其结果与 (4) 式等价, 而且简洁了不少.

这时可能有同学要问, 这有什么用呢? 我们不断地让 应用它自身, 还是没完没了啊! 其实我们离胜利只剩一步之遥了. 观察 (5) 式, 我们想要的其实不过是

也就是我们希望 能等价于 它本身, 使得它能够递归调用. 那么我们能不能不写无数个应用 lambda 项呢? 试试这样:

这样 会等于 也就是 (3) 式. 它是不能传入 以求 的阶乘的. 且慢! 虽然 不是 , 但是 能生成它! 那么, 如果我们让 应用它自己, 也就是 , 它就会生成一个递归调用 的函数, 这个函数似乎可以求阶乘! 于是我们把 (6) 式改写成:

我们把它展开试试:

我们惊奇地发现, 它能无限执行 规约, 其结果与 (2) 式完全一致. 也就是说我们得到了阶乘的 lambda 演算.

虽然 (7) 式能完成递归阶乘运算, 但是 这种写法有些丑, 能不能优化一下呢? 很简单, 使用 lambda 演算替换掉就好了. 我们先定义:

我们只需要将 (3) 式应用 即可得到阶乘的 lambda 演算:

我们把它展开看看:

与 (7) 式完全一致. 至此, 我们得到了完美的阶乘 lambda 项.

(8) 式被称为 Y-Combinator. 我们再回过头看来 (9) 式中传入 中的 lambda 项, 也就是 (3) 式, 令

实际上 希望能传入一个 lambda 项 , 使得 . 因为只有这样, 才能让 递归调用自身. 我们称使得 成立的 为 的不动点(fixed point). 那么 对 做了什么呢? 我们算算看:

所以我们有 . 因此 的不动点为 . 这就是 Y-Combinator 的神奇之处, 它通过求 的不动点实现递归.

编程语言中的 Y-Combinator

OK, 现在我们来看文章开头的 Y = (F) => ((g) => g(g))((g) => F((x) => g(g)(x))) 是什么. 其实它就是 Y-Combinator 的 JavaScript 实现, 等价于 (8) 式. 我们把它写得更清楚些:

const Y = (F) =>
    ((g) => g(g))               // (λ g . (g g))
    ((g) => F((x) => g(g)(x)))  // (λ g . (F (g g)))

不过略微不同的是, 不能直接写成 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 解释器及其实现, 同样推荐大家阅读.