Y Combinator 推导

什么是Y Combinator

Y Combinator这个东西,确实有些绕。

Y Combiantor在工程中几乎没有任何用处,可能用到它的场合,可以有无数种替代方案。它的存在仅仅是为了让lambda算子模型变得完备。

要解释什么是Y Combinator,首先得说明下何为lambda算子。

lambda calculus

lambda算子极其简洁,这里搬运(并翻译)下wikipedia中lambda算子的语法,并用常见的js语法对其做一些说明:

语法 名称 描述 js描述
a Variable 一个用于表示参数数学/逻辑值字符字符串 a
(λx.M) Abstraction 函数定义(M是一个lambda项)。其中,变量x被绑定在这个表达式中。 function(x) { return M; }
(M N) Application 将一个函数应用于一个参数。其中M和N均为lambda项。 M(N)

以上便是lambda算子的所有语法组成,极为简洁、易懂。

在此语法基础上,有两条同样简洁明了的变换规则:

运算 名称 描述 js描述
(λx.M[x]) → (λy.M[y]) α-变换 绑定的变量名称替换 function(x) { return x + 1; } → function(y) { return y + 1; }
((λx.M) E) → (M[x:=E]) β-规约 根据实参替换函数中绑定的参数 (function(x) { return x + 1; })(2) → 2 + 1;

以上就是lambda算子模型的整个系统。

Currying

在语法描述中,我们看到,Abstraction的参数部分只有一个参数。不管是数学,还是平时接触的c系语言,函数常常有多个输入。那么lambda算子应该怎么描述多参数的函数呢?

这里需要用到一个叫做Currying的技巧。

1
2
3
(function (x, y, z) {
return x + y + z
})(1, 2, 3)

可以写作

1
2
3
4
5
6
7
(function(x) {
return function(y) {
return function(z) {
return x + y + z
}
}
})(1)(2)(3)

这便是Currying,lambda算子中的“多个参数函数”表示为:传入一个参数,返回一个“捕获了这个参数”并“接收下一个参数”的函数。

递归???

lambda算子里没有任何循环的影子。我们都知道,任何循环和递归都能相互转化。既然不存在循环,那么只要函数能够递归即可。

然而很不幸,lambda算子也无法实现递归。递归需要调用自己,要调用,就得知道函数名,然而lambda算子不存在“函数名”这一概念,所谓的Variable也只是函数形参以及函数体中的使用而已。

那怎么办?难道lambda算子没有实际意义吗?

而事实已经告诉我们lambda算子与图灵机是等价的,它可以计算任何可计算问题。所以总有一种方法能够将循环带入lambda算子模型中。

虽然我们没有办法定义一个函数自己的名字,但是我们能够定义函数参数的名字,如果参数f是一个函数,那么我们只需要把f传入f,不就相当于完成了递归吗?
举一个实际例子:计算阶乘时,在js里,我们能够这样写:

1
2
fac = (f, n) => n === 1 ? 1 : n * f(f, n-1)
fac(fac, 5) // 120

但是,要知道,lambda算子里没有函数名这一概念,也就是说,我们没有办法定义fac这个variable。所以这个表达式会写作:

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

永远也写不完。为了解决这个问题,我们需要引入一个概念,叫做“不动点”。

不动点

不动点,在数学中是指“被这个函数映射到其自身一个点”,可以写作x = F(x)。例如f(x) = x^2 - 3x + 4中,f(2) = 2,因此2是函数f(x)的不动点。

上述例子的f是一个一阶函数,不动点是一个值;那么,如果f是一个高阶函数,那么“不动点”不就是一个函数了吗?

暂时回到上面fac的例子。Currying一下,则可以得到:

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

我们根据不动点的性质x = F(x),若令x = fac(f),可以得到fac(f) = F(fac(f))fac中的f,虽然lambda算子里不能传fac,但是我们希望传入的的确是fac,所以f(f)即为fac(f)。也就是说,如果我们能够找到一个F,用于替代f(f),那么所谓的“递归”就变得可行了。

计算一个函数的不动点的算子,我们称之为Y Combinator

Y Combinator 推导

我们希望有这样的结果:使用Y Combinator计算“某个函数”的不动点,该不动点是一个函数;接着传入一个参数,作为实际“递归”计算的起始值。在计算阶乘fac的这个例子中,可以写作:

1
Y(fac0)(5) // result: 120

我们依然使用fac进行推导,我们目前拿到的是fac的Currying后的模式。后面将一步步提取出fac0*,并导出Y

实际上fac0就是fac,见后面推导。

1
2
3
fac = f => n => n === 1 ? 1 : n * f(f)(n-1)
// 调用:
fac(fac)(5)

将实际运算做一层封装,将f和n作为参数传入

1
2
3
fac = f => n => (g => h => h === 1 ? 1 : h * g(g)(h-1))(f)(n)
// 调用:
fac(fac)(5)

我们发现这个函数中有一个g(g),那么我们稍微修改一下,将g(g)替换为一个函数

1
2
3
fac = f => n => (g => h => h === 1 ? 1 : h * g(h-1))(f(f))(n)
// 调用:
fac(fac)(5)

提取该函数

1
2
3
4
fac0 = g => h => h === 1 ? 1 : h * g(h-1)
fac = f => n => fac0(f(f))(n)
// 调用:
fac(fac)(5)

将fac0作为参数传入,而不是写死(lambda算子不允许函数名)

1
2
3
4
fac0 = g => h => h === 1 ? 1 : h * g(h-1)
fac = g => f => n => g(f(f))(n)
// 调用:由于fac多了一个参数,所以调用时同样增加一个参数
fac(fac0)(fac(fac0))(5)

可以看到,fac(fac0)是重复的,我们可以对调用做一个简单的封装

1
2
3
4
fac0 = g => h => h === 1 ? 1 : h * g(h-1)
fac = g => f => n => g(f(f))(n)
// 调用:
(g => g(g))(fac(fac0))(5)

这时能看到,调用有了一丝Y的影子。现在我们尝试把fac0单独提出去

1
2
3
4
fac0 = g => h => h === 1 ? 1 : h * g(g)(h-1)
fac = g => f => n => g(f(f))(n)
// 调用:
(p => q => (g => g(g))(p(q)))(fac)(fac0)(5)

ok,这时调用已经完整的以Y的形式展现了,我们把“调用”的Y部分提取一下

1
2
3
4
5
fac0 = g => h => h === 1 ? 1 : h * g(g)(h-1)
fac = g => f => n => g(f(f))(n)
Y = (p => q => (g => g(g))(p(q)))(fac)
// 调用:
Y(fac0)(5)

这时我们不必再考虑调用fac0了。
我们把fac代入Y

1
Y = (p => q => (g => g(g))(p(q)))(g => f => n => g(f(f))(n))

根据β-规约,化简一下

1
2
3
4
// 代入p
Y = q => (g => g(g))((g => f => n => g(f(f))(n))(q))
// 代入后面那个g
Y = q => (g => g(g))(f => n => q(f(f))(n))

根据α-变换,改一下变量名,好看点

1
Y = x => (g => g(g))(y => z => x(y(y))(z))

到此,我们已经找到了Y Combinator。再检查一下,我们推导过程中声明了许多中间变量,但是可以看到,没有任何的依赖关系,它们相互之间是完全独立的函数,并且,它们完全符合lambda算子模型的所有要求。

我们可以试验一下我们的成果:

1
(x => (g => g(g))(y => z => x(y(y))(z)))(g => h => h === 1 ? 1 : h * g(h-1))(5)

结果是120,ok。

结论

我们回顾一下fac0这个函数:

1
fac0 = g => h => h === 1 ? 1 : h * g(h-1)

做一下α-变换,转换为fac0 = f => n => n === 1 ? 1 : n * f(n-1)后发现和最初我们写的那个fac一模一样。也就是说,Y Combinator计算出了最初那个fac函数的不动点!

另外,有同学可能发现y => z => x(y(y))(z)中的z似乎没有任何意义,毕竟return function(x) { return some_func(x); }还不如直接return some_func
也就是说,应当可以写作Y = x => (g => g(g))(y => x(y(y)))
但是在js、或者主流的c、java、go等call by value的语言中,省略z意味着无限递归。具体原因或者证明解释起来有点麻烦,但是相信大家脑中都能隐约体会这一点(而且实际也是如此),此处不再详提。对于call by need的语言(大多数LISP|ML|HASKELL)来说,是可以省略的。

wikipedia给出的Y Combinator描述是这样的:

\lambda f.(\lambda y.y\ y)\ (\lambda z.f\ (z\ z))

这和我们得出的“省略z”的写法完全相同。

应用

推导了这么多,那么,Y Combinator有什么实际应用吗?在主流的c系语言,甚至是主流函数式语言中,答案都是:没有作用。

对于c来说,就是一个循环的事;对于Haskell或者ML来说,就是一个递归的事,为什么要用Y Combinator来算不动点呢?

实际上在开头也提过,Y Combinator的确“没有用”,它只是为了lambda逻辑完备而提出的一个工具,具体实现中变通的方式很多,没有它也一样能做的很好。