计算机程序的构造和解释（原书第2版）典藏版

本书曾是美国麻省理工学院计算机科学专业的入门课程教材之一， 从理论上讲解计算机程序的创建、 执行和研究。 主要内容包括：构造过程抽象，构造数据抽象，模块化、 对象和状态，元语言抽象，寄存器机器里的计算等。

哈罗德•阿贝尔森（Harold Abelson）是MIT 1992年度MacVicar Faculty Fellow。在MIT电子工程和计算机科学系工作，得到过重要的计算机科学教育奖——IEEE计算机学会的Booth奖。
杰拉尔德•杰伊•萨斯曼（Gerald Jay Sussman）是Matsushita电子工程教授。在MIT电子工程和计算机科学系工作，得到过重要的计算机科学教育奖——ACM的Karlstrom奖。
朱莉•萨斯曼（Julie Sussman）是作家和编辑，同时使用自然语言和计算机语言写作。

出版者的话
序
第2版前言
第1版前言
致谢
第1章 构造过程抽象1
1.1 程序设计的基本元素3
1.1.1 表达式3
1.1.2 命名和环境5
1.1.3 组合式的求值6
1.1.4 复合过程7
1.1.5 过程应用的代换模型9
1.1.6 条件表达式和谓词11
1.1.7 实例：采用牛顿法求平方根14
1.1.8 过程作为黑箱抽象17
1.2 过程及其产生的计算20
1.2.1 线性的递归和迭代21
1.2.2 树形递归24
1.2.3 增长的阶28
1.2.4 求幂29
1.2.5 最大公约数32
1.2.6 实例：素数检测33
1.3 用高阶函数做抽象37
1.3.1 过程作为参数37
1.3.2 用lambda构造过程41
1.3.3 过程作为一般性的方法44
1.3.4 过程作为返回值48
第2章 构造数据抽象53
2.1 数据抽象导引55
2.1.1 实例：有理数的算术运算55
2.1.2 抽象屏障58
2.1.3 数据意味着什么60
2.1.4 扩展练习：区间算术62
2.2 层次性数据和闭包性质65
2.2.1 序列的表示66
2.2.2 层次性结构72
2.2.3 序列作为一种约定的界面76
2.2.4 实例：一个图形语言86
2.3 符号数据96
2.3.1 引号96
2.3.2 实例：符号求导99
2.3.3 实例：集合的表示103
2.3.4 实例：Huffman编码树109
2.4 抽象数据的多重表示115
2.4.1 复数的表示116
2.4.2 带标志数据119
2.4.3 数据导向的程序设计和可加性122
2.5 带有通用型操作的系统128
2.5.1 通用型算术运算129
2.5.2 不同类型数据的组合132
2.5.3 实例：符号代数138
第3章 模块化、对象和状态149
3.1 赋值和局部状态149
3.1.1 局部状态变量150
3.1.2 引进赋值带来的利益154
3.1.3 引进赋值的代价157
3.2 求值的环境模型162
3.2.1 求值规则163
3.2.2 简单过程的应用165
3.2.3 将框架看作局部状态的展台167
3.2.4 内部定义171
3.3 用变动数据做模拟173
3.3.1 变动的表结构173
3.3.2 队列的表示180
3.3.3 表格的表示183
3.3.4 数字电路的模拟器188
3.3.5 约束的传播198
3.4 并发：时间是一个本质问题206
3.4.1 并发系统中时间的性质207
3.4.2 控制并发的机制210
3.5 流220
3.5.1 流作为延时的表220
3.5.2 无穷流226
3.5.3 流计算模式的使用232
3.5.4 流和延时求值241
3.5.5 函数式程序的模块化和对象的
模块化245
第4章 元语言抽象249
4.1 元循环求值器251
4.1.1 求值器的内核252
4.1.2 表达式的表示255
4.1.3 求值器数据结构260
4.1.4 作为程序运行求值器264
4.1.5 将数据作为程序266
4.1.6 内部定义269
4.1.7 将语法分析与执行分离273
4.2 Scheme的变形—惰性求值276
4.2.1 正则序和应用序277
4.2.2 一个采用惰性求值的解释器278
4.2.3 将流作为惰性的表284
4.3 Scheme的变形—非确定性计算286
4.3.1 amb和搜索287
4.3.2 非确定性程序的实例290
4.3.3 实现amb求值器296
4.4 逻辑程序设计304
4.4.1 演绎信息检索306
4.4.2 查询系统如何工作315
4.4.3 逻辑程序设计是数理逻辑吗321
4.4.4 查询系统的实现324
第5章 寄存器机器里的计算343
5.1 寄存器机器的设计344
5.1.1 一种描述寄存器机器的语言346
5.1.2 机器设计的抽象348
5.1.3 子程序351
5.1.4 采用堆栈实现递归354
5.1.5 指令总结358
5.2 一个寄存器机器模拟器359
5.2.1 机器模型360
5.2.2 汇编程序364
5.2.3 为指令生成执行过程366
5.2.4 监视机器执行372
5.3 存储分配和废料收集374
5.3.1 将存储看作向量374
5.3.2 维持一种无穷存储的假象378
5.4 显式控制的求值器383
5.4.1 显式控制求值器的内核384
5.4.2 序列的求值和尾递归388
5.4.3 条件、赋值和定义391
5.4.4 求值器的运行393
5.5 编译397
5.5.1 编译器的结构399
5.5.2 表达式的编译402
5.5.3 组合式的编译407
5.5.4 指令序列的组合412
5.5.5 编译代码的实例415
5.5.6 词法地址422
5.5.7 编译代码与求值器的互连425
参考文献431
练习表437
索引439

第2版前言
软件很可能确实与其他任何东西都不同，它的本意就是被抛弃：这一观点就是总将它看作一个肥皂泡吗？
—Alan J. Perlis

自1980年以来，本书的材料就一直在MIT作为计算机科学入门课程的基础。在本书第1版出版之前，我们已经用这一材料教了4年课，而到第2版出版，时间又过去了12年。我们非常高兴地看到这一工作得到广泛认可，并被结合到其他一些教材中。我们已经看到我们的学生掌握了本书中的思想和程序，并将它们构筑到新的计算机系统或者语言的核心里—我们的学生已经变成了我们的创造者。我们非常幸运能有如此有能力的学生和如此有建树的创造者。
在准备这一新版本的过程中，我们采纳了成百条澄清性建议，它们来自我们自己的教学经验，也来自MIT和其他地方的同行们的评述。我们重新设计了本书里大部分主要程序设计系统，包括通用型算术系统、解释器、寄存器机器模拟器和编译器，也重写了所有的程序实例，以保证任何符合IEEE的Scheme标准（IEEE 1990）的Scheme实现都能运行这些代码。
这一版本中强调了几个新问题，其中最重要的是计算模型里对于时间的处理所起的中心作用：带有状态的对象、并发程序设计、函数式程序设计、惰性求值和非确定性程序设计。这里为并发和非确定性新增加了几节，我们也设法将这一论题集成到整本书里，贯穿始终。
本书第1版基本上是按照我们在MIT一学期课程的教学大纲撰写的。第2版中由于有了增加的这些新材料，已经不可能在一个学期里覆盖所有内容了，所以教师需要从中做一些选择。在我们自己的教学里，有时会跳过有关逻辑程序设计的一节（4.4节）；让学生使用寄存器机器模拟器，但不去讨论它的实现（5.2节）；对于编译器则只给出粗略的概述（5.5节）。即便如此，这仍然是一门内容非常多的课程。一些教师可能希望只覆盖前面的三章或者四章，而将其他内容留给后续课程。

第1版前言
一台计算机就像是一把小提琴。你可以想象一个新手试了一个音符后丢掉了它。后来他说，听起来真难听。我们已经从大众和我们的大部分计算机科学家那里反复听到这种说法。他们说，计算机程序对个别具体用途而言确实是好东西，但它们太缺乏弹性。一把小提琴或者一台打字机也同样缺乏弹性，那是在你学会了如何去使用它们之前。
—Marvin Minsky，“为什么说程序设计很容易成为一种媒介，
用于表述理解浮浅、草率而就的思想”

本书是麻省理工学院（MIT）计算机科学的入门教材。在MIT主修电子工程或者计算机科学的所有学生都必须学这门课，作为“公共核心课程计划”的四分之一。该计划还包含两个关于电路和线性系统的科目，以及一个关于数字系统设计的科目。我们从1978年开始涉足这些科目的开发，从1980年秋季以后，我们就一直按照现在这种形式教授这门课程，每年600到700个学生。大部分学生此前没有或者很少有计算方面的正式训练，虽然许多人玩过计算机，也有少数人有丰富的程序设计或者硬件设计经验。
我们所设计的这门计算机科学入门课程主要考虑了两个方面。首先，我们希望建立起一种认识：计算机语言并不仅仅是一种让计算机去执行操作的方式，更重要的，它是一种表述有关方法学的思想的新颖的形式化媒介。因此，程序必须写得能够供人们阅读，偶尔地去供计算机执行。其次，我们相信，在这一层次的课程里，最基本的材料并不是特定程序设计语言的语法，不是高效完成某种功能的巧妙算法，也不是算法的数学分析或者计算的本质基础，而是一些能够控制大型软件系统的复杂性的技术。
我们的目标是，完成了这一科目的学生能对程序设计的风格要素有一种很好的审美观。他们应该掌握了控制大型系统的复杂性的主要技术。他们应该能够去读50页长的程序，只要该程序是以一种值得模仿的形式写出来的。他们应该知道在什么时候哪些东西不需要去读，哪些东西不需要去理解。他们应该很有把握地去修改一个程序，同时又能保持原来作者的精神和风格。
这些技能并不仅仅适用于计算机程序设计。我们所教授和提炼出来的这些技术，对于所有的工程设计都是通用的。我们在适当的时候隐藏起一些细节，通过创建抽象去控制复杂性。我们通过建立约定的界面，以一种“混合与匹配”的方式组合起一些标准的、已经很好理解的片段去控制复杂性。我们通过建立一些新的语言去描述各种设计，每种语言强调设计中的一个特定方面并降低其他方面的重要性，以控制复杂性。
设计这门课程的基础是我们的一种信念—“计算机科学”并不是一种科学，而且其重要性也与计算机本身并无太大关系。计算机革命是关于我们如何去思考，以及如何去表达自己的思考的。在这个变化里，最基本的东西就是出现了一种或许最好称为过程性认识论的现象—如何从命令式的观点去研究知识的结构，这一观点与经典数学领域中所采用的更具说明性的观点是完全不同的。数学为精确处理“是什么”提供了一种框架，而计算则为精确处理“怎样做”提供了一种框架。
在教授这里的材料时，我们采用的是Lisp语言的一种方言。我们绝没有形式化地教授这一语言，因为完全不必那样做。我们只是使用它，学生可以在几天之内就学会它。这也是类Lisp语言的重要优