Javascript 中 Y 组合子的【再】推导

三载前,吾尝书 Javascript 中 Y 组合子的推导 。前日,夜半欲眠,突思此物。试无凭而推,竟得。

次日,观前文,觉冗长晦涩,故作此文。

Y 组合子的目的

写出一个递归函数很简单,以阶乘函数为例:

let F = x => x ? x * F(x-1) : 1;
F(5) //120

但对于匿名函数,没有变量赋值的情况下,如何解决上面的问题?
这就用到 Y 组合子。

推导

变量与参数的概念其实非常相似,我们可以用参数,替代变量赋值

(f => x => x ? x * f(x-1) : 1)

我们只要给 f 这个参数传这个函数自身,就达到了目的,首先尝试把函数直接复制一份作为参数传入:

(f => x => x ? x * f(x-1) : 1)(f => x => x ? x * f(x-1) : 1)

容易发现,如果前半部分中的 f 是后面这个函数:

(f => x => x ? x * f(x-1) : 1)(f => x => x ? x * f(x-1) : 1)
//                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

那么 f 接收的参数应该是它自身,像上面 f(x-1) 这样的调用方式是错误的。
我们把上面的表达式改造一下:

(f => x => x ? x * f(f)(x-1) : 1)(f => x => x ? x * f(f)(x-1) : 1)
//                 ^^^^                             ^^^^

上面就是我们的基本形式,可以开始化简了。

化简

首先左右两大块是一模一样的,可以用一个变量代替:

let a = f => x => x ? x * f(f)(x-1) : 1;
a(a);

还记得上面我们说的变量赋值 ↔ 参数的关系吗?我们将它改造为函数:

(a => a(a))(f => x => x ? x * f(f)(x-1) : 1)

我们的目标是分离出下面的部分:

(f => x => x ? x * f(x-1) : 1)

观察原式,只需要把下面的 f(f) 替换为 f 就能很方便的提取最后的结果了

(a => a(a))(f => x => x ? x * f(f)(x-1) : 1)
//                            ^^^^

易知,对于函数 f, g (我们这里讨论的全是单参数函数)

1) f 等价于 x => f(x)
2) (x => f(g(x)))(x) 等价于 (x => f(x))(g(x))

运用 1)

(a => a(a))(b => (f => x => x ? x * f(f)(x-1) : 1)(b))
//         ^^^^^                                  ^^^

运用 2)

(a => a(a))(b => (f => x => x ? x * f(x-1) : 1)(b(b)))
//         ^^^^^                    ^          ^^^^^

运用 1)2)

(c => (a => a(a))(b => c(b(b))))(f => x => x ? x * f(x-1) : 1)
//^^^                  ^        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

也就是说,前半部分就是我们要找的 Y 组合子,即

Y = c => (a => a(a))(b => c(b(b)))

重命名参数

Y = f => (x => x(x))(x => f(x(x)))

尝试调用

(f => (x => x(x))(x => f(x(x))))(f => x => x ? x * f(x - 1) : 1)(5)

然而,当我们用上面的式子调用时会爆栈:Maximum call stack size exceeded

惰性求值

下面来解决爆栈问题

还记得

f => (x => x(x))(x => f(x(x)))
//                      ^^^^

是怎么来的吗?是我们从递归中 ?: 部分中抽离出来的,是递归条件为真的情况。递归之所以能结束,是因为函数有终止条件。而现在我们把 x(x) 抽离出来,相当于把递归移到了判断之前,在没有终止条件的情况下自身调用自身,最终造成了爆栈。


(a => a(a))(b => (f => x => x ? x * f(f)(x-1) : 1)(b))
//                          ^^  ^^^^^^^^^^^^^   ^
//                          判断    递归       返回
(a => a(a))(b => (f => x => x ? x * f(x-1) : 1)(b(b)))
//                                             ^^^^^
//                                             递归

其实因为 js 不是惰性求值的语言,之前的等价代换不完全正确,
对于 fx => f(x) 它们不是完全等价,区别是 f 本身如果是表达式,当以 f 的形式出现时,表达式会立即计算值,而如果以 x => f(x) 的形式出现,只有调用时才会求 f 的值。

运用 1)懒求值特性,把

Y = f => (x => x(x))(x => f(x(x)))

改造为:

Y = f => (x => x(x))(x => f(y => x(x)(y)))
//                          ^^^^^    ^^^

这样,就得到了在 js 中可用的 Y 组合子。

尝试调用

Y(f => x => x ? x * f(x-1) : 1)(5)
// 120

成功。