重新发明 Y 组合子（JavaScript 版）

关于 Y 组合子的来龙去脉，我读过几篇介绍文章。相比之下，还是王垠的讲解最易懂。不过他原来用的是 Scheme，我这里写一个 JavaScript 版，帮助理解。

我们先看递归是怎么长出来的。

lambda 演算的语法很简洁，一言以蔽之：

x | t t | λx.t

其中 x 表示变量，t t 表示调用，λx.t 表示函数定义。

先定义一个阶乘函数，然后调用它：

fact = n => n == 1 ? 1 : n * fact(n - 1)
fact(5)

在 lambda 演算中，事情没有这么简单，因为它没有 = 赋值符号。

上面这个定义里，fact 这个名字还在。如果我们想要一个真正无名的递归调用，便不能这样写：

(n => n == 1 ? 1 : n * fact(n - 1))(5) // there is still `fact` name

那么，怎样消去一个函数的名字？

首先，没有名字，就无法直接定义递归函数。

但参数是可以随意命名的，所以可以把“名字”变成参数：

fact = (f, n) => n == 1 ? 1 : n * f(f, n - 1)
fact(fact, 5)

lambda 演算里函数只能有一个参数，所以再变形一次：

fact = f => n => n == 1 ? 1 : n * f(f)(n - 1)
fact(fact)(5)

再进一步，只需把 fact 直接代入，就得到一个完全匿名的调用：

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

这坨代码是可以运行的。它可以叫作“穷人的 Y 组合子”。能用，但不通用，因为你仍要针对每个具体函数重写一遍。

所以，接下来要做的，就是把通用模式抽出来。

先看这里，f(f) 出现了两次，fact(fact) 出现了一次。既然模式重复了三次，按 DRY，就先抽一层：

w = f => f(f)
w(fact)(5)
w(f => n => n == 1 ? 1 : n * f(f)(n - 1))(5)

现在只剩下一个重复模式：f(f)。但它还嵌在业务逻辑内部，所以要继续 factor out。

从这个定义开始：

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

令 g = f(f)，则可改写为：

f =>
  (g => n => n == 1 ? 1 : n * g(n - 1))(f(f))

当然，f(f) 在 call by value 时会导致栈溢出，所以再做一次 η 化：

f =>
  (g => n => n == 1 ? 1 : n * g(n - 1))(v => f(f)(v))

这里的 g => n => n == 1 ? 1 : n * g(n - 1)，其实就是更本质的阶乘定义。

把它提出来，命名为 fact0：

(fact0 => f =>
  fact0(v => f(f)(v))
)(g => n => n == 1 ? 1 : n * g(n - 1))

不要忘了最初的 w，于是有：

w(
  (fact0 => f => fact0(v => f(f)(v)))(g => n => n == 1 ? 1 : n * g(n - 1))
)(5)

接着把“阶乘函数的定义”也抽成参数。把 fact0 换成更一般的名字 s，再把那一大坨定义抽象成参数 h：

(h =>
  w((s => f => s(v => f(f)(v)))(h))
)(g => n => n == 1 ? 1 : n * g(n - 1))(5)

好。大功告成。上面括号里的那部分，就是 Y。

单独拿出来看：

(h =>
  w(
    (s => f => s(v => f(f)(v)))(h)
  )
)

中间那一层 h 还可以 apply 一次，继续化简：

(h =>
  w(
    (f => h(v => f(f)(v)))
  )
)

而 w 这个名字也可以继续消掉：

(h =>
  (f => h(v => f(f)(v)))(f => h(v => f(f)(v)))
)

这就是最后的结果。

若换回 lambda 记法，可以写成：

$ \lambda f.(\lambda u. u \ u) (\lambda x. f (x \ x)) $

或者更经典的形式：

$ \lambda f. (\lambda x. f (x \ x)) (\lambda x. f (x \ x)) $