计算机程序的构造和解释

前　言
Structure and Interpretation of Computer Programs: JavaScript Edition
《计算机程序的构造和解释》（SICP）给读者介绍计算的核心思想，采用的方法是为计算建立一系列的概念模型。第1章到第3章涵盖了所有时新的高级程序设计语言所共有的程序设计概念。在原SICP的两个版本里，程序设计示例用程序设计语言Scheme描述，该语言具有极简的风格和基于表达式的语法形式，这些使原书可以聚焦于基础概念，而不是所选语言本身的设计。第4章和第5章使用Scheme构造Scheme的处理器，用以加深读者对概念模型的理解，并探索了语言的一些扩充和替代结构。
自1984年出版，以及1996年第2版出版后，SICP被全世界许多大学和学院选作教科书。新加坡国立大学（NUS）1997年开始开设基于SICP的引论课程CS1101S。20世纪90年代中期，Python、JavaScript和Ruby等语言发展起来，它们都共享了Scheme的核心设计元素，但采用了更复杂的基于语句的语法结构，使用了人们更熟悉的代数表达形式（中缀形式）。这些语言的兴起，导致一些教师调整基于SICP的课程，典型方法是把其中的示例程序都翻译为他们所选的语言，再加上一些特别的与语言相关的材料，并略去原书的第4章和
第5章。
把SICP改编到JavaScript
在NUS，把SICP的第2版改编到JavaScript（SCIP JS）的工作开始于2008年，2012年CS1101S课程转到了JavaScript。ECMAScript 2015语言标准引进了lambda表达式、尾递归和分程序作用域的变量和常量，这些使有关的改编更接近原书。我们对SICP的实质性修改不多，只出现在JavaScript与Scheme的差异使我们感到不得不修改的地方。这本书只涉及JavaScript的很少一部分，所以绝不建议读者用它学习这个语言。举例说，JavaScript对象的概念在本书里就完全没有提及—而对象被认为是该语言最基本的成分。
通过加入一些模拟Scheme原语的库，包括支持表结构的库，并相应修改正文中的文字，翻译第1～3章的程序是直截了当的。然而，转到JavaScript，也迫使我们对第4章和第5章的解释器和编译器做了一些实质性的修改，以便处理返回语句。Scheme的基于表达式的语法里没有返回语句，而这种语句是基于语句的语言中不可或缺的特征。
通过使用JavaScript，第1章到第3章给读者介绍了今天大多数主流语言的语法风格。然而，在第4章，语法风格产生了重大变化，因为把程序直接表示为数据结构已经无法看作是理所当然了。但这也为我们提供了一个机会，在4.1节为读者介绍语法分析，这是程序设计语言处理器的一个重要组成部分。在4.4节，JavaScript严格的语法结构使展示逻辑程序设计系统的工作大大复杂化，显示出用JavaScript作为程序语言设计工具的局限性。
使用SICP JS资源
MIT出版社有关SICP JS的网页上有针对本书使用者的支持链接，那里提供了书中所有程序和扩展教学资源，包括一大批附加练习，以及安排典型的大学一学期课程的SICP JS选学子集的建议。本书中的JavaScript程序可以在符合ECMAScript 2020规范（ECMA 2020）的任何JavaScript解释器推荐的严格模式下运行。MIT出版社的网页包含一个名为sicp的JavaScript包，它提供了本书中当作“原语”的所有JavaScript函数。
致读者
我们真诚地希望，如果你在阅读本书时第一次遇到程序设计，你将能运用自己对计算机程序的构造和解释的新理解去学习更多的程序设计语言，包括Scheme和完整的JavaScript。如果你在拿起SICP JS之前已经学过JavaScript，你可能得到有关该语言背后的基本概念的一些新见解，并看到只需要多么少的东西就可以得到多么多。如果你遇到SICP JS时已经学过有关原SICP的知识，你可能看到熟悉的思想如何用一种新形式表达，还可以欣赏在线的对照版本（在本书的网页上可用），它使你可以并排地对照着看SICP和SICP JS。

Martin Henz和Tobias Wrigstad

本书主要介绍计算的核心思想，采用的方法是为计算建立一系列概念模型。主要内容包括：构造过程抽象，构造数据抽象，模块化、对象和状态，元语言抽象，寄存器机器里的计算等。采用JavaScript作为实例分析，但并不拘泥于对语言的解释，而是通过这种语言来阐述程序设计思想。第1章介绍了计算过程以及函数在程序设计中扮演的角色。第2章在第1章的基础上提供了将数据对象组合起来形成复合数据，进而构造抽象的方法。第3章介绍了一些帮助我们模块化构造大型系统的策略。第4章通过元语言抽象探究如何在一些语言的基础上开发新语言的技术。第5章从寄存器机器的角度出发，通过设计寄存器机器，开发一些机制，实现重要的程序设计结构，同时给出一种描述寄存器机器设计的语言。本书揭示计算机程序设计思想的实质是改变了人们的思考方式：从命令式的观点去研究知识的结构。因此，本书所阐述的设计思想不仅适用于计算机程序设计，而且适用于所有工程设计。

哈罗德?阿贝尔森（Harold Abelson）是MIT 1992年度MacVicar Faculty Fellow。在MIT电子工程和计算机科学系工作，得到过重要的计算机科学教育奖——IEEE计算机协会的Booth奖。
杰拉尔德·杰伊·萨斯曼（Gerald Jay Sussman），麻省理工学院电子工程系教授。他长期从事人工智能的研究，还从事过计算机语言、计算机体系结构和超大规模集成电路设计方面的工作（Scheme编程语言的发明人之一），并致力于用计算机语言来表达和解决各领域的实际问题。他是IEEE 、AAAI 、ACM、AAAS等协会的Fellow，曾获得ACM Karl Karlstrom杰出教育家奖、Bose教学奖等。
马丁·亨茨（Martin Henz），新加坡国立大学计算机科学系副教授。他曾是德国人工智能研究中心的科学家。他目前主要从事体验式学习的可扩展性的研究和教学。他因为在这方面的出色工作，而和Tobias Wrigstad将SICP这本书改编为JavaScript版本。他发表很多关于计算机科学和工程教育、编程语言等方面的论文。
托拜厄斯·瑞格斯塔德（Tobias Wrigstad），乌普萨拉大学信息技术系教授，主要从事编程语言、并行编程、软件工程、并发编程方面的研究工作。在教学方面，长期为本科生讲授命令与面向对象编程方法论的导论课程。
朱莉·萨斯曼（Julie Sussman），作家和编辑，同时使用自然语言和计算机语言写作。

目　录
Structure and Interpretation of Computer Programs: JavaScript Edition
译者序
序言
1984年版《计算机程序的构造和解释》的原序
前言
1996年SICP第2版的前言
1984年SICP第1版的前言
致谢
1996年SICP第2版的致谢
第1章　构造函数抽象1
1.1　程序设计的基本元素2
1.1.1　表达式3
1.1.2　命名和环境4
1.1.3　运算符组合式的求值5
1.1.4　复合函数6
1.1.5　函数应用的代换模型8
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　最大公约数31
1.2.6　实例：素数检测33
1.3　用高阶函数做抽象37
1.3.1　函数作为参数37
1.3.2　用lambda表达式构造函数41
1.3.3　函数作为通用的方法45
1.3.4　函数作为返回值48
第2章　构造数据抽象54
2.1　初识数据抽象56
2.1.1　实例：有理数的算术运算56
2.1.2　抽象屏障59
2.1.3　数据是什么意思？61
2.1.4　扩展练习：区间算术63
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　实例：符号求导97
2.3.3　实例：集合的表示102
2.3.4　实例：Huffman编码树108
2.4　抽象数据的多重表示114
2.4.1　复数的表示115
2.4.2　带标签数据118
2.4.3　数据导向的程序设计和可
　　　加性121
2.5　包含通用型操作的系统127
2.5.1　通用型算术运算128
2.5.2　不同类型数据的组合131
2.5.3　实例：符号代数136
第3章　模块化、对象和状态146
3.1　赋值和局部状态146
3.1.1　局部状态变量147
3.1.2　引进赋值带来的利益152
3.1.3　引进赋值的代价155
3.2　求值的环境模型159
3.2.1　求值规则160
3.2.2　简单函数的应用163
3.2.3　框架作为局部状态的仓库165
3.2.4　内部定义169
3.3　用变动数据建模172
3.3.1　可变的表结构172
3.3.2　队列的表示179
3.3.3　表格的表示182
3.3.4　数字电路模拟器187
3.3.5　约束传播196
3.4　并发：时间是一个本质问题205
3.4.1　并发系统中时间的性质206
3.4.2　控制并发的机制209
3.5　流218
3.5.1　流作为延迟的表219
3.5.2　无穷流225
3.5.3　流计算模式的应用230
3.5.4　流和延迟求值238
3.5.5　函数式程序的模块化和对象
　　　的模块化242
第4章　元语言抽象246
4.1　元循环求值器248
4.1.1　求值器的核心部分249
4.1.2　组件的表示254
4.1.3　求值器的数据结构263
4.1.4　把求值器作为程序运行267
4.1.5　以数据为程序270
4.1.6　内部声明272
4.1.7　分离语法分析与执行275
4.2　惰性求值280
4.2.1　正则序和应用序280
4.2.2　采用惰性求值的解释器281
4.2.3　流作为惰性的表288
4.3　非确定性计算289
4.3.1　搜索和amb291
4.3.2　非确定性程序实例294
4.3.3　实现amb求值器300
4.4　逻辑程序设计309
4.4.1　演绎式信息检索311
4.4.2　查询系统如何工作320
4.4.3　逻辑程序设计
　　　是数理逻辑吗？326
4.4.4　实现查询系统330
第5章　寄存器机器里的计算350
5.1　寄存器机器的设计351
5.1.1　一种描述寄存器机器的语言352
5.1.2　机器设计的抽象355
5.1.3　子程序357
5.1.4　使用栈实现递归360
5.1.5　指令总结364
5.2　寄存器机器的模拟器365
5.2.1　机器模型366
5.2.2　汇编器369
5.2.3　指令和它们的执行函数372
5.2.4　监视机器执行378
5.3　存储分配和废料收集380
5.3.1　把存储器看作向量380
5.3.2　维持一种无穷存储的假象384
5.4　显式控制的求值器389
5.4.1　分派器和基本求值390
5.4.2　函数应用的求值393
5.4.3　块结构、赋值和声明400
5.4.4　求值器的运行401
5.5　编译405
5.5.1　编译器的结构407
5.5.2　组件的编译411
5.5.3　编译函数应用和返回语句417
5.5.4　指令序列的组合423
5.5.5　编译代码的实例426
5.5.6　词法地址433
5.5.7　将编译代码与求值器接口435
参考文献441
索引447
练习列表490

本书主要介绍计算的核心思想，采用的方法是为计算建立一系列概念模型。主要内容包括：构造过程抽象，构造数据抽象，模块化、对象和状态，元语言抽象，寄存器机器里的计算等。采用JavaScript作为实例分析，但并不拘泥于对语言的解释，而是通过这种语言来阐述程序设计思想。第1章介绍了计算过程以及函数在程序设计中扮演的角色。第2章在第1章的基础上提供了将数据对象组合起来形成复合数据，进而构造抽象的方法。第3章介绍了一些帮助我们模块化构造大型系统的策略。第4章通过元语言抽象探究如何在一些语言的基础上开发新语言的技术。第5章从寄存器机器的角度出发，通过设计寄存器机器，开发一些机制，实现重要的程序设计结构，同时给出一种描述寄存器机器设计的语言。本书揭示计算机程序设计思想的实质是改变了人们的思考方式：从命令式的观点去研究知识的结构。因此，本书所阐述的设计思想不仅适用于计算机程序设计，而且适用于所有工程设计。

哈罗德?阿贝尔森（Harold Abelson）是MIT 1992年度MacVicar Faculty Fellow。在MIT电子工程和计算机科学系工作，得到过重要的计算机科学教育奖——IEEE计算机协会的Booth奖。
杰拉尔德·杰伊·萨斯曼（Gerald Jay Sussman），麻省理工学院电子工程系教授。他长期从事人工智能的研究，还从事过计算机语言、计算机体系结构和超大规模集成电路设计方面的工作（Scheme编程语言的发明人之一），并致力于用计算机语言来表达和解决各领域的实际问题。他是IEEE 、AAAI 、ACM、AAAS等协会的Fellow，曾获得ACM Karl Karlstrom杰出教育家奖、Bose教学奖等。
马丁·亨茨（Martin Henz），新加坡国立大学计算机科学系副教授。他曾是德国人工智能研究中心的科学家。他目前主要从事体验式学习的可扩展性的研究和教学。他因为在这方面的出色工作，而和Tobias Wrigstad将SICP这本书改编为JavaScript版本。他发表很多关于计算机科学和工程教育、编程语言等方面的论文。
托拜厄斯·瑞格斯塔德（Tobias Wrigstad），乌普萨拉大学信息技术系教授，主要从事编程语言、并行编程、软件工程、并发编程方面的研究工作。在教学方面，长期为本科生讲授命令与面向对象编程方法论的导论课程。
朱莉·萨斯曼（Julie Sussman），作家和编辑，同时使用自然语言和计算机语言写作。