01 / 導讀
導讀
引用
Abelson, H., & Sussman, G. J., with Sussman, J. (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press. Free official edition: https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/index.html
章節概要
全書共五章，每章圍繞一種控制複雜性的手段：過程、資料、狀態與流、新語言以及機器。作者順帶講授 Scheme，理由是 Lisp 方言幾乎沒有語法，幾天即可學會。第一版序言把目標描述為：教授控制大型系統思維複雜性的技術，而不是某種語言的語法或巧妙的演算法。
第1章：用過程構造抽象
1.1 節介紹表示式、命名與環境、組合式的求值、複合過程、代換模型、條件表示式、用牛頓法求平方根，以及作為黑箱抽象的過程。1.2 節考察過程所產生的計算過程：線性遞迴與迭代、樹形遞迴、增長的階、求冪、最大公約數和素數檢測。1.3 節通過高階過程提升層次：過程作為引數、lambda、作為一般性方法的過程（不動點、牛頓法）以及作為返回值的過程。
第2章：用資料構造抽象
第2章從過程轉向複合資料。2.1 節通過有理數算術、抽象屏障、「資料意味著什麼」的問題以及區間算術練習來發展資料抽象。2.2 節講序列、層次結構與閉包性質、作為約定介面的序列，以及一種圖形語言。2.3 節引入符號資料：引號、符號求導、集合和霍夫曼編碼樹。2.4、2.5 節討論多重表示、帶標記資料、資料導向的程式設計和通用型操作，最後以符號代數收尾。
第3章：模組化、物件和狀態
本章對比組織程式的兩種方式：圍繞隨時間變化的物件，以及圍繞資訊流。3.1 節引入賦值與區域性狀態，並權衡其好處與代價。3.2 節用求值的環境模型取代代換模型。3.3 節為可變資料建模（表、佇列、表格），並討論數位電路模擬器和約束傳播。3.4 節提出並行及其控制機制。3.5 節講述作為延遲表的流、無窮流和延遲求值，並比較函式式程式與物件的模組性。
第4章：元語言抽象
本章的前提是，求值器不過是另一個程式。4.1 節構造元迴圈求值器，包括求值核心、表示式的表示、將其作為程式執行，以及把語法分析與執行分離。4.2 節將其變化為惰性求值的直譯器，對比正則序與應用序。4.3 節加入帶 amb 與搜尋的非確定性計算。4.4 節是邏輯程式設計的查詢系統，包括它是否就是數理邏輯的問題以及一種實現。
第5章：暫存器機器裡的計算
最後一章說明元迴圈求值器從宿主繼承而來的控制機制。5.1 節設計暫存器機器，並用棧實現遞迴。5.2 節構造暫存器機器模擬器。5.3 節講作為向量的記憶體和垃圾回收。5.4 節給出顯式控制求值器，包括尾遞迴。5.5 節描述從 Scheme 到暫存器機器程式碼的編譯器。
核心概念
第1章：過程與計算過程
- 代換模型：推演過程應用如何求值的一種方式。
- 遞迴與迭代的計算過程：遞迴過程既可產生遞迴的，也可產生迭代的計算過程，其空間和時間增長各不相同。
- 高階過程：以過程為引數或返回過程的過程。
第2章：資料抽象
- 抽象屏障：把資料型別的使用與其表示分隔開的介面。
- 閉包性質：組合資料的方法，其結果仍可再次用同一方法組合。
- 資料導向的程式設計：按型別標記分派，使新的表示可以在不修改已有程式碼的情況下加入。
第3章：狀態與流
- 區域性狀態與賦值：會變化的物件，以及由此造成的代換模型失效。
- 環境模型：以框架和約束解釋帶賦值的求值。
- 流：延遲表，使程式可以把序列作為整體處理。
第4章：求值器
- 元迴圈求值器：用某語言寫成的該語言的直譯器。
- 惰性求值與
amb：改變表示式求值時機的求值器變體。 - 查詢系統：以模式匹配和合一作為計算模型。
第5章：機器
- 暫存器機器：帶暫存器和棧、按步驟執行的機器。
- 顯式控制求值器與編譯器：在機器層面表達的求值器及其編譯。
評析
優點
- 清晰統一的主旨。 全書以抽象、約定介面和新語言來控制複雜性為主線，每一章都擴充套件一種語言或模型。
- 以少數要素達到深度。 由於 Scheme 幾乎沒有語法，篇幅用在環境、流、求值器和編譯等思想上。讀者要親自實現求值器、查詢系統和編譯器，而不只是閱讀。
- 精心修訂。 第二版重新設計了主要系統（通用算術、直譯器、暫存器機器模擬器和編譯器），重寫了程式碼使其可在任何符合 IEEE 標準的 Scheme 中執行，並新增了並行與非確定性的章節。
- 習題與配套材料。 正文配有大量習題，書的網站上還有書中程式碼、MIT 的示例作業、教師手冊和 Scheme 實現。
- 開放許可。 全文以知識共享署名-相同方式共享 4.0 許可免費提供，並帶有連結式目錄。
侷限
- 對初學者要求高。 第一版序言把本書描述為 MIT 的入門課程，是電子工程與電腦科學專業共同核心課程的四分之一。第3–5章推進很快，並且要求具備大學一年級數學基礎，還要為習題投入時間。
- 一學期無法講完。 第二版序言說明全書無法在一個學期內講完；作者自己常跳過邏輯程式設計（4.4）、模擬器的實現（5.2）和大部分編譯器內容（5.5）。
- 以 Scheme 為中心。 本書不教授業界主流語言，暫存器機器部分使用的是書中自己的暫存器機器語言，而非真實指令集。
- 版本較舊。 第二版出版於 1996 年，勘誤頁最後更新於 1999 年。
在課程中的定位
這是入門程式設計書架上要求高、重思想的一端。《How to Design Programs》同樣免費並使用 Lisp 家族的語言，但它為初學者建立了循序漸進的設計方法，適合作為第一門課；SICP 更適合作為第二遍，或已經會程式設計的讀者。《Think Python》和《Python Crash Course》是針對一門流行語言的平易、實用的入門書；《Introduction to Computation and Programming Using Python》是以 Python 為載體的計算問題求解課程；《The C Programming Language》是講底層語言的簡短經典。SICP 教的與其說是一門語言，不如說是思考程式的方式；需要同時掌握主流語言時，其他幾本是很好的搭配。
如何使用本書
本書適合有大學一年級數學基礎、能夠為習題投入時間且有動力的讀者。請安裝一個 Scheme（書的網站列出了 MIT Scheme 等），並執行書中的程式碼。
實用安排：
- 核心： 第1、2章全部，然後是 3.1–3.3 節和 3.5 節（狀態、環境模型和流），以及 4.1、4.2 節（元迴圈求值器和惰性求值器）。
- 選讀： 3.4 節（並行）、4.3 節（
amb）、4.4 節（邏輯程式設計）以及整個第5章，作者自己也是有選擇地講授；如想從機器層面理解遞迴，可先讀 5.1 和 5.4 節。 - 習題： 每節讀完先做習題再繼續，尤其是第2章的資料抽象習題和第4章的直譯器習題。
如想先少接觸理論，可以先讀一本更平易的、基於 Scheme 的入門書，之後再回到第1章。
版本與來源
本導讀依據第二版（MIT Press，1996），所讀為 MIT Press 官方 SICP 網站上的 HTML 版本，該站宣告全文以知識共享署名-相同方式共享 4.0 許可釋出。內容基於前言、序言、完整目錄，以及五章的導言和各節結構，並參考了配套網站對輔助材料的說明。