全新计算机程序的构造和解释(原书第2版)(典藏版)

出版者的话序第2版前言版前言致谢章 构造过程抽象11.1 程序设计的基本元素31.1.1 表达式31.1.2 命名和环境51.1.3 组合式的求值61.1.4 复合过程71.1.5 过程应用的代换模型91.1.6 条件表达式和谓词111.1.7 实例：采用牛顿法求平方根141.1.8 过程作为黑箱抽象171.2 过程及其产生的计算201.2.1 线的递归和迭代211.2.2 树形递归241.. 增长的阶281.2.4 求幂291.2.5 优选公约数321.2.6 实例：素数检测331.3 用高阶函数做抽象371.3.1 过程作为参数371.3.2 用lambda构造过程411.3.3 过程作为一般的方法441.3.4 过程作为返回值48第2章 构造数据抽象532.1 数据抽象导引552.1.1 实例：有理数的算术运算552.1.2 抽象屏障582.1.3 数据意味着什么602.1.4 扩展练习：区间算术622.2 层次数据和闭包质652.2.1 序列的表示662.2.2 层次结构722.. 序列作为一种约定的界面762.2.4 实例：一个图形语言86. 符号数据96..1 引号96..2 实例：符号求导99.. 实例：集合的表示103..4 实例：Huffman编码树1092.4 抽象数据的多重表示1152.4.1 复数的表示1162.4.2 带标志数据1192.4.3 数据导向的程序设计和可加1222.5 带有通用型操作的系统1282.5.1 通用型算术运算1292.5.2 不同类型数据的组合1322.5.3 实例：符号代数138第3章 模块化、对象和状态1493.1 赋值和局部状态1493.1.1 局部状态变量1503.1.2 赋值带来的利益1543.1.3 赋值的代价1573.2 求值的环境模型16.2.1 求值规则1633.2.2 简单过程的应用1653.. 将框架看作局部状态的展台1673.2.4 内部定义1713.3 用变动数据做模拟1733.3.1 变动的表结构1733.3.2 队列的表示1803.3.3 表格的表示1833.3.4 数字电路的模拟器1883.3.5 约束的传播1983.4 并发：时间是一个本质问题2063.4.1 并发系统中时间的质2073.4.2 控制并发的机制2103.5 流2203.5.1 流作为的表2203.5.2 无穷流2263.5.3 流计算模式的使用2.5.4 流和求值2413.5.5 函数式程序的模块化和对象的模块化245第4章 元语言抽象2494.1 元循环求值器2514.1.1 求值器的内核2524.1.2 表达式的表示2554.1.3 求值器数据结构2604.1.4 作为程序运行求值器2644.1.5 将数据作为程序2664.1.6 内部定义2694.1.7 将语法分析与执行分离2734.2 Scheme的变形—惰求值2764.2.1 正则序和应用序2774.2.2 一个采用惰求值的解释器2784.. 将流作为惰的表2844.3 Scheme的变形—非确定计算2864.3.1 amb和搜索2874.3.2 非确定程序的实例2904.3.3 实现amb求值器2964.4 逻辑程序设计3044.4.1 演绎信息检索3064.4.2 查询系统如何工作3154.4.3 逻辑程序设是理逻辑吗3214.4.4 查询系统的实现324第5章 寄存器机器里的计算3435.1 寄存器机器的设计3445.1.1 一种描述寄存器机器的语言3465.1.2 机器设计的抽象3485.1.3 子程序3515.1.4 采用堆栈实现递归3545.1.5 指令总结3585.2 一个寄存器机器模拟器3595.2.1 机器模型3605.2.2 汇编程序3645.. 为指令生成执行过程3665.2.4 监视机器执行3725.3 存储分配和废料收集3745.3.1 将存储看作向量3745.3.2 维持一种无穷存储的象3785.4 显式控制的求值器3835.4.1 显式控制求值器的内核3845.4.2 序列的求值和尾递归3885.4.3 条件、赋值和定义3915.4.4 求值器的运行3935.5 编译3975.5.1 编译器的结构3995.5.2 表达式的编译4025.5.3 组合式的编译4075.5.4 指令序列的组合4125.5.5 编译代码的实例4155.5.6 词法地址4225.5.7 编译代码与求值器的互连425参考文献431练习表437索引439

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

第2版前言软件很可能确实与任何东西都不同，它的本意就是被抛弃：这一观点就是总将它看作一个肥皂泡吗？—Alan J. Perlis自1980年以来，本书的材料就一直在MIT作为计算机科学入门课程的基础。在本书版出版之前，我们已经用这一材料教了4年课，而到第2版出版，时间又过去了12年。我们很好高兴地看到这一工作得到广泛认可，并被结合到一些教材中。我们已经看到我们的学生掌握了本书中的思想和程序，并将它们构筑到新的计算机系统或者语言的核心里—我们的学生已经变成了我们的创造者。我们很好幸运能有如此有能力的学生和如此有建树的创造者。在准备这一新版本的过程中，我们采纳了成百条澄清建议，它们来自我们自己的教学经验，也来自MIT和地方的同行们的评述。我们重新设计了本书里大部分主要程序设计系统，包括通用型算术系统、解释器、寄存器机器模拟器和编译器，也重写了所有的程序实例，以保任何符合IEEE的Scheme标准（IEEE 1990）的Scheme实现都能运行这些代码。这一版本中强调了几个新问题，其中重要的是计算模型里对于时间的处理所起的中心作用：带有状态的对象、并发程序设计、函数式程序设计、惰求值和非确定程序设计。这里为并发和非确定新增加了几节，我们也设法将这一论题集成到整本书里，贯穿始终。本书版基本上是按照我们在MIT一学期课程的教学大纲撰写的。第2版中由于有了增加的这些新材料，已经不可能在一个学期里覆盖所有内容了，所以教师需要从中做一些选择。在我们自己的教学里，有时会跳过有关逻辑程序设计的一节（4.4节）；让学生使用寄存器机器模拟器，但不去讨论它的实现（5.2节）；对于编译器则只给出粗略的概述（5.5节）。即便如此，这仍然是一门内容很好多的课程。一些教师可能希望只覆盖前面的三章或者四章，而将内容留给后续课程。版前言一台计算机就像是一把小提琴。你可以想象一个新手试了一个音符后丢掉了它。后来他说，听起来真难听。我们已经从大众和我们的大部分计算机科学家那里反复听到这种说法。他们说，计算机程序对个别具体用途而言确实是好东西，但它们太缺乏弹。一把小提琴或者一台打字机也同样缺乏弹，那是在你学会了如何去使用它们之前。—Marvin Minsky，“为什么说程序设计很容易成为一种媒介，用于表述理解浮浅、草率而就的思想”本书是麻省理工学院（MIT）计算机科学的入门教材。在MIT主修工程或者计算机科学的所有学生都必须学这门课，作为“公共核心课程计划”的四分之一。该计划还包含两个关于电路和线系统的科目，以及一个关于数字系统设计的科目。我们从1978年开始涉足这些科目的开发，从1980年秋季以后，我们就一直按照现在这种形式教授这门课程，每年600到700个学生。大部分学生此前没有或者很少有计算方面的正式训练，虽然许多人玩过计算机，也有少数人有丰富的程序设计或者硬件设计经验。我们所设计的这门计算机科学入门课程主要考虑了两个方面。首先，我们希望建立起一种认识：计算机语言并不仅仅是一种让计算机去执行操作的方式，更重要的，它是一种表述有关方法学的思想的新颖的形式化媒介。因此，程序必须写得能够供人们阅读，偶尔地去供计算机执行。其次，我们相信，在这一层次的课程里，基本的材料并不是特定程序设计语言的语法，不是高效完成某种功能的巧妙算法，也不是算法的数学分析或者计算的本质基础，而是一些能够控制大型软件系统的复杂的技术。我们的目标是，完成了这一科目的学生能对程序设计的风格要素有一种很好的审美观。他们应该掌握了控制大型系统的复杂的主要技术。他们应该能够去读50页长的程序，只要该程序是以一种值得模仿的形式写出来的。他们应该知道在什么时候哪些东西不需要去读，哪些东西不需要去理解。他们应该很有把握地去修改一个程序，同时又能保持原来作者的精神和风格。这些技能并不仅仅适用于计算机程序设计。我们所教授和提炼出来的这些技术，对于所有的工程设计都是通用的。我们在适当的时候隐藏起一些细节，通过创建抽象去控制复杂。我们通过建立约定的界面，以一种“混合与匹配”的方式组合起一些标准的、已经很好理解的片段去控制复杂。我们通过建立一些新的语言去描述各种设计，每种语言强调设计中的一个特定方面并降低方面的重要，以控制复杂。设计这门课程的基础是我们的一种信念—“计算机科学”并不是一种科学，而且其重要也与计算机本身并无太大关系。计机革是关于我们如何去思考，以及如何去表达自己的思考的。在这个变化里，基本的东西就是出现了一种或许优选称为过程认识论的现象—如何从命令式的观点去研究知识的结构，这一观点与经典数学领域中所采用的更具说明的观点是接近不同的。数学为准确处理“是什么”提供了一种框架，而计算则为准确处理“怎样做”提供了一种框架。在教授这里的材料时，我们采用的是Lisp语言的一种方言。我们绝没有形式化地教授这一语言，因为接近不必那样做。我们只是使用它，学生可以在几天之内就学会它。这也是类Lisp语言的重要优