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

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

想要了解更多？您可以

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

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

簡介

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

唯一的一點是，偶爾確實會出現具有挑戰性的文章。如果你檢視正確的地方，你會發現每隔幾天至少有一篇這樣的文章。這些文章很難讀懂，需要花一些時間，所以它們開始堆積起來。不知不覺中，你擁有一份連結列表和一個裝滿 PDF 檔案的資料夾，你希望自己有一年時間住在森林中央的一間小屋裡，周圍方圓數英里都沒有人，這樣你就能趕上進度。如果有人在你每天早晨沿著河邊散步時進來送食物並把垃圾拿走，那就太好了。

我不知道你的列表，但我列表中很大一部分文章都是關於函數語言程式設計的。這些通常是最難讀懂的。即使是“十年華爾街行業老手”也無法理解函數語言程式設計（也稱為FP）文章的全部內容。如果你問花旗集團或德意志銀行的專案經理¹ 為什麼他們選擇使用 JMS 而不是 Erlang，他們會說他們無法將學術語言用於工業級應用程式。問題是，一些最複雜的系統，它們具有最嚴格的要求，是用函數語言程式設計元素編寫的。有些地方不對勁。

確實，FP 文章和論文很難理解，但它們並不一定如此。造成知識差距的原因純粹是歷史性的。FP 概念本身並不難。將這篇文章視為“通往 FP 的便捷指南”，是我們從命令式思維模式到 FP 世界的橋樑。喝點咖啡，繼續閱讀。幸運的話，你的同事很快就會開始嘲笑你關於 FP 的評論。

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

公園漫步

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

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

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

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

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

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

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

一點歷史³

讓我們在時間機器中換檔。這次我們會走得更近一些，到1930年代。大蕭條席捲了新舊世界。幾乎每個社會階層的家庭都受到了這場巨大經濟衰退的影響。人們遠離貧困的危險，幾乎沒有安全的地方。很少有人有幸身處這些避風港，但它們確實存在。我們感興趣的是普林斯頓大學的數學家。

用哥特式風格建造的新辦公室賦予了普林斯頓一種避風港的氛圍。來自世界各地的邏輯學家被邀請到普林斯頓，建立一個新的系。當美國大多數人無法找到一塊麵包來吃晚餐時，普林斯頓卻擁有高高的天花板、覆蓋著精雕細刻的木頭的牆壁、每天一杯茶的討論和森林裡的散步。

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

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

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

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

如果沒有第二次世界大戰的爆發，故事就會到此結束，我會結束這篇文章，而你會導航到另一個頁面。全世界都陷入戰火。美國陸軍和海軍比以往任何時候都更頻繁地使用火炮。為了提高精度，陸軍僱傭了一大批數學家來不斷計算解決彈道射擊表所需的微分方程。很明顯，這項任務太繁重了，無法手動完成，因此開發了各種裝置來克服這個問題。第一臺解決彈道表的機器是 IBM 製造的 Mark I——它重達 5 噸，擁有 750,000 個零件，每秒鐘可以執行 3 次操作。

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

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

函數語言程式設計

函數語言程式設計是阿隆佐·丘奇思想的實際實現。並非所有的 lambda 演算思想都轉化為實踐，因為 lambda 演算並非設計用於在物理限制下工作。因此，與面向物件程式設計一樣，函數語言程式設計是一組思想，而不是一組嚴格的準則。有許多函數語言程式設計語言，它們中的大多數在很多方面都大不相同。在這篇文章中，我將使用用 Java 編寫的示例解釋函式式語言中最常用的思想（是的，如果你覺得特別受虐，你可以在 Java 中編寫函式式程式）。在接下來的幾節中，我們將照常使用 Java，並對其進行修改以將其轉變為可用的函式式語言。讓我們開始我們的探索。

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

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

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

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

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

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

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

FP 的優勢

你可能在想，我絕不可能為上面那個函式的怪異行為辯解。當我學習函數語言程式設計時，我也是這麼想的。我錯了。使用這種風格有很多很好的理由。其中一些是主觀的。例如，人們聲稱函式式程式更容易理解。我會省略這些論點，因為每個街區的孩子都知道理解的難易程度是見仁見智的。幸運的是，對我有利的是，有很多客觀論據。

單元測試

由於 FP 中的每個符號都是最終的，因此任何函式都無法產生副作用。你永遠無法就地修改事物，也不能讓一個函式修改其作用域之外的值供另一個函式使用（例如類成員或全域性變數）。這意味著評估函式的唯一效果是它的返回值，而影響函式返回值的唯一因素是它的引數。

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

除錯

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

一旦你重現了問題，找出根本原因就變得微不足道。這幾乎是一種享受。你中斷程式的執行並檢查堆疊。堆疊中每個函式呼叫中的每個引數都可供你檢查，就像在命令式程式中一樣。除了在命令式程式中，這還不夠，因為函式依賴於成員變數、全域性變數和其他類的狀態（而這些類反過來又依賴於這些東西）。函式式程式中的函式只依賴於它的引數，而該資訊就在你的眼前！此外，在命令式程式中，檢查函式的返回值並不能讓你很好地判斷該函式是否正常執行。你需要追蹤其作用域之外的數十個物件，以驗證它是否執行了正確的操作。在函式式程式中，你只需要檢視返回值就行了！

遍歷堆疊，檢視傳遞給函式的引數及其返回值。只要返回值沒有意義，你就進入有問題的函式並遍歷它。你遞迴地重複這個過程，直到這個過程把你帶到錯誤的源頭！

併發性

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

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

併發性的故事並沒有就此結束。如果你的應用程式本質上是單執行緒的，編譯器仍然可以最佳化函式式程式以在多個 CPU 上執行。請檢視以下程式碼片段

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

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

熱程式碼部署

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

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

在函式式程式中，所有狀態都儲存在堆疊中，位於傳遞給函式的引數中。這使得熱部署變得非常容易！實際上，我們真正需要做的只是執行生產程式碼和新版本程式碼之間的差異，並部署新程式碼。其餘的可以透過語言工具自動完成！如果你認為這是科幻小說，那就再想想。Erlang 工程師多年來一直升級即時系統，而無需停止它們。

機器輔助證明和最佳化

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

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

高階函式

我記得學習上面概述的優點時，我曾想“這很好，但如果我必須用一種受限的語言程式設計，其中所有東西都是最終的，那將毫無用處”。這是一種誤解。在像 Java 這樣的命令式語言的環境中，使所有變數都成為最終的是受限的，但在函式式語言的環境中則不然。函式式語言提供了不同型別的抽象工具，使你忘記你曾經喜歡修改變數。其中一個工具是使用高階函式的能力。

在這些語言中，函式不同於 Java 或 C 中的函式。它是一個超集——它可以做 Java 函式可以做的所有事情，以及更多。我們在 C 中建立函式的方式相同

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

這與等效的 C 程式碼有不同的含義。讓我們擴充套件我們的 Java 編譯器以支援這種表示法。當我們輸入類似以下內容時，我們的編譯器會將其轉換為以下 Java 程式碼（不要忘記，所有內容都是最終的）

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

請注意，如果條件為真，則code永遠不會被求值。我們無法在嚴格的語言中再現這種行為，因為引數將在進入unless之前被求值。

無限資料結構

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

缺點

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

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

在惰性語言中，你無法保證第一行程式碼會在第二行程式碼之前執行！這意味著，如果惰性是絕對原則，我們就無法進行 I/O，也無法以任何有意義的方式使用原生函式（因為它們需要按順序呼叫，因為它們依賴於副作用），也無法與外部世界互動！如果我們引入強制程式碼按順序執行的原語，我們將失去以數學方式推理程式碼的能力（這將帶走函數語言程式設計的所有好處）。幸運的是，並非所有東西都丟失了。數學家們開始工作，開發了一些技巧來確保程式碼在函式式環境中按特定順序執行。因此我們真正獲得了兩全其美！這些技術包括延續、單子、唯一性型別。在這篇文章中，我們只討論延續。我們會留出單子和唯一性型別，在下次再討論。有趣的是，延續對除了強制特定求值順序之外的許多事情都有用。我們也會談到這一點。

延續

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

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

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。

這裡介紹了第一個技巧，它強制惰性語言按順序計算兩個表示式。考慮以下（熟悉的）I/O 程式碼

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 的情況下是下一個要呼叫的函式）。你可以將此物件儲存在變數中（或者在磁碟上）。當你選擇用這個延續物件“重新啟動”程式時，你將“轉換”到獲取延續物件時程式的狀態。這與切換回掛起的執行緒或從休眠狀態喚醒作業系統一樣，只是你可以一遍又一遍地執行。當作業系統醒來時，休眠資訊會被銷燬。如果它沒有被銷燬，你將能夠從同一個點醒來，就像回到過去一樣。你用延續就可以控制這一切！

在哪些情況下，延續（Continuation）是有用的？通常，當你在一個本質上無狀態的應用程式中模擬狀態以簡化你的工作時，延續就派上用場了。一個很好的延續應用例子是 Web 應用程式。微軟的 ASP.NET 竭盡全力嘗試模擬狀態，以便你能夠更輕鬆地編寫應用程式。如果 C# 支援延續，ASP.NET 中一半的複雜性就會消失——你只需儲存一個延續，並在使用者再次發起 Web 請求時重新啟動它。對於 Web 應用程式的程式設計師來說，不會有任何中斷——程式會直接從下一行開始執行！延續對於某些問題來說是一個非常有用的抽象。考慮到許多傳統的胖客戶端正在遷移到 Web，延續在未來會變得越來越重要。

模式匹配

模式匹配並不是一個新穎的功能。事實上，它與函數語言程式設計關係不大。它通常被歸功於函數語言程式設計的唯一原因是，函式式語言已經擁有模式匹配功能很長時間了，而現代命令式語言還沒有。

讓我們透過一個例子深入瞭解模式匹配。這是一個用 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，以便 incrementers 可以訪問它。此外，它儲存了多個副本，每個副本對應於每個 incrementer，即使它們應該在 makeIncrementer 返回時消失。這段程式碼編譯成什麼？閉包在幕後是如何工作的？幸運的是，我們有後臺通行證。

一點常識可以走很遠。第一個觀察是，區域性變數不再侷限於簡單的作用域規則，並且具有未定義的生存期。顯而易見的結論是，它們不再儲存在堆疊上——它們必須儲存在堆上⁸。然後，閉包就像我們之前討論過的函式一樣實現，只是它額外包含一個對周圍變數的引用

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

當閉包引用一個不在其區域性作用域內的變數時，它會諮詢這個對父作用域的引用。就是這樣！閉包將函式式和麵向物件的世界更緊密地聯絡在一起。每當你建立一個包含某些狀態並將其傳遞到其他地方的類時，想想閉包。閉包只是一個物件，它透過從作用域中獲取變數來動態建立“成員變數”，因此你不必這樣做！

接下來呢？

本文只是觸及了函數語言程式設計的皮毛。有時，一個小小的觸及可以發展成更大的東西，在我們這個例子中，這是一件好事。在未來，我計劃撰寫關於範疇論、單子、函式式資料結構、函式式語言中的型別系統、函式式併發、函式式資料庫以及更多內容的文章。如果我能寫（並在這個過程中學習）這些主題中的一半，我的生命將圓滿。與此同時，谷歌是我們的朋友。

評論？

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

¹當我在 2005 年秋季尋找工作時，我經常問這個問題。真是有趣，我收到了多少茫然的眼神。你可能會認為，以大約 30 萬美元的價格，這些人至少應該對他們可用的絕大多數工具有一個很好的理解。

²這個問題似乎很有爭議。物理學家和數學家被迫承認，宇宙中的一切是否都遵循可以用數學描述的定律，目前還不清楚。

³我一直討厭那些提供乾巴巴的年代、姓名和事件的史料。對我來說，歷史是關於改變世界的人的故事。它是關於他們行動背後的私人原因，以及他們影響數百萬靈魂的機制。出於這個原因，這個歷史部分是不完整的。只討論了非常相關的人和事件。

⁴當我學習函數語言程式設計時，我非常討厭“lambda”這個詞，因為我真的不明白它的真正含義。在這個上下文中，lambda 是一個函式，使用單個希臘字母只是在數學符號中更容易寫。每次你聽到關於函數語言程式設計的“lambda”時，就把它在你的腦海裡翻譯成“函式”。

⁵有趣的是，Java 字串本來就是不可變的。探索這種欺詐背後的原因很有趣，但這會讓我們偏離目標。

⁶大多數函式式語言編譯器會透過將遞迴函式轉換為迭代的替代方案（只要可能）來最佳化它們。這被稱為尾遞迴最佳化。

⁷反過來並不總是成立。雖然有時可以證明兩段程式碼是等價的，但在所有情況下都不行。

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

簡介