计算机程序的构造和解释

引用

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 许可发布。内容基于前言、序言、完整目录，以及五章的导言和各节结构，并参考了配套网站对辅助材料的说明。