书 · 1985 · 哈罗德(哈尔)·阿贝尔森、杰拉尔德·杰伊·萨斯曼,朱莉·萨斯曼(合著)

《计算机程序的构造和解释》

计算机与 AI书单第 2 名

一句话结论

这本书把编程当成一门管理复杂性的思维训练,用很少的几种构件,从过程、数据、状态一路搭到“自己写一个解释器”。

值不值得读完整本？

值得,但不必按顺序啃完整本。前两章加第三章的核心部分和第四章开头,就是这本书的精华,其余可按兴趣取舍。书里的思想比语言本身持久,但真正的收获来自做习题,光读正文收获有限。

必读:第 1 章(全章)、第 2 章的 2.1 到 2.2 和 2.4 到 2.5、第 3 章的 3.1 到 3.2 与 3.5 流、第 4 章的 4.1 元循环求值器。这些是全书的主干。
可略读:2.3 符号数据、3.3 可变数据建模、3.4 并发、4.3 非确定性计算、4.4 逻辑程序设计。想理解“语言可以被设计”再回头细看。
第 5 章(寄存器机、垃圾回收、编译)是把第 4 章的求值器落到机器层面,对多数读者可以跳过。
一定要配合练习:不做习题,后半部分基本读不进去。1986 年的配套视频讲座和全文都能免费看到,可以边看边做。
如果是零基础又只想学实用编程,先读别的入门书再回头读它更合适。

核心观点

1. 编程的核心是控制复杂性,靠“基本表达式、组合、抽象”三件事

一门编程语言要有三种机制:基本表达式、把简单东西组合成复杂东西的手段、给组合物命名并当成整体使用的抽象手段。作者还强调,程序首先是写给人读的,机器执行只是顺带。

为什么：人脑能同时处理的细节有限,所以大系统只能靠“分层”来驾驭。给一个复杂结构起名字后,使用它的人只需关心它做什么,不必关心它怎么做,这样每一层的推理量都很小。组合手段让小零件能搭成大零件,抽象手段让搭好的大零件又能当成新的“基本零件”继续往上搭。这个循环不断重复,就让系统可以任意增长而不超出人的理解力。反过来,如果程序主要为机器写,可读性就被牺牲,复杂度会在没人看得懂的地方积累。

2. 过程的写法不等于计算过程的形状:要能预见递归与迭代的代价

一个过程(函数)的文本是对计算过程如何演化的局部规则。同样写成“递归函数”,产生的可能是不断展开再收缩的递归过程,也可能是状态固定、可以一直循环下去的迭代过程。

为什么：写程序时我们只写局部规则,运行时却会长出全局的结构,好的程序员要能在脑子里把局部规则“推演”成整体形状。形状决定时间和空间的增长阶:线性递归会占用与输入成正比的栈,迭代过程只需常数空间,树形递归如果重复计算会出现指数级膨胀。作者认为理解这一点是区分“能运行”和“写得好”的门槛。而且迭代过程可以用递归写法表达,只要语言实现做了尾调用优化,就不必引入专门的循环语法。

3. 过程是一等公民:高阶过程让我们抽象“计算的模式”

过程可以作为参数传给别的过程,也可以作为返回值,还能存进数据结构。有了这种能力,不只是数值可以被抽象,连“求和”“找不动点”“求导”这样的计算套路也能被抽象成一个通用工具。

为什么：如果过程只能接受数值,那么两个形状相似的函数(比如求自然数和与求平方和)只能各写一遍,重复就成了错误和维护的来源。把“怎么累加”这一部分提取出来,把“加什么”作为参数传进去,就能把共性写一次、用在各处。再配合“闭包性质”,即用某种方式组合出来的结果仍可以再被同样的方式组合,结构就能层层嵌套而不必另立规则。作者认为这是语言表达力的核心来源之一。

4. 数据抽象:用构造函数和选择函数筑起抽象屏障

程序使用数据时,应只通过一组构造函数和选择函数,而不去碰内部表示。更进一步,同一种“数据”可以有多种内部表示,通过带类型标签的通用操作让它们共存。

为什么：表示方式迟早要变,比如为了效率或需求变化。如果上层代码直接依赖内部细节,那么改一处就要改处处;抽象屏障把变化挡在一层之内,波及面就被限制住了。再往前一步,当系统要接纳多个团队、多种表示时,不可能强行统一,于是靠类型标签加分派,让各自的表示共存,新增类型也不改旧代码。作者用的是同一个逻辑:让系统可演化,比让它在某一刻最优更重要。

5. 一旦引入赋值,时间进入程序,代换模型失效

第 3 章讨论带状态的对象。作者指出,引入赋值(set!)后,原本“表达式等于它的值”的简单代换模型不再成立,必须改用环境模型才能解释程序行为。

为什么：在纯函数式的世界里,相同表达式在任何时候求值结果都一样,所以可以放心地把它替换成它的值来推理。赋值让同一个表达式在不同时刻代表不同的值,于是推理必须带上“当前状态”和“发生顺序”,也就是时间。作者并不否定状态,因为用对象建模真实世界(如银行账户)很自然;他是想让读者清楚看到这笔代价,并提供另一条路:流。流把“随时间变化”变成“值的序列”,把时间推迟到程序之外,从而在不使用赋值的情况下建模变化。

6. 元语言抽象:解释器本身就是一个程序,语言是可以被设计的

当现有语言不足以简洁地描述某类问题,就为这类问题设计一门新语言。第 4 章让读者用 Lisp 写出 Lisp 的求值器,并改造它得到惰性求值、非确定性计算和逻辑程序设计。

为什么：解释器本身不过是一段读入程序、产出结果的程序,所以人人都能写。一旦读者亲手写过一遍“求值”和“应用”的交替,就能看穿语言的神秘感,并获得设计新语言规则的能力。因为程序与它描述的对象在 Lisp 里用同样的数据结构表示,改造求值器只需几十行。按作者的看法,许多大型软件其实都是在不自觉地实现某种小语言,不如自觉地做。这一章也是全书把前面所有抽象思想收束在一起的地方。

反对意见

选 Scheme 做载体不利于推理和教学(Philip Wadler)

Wadler 在 1987 年的《A critique of Abelson and Sussman, or why calculating is better than scheming》中认为,Scheme 缺少模式匹配、没有代数数据类型、过度依赖 cons 对子来构造所有数据,而且默认采用严格求值。这些都会让程序的推理变得笨拙,不如他所推崇的惰性纯函数式语言(Miranda)那样能直接用等式演算。

书里展示了漂亮的程序,却没教新手系统地设计程序(Felleisen 等人)

Felleisen、Findler、Flatt、Krishnamurthi 在 2004 年的《The Structure and Interpretation of the Computer Science Curriculum》中承认 SICP 用 Scheme 和函数式编程讲了重要思想,但认为用它开出来的课很快消失,原因包括这本书自身的不足和 Scheme 的一些毛病。他们另写《How to Design Programs》,主张用“设计方法”(从数据定义推出函数结构)来系统地教初学者设计程序。

今天的工程不再是“自底向上弄懂一切”,而是“摆弄库”(萨斯曼本人)

萨斯曼在回答 MIT 为什么停开 6.001 时说,1980 年的工程师面对的是自己能完全理解的小系统,而现在大家要为并不完全了解的硬件写代码,环境由庞大的库构成,学生大部分时间在读手册、把东西拼起来。他把这称为更像科学实验的“摆弄”式编程,所以新课转向机器人,让学生面对不理想的真实世界。注意这是作者自己对 SICP 适用范围的修正,不是外人的批评。

程序应当被证明,而不是被试出来(戴克斯特拉)

Dijkstra 在 1988 年的《On the cruelty of really teaching computing science》(EWD1036)里主张,学生应当学会对程序做形式推理,程序员的主要任务是给出程序满足规格的形式证明,而不是靠运行来检验。这篇文章没有点名 SICP,但它代表了一条与 SICP “通过运行和代换模型来理解程序”截然不同的教学路线。