Snowdream

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

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

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

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

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

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

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

信步游園

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

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

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

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

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

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

歷史一瞥[3]

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

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

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

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

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

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

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

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

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

函數式編程

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

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

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

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

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

答案是函數式程序能保存狀態，只是它并非通過變量而是使用函數來保存狀態。狀態保存在函數的參數中，保存在堆棧上。如果你要保存某個狀態一段時間并時不時地對其進行一些修改，可以寫個遞歸函數。舉個例子，我們寫個函數來翻轉 Java 的字符串。記住，我們聲明的每個變量默認都是 final 的。[5]

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

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

函數式編程的優點

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

單元測試

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

這是單元測試者的夢中仙境(wet dream)。對被測試程序中的每個函數，你只需在意其參數，而不必考慮函數調用順序，不用謹慎地設置外部狀態。所有要做的就是傳遞代表了邊際情況的參數。如果程序中的每個函數都通過了單元測試，你就對這個軟件的質量有了相當的自信。而命令式編程就不能這樣樂觀了，在 Java 或 C++ 中只檢查函數的返回值還不夠——我們還必須驗證這個函數可能修改了的外部狀態。

調試

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

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

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

并行

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

事實既然如此，為什么并不是所有人都在需要高度并行作業的應用中采用函數式程序？嗯，他們正在這樣做。愛立信公司設計了一種叫作 Erlang 的函數式語言并將它使用在需要極高抗錯性和可擴展性的電信交換機上。還有很多人也發現了 Erlang 的優勢并開始使用它。我們談論的是電信通信控制系統，這與設計華爾街的典型系統相比對可靠性和可升級性要求高了得多。實際上，Erlang 系統并不可靠和易擴展，Java 才是。Erlang 系統只是堅如磐石。

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

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

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

代碼熱部署

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

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

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

機器輔助的推理和優化

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

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

高階函數

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

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

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

這意味著有些東西和同樣的 C 代碼有區別。現在擴展我們的 Java 編譯器使其支持這種記法。當我們輸入上述代碼后編譯器會把它轉換成下面的Java代碼（別忘了，所有東西都是 final 的）：

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

add_function_t add = new add_function_t();

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

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

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

sendMessage(msg);
}

// …

}

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

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

sendMessage(msg);
}

// …

}

然而這不是可擴展的方法，如果加入了更多的服務器，這個函數將線性增長，更新它會成為我的夢魘。面向對象的方法是把MessageHandler作為基類，在導出類中專業化客戶代碼操作：

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”;
}

}

現在就可以對每一個服務器實例化一個適合的類。添加服務器的操作變得容易維護了。但對于這么一個簡單的修改仍然要添加大量的代碼。為了支持不同的客戶代碼我們創建了兩個新的類型！現在我們用高階函數完成同樣的功能：

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);

沒有創建新的類型和新的class層次，只是傳入合適的函數作為參數，完成了面向對象方式同樣的功能，同時還有一些額外的優點。沒有使自己囿于類的層次之中：可以在運行時傳入函數并在任何時候以更高的粒度更少的代碼修改他們。編譯器高效地為我們生成了面向對象的“粘合”代碼！除此之外，我們還獲得了所有函數式編程的其他好處。當然函數式語言提供的抽象不只這些，高階函數只是一個開始：

currying

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

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

currying.

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

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

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

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

square = int pow(int i, 2);

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

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

square_function_t square = new square_function_t();

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

惰性求值

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

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

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

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

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

優化

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

抽象控制結構

惰性求值提供了更高一級的抽象，它使得不可能的事情得以實現。例如，考慮實現如下的控制結構：

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

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

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

注意如果條件為真代碼將不被執行。我們不能在一個嚴格（strict）的語言中再現這種求值，因為 unless 調用之前會先對參數進行求值。

無窮(infinite)數據結構

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

缺點

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

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

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

Continuations

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Continuation 應該在什么情況下使用呢？通常在嘗試模擬一個本質上是無狀態的應用時可以簡化你的任務。Continuation 很適合在Web應用程序中使用。微軟公司的 ASP.NET 技術極盡苦心地模擬狀態以便你在開發 Web 應用時少費周折。可如果 C# 支持了continuation，ASP.NET 的復雜度就可以減半——你只需要保存一個 continuation，當用戶下次發出 web 請求時重啟它即可。對程序員來說，web 應用程序將不再有中斷——程序只是簡單的從下一行重啟！利用 continuation 這一抽象解決問題真是令人難以置信的便利。考慮到越來越多的胖客戶端應用程序正在向服務器端轉移，將來 continuation 也會變得越來越重要。

模式匹配

模式匹配不是什么新的創新的特性。事實上，它和函數式編程的關系不大。把產生模式匹配歸因于函數式編程的唯一的原因是函數式語言一度提供了模式匹配，然而現在的命令式語言還做不到。

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

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);

}

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

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

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

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

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

Closures

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

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

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

函數 make-power-fn 返回了一個函數，它有一個參數，并對這個參數進行一定階的冪運算。如果對 square(3) 求值會有什么結果？變量 power 不在 powerFn 的作用域中，因為 makePowerFn 已經返回它的棧楨而不復存在。那么square如何工作？一定是這個語言以某種方式將power的值保存了起來以便 square 使用。如果我們再新建一個函數cube，用來計算參數的立方又會怎樣？運行環境必須存儲兩個power的拷貝，每個我們用 make-power-fn 生成的函數都用一個拷貝。保存這些值的現象就被稱為 closure。 closure 不只保存宿主函數的參數。例如，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 的拷貝，即使這些拷貝本應在 makeIncrementer
返回時消失。這些代碼被如何編譯？closure 在底層是如何工作的？很幸運，我們可以去幕后看看。

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

class some_function_t {
SymbolTable parentScope;

// …

}

當一個 closure 引用了一個不在其作用域的變量時，它會在其祖先作用域中查找這個引用。就是這樣！Closure 將函數式和面向對象的世界緊密結合。當你創建了一個包含了一些狀態的類并把它傳到別處時，考慮一下 closure。Closure 就是這樣在取出作用域中的變量的同時創建“成員變量”，所以你不必親自去做這些！

下一步的計劃？

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

評論？

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

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

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

[2] 這像是個悖論。物理學家和數學家被迫確認他們還不完全清楚是否宇宙萬物遵循著可以被數學描述的規則。

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

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

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

[6] 大多數函數式編程語言的編譯器能通過將遞歸盡可能轉為迭代來進行優化，這被稱為尾遞歸。

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

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