上接第一部分《图灵停机问题》 原文链接:https://blog.csdn.net/pongba/article/details/1336028 2. Y Combinator 了解 Y combinator 的请直接跳过这一节,到下一节 “ 哥德尔的不完备性定理 ” 。 让我们暂且搁下但记住绕人的图灵停机问题,走进函数式编程语言的世界,走进由跟图灵机理论等价的 lambda 算子发展出来的另一个平行的语言世界。让我们来看一看被人们一代一代吟唱着的神奇的 Y Combinator… 关于 Y Combinator 的文章可谓数不胜数,这个由师从希尔伯特的著名逻辑学家 Haskell B.Curry ( Haskell 语言就是以他命名的,而函数式编程语言里面的 Curry 手法也是以他命名) “ 发明 ” 出来的组合算子( Haskell 是研究 组合逻辑(combinatory logic) 的)仿佛有种神奇的魔力,它能够算出给定 lambda 表达式(函数)的 不动点 。从而使得递归成为可能。事实上,我们待会就会看到, Y Combinator 在神奇的表面之下,其实隐藏着深刻的意义,其背后体现的意义,曾经开出过历史上最灿烂的数学之花,所以 MIT 的计算机科学系将它做成系徽也就不足为奇了 [5] 。 当然,要了解这个神奇的算子,我们需要一点点 lambda 算子理论的基础知识,不过别担心, lambda 算子理论是我目前见过的最简洁的公理系统,这个系统仅仅由三条非常简单的公理构成,而这三条公理里面我们又只需要关注前两条。 以下小节 ——lambda calculus—— 纯粹是为了没有接触过 lambda 算子理论的读者准备的,并不属于本文重点讨论的东西,然而要讨论 Y combinator 就必须先了解一下 lambda (当然,以编程语言来了解也行,但是你会看到,丘齐最初提出的 lambda 算子理论才是最最简洁和漂亮的,学起来也最省事。)所以我单独准备了一个小节来介绍它。如果你已经知道,可以跳过这一小节。不知道的读者也可以跳过这一小节去 wikipedia 上面看,这里的介绍使用了 wikipedia 上的方式 2.1. lambda calculus 先来看一下 lambda 表达式的基本语法 (BNF) : < expr > < expr >::= lambda < expr >::= (< expr >< expr >) 前两条语法用于生成 lambda 表达式( lambda 函数),如: lambda x y. x + y haskell 里面为了简洁起见用 “/” 来代替希腊字母 lambda ,它们形状比较相似。故而上面的定义也可以写成: / x y. x + y 这是一个匿名的加法函数,它接受两个参数,返回两值相加的结果。当然,这里我们为了方便起见赋予了 lambda 函数直观的计算意义,而实际上 lambda calculus 里面一切都只不过是文本替换,有点像 C 语言的宏。并且这里的 “+” 我们假设已经是一个具有原子语义的运算符 [6] ,此外,为了方便我们使用了中缀表达(按照 lambda calculus 系统的语法实际上应该写成 “(+ x y)” 才对 —— 参考第三条语法)。 那么,函数定义出来了,怎么使用呢?最后一条规则就是用来调用一个 lambda 函数的: ((lambda x y. x + y) 2 3) 以上这一行就是把刚才定义的加法函数运用到 2 和 3 上(这个调用语法形式跟 命令式语言(imperative language) 惯用的调用形式有点区别,后者是 “f(x, y)” ,而这里是 “(f x y)” ,不过好在顺序没变 :) )。为了表达简洁一点,我们可以给 (lambda x y. x + y) 起一个名字,像这样: let Add = (lambda x y. x + y) 这样我们便可以使用 Add 来表示该 lambda 函数了: (Add 2 3) 不过还是为了方便起见,后面调用的时候一般用 “Add(2, 3)” ,即我们熟悉 的形式。 有了语法规则之后,我们便可以看一看这个语言系统的两条简单至极的公理了: Alpha 转换公理 :例如, “lambda x y. x + y” 转换为 “lambda a b. a + b” 。换句话说,函数的参数起什么名字没有关系,可以随意替换,只要函数体里面对参数的使用的地方也同时注意相应替换掉就是了。 Beta 转换公理 :例如 , “(lambda x y. x + y) 2 3” 转换为 “2 + 3” 。这个就更简单了,也就是说,当把一个 lambda 函数用到参数身上时,只需用实际的参数来替换掉其函数体中的相应变量即可。 就这些。是不是感觉有点太简单了?但事实就是如此, lambda 算子系统从根本上其实就这些东西,然而你却能够从这几个简单的规则中推演出神奇无比的 Y combinator 来。我们这就开始! 2.2. 表示递归 2.2.1. 困难:Lambda没有名字 敏锐的你可能会发现,就以上这两条公理,我们的 lambda 语言中无法表示递归函数,为什么呢?假设我们要计算经典的阶乘,递归描述肯定像这样: f(n): if n == 0 return 1 return n*f(n-1) 当然,上面这个程序是假定 n 为正整数。这个程序显示了一个特点, f 在定义的过程中用到了它自身。那么如何在 lambda 算子系统中表达这一函数呢?理所当然的想法如下: lambda n. If_Else n==0 1 n*< self >(n-1) 当然,上面的程序假定了 If_Else 是一个已经定义好的三元操作符(你可以想象 C 的 “?:” 操作符,后面跟的三个参数分别是判断条件、成功后求值的表达式、失败后求值的表达式。那么很显然,这个定义里面有一个地方没法解决,那就是 < self > 那个地方我们应该填入什么呢?很显然,熟悉 C 这类命令式语言的人都知道应该填入这个函数本身的名字,然而 lambda 算子系统里面的 lambda 表达式(或称函数)是没有名字的。 2.2.2. 期望的形式:F 怎么办?难道就没有办法实现递归了?或者说,丘齐做出的这个 lambda 算子系统里面根本没法实现递归从而在计算能力上面有重大的缺陷?显然不是。马上你就会看到 Y combinator 是如何把一个看上去非递归的 lambda 表达式像变魔术那样变成一个递归版本的。在成功之前我们再失败一次,注意下面的尝试: let F = lambda n. IF_Else n==0 1 n*F(n-1) // (1)简洁的形式 看上去不错,是吗?可惜还是不行。因为 let F 只是起到一个 语法糖 的作用,在它所代表的 lambda 表达式还没有完全定义出来之前你是不可以使用 F 这个名字的。更何况实际上丘齐当初的 lambda 算子系统里面也并没有这个语法元素,这只是刚才为了简化代码而引入的语法糖。当然,了解这个 let 语句还是有意义的,后面还会用到。 2.2.3. 可行的形式:P:self作为参数 在上面几次失败的尝试之后,我们是不是就一筹莫展了呢?别忘了软件工程里面的一条黄金定律: “ 任何问题都可以通过增加一个间接层来解决 ” 。不妨把它沿用到我们面临的递归问题上:没错,我们的确没办法在一个 lambda 函数的定义里面直接(按名字)来调用其自身。但是,可不可以间接调用呢? 我们回顾一下刚才不成功的定义: lambda n. If_Else n==0 1 n*< self >(n-1) 现在< self > 处不是缺少 “ 这个函数自身 ” 嘛,既然不能直接填入 “ 这个函数自身 ” ,我们可以增加一个参数,也就是说,把 lambda self n. If_Else n==0 1 n*self(n-1) 上面这个 lambda 算子总是合法定义了吧。现在,我们调用这个函数的时候,只要加传一个参数 self ,这个参数不是别人,正是这个函数自身。还是为了简单起见,我们用 let 语句来给上面这个函数起个别名: let P = lambda self n. If_Else n==0 1 n*self(n-1) 我们这样调用,比如说我们要计算 3 的阶乘: P (P, 3) 也就是说,把 P 自己 作为 P 的第一个参数(注意,调用的时候 P 已经定义完毕了,所以我们当然可以使用它的名字了)。这样一来, P 里面的 self 处不就等于是 P 本身了吗?自身调用自身,递归! 可惜这只是个美好的设想,还差一点点。我们分析一下 P(P, 3) 这个调用。利用前面讲的 Beta 转换规则,这个函数调用展开其实就是(你可以完全把 P 当成一个宏来进行展开!): IF_Else n==0 1 n*P(n-1) 看出问题了吗?这里的 P (n-1) 虽然调用到了 P ,然而只给出了一个参数;而从 P 的定义来看,它是需要两个参数的(分别为 self 和 n )!也就是说,为了让 P (n-1) 变成良好的调用,我们得加一个参数才行,所以我们得稍微修改一下 P 的定义: let P = lambda self n. If_Else n==0 1 n*self(self, n-1) // (2)成功表达递归 请注意,我们在 P 的函数体内调用 self 的时候增加了一个参数。现在当我们调用 P(P, 3) 的时候,展开就变成了: IF_Else 3==0 1 3*P(P, 3-1) 而 P (P, 3-1) 是对 P 合法的递归调用。这次我们真的成功了! 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) 完美的阶乘函数! 下接《哥德尔不完备定理》 Reference [1] 《数学——确定性的丧失》 [2] 也有观点认为函数式编程语言之所以没有广泛流行起来是因为一些实际的商业因素。 [3] Douglas R.Hofstadter的著作《Godel, Escher, Bach: An Eternal Golden Braid》(《哥德尔、艾舍尔、巴赫——集异璧之大成》)就是围绕这一思想写出的一本奇书。非常建议一读。 [4] 《数学——确定性的丧失》 [5] 虽然我觉得那个系徽做得太复杂,要表达这一简洁优美的思想其实还能有更好的方式。 [6] 关于如何在lambda calculus系统里实现“+”操作符以及自然数等等,可参见 这里, 这里,和 这里。 [7] g9的blog(负暄琐话) http://blog.csdn.net/g9yuayon/ 上有一系列介绍lambda calculus的文章(当然,还有其它好文章:)),非常不错,强烈推荐。最近的两篇就是介绍Y combinator的。其中有一篇以javaScript语言描述了迭代式逐步抽象出Y Combinator的过程。 [8] 实际上这只是第一不完备性定理,它还有一个推论,被称为第二不完备性定理,说的是任一个系统T内无法证明这个系统本身的一致性。这个定理的证明核心思想如下:我们前面证明第一不完备性定理的时候用的推断其实就表明 Con/T -> G(g) (自然语言描述就是,由系统T的无矛盾,可以推出G(g)成立),而这个“Con/T -> G(g)”本身又是可以在T内表达且证明出来的(具体怎么表达就不再多说了)——只需要用排中律即可。于是我们立即得到,T里面无法推出Con/T,因为一旦推出Con/T就立即推出G(g)从而推出UnPr(G(g)),这就矛盾了。所以,Con/T无法在T内推出(证明)。 |