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

一次成功的嘗試

在上面幾次失敗的嘗試之后，我們是不是就一籌莫展了呢？別忘了軟件工程里面的一條黃金定律：“任何問題都可以通過增加一個間接層來解決”。不妨把它沿用到我們面臨的遞歸問題上：沒錯，我們的確沒辦法在一個lambda函數的定義里面直接（按名字）來調用其自身。但是，可不可以間接調用呢？

我們回顧一下剛才不成功的定義：

lambda n. If_Else n==0 1 n*<self>(n-1)

現在<self>處不是缺少“這個函數自身”嘛，既然不能直接填入“這個函數自身”，我們可以增加一個參數，也就是說，把<self>參數化：

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

上面這個lambda算子總是合法定義了吧?，F在，我們調用這個函數的時候，只要加傳一個參數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當成一個宏來進行展開?。?/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)

請注意，我們在P的函數體內調用self的時候增加了一個參數?，F在當我們調用P(P, 3)的時候，展開就變成了：

IF_Else 3==0 1 3*P(P, 3-1)

而P(P, 3-1)是對P合法的遞歸調用。這次我們真的成功了！

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