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

书籍
计算机书籍
　　 [style type="text/css"] [!-- .unnamed1 { font-size: 12px} --] [/style]    本书1984年出版，成型于美国麻省理工学院(mit)多年使用的一本教材，1996年修订为第2版。在过去的二十多年里，本书对于计算机科学的教育计划产生了深刻的影响。
　　 第2版中大部分重要程序设计系统都重新修改并做过测试，包括各种解释器和编译器。作者根据其后十余年的教学实践，还对其他许多细节做了相应的修改。
　　 本书自出版以来，世界各地已有100多所院校采用本书做教材，其中包括美国斯坦福大学、美国普林斯顿大学、英国牛津大学、日本东京大学等。
　　 相关网站有本书源代码及其他教辅资料，网址为：[a href="http://www-mitpress.mit.edu/sicp/"]www-mitpress．mit.edu／sicp／[/a]
　　
　　 作者简介：
　　 harold abelson是mit1992年度macvicarfacultyfellow。gerald jaysussman是matsushita电子工程教授。他们都在mit电子工程和计算机科学系工作．都得到过最重要的计算机科学教育奖：如abelson得到了ieee计算机学会的booth奖。sussman得到了acm的karlstrom奖。
　　 julie sussman是作家和编辑，同时使用自然语言和计算机语言写作。
　　 每一位严肃的计算机科学家都应该阅读这本书。由于本书清晰、简洁和富于才智，我们强烈推荐本书，它适合所有希望深刻理解计算机科学的人们。
　　 ——mitchell wand[dr]
　　 《美国科学家》杂志
　　 [font color="#ff0000"]译者的相关作品：
　　 [/font]
　　 [table width="398" border="0" align="center" cellpadding="5" cellspacing="5" bgcolor="#ffffff"] [tr bgcolor="#dec4fb"] [td width="271" class="unnamed1" height="14" bgcolor="#dec4fb"][a href="http://www.china-pub.com/computers/common/info.asp?id=6591" target="_blank"]《c++程序设计语言（特别版）》[/a] [/td] [td width="219" class="unnamed1" height="14"] [a href="http://www.china-pub.com/computers/common/info.asp?id=5451" target="_blank"]《程序设计语言：概念......》[/a] [/td] [/tr] [tr bgcolor="#dec4fb"] [td width="271" class="unnamed1" height="10"] [a href="http://www.china-pub.com/computers/common/info.asp?id=5217" target="_blank"]《c++语言的设计和演化 》[/a][/td] [td width="219" class="unnamed1" height="10"][a href="http://www.china-pub.com/computers/common/info.asp?id=8134" target="_blank"]《从规范出发的程序设计....》[/a][/td] [/tr] [tr bgcolor="#dec4fb"] [td width="271" class="unnamed1" height="12"][a href="http://www.china-pub.com/computers/common/info.asp?id=664" target="_blank"]《程序设计实践 》[/a][/td] [td width="219" class="unnamed1" height="12"][a href="http://www.china-pub.com/computers/common/info.asp?id=6159"]《从规范出发的程序设计》[/a][/td] [/tr] [tr bgcolor="#dec4fb"] [td width="271" class="unnamed1"][a href="http://www.china-pub.com/computers/common/info.asp?id=8224" target="_blank"]《c++程序设计语言题解》[/a] [/td] [td width="219" class="unnamed1"][a href="http://www.china-pub.com/computers/common/info.asp?id=16989" target="_blank"]《科学程序设计引论——用mathematica和c求解计算问题》[/a] [/td] [/tr] [/table] [dr]

第1章 构造过程抽象
1．1程序设计的基本元素
1．1．1表达式
1．1．2命名和环境
1．1．3组合式的求值
1．1．4复合过程
1．1．5过程应用的代换模型
1．1．6条件表达式和谓词
1．1．7实例：采用牛顿法求平方根
1．1．8过程作为黑箱抽象
1．2过程与它们所产生的计算
1．2．1线性的递归和迭代
1．2．2树形递归
1．2．3增长的阶
1．2．4求幂
1．2．5最大公约数
1．2．6实例：素数检测
1．3用高阶函数做抽象
1．3．1过程作为参数
1．3．2用lambda构造过程

　　 第2版前言
　　 软件很可能确实与其他任何东西都不同，它的本意就是被抛弃：这一观点的全部就是总将它看作一个肥皂泡吗?
　　 ——Alan J．Perils
　　 自1980年以来，本书的材料就一直在MIT作为计算机科学学科入门课程的基础。在本书第1版出版之前，我们已经用这一材料教了4年课，而到这个第2版出版，时间又过去了12年。
　　我们非常高兴地看到这一工作被广泛接受，并被结合到其他一些教材中。我们已经看到自己的学生掌握了本书中的思想和程序，并将它们构筑到新的计算机系统或者语言的核心里。这就在文字上实现了一个古犹太教法典的双关语，我们的学生已经变成了我们的创造者。我们非常幸运能有如此有能力的学生和如此有建树的创造者。
　　 在准备这一新版本的过程中，我们结合进了成百条澄清性建议，它们来自我们自己的教学经验，也来自MIT和其他地方的同行们的评述。我们重新设计了本书里主要的程序设计系统中的大部分，包括通用型算术系统、解释器、寄存器机器模拟器和编译器，也重写了所有的程序实例，以保证任何符合IEEE的Scheme标准(IEEE 1990)的Scheme实现都能运行这些代码。
　　 这一版本中强调了几个新问题，其中最重要的是有关在不同的途径中，计算模型里对于时间的处理所起的中心作用：带有状态的对象、并发程序设计、函数式程序设计、惰性求值和非确定性程序设计。这里为并发和非确定性新增加了几节，我们也设法将这一论题集成到整本书里，贯穿始终。
　　 本书第1版基本上是按照我们在MIT一学期课程的教学大纲撰写的。由于有了第2版中增加的这些新材料，在一个学期里覆盖所有内容已经不可能了，所以教师需要从中做一些选择。
　　在我们自己的教学里，有时会跳过有关逻辑程序设计的一节(4．4节)；让学生使用寄存器机器模拟器，但并不去讨论它的实现(5．2节)；对于编译器则只给出一个粗略的概述(5．5节)。即使如此，这还是一个内容非常多的课程。一些教师可能希望只覆盖前面的三章或者四章，而将其他内容留给后续课程。
　　 万维网站点www-mitpress．mit．edu／sicp为本书的使用者提供支持。其中包含了取自本书的程序，示例程序作业、辅助材料和Lisp的Scheme方言的可下载实现。
　　

　　 教育者、将军、减肥专家、心理学家和父母做规划(program)，而军人、学生和另一些社会阶层则被人规划(are progfammed)。解决大规模问题需要经过一系列规划，其中的大部分东西只有在工作进程中才能做出来，这些规划中充满着与手头问题的特殊性相关的情况。如果想要把做规划这件事情本身作为一种智力活动来欣赏，你就必须转到计算机的程序设计(programming)，你需要读或者写计算机程序——而且要大量地做。有关这些程序具体是关于什么的、服务于哪类应用等等的情况常常并不重要，重要的是它们的性能如何，在用于构造
　　更大的程序时能否与其他程序平滑衔接。程序员们必须同时追求具体部分的完美和汇合的适宜性。在这部书里使用“程序设计”一词时，所关注的是程序的创建、执行和研究，这些程序是用一种Lisp方言书写的，为了在数字计算机上执行。采用Lisp并没有对我们可以编程的范围施以任何约束或者限制，而只不过确定了程序描述的记法形式。
　　 本书中要讨论的各种问题都牵涉到三类需要关注的对象：人的大脑、计算机程序的集合以及计算机本身。每一个计算机程序都是现实中的或者精神中的某个过程的一个模型，通过人的头脑孵化出来。这些过程出现在人们的经验或者思维之中，数量上数不胜数，详情琐碎繁杂，任何时候人们都只能部分地理解它们。我们很少能通过自己的程序将这种过程模拟到永远令人满意的程度。正因为如此，即使我们写出的程序是一集经过仔细雕琢的离散符号，是交织在一起的一组函数，它们也需要不断地演化：当我们对于模型的认识更深入、更扩大、更广泛时，就需要去修改程序，直至这一模型最终到达了一种亚稳定状态。而在这时，程序中就又会出现另一个需要我们去为之奋斗的模型。计算机程序设计领域之令人兴奋的源泉，就在于它所引起连绵不绝的发现，在我们的头脑之中，在由程序所表达的计算机制之中，以及在由此所导致的认识爆炸之中。如果说艺术解释了我们的梦想，那么计算机就是以程序的名义执行着它们。
　　 就其本身的所有能力而言，计算机是一位一丝不苟的工匠：它的程序必须正确，我们希望说的所有东西，都必须表述得准确到每一点细节。就像在其他所有使用符号的活动中一样，我们需要通过论证使自己相信程序的真。可以为Lisp本身赋予一个语义(可以说是另一个模型)，假如说，一个程序的功能可以在(例如)谓词演算里描述，那么就可以用逻辑方法做出一个可接受的正确性论证。不幸的是，随着程序变得更大更复杂(实际上它们几乎总是如此)，这种描述本身的适宜性、一致性和正确性也都变得非常值得怀疑了。因此，很少能够看到有
　　关大程序正确性的完全形式化的论证。因为大的程序是从小东西成长起来的，开发出一个标准化的程序结构的武器库，并保证其中每种结构的正确性一—我们称它们为惯用法，再学会如何利用一些已经证明很有价值的组织技术，将这些结构组合成更大的结构，这些都是至关重要的。本书中将详尽地讨论这些技术。理解这些技术，对于参与这种被称为程序设计的具有创造性的事业是最最本质的。特别值得提出的是，发现并掌握强有力的组织技术，将提升我们构造大型的重要程序的能力。反过来说，因为写大程序非常耗时费力，这也推动着我们
　　去发明新方法，减轻由于大程序的功能和细节而引起的沉重负担。
　　 与程序不同，计算机必须遵守物理定律。如果它们要快速执行——几个纳秒做一次状态转换——那么就必须在很短的距离内传导电子(至多1．5英尺)。必须消除由于大量元件而产生的热量集中。人们已经开发出了一些巧妙的工程艺术，用于在功能多样性与元件密度之间求得一种平衡。在任何情况下，硬件都是在比我们编程时所需要关心的层次更低的层次上操作的。将我们的Lisp程序变换到“机器”程序的过程本身也是抽象模型，是通过程序设计做出来的。研究和构造它们，能使人更加深刻地理解与任何模型的程序设计有关的程序组织问题。当然，计算机本身也可以这样模拟。请想一想：最小的物理开关元件在量子力学里建模，而量子力学又由一组微分方程描述，微分方程的细节行为可以由数值去近似，这种数值又由计算机程序所描述，计算机程序的组成……
　　 区分出上述三类需要关注的对象，并不仅仅是为了策略上的便利。即使有人说它不过是人头脑里的东西，这种逻辑区分也引起了这些关注焦点之间符号流动的加速，它们在人们经验中的丰富性、活力和潜力，只能由现实生活中的不断演化去超越。我们至多只能说，这些关注焦点之间的关系是基本稳定的。计算机永远都不够大也不够快。硬件技术的每一次突破都带来了更大规模的程序设计事业，新的组织原理，以及更加丰富的抽象模型。每个读者都应该反复地问自己“到哪里才是头儿，到哪里才是头儿?”——但是不要问得过于频繁，以
　　免忽略了程序设计的乐趣，使自己陷入一种喜忧参半的呆滞状态中。
　　 在我们写出的程序里，有些程序执行了某个精确的数学函数(但是绝不够精确)，例如排序，或者找出一系列数中的最大元，确定素数性，或者找出平方根。我们将这种程序称为算法，关于它们的最佳行为已经有了许多认识，特别是关于两个重要的参数：执行的时间和对数据存储的需求。程序员应该追求好的算法和惯用法。即使某些程序难以精确地描述，程序员也有责任去估计它们的性能，并要继续设法去改进之。
　　 Lisp是——个幸存者，已经使用了四分之一个世纪。在现存的活语言里，只有Fortran比它的寿命更长些。这两种语言都支持着一些重要领域中的程序设计需要，Fortran用于科学与工程计算，Lisp用于人工智能。这两个领域现在仍然很重要，它们的程序员都如此倾心于这两种语言，因此，Lisp和Fortran都还可能继续生存至少四分之一个世纪。
　　 Lisp一直在改变着。这本教科书中所用的Scheme方言就是从原来的Lisp里演化出来的，并在若干重要方面与之相异，包括变量约束的静态作用域，以及允许函数产生出函数作为值。在语义结构上，Scheme更接近于Algol 60而不是早期的Lisp。Algol 60已经不可能再变为活的语言了，但它还活在Scheme和Pascal的基因里。很难找到这样的两种语言，它们能如此清晰地代表着围绕这两种语言而聚集起来的两种差异巨大的文化。Pascal是为了建造金字塔——壮丽辉煌、令人震憾，是由各就其位的沉重巨石筑起的静态结构。而Lisp则是为了构造有机体——同样的壮丽辉煌并令人震憾，由各就其位但却永不静止的无数简单的有机体片段构成的动态
　　结构。在两种语言里都采用了同样的组织原则，除了其中特别重要的一点不同之外：托付给Lisp程序员个人可用的自由支配权，要远远超过在Pascal社团里可找到的东西。Lisp程序大大抬高了函数库的地位，使其可用性超越了催生它们的那些具体应用。作为Lisp的内在数据结构，表对于这种可用性的提升起着最重要的作用。表的简单结构和自然可用性反应到函数里，就使它们具有了一种奇异的普适性。而在Pascal里，数据结构的过度声明导致函数的专用性，阻碍并惩罚临时性的合作。采用100个函数在一种数据结构上操作，远远优于用10个函数在10个数据结构上操作。作为这些情况的必然后果，金字塔矗立在那里千年不变，而有机体则必须演化，否则就会死亡。
　　 为了看清楚这种差异，请将本书中给出的材料和练习与任何第一门Pascal课程的教科书中的材料做一个比较。请不要费力地去想象，说这不过是一本在MIT采用的教科书，其特异性仅仅是因为它出自那个地方。准确地说，任何一本严肃的关于Lisp程序设计的书都应该如此，无论其学生是谁，在什么地方使用。
　　 请注意，这是一本有关程序设计的教科书，它不像大部分关于Lisp的书，因为那些书多半是为人们在人工智能领域工作做准备。当然，无论如何，在研究工作规模不断增长的过程中，软件工程和人工智能所关心的重要程序设计工作正趋于相互结合。这也解释了为什么在人工智能领域之外的人们对Lisp的兴趣在不断增加。
　　 正如由其目标可以预见到的，人工智能的研究产生出许多重要的程序设计问题。在其他程序设计文化中，问题的洪水孵化出一种又一种新的语言。确实，在任何非常大的程序设计工作中，一条有用的组织原则就是通过发明新语言，去控制和隔离作业模块之间的信息流动。这些语言趋向于变得越来越不基本，逐渐逼近系统的边界，逼近我们作为人最经常与之交互的地方。作为这一情况的结果，在这种系统里包含着大量重复的复杂的语言处理功能。Lisp有着如此简单的语法和语义，程序的语法分析可以看作一种很简单的工作。这样，语法分析技术对于Lisp程序几乎就没有价值，语言处理器的构造对于大型Lisp系统的成长和变化不会成为阻碍。最后，正是这种语法和语义的极端简单性，产生出了所有Lisp程序员的负担和自由。任何规模的Lisp程序，除了那种寥寥几行的程序外，都饱含着考虑周到的各种功能。发明并调整，调整恰当后再去发明!让我们举起杯，祝福那些将他们的思想镶嵌在重重括号之间的Lisp程序员。
　　 Alan J．Perlis
　　 纽黑文，康涅狄格