目 錄

譯者序推薦序前言
致謝
第 1 章 自然和設計中的靈活性 1
1.1 計算體繫結構 3
1.2 靈活的智能組件 4
1.3 冗餘和簡並 7
1.4 探索行為 9
1.5 靈活性的成本 10
第 2 章 領域專用語言 13
2.1 組合器 13
2.1.1 函數組合器 14
2.1.2 組合器和形體構造 24
2.2 正則表達式 25
2.2.1 一種正則表達式組合語言 26
2.2.2 翻譯器的實現 26
2.3 包裝器 32
2.3.1 定制化包裝器 34
2.3.2 實現定制器 35
2.3.3 適配器 36
2.4 抽像領域模型 37
2.4.1 單一化實現 38
2.4.2 領域模型分解 41
2.5 小結 46
第 3 章 算 術 主題 48
3.1 組合算術 48

XIII

3.1.1 一個簡單的 ODE 積分器 48
3.1.2 調整算術運算符 50
3.1.3 組合運算 52
3.1.4 算術函數 57
3.1.5 組合器問題 60
3.2 可擴展的通用程序 63
3.2.1 通用運算 65
3.2.2 構建取決於順序 68
3.2.3 實現通用程序 70
3.3 示例：自動微分 75
3.3.1 自動微分的工作原理 77
3.3.2函數的導數 81
3.3.3 一些技術細節 82
3.3.4 微分參數的文字函數 90
3.4 高效的通用程序 91
3.4.1 trie 91
3.4.2 緩存 96
3.5 高效的用戶自定義類型 97
3.5.1 謂詞的類型 97
3.5.2 謂詞之間的關繫 99
3.5.3 謂詞調度關鍵字 99
3.5.4 示例：冒險遊戲 101
3.6 小結 113
第 4 章 模式匹配 115
4.1 模式 115
4.2 項重寫 117
4.2.1 代數中的段變量 118
4.2.2 規則繫統的實現 120
4.2.3 旁白：魔術宏 122
4.2.4 有向模式調用 123
4.3 匹配器設計 124
4.3.1 編譯模式 130
4.3.2 匹配變量限制 132
4.4 合一匹配 135

XIV

4.4.1 合一的工作原理 137
4.4.2 應用：類型推斷 143
4.4.3 類型推斷的工作原理 144
4.4.4 添加段變量— 一個實驗 150
4.5 圖上的模式匹配 155
4.5.1 將列表表示為圖 155
4.5.2 實現圖 156
4.5.3 圖上的匹配 158
4.5.4 棋盤和可交換圖形視圖 160
4.5.5 棋步 164
4.5.6 實現圖形匹配 167
4.6 小結 172
第 5 章 評 估 174
5.1 通用 eval/apply 解釋器 174
5.1.1 eval 175
5.1.2 apply 182
5.2 具有非嚴格參數的程序 187
5.3 編譯為可執行程序 194
5.4 探索行為 202
5.4.1 amb 203
5.4.2 實現 amb 205
5.5 探索潛在連續 210
5.5.1 作為非本地出口的連續 213
5.5.2 控制權的非本地轉移 214
5.5.3 從連續到 amb 216
5.6 能力與責任 223
第 6 章 分 層 225
6.1 使用分層 225
6.2 分層的實現 226
6.2.1 分層數據 227
6.2.2 分層程序 229
6.3 分層算法 232
6.3.1 單位運算 233

XV

6.4 使用依賴項注釋值 237
6.4.1 支持層 239
6.4.2 提供正當性 243
6.5 分層的前景 243
第 7 章 傳 播 245
7.1 示例：到恆星的距離 246
7.2 傳播機制 257
7.2. 257
7.2.2 傳播器 259
7.3 多種不同的世界觀 261
7.4 合並值 263
7.4.1 合並基值 263
7.4.2 合並支持值 264
7.4.3 合並值集 265
7.5 搜索可能的世界 266
7.5.1 依賴定向回溯 268
7.5.2 解決組合問題 273
7.6 傳播導致簡並 277
後 記 279 附錄 A 支持軟件 281 附錄 B Scheme 編程語言 283 參考文獻 297

前 言

我們都曾花費太多的時間試圖改造一段舊的代碼，以便能以一種編寫時沒有意識到的方式使用它。這是一種可怕的時間和精力上的浪費。不幸的是，對我們而言，要為一個非常具體的目的寫出特別好用的代碼，並且很少有可重復使用的部分，是一件很有壓力的事情。但我們認為，這並不是必要的。
我們很難建立一個繫統，使其在比設計者預期的更大範圍內具有可接受行為。最好的繫統是可進化的，隻需稍加修改就能適應新的環境。我們怎樣纔能設計出具有這種靈活性的繫統呢？
如果我們為程序添加一個新的功能時所要做的就隻是添加一些代碼，而不改變現有的代碼庫，那就太棒了。我們通常可以通過在構建代碼庫時使用特定組織原理，同時加入適當的鉤子（hook）來實現這一目的。
對生物繫統的觀察告訴我們很多關於如何建立靈活和可進化繫統的知識。最初為支持符號人工智能而開發的技術通常被認為可以提高程序和其他工程繫統靈活性和適應性。相比之下，計算機科學的普遍做法是不鼓勵構建便於在新環境中使用的易於修改的繫統。
我們的編程經常把自己逼到死胡同裡，不得不花大力氣重構代碼以擺脫這些死胡同。現在，我們已經積累了足夠的經驗，可以識別、分離並展示我們發現的對構建大型繫統有效的策略和技術，這些策略和技術可以適應原始設計中沒有預料到的目的。在本書中，我們分享了多年編程經驗總結而成的一些成果。

關於本書
本書是為了在麻省理工學院教授計算機程序設計而編寫的。我們在多年前就開設了這門課，打算讓高年級本科生和研究生了解用於構建人工智能應用的核心程序的有效技術，如數學符號操作和基於規則的繫統。
我們希望學生能夠靈活地建立這些繫統，這樣就可以輕松地將這些繫統組合起來，從而形成更強大的繫統。我們還想讓學生了解依賴關繫，包括如何跟蹤它們以及如何利用它們來解釋和控制回溯。
雖然這門課過去和現在都很成功，但事實證明，一開始我們對這門課的理解並不像我們最初認為的那樣深入。因此，我們投入了大量的精力來推敲打磨，使我們的想法更加精確，並且意識到這些技術不僅可以用於人工智能應用。任何正在構建復雜繫

VIII

統（如計算機語言編譯器和集成開發環境）的人，都會從我們的經驗中受益。本書是由我們的課程中正在使用的講義以及問題集整理而成的。

主要內容
本書中的內容比一個學期課程所能涵蓋的知識更加豐富。因此，我們每次上課時都會挑選部分內容進行講解。第 1 章是對編程哲學的介紹。我們在自然和工程的大背景下提出了靈活性的概念，並試圖說明靈活性是與效率和正確性同樣重要的問題。在隨後的每一章中都介紹了一些技術，並通過一組練習來說明這些技術。這是本書的一個重要組織原則。
在第 2 章中，我們探討了用一些普遍適用的方法構建易於擴展的繫統。組織靈活繫統的一個強有力的方法是把它建成特定領域語言的集合體，每一種語言都適合輕松表達一個子繫統的構造。我們設計了開發特定領域語言的基本工具，展示了如何圍繞混合 - 匹配組件來組織子繫統，如何用組合器來靈活地組合它們，如何用包裝器來泛化組件，以及如何通過抽像出領域模型來簡化程序設計。
在第 3 章中，我們介紹了極其強大但有潛在危險的靈活性技術—謂詞調度的通用程序。我們從泛化算術以處理符號代數表達式開始，展示如何通過使用數據的類型標記使這種泛化變得高效。我們通過設計一個簡單但易於詳細說明的冒險遊戲來展示該技術的能力。
在第 4 章中，我們介紹了符號模式匹配，首先啟用了術語重寫繫統，然後通過合一展示了類型推理是如何輕松實現的。在這裡，我們遇到了由於段變量而需要進行回溯的問題。合一是我們看到表示和組合部分信息結構的力量的第一個地方。在本章的最後，我們將這個想法擴展到匹配一般的圖上。
在第 5 章中，我們探討了解釋和編譯的力量。我們認為，程序員應該知道如何擺脫他們必須使用的任何編程語言的束縛，為一種更適合表達當前問題的解決方案的語言制作一個解釋器。我們還展示了如何通過在解釋器 / 編譯器繫統中實現非確定性的
amb 來自然地納入回溯搜索，以及如何使用連續。
在第 6 章中，我們展示了如何構造分層數據和分層程序的繫統，其中每個數據項都可以數據進行注釋。底層數據的處數據的影響，處理底層數據的代碼甚至不知道或數據。數據是由它自己的程序處理的，有效地與數據並行。我們通過給數字量附加單位來說明這一點，並展示如何攜帶依賴性信息， 就像從原始來源得到的那樣給出數據的出處。
前面所述的一切都彙集在第 7 章，在這章我們引入了傳播，以擺脫計算機語言的面向表達式範式。在這章，我們有一個將模塊連接在一起的布線圖設想，允許靈活地納入部分信息的多個來源。使用分層數據來支持對依賴關繫的跟蹤，可以實現依賴定

IX

向回溯，從而大大減小大型復雜繫統的搜索空間。
本書可用於各種高年級課程，在隨後的所有章節中都使用了第 2 章介紹的組合器