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

Y Combinator

讓我們暫且擱下但記住繞人的圖靈停機問題，走進函數式編程語言的世界，走進由跟圖靈機理論等價的lambda算子發展出來的另一個平行的語言世界。讓我們來看一看被人們一代一代吟唱著的神奇的Y Combinator。

關于Y Combinator的文章可謂數不勝數，這個由師從希爾伯特的著名邏輯學家Haskell B.Curry（Haskell語言就是以他命名的，而函數式編程語言里面的Curry手法也是以他命名）“發明”出來的組合算子（Haskell是研究組合邏輯(combinatory logic)的）仿佛有種神奇的魔力，它能夠算出給定lambda表達式（函數）的不動點。從而使得遞歸成為可能。事實上，我們待會就會看到，Y Combinator在神奇的表面之下，其實隱藏著深刻的意義，其背后體現的意義，曾經開出過歷史上最燦爛的數學之花，所以MIT的計算機科學系將它做成系徽也就不足為奇了。

作者：劉未鵬 出版：電子工業出版社

當然，要了解這個神奇的算子，我們需要一點點lambda算子理論的基礎知識，不過別擔心，lambda算子理論是我目前見過的最簡潔的公理系統，這個系統僅僅由三條非常簡單的公理構成，而這三條公理里面我們又只需要關注前兩條。

以下小節——lambda calculus——純粹是為了沒有接觸過lambda算子理論的讀者準備的，并不屬于本文重點討論的東西，然而要討論Y combinator就必須先了解一下lambda（當然，以編程語言來了解也行，但是你會看到，丘齊最初提出的lambda算子理論才是最最簡潔和漂亮的，學起來也最省事。）所以我單獨準備了一個小節來介紹它。如果你已經知道，可以跳過這一小節。不知道的讀者也可以跳過這一小節去wikipedia上面看，這里的介紹使用了wikipedia上的方式。

lambda calculus

先來看一下lambda表達式的基本語法(BNF)：

<expr> ::= <identifier>

<expr> ::= lambda <identifier-list>. <expr>

<expr> ::= (<expr> <expr>)

前兩條語法用于生成lambda表達式（lambda函數），如：

lambda x y. x + y

haskell里面為了簡潔起見用“\”來代替希臘字母lambda，它們形狀比較相似。故而上面的定義也可以寫成：

\ x y. x + y

這是一個匿名的加法函數，它接受兩個參數，返回兩值相加的結果。當然，這里我們為了方便起見賦予了lambda函數直觀的計算意義，而實際上lambda calculus里面一切都只不過是文本替換，有點像C語言的宏。并且這里的“+”我們假設已經是一個具有原子語義的運算符^[1]，此外，為了方便我們使用了中綴表達（按照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來。我們這就開始！

【注釋】

[1]關于如何在lambdacalculus系統里實現“+”操作符及自然數等等，可參加擴展閱讀。

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