这学期在学校选了一门讲可计算性(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$ 演算」并没有像是 whilefor 这样的循环命令。不过好在我们刚刚发现,所有的循环都可以被我们转换成递归

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

尝试

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

((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$ 演算的知识一次性串联起来,建立一个对可计算性的直观系统的理解。

岂不是很好吗?