|
2.3. 不动点原理 2.3.1. 假想一个函数，得到简洁的递归 然而，看看我们的
P 的定义，是不是很丑陋？ “n*self(self, n-1)” ？什么玩意？为什么要多出一个多余的 self ？ DRY
！怎么办呢？我们想起我们一开始定义的那个失败的 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 。 2.3.2. 使用部分求值观察“不动点” 什么是不动点？一点都不神秘。让我们考虑刚才的
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 的作用下是 “ 不动 ” 的。 2.3.3. 构造“不动点”函数 2.3.3.1. 能生成“不动点”函数的函数：Y 可惜的是，这一切居然都是建立在一个不存在的
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)) // （3）能生成不动点函数的函数性质 性质倒是找出来了，怎么构造出这个 Y 却又成了难题。一个办法就是使用抽象法，这是从工程学的思想的角度，也就是通过不断迭代、重构，最终找到问题的解。然而对于这里的 Y combinator
，接近问题解的过程却显得复杂而费力，甚至过程中的有些点上的思维跳跃有点如羚羊挂角无迹可寻。然而，在这整个 Y combinator
介绍完了之后我们将会介绍著名的哥德尔不完备性定理，然后我们就会发现，通过哥德尔不完备性定理证明中的一个核心构造式，只需一步自然的推导就能得出我们的
Y combinator
。而且，最美妙的是，还可以再往下归约，把一切都归约到康托尔当初提出的对角线方法，到那时我们就会发现原来同样如羚羊挂角般的哥德尔的证明其实是对角线方法的一个自然推论。数学竟是如此奇妙，我们由简单得无法再简单的
lambda calculus 系统的两条公理居然能够导出如此复杂如此令人目眩神迷的 Y Combinator
，而这些复杂性其实也只是荡漾在定理海洋中的涟漪，拨开复杂性的迷雾我们重又发现它们居然寓于极度的简洁之中。这就是数学之美。 2.3.3.2. 构造函数Y 让我们先来看一看 Y combinator 的费力而复杂的工程学构造法，我会尽量让这个过程显得自然而流畅 [7] ： 我们再次回顾一下那个伪递归的求阶乘函数： 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) 就是我们苦苦寻找的不动点了！ 2.4. 铸造 Y Combinator 现在我们终于可以铸造我们的 Y Combinator 了， Y Combinator 只要生成一个形如 power_gen 的 lambda 函数然后把它应用到自身，就大功告成： let Y = lambda F. let f_gen = lambda self. F(self(self)) return f_gen(f_gen) 稍微解释一下，
Y 是一个 lambda 函数，它接受一个伪递归 F ，在内部生成一个 f_gen （还记得我们刚才看到的 power_gen 吧），然后把
f_gen 应用到它自身（记得 power_gen(power_gen) 吧），得到的这个 f_gen(f_gen) 也就是 F
的不动点了（因为 f_gen(f_gen) = F(f_gen(f_gen)) ），而根据不动点的性质， F 的不动点也就是那个对应于 F
的真正的递归函数！ 如果你还觉得不相信，我们稍微展开一下看看，还是拿阶乘函数说事，首先我们定义阶乘函数的伪递归版本： let Pwr = lambda self n. If_Else n==0 1 n*self(n-1) 让我们把这个 Pwr 交给 Y ，看会发生什么（根据刚才 Y 的定义展开吧）： Y(Pwr) => let f_gen = lambda self. Pwr(self(self)) return f_gen(f_gen) Y(Pwr) 的求值结果就是里面返回的那个 f_gen(f_gen) ，我们再根据 f_gen 的定义展开 f_gen(f_gen) ，得到： Pwr(f_gen(f_gen)) 也就是说： Y(Pwr) => f_gen(f_gen) => Pwr(f_gen(f_gen)) 我们来看看得到的这个 Pwr(f_gen(f_gen)) 到底是不是真有递归的魔力。我们展开它（注意，因为 Pwr 需要两个参数，而我们这里只给出了一个，所以 Pwr(f_gen(f_gen)) 得到的是一个单参（即 n ）的函数）： Pwr(f_gen(f_gen)) => If_Else n==0 1 n*f_gen(f_gen) (n-1) 而里面的那个 f_gen (f_gen) ，根据 f_gen 的定义，又会展开为 Pwr(f_gen(f_gen)) ，所以： Pwr(f_gen(f_gen)) => If_Else n==0 1 n* Pwr(f_gen(f_gen)) (n-1) 看到加粗的部分了吗？因为 Pwr(f_gen(f_gen)) 是一个接受 n 为参数的函数，所以不妨把它令成 f （ f 的参数是 n ），这样上面的式子就是： f => If_Else n==0 1 n*f(n-1) 完美的阶乘函数！ | 
