【专栏】康托尔、哥德尔、图灵——永恒的金色对角线（6）

不动点原理

然而，看看我们的P的定义，是不是很丑陋？“n*self(self, n-1)”？什么玩意？为什么要多出一个多余的self？DRY[1]！怎么办呢？我们想起我们一开始定义的那个失败的P，虽然行不通，但最初的努力往往是大脑最先想到的最直观的做法，我们来回顾一下：

let P = lambda self n. If_Else n==0 1 n*self(n-1)

这个P的函数体就非常清晰，没有冗余成分，虽然参数列表里面多出一个self，但我们其实根本不用管它，看函数体就行了，self这个名字已经可以说明一切了对不对？但很可惜这个函数不能用。我们再来回想一下为什么不能用呢？因为当你调用P(P, n)的时候，里面的self(n-1)会展开为P(n-1)而P是需要两个参数的。唉，要是这里的self是一个“真正”的，只需要一个参数的递归阶乘函数，那该多好啊。为什么不呢？干脆我们假设出一个“真正”的递归阶乘函数：

power(n):

if(n==0) return 1;

return n*power(n-1);

但是，前面不是说过了，这个理想的版本无法在lambda算子系统中定义出来吗（由于lambda函数都是没名字的，无法自己内部调用自己）？不急，我们并不需要它被定义出来，我们只需要在头脑中“假设”它以“某种”方式被定义出来了，现在我们把这个真正完美的power传给P，这样：

P(power, 3)

注意它跟P(P, 3)的不同，P(P, 3)我们传递的是一个有缺陷的P为参数。而P(power, 3)我们则是传递的一个真正的递归函数power。我们试着展开P(power, 3):

IF_Else 3==0 1 3*power(3-1)

发生了什么？power(3-1)将会计算出2的阶乘（别忘了，power是我们设想的完美递归函数），所以这个式子将会忠实地计算出3的阶乘！

作者：刘未鹏 出版：电子工业出版社

回想一下我们是怎么完成这项任务的：我们设想了一个以某种方式构造出来的完美的能够内部自己调用自己的递归阶乘函数power，我们发现把这个power传给P的话，P(power, n)的展开式就是真正的递归计算n阶乘的代码了。

你可能要说：废话！都有了power了我们还要费那事把它传给P来个P(power, n)干嘛？直接power(n)不就得了？别急，之所以设想出这个power只是为了引入不动点的概念，而不动点的概念将会带领我们发现Y combinator。

什么是不动点？一点都不神秘。让我们考虑刚才的power与P之间的关系。一个是真正可递归的函数，一个呢，则是以一个额外的self参数来试图实现递归的伪递归函数，我们已经看到了把power交给P为参数发生了什么，对吧？不，似乎还没有，我们只是看到了，“把power加上一个n一起交给P为参数”能够实现真正的递归。现在我们想考虑power跟P之间的关系，直接把power交给P如何？

P(power)

这是什么？这叫函数的部分求值(partial evaluation)。换句话说，第一个参数是给出来了，但第二个参数还悬在那里，等待给出。那么，光给一个参数得到的是什么呢？是“还剩一个参数待给的一个新的函数”。其实也很简单，只要按照Beta转换规则做就是了，把P的函数体里面的self出现处皆替换为power就可以了。我们得到：

IF_Else n==0 1 n*power(n-1)

当然，这个式子里面还有一个变量没有绑定，那就是n，所以这个式子还不能求值，你需要给它一个n才能具体求值，对吧。这么说，这可不就是一个以n为参数的函数么？实际上就是的。在lambda算子系统里面，如果给一个lambda函数的参数不足，则得到的就是一个新的lambda函数，这个新的lambda函数所接受的参数也就是你尚未给出的那些参数。换句话来说，调用一个lambda函数可以分若干步来进行，每次只给出一部分参数，而只有等所有参数都给齐了，函数的求值结果才能出来，否则你得到的就是一个“中间函数”。

那么，这跟不动点定理有什么关系？关系大了，刚才不是说了，P(power)返回的是一个新的“中间函数”嘛？这个“中间函数”的函数体我们刚才已经看到了，就是简单地展开P(power)而已，回顾一遍：

IF_Else n==0 1 n*power(n-1)

我们已经知道，这是个函数，参数n待定。因此我们不妨给它加上一个“lambda n”的帽子，这样好看一点：

lambda n. IF_Else n==0 1 n*power(n-1)

这是什么呢？这可不就是power本身的定义？（当然，如果我们能够定义power的话）。不信我们看看power如果能够定义出来像什么样子：

let power = lambda n. IF_Else n==0 1 n*power(n-1)

一模一样！也就是说，P(power)展开后跟power是一样的。即：

P(power) = power

以上就是所谓的不动点。即对于函数P来说power是这样一个“点”：当把P用到power身上的时候，得到的结果仍然还是power，也就是说，power这个“点”在P的作用下是“不动”的。

可惜的是，这一切居然都是建立在一个不存在的power的基础上的，又有什么用呢？可别过早提“不存在”这个词，你觉得一样东西不存在或许只是你没有找到使它存在的正确方法。我们已经看到power是跟P有着密切联系的。密切到什么程度呢？对于伪递归的P，存在一个power，满足P(power)=power。注意，这里所说的“伪递归”的P，是指这样的形式：

let P = lambda self n. If_Else n==0 1 n*self(n-1) // 注意，不是self(self,n-1)

一般化的描述就是，对任一伪递归F（回想一下伪递归的F如何得到——是我们为了解决lambda函数不能引用自身的问题，于是给理想的f加一个self参数从而得到的），必存在一个理想f（F就是从这个理想f演变而来的），满足F(f) = f。

那么，现在的问题就归结为如何针对F找到它的f了。根据F和f之间的密切联系（F就比f多出一个self参数而已），我们可以从F得出f吗？假设我们可以（又是假设），也就是说假设我们找到了一根魔棒，把它朝任意一个伪递归的F一挥，眼前一花，它就变成了真正的f了。这根魔棒如果存在的话，它具有什么性质？我们假设这个神奇的函数叫做Y，把Y用到任何伪递归的函数F上就能够得到真正的f，也就是说：

Y(F) = f

结合上面的F(f) = f，我们得到：

Y(F) = f = F(f) = F(Y(F))

也就是说，Y具有性质：

Y(F) = F(Y(F))

性质倒是找出来了，怎么构造出这个Y却又成了难题。一个办法就是使用抽象法，这是从工程学的思想的角度，也就是通过不断迭代、重构，最终找到问题的解。然而对于这里的Y combinator，接近问题解的过程却显得复杂而费力，甚至过程中的有些点上的思维跳跃有点如羚羊挂角无迹可寻。然而，在这整个Y combinator介绍完了之后我们将会介绍著名的哥德尔不完备性定理，然后我们就会发现，通过哥德尔不完备性定理证明中的一个核心构造式，只需一步自然的推导就能得出我们的Y combinator。而且，最美妙的是，还可以再往下归约，把一切都归约到康托尔当初提出的对角线方法，到那时我们就会发现原来同样如羚羊挂角般的哥德尔的证明其实是对角线方法的一个自然推论。数学竟是如此奇妙，我们由简单得无法再简单的lambda calculus系统的两条公理居然能够导出如此复杂如此令人目眩神迷的Y Combinator，而这些复杂性其实也只是荡漾在定理海洋中的涟漪，拨开复杂性的迷雾我们重又发现它们居然寓于极度的简洁之中。这就是数学之美。

让我们先来看一看Y combinator的费力而复杂的工程学构造法，我会尽量让这个过程显得自然而流畅^[2]：

我们再次回顾一下那个伪递归的求阶乘函数：

let P = lambda self n. If_Else n==0 1 n*self(n-1)

我们的目标是找出P的不动点power，根据不动点的性质，只要把power传给P，即P(power)，便能够得到真正的递归函数了。

现在，关键的地方到了，由于：

power = P(power) // 不动点原理

这就意味着，power作为一个函数（lambda calculus里面一切都是函数），它是自己调用了自己的。那么，我们如何实现这样一个能够自己调用自己的power呢？回顾我们当初成功的一次尝试，要实现递归，我们是通过增加一个间接层来进行的：

let power_gen = lambda self. P(self(self))

还记得self(self)这个形式吗？我们在成功实现出求阶乘递归函数的时候不就是这么做的？那么对于现在这个power_gen，怎么递归调用？

power_gen(power_gen)

不明白的话可以回顾一下前面我们调用P(P, n)的地方。这里power_gen(power_gen)展开后得到的是什么呢？我们根据刚才power_gen的定义展开看一看，原来是：

P(power_gen(power_gen))

看到了吗？也就是说：

power_gen(power_gen) => P(power_gen(power_gen))

现在，我们把power_gen(power_gen)当成整体看，不妨令为power，就看得更清楚了：

power => P(power)

这不正是我们要的答案么？

OK，我们总结一下：对于给定的P，只要构造出一个相应的power_gen如下：

let power_gen = lambda self. P(self(self))

我们就会发现，power_gen(power_gen)这个调用展开后正是P(power_gen(power_gen))。也就是说，我们的power_gen(power_gen)就是我们苦苦寻找的不动点了！

【注释】

[1]“Don't Repeat Your self”的缩写。

[2]g9的Blog(负暄琐话)上有一系列介绍lambda calculus的文章。有两篇就是介绍Y Combinator的，其中有一篇以JavaScript语言描述了迭代式逐步抽象出Y Combinator的过程。

（待续；此文的修订版已收录《暗时间》一书，由电子工业出版社2011年8月出版。作者于2009年7月获得南京大学计算机系硕士学位，现在微软亚洲研究院创新工程中心从事软件研发工程师工作。）