A brief introduction to Y-Combinator

为什么要写这篇：当我们谈论计算机科学时，lambda 演算算得上其中最抽象，同时又是最优雅的一部分了。它可以构建出一些很神奇的东西，例如神奇的丘奇数（church numeral），用函数定义了所有的自然数和运算。3 月初出于兴趣了解了一下什么是 Y-组合子，当时恰好手写了一些笔记，但更多是对于别人的知识的整理，我个人水平有限，对于这块理论学习不多，就当作写博客练练手吧，如果能让读者产生一丝“计算机科学还挺有意思”的想法就再好不过啦~

当我们需要创建一个递归函数时，如果写成 lambda 表达式，我们可以写成

python

f = lambda x: 1 if x == 0 else x * f(x - 1)

但是假如我给定一个奇怪的规则：不允许使用赋值符号，也就是不能用 f = ...，此时我们创建的就是匿名函数，还能实现同样的递归函数吗？

在上面的例子中，调用 f(4) 可以得到 24，我们要做的就是定义一个 ?，然后立即调用它（因为不能把它存下来），即 (?)(4) 的结果是 24。这看上去挺难的，我们要在 ? 的函数体内递归调用自己，而此时 ? 甚至都没有名字！

为了做到这件事，我们要转换下思维，用上“高阶函数”的概念：不再局限于函数参数只能是一个值，它还可以是一个“函数”。假设有这样一个神奇的函数 g，把 f 作为参数传给它，它返回我们需要的 ?。这时，我们可以在 g 的函数体内调用 f 了

python

g = lambda f: (lambda x: (1 if x == 0 else x * (f f)(x - 1)))

这里为什么是 (f f) 呢？因为我们想要实现 g(x-1) 的效果，但我们手头能用的只有 f 这个传进来的参数，不妨想象 f 跟 g 有类似的性质：f 传入一个函数也能返回想要的 ?。那么自然就需要先让 f 作用于自身，得到 ?，再进行 ?(x-1) 的调用。这样解释似乎有些从结果反过来说的意味，事实上如果接受了这种写法，我们要实现的 ? 也就得到了：g(g)

python

g(g)(4)
= (lambda f: (lambda x: (1 if x == 0 else x * (f f)(x - 1))))(g g)(4)
= (lambda x: (1 if x == 0 else x * (g g)(x - 1)))(4)
= 4 * (g g)(3)
= 4 * (lambda x: (1 if x == 0 else x * (g g)(x - 1)))(3)
= 4 * (3 * (g g)(2))
= 4 * (3 * (lambda x: (1 if x == 0 else x * (g g)(x - 1)))(2))
= 4 * (3 * (2 * (g g)(1)))
= 4 * (3 * (2 * (lambda x: (1 if x == 0 else x * (g g)(x - 1)))(1)))
= 4 * (3 * (2 * (1 * (g g)(0))))
= 4 * (3 * (2 * (1 * (lambda x: (1 if x == 0 else x * (g g)(x - 1)))(0))))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

上面这段推导来自于 GPT，虽然此时我们还用了 g 这个名字，但 g 的表达式可是一个纯纯的函数表达式，把那串很长的 lambda 表达式替换 g，我们实际上得到了前面提到的匿名递归函数。想想还是挺妙的。

这种思想到底是怎么来的呢？继续考虑 g，如果对于一个递归函数 f，调用 g(f) 还是得到 f，这里的 g(f) = f 看上去跟不动点方程的表达式很像，我们把 f 称为 g 的不动点。

怎么求解不动点呢？假设存在一种解法可以求得 g 的不动点，设为 Y，有

f = Y g

对于不动点方程不断迭代下去，

f = g(g(g(...)))

这个无限长序列假设可以开方的话，可以简写成

f = G(G)
  = g(G(G))

把 G 写成定义的形式，就是

G = λG. g(G(G))

由 alpha-变换（函数的参数名可以任意替换，都是等价的），换名得到

G = λx. g(x x)

代入 Y g = f，得

Y g = f 
    = G(G)
    = (λx. g(x x))(λx. g(x x))

那么 Y = λg. (λx. g(x x))(λx. g(x x))，换名得到

Y = λf. (λx. f(x x))(λx. f(x x))

可以验证 Y 是满足不动点方程，即 f(Y) = Y 的，这便是大名鼎鼎的 Y-组合子，它是一种通用的构造递归函数的算子。

用 JavaScript 的箭头函数来实现，可以是

javascript

const Y = f => {
  const g = x => f(y => x(x)(y));
  return g(g);
};

Y(fac => n => {
  return n <= 1 ? 1 : n * fac(n - 1);
})(3); // 6

或者是

javascript

const Y = t => (f => f(f))(
  f => t(
    x => (f(f))(x)
  )
);

Y(fac => n => {
  return n <= 1 ? 1 : n * fac(n - 1);
})(3); // 6

回到一开始提出的问题，我们不可以写

javascript

const f = fac => n => {
  return n <= 1 ? 1 : n * fac(n - 1);
}

但是有了神奇的魔法 Y 之后，把上面的错误写法用魔法变换一下，就变成了可以正确计算的黑盒子！

JavaScript

const factorial = Y(fac => n => {
  return n <= 1 ? 1 : n * fac(n - 1);
});

console.log(factorial(3)); // 6

lambda 演算系统是一个形式系统，只有三条语法规则

x | λx. expr | expr expr

分别表示变量定义、函数定义、函数调用和两个操作

alpha-变换：变量任意替换
beta-规约：两个 λ 项，把右侧替换左侧，剩下一个 λ 项

可以证明，lambda 演算和图灵机的计算能力是等价的，而后者是使得今天一切通用计算机得以成立的计算模型。

参考知乎文章：

https://zhuanlan.zhihu.com/p/547191928

https://www.zhihu.com/question/21099081/answer/18830200

A brief introduction to Y-Combinator ​

A brief introduction to Y-Combinator