Y 组合子的一个启发式推导

2023-05-15
北京
本文字数：4317 字
阅读完需：约 14 分钟

Y Combinator 是 Lambda 演算理论中的一个关键性概念，通过它我们可以实现匿名的递归调用函数。关于它的解释，一般是所谓的“懂的都懂”，换句话说，不懂的人看了之后，大概还是不懂。在本文中，我希望提供一个启发式的推导，尽量使得 Y 组合子的构造显得直观一些。为了方便对 lambda 演算不熟悉的同学，在附录一节中我也增加了一段对 lambda 演算规则的简短介绍。

一. Y Combinator

首先，我们来看一下递归函数的基本形式：

let f = x => 函数体中用f指代自身，实现递归调用// 例如阶乘函数let fact = n => n < 2 ? 1 : n * fact(n-1)

复制代码

上述递归函数是所谓的一阶递归函数，即定义中只引用自身导致递归的函数

我们看到，递归函数的实现体中通过函数名 f 引用了自身。如果我们希望消除这个对自身的引用，就必须把它转换为一个参数。从而得到

let g = f => x => 函数体中用f表示原递归函数

复制代码

函数 g 相当于是在 f 的基础上加盖了一层，使它成为了一个高阶函数。因为 f 是任意的某个递归函数，关于函数 g，我们唯一知道的就是它能作用到函数 f 上。

g(f) = x => 函数体中的f通过闭包变量引用了参数f

复制代码

显然 g(f)的返回值就是我们所需要的目标递归函数，由此我们得到了所谓的不动点方程

g(f) = f

复制代码

函数 g 作用于参数 f 上，返回的结果也等于 f，在这种情况下，f 称作是函数 g 的不动点。

现在我们可以制定一个构造匿名的递归函数的标准程序：

根据命名函数 f 定义辅助函数 g
求解函数 g 的不动点

假设存在一个标准解法可以得到 g 的不动点，我们把这个解法记作 Y，

f = Y g  ==>  Y g = g (Y g)

复制代码

Y 这个解法如果存在，它到底长什么样？为了求解不动点方程，一个常用的方法是迭代法：我们反复应用原方程，然后考察系统演进的结果。

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

复制代码

如果完全展开，则 f 对应于一个无限长的序列。假设这个无限长的序列可以开平方

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

复制代码

如果存在这样的函数 G，它的定义是什么？幸运的是 G(G) = g(G(G))本身就可以被看作是函数 G 的定义

G(G) = g(G(G)) ==> G = λG. g(G(G)) = λx. g(x x)

复制代码

上式中的最后一个等号对应于函数的参数名重命名，即λ演算中的所谓 alpha-变换。

在 G 已知的情况下，Y 的定义就很显然了

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

复制代码

上式中(1)是直接代入 G 的定义。而(2)是把 Y g 看作是对 Y 的定义

 Y g = expr ==> Y = λg. expr

复制代码

我们可以继续执行 alpha-变换，改变参数名，从而使得 Y 组合子的定义成为一般文献中常见的样子。

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

复制代码

可以验证，Y 确实满足不动点方程

上图中的 Y 实际上是 Y f，即 Y 作用到 f 上的结果，因此它验证了 Y f = f(Y f)。

二. 递归的本质 G(G)

上一节的推导中，最关键的步骤是 f = G(G)，即我们把递归函数开平方分解为 G 函数作用到自身上的结果。下面我们通过一个具体的例子来加深对这个结构的必然性的理解。

所谓的递归函数，其内部必然存在着两种结构：递归结构和(无递归的)计算结构。例如

let fact = n => n < 2 ? 1 : n * fact(n-1)// 或者写成函数声明的形式function fact(n){    return n < 2 ? 1: n*fact(n-1)}

复制代码

fact 函数既完成了本步骤的计算，又通过 fact 名称引用自身实现了递归。

如果我们试图把递归结构和计算结构分离，可以定义如下纯计算结构（所有计算中用到的变量都是参数传递过来的，不存在自引用而产生的递归）

function fact0(fact, n){    return n < 2 ? 1 : n * fact(n-1)}// 或者使用lambda表达式形式const fact0 = fact => n => n < 2 ? 1 : n * fact(n-1)

复制代码

如果递归结构可以被抽象到一个算子 Y 中，则我们可以期望通过如下调用形式为 fact0 增加递归结构。

Y(fact0)(n) = fact(n), fact = Y(fact0)

复制代码

即算子 Y 可以看作是一个加工器，它吃入无递归的 fact0，吐出带有递归功能的 fact。fact0 是一个两参数函数，而生成的 fact 是一个单参数函数。

接下来，我们注意到，fact0 是我们认为已经存在的东西，而 fact 是某种需要我们去构造的、未知的东西，fact0 的定义中同时包含已知和未知的量，因此我们有必要将 fact0 的定义改写为完全基于已知量来构造

const fact1 = fact1 => n => n < 2 ? 1: n * fact1(fact1)(n-1)

复制代码

上式中，函数体内的 fact1 实际指向的是参数名 fact1，而不是函数名。如果觉得命名容易混淆，我们可以再次改写为

const fact1 = self => n => n < 2 ? 1 : n * self(self)(n-1)

复制代码

我们可以验证，fact(n)等价于 fact1(fact1)(n)

Y(fact0)(n) = fact(n) = fact1(fact1)(n)

复制代码

对比等式两边，可以得知

Y(fact0) = fact1(fact1), 也就是上一节中的 Y g = G(G)

复制代码

通过以上的分析，我们注意到递归函数中必然出现的一个基本结构x(x)。

如果我们定义如下的函数

function w(x){   return x(x)}// 或者写成lambda表达式形式const w = x => x(x)

复制代码

显然 w(G)=G(G)，w(w)提供了一个最简单也是最本质的无限循环形式。在 lambda 演算理论中，上述 w 函数被称为是 Omega 组合子，

ω : = λ x . x x

Ω : = ω ω = (λ x . x x) (λ x . x x)

$$(\lambda x.x x)(\lambda x.x x) \mapsto (\lambda x.x x)[x\mapsto (\lambda x.x x)]\mapsto (\lambda x.x x)(\lambda x.x x)\

也就是说

ω ω = ω ω

w 作用于自身，可以不断的产生自身，因此 x(x)可以编码无限循环，那么为任意函数 F 引入无限循环的能力，可以采用如下形式

const wF = x => F(x(x))

复制代码

注意, w 函数是直接返回x(x)，而 wF 是把x(x)送入函数 F 作为参数。参考上文中对 fact0 函数的分析，wF 相当于是将 fact0 中的 fact 函数调用替换为fact1(fact1)。

wF 函数对应于

ω_{F} : = λ x . F (x x)

Y 组合子的定义对应于

Y_{F} : = ω_{F} ω_{F} = (λ x . F (x x)) (λ x . F (x x))

写成 JavaScript 函数，形式为

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

复制代码

三. Z Combinator

如果我们真的按照上一节的形式来实现 Y 组合子，我们会发现Y(fact0)(3)抛出了堆栈溢出的错误，并没有得到计算结果fact(3)。

这是因为 JavaScript 采用的是 Call-by-value 调用约定(CBV)，它的参数的值在传入函数之前就必须被计算出来，而 f(x(x))调用会产生死循环。

为了解决这个问题，在 JavaScript 中实现 Y 组合子，我们需要将参数改造成延迟求值的，简单的说，就是把直接的参数改造成一个延迟加载的函数，这一步对应于λ 演算中所谓的 eta-规约。

- Y = λf.(λx.f (x x)) (λx.f (x x))+ Z = λf.(λx.f (λy. (x x) y)) (λx. f (λy. (x x) y))

复制代码

通过这种方式我们得到的就是所谓的 Z 组合子。对应到 JavaScript 中

function Z(f) {    const g = x => {-       return f(x(x));+       return f(y => x(x)(y));    };    return g(g);}
fact(n) == Z(fact0)(n)

复制代码

四. Turing Combinator

函数的不动点组合子并不是只有 Y Combinator，实际上它是无限多的。我们重新回顾一下不动点的定义

f_{*} = f (f_{*}) f_{*} = Θ f Θ f = f (Θ f)

仿照第一节中的做法递归展开，我们可以得到一个新的递归方程

Θ f = f (f (Θ f)) = f (f (. . . f)) = Θ^{'} Θ^{'} f = f (Θ^{'} Θ^{'} f)

Θ \equiv Θ^{'} Θ^{'}

Theta'的定义可以从上式中直接读出来

Θ^{'} Θ^{'} f = Θ^{'} (Θ^{'}) (f) = (λ Θ^{'} λ f . f (Θ^{'} Θ^{'} f)) (Θ^{'}) (f)

Θ^{'} : = λ t . λ f . f (t t f)

通过这种分解方式得到的 Theta 就是所谓的图灵组合子。

五. 更多的不动点组合子

上述启发式构造方法是我很早之前提出的，今天仔细想了一下，发现它相当通用，可以用来发现其他的不动点组合子。例如

如果我们不是对无穷序列开平方，而是保留中间的一个 g，我们可以得到

f = G g G = g (G g G)  对比Y组合子对应  G G = g(G G)

复制代码

从上述不动点方程我们可以直接读出 G 的定义

G := λg. λG. g (G g G) = λy.λx. y(xyx)

复制代码

而不动点组合子可以从如下方程直接读出

f = Y g = G g G  ==>  Y := λg. G g G = λy. G y G

复制代码

把 G 的定义代入，我们得到最终完全由匿名的 lambda 函数所构成的不动点组合子

Y := (λx.λy. xyx)(λy.λx. y(xyx))

复制代码

这是由John Tromp发现的一个组合子。

类似的，如果我们选择开立方而不是开平方，可以得到

G G G = f (G G G) ==> G := λxy. f(x y x)Y g = G G G       ==> Y := λg. G G G = λf.(λx. xxx)(λxy. f(x y x))

复制代码

在 javascript 中的实现对应于

const Y3 = f =>{    const g = (x,y) => {       return f(u => x(y,x)(u));    };    return g(g,g)}

复制代码

可以验证 Y3(fact0) == fact。

Y 组合子的形态在很多程序语言中看起来都有点吓人，所以可能很多人一直都在疑惑这么复杂的东西是怎么想出来的，为什么要选择 f = G(G)这种分解形式？事实的真相是，压根没有什么为什么。选择开平方完全是一个很随意的选择（或者说最简单的选择）。如果不选择开平方，还可以选择开立方f=G G G，或者选择做个夹心饼干f=G g G，如果你乐意，你甚至可以做个千层饼。同样的套路你可以反复套用，产生无限多的不动点组合子。

附录：lambda 演算（Lambda calculus)

λ 演算号称是最简单、最小化的一个形式系统，它包含三条语法规则

x | λx.expr | expr expr

复制代码

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

以上三种情况分别对应 JS 中的

xx => exprexpr(expr)例如expr0 = 2expr1 = x => x + 1expr1(expr0) = 2 + 1

复制代码

λ 演算的惊人之处在于仅仅依赖上述三条规则，我们就可以完成所有通用计算，它就是最简形式的通用编程语言！

约定：

函数的作用是左结合的. 这意味着 f x y ≡ (f(x)y)
λ操作符被绑定到它后面的整个表达式
这样可以省略很多括号, 例如 ((λx.(x x))(λy.y))可以简写为 (λx.x x)λy.y

三条公理：

alpha-变换：函数参数名是随意取的
λx.(λx.x)x 与λy.(λx.x)y 是等价的。
beta-归约：函数应用（运算过程）就是符号模板的替换过程。
(λx. M) N 表示将函数体 M 中所有名称为 x 的符号都替换为 N。例如(λf.f 3)(λx.x+2) = (λx.x+2)3 = 3 + 2 = 5

这里存在一个隐含的内在复杂性：没有一个通用的方法来判定两个λ表达式是否等价。Church 提出 lambda 演算就是为了证明这个定理，从而否证希尔伯特判定性问题。