【專欄】康托爾、哥德爾、圖靈——永恒的金色對角線（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為參數”能夠實現真正的遞歸?，F在我們想考慮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月獲得南京大學計算機系碩士學位，現在微軟亞洲研究院創新工程中心從事軟件研發工程師工作。）