本书从理论上讲解计算机程序的创建、执行和研究，主要内容包括：构造过程抽象，构造数据抽象，模块化、对象和状态，元语言抽象，寄存器机器里的计算等。本书采用Lisp语言的一种方言作为实例分析，但并不拘泥于对这个语言的解释，而是通过这种简单易学的语言来阐述程序设计思想。本书通过创建抽象去控制复杂性，提倡建立约定的界面来组合程序片断，建立新的语言来专门描述某种设计；力图培养计算机专业学生对程序设计的风格要素和审美观有一种良好感觉，从而能够掌握控制大型计算机系统的主要技术。本书揭示计算机程序设计思想的实质是改变了人们的思考方式：从命令式的观点去研究知识的结构。因此，本书所阐述的设计思想不仅适用于计算机程序设计，而且适用于所有工程设计。
本书1984年出版，成型于美国麻省理工学院 (MIT) 多年使用的一本教材，1996年修订为第2版。在过去的20多年里，本书对于计算机科学的教育计划产生了深刻的影响。自出版以来，已被世界上100多所高等院校采用为教材，其中包括斯坦福大学、普林斯顿大学、牛津大学、东京大学等。第2版中大部分重要程序设计系统都重新修改并做过测试，包括各种解释器和编译器。作者根据其后十余年的教学实践，还对其他许多细节做了相应的修改。本书译者为北京大学计算机学院教授，曾经翻译过多部计算机专业的教材，并深受好评；本书译文流畅，细腻准确，较好地反映了原书的风貌。
无
教育者、将军、减肥专家、心理学家和父母做规划（program），而军人、学生和另一些社会阶层则被人规划（are programmed）。解决大规模问题需要经过一系列规划，其中的大部分东西只有在工作进程中才能做出来，这些规划中充满着与手头问题的特殊性相关的情况。如果想要把做规划这件事情本身作为一种智力活动来欣赏，你就必须转到计算机的程序设计（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
纽黑文，康涅狄格
第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节）。即使如此，这还是一个内容非常多的课程。一些教师可能希望只覆盖前面的三章或者四章，而将其他内容留给后续课程。
万维网站点www-mitpress.mit.edu/sicp为本书的使用者提供支持。其中包含了取自本书的程序，示例程序作业、辅助材料和Lisp的Scheme方言的可下载实现。
第1版前言
一台计算机就像是一把小提琴。你可以想象一个新手试了一个音符并丢掉了它。后来他说，听起来真难听。我们已经从大众和我们的大部分计算机科学家那里反复听到这种说法。他们说，计算机程序对个别具体用途而言确实是好东西，但它们太缺乏弹性。一把小提琴或者一台打字机也同样缺乏弹性，那是你学会了如何去使用它们之前。
—Marvin Minsky，“为什么说程序设计很容易成为一种媒介，
用于表述理解浮浅、草率而就的思想”
本书是麻省理工学院（MIT）计算机科学的入门教材。在MIT主修电子工程或者计算机科学的所有学生都必须学这门课，作为“公共核心课程计划”的四分之一。这里还包含两个关于电路和线性系统的科目，还有一个关于数字系统设计的科目。我们从1978年开始涉足这些科目的开发，从1980年秋季以后，我们就一直按照现在这种形式教授这个课程，每年600到700个学生。大部分学生此前没有或者很少有计算方面的正式训练，虽然许多人玩过计算机，也有少数人有许多程序设计或者硬件设计的经验。
我们所设计的这门计算机科学导引课程反映了两方面的主要考虑。首先，我们希望建立起一种看法：一个计算机语言并不仅仅是让计算机去执行操作的一种方式，更重要的，它是一种表述有关方法学的思想的新颖的形式化媒介。因此，程序必须写得能够供人们阅读，偶尔地去供计算机执行。其次，我们相信，在这一层次的课程里，最基本的材料并不是特定程序设计语言的语法，不是有效计算某种功能的巧妙算法，也不是算法的数学分析或者计算的本质基础，而是一些能够用于控制大型软件系统的智力复杂性的技术。
我们的目标是，使完成了这一科目的学生能对程序设计的风格要素和审美观有一种很好的感觉。他们应该掌握了控制大型系统中的复杂性的主要技术。他们应该能够去读50页长的程序，只要该程序是以一种值得模仿的形式写出来的。他们应该知道在什么时候哪些东西不需要去读，哪些东西不需要去理解。他们应该很有把握地去修改一个程序，同时又能保持原来作者的精神和风格。
这些技能并不仅仅适用于计算机程序设计。我们所教授和提炼出来的这些技术，对于所有的工程设计都是通用的。我们在适当的时候隐藏起一些细节，通过创建抽象去控制复杂性。我们通过建立约定的界面，以便能以一种“混合与匹配”的方式组合起一些标准的、已经很好理解的片段，去控制复杂性。我们通过建立一些新的语言去描述各种设计，每种语言强调设计中的一个特定方面并降低其他方面的重要性，以控制复杂性。
设计这门课程的基础是我们的一种信念，“计算机科学”并不是一种科学，而且其重要性也与计算机本身并无太大关系。计算机革命是有关我们如何去思考的方式，以及我们如何去表达自己的思考的一个革命。在这个变化里最基本的东西，就是出现了这样一种或许最好是称为过程性认识论的现象—这就是如何从一种命令式的观点去研究知识的结构，这一观点是与经典数学领域中所采用的更具说明性的观点完全不同的。数学为精确处理“是什么”提供了一种框架，而计算则为精确处理“怎样做”的概念提供了一种框架。
在教授这里的材料时，我们采用的是Lisp语言的一种方言。我们绝没有形式化地教授这一语言，因为完全不必那样做。我们只是使用它，学生可以在几天之内就学会它。这也是类Lisp语言的重要优点：它们只有不多几种构造复合表达式的方式，几乎没有语法结构。所有的形式化性质都可以在一个小时里讲完，就像下象棋的规则似的。在很短时间之后，我们就可以不再去管语言的语法细节（因为这里根本就没有），而进入真正的问题—弄清楚我们需要去计算什么，怎样将问题分解为一组可以控制的部分，如何对这样的部分开展工作。Lisp的另一优势在于，与我们所知的任何其他语言相比，它可以支持（但并不是强制性的）更多的能用于以模块化的方式分解程序的大规模策略。我们可以做过程性抽象和数据抽象，可以通过高阶函数抓住公共的使用模式，可以用赋值和数据操作去模拟局部状态，可以利用流和延时求值连接起一个程序里的各个部分，可以很容易地实现嵌入性语言。所有这些都融合在一个交互式的环境里，带有对递增式程序设计、构造、测试和排除错误的绝佳支持功能。我们要感谢一代又一代的Lisp大师，从John McCarthy开始，是他们铸造起了这样一个具有空前威力的如此优美的好工具。
作为我们所用的Lisp方言，Scheme试图将Lisp和Algol的威力和优雅集成到一起。我们从Lisp那里取来了元语言的威力，它来自简单的语法形式，程序与数据对象的统一表示，以及带有废料收集的堆分配数据。我们从Algol那里取来了词法作用域和块结构，这是当年参加Algol委员会的那些程序设计语言先驱者们的礼物。我们想特别提出John Reynolds和 Peter Landin，为了他们对丘奇的lambda演算与程序设计语言的结构之间关系的真知灼见。我们也认识到应该感谢那些数学家们，他们在计算机出现之前，就已经在这一领域中探索了许多年。这些先驱者包括丘奇（Alonzo Church）、罗塞尔（Barkley Rosser）、克里尼（Stephen Kleene）和库里（Haskell Curry）。
裘宗燕：裘宗燕: 北京大学数学学院信息科学系教授。长期从事计算机软件与理论、程序设计语言和符号计算方面的研究和教学工作。已出版多部著作和译著，包括《程序设计语言基础》（译著，北京大学出版社，1990），《Mathematica数学软件系统的应用与程序设计》（编著，北京大学出版社，1994），《计算概论（上）》（合著，高等教育出版社，1997），《从问题到程序—程序设计与C语言引论》（编著，北京大学出版社，1999）等；自2000年以来，他先后为机械工业出版社华章分社翻译了《程序设计实践》（2000），《C++程序设计语言（特别版）》（2001），《C++语言的设计和演化》（2002），《程序设计语言——概念和结构》（2002），《从规范出发的程序设计》（2003），《计算机程序的构造和解释》（2004）等一系列经典著作，他认真的工作作风、严谨的治学态度，以及所做出的巨大贡献，赢得广大读者的好评。 在北京大学教授的主要课程：计算概论（一年级本科生，主要内容为C语言程序设计），程序设计技术与方法（本科生），程序设计语言原理（研究生），算法和数据结构（本科生），算法设计与分析（本科生和研究生），数理逻辑（本科生）等。 点击进入[URL=http://www.math.pku.edu.cn/teachers/qiuzy/]作者主页[/URL]。
第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
