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

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

哈罗德·阿贝尔森（Harold Abelson）[美] 杰拉尔德•杰伊·萨斯曼（Gerald Jay Sussman） 著朱莉·萨斯曼（Julie Sussman）：哈罗德•阿贝尔森（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

　　第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语言的重要优点：只有为数不多的几种构造复合表达式的方式，几乎没有语法结构。所有的形式化性质都可以在一个小时里讲完，就像下象棋的规则一样。在很短时间之后，我们就可以不再去管语言的语法细节（因为这里根本就没有），而进入真正的问题—弄清楚我们需要计算什么，怎样将问题分解为一组可以控制的部分，如何对各个部分开展工作。Lisp的另一优势在于，与我们所知的任何其他语言相比，它可以支持（但并不是强制性的）更多以模块化的方式分解程序的大规模策略。我们可以做过程性抽象和数据抽象，可以通过高阶函数抓住公共的使用模式，可以用赋值和数据操作去模拟局部状态，可以利用流和延时求值连接起一个程序里的各个部分，可以很容易地实现嵌入性语言。所有这些都融合在一个交互式的环境里，带有对递增式程序设计、构造、测试和排除错误的绝佳支持功能。我们要感谢一代又一代的Lisp大师，从John McCarthy开始，是他们打造了这样一个优美的、具有空前威力的好工具。
　　作为我们所用的Lisp方言，Scheme试图将Lisp和Algol的威力和优雅集成到一起。我们从Lisp那里取来了元语言的威力—简单的语法形式、程序与数据对象的统一表示，以及带有废料收集的堆分配数据。我们从Algol那里取来了词法作用域和块结构，这是来自当年参加Algol委员会的程序设计语言先驱者的礼物。这些先驱者包括丘奇（Alonzo Church）、罗塞尔（Barkley Rosser）、克里尼（Stephen Kleene）和库里（Haskell Curry）。我们想特别感谢John Reynolds和 Peter Landin对丘奇的lambda演算与程序设计语言的结构之间关系的真知灼见。我们也感谢那些数学家们，他们在计算机出现之前，就已经在这一领域中探索了许多年。

　　“每一位严肃的计算机科学家都应该阅读这本书。本书清晰、简洁并充满智慧，我们强烈推荐本书，它适合所有希望深刻理解计算机科学的人们。”
　　——Mitchell Wand，《美国科学家》杂志
　　本书第1版于1984年出版，源于美国麻省理工学院 (MIT) 多年使用的一本教材，1996年修订为第2版。在过去的30多年里，本书对于计算机科学的教育计划产生了深刻的影响。
　　第2版中大部分主要程序设计系统都重新修改并做过测试，包括各种解释器和编译器。作者根据多年的教学实践，还对许多其他细节做了相应的修改。
　　本书自出版以来，已被世界上100多所高等院校采纳为教材，其中包括斯坦福大学、普林斯顿大学、牛津大学、东京大学等。