十分钟速通 Y Combinator

引

这学期在学校选了一门讲可计算性（Computability）的计算机科学基础课程。过程中也把很多概念给自己重新复习了一下，不过从这课课堂的反馈来看，可以说同学都听得非常吃力。我想到几年前我有尝试写过一篇通过 Y 组合子来讨论 Lambda 演算的文章，考虑到当时写得很不完善，我打算拿出来重新炒一下冷饭。顺便改使用傻子都能看懂的 JavaScript 来描述这个问题。顺便调试一下我博客系统 Markdown 引入 $\LaTeX$ 后会遇到的坑。

循环 -> 递归

我们还是从下面这个简单的循环问题开始探讨。通过写一个循环（不使用等差数列的情况下），求自然数列 1 到 n 的和（即 $1+2+3+…+n$）。一个最容易想到的实现可能如下：

function sum(n) {
  let result = 0
  for (let i = 1; i <= n; i++) {
    result += i
  }
  return result
}

sum(10) // => 55

我们现在对这个问题稍作变形，如果在这个程序中不得使用 for 循环，我们还能实现这个程序吗？显然这也是非常简单的，因为我们还可以用 while 循环。

function sum(n) {
  let result = 0
  let counter = 1
  while (counter <= n) {
    result += counter
    counter++
  }
  return result
}

sum(10) // => 55

或者进一步地，我们可以写成：

function sum(n) {
  let result = 0
  let counter = 1
  while (true) {
    if (counter > n) break
    result += counter
    counter++
  }
  return result
}

sum(10) // => 55

抽象地来看，我们这里使用到的 counter 变量，既可以看成是循环变量，更可以看成是一个程序计数器。也就是从一个状态转移到下一个状态的过程，而 break 则是指出了终止状态发生的位置。我们现在对这个题目进行进一步地变形，如果我们不允许在这里使用包括 while 在内的任何循环，我们还能实现这个程序吗？

我们不但能，而且程序写起来更简单了。

function sum(n) {
  if (n === 0) return 0
  return sum(n - 1) + n
}

sum(10) // => 55

这个写法可以优雅地由数学形式表示：

\[sum(x)= \begin{cases} 0 &x = 0 \cr sum(x-1) + x &otherwise \end{cases}\]

也就是我们只需要定义 $sum(0) = 0$，然后无论求什么的和，都是其之前所有数的和加上当前这个数。计算机会一次一次向下找，直到找到 0 为止，最后把找到的数全部加起来。解决！当然你可能会觉得这么做的效率很低，计算机不停递归会影响性能，我们会在之后讨论这个问题，我们目前暂时先只讨论「可计算性」上的等价。

匿名函数化

「$\lambda$ 演算」和我们刚刚那个例子很接近，但是又稍有不同。我们先抛开「$\lambda$ 演算」本身复杂的定义，从其性质入手，就可以简单对「$\lambda$ 演算」有直观的认识。

• 如果有这么一个式子 $\lambda x.x$，那么 x 就是一个变量。对于一个变量，我们可以任意更换其名字，比如可以从 x 改成 y，得到 $\lambda y.y$，这一步称作「$\alpha$ 等价」。
• 如果有形如一个式子 $(\lambda x.x+1)(1)$，我们可以把后面的 1 替代掉前面的 x，即 $(\lambda x.x+1)(1) = 1+1 = 2$，这一步称作「$\beta$ 规约」。

如果你对符号不敏感，可能看到这里有点晕。但如果你敏感一点的话，就会发现这里其实只不过是换了一个说法的「匿名函数」而已。像我们之前的例子里，我们定义函数都要起一个函数名。但如果我们一次性使用这个函数，我们完全可以不命名，定义完接受的参数和运算方法直接执行即可，这就是所谓的「匿名函数」。用 JavaScript 的语言来描述的话如下：

// alpha 等价
(x) => x
(y) => y
// 这两个东西是等价的

// beta 规约
((x) => x + 1)(1) // => 1 + 1 => 2

如果你不熟悉 ES6 的箭头函数，用 ES5 写的话如下：

// alpha 等价
function (x) { return x }
function (y) { return y }
// 这两个东西是等价的

// beta 规约
(function (x) { return x + 1 })(1) // => 1 + 1 => 2

换句话说，也就是说「$\alpha$ 等价」说明了匿名函数中的变量名不会影响运算结果，而「$\beta$ 规约」就是去执行这个匿名函数而已。

为什么？

我们之前讨论了一个递归和循环的例子，这和「匿名函数」有什么关系呢？我们可以看到，我们现在的匿名函数看起来很方便，但是实际上用来实现递归和循环听起来就很奇怪。首先，纯「$\lambda$ 演算」并没有像是 while 或 for 这样的循环命令。不过好在我们刚刚发现，所有的循环都可以被我们转换成递归

递归听起来就和函数更相关一些，不过我们又产生了一个新问题：递归时，我们需要具名地指定我们递归调用那个函数。而我们现在的函数，没有名字。我们还能实现递归吗？

尝试

我们先大致写一个类似递归的匿名函数：

((n) => {
  if (n === 0) return 0
  return n + // 我不知道这里要加什么东西
})(10) // 应该要输出 55

不过既然递归要调用一个函数，我们先假设我们存在这个函数，将其命名为 f：

((n) => {
  if (n === 0) return 0
  return n + f(n - 1)
})(10) // 应该要输出 55

我们可以想象，对于匿名函数，如果没有全局变量，那么其获取数据的来源是唯一的，那就是参数。那我们为什么不把我们想要的函数 f 作为参数呢？

((f, n) => {
  if (n === 0) return 0
  return n + f(n - 1)
})(10) // 应该要输出 55

这样似乎已经快到我们想要的结果了，既然我们加了一个参数 f，那么在执行的时候，这个 f 又是多少呢？答案很简单，就是这个匿名函数自己。匿名函数不能起名字，但其本身还是可以作为参数传递啊，于是我们得到了：

((f, n) => {
  if (n === 0) return 0
  return n + f(f, n - 1)
})(((f, n) => {
  if (n === 0) return 0
  return n + f(f, n - 1)
}), 10) // # => 55

解决！我们使用了纯匿名函数解决了这个问题。

Y 组合子

那什么是 Y 组合子（Y Combinator）呢？Y 组合子不过是解决这一类问题的通用方案而已。Y 组合子的定义是

\[Y := \lambda f.(\lambda x.(f (x\ x)) \lambda x.(f (x\ x)))\]

听起来挺搞脑子的，不过如果我们代入任何一个东西算一下的话，就会发现其实很简单。如果我们存在一个函数 g，那么：

\[\begin{align} Y\ g & = \lambda f.(\lambda x.(f (x\ x)) \lambda x.(f (x\ x))) g \\\\ & = \lambda x.(g (x\ x)) \lambda x.(g (x\ x)) \\\\ & = \lambda y.(g (y\ y)) \lambda x.(g (x\ x)) \\\\ & = (g (\lambda x.(g (x\ x)) \lambda x.(g (x\ x)))) \\\\ \end{align}\]

而同时：

\[\begin{align} g (Y\ g) & = g (\lambda f.(\lambda x.(f (x\ x)) \lambda x.(f (x\ x))) g) \\\\ & = (g (\lambda x.(g (x\ x)) \lambda x.(g (x\ x)))) \\\\ \end{align}\]

故 $Y g = g (Y\ g) = g (g (Y\ g)) = g (g (g (Y\ g))) $，也就是对于任意函数都能实现递归。

这里我们再使用 JavaScript 来实现一下 Y 组合子版的自然数列 1 到 n 的和：

// \lambda f.(\lambda x.(f (x x)) \lambda x.(f (x x)))
const Y = fn => (f => fn(x => f(f)(x)))(f => fn(x => f(f)(x)))

g = f => n => {
  if (n === 0) return 0
  return n + f(n - 1)
}

Y(g)(10) // => 55

不动点组合子

你也许听过 Y 组合子是一类不动点组合子。不动点组合子究竟是什么意思呢？组合子是一种消除变量的函数。在 Y 组合子中你可以看到并没有用任何 let var const 之类的变量定义，而是通过一系列参数传递消除了这一过程。而至于不动点，你可能在初中的代数课本上学习过「不动点」的概念，这在这里几乎是一样的。通常我们眼中的不动点，即在函数 $f(x) = y$ 上找到一个值 x 使得 $x = f(x)$。比如对于函数 $f(x) = x^2 - 1$，不动点是 1 和 -1。

但是初中的代数中的这个不动点的定义其实是一个简化版本。事实上所谓找到一个「值」x，也可以被表述成「找到一个『函数』」g(x)，使得 $g(x) = f(g(x))$。而值 x 是这个 g(x) 的一个特例，即常值函数 g(x) = c（c 是一个常数）。

这样我们就不难理解不动点组合子的意义了。我们找到一个函数 Y，使得 $Y\ g = g(Y\ g)$。这就是所谓的不动点组合子。

结论

费了那么大劲到底干什么？因为图灵机、递归和 $\lambda$ 演算被证明在可计算性上是等价的，如果存在一个问题（比如递归或者循环）在其中一种可计算，在另一种不可计算。这是有悖于数学原理的。而更重要的是，我们基于 Y 组合子这个例子，可以一次性将图灵机、递归和 $\lambda$ 演算的知识一次性串联起来，建立一个对可计算性的直观系统的理解。

岂不是很好吗？