【專欄】康托爾、哥德爾、圖靈——永恒的金色對角線（7）

鑄造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)

完美的階乘函數！

（待續；此文的修訂版已收錄《暗時間》一書，由電子工業出版社2011年8月出版。作者于2009年7月獲得南京大學計算機系碩士學位，現在微軟亞洲研究院創新工程中心從事軟件研發工程師工作。）