計算機程式設計/函數語言程式設計

函數語言程式設計是一種將計算機程式視為數學函式的正規化。在使用純函式式風格程式設計時，我們不操作狀態和變數（會改變值的元素），而是完全關注常量和函式（永遠不會改變的元素）。函數語言程式設計 (FP) 的另一個顯著特徵是函式被視為一等公民。用函式式風格編寫的程式通常由接受其他函式作為輸入的函式組成。這是 FP 語言的關鍵特徵，因為它使得構建模組化程式變得非常容易。結果是，用 FP 語言編寫的軟體往往非常簡潔。事實上，烏特勒支大學的一組程式設計師僅用 10,000 行 Haskell 程式碼（包括圖形介面）就構建了用於“構建、編輯和分析貝葉斯網路”的工具。等效的 Java 程式則需要 200,000 行程式碼，是前者的 20 倍。

想要了解更多？你可以

快速瀏覽一下函數語言程式設計概覽，以獲得快速概述
訪問函數語言程式設計語言的華夏公益教科書，例如，Haskell（另請參閱Scheme 和 Common Lisp）。
閱讀下面的文章（針對來自命令式背景的程式設計師）

另請參閱程序式程式設計。

介紹

程式設計師是拖延症患者。進來，喝杯咖啡，檢視郵件，閱讀 RSS 訂閱，閱讀新聞，檢視技術網站上的最新文章，瀏覽程式設計論壇的指定部分的政治討論。重複這些步驟，確保沒有遺漏任何內容。去吃午飯。回來，盯著 IDE 看幾分鐘。檢視郵件。喝杯咖啡。不知不覺，一天就過去了。

唯一的一點是，偶爾確實會彈出一些有挑戰性的文章。如果你訪問了正確的地方，你每隔幾天就會找到至少一篇這樣的文章。這些文章很難讀懂，需要一些時間，所以它們開始堆積起來。不知不覺，你有一長串連結和一個裝滿 PDF 檔案的資料夾，你希望自己有一年時間待在一個與世隔絕的森林小屋裡，周圍沒有任何人，這樣你就可以追趕進度了。如果有人每天早上在你沿著河邊散步時過來送些食物並把垃圾帶走，那就太好了。

我不知道你的列表，但我的列表中很大一部分是關於函數語言程式設計的文章。這些文章通常是最難理解的。即使是“十年華爾街行業資深人士”，也無法理解函數語言程式設計（也稱為FP）文章的含義。如果你問花旗集團或德意志銀行¹ 的專案經理為什麼選擇使用 JMS 而不是 Erlang，他們會說他們不能使用學術語言來構建工業級應用。問題是，一些最複雜的系統，具有最嚴格的要求，是用函數語言程式設計元素編寫的。某些事情無法解釋。

FP 文章和論文確實很難理解，但這並非必然。造成知識差距的原因純粹是歷史性的。FP 概念本身並沒有什麼難懂之處。將這篇文章視為“FP 的易懂指南”，一座從我們命令式思維橋樑通往 FP 世界的橋樑。喝杯咖啡，繼續讀下去。如果幸運的話，你的同事很快就會開始因為你在 FP 方面的評論而嘲笑你。

那麼什麼是 FP？它是怎麼產生的？它能吃嗎？如果它像它的支持者聲稱的那樣有用，為什麼它在行業中沒有得到更廣泛的應用？為什麼只有擁有博士學位的人才會使用它？最重要的是，為什麼它如此難學？閉包、延續、柯里化、惰性求值和無副作用這些都是什麼？它如何在不涉及大學專案的專案中使用？為什麼它似乎與我們命令式思維中所有美好的、神聖的、珍貴的事物如此不同？我們很快就會澄清這一點。讓我們從解釋現實世界和學術文章之間巨大差距的原因開始。答案就像在公園裡散步一樣簡單。

公園漫步

啟動時光機。我們這次公園漫步發生在兩千多年前，在公元前 380 年一個被遺忘的春天裡一個陽光明媚的下午。在雅典城牆外，在橄欖樹的陰涼下，柏拉圖帶著一個美麗的奴隸男孩走向學院。天氣宜人，晚餐很豐盛，談話轉向哲學。

“看看這兩個學生，”柏拉圖一邊說一邊仔細地選擇詞語，以便使問題具有教育意義。“你認為誰更高？”奴隸男孩朝水池望去，那裡站著兩個人。“他們差不多高，”他說。“你說‘差不多’是什麼意思？”柏拉圖問道。“嗯，從這裡看他們看起來一樣高，但我相信如果我走近一點，就會發現他們之間有一些差異。”

柏拉圖笑了。他正在引導男孩走向正確的方向。“所以你會說我們世界上沒有完全相同的東西？”經過一番思考，男孩回答道：“我認為沒有。所有東西至少都有點不同，即使我們看不到。”重點突出了！“那麼，如果我們世界上沒有完全相同的東西，你認為你是如何理解‘完美’平等的概念的？”奴隸男孩看起來很困惑。“我不知道，”他回答道。

因此，第一次試圖理解數學的本質誕生了。柏拉圖認為，我們世界上所有事物都只是完美的近似值。他還意識到，即使我們從未遇到過完美，我們也理解完美的概念。他得出的結論是，完美的數學形式必須存在於另一個世界，而我們透過與那個“替代”宇宙的聯絡而瞭解它們。很明顯，我們無法觀察到完美的圓。但我們也理解什麼是完美的圓，並且可以透過方程來描述它。那麼什麼是數學？為什麼宇宙是用數學定律來描述的？我們宇宙的所有現象都可以用數學來描述嗎？²

數學哲學是一個非常複雜的學科。就像大多數哲學學科一樣，它更擅長提出問題而不是提供答案。許多共識圍繞這樣一個事實：數學實際上是一個謎題：我們建立一組基本的、不衝突的原則，以及一組關於如何操作這些原則的規則。然後我們可以將這些規則疊加在一起，得出更復雜的規則。數學家稱這種方法為“形式系統”或“演算”。如果我們想，我們就可以為俄羅斯方塊編寫一個形式系統。事實上，俄羅斯方塊的工作實現本身就是一個形式系統，只是用一種不尋常的表示方式指定。

半人馬座阿爾法星上的一群毛茸茸的生物文明將無法閱讀我們關於俄羅斯方塊和圓圈的形式化，因為它們唯一的感官輸入可能是一種感知氣味的器官。它們可能永遠不會發現關於俄羅斯方塊的形式化，但它們很有可能有一個關於圓圈的形式化。我們可能無法閱讀它，因為我們的嗅覺沒有那麼靈敏，但一旦你超越了形式化的表示（透過各種感官儀器和標準的破譯技術來理解語言），下面的概念是可以理解的任何智慧文明。

有趣的是，如果宇宙中從未存在過任何智慧文明，那麼關於俄羅斯方塊和圓圈的形式化仍然會成立，只是沒有人會在那裡發現它們。如果一個智慧文明出現了，它很可能會發現一些有助於描述我們宇宙定律的形式化。它們也很不可能發現俄羅斯方塊，因為宇宙中沒有與之相似的東西。俄羅斯方塊是無數形式系統（一個謎題）的例子之一，它與現實世界無關。我們甚至不能確定自然數是否與現實世界完全相似，畢竟人們很容易想到一個如此大的數字，以至於它不能描述我們宇宙中的任何東西，因為它實際上可能被證明是有限的。

一點歷史³

讓我們在我們的時光機中換擋。這一次我們將前往更近的地方，即 1930 年代。大蕭條正在席捲新舊世界。幾乎每個社會階層的家庭都受到了這場巨大經濟衰退的影響。幾乎沒有多少庇護所可以讓人們免受貧困的危害。很少有人有幸身處這些庇護所，但它們確實存在。我們感興趣的是普林斯頓大學的數學家。

新建的哥特式風格的辦公室為普林斯頓增添了一絲避風港的氛圍。來自世界各地的邏輯學家被邀請到普林斯頓建立一個新的系。當大多數美國人找不到一塊麵包吃晚飯的時候，普林斯頓卻擁有高高的天花板、用精雕細琢的木頭覆蓋的牆壁、每天喝著茶進行討論，以及在森林中散步等條件。

一位過著如此奢華生活的數學家是一位名叫阿隆佐·丘奇的年輕人。阿隆佐獲得了普林斯頓大學的理學士學位，並被勸說留在那裡攻讀研究生。阿隆佐覺得建築比必要的更華麗。他很少出現在喝茶討論數學的時候，也不喜歡在樹林裡散步。阿隆佐是一個獨來獨往的人：他獨自工作時效率最高。然而，阿隆佐與其他普林斯頓居民定期聯絡。其中包括艾倫·圖靈、約翰·馮·諾依曼和庫爾特·哥德爾。

這四個人對形式系統很感興趣。他們沒有過多地關注物理世界，而是對處理抽象的數學難題更感興趣。他們的難題有一個共同點：這些人都在努力回答關於計算的問題。如果我們擁有具有無限計算能力的機器，我們將能夠解決什麼問題？我們能自動解決它們嗎？一些問題會永遠無法解決嗎？為什麼？具有不同設計的各種機器在能力上是否相等？

阿隆佐·丘奇與其他男士合作開發了一個名為 lambda 演算的形式系統。該系統本質上是這些假想機器之一的程式語言。它基於將其他函式作為引數並返回函式作為結果的函式。該函式由希臘字母 lambda 標識，因此得名⁴。使用這種形式化，阿隆佐能夠對上述許多問題進行推理並提供結論性答案。

艾倫·圖靈獨立於阿隆佐·丘奇進行類似的工作。他開發了一個不同的形式化（現在被稱為圖靈機），並用它獨立地得出了與阿隆佐相似的結論。後來證明，圖靈機和 lambda 演算在能力上是等價的。

如果不是因為第二次世界大戰的爆發，故事就會在這裡結束，我會總結這篇文章，然後你就會轉到另一個頁面。世界陷入火海。美國陸軍和海軍比以往任何時候都更頻繁地使用炮兵。為了提高精度，陸軍僱用了一大批數學家來不斷計算解決彈道射擊表所需的微分方程。很明顯，這項任務對於人工解決來說太大了，因此開發了各種裝置來克服這個問題。第一臺解決彈道表的機器是由 IBM 製造的 Mark I - 它重達五噸，有 750,000 個部件，每秒可以進行三次運算。

當然，比賽還沒有結束。1949 年，電子離散變數自動計算機 (EDVAC) 問世，並取得了巨大的成功。它是馮·諾依曼體系結構的第一個例子，實際上是圖靈機的現實世界實現。暫時來說，阿隆佐·丘奇運氣不佳。

在 1950 年代後期，麻省理工學院教授約翰·麥卡錫（也是普林斯頓大學畢業生）對阿隆佐·丘奇的工作產生了興趣。1958 年，他公佈了一種列表處理語言 (Lisp)。Lisp 是阿隆佐的 lambda 演算的實現，可以在馮·諾依曼計算機上執行！許多計算機科學家認識到 Lisp 的表達能力。1973 年，麻省理工學院人工智慧實驗室的一組程式設計師開發了他們稱之為 Lisp 機器的硬體 - 實際上是阿隆佐的 lambda 演算的原生硬體實現！

函數語言程式設計

函數語言程式設計是阿隆佐·丘奇思想的實際應用。並非所有 lambda 演算思想都能轉化為實踐，因為 lambda 演算並非為在物理限制下工作而設計的。因此，與面向物件程式設計一樣，函數語言程式設計是一組思想，而不是一組嚴格的準則。存在許多函數語言程式設計語言，它們中的大多數在許多方面都大相徑庭。在本文中，我將使用用 Java 編寫 (是的，如果你覺得特別虐待狂，你可以在 Java 中編寫函式式程式) 的示例解釋函式式語言中最廣泛使用的思想。在接下來的幾節中，我們將按原樣使用 Java，並對其進行修改，將其轉換為可用的函式式語言。讓我們開始我們的探索。

lambda 演算旨在研究與計算相關的問題。因此，函數語言程式設計主要處理計算，並且令人驚訝的是，它使用函式來進行計算。函式是函數語言程式設計中最基本的單元。函式幾乎用於所有事情，即使是最簡單的計算。甚至變數也被替換為函式。在函數語言程式設計中，變數只是表示式的別名（因此我們不必在一行中輸入所有內容）。它們不能被修改。所有變數只能被賦值一次。在 Java 術語中，這意味著每個變數都被宣告為final (或者如果我們使用的是 C++，則是const)。FP 中沒有非最終變數。

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

由於 FP 中的每個變數都是最終的，所以可以做出兩個相當有趣的陳述。始終編寫關鍵字final 沒有意義，並且將變數稱為變數也沒有意義。現在，我們將對 Java 進行兩項修改：我們函式式 Java 中宣告的每個變數預設情況下都是最終的，我們將把變數稱為符號。

到目前為止，你可能想知道如何在我們新建立的語言中編寫任何合理複雜的東西。如果每個符號都是不可變的，我們就無法改變任何東西的狀態！這並不完全正確。當阿隆佐研究 lambda 演算時，他並不關心如何維護一段時間內的狀態以便以後修改它。他感興趣的是對資料進行操作（也通常稱為“計算東西”。然而，它被證明 lambda 演算等價於圖靈機。它可以做指令式程式設計語言可以做的所有事情。那麼，我們如何才能實現相同的結果呢？

事實證明，函式式程式可以保持狀態，只是它們不使用變數來做到這一點。它們使用函式來代替。狀態儲存在函式引數中，在堆疊上。如果你想保留一段時間的狀態，並偶爾修改它，你可以編寫一個遞迴函式。例如，讓我們寫一個反轉 Java 字串的函式。記住，我們宣告的每個變數預設都是 final⁵。

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

這個函式很慢，因為它反覆呼叫自身⁶。它是一個記憶體佔用大戶，因為它反覆分配物件。但它的風格是函式式的。你可能想知道為什麼有人會想要以這種方式程式設計。嗯，我正要告訴你。

FP 的優點

你可能認為我絕不可能為上面的函式怪物找出一個合理的解釋。當我學習函數語言程式設計的時候，我也這麼想。我錯了。使用這種風格有很多很好的理由。其中一些是主觀的。例如，人們聲稱函式式程式更容易理解。我將省略這些論點，因為每個人都知道理解的難易程度見仁見智。幸運的是，還有很多客觀的論點。

單元測試

由於 FP 中的每個符號都是 final，所以沒有任何函式能夠引起副作用。你永遠不能在原地修改東西，也不能一個函式修改其作用域之外的值供另一個函式使用（比如類成員或全域性變數）。這意味著，評估一個函式的唯一效果是它的返回值，而影響函式返回值的唯一因素是它的引數。

這對單元測試人員來說非常有用。你可以在你的程式中測試每個函式，只需關注它的引數。你不需要擔心以正確的順序呼叫函式，或者正確設定外部狀態。這意味著你可以減少在編寫模擬、存根和其他形式的偽物件上的時間，以及減少在驗證測試套件是否運行了設定和拆卸方法上的時間。你所需要做的就是傳遞代表邊緣情況的引數。如果你的程式中的每個函式都通過了單元測試，那麼你對軟體質量的信心會比使用命令式語言要高得多。在 Java 或 C++ 中，檢查一個函式的返回值是不夠的 - 它可能會修改外部狀態，我們需要驗證它。在函式式語言中則不是這樣。

除錯

如果一個函式式程式的行為不符合預期，除錯它將變得輕而易舉。你將始終能夠重現你的問題，因為函式式程式中的 bug 不依賴於之前執行的無關程式碼路徑。在命令式程式中，bug 只會在某些時候出現。因為函式依賴於由其他函式的副作用產生的外部狀態，你可能需要經歷一系列與 bug 無關的步驟。在函式式程式中，情況並非如此 - 如果一個函式的返回值是錯誤的，它就始終是錯誤的，無論你在執行該函式之前執行了什麼程式碼。

一旦你重現了問題，找到問題的根源就變得非常簡單。這幾乎是令人愉快的。你中斷程式的執行，並檢查堆疊。堆疊中每個函式呼叫中的每個引數都可供你檢查，就像在命令式程式中一樣。區別在於，在命令式程式中，這還不夠，因為函式依賴於成員變數、全域性變數和其他類的狀態（而這些類又依賴於這些相同的東西）。函式式程式中的函式只依賴於它的引數，而這些資訊就在你眼前！此外，在命令式程式中，檢查一個函式的返回值並不能很好地告訴你該函式是否正常工作。你需要找出它作用域之外的許多物件，以驗證它是否執行了正確的操作。在函式式程式中，你只需要檢視返回值！

在堆疊中一步一步地走，檢視傳遞給函式的引數及其返回值。當返回值沒有意義時，你就進入有問題的函式，並一步一步地走完它。你遞迴地重複此過程，直到找到 bug 的根源！

併發

函式式程式已經做好了併發準備，無需任何進一步的修改。你永遠不需要擔心死鎖和競爭條件，因為你不需要使用鎖！函式式程式中沒有一塊資料會被同一個執行緒修改兩次，更不用說被兩個不同的執行緒修改了。這意味著你可以輕鬆地新增執行緒，而無需考慮困擾併發應用程式的傳統問題！

如果是這樣，為什麼沒有人使用函式式程式來開發高度併發的應用程式呢？事實證明，他們確實使用了。愛立信設計了一種名為 Erlang 的函式式語言，用於其高度容錯和可擴充套件的電信交換機。許多人認識到 Erlang 提供的優勢，並開始使用它。我們談論的是電信和交通控制系統，它們比華爾街設計的典型系統更具可擴充套件性和可靠性。Erlang 系統非常堅固。

併發的故事並沒有止步於此。如果你的應用程式本質上是單執行緒的，編譯器仍然可以最佳化函式式程式以在多個 CPU 上執行。看看下面的程式碼片段

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

在函式式語言中，編譯器可以分析程式碼，將建立字串s1和s2的函式歸類為潛在的耗時操作，並並行執行它們。在命令式語言中這是不可能做到的，因為每個函式都可能修改其作用域之外的狀態，而隨後的函式可能依賴於它。在函式式語言中，自動分析函式並找到並行執行的良好候選者與自動內聯一樣簡單！從這個意義上說，函式式程式是“面向未來的”（儘管我很討厭流行語，但這次我忍不住）。硬體製造商無法再讓 CPU 執行得更快。相反，他們增加了核心數量，並將四倍的速度提升歸功於併發。當然，他們很方便地忘記了，只有在處理並行化問題的軟體上，我們才能物有所值。這在命令式軟體中只佔一小部分，而在函式式軟體中則佔 100%，因為函式式程式都支援開箱即用的並行化。

熱程式碼部署

在 Windows 的早期，為了安裝更新，必須重啟計算機。很多次。在安裝了更新版本的媒體播放器之後。隨著 Windows XP 的出現，情況有了顯著改善，但它仍然不是理想的（我今天在工作中運行了 Windows Update，現在一個煩人的系統托盤圖示不會消失，除非我重啟）。Unix 系統已經有一段時間了，它們有一個更好的模型。為了安裝更新，你只需要停止相關的元件，而不是整個作業系統。雖然這種情況已經改善，但對於一大類伺服器應用程式來說，它仍然不可接受。電信系統需要 100% 的時間執行，因為如果由於升級而無法撥打緊急電話，可能會造成人員傷亡。華爾街的公司沒有理由在週末停機安裝軟體更新。

理想的情況是在不停止系統任何部分的情況下更新程式碼的相關部分。在命令式世界中，這是不可能的。考慮在執行時解除安裝 Java 類並重新載入新的定義。如果我們這樣做，類的每個例項都將變得不可用，因為它所持有的狀態將丟失。我們需要求助於編寫棘手的版本控制程式碼。我們需要序列化所有正在執行的類例項，銷燬它們，建立新類的例項，嘗試將序列化資料載入到它們中，並希望載入程式碼能夠將資料正確地遷移到新例項中。最重要的是，每次我們改變一些東西時，我們都必須手動編寫遷移程式碼。而且我們的遷移程式碼必須特別小心，不要破壞物件之間的關係。理論上很好，但在實踐中永遠不會有效。

在函式式程式中，所有狀態都儲存在堆疊中，儲存在傳遞給函式的引數中。這使得熱部署變得容易得多！事實上，我們真正需要做的就是執行生產程式碼和新版本之間的 diff，並部署新程式碼。剩下的可以由語言工具自動完成！如果你認為這是科幻小說，那就再想想。Erlang 工程師已經升級了執行中的系統多年，而沒有停止它們。

機器輔助證明和最佳化

函式式語言的一個有趣的特性是它們可以用數學方法進行推理。由於函式式語言僅僅是形式系統的實現，因此所有可以在紙上進行的數學運算仍然適用於用該語言編寫的程式。例如，編譯器可以將程式碼片段轉換為等效的但更有效的程式碼片段，並用數學證明兩個程式碼片段是等效的⁷。關係型資料庫多年來一直在執行這些最佳化。沒有理由同樣的技術不能應用於常規軟體。

此外，您可以使用這些技術來證明程式的某些部分是正確的。甚至可以建立工具來分析程式碼並自動生成單元測試的邊緣案例！此功能對於堅如磐石的系統來說非常寶貴。如果您正在設計起搏器和空中交通管制系統，這些工具幾乎總是必需的。如果您正在編寫非真正關鍵任務行業的應用程式，這些工具可以使您在競爭中佔據巨大優勢。

高階函式

我記得我學到上面列出的好處時，心想“這很好，但如果我必須用一種功能受限的語言程式設計，而其中所有東西都是最終的，那這毫無用處。”這是一個誤解。在像 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 類沒有什麼不同（我們可以將類例項傳遞給其他類）。我們可以稱它們為“高階類”，但沒有人關心，因為 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);

我們沒有建立新的型別，也沒有建立類層次結構。我們只是將合適的函式作為引數傳遞。我們以面向物件對應物的優勢實現了相同的功能。我們不會將自己限制在類層次結構中：我們可以在執行時傳遞新的函式，並在任何時候以更高的粒度、更少的程式碼來更改它們。實際上，編譯器為我們編寫了面向物件的“粘合”程式碼！此外，我們獲得了 FP 的所有其他好處。當然，函式式語言提供的抽象不會止步於此。高階函式只是開始。

柯里化

我遇到的大多數人讀過四人幫寫的 _設計模式_ 一書。任何自尊的程式設計師都會告訴你，這本書與語言無關，這些模式適用於一般的軟體工程，無論你使用哪種語言。這是一個崇高的主張。不幸的是，它與事實相去甚遠。

函式式語言表達能力極強。在函式式語言中，不需要設計模式，因為語言可能非常高階，最終你會用一些概念程式設計，這些概念完全消除了設計模式。一旦這樣的模式是介面卡模式（它與外觀模式有何不同？聽起來像是有人需要填寫更多頁面來滿足他們的合同）。一旦語言支援一種稱為 _柯里化_ 的技術，它就會被消除。

介面卡模式在應用於 Java 中的“預設”抽象單元（類）時最為人知。在函式式語言中，該模式應用於函式。該模式採用介面，將其轉換為其他人期望的另一個介面。以下是一個介面卡模式的示例

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

上面的程式碼將一個將整數升到整數次冪的函式的介面適配到一個將整數平方為整數的函式的介面。在學術界，這種微不足道的技術被稱為柯里化（以邏輯學家 Haskell Curry 的名字命名，他進行了將這種技術形式化的數學特技）。因為在 FP 中，函式（與類相反）作為引數傳遞，所以柯里化經常被用來將函式適配到其他人期望的介面。由於函式的介面是其引數，因此柯里化用於減少引數數量（如上面的示例中）。

函式式語言內建了這種技術。您不需要手動建立一個包裝原始函式的函式，函式式語言會為您做到這一點。像往常一樣，讓我們擴充套件我們的語言以支援這種技術。

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

如您所見，我們只是為原始函式建立了一個包裝器。在 FP 中，柯里化僅僅是 - 一種快速輕鬆地建立包裝器的捷徑。您專注於自己的任務，編譯器會為您編寫合適的程式碼！您什麼時候使用柯里化？這應該很簡單。任何時候您想使用介面卡模式（包裝器）。

惰性求值

惰性（或延遲）求值是一種有趣的技術，一旦我們採用函式式哲學，它就成為可能。我們已經在討論併發時看到了以下程式碼片段

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

在命令式語言中，求值的順序將是明確的。因為每個函式都可能影響或依賴於外部狀態，所以有必要按順序執行它們：首先是 somewhatLongOperation1，然後是 somewhatLongOperation2，最後是 concatenate。在函式式語言中則不然。

正如我們之前所看到的，somewhatLongOperation1 和 somewhatLongOperation2 可以併發執行，因為我們保證沒有函式影響或依賴於全域性狀態。但是，如果我們不想併發執行這兩個函式，我們是否需要按順序執行它們？答案是否定的。我們只需要在另一個函式依賴於 s1 和 s2 時執行這些操作。我們甚至不必在呼叫 concatenate 之前執行它們 - 我們可以延遲它們的求值，直到它們在 concatenate 中被需要。如果我們將 concatenate 替換為一個具有條件語句並只使用兩個引數之一的函式，我們可能根本不會對其中一個引數進行求值！Haskell 是一個延遲求值語言的例子。在 Haskell 中，您不能保證任何東西都會按順序（或完全）執行，因為 Haskell 只會在需要時執行程式碼。

惰性求值有很多優點和缺點。我們將在這裡討論優點，並在下一節中解釋如何克服缺點。

最佳化

惰性求值為最佳化提供了巨大的潛力。一個惰性編譯器對函式式程式碼的看法與數學家對代數表示式的看法完全相同 - 它可以消除某些東西，並完全阻止執行，重新排列程式碼片段以提高效率，甚至以減少錯誤的方式安排程式碼，所有這些都保證最佳化不會破壞程式碼。這是用嚴格的形式原語表示程式的最大好處 - 程式碼遵循數學定律，可以用數學方法進行推理。

抽象控制結構

惰性求值提供了更高層次的抽象，允許以其他方式不可能的方式實現事物。例如，考慮實現以下控制結構

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

我們希望除非股票是歐洲股票，否則執行 sendToSEC。我們如何實現 unless？如果沒有惰性求值，我們需要某種宏系統，但在像 Haskell 這樣的語言中，這是不必要的。我們可以將 unless 實現為一個函式！

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

請注意，如果條件為真，則程式碼永遠不會被評估。由於引數將在unless之前進行評估，因此我們無法在嚴格的語言中複製此行為。

無限資料結構

惰性語言允許定義無限資料結構，這在嚴格的語言中要複雜得多。例如，考慮一個包含斐波那契數的列表。很明顯，我們無法在合理的時間內計算一個無限列表，也無法將其儲存在記憶體中。在像Java這樣的嚴格語言中，我們只需定義一個斐波那契函式，它從序列中返回特定成員。在像Haskell這樣的語言中，我們可以進一步抽象，並簡單地定義一個無限的斐波那契數列表。由於該語言是惰性的，因此程式實際使用的列表的必要部分才會被評估。這允許抽象出許多問題，並從更高的層次（例如，我們可以對無限列表使用列表處理函式）來解決這些問題。

缺點

當然，沒有免費的午餐™。（除非你幸運。）惰性求值似乎帶來了一些缺點。主要是因為它很懶，有時不允許程式設計師也隨心所欲，這意味著在某些情況下，你需要使用一些變通方法。現實世界中存在需要嚴格求值的問題。例如，考慮以下情況

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

在惰性語言中，你無法保證第一行會在第二行之前執行！這意味著，如果惰性是絕對的原則，我們就無法進行IO，也無法以任何有意義的方式使用原生函式（因為它們需要按順序呼叫，因為它們依賴於副作用），也不能與外部世界互動！如果我們要引入強制順序程式碼執行的原語，我們將失去以數學方式推理程式碼的能力（這將帶走函數語言程式設計的所有好處）。幸運的是，並非所有希望都破滅了。數學家們開始研究並開發了許多技巧，以確保程式碼在函式式環境中按特定順序執行。因此，我們真的得到了兩全其美！這些技術包括延續、單子、以及唯一型別。在本文中，我們只討論延續。我們將在以後討論單子和唯一型別。有趣的是，延續除了強制執行特定的評估順序之外，還有很多其他的用途。我們也會討論這些。

延續

延續對於程式設計來說，就像達芬奇密碼對於人類歷史一樣：一個關於人類歷史上最偉大的掩蓋的驚人啟示。好吧，也許不是，但它們確實揭示了欺騙，就像負數的平方根一樣。

當我們學習函式時，我們只學習了基於一個錯誤假設的半真半假的內容，即函式必須將其值返回給原始呼叫者。從這個意義上說，延續是函式的泛化。函式不一定要返回給它的呼叫者，它可以返回到程式的任何部分。“延續”是我們選擇傳遞給函式的引數，它指定函式應該返回的位置。描述可能比聽起來更復雜。看看下面的程式碼

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

函式add返回15，以便分配給i，即add最初被呼叫的地方。之後，i的值被用來呼叫square。請注意，惰性編譯器不能重新排列這些程式碼行，因為第二行依賴於第一行的成功評估。我們可以使用Continuation Passing Style（CPS）重寫此程式碼塊，其中函式add不返回給原始呼叫者，而是將結果返回給square。

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

在這種情況下，add獲得了另一個引數 - 一個函式，add必須在完成時用其結果呼叫該函式。在本例中，square是add的延續。在這兩種情況下，j都將等於225。

這裡包含了迫使惰性語言按順序評估兩個表示式的第一個技巧。考慮以下（熟悉的）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可以接受），我們將解決我們的問題！當然，像這樣連結函式呼叫很快就會變得難以閱讀，但這不是必需的。我們可以向語言新增語法糖，允許我們按順序簡單地鍵入表示式，編譯器將自動為我們連結這些呼叫。我們現在可以按照我們希望的任何順序評估表示式，而不會失去FP的任何好處（包括以數學方式推理程式的能力）！如果這仍然令人困惑，請記住，函式只是具有一個成員的類的例項。重寫上面兩行，使println和readLine成為類的例項，一切都會變得清晰。

我現在將結束本節，因為我們只觸及了延續及其有用性的皮毛。我們可以用CPS編寫完整的程式，其中每個函式都接受一個額外的延續引數，並將結果傳遞給它。我們還可以簡單地將任何程式轉換為CPS，方法是將函式視為延續的特例（總是返回給其呼叫者的函式）。這種轉換很容易自動完成（實際上，許多編譯器就是這麼做的）。

一旦我們將程式轉換為CPS，就會發現每個指令都有一個延續，一個函式，它將使用結果呼叫該函式，這在常規程式中將是它必須返回到的位置。讓我們從上面的程式碼中選擇任何一條指令，比如add(5, 10)。在用CPS編寫的程式中，很清楚add的延續是什麼 - 它是一個函式，add完成時會呼叫它。但在非CPS程式中呢？當然，我們可以將程式轉換為CPS，但我們必須這樣做嗎？

事實證明我們不需要。仔細觀察我們的CPS轉換。如果你嘗試為它編寫一個編譯器，並仔細考慮它，你會意識到CPS版本不需要堆疊！沒有函式以傳統意義上“返回”，它只是用結果呼叫另一個函式。我們不需要在每次呼叫時將函式引數壓入堆疊，然後將它們彈出，我們只需將它們儲存在記憶體的某個塊中，並使用跳轉指令。我們永遠不需要原始引數 - 它們永遠不會被再次使用，因為沒有函式會返回！

因此，用CPS編寫的程式沒有堆疊，但有一個帶有函式的額外引數要呼叫。沒有用CPS編寫的程式沒有帶有函式的額外引數要呼叫，但有堆疊。堆疊包含什麼？僅僅是引數，以及指向函式應該返回的記憶體位置的指標。你看到燈泡了嗎？堆疊只是包含延續資訊！指向堆疊中返回指令的指標本質上與CPS程式中要呼叫的函式相同！如果你想找出add(5, 10)的延續是什麼，你只需要檢查它執行時的堆疊即可！

所以這很容易。延續和指向堆疊中返回指令的指標實際上是一回事，只是顯式地傳遞了一個延續，因此它不需要與呼叫函式的相同位置相同。如果你記得延續是一個函式，而我們語言中的函式被編譯成一個類的例項，你會意識到，指向堆疊中返回指令的指標和延續引數實際上是一回事，因為我們的函式（就像類的例項一樣）只是一個指標。這意味著，在程式中的任何給定時間點，你都可以請求當前延續（它只是堆疊上的資訊）。

好的，我們已經知道什麼是當前延續，那它意味著什麼呢？當我們獲取當前延續並將它儲存在某個地方時，我們最終會儲存程式的當前狀態 - 將其凍結在時間中。這類似於作業系統將自身置於休眠狀態。延續物件包含重啟程式所需的資訊，從獲取延續物件的位置開始。作業系統在它線上程之間切換上下文時一直這樣做。唯一的區別是它保留了所有控制權。如果你請求一個延續物件（在 Scheme 中，這是透過呼叫 `call-with-current-continuation` 函式完成的），你將得到一個包含當前延續的物件 - 棧（或者在 CPS 情況下，下一個要呼叫的函式）。你可以將此物件儲存在一個變數中（或者也可以儲存在磁碟上）。當你選擇使用這個延續物件“重啟”你的程式時，你將“轉換”到獲取延續物件時程式的狀態。這與切換回一個掛起的執行緒或喚醒作業系統從休眠狀態相同，只是你可以反覆執行。當作業系統喚醒時，休眠資訊會被銷燬。如果它沒有被銷燬，你將能夠一遍又一遍地從同一個點喚醒，幾乎就像回到過去。你擁有使用延續的這種控制權！

在哪些情況下延續是有用的？通常當你嘗試在一個本質上是無狀態的應用程式中模擬狀態以簡化你的生活時。延續的一個很好的應用是 Web 應用程式。微軟的 ASP.NET 竭盡全力地嘗試模擬狀態，以便你能更容易地編寫你的應用程式。如果 C# 支援延續，ASP.NET 的一半複雜性將會消失 - 你只需儲存一個延續並在使用者再次發出 Web 請求時重啟它。對於 Web 應用程式的程式設計師來說，將不會有任何中斷 - 程式將簡單地從下一行開始！延續對於一些問題來說是一個非常有用的抽象。考慮到許多傳統的胖客戶端正在轉向 Web，延續在未來會變得越來越重要。

模式匹配

模式匹配不是一個新的或創新的特性。事實上，它與函數語言程式設計關係不大。它通常被歸因於 FP 的唯一原因是函式式語言已經有了模式匹配一段時間了，而現代的命令式語言還沒有。

讓我們透過一個例子深入瞭解模式匹配。這是一個在 Java 中的斐波那契函式

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

（不要嘗試使用更高的數字，因為這個演算法不適合更高的數字，因為它具有 ${\mathcal {O}}(2^{n})$ 時間複雜度；`fib(35)` 將會花費相當長的時間）

有什麼區別？編譯器為我們實現了分支。

有什麼大不了的？沒什麼。有人注意到大量的函式包含非常複雜的 switch 語句（這對函式式程式來說尤其如此），並決定將這些抽象出來是一個好主意。我們將函式定義拆分為多個，並將模式放在一些引數的位子上（有點像過載）。當函式被呼叫時，編譯器在執行時將引數與定義進行比較，並選擇正確的定義。這通常是透過選擇最具體的可用定義來完成的。例如，`int fib(int n)` 可以用 `n` 等於 `1` 來呼叫，但它不會被呼叫，因為 `int fib(1)` 更具體。

另一個可能性，你可以在 Haskell 中找到，是按定義的順序檢查模式（函式式程式中表達式順序為數不多的幾個重要的例子之一，但你的大部分程式碼可以按任何你想要的順序編寫，這非常方便）。例如，函式的引數可能針對三種模式進行測試：`fun (x < 100)`、`fun (x < 1000)`、`fun (x = anything)`，當用 `x = 50` 呼叫時，將使用其定義的第一個例項，儘管 `x = 50` 也適合另外兩個例項。（從數學意義上講，考慮到負數，這些定義中沒有一個是更具體的，因為匹配模式的集合的大小都相同。）在這個系統中，你通常按順序排列定義，以便更具體的定義排在前面，這會自動涵蓋決定使用哪個函式例項的其他方式。

模式匹配通常比我們的例子更復雜。例如，一個高階模式匹配系統將允許我們執行以下操作

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

模式匹配什麼時候有用？在令人驚訝的大量情況下！每當你有一個巢狀 `if` 的複雜結構時，模式匹配可以使用更少的程式碼來完成更好的工作。一個想到的好函式是所有 Win32 應用程式都必須提供的標準 `WndProc` 函式（即使它通常被抽象掉了）。通常情況下，模式匹配系統可以檢查集合以及簡單值。例如，如果你將一個數組傳遞給你的函式，你可以挑選出所有第一個元素等於 `1` 且第三個元素大於 `3` 的陣列。

模式匹配的另一個好處是，如果你需要新增或修改條件，你不需要進入一個巨大的函式。你只需新增（或修改）相應的定義即可。這消除了對 Gang of Four 書籍中的一系列設計模式的需求。你的條件越複雜，模式匹配就能越幫助你。一旦你習慣了它，你就會開始思考沒有它你曾經是如何度過每一天的。

閉包

到目前為止，我們已經在“純粹”函式式語言的背景下討論了這些特性 - 這些語言是 lambda 演算的實現，不包含與 Church 形式主義衝突的特性。然而，函式式語言的許多特性在 lambda 演算框架之外也很有用。雖然一個公理化系統的實現很有用，因為它允許用數學表示式來思考程式，但它可能實用也可能不實用。許多語言選擇包含函式式元素，而沒有嚴格遵守函式式教條。許多這樣的語言（如 Common Lisp）不要求變數是最終的 - 你可以在適當的位置修改它們。它們也不要求函式只依賴於它們的引數 - 函式被允許訪問它們邊界之外的狀態。但是它們確實包含函式式特性 - 比如高階函式。在非純語言中傳遞函式與在 lambda 演算的限制下傳遞函式略有不同，它需要對一個有趣的特性提供支援，這個特性通常被稱為詞法閉包。讓我們看一些示例程式碼。記住，在這種情況下，變數不是最終的，函式可以引用其範圍之外的變數

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

   return powerFn;
}

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

函式 `makePowerFn` 返回一個函式，該函式接收一個引數並將它提升到某個冪。當我們嘗試評估 `square(3)` 時會發生什麼？變數 `power` 在 `powerFn` 的範圍內不存在，因為 `makePowerFn` 已經返回，它的棧早就消失了。那麼 `square` 如何工作呢？該語言必須以某種方式將 `power` 的值儲存在某個地方，以便 `square` 工作。如果我們建立一個新的函式 `cube`，它將某個值提升到三次冪，會發生什麼？執行時現在必須儲存 `power` 的兩個副本，一個用於每個使用 `makePowerFn` 生成的函式。儲存這些值的現象被稱為 `閉包`。閉包不僅儲存宿主函式的引數。例如，閉包可以是這樣的

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`，以便 `incrementer` 可以訪問它。此外，它儲存了各個副本，每個 `incrementer` 一個，即使它們應該在 `makeIncrementer` 返回時消失。這段程式碼編譯成什麼？閉包在幕後是如何工作的？幸運的是，我們有一個後臺通行證。

一點常識可以走很遠。第一個觀察結果是，區域性變數不再侷限於簡單的範圍規則，並且具有未定義的壽命。顯而易見的結論是，它們不再儲存在棧上 - 它們必須儲存在堆上8。那麼，閉包的實現方式就像我們之前討論的函式一樣，只是它有一個額外的引用指向周圍的變數

class some_function_t {
   SymbolTable parentScope;
   
   // ...
}

當一個閉包引用一個不在其區域性範圍內的變數時，它會查詢這個引用以獲取父範圍。就是這樣！閉包使函式式和麵向物件的世界更接近。每次你建立一個包含某些狀態的類並將其傳遞到其他地方時，都想想閉包。閉包只是一個物件，它透過從範圍內獲取它們來動態建立“成員變數”，因此你不需要這樣做！

接下來是什麼？

這篇文章只是觸及了函數語言程式設計的表面。有時一個小小的劃痕可以發展成更大的東西，在我們的例子中，這是一件好事。在將來，我計劃寫一些關於範疇論、單子、函式式資料結構、函式式語言中的型別系統、函式式併發、函式式資料庫等等的內容。如果我能夠寫出（並在這個過程中學習）這些主題中的一半，我的生活將完整無缺。同時，Google 是我們的朋友。

評論？

如果你有任何問題、評論或建議，請在 coffeemug@gmail.com 上留言。我很樂意聽到你的反饋。

¹2005 年秋季找工作的時候，我經常問這個問題。有趣的是，很多人對此一臉茫然。你會以為，這些價值 30 萬美元的人至少應該對他們能用的工具有所瞭解吧。

²這個問題似乎頗具爭議。物理學家和數學家不得不承認，宇宙中所有事物是否都遵循可以用數學描述的規律，目前尚不清楚。

³我一直不喜歡那些枯燥地列出年代、人物和事件的歷史課。對我來說，歷史是關於改變世界的人們的故事。它關乎他們行動背後的個人原因，以及他們影響數百萬人的機制。因此，本歷史部分內容不完整。只討論了非常重要的人物和事件。

⁴學習函數語言程式設計時，我對 “lambda” 這個詞感到很困惑，因為它讓我難以理解其真正的含義。在這個語境下，lambda 指的是函式，用單個希臘字母在數學符號中更易於書寫。每次你聽到函數語言程式設計中的 “lambda”，就在腦海中將其替換為 “函式”。

⁵有趣的是，Java 字串本身就是不可變的。探索其背後的原因很有意思，但會偏離我們的目標。

⁶大多數函式式語言編譯器會透過將遞迴函式轉換為迭代形式來最佳化它們，只要有可能就會這樣做。這被稱為尾呼叫最佳化（tail call optimization）。

⁷反過來卻不一定成立。雖然有時可以證明兩段程式碼等價，但在所有情況下都無法做到。

⁸實際上，這並不比儲存在棧上慢，因為一旦引入了垃圾收集器，記憶體分配就變成了一個 O(1) 操作。

介紹