Snowdream

http://chn.blogbeta.com/232.html

原文鏈接：Functional Programming For The Rest of Us
原文作者：Vyacheslav Akhmechet
翻譯：lihaitao (電郵: lihaitao在gmail.com)
校對(duì)：劉凱清

程序員拖沓成性，每天到了辦公室后，泡咖啡，檢查郵箱，閱讀 RSS feed，到技術(shù)站點(diǎn)查閱最新的文章，在編程論壇的相關(guān)版面瀏覽公共討論，并一次次地刷新以免漏掉一條信息。然后是午飯，回來(lái)后盯了IDE沒(méi)幾分鐘，就再次檢查郵箱，倒咖啡。最后在不知不覺(jué)中，結(jié)束了一天。

不平凡的事是每隔一段時(shí)間會(huì)跳出一些很有挑戰(zhàn)性的文章。如果沒(méi)錯(cuò)，這些天你至少發(fā)現(xiàn)了一篇這類(lèi)文章——很難快速通讀它們，于是就將之束之高閣，直到突然你發(fā)現(xiàn)自己已經(jīng)有了一個(gè)長(zhǎng)長(zhǎng)的鏈接列表和一個(gè)裝滿(mǎn)了PDF文件的目錄，然后你夢(mèng)想著到一個(gè)人跡罕至的森林里的小木屋苦讀一年以期趕上，要是每天清晨你沿著那里的林中小溪散步時(shí)會(huì)有人帶來(lái)食物和帶走垃圾就更好了。

雖然我對(duì)你的列表一無(wú)所知，但我的列表卻是一大堆關(guān)于函數(shù)式編程的文章。而這些基本上是最難閱讀的了。它們用枯燥的學(xué)院派語(yǔ)言寫(xiě)成，即使“在華爾街行業(yè)浸淫十年的專(zhuān)家（veterans）”也不能理解函數(shù)式編程（也寫(xiě)作FP）都在探討些什么。如果你去問(wèn)花旗集團(tuán)（Citi Group）或德意志銀行（Deutsche Bank）的項(xiàng)目經(jīng)理[1]，為什么選擇了 JMS 而不 Erlang，他們可能回答不能在產(chǎn)業(yè)級(jí)的應(yīng)用中使用學(xué)院派語(yǔ)言。問(wèn)題是，一些最為復(fù)雜的，有著最嚴(yán)格需求的系統(tǒng)卻是用函數(shù)式編程元素寫(xiě)成。有些說(shuō)法不能讓人信服。

的確，關(guān)于函數(shù)式編程的文章和論文難于理解，但他們本來(lái)不必這么晦澀。這一知識(shí)隔閡的形成完全是歷史原因。函數(shù)式編程的概念本身并不困難。這篇文章可以作為“簡(jiǎn)易的函數(shù)式編程導(dǎo)引”。是一座從我們命令式（imperative）的思維模式到函數(shù)式編程的橋梁。去取杯咖啡回來(lái)繼續(xù)讀下去吧。可能你的同事很快就會(huì)開(kāi)始取笑你對(duì)函數(shù)式編程發(fā)表的觀(guān)點(diǎn)了。

那么什么是函數(shù)式編程呢？它怎么產(chǎn)生？它可以被掌握嗎（Is it edible)？如果它真如其倡導(dǎo)者所言，為什么沒(méi)有在行業(yè)中得到更廣泛的使用？為什么好像只有那些拿著博士學(xué)位的人才使用它？最要緊的是，為什么它就 TMD 這么難學(xué)？這些 closure, continuation, currying，惰性求值和無(wú)副作用等等究竟是些什么東西？沒(méi)有大學(xué)參與的項(xiàng)目怎么使用它？為什么它看上去這么詭異于和我們命令式思想友好，圣潔和親近的一切的一切？我們將于不久掃清這些疑問(wèn)。首先讓我來(lái)解釋形成實(shí)際生活和學(xué)界文章之間巨大隔閡的緣起，簡(jiǎn)單得像一次公園的散步。

信步游園

啟動(dòng)時(shí)間機(jī)器，我們散步在兩千多年以前的一個(gè)被遺忘了太久的春季明媚的日子，那是公元前380年。雅典城墻外的橄欖樹(shù)樹(shù)蔭里，柏拉圖和一個(gè)英俊的奴隸小男孩朝著學(xué)院走去。“天氣真好”，“飲食不錯(cuò)”，然后話(huà)題開(kāi)始轉(zhuǎn)向哲思。

“瞧那兩個(gè)學(xué)生，”為了使問(wèn)題更容易理解，柏拉圖仔細(xì)地挑選著用詞，“你認(rèn)為誰(shuí)更高呢？”
小男孩看著那兩個(gè)人站著的水漕說(shuō)，“他們差不多一樣高”。
柏拉圖說(shuō)：“你的差不多一樣是什么意思？”。“我在這里看他們是一樣高的，不過(guò)我肯定如果走近些就會(huì)看出他們高度的差別。”
柏拉圖笑了，他正把這個(gè)孩子帶到正確的方向。“那么你是說(shuō)，我們這個(gè)世界沒(méi)有完全的等同了？”
小男孩想了一會(huì)兒回答，“對(duì)，我不這樣認(rèn)為，任何事物總有一些區(qū)別，即使我們看不到它。”
這句話(huà)非常到位！“那么如果這世上沒(méi)有完全的相等，你又是如何理解‘完全’相等這個(gè)概念的呢？”
小男孩迷惑得說(shuō)：“我不知道。”最初嘗試著理解數(shù)學(xué)的本源（nature）時(shí)也會(huì)產(chǎn)生這種疑惑。

柏拉圖暗示這個(gè)世上的萬(wàn)物都只是一個(gè)對(duì)完美的近似。他還認(rèn)識(shí)到我們即使沒(méi)有接觸到完美但依然可以理解這一概念。所以他得出結(jié)論，完美的數(shù)學(xué)形式只能存在于另一個(gè)世界，我們通過(guò)和那個(gè)世界的某種聯(lián)系在一定程度上知曉他們。很明顯我們不能看到完美的圓，但我們可以理解什么是完美的圓并用數(shù)學(xué)公式將它表達(dá)出來(lái)。那么，什么是數(shù)學(xué)？為什么宇宙可以用數(shù)學(xué)定理描述？數(shù)學(xué)可以描述宇宙中的所有現(xiàn)象嗎？[2]

數(shù)學(xué)哲學(xué)是一個(gè)很復(fù)雜的課題。像大多數(shù)哲學(xué)學(xué)科一樣它更傾向于提出問(wèn)題而不是給出解答。這些意見(jiàn)中很多都循回繞轉(zhuǎn)于一個(gè)事實(shí)，即數(shù)學(xué)實(shí)際上是一個(gè)謎語(yǔ)：我們?cè)O(shè)置了一系列基本的不沖突的原理和一些可以施加于這些原理的操作規(guī)則，然后我們就能堆砌這些規(guī)則以形成更復(fù)雜的規(guī)則。數(shù)學(xué)家把這種方法叫做“形式系統(tǒng)”或“演算”。如果愿意，我們可以很快寫(xiě)出一個(gè)關(guān)于 Tetris（譯者注：一種通常被稱(chēng)為俄羅斯方塊的游戲）的形式系統(tǒng)。實(shí)際上，工作中的 Tetris 實(shí)現(xiàn)就是一個(gè)形式系統(tǒng)，只是被指定使用了個(gè)不常見(jiàn)的表現(xiàn)形式。

人馬座的那個(gè)生物文明也許不能理解我們的 Tetris 和圓的范式，因?yàn)榭赡芩麄兾ㄒ坏母兄斎胧菤馕断愠鹊拈僮印Ｋ麄円苍S永遠(yuǎn)不會(huì)發(fā)現(xiàn) Tetris 范式，但很可能會(huì)有一個(gè)圓的范式。我們也可能將無(wú)法閱讀它，因?yàn)槲覀兊男嵊X(jué)沒(méi)有那么復(fù)雜，可是一旦我們理解(pass)了那一范式的表示形式（通過(guò)這種傳感器和標(biāo)準(zhǔn)解碼技術(shù)來(lái)理解這種語(yǔ)言），其底層的概念就可被任何智能文明所理解。

有趣的是如果從來(lái)沒(méi)有智能文明存在，Tetris 和圓的范式仍然嚴(yán)密合理，只是沒(méi)有人注定將會(huì)發(fā)現(xiàn)他們。如果產(chǎn)生了一種智能文明，他就會(huì)發(fā)現(xiàn)一些形式系統(tǒng)來(lái)幫助描述宇宙的規(guī)律。但他還是不大可能發(fā)現(xiàn) Tetris 因?yàn)橛钪嬷性贈(zèng)]有和它相似的事物。在現(xiàn)實(shí)世界中這類(lèi)無(wú)用的形式系統(tǒng)或迷題的例子數(shù)不勝數(shù)，Tetris 只是其中的一個(gè)典型。我們甚至不能確定自然數(shù)是否是對(duì)客觀(guān)世界的完整近似，至少我們可以簡(jiǎn)單的想像一個(gè)很大的數(shù)它不能用宇宙中任何東西描述，因?yàn)樗越鯚o(wú)窮。

歷史一瞥[3]

再次啟動(dòng)時(shí)間機(jī)器，這一次的旅行近了很多，我們回到 1930 年代。大蕭條正在蹂躪著那個(gè)或新或就的時(shí)代。空前的經(jīng)濟(jì)下挫影響著幾乎所有階層的家庭生活，只有少數(shù)人還能夠保持著饑謹(jǐn)危機(jī)前的安逸。一些人就如此幸運(yùn)地位列其中，我們關(guān)心的是普林斯頓大學(xué)的數(shù)學(xué)家們。

采用了歌特式風(fēng)格設(shè)計(jì)建造的新辦公室給普林斯頓罩上天堂般的幸福光環(huán)，來(lái)自世界各地的邏輯學(xué)家被邀請(qǐng)到普林斯頓建設(shè)一個(gè)新的學(xué)部。雖然彼時(shí)的美國(guó)民眾已難能弄到一餐的面包，普林斯頓的條件則是可以在高高的穹頂下，精致雕鑿的木質(zhì)墻飾邊上整日的品茶討論或款款慢步于樓外的林蔭之中。

阿隆左·丘奇就是一個(gè)在這種近于奢侈的環(huán)境中生活著的數(shù)學(xué)家。他在普林斯頓獲得本科學(xué)位后被邀留在研究生院繼續(xù)攻讀。阿隆左認(rèn)為那里的建筑實(shí)屬浮華，所以他很少一邊喝茶一邊與人討論數(shù)學(xué)，他也不喜歡到林中散步。阿隆左是一個(gè)孤獨(dú)者：因?yàn)橹挥幸粋€(gè)人時(shí)他才能以最高的效率工作。雖然如此，他仍與一些普林斯頓人保持的定期的聯(lián)系，其中包括阿蘭·圖靈，約翰·馮·諾依曼，和 kurt Grodel。

這四個(gè)人都對(duì)形式系統(tǒng)很感興趣，而不太留意現(xiàn)實(shí)世界，以便致力于解決抽象的數(shù)學(xué)難題。他們的難題有些共同之處：都是探索關(guān)于計(jì)算的問(wèn)題。如果我們有了無(wú)限計(jì)算能力的機(jī)器，哪些問(wèn)題可以被解決？我們可以使他們自動(dòng)地得以解決嗎？是否還是有些問(wèn)題無(wú)法解決，為什么？不同設(shè)計(jì)的各種機(jī)器是否具有相同的計(jì)算能力？

通過(guò)和其它人的合作，阿隆左·丘奇提出了一個(gè)被稱(chēng)為 lambda 演算的形式系統(tǒng)。這個(gè)系統(tǒng)本質(zhì)上是一種虛擬的機(jī)器的編程語(yǔ)言，他的基礎(chǔ)是一些以函數(shù)為參數(shù)和返回值的函數(shù)。函數(shù)用希臘字母 lambda 標(biāo)識(shí)，這個(gè)形式系統(tǒng)因此得名[4]。利用這一形式系統(tǒng)，阿隆左就可以對(duì)上述諸多問(wèn)題推理并給出結(jié)論性的答案。

獨(dú)立于阿隆左，阿蘭·圖靈也在進(jìn)行著相似的工作，他提出了一個(gè)不同的形式系統(tǒng)（現(xiàn)在被稱(chēng)為圖靈機(jī)），并使用這一系統(tǒng)獨(dú)立得給出了和阿隆左相似的結(jié)論。后來(lái)被證明圖靈機(jī)和 lambda 演算能力等同。

我們的故事本可以到此結(jié)束，我會(huì)就此歇筆，而你也將瀏覽到下一個(gè)頁(yè)面，如果第二次世界大戰(zhàn)沒(méi)有在那時(shí)打響。整個(gè)世界籠罩在戰(zhàn)爭(zhēng)的火光和硝煙之中，美國(guó)陸軍和海軍前所未有的大量使用炮彈，為了改進(jìn)炮彈的精確度，部隊(duì)組織了大批的科學(xué)家持續(xù)地計(jì)算微分方程以解出彈道發(fā)射軌跡。漸漸意識(shí)到這個(gè)任務(wù)用人力手工完成太耗精力后，人們開(kāi)始著手開(kāi)發(fā)各種設(shè)備來(lái)攻克這個(gè)難關(guān)。第一個(gè)解出了彈道軌跡的機(jī)器是 IBM 制造的 Mark I —— 它重達(dá)5噸，有75萬(wàn)個(gè)組件，每秒可以完成三次操作。

競(jìng)爭(zhēng)當(dāng)然沒(méi)有就此結(jié)束，1949年，EDVAC（Electronic Discrete Variable Automatic Computer，愛(ài)達(dá)瓦克）被推出并獲得了極大的成功。這是對(duì)馮·諾依曼架構(gòu)的第一個(gè)實(shí)踐實(shí)例，實(shí)際上也是圖靈機(jī)的第一個(gè)現(xiàn)實(shí)實(shí)現(xiàn)。那一年好運(yùn)與阿隆左 ·丘奇無(wú)緣。

直到1950年代將盡，一位 MIT 的教授John McCarthy（也是普林斯頓畢業(yè)生）對(duì)阿隆左·丘奇的工作產(chǎn)生了興趣。1958年，他公開(kāi)了表處理語(yǔ)言 Lisp。Lisp 是對(duì)阿隆左·丘奇的 lambda 演算的實(shí)現(xiàn)但同時(shí)它工作在馮·諾依曼計(jì)算機(jī)上！很多計(jì)算機(jī)科學(xué)家認(rèn)識(shí)到了 Lisp 的表達(dá)能力。1973年，MIT人工智能實(shí)驗(yàn)室的一組程序員開(kāi)發(fā)了被稱(chēng)為L(zhǎng)isp機(jī)器的硬件－阿隆左 lambda 演算的硬件實(shí)現(xiàn)！

函數(shù)式編程

函數(shù)式編程是對(duì)阿隆左·丘奇理論的實(shí)踐應(yīng)用。但也并非全部 lambda 演算都被應(yīng)用到了實(shí)踐中，因?yàn)?lambda 演算不是被設(shè)計(jì)為在物理局限下工作的。因此，象面向?qū)ο蟮木幊桃粯樱瘮?shù)式編程是一系列理念，而不是嚴(yán)格的教條。現(xiàn)在有很多種函數(shù)式編程語(yǔ)言，他們中的大多數(shù)以不同方式完成不同任務(wù)。在本文中我將就最廣泛使用的源自函數(shù)式編程的思想作一解釋?zhuān)⒂肑ava語(yǔ)言舉例。(的確，你可以用Java寫(xiě)出函數(shù)式的程序如果你有顯著的受虐傾向）。在下面的小節(jié)中，我將會(huì)把Java作為一種函數(shù)式語(yǔ)言，并對(duì)其稍加修改使它成為一種可用的函數(shù)式語(yǔ)言。現(xiàn)在開(kāi)始吧。

lambda 演算被設(shè)計(jì)用來(lái)探詢(xún)關(guān)于計(jì)算的問(wèn)題，所以函數(shù)式編程主要處理計(jì)算，并驚人地用函數(shù)來(lái)完成這一過(guò)程。函數(shù)是函數(shù)式編程的基本單位，函數(shù)幾乎被用于一切，包括最簡(jiǎn)單的計(jì)算，甚至變量都由計(jì)算取代。在函數(shù)式編程中，變量只是表達(dá)式的別名（這樣我們就不必把所有東西打在一行里）。變量是不能更改的，所有變量只能被賦值一次。用 Java 的術(shù)語(yǔ)來(lái)說(shuō)，這意味著所有單一變量都被聲明為 final（或 C++ 的 const）。在函數(shù)式編程中沒(méi)有非 final 的變量。

final int i = 5;
final int j = i + 3;

因?yàn)楹瘮?shù)式編程中所有變量都是 final 的，所以可以提出這樣兩個(gè)有趣的表述：沒(méi)有必要總是寫(xiě)出關(guān)鍵字 final，沒(méi)有必要把變量再稱(chēng)為變量。那么現(xiàn)在我們對(duì)Java作出兩個(gè)修改：在我們的函數(shù)式 Java 中所有變量默認(rèn)都是 final的，我們將變量（variable）稱(chēng)為符號(hào)（symbol）。

就此你也許會(huì)質(zhì)疑，用我們新創(chuàng)造的語(yǔ)言還能寫(xiě)出有些復(fù)雜度的程序嗎？如果每個(gè)符號(hào)都是不可變更(non-mutalbe)的，那么就無(wú)法改變?nèi)魏螤顟B(tài)！其實(shí)事實(shí)并非完全如此。在阿隆左研究其 lambda 演算時(shí)，他并不想將某個(gè)狀態(tài)維護(hù)一段時(shí)間以期未來(lái)對(duì)其進(jìn)行修改。他關(guān)注的是對(duì)數(shù)據(jù)的操作（也通常被稱(chēng)為”演算體 caculating stuff”）。既然已被證明lambda演算與圖靈機(jī)等價(jià)，它可以完成所有命令式編程語(yǔ)言能夠完成的任務(wù)。那么，我們?cè)趺床拍茏龅侥兀?/p>

答案是函數(shù)式程序能保存狀態(tài)，只是它并非通過(guò)變量而是使用函數(shù)來(lái)保存狀態(tài)。狀態(tài)保存在函數(shù)的參數(shù)中，保存在堆棧上。如果你要保存某個(gè)狀態(tài)一段時(shí)間并時(shí)不時(shí)地對(duì)其進(jìn)行一些修改，可以寫(xiě)個(gè)遞歸函數(shù)。舉個(gè)例子，我們寫(xiě)個(gè)函數(shù)來(lái)翻轉(zhuǎn) Java 的字符串。記住，我們聲明的每個(gè)變量默認(rèn)都是 final 的。[5]

String reverse(String arg) {
if(arg.length == 0) {
return arg;
}
else {
return reverse(arg.substring(1, arg.length)) + arg.substring(0,1);
}}

這個(gè)函數(shù)很慢因?yàn)樗粩嗟卣{(diào)用自己[6]，它還也是個(gè)嗜內(nèi)存魔因?yàn)橐掷m(xù)分配對(duì)象。不過(guò)它的確是在用函數(shù)式風(fēng)格。你可能會(huì)問(wèn)，怎么有人會(huì)這樣寫(xiě)程序？好的，我這就慢慢講來(lái)：

函數(shù)式編程的優(yōu)點(diǎn)

你可能會(huì)認(rèn)為我根本無(wú)法對(duì)上面那個(gè)畸形的函數(shù)給出個(gè)合理的解釋。我開(kāi)始學(xué)習(xí)函數(shù)式編程時(shí)就是這么認(rèn)為的。不過(guò)我是錯(cuò)了。有很好的理由使用這種風(fēng)格，當(dāng)然其中一些屬主觀(guān)因素。例如，函數(shù)式程序被認(rèn)為更容易閱讀。因?yàn)槊總€(gè)街區(qū)的孩子都知道，是否容易理解在旁觀(guān)者的眼中，所以我將略去這些主觀(guān)方面的理由。幸運(yùn)的是，還有很多的客觀(guān)理由。

單元測(cè)試

因?yàn)楹瘮?shù)式編程的每一個(gè)符號(hào)都是 final 的，沒(méi)有函數(shù)產(chǎn)生過(guò)副作用。因?yàn)閺奈丛谀硞€(gè)地方修改過(guò)值，也沒(méi)有函數(shù)修改過(guò)在其作用域之外的量并被其他函數(shù)使用（如類(lèi)成員或全局變量）。這意味著函數(shù)求值的結(jié)果只是其返回值，而惟一影響其返回值的就是函數(shù)的參數(shù)。

這是單元測(cè)試者的夢(mèng)中仙境(wet dream)。對(duì)被測(cè)試程序中的每個(gè)函數(shù)，你只需在意其參數(shù)，而不必考慮函數(shù)調(diào)用順序，不用謹(jǐn)慎地設(shè)置外部狀態(tài)。所有要做的就是傳遞代表了邊際情況的參數(shù)。如果程序中的每個(gè)函數(shù)都通過(guò)了單元測(cè)試，你就對(duì)這個(gè)軟件的質(zhì)量有了相當(dāng)?shù)淖孕拧６钍骄幊叹筒荒苓@樣樂(lè)觀(guān)了，在 Java 或 C++ 中只檢查函數(shù)的返回值還不夠——我們還必須驗(yàn)證這個(gè)函數(shù)可能修改了的外部狀態(tài)。

調(diào)試

如果一個(gè)函數(shù)式程序不如你期望地運(yùn)行，調(diào)試也是輕而易舉。因?yàn)楹瘮?shù)式程序的 bug 不依賴(lài)于執(zhí)行前與其無(wú)關(guān)的代碼路徑，你遇到的問(wèn)題就總是可以再現(xiàn)。在命令式程序中，bug 時(shí)隱時(shí)現(xiàn)，因?yàn)樵谀抢锖瘮?shù)的功能依賴(lài)與其他函數(shù)的副作用，你可能會(huì)在和 bug 的產(chǎn)生無(wú)關(guān)的方向探尋很久，毫無(wú)收獲。函數(shù)式程序就不是這樣——如果一個(gè)函數(shù)的結(jié)果是錯(cuò)誤的，那么無(wú)論之前你還執(zhí)行過(guò)什么，這個(gè)函數(shù)總是返回相同的錯(cuò)誤結(jié)果。

一旦你將那個(gè)問(wèn)題再現(xiàn)出來(lái)，尋其根源將毫不費(fèi)力，甚至?xí)屇汩_(kāi)心。中斷那個(gè)程序的執(zhí)行然后檢查堆棧，和命令式編程一樣，棧里每一次函數(shù)調(diào)用的參數(shù)都呈現(xiàn)在你眼前。但是在命令式程序中只有這些參數(shù)還不夠，函數(shù)還依賴(lài)于成員變量，全局變量和類(lèi)的狀態(tài)（這反過(guò)來(lái)也依賴(lài)著這許多情況）。函數(shù)式程序里函數(shù)只依賴(lài)于它的參數(shù)，而那些信息就在你注視的目光下！還有，在命令式程序里，只檢查一個(gè)函數(shù)的返回值不能夠讓你確信這個(gè)函數(shù)已經(jīng)正常工作了，你還要去查看那個(gè)函數(shù)作用域外數(shù)十個(gè)對(duì)象的狀態(tài)來(lái)確認(rèn)。對(duì)函數(shù)式程序，你要做的所有事就是查看其返回值！

沿著堆棧檢查函數(shù)的參數(shù)和返回值，只要發(fā)現(xiàn)一個(gè)不盡合理的結(jié)果就進(jìn)入那個(gè)函數(shù)然后一步步跟蹤下去，重復(fù)這一個(gè)過(guò)程，直到它讓你發(fā)現(xiàn)了 bug 的生成點(diǎn)。

并行

函數(shù)式程序無(wú)需任何修改即可并行執(zhí)行。不用擔(dān)心死鎖和臨界區(qū)，因?yàn)槟銖奈从面i！函數(shù)式程序里沒(méi)有任何數(shù)據(jù)被同一線(xiàn)程修改兩次，更不用說(shuō)兩個(gè)不同的線(xiàn)程了。這意味著可以不假思索地簡(jiǎn)單增加線(xiàn)程而不會(huì)引發(fā)折磨著并行應(yīng)用程序的傳統(tǒng)問(wèn)題。

事實(shí)既然如此，為什么并不是所有人都在需要高度并行作業(yè)的應(yīng)用中采用函數(shù)式程序？嗯，他們正在這樣做。愛(ài)立信公司設(shè)計(jì)了一種叫作 Erlang 的函數(shù)式語(yǔ)言并將它使用在需要極高抗錯(cuò)性和可擴(kuò)展性的電信交換機(jī)上。還有很多人也發(fā)現(xiàn)了 Erlang 的優(yōu)勢(shì)并開(kāi)始使用它。我們談?wù)摰氖请娦磐ㄐ趴刂葡到y(tǒng)，這與設(shè)計(jì)華爾街的典型系統(tǒng)相比對(duì)可靠性和可升級(jí)性要求高了得多。實(shí)際上，Erlang 系統(tǒng)并不可靠和易擴(kuò)展，Java 才是。Erlang 系統(tǒng)只是堅(jiān)如磐石。

關(guān)于并行的故事還沒(méi)有就此停止，即使你的程序本身就是單線(xiàn)程的，那么函數(shù)式程序的編譯器仍然可以?xún)?yōu)化它使其運(yùn)行于多個(gè)CPU上。請(qǐng)看下面這段代碼：

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

在函數(shù)編程語(yǔ)言中，編譯器會(huì)分析代碼，辨認(rèn)出潛在耗時(shí)的創(chuàng)建字符串s1和s2的函數(shù)，然后并行地運(yùn)行它們。這在命令式語(yǔ)言中是不可能的，因?yàn)樵谀抢铮總€(gè)函數(shù)都有可能修改了函數(shù)作用域以外的狀態(tài)并且其后續(xù)的函數(shù)又會(huì)依賴(lài)這些修改。在函數(shù)式語(yǔ)言里，自動(dòng)分析函數(shù)并找出適合并行執(zhí)行的候選函數(shù)簡(jiǎn)單的像自動(dòng)進(jìn)行的函數(shù)內(nèi)聯(lián)化！在這個(gè)意義上，函數(shù)式風(fēng)格的程序是“不會(huì)過(guò)時(shí)的技術(shù)(future proof)”(即使不喜歡用行業(yè)術(shù)語(yǔ)，但這回要破例一次)。硬件廠(chǎng)商已經(jīng)無(wú)法讓CPU運(yùn)行得更快了，于是他們?cè)黾恿颂幚砥骱诵牡乃俣炔⒁虿⑿卸@得了四倍的速度提升。當(dāng)然他們也順便忘記提及我們的多花的錢(qián)只是用在了解決平行問(wèn)題的軟件上了。一小部分的命令式軟件和 100% 的函數(shù)式軟件都可以直接并行運(yùn)行于這些機(jī)器上。

代碼熱部署

過(guò)去要在 Windows上安裝更新，重啟計(jì)算機(jī)是難免的，而且還不只一次，即使是安裝了一個(gè)新版的媒體播放器。Windows XP 大大改進(jìn)了這一狀態(tài)，但仍不理想（我今天工作時(shí)運(yùn)行了Windows Update，現(xiàn)在一個(gè)煩人的圖標(biāo)總是顯示在托盤(pán)里除非我重啟一次機(jī)器）。Unix系統(tǒng)一直以來(lái)以更好的模式運(yùn)行，安裝更新時(shí)只需停止系統(tǒng)相關(guān)的組件，而不是整個(gè)操作系統(tǒng)。即使如此，對(duì)一個(gè)大規(guī)模的服務(wù)器應(yīng)用這還是不能令人滿(mǎn)意的。電信系統(tǒng)必須100%的時(shí)間運(yùn)行，因?yàn)槿绻谙到y(tǒng)更新時(shí)緊急撥號(hào)失效，就可能造成生命的損失。華爾街的公司也沒(méi)有理由必須在周末停止服務(wù)以安裝更新。

理想的情況是完全不停止系統(tǒng)任何組件來(lái)更新相關(guān)的代碼。在命令式的世界里這是不可能的。考慮運(yùn)行時(shí)上載一個(gè)Java類(lèi)并重載一個(gè)新的定義，那么所有這個(gè)類(lèi)的實(shí)例都將不可用，因?yàn)樗鼈儽槐４娴臓顟B(tài)丟失了。我們可以著手寫(xiě)些繁瑣的版本控制代碼來(lái)解決這個(gè)問(wèn)題，然后將這個(gè)類(lèi)的所有實(shí)例序列化，再銷(xiāo)毀這些實(shí)例，繼而用這個(gè)類(lèi)新的定義來(lái)重新創(chuàng)建這些實(shí)例，然后載入先前被序列化的數(shù)據(jù)并希望載入代碼可以恰到地將這些數(shù)據(jù)移植到新的實(shí)例。在此之上，每次更新都要重新手動(dòng)編寫(xiě)這些用來(lái)移植的代碼，而且要相當(dāng)謹(jǐn)慎地防止破壞對(duì)象間的相互關(guān)系。理論簡(jiǎn)單，但實(shí)踐可不容易。

對(duì)函數(shù)式的程序，所有的狀態(tài)即傳遞給函數(shù)的參數(shù)都被保存在了堆棧上，這使的熱部署輕而易舉！實(shí)際上，所有我們需要做的就是對(duì)工作中的代碼和新版本的代碼做一個(gè)差異比較，然后部署新代碼。其他的工作將由一個(gè)語(yǔ)言工具自動(dòng)完成！如果你認(rèn)為這是個(gè)科幻故事，請(qǐng)?jiān)偎伎家幌隆６嗄陙?lái) Erlang工程師一直更新著他們的運(yùn)轉(zhuǎn)著的系統(tǒng)，而無(wú)需中斷它。

機(jī)器輔助的推理和優(yōu)化

函數(shù)式語(yǔ)言的一個(gè)有趣的屬性就是他們可以用數(shù)學(xué)方式推理。因?yàn)橐环N函數(shù)式語(yǔ)言只是一個(gè)形式系統(tǒng)的實(shí)現(xiàn)，所有在紙上完成的運(yùn)算都可以應(yīng)用于用這種語(yǔ)言書(shū)寫(xiě)的程序。編譯器可以用數(shù)學(xué)理論將轉(zhuǎn)換一段代碼轉(zhuǎn)換為等價(jià)的但卻更高效的代碼[7]。多年來(lái)關(guān)系數(shù)據(jù)庫(kù)一直在進(jìn)行著這類(lèi)優(yōu)化。沒(méi)有理由不能把這一技術(shù)應(yīng)用到常規(guī)軟件上。

另外，還能使用這些技術(shù)來(lái)證明部分程序的正確，甚至可能創(chuàng)建工具來(lái)分析代碼并為單元測(cè)試自動(dòng)生成邊界用例！對(duì)穩(wěn)固的系統(tǒng)這種功能沒(méi)有價(jià)值，但如果你要設(shè)計(jì)心房脈沖產(chǎn)生器 (pace maker)或空中交通控制系統(tǒng)，這種工具就不可或缺。如果你編寫(xiě)的應(yīng)用程序不是產(chǎn)業(yè)的核心任務(wù)，這類(lèi)工具也是你強(qiáng)于競(jìng)爭(zhēng)對(duì)手的殺手锏。

高階函數(shù)

我記得自己在了解了上面列出的種種優(yōu)點(diǎn)后曾想：“那都是非常好的特性，可是如果我不得不用天生就不健全的語(yǔ)言編程，把一切變量聲明為
final 產(chǎn)生的代碼將是垃圾一堆。” 這其實(shí)是誤解。在如Java 這般的命令式語(yǔ)言環(huán)境里，將所有變量聲明為 final 沒(méi)有用，但是在函數(shù)式語(yǔ)言里不是這樣。函數(shù)式語(yǔ)言提供了不同的抽象工具它會(huì)使你忘記你曾經(jīng)習(xí)慣于修改變量。高階函數(shù)就是這樣一種工具。

函數(shù)式語(yǔ)言中的函數(shù)不同于 Java 或 C 中的函數(shù)，而是一個(gè)超集——它有著 Java 函數(shù)擁有的所有功能，但還有更多。創(chuàng)建函數(shù)的方式和 C 中相似:

int add(int i, int j) {
return i + j;
}

這意味著有些東西和同樣的 C 代碼有區(qū)別。現(xiàn)在擴(kuò)展我們的 Java 編譯器使其支持這種記法。當(dāng)我們輸入上述代碼后編譯器會(huì)把它轉(zhuǎn)換成下面的Java代碼（別忘了，所有東西都是 final 的）：

class add_function_t {
int add(int i, int j) {
return i + j;
}
}

add_function_t add = new add_function_t();

這里的符號(hào) add 并不是一個(gè)函數(shù)。這是一個(gè)有一個(gè)成員函數(shù)的很小的類(lèi)。我們現(xiàn)在可以把 add 作為函數(shù)參數(shù)放入我們的代碼中。還可以把它賦給另一個(gè)符號(hào)。我們?cè)谶\(yùn)行時(shí)創(chuàng)建的 add_function_t 的實(shí)例如果不再被使用就將會(huì)被垃圾回收掉。這些使得函數(shù)成為第一級(jí)的對(duì)象無(wú)異于整數(shù)或字符串。（作為參數(shù)）操作函數(shù)的函數(shù)被稱(chēng)為高階函數(shù)。別讓這個(gè)術(shù)語(yǔ)嚇著你，這和 Java 的 class 操作其它 class（把它們作為參數(shù)）沒(méi)有什么區(qū)別。我們本可以把它們稱(chēng)為“高階類(lèi)”但沒(méi)有人注意到這個(gè)，因?yàn)?Java 背后沒(méi)有一個(gè)強(qiáng)大的學(xué)術(shù)社區(qū)。

那么怎樣，何時(shí)應(yīng)該使用高階函數(shù)呢？我很高興你這樣問(wèn)。如果你不曾考慮類(lèi)的層次，就可能寫(xiě)出了一整團(tuán)堆砌的代碼塊。當(dāng)你發(fā)現(xiàn)其中一些行的代碼重復(fù)出現(xiàn)，就把他們提取成函數(shù)（幸運(yùn)的是這些依然可以在學(xué)校里學(xué)到）。如果你發(fā)現(xiàn)在那個(gè)函數(shù)里一些邏輯動(dòng)作根據(jù)情況有變，就把他提取成高階函數(shù)。糊涂了？下面是一個(gè)來(lái)自我工作的實(shí)例：假如我的一些 Java 代碼接受一條信息，用多種方式處理它然后轉(zhuǎn)發(fā)到其他服務(wù)器。

class MessageHandler {
void handleMessage(Message msg) {
// …
msg.setClientCode(”ABCD_123″);
// …

sendMessage(msg);
}

// …

}

現(xiàn)在假設(shè)要更改這個(gè)系統(tǒng)，現(xiàn)在我們要把信息轉(zhuǎn)發(fā)到兩個(gè)服務(wù)器而不是一個(gè)。除了客戶(hù)端的代碼一切都像剛才一樣——第二個(gè)服務(wù)器希望這是另一種格式。怎么處理這種情況？我們可以檢查信息的目的地并相應(yīng)修改客戶(hù)端代碼的格式，如下：

class MessageHandler {
void handleMessage(Message msg) {
// …
if(msg.getDestination().equals(”server1″) {
msg.setClientCode(”ABCD_123″);
} else {
msg.setClientCode(”123_ABC”);
}
// …

sendMessage(msg);
}

// …

}

然而這不是可擴(kuò)展的方法，如果加入了更多的服務(wù)器，這個(gè)函數(shù)將線(xiàn)性增長(zhǎng)，更新它會(huì)成為我的夢(mèng)魘。面向?qū)ο蟮姆椒ㄊ前袽essageHandler作為基類(lèi)，在導(dǎo)出類(lèi)中專(zhuān)業(yè)化客戶(hù)代碼操作：

abstract class MessageHandler {
void handleMessage(Message msg) {
// …
msg.setClientCode(getClientCode());
// …

sendMessage(msg);
}

abstract String getClientCode();

// …

}

class MessageHandlerOne extends MessageHandler {
String getClientCode() {
return “ABCD_123″;
}

}

class MessageHandlerTwo extends MessageHandler {
String getClientCode() {
return “123_ABCD”;
}

}

現(xiàn)在就可以對(duì)每一個(gè)服務(wù)器實(shí)例化一個(gè)適合的類(lèi)。添加服務(wù)器的操作變得容易維護(hù)了。但對(duì)于這么一個(gè)簡(jiǎn)單的修改仍然要添加大量的代碼。為了支持不同的客戶(hù)代碼我們創(chuàng)建了兩個(gè)新的類(lèi)型！現(xiàn)在我們用高階函數(shù)完成同樣的功能：

class MessageHandler {
void handleMessage(Message msg, Function getClientCode) {
// …
Message msg1 = msg.setClientCode(getClientCode());
// …

sendMessage(msg1);
}

// …

}

String getClientCodeOne() {
return “ABCD_123″;

}

String getClientCodeTwo() {
return “123_ABCD”;

}

MessageHandler handler = new MessageHandler();
handler.handleMessage(someMsg, getClientCodeOne);

沒(méi)有創(chuàng)建新的類(lèi)型和新的class層次，只是傳入合適的函數(shù)作為參數(shù)，完成了面向?qū)ο蠓绞酵瑯拥墓δ埽瑫r(shí)還有一些額外的優(yōu)點(diǎn)。沒(méi)有使自己囿于類(lèi)的層次之中：可以在運(yùn)行時(shí)傳入函數(shù)并在任何時(shí)候以更高的粒度更少的代碼修改他們。編譯器高效地為我們生成了面向?qū)ο蟮摹罢澈稀贝a！除此之外，我們還獲得了所有函數(shù)式編程的其他好處。當(dāng)然函數(shù)式語(yǔ)言提供的抽象不只這些，高階函數(shù)只是一個(gè)開(kāi)始：

currying

我認(rèn)識(shí)的大多數(shù)人都讀過(guò)“四人幫”的那本設(shè)計(jì)模式，任何自重的程序員都會(huì)告訴你那本書(shū)是語(yǔ)言中立的(agnostic)，模式在軟件工程中是通用的，和使用的語(yǔ)言無(wú)關(guān)。這個(gè)說(shuō)法頗為高貴，故而不幸的是，有違現(xiàn)實(shí)。

函數(shù)式編程極具表達(dá)能力。在函數(shù)式語(yǔ)言中，語(yǔ)言既已達(dá)此高度，設(shè)計(jì)模式就不再是必需，最終你將設(shè)計(jì)模式徹底消除而以概念編程。適配器 (Adapter)模式就是這樣的一個(gè)例子。(究竟適配器和 Facade 模式區(qū)別在哪里？可能有些人需要在這里再多費(fèi)些篇章)。一旦語(yǔ)言有了叫作 currying 的技術(shù)，這一模式就可以被消除。

currying.

適配器模式最有名的是被應(yīng)用在 Java 的“默認(rèn)”抽象單元——class 上。在函數(shù)式編程里，模式被應(yīng)用到函數(shù)。模式帶有一個(gè)接口并將它轉(zhuǎn)換成另一個(gè)對(duì)他人有用的接口。這有一個(gè)適配器模式的例子：

int pow(int i, int j);
int square(int i)
{
return pow(i, 2);
}

上面的代碼把一個(gè)整數(shù)冪運(yùn)算接口轉(zhuǎn)換成為了一個(gè)平方接口。在學(xué)術(shù)文章里，這個(gè)雕蟲(chóng)小技被叫作currying(得名于邏輯學(xué)家Haskell
Curry，他曾將相關(guān)的數(shù)學(xué)理論形式化 )。因?yàn)樵诤瘮?shù)式編程中函數(shù)（反之如class)被作為參數(shù)來(lái)回傳遞，currying 很頻繁地被用來(lái)把函數(shù)調(diào)整為更適宜的接口。因?yàn)楹瘮?shù)的接口是他的參數(shù)，使用 currying 可以減少參數(shù)的數(shù)目(如上例所示)。

函數(shù)式語(yǔ)言?xún)?nèi)建了這一技術(shù)。不用手動(dòng)地創(chuàng)建一個(gè)包裝了原函數(shù)的函數(shù)，函數(shù)式語(yǔ)言可以為你代勞。同樣地，擴(kuò)展我們的語(yǔ)言，讓他支持這個(gè)技術(shù)：

square = int pow(int i, 2);

這將為我們自動(dòng)創(chuàng)建出一個(gè)有一個(gè)參數(shù)的函數(shù) square。他把第二個(gè)參數(shù)設(shè)置為 2 再調(diào)用函數(shù) pow。這行代碼會(huì)被編譯為如下的 Java 代碼：

class square_function_t {
int square(int i) {
return pow(i, 2);
}
}

square_function_t square = new square_function_t();

正如你所見(jiàn)，通過(guò)簡(jiǎn)單地創(chuàng)建一個(gè)對(duì)原函數(shù)的包裝，在函數(shù)式編程中，這就是 currying —— 快速簡(jiǎn)易創(chuàng)建包裝的捷徑。把精力集中在你的業(yè)務(wù)上，讓編譯器為你寫(xiě)出必要的代碼！什么時(shí)候使用 currying？這很簡(jiǎn)單，任何時(shí)候你想要使用適配器模式（包裝）時(shí)。

惰性求值

惰性（或延遲）求值這一技術(shù)可能會(huì)變得非常有趣一旦我們采納了函數(shù)式哲學(xué)。在討論并行時(shí)已經(jīng)見(jiàn)過(guò)下面的代碼片斷：

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

在一個(gè)命令式語(yǔ)言中求值順序是確定的，因?yàn)槊總€(gè)函數(shù)都有可能會(huì)變更或依賴(lài)于外部狀態(tài)，所以就必須有序的執(zhí)行這些函數(shù)：首先是
somewhatLongOperation1，然后 somewhatLongOperation2，最后 concatenate，在函數(shù)式語(yǔ)言里就不盡然了。

前面提到只要確保沒(méi)有函數(shù)修改或依賴(lài)于全局變量，somewhatLongOperation1 和 somewhatLongOperation2 可以被并行執(zhí)行。但是如果我們不想同時(shí)運(yùn)行這兩個(gè)函數(shù)，還有必要保證有序的執(zhí)行他們呢？答案是不。我們只在其他函數(shù)依賴(lài)于s1和s2時(shí)才需要執(zhí)行這兩個(gè)函數(shù)。我們甚至在concatenate調(diào)用之前都不必執(zhí)行他們——可以把他們的求值延遲到concatenate函數(shù)內(nèi)實(shí)際用到他們的位置。如果用一個(gè)帶有條件分支的函數(shù)替換concatenate并且只用了兩個(gè)參數(shù)中的一個(gè)，另一個(gè)參數(shù)就永遠(yuǎn)沒(méi)有必要被求值。在 Haskell 語(yǔ)言中，不確保一切都（完全）按順序執(zhí)行，因?yàn)?Haskell 只在必要時(shí)才會(huì)對(duì)其求值。

惰性求值優(yōu)點(diǎn)眾多，但缺點(diǎn)也不少。我們會(huì)在這里討論它的優(yōu)點(diǎn)而在下一節(jié)中解釋其缺點(diǎn)。

優(yōu)化

惰性求值有客觀(guān)的優(yōu)化潛力。惰性編譯器看函數(shù)式代碼就像數(shù)學(xué)家面對(duì)的代數(shù)表達(dá)式————可以注銷(xiāo)一部分而完全不去運(yùn)行它，重新調(diào)整代碼段以求更高的效率，甚至重整代碼以降低出錯(cuò)，所有確定性?xún)?yōu)化(guaranteeing optimizations)不會(huì)破壞代碼。這是嚴(yán)格用形式原語(yǔ)描述程序的巨大優(yōu)勢(shì)————代碼固守著數(shù)學(xué)定律并可以數(shù)學(xué)的方式進(jìn)行推理。

抽象控制結(jié)構(gòu)

惰性求值提供了更高一級(jí)的抽象，它使得不可能的事情得以實(shí)現(xiàn)。例如，考慮實(shí)現(xiàn)如下的控制結(jié)構(gòu)：

unless(stock.isEuropean()) {
sendToSEC(stock);
}

我們希望只在祖先不是歐洲人時(shí)才執(zhí)行sendToSEC。如何實(shí)現(xiàn) unless？如果沒(méi)有惰性求值，我們需要某種形式的宏（macro）系統(tǒng)，但
Haskell 這樣的語(yǔ)言不需要它。把他實(shí)現(xiàn)為一個(gè)函數(shù)即可：

void unless(boolean condition, List code) {
if(!condition)
code;
}

注意如果條件為真代碼將不被執(zhí)行。我們不能在一個(gè)嚴(yán)格（strict）的語(yǔ)言中再現(xiàn)這種求值，因?yàn)?unless 調(diào)用之前會(huì)先對(duì)參數(shù)進(jìn)行求值。

無(wú)窮(infinite)數(shù)據(jù)結(jié)構(gòu)

惰性求值允許定義無(wú)窮數(shù)據(jù)結(jié)構(gòu)，對(duì)嚴(yán)格語(yǔ)言來(lái)說(shuō)實(shí)現(xiàn)這個(gè)要復(fù)雜的多。考慮一個(gè) Fibonacci 數(shù)列，顯然我們無(wú)法在有限的時(shí)間內(nèi)計(jì)算出或在有限的內(nèi)存里保存一個(gè)無(wú)窮列表。在嚴(yán)格語(yǔ)言如 Java 中，只能定義一個(gè)能返回 Fibonacci 數(shù)列中特定成員的 Fibonacci 函數(shù)，在 Haskell
中，我們對(duì)其進(jìn)一步抽象并定義一個(gè)關(guān)于 Fibonacci 數(shù)的無(wú)窮列表，因?yàn)樽鳛橐粋€(gè)惰性的語(yǔ)言，只有列表中實(shí)際被用到的部分才會(huì)被求值。這使得可以抽象出很多問(wèn)題并從一個(gè)更高的層次重新審視他們。（例如，我們可以在一個(gè)無(wú)窮列表上使用表處理函數(shù)）。

缺點(diǎn)

當(dāng)然從來(lái)不存在免費(fèi)的午餐。惰性求值有很多的缺點(diǎn)，主要就在于，懶。有很多現(xiàn)實(shí)世界的問(wèn)題需要嚴(yán)格求值。例如考慮下例：

System.out.println(”P(pán)lease enter your name: “);
System.in.readLine();

在惰性求值的語(yǔ)言里，不能保證第一行會(huì)在第二行之前執(zhí)行！那么我們就不能進(jìn)行輸入輸出操作，不能有意義地使用本地（native）接口（因?yàn)樗麄兿嗷ヒ蕾?lài)其副作用必須被有序的調(diào)用），從而與整個(gè)世界隔離。如果引入允許特定執(zhí)行順序的原語(yǔ)又將失去數(shù)學(xué)地推理代碼的諸多好處（為此將葬送函數(shù)式編程與其相關(guān)的所有優(yōu)點(diǎn)）。幸運(yùn)的是，并非喪失了一切，數(shù)學(xué)家為此探索并開(kāi)發(fā)出了許多技巧來(lái)保證在一定函數(shù)設(shè)置下(function setting)代碼以一特定的順序執(zhí)行。這樣我們就贏得了兩個(gè)世界。這些技術(shù)包括 continuation， monad 和 uniqueness typing
（一致型別）。我只會(huì)在本文中解釋continuation，把 monad 和 uniqueness typing 留到將來(lái)的文章中。有趣的是，除了確保函數(shù)求值順序， continuation 在很多別的情況下也很有用。這點(diǎn)等一會(huì)兒就會(huì)提到。

Continuations

Continuations 對(duì)于程序設(shè)計(jì)的意義，就像《達(dá)芬奇密碼》對(duì)人類(lèi)歷史的意義：即對(duì)人類(lèi)最大秘密的驚人揭示。也許不是，但他在概念上的突破性至少和揭示了負(fù)數(shù)的平方根意義等同。

我們?cè)趯W(xué)習(xí)函數(shù)時(shí)，只是學(xué)到了一半的事實(shí)，因?yàn)槲覀兓谝粋€(gè)錯(cuò)誤的假定:函數(shù)只能將結(jié)果返回到它的調(diào)用函數(shù)。在這個(gè)意思上continuation 是廣義的函數(shù)。函數(shù)不必要返回到其調(diào)用函數(shù)而可以返回到程序的任何地方。我們把”continuation” 作為參數(shù)傳給一個(gè)函數(shù)，它指定了這個(gè)函數(shù)返回的位置。這個(gè)描述可能聽(tīng)起來(lái)更加復(fù)雜。看一下下面的代碼：

int i = add(5, 10);
int j = square(i);

函數(shù) add 在其被調(diào)用的位置將結(jié)果 15 賦給了 i，接下來(lái) i 的值被用來(lái)調(diào)用 square。注意所有的惰性求值編譯器都不能調(diào)整這幾行代碼因?yàn)榈诙幸蕾?lài)著第一行的成功求值。下面用 continuation 風(fēng)格又稱(chēng) CPS (Continuation Programming Style) 來(lái)重寫(xiě)這段代碼，這里函數(shù) add 會(huì)將結(jié)果返回到 square 而不是原來(lái)的調(diào)用函數(shù)。

int j = add(5, 10, square);

這個(gè)例子中 add 有了另一個(gè)參數(shù) —— 一個(gè) add 必須在它求值結(jié)束時(shí)用其返回值調(diào)用的函數(shù)。這里 square 是 add 的一個(gè) continuation。這兩種情況下，j 都將等于 255。

這就是強(qiáng)制使惰性語(yǔ)言有序地求值兩個(gè)表達(dá)式的第一個(gè)技巧。考慮下面這個(gè)（熟悉的）IO代碼：

System.out.println(”P(pán)lease enter your name: “);
System.in.readLine();

這兩行不相依賴(lài)所以編譯器會(huì)自由的重新調(diào)整他們的執(zhí)行順序。然而，如果我們用 CPS 來(lái)重寫(xiě)這段代碼，就會(huì)有一個(gè)依賴(lài)，編譯器會(huì)因此而強(qiáng)制對(duì)這兩行代碼有序執(zhí)行！

System.out.println(”P(pán)lease enter your name: “, System.in.readLine);

這里 println 需要用自己的返回結(jié)果作為參數(shù)去調(diào)用 readLine 并將 readLine 返回值作為自己的返回值。這樣就能確保這兩行被有序執(zhí)行而且 readLine 一定被執(zhí)行（因?yàn)檎麄€(gè)計(jì)算期望最后的結(jié)果為結(jié)果）。Java 的 println 返回 void 但如果它返回的是一個(gè)抽象值（readLine所期待的），我們就解決了這個(gè)問(wèn)題！當(dāng)然這樣的鏈接函數(shù)調(diào)用很快就會(huì)使代碼難以讀懂，不過(guò)這個(gè)可以避免。比如我們可以給語(yǔ)言添加些語(yǔ)法甜點(diǎn)(syntactic sugar)就可以簡(jiǎn)單的按順序輸入表達(dá)式，然后由編譯器自動(dòng)為我們鏈接這些函數(shù)調(diào)用。這樣就可以如愿地使用期望的求值順序并保留一切函數(shù)式編程的好處（包括數(shù)學(xué)地對(duì)我們程序進(jìn)行推理的能力）！如果還是有迷惑，記住函數(shù)是只有一個(gè)成員的類(lèi)的實(shí)例。重寫(xiě)上述代碼使得 println 和 readLine 成為類(lèi)的實(shí)例，這樣就對(duì)一切都清楚了。

如果我在此結(jié)束本節(jié)，那將僅僅涉及到 continuation 最淺顯的應(yīng)用。用 CPS 重寫(xiě)整個(gè)程序，那里所有的函數(shù)都增加一個(gè)額外的 continuation 參數(shù)并把函數(shù)結(jié)果傳給它。也可以通過(guò)簡(jiǎn)單地把函數(shù)當(dāng)作 continuation 函數(shù)（總是返回到調(diào)用者的函數(shù)）的特殊實(shí)例來(lái)將程序轉(zhuǎn)為 CPS 風(fēng)格。這種轉(zhuǎn)換很容易被自動(dòng)化（事實(shí)上，許多編譯器就是這么做的）。

一旦我們將一個(gè)程序轉(zhuǎn)為了CPS，那么很明顯每個(gè)指令都將有些 continuation, 這是一個(gè)該指令在執(zhí)行結(jié)束時(shí)會(huì)用其執(zhí)行結(jié)果調(diào)用的函數(shù)，通常的程序中，這是一個(gè)它要返回的地址。從上面的例子中隨便舉個(gè)例子，比如 add(5, 10)。在用CPS風(fēng)格寫(xiě)的程序里，add 的continuation很明顯——這是一個(gè) add 在其執(zhí)行結(jié)束時(shí)會(huì)調(diào)用的函數(shù)。那么如果在非CPS的程序里，它是什么呢？當(dāng)然我們可以把程序轉(zhuǎn)為 CPS ，但有這個(gè)必要嗎？

其實(shí)沒(méi)有必要。仔細(xì)看一下我們的 CPS 轉(zhuǎn)換過(guò)程。如果嘗試為它寫(xiě)一個(gè)編譯器，然后經(jīng)過(guò)長(zhǎng)期的思考后，你意識(shí)到這個(gè) CPS 的版本根本不需要棧！沒(méi)有函數(shù)會(huì)以傳統(tǒng)的意義“返回”，它只是用結(jié)果調(diào)用了另一個(gè)函數(shù)。我們無(wú)需在調(diào)用時(shí)將函數(shù)參數(shù)壓棧再于調(diào)用結(jié)束時(shí)彈出棧，而只是簡(jiǎn)單的把他們保存在一大塊內(nèi)存中，然后使用跳轉(zhuǎn)指令。不再需要原來(lái)的參數(shù)——他們不會(huì)再次被用到，因?yàn)闆](méi)有函數(shù)會(huì)返回！

所以，用 CPS 風(fēng)格寫(xiě)成的程序沒(méi)有堆棧，但每個(gè)函數(shù)卻有一個(gè)額外的參數(shù)可被調(diào)用。不是 CPS 風(fēng)格的程序沒(méi)有可以被調(diào)用的這個(gè)參數(shù)，但卻有棧。棧中存放著什么？只是參數(shù)和一個(gè)指向函數(shù)返回地址的指針。你看到光了嗎？棧中只是放著 continuation 的信息！ 棧中指向返回指令的指針本質(zhì)上和 CPS 程序里將被調(diào)用的函數(shù)是等價(jià)的。如果你想探究 add(5,10) 的 continuation，只要簡(jiǎn)單地檢查它在堆棧的執(zhí)行點(diǎn)！

這的確很簡(jiǎn)單。continuation 和棧上指向返回地址的指針是等價(jià)的，只是 continuation 是被顯式傳遞，所以不必和函數(shù)被調(diào)用點(diǎn)是同一位置。如果還記得 continuation 就是一個(gè)函數(shù)，并且在我們的語(yǔ)言里，函數(shù)被編譯為一個(gè)類(lèi)的實(shí)例，你就會(huì)理解指向棧中返回指令的指針實(shí)際就是傳遞給 continuation 的參數(shù)，因?yàn)槲覀兊暮瘮?shù)（就像一個(gè)類(lèi)的實(shí)例）只是一個(gè)指針。這意味著給定程序中任意時(shí)間和任意位置，你都可以去請(qǐng)求一個(gè)當(dāng)前的 continuation (current continuation)（它就是當(dāng)前的棧的信息）。

好的，這樣我們就知道了什么是 current continuation。他有什么意義？一旦我們得到了當(dāng)前的 continuation 并將它保存在某處，我們就最終將程序當(dāng)前的狀態(tài)保存了下來(lái)——及時(shí)地冷凍下來(lái)。這就像操作系統(tǒng)將其置為休眠狀態(tài)。一個(gè) continuation 對(duì)象里保存了在我們獲得它的地方重新啟動(dòng)程序的必要信息。操作系統(tǒng)在每次發(fā)生線(xiàn)程間的上下文切換時(shí)也是如此。唯一的區(qū)別是它保留著全部控制。請(qǐng)求一個(gè) continuation 對(duì)象（在Scheme里，可以調(diào)用 call-with-current-continuation 函數(shù)）后，你就會(huì)獲得一個(gè)包括了當(dāng)前 continuation
的對(duì)象——堆棧（或者在CPS情況下則是下一個(gè)要調(diào)用的函數(shù)）。可以把這個(gè)對(duì)象保存在一個(gè)變量（或者是磁盤(pán)）里。當(dāng)你用這 continuation “重啟”程序時(shí)，就會(huì)轉(zhuǎn)回到處你取得這個(gè)對(duì)象的那個(gè)狀態(tài)。這就象切換回一個(gè)被掛起的線(xiàn)程或喚醒休眠著的操作系統(tǒng)，區(qū)別是用 continuation，你可以多次地重復(fù)這一過(guò)程。當(dāng)操作系統(tǒng)被喚醒時(shí)，休眠信息就被銷(xiāo)毀了。但如果那些信息沒(méi)有被銷(xiāo)毀，你也就可以一次次地將它喚醒到同一點(diǎn)，就象重返過(guò)去一樣。有了 continuation 你就有了這個(gè)控制力！

Continuation 應(yīng)該在什么情況下使用呢？通常在嘗試模擬一個(gè)本質(zhì)上是無(wú)狀態(tài)的應(yīng)用時(shí)可以簡(jiǎn)化你的任務(wù)。Continuation 很適合在Web應(yīng)用程序中使用。微軟公司的 ASP.NET 技術(shù)極盡苦心地模擬狀態(tài)以便你在開(kāi)發(fā) Web 應(yīng)用時(shí)少費(fèi)周折。可如果 C# 支持了continuation，ASP.NET 的復(fù)雜度就可以減半——你只需要保存一個(gè) continuation，當(dāng)用戶(hù)下次發(fā)出 web 請(qǐng)求時(shí)重啟它即可。對(duì)程序員來(lái)說(shuō)，web 應(yīng)用程序?qū)⒉辉儆兄袛唷绦蛑皇呛?jiǎn)單的從下一行重啟！利用 continuation 這一抽象解決問(wèn)題真是令人難以置信的便利。考慮到越來(lái)越多的胖客戶(hù)端應(yīng)用程序正在向服務(wù)器端轉(zhuǎn)移，將來(lái) continuation 也會(huì)變得越來(lái)越重要。

模式匹配

模式匹配不是什么新的創(chuàng)新的特性。事實(shí)上，它和函數(shù)式編程的關(guān)系不大。把產(chǎn)生模式匹配歸因于函數(shù)式編程的唯一的原因是函數(shù)式語(yǔ)言一度提供了模式匹配，然而現(xiàn)在的命令式語(yǔ)言還做不到。

讓我們用一個(gè)例子深入了解一下模式匹配。這是一個(gè)Java的Fibonacci函數(shù)：

int fib(int n) {
if(n == 0) return 1;
if(n == 1) return 1;

return fib(n - 2) + fib(n - 1);
}

讓我們從Java衍生出的語(yǔ)言來(lái)支持模式匹配：

int fib(0) {
return 1;
}

int fib(1) {
return 1;
}

int fib(int n) {
return fib(n - 2) + fib(n - 1);

}

兩者有什么區(qū)別？編譯器為我們實(shí)現(xiàn)了分支。這有什么大不了？的確沒(méi)什么。有人注意到很多函數(shù)包括了復(fù)雜的 swith 語(yǔ)句（尤其是在函數(shù)式程序中）所以認(rèn)為這種抽象形式很好。我們把一個(gè)函數(shù)定義分離成多個(gè)，然后把模式置于參數(shù)中（有點(diǎn)象重載）。當(dāng)這個(gè)函數(shù)被調(diào)用時(shí)，編譯器使其比較參數(shù)和其運(yùn)行時(shí)的定義然后選擇其中正確的一個(gè)。這一般是通過(guò)選擇可選的最特定的定義來(lái)完成。例如，int fib(int n) 可以以 n 等于 1 被調(diào)用，但是實(shí)際上 fib(n) 沒(méi)有被調(diào)用，因?yàn)?fib(1) 更加特定。

模式匹配通常要比我這個(gè)例子復(fù)雜，比如，高級(jí)模式匹配系統(tǒng)可以讓我們這樣做：

int f(int n < 10) { ... }
int f(int n) { ... }

模式匹配什么時(shí)候適用？情況太多了！每當(dāng)你有一個(gè)嵌套著 if 的復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，這時(shí)就可以用模式匹配以更少的代碼完成得更好。一個(gè)很好的例子閃現(xiàn)在我腦海，這就是所有 Win32 平臺(tái)都提供了的標(biāo)準(zhǔn)的 WinProc 函數(shù)（即使它通常被抽象了）。通常模式匹配系統(tǒng)能檢測(cè)集合也可以應(yīng)付簡(jiǎn)單的值。例如，當(dāng)傳給函數(shù)一個(gè)數(shù)組后，就可以找出所有首元素為 1 第三個(gè)元素大于 3 的所有數(shù)組。

模式匹配還有一個(gè)好處即如果需要增加或修改條件，那么不必對(duì)付一個(gè)巨大的函數(shù)。只需增加或修改適合的定義即可。這消除了“四人幫”（GoF）書(shū)中的一大類(lèi)設(shè)計(jì)模式。條件越復(fù)雜，模式匹配就越有用。一旦習(xí)慣了它，你就會(huì)擔(dān)心沒(méi)有了模式匹配的日子如何打發(fā)。

Closures

到此我們已經(jīng)討論了純的函數(shù)式語(yǔ)言——實(shí)現(xiàn)了lambda演算又不包括與丘奇形式系統(tǒng)矛盾的語(yǔ)言——環(huán)境里的特性，可是還有很多在lambda演算框架之外的函數(shù)語(yǔ)言的有用特征。雖然一個(gè)公理系統(tǒng)的實(shí)現(xiàn)可以讓我們象數(shù)學(xué)表達(dá)式那樣思考程序但它未必是實(shí)際可行的。許多語(yǔ)言選擇去合并一些函數(shù)式的元素而沒(méi)有嚴(yán)格的堅(jiān)持函數(shù)式的教條。很多象這樣的語(yǔ)言（如Common Lisp）不要求變量是 final 的——可以即處對(duì)其修改。他們還不要求函數(shù)只依賴(lài)于其參數(shù)——允許函數(shù)訪(fǎng)問(wèn)外部狀態(tài)。但這些語(yǔ)言也的確包含著函數(shù)式的特征——如高階函數(shù)，在非純粹的函數(shù)式語(yǔ)言里傳遞函數(shù)作為參數(shù)和限制在 lambda 演算系統(tǒng)中的作法有些不同，它需要一種常被稱(chēng)為詞法（lexical）closure 的有趣特性。下面我給出幾個(gè)例子。記住，這里變量不再是final的，函數(shù)可以引用其作用域外的變量：

Function makePowerFn(int power) {
int powerFn(int base) {
return pow(base, power);
}
return powerFn;
}

Function square = makePowerFn(2);
square(3); // returns 9

函數(shù) make-power-fn 返回了一個(gè)函數(shù)，它有一個(gè)參數(shù)，并對(duì)這個(gè)參數(shù)進(jìn)行一定階的冪運(yùn)算。如果對(duì) square(3) 求值會(huì)有什么結(jié)果？變量 power 不在 powerFn 的作用域中，因?yàn)?makePowerFn 已經(jīng)返回它的棧楨而不復(fù)存在。那么square如何工作？一定是這個(gè)語(yǔ)言以某種方式將power的值保存了起來(lái)以便 square 使用。如果我們?cè)傩陆ㄒ粋€(gè)函數(shù)cube，用來(lái)計(jì)算參數(shù)的立方又會(huì)怎樣？運(yùn)行環(huán)境必須存儲(chǔ)兩個(gè)power的拷貝，每個(gè)我們用 make-power-fn 生成的函數(shù)都用一個(gè)拷貝。保存這些值的現(xiàn)象就被稱(chēng)為 closure。 closure 不只保存宿主函數(shù)的參數(shù)。例如，closure可能會(huì)是這樣：

Function makeIncrementer() {
int n = 0;

int increment() {
return ++n;
}
}

Function inc1 = makeIncrementer();
Function inc2 = makeIncrementer();

inc1(); // returns 1;
inc1(); // returns 2;
inc1(); // returns 3;
inc2(); // returns 1;
inc2(); // returns 2;
inc2(); // returns 3;

運(yùn)行時(shí)已保存了n，所以遞增器可以訪(fǎng)問(wèn)它，而且運(yùn)行時(shí)為每個(gè)遞增器都保存了一個(gè) n 的拷貝，即使這些拷貝本應(yīng)在 makeIncrementer
返回時(shí)消失。這些代碼被如何編譯？closure 在底層是如何工作的？很幸運(yùn)，我們可以去幕后看看。

一點(diǎn)常識(shí)會(huì)很有幫助，首先會(huì)注意到的是局部變量的生命期不再由簡(jiǎn)單的作用域限定而是不確定的。那么顯然可以由此得出結(jié)論它們不再被保存在棧上——反之必須被保存在堆上[8]。這樣一來(lái)，closure 的實(shí)現(xiàn)就象我們前面討論的函數(shù)一樣了，只是它還有一個(gè)指向周?chē)兞康囊谩?/p>

class some_function_t {
SymbolTable parentScope;

// …

}

當(dāng)一個(gè) closure 引用了一個(gè)不在其作用域的變量時(shí)，它會(huì)在其祖先作用域中查找這個(gè)引用。就是這樣！Closure 將函數(shù)式和面向?qū)ο蟮氖澜缇o密結(jié)合。當(dāng)你創(chuàng)建了一個(gè)包含了一些狀態(tài)的類(lèi)并把它傳到別處時(shí)，考慮一下 closure。Closure 就是這樣在取出作用域中的變量的同時(shí)創(chuàng)建“成員變量”，所以你不必親自去做這些！

下一步的計(jì)劃？

關(guān)于函數(shù)式編程，本文作了淺顯地討論。有時(shí)候一次粗淺的射獵可能會(huì)進(jìn)展為重大的收獲與我也受益匪淺。將來(lái)我還計(jì)劃寫(xiě)寫(xiě) category 理論，monad，函數(shù)式數(shù)據(jù)結(jié)構(gòu)，函數(shù)式語(yǔ)言中的類(lèi)型(type)體系，函數(shù)式并發(fā)，函數(shù)式數(shù)據(jù)庫(kù)等等還有很多。如果我得以（在學(xué)習(xí)的過(guò)程中）寫(xiě)出了上述諸多主題中的一半，我的生命就會(huì)完整了。還有，Google 是我們的朋友。

評(píng)論？

如果你有任何問(wèn)題，意見(jiàn)或建議，請(qǐng)發(fā)到郵箱 coffee…@gmail.com。很高興收到你的反饋

===========================

[1] 我在2005年找工作時(shí)常常提出這個(gè)問(wèn)題，當(dāng)時(shí)我得到的是數(shù)量可觀(guān)的一臉茫然。想像一下，這些人至少每人會(huì)得到30萬(wàn)美元，如果他們理解了他們可以得到的大部分工具。

[2] 這像是個(gè)悖論。物理學(xué)家和數(shù)學(xué)家被迫確認(rèn)他們還不完全清楚是否宇宙萬(wàn)物遵循著可以被數(shù)學(xué)描述的規(guī)則。

[3] 我一直厭惡提供了一堆枯燥的日期，人名和地點(diǎn)的紀(jì)年式歷史課。對(duì)我而言，歷史是改變了這個(gè)世界的人的生活，是他們行為之后的個(gè)人動(dòng)機(jī)，是他們得以影響億萬(wàn)生靈的體制。所以這個(gè)關(guān)于歷史的小節(jié)注定無(wú)法完整，只討論了于此關(guān)系及其密切的人物與事件。

[4] 我在學(xué)習(xí)函數(shù)式編程的時(shí)候，很不喜歡術(shù)語(yǔ) lambda，因?yàn)槲覜](méi)有真正理解它的意義。在這個(gè)環(huán)境里，lambda 是一個(gè)函數(shù)，那個(gè)希臘字母只是方便書(shū)寫(xiě)的數(shù)學(xué)記法。每當(dāng)你聽(tīng)到 lambda 時(shí)，只要在腦中把它翻譯成函數(shù)即可。

[5] 有趣的是 Java 的字符串是不可變更的，探討這一離經(jīng)叛道的設(shè)計(jì)的原因也非常有趣，不過(guò)在這里會(huì)分散我們對(duì)原目標(biāo)的注意力

[6] 大多數(shù)函數(shù)式編程語(yǔ)言的編譯器能通過(guò)將遞歸盡可能轉(zhuǎn)為迭代來(lái)進(jìn)行優(yōu)化，這被稱(chēng)為尾遞歸。

[7] 相反未必成立，雖然有時(shí)可以證明兩端代碼等價(jià)，但這不是所有情況下都成立。

[8] 這實(shí)際上不比存儲(chǔ)在棧上慢，因?yàn)橐坏┮肓死厥掌鳎瑑?nèi)存分配就成為了一個(gè)O(1)的操作。