原文：http://www.defmacro.org/ramblings/fp.html
中文：http://hi.baidu.com/bigbigant/blog/item/8418ba12b29450c8c3fd7813.html

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

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

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

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

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

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

信步游園

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

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

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

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

人馬座的那個生物文明也許不能理解我們的 Tetris 和圓的范式，因為可能他們唯一的感知輸入是氣味香橙的橘子。他們也許永遠(yuǎn)不會發(fā)現(xiàn) Tetris 范式，但很可能會有一個圓的范式。我們也可能將無法閱讀它，因為我們的嗅覺沒有那么復(fù)雜，可是一旦我們理解(pass)了那一范式的表示形式（通過這種傳 感器和標(biāo)準(zhǔn)解碼技術(shù)來理解這種語言），其底層的概念就可被任何智能文明所理解。

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

歷史一瞥[3]

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

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

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

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

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

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

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

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

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

函數(shù)式編程

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

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

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

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

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

答案是函數(shù)式程序能保存狀態(tài)，只是它并非通過變量而是使用函數(shù)來保存狀態(tài)。狀態(tài)保存在函數(shù)的參數(shù)中，保存在堆棧上。如果你要保存某個狀態(tài)一段時間并 時不時地對其進(jìn)行一些修改，可以寫個遞歸函數(shù)。舉個例子，我們寫個函數(shù)來翻轉(zhuǎn) Java 的字符串。記住，我們聲明的每個變量默認(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);
}}

這個函數(shù)很慢因為它不斷地調(diào)用自己[6]，它還也是個嗜內(nèi)存魔因為要持續(xù)分配對象。不過它的確是在用函數(shù)式風(fēng)格。你可能會問，怎么有人會這樣寫程序？好的，我這就慢慢講來：

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

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

單元測試

因為函數(shù)式編程的每一個符號都是 final 的，沒有函數(shù)產(chǎn)生過副作用。因為從未在某個地方修改過值，也沒有函數(shù)修改過在其作用域之外的量并被其他函數(shù)使用（如類成員或全局變量）。這意味著函數(shù)求值的結(jié)果只是其返回值，而惟一影響其返回值的就是函數(shù)的參數(shù)。

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

調(diào)試

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

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

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

并行

函數(shù)式程序無需任何修改即可并行執(zhí)行。不用擔(dān)心死鎖和臨界區(qū)，因為你從未用鎖！函數(shù)式程序里沒有任何數(shù)據(jù)被同一線程修改兩次，更不用說兩個不同的線程了。這意味著可以不假思索地簡單增加線程而不會引發(fā)折磨著并行應(yīng)用程序的傳統(tǒng)問題。

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

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

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

在函數(shù)編程語言中，編譯器會分析代碼，辨認(rèn)出潛在耗時的創(chuàng)建字符串s1和s2的函數(shù)，然后并行地運行它們。這在命令式語言中是不可能的，因為在那 里，每個函數(shù)都有可能修改了函數(shù)作用域以外的狀態(tài)并且其后續(xù)的函數(shù)又會依賴這些修改。在函數(shù)式語言里，自動分析函數(shù)并找出適合并行執(zhí)行的候選函數(shù)簡單的像 自動進(jìn)行的函數(shù)內(nèi)聯(lián)化！在這個意義上，函數(shù)式風(fēng)格的程序是“不會過時的技術(shù)(future proof)”(即使不喜歡用行業(yè)術(shù)語，但這回要破例一次)。硬件廠商已經(jīng)無法讓CPU運行得更快了，于是他們增加了處理器核心的速度并因并行而獲得了四 倍的速度提升。當(dāng)然他們也順便忘記提及我們的多花的錢只是用在了解決平行問題的軟件上了。一小部分的命令式軟件和 100% 的函數(shù)式軟件都可以直接并行運行于這些機器上。

代碼熱部署

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

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

對函數(shù)式的程序，所有的狀態(tài)即傳遞給函數(shù)的參數(shù)都被保存在了堆棧上，這使的熱部署輕而易舉！實際上，所有我們需要做的就是對工作中的代碼和新版本的 代碼做一個差異比較，然后部署新代碼。其他的工作將由一個語言工具自動完成！如果你認(rèn)為這是個科幻故事，請再思考一下。多年來 Erlang工程師一直更新著他們的運轉(zhuǎn)著的系統(tǒng)，而無需中斷它。

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

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

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

高階函數(shù)

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

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

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

這意味著有些東西和同樣的 C 代碼有區(qū)別。現(xiàn)在擴展我們的 Java 編譯器使其支持這種記法。當(dāng)我們輸入上述代碼后編譯器會把它轉(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();

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

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

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

sendMessage(msg);
}

// …

}

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

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

sendMessage(msg);
}

// …

}

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

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)在就可以對每一個服務(wù)器實例化一個適合的類。添加服務(wù)器的操作變得容易維護了。但對于這么一個簡單的修改仍然要添加大量的代碼。為了支持不同的客戶代碼我們創(chuàng)建了兩個新的類型！現(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);

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

currying

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

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

currying.

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

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

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

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

square = int pow(int i, 2);

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

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

square_function_t square = new square_function_t();

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

惰性求值

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

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

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

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

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

優(yōu)化

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

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

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

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

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

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

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

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

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

缺點

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

System.out.println(”Please enter your name: “);
System.in.readLine();

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

Continuations

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

我們在學(xué)習(xí)函數(shù)時，只是學(xué)到了一半的事實，因為我們基于一個錯誤的假定:函數(shù)只能將結(jié)果返回到它的調(diào)用函數(shù)。在這個意思上continuation 是廣義的函數(shù)。函數(shù)不必要返回到其調(diào)用函數(shù)而可以返回到程序的任何地方。我們把”continuation” 作為參數(shù)傳給一個函數(shù)，它指定了這個函數(shù)返回的位置。這個描述可能聽起來更加復(fù)雜。看一下下面的代碼：

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

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

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

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

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

System.out.println(”Please enter your name: “);
System.in.readLine();

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

System.out.println(”Please enter your name: “, System.in.readLine);

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

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

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

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

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

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

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

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

模式匹配

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

讓我們用一個例子深入了解一下模式匹配。這是一個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衍生出的語言來支持模式匹配：

int fib(0) {
return 1;
}

int fib(1) {
return 1;
}

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

}

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

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

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

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

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

Closures

到此我們已經(jīng)討論了純的函數(shù)式語言——實現(xiàn)了lambda演算又不包括與丘奇形式系統(tǒng)矛盾的語言——環(huán)境里的特性，可是還有很多在lambda演算 框架之外的函數(shù)語言的有用特征。雖然一個公理系統(tǒng)的實現(xiàn)可以讓我們象數(shù)學(xué)表達(dá)式那樣思考程序但它未必是實際可行的。許多語言選擇去合并一些函數(shù)式的元素而 沒有嚴(yán)格的堅持函數(shù)式的教條。很多象這樣的語言（如Common Lisp）不要求變量是 final 的——可以即處對其修改。他們還不要求函數(shù)只依賴于其參數(shù)——允許函數(shù)訪問外部狀態(tài)。但這些語言也的確包含著函數(shù)式的特征——如高階函數(shù)，在非純粹的函數(shù) 式語言里傳遞函數(shù)作為參數(shù)和限制在 lambda 演算系統(tǒng)中的作法有些不同，它需要一種常被稱為詞法（lexical）closure 的有趣特性。下面我給出幾個例子。記住，這里變量不再是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 返回了一個函數(shù)，它有一個參數(shù)，并對這個參數(shù)進(jìn)行一定階的冪運算。如果對 square(3) 求值會有什么結(jié)果？變量 power 不在 powerFn 的作用域中，因為 makePowerFn 已經(jīng)返回它的棧楨而不復(fù)存在。那么square如何工作？一定是這個語言以某種方式將power的值保存了起來以便 square 使用。如果我們再新建一個函數(shù)cube，用來計算參數(shù)的立方又會怎樣？運行環(huán)境必須存儲兩個power的拷貝，每個我們用 make-power-fn 生成的函數(shù)都用一個拷貝。保存這些值的現(xiàn)象就被稱為 closure。 closure 不只保存宿主函數(shù)的參數(shù)。例如，closure可能會是這樣：

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;

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

一點常識會很有幫助，首先會注意到的是局部變量的生命期不再由簡單的作用域限定而是不確定的。那么顯然可以由此得出結(jié)論它們不再被保存在棧上——反之必須被保存在堆上[8]。這樣一來，closure 的實現(xiàn)就象我們前面討論的函數(shù)一樣了，只是它還有一個指向周圍變量的引用。

class some_function_t {
SymbolTable parentScope;

// …

}

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

下一步的計劃？

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

評論 ？

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

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

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

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

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

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

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

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

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

[8] 這實際上不比存儲在棧上慢，因為一旦引入了垃圾回收器，內(nèi)存分配就成為了一個O(1)的操作。