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

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

'use strict';

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

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

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

1
2
3
4
5
6
7
8
9
10
11
'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 项
• 应用: 如果 $M$ 和 $N$ 是 lambda 项, 则 $(M\ N)$ 也是 lambda 项
• 抽象: 如果 $M$ 是 lambda 项, $\phi$ 是一个合法的标识符, 则 $(\lambda \phi . M)$ 也是 lambda 项

以下的式子都是 lambda 项:

• $a$
• $(a\ b)$
• $(a (b\ c))$
• $(\lambda x . (x\ y))$
• $(\lambda x . (\lambda y . (x\ y)))$

以 lambda 项 $(\lambda x . (x\ y))$ 为例, 其中点号右边的 $x$ 在点号左边被标记为 $\lambda x$ , 这样的变量我们称为约束变量; 与之相对的 $y$ 则被称为自由变量. 在 lambda 项 $(\lambda x . (\lambda y . (x\ y)))$ 中, $x$ 和 $y$ 都是约束变量.

Lambda 演算

Lambda 演算仅有如下两个规则:

$\alpha$ 变换

约束变量可随意替换, 只要不与自由变量冲突. 例如 $(\lambda x . (x\ y))$ 可以变换成 $(\lambda t . (t\ y))$ 或者 $(\lambda u . (u\ y))$, 它们完全等价. 但是不能变换成 $(\lambda y . (y\ y))$, 这与自由变量 $y$ 冲突了. 我们称这种变换为 $\alpha$ 变换.

$\beta$ 规约

对于应用 lambda 项 $(M\ N)$, 其中 $M$ 为抽象 lambda 项, $(M\ N)$ 等价于将 $M$ 中的约束变量替换成 $N$ 的 lambda 项. 例如 $((\lambda x . (x\ y)) k)$ 等价于 $(k\ y)$, $((\lambda x . (\lambda y . (x\ y))) k)$ 等价于 $(\lambda y . (k\ y)))$.

再比如, 我们令 lambda 项 $\times \equiv (\lambda x . (\lambda y . x \times y))$, 这里 $x \times y$ 只是 "伪代码" (它并不符合 lambda 项的规范), 表示求 $x$ 与 $y$ 之积. 则如下的 $\beta$ 规约为:

也就是 $((\times 2) 3)$ 首先会求 $(\times 2)$, $\beta$ 规约得到一个新的抽象 lambda 项 $(\lambda y . 2 \times y)$, 然后再求 $((\lambda y . 2 \times y) 3)$, 最后得到 $2 \times 3 = 6$.

$((\times x) y)$ 这样的写法不太方便, 这种始终左结合的应用 lambda 项可以省略括号, 例如 $(a\ b\ c\ d)$ 实际表示的是 $(((a\ b)\ c)\ d)$. 因此 $((\times x) y)$ 可写作 $(\times x\ y)$ .

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

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

Y-Combinator

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

• $\mathrm{eq} \equiv (\lambda x . \lambda y . x = y)$ 其中 $a = b$ 是伪代码, 当且仅当 $a$ 与 $b$ 相等时值为真.
• $\mathrm{if} \equiv (\lambda\ cond\ .\ \lambda\ a\ .\ \lambda\ b .\ \mathrm{if}\ cond\ \mathrm{then}\ a\ \mathrm{else}\ b )$ 其中 $\mathrm{if}\ cond\ \mathrm{then}\ a\ \mathrm{else}\ b$ 是伪代码, 表示当 cond 为真时值为 $a$ 否则为 $b$.
• $- \equiv (\lambda a . \lambda b . a - b)$ 其中 $a - b$ 是伪代码, 表示求 $a$ 与 $b$ 之差.

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

其中 $(\mathrm{if}\ (\mathrm{eq}\ n\ 0)\ 1\ (\times\ (factorial\ (-\ n\ 1))\ n)\ )$ 应用 $\mathrm{if}$ , 当 $n$ 为 0 即 $(\mathrm{eq}\ n\ 0)$ 为真时值为 1; 否则为 $(\times\ (factorial\ (-\ n\ 1))\ n)$, 即递归调用 $(factorial\ (-\ n\ 1))$ 再乘以 $n$.

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

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

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

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

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

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

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

也就是我们希望 $(g (g (g (…))))$ 能等价于 $(\lambda n . (\mathrm{if}\ (\mathrm{eq}\ n\ 0)\ 1\ (\times\ (f\ (-\ n\ 1))\ n)))$ 它本身, 使得它能够递归调用. 那么我们能不能不写无数个应用 lambda 项呢? 试试这样:

这样 $f$ 会等于 $g$ 也就是 (3) 式. 它是不能传入 $(-\ n\ 1)$ 以求 $n - 1$ 的阶乘的. 且慢! 虽然 $g$ 不是 $(\lambda n . (\mathrm{if}\ (\mathrm{eq}\ n\ 0)\ 1\ (\times\ (f\ (-\ n\ 1))\ n)))$, 但是 $g$ 能生成它! 那么, 如果我们让 $g$ 应用它自己, 也就是 $(g\ g)$, 它就会生成一个递归调用 $(g\ g)$ 的函数, 这个函数似乎可以求阶乘! 于是我们把 (6) 式改写成:

我们把它展开试试:

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

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

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

我们把它展开看看:

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

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

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

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

编程语言中的 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))$ 不能直接写成 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 解释器及其实现, 同样推荐大家阅读.