本书是国外比较成功的一本讨论程序设计语言的教科书，已在一些学校使用多年。书的主要内容包括：引论、命令式程序设计、面向对象的程序设计、函数式程序设计、其他程序设计范型以及语言的描述六大部分。本书适合作为计算机及其相关专业本科高年级学生的教材或教学参考书，或作为研究生的基础课程教材或参考书，也适合其他相关的技术人员参考。本书的学习基础是学过用过一种或几种程序设计语言（最好是Pascal/C/C++），有一定程序设计经验，并对数据结构等计算机基础知识有所理解。

本书的设计是面向有关程序设计语言的大学三、四年级课程，至少要求前面已经学过一门有关程序设计的引论课程。如果加上一些辅助性阅读材料，这本书也可以用于研究生课程。
本版有什么新变化
人们对语言的观点变化以及使用本书的反馈意见是本次修订的最根本动力。教师们希望能强调概念，但也要求用比较少的语言来阐述有关的概念。在这段时期内，Modula-2已逐渐淡出，而C++已占据了重要地位，被作为开发软件产品所用的程序设计语言。目前函数式程序设计语言的候选者还应该包括Standard ML、Haskell和Miranda。
这个新版本包括15章，比第1版多了3章。新的3章的内容分别是：
数据类型，如数组、记录和指针，占有一章。
另一章用Standard ML介绍函数式程序设计。
最后一章是有关语言的总结。
语言描述和语法问题移到了前面的第2章。
本书的组织
本书特别强调的是概念和它们协同工作的情况，而不是各种语言特征。因此讨论中将相关的概念放在一起，以便能够同步地给出有意思的例子和程序设计练习。对于一种语言，只是根据例子和练习的需要介绍足够多的东西，对所有有关语言的总结放在第15章。
第一部分：引言
第1章讨论程序设计语言所扮演的角色及其开发过程。这里介绍了本书提出的各种程序设计范型，包括命令式、面向对象、函数式和逻辑式的程序设计。
第2章讨论程序设计语言的描述问题，以便使这些东西能够应用到本书的其他部分。这一章的例子主要讨论表达式，描述表达式语法的方法可以用到语言的其他部分。
第二部分：命令式程序设计
命令式语言族在第3～5章讨论。术语“命令式”（imperative）来自于命令和动作，这种计算模型就是基于基础机器的一系列动作。
第3章的主题是控制流。结构化的控制结构，如while语句，能用于组织程序的控制流，形成以结构化语句为单位的程序设计，而不是以单个赋值为单位。学过主要关注命令式程序设计课程的学生一般都熟悉Pascal，因此，这一章不仅讨论了赋值和结构语句，还讨论了借助不变式考虑程序设计的问题。所举例子涉及各种基本的值，例如整数和数组等。
第4章讨论命令式程序设计中的数据。在Pascal和C出现之后，各种数据表示机制，如数组、记录和指针，已经趋于稳定。有关这些机制的讨论中也结合了它们在第6章和第7章中用来表示对象的应用。
第5章的讨论围绕着命令式程序设计的核心，也就是像Pascal或C一类语言的内部东西。有关的论题包括：过程的源代码正文与过程活动的对比，参数传递机制，作用域规则和存储管理等。
在本书中，只要可能，就采用Pascal去展示命令式程序设计的有关问题。Pascal对于第3～5章而言已经足够了。另一种可能的选择是用C语言。
第三部分：面向对象程序设计
随着程序变得越来越大，程序设计的自然单位也变成了一组组的数据和操作。程序结构概念的发展产生了一系列的术语，包括模块、用户定义类型（例如堆栈）以及类（在面向对象的程序设计中）。
第6章开始讨论基于过程、模块和类的程序设计。这些概念服务于不同的需要，也能够互相组合一起使用：在实现模块或者类的操作时总需要使用过程；模块能够被用作带类的程序的源代码中的静态部分。Pascal的某些版本支持模块概念，因此它们就可以用于第6章的前半部分。C++是C的一种扩充，第6章里将会介绍它。
第7章中的计算模型是独立的对象，这些对象通过互相传递消息的方式交互。这一章的前三分之一是有关面向对象程序设计的一般性讨论，用了一个在C++和Smalltalk里可以有相似实现的实例。其余部分是有关C++和Smalltalk的独立材料，以便能用这两种语言中的任何一种来研究面向对象程序设计的问题。基于教师的反馈，这里将C++放在Smalltalk之前，与原版本相比，交换了位置。面向对象的程序设计用C++和Smalltalk阐释，是因为它们代表了两条不同的途径。
第3～7章里的所有概念都可以用C++语言阐述。因此，也可以直接向学生介绍C++，无须先经过C语言。
第四部分：函数式程序设计
函数式程序设计是一种非常值得学习的程序设计风格，无论是就其自身，是作为一种研究类型等概念的媒介，还是作为一种描述语言的技术。第8章强调的重点还是概念，第9章和第10章强调程序设计风格，第13章则是语言描述。其中的计算模型是基于一个表达式解释器，表达式通过将函数应用到一些子表达式上而构成。
第8章强调的是概念。函数式语言的简单性使它们可以非常方便地用于介绍诸如值、类型、名字和函数一类的概念。这种简单性结果源自对表达式和值的强调，与作为其基础的机器无关。本章讨论函数式语言的公共基础问题，以ML作为工作语言。
ML和Lisp之间的根本性差别在于ML是有类型的，类型的影响遍及整个语言。第9章用ML阐述函数和数据类型的使用。在函数式程序设计中，函数作为一级成员（一等公民），处在与其他值同等的地位。这种一级地位使我们可以构造出各种威力强大的针对数据集合的操作。
函数式程序设计始于Lisp。Lisp的程序和数据都用表来表示，甚至这种语言的名字本身也就是“表处理系统（List Processor）”的缩写形式。这种对于表的一致使用方式使得Lisp语言以其可扩充性而闻名于世。第10章将探索表的使用，以Lisp的方言Scheme作为基础。
另请参看第13章，那里包含了对Scheme的一个小子集的解释器。还有第14章，其中讨论了lambda演算。
第五部分：其他范型
在第11章中，逻辑式程序设计是结合Prolog一起讨论的。逻辑式程序设计处理的是关系而不是函数。对于合适的问题，采用这种范型写出的程序短小精悍，由规则和事实组成。这种语言利用给定的规则和事实，推导出对于查询的回答。
在第12章用Ada语言展示了并发程序设计的情况。也可以采用另一种方式，在面向对象的程序设计之后讨论并发程序设计，通过给每个对象一个计算线程，就能形成许许多多的进程。目前的组织方式是将函数式程序设计放在并发程序设计之前。
第六部分：语言的描述
第13章有关语言描述的方法介绍是针对专业人员写的。这些方法范围广泛，从为语言翻译而用的属性，到用于类型推理的逻辑规则，再到用于澄清微妙的语言问题的解释器。
要描述一种语言，可以为它专门写一个定义性解释器，这种解释器的目的就是定义被解释的语言，效率并不是这里关心的问题。McCarthy用Lisp语言写出了Lisp语言的最早的定义性解释器，在语言描述方面仍有重要意义，因此，这里的语言描述问题使用Lisp的方言Scheme。第13章为Scheme的一个小子集开发了一个解释器。
lambda演算是函数式程序语言在智慧方面的先驱者。lambda演算具有极其简单的语法形式，这使它被广泛用做研究语言的媒介。第14章介绍了lambda演算的一些变体，从纯的无类型lambda演算一直讨论到有类型的lambda演算。
第15章是对本书中所用的各种语言的一个总结。

RS

（美）Ravi Sethi：Ravi Sethi: 自1976年起一直在新泽西州Murray Hill的AT&T贝尔实验室工作，是贝尔实验室计算科学研究中心的主任。他曾在宾夕法尼亚州立大学和亚利桑那大学担任教授，并曾在普林斯顿大学和Rutgers大学任教。他是著名的“龙书”（《编译器：原理和工具》）的作者之一，还写过许多文章。他的书已经被译为多种文字在世界范围流传。

裘宗燕 等：裘宗燕: 北京大学数学学院信息科学系教授。长期从事计算机软件与理论、程序设计语言和符号计算方面的研究和教学工作。已出版多部著作和译著，包括《程序设计语言基础》（译著，北京大学出版社，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]。

IEEE/ACM的1991教程将“程序设计语言”课程列为计算机及其相关专业本科生必修课程。在IEEE/ACM联合拟定的2001教程草案中，也将“程序设计语言”列为教育计划的14个基本知识领域之一，并特别强调了它的重要性。本书就是国外比较成功的一本讨论程序设计语言的教科书，已在一些学校使用多年（这里是第2版）。本书作者是贝尔实验室计算科学研究中心主任，在程序设计语言、编译技术等方面颇有建树，在程序设计语言的教学方面也有丰富经验。本书取材比较合理，既讨论了许多实际技术问题，以帮助人们认识程序设计语言的方方面面；也适当地介绍了一些问题的理论基础。书的内容组织也比较合理。本书适合作为计算机及其相关专业本科高年级学生的教材或教学参考书，或作为研究生的基础课程教材或参考书，也适合其他热爱计算机科学技术、希望进一步提升自己的计算机基础和能力的人阅读参考。本书的学习基础是学过用过一种或几种程序语言（最好包括Pascal/C/C++），有一定程序设计经验，并对数据结构等计算机基础知识有所理解。
本书以介绍常规的命令式语言及其面向对象的发展为重点，讨论了常规语言各方面的基本问题，包括语言描述，控制结构、数据类型以及它们的实现机理，过程抽象及其实现，数据抽象和面向对象的有关特征及其实现，并行机制的各种问题。也用相当的篇幅介绍了程序设计的其他范型，主要是函数式程序设计、逻辑程序设计，以及支持这些范型的语言。学习了解这些知识，对于计算机及其相关专业学生的知识完整性也是非常重要的。从这些非常规的范型中可以看到许多很有价值的思想。实际上，无论是过去、现在、还是将来，其他程序设计范型的许多有价值的思想都已经/正在/将以各种形式被常规程序设计实践所接纳和使用。了解在更大范围里的程序设计实践情况，对于在计算机领域中的创新思维也是极端重要的，无论是从事实践性工作还是研究性工作。
本书还用了一定篇幅，简略讨论了与程序语言有关的一些理论问题，包括程序语言的语法、语义模型、类型，等等。虽然大部分计算机领域的工作者不会去从事理论研究工作，但也应该看到理论对于实际工作的重要作用。按我的个人观点，理论至少可以帮助人擦亮眼睛，使我们能看清楚那些隐藏在繁杂的实际细节背后的根本原因，使我们在从事实践性的工作时心里有底。对理论问题的重视不够，至少说，已经在一定程度上阻碍了我国计算机事业的发展，阻碍了许多很有潜力的个人的发展。虽然改变计算机教育的现状，推动我国计算机事业的发展不是一朝一夕之事，但是，每个立志投身于这一领域的个人还是能尽量为自己的未来前途多做一些事情。加强个人的理论素养就是最基本的问题之一。本书提供了有关方面的一些基本知识，可以作为相关学习的起点。
对于大部分计算机工作者、大部分软件人员、大部分计算机及其相关专业的学生而言，程序设计语言就是我们所面对的计算机。因此，理解计算机、掌握计算机技术的一个重要方面就是理解和掌握程序设计语言。程序语言规定了我们在描述要解决的问题时所能使用的手段，规定了这种描述的形式及其意义。在另一个层次上，一种特定的程序语言还对我们在解决问题时可能采用的技术和方式限定了一个大的边界。
目前，世界上流行的程序语言有许多种，这种情况将来也不会改变，因为这是由我们所面临的需要解决的计算问题的五彩缤纷所决定的。任何语言都不可能是最完美的工具，不可能在处理任何问题时都是最锐利的宝剑。每种语言都有其最强的地方，也有其薄弱之处。当我们面对一项具体工作时，即使有各种环境因素的制约，也还是应该尽可能地去选择最适合这个问题的语言。一个计算机工作者需要理解掌握多种程序设计语言，只有这样，在遇到具体问题时才可能做出更合理的选择。为此，我们就需要学习多种程序设计语言，需要在实际工作中，针对具体问题，对各种可能用的语言进行评价和比较。而要能正确地做这种评价比较，就需要有对于语言的更深入理解。
各种常规语言有许多共同点，也有许多差异。许多共同点和差异在程序的表面形式上表现得并不明显。有些程序机制的引入将引起语言实现模型的根本性变化，例如支持递归，支持数组的越界检查，支持动态的类型检查，支持各种面向对象的概念，等等。这些都会对我们写程序的方式，写出的程序的效率和灵活性产生重要影响。为什么会出现这种情况？其根源就在于程序语言与常规计算机的深层关系，在于将这些语言特征映射到常规计算机的方式和技术。理解了这些问题，不但能够帮助我们做出更合理的语言选择，也使我们能更有把握地选择所使用的程序机制与结构，不管在哪种具体语言里写程序，这些选择也是极端重要的。对于本书有关知识的学习将能在这个方面给我们以帮助。
在实际中，新的语言层出不穷，学习新语言会成为许多计算机工作者毕生都要做的事情。由于新的应用问题（太多了，数不胜数），新的程序运行环境（例如网络环境，并行环境等），对于程序设计实践的新认识（例如，面向对象），理论研究的新成果，甚至是为了个别公司自身的商业利益，如此等等，这些都可能导致新语言的出现。学习程序设计语言课程或相关书籍有一个重要作用，那就是能使人更容易看清自己正在学习的语言的关键性特征，也更容易看清楚语言中的陷阱（没有语言能完全避免这些东西），使语言学习更有成效，也使人能将新学习的语言更快更好地应用于实际。
换一个角度，从更不功利的观点出发去看问题。程序设计语言是计算机科学技术领域中的一个重要分支，在过去的50年里，人们在这个领域中的研究和开发取得了极其丰硕的成果。这些成果，作为计算机科学技术研究的智力产出，也是非常值得了解和学习的。即使作为一种欣赏，观看、领略那些从事程序设计语言研究和实践的先行者的各种智力的和技术的杰作，也是非常令人愉快的事情，且不说这些思想和技术还可能作为我们工作中的借鉴。
我们非常高兴地看到，本书的出版将为图书市场上数量极少的类似书籍增添新的一员，也使关心这一领域的读者，准备和正在开设这方面课程的教师，学习这方面课程的学生增加一种新的选择。本书的翻译工作由我负责组织，我的一些学生参予。前言和第1、2、8、9、10、11章由我翻译，第3、4章由蒲戈光翻译，第5章由魏晋伟翻译，第6、7章由林宗芳翻译，第12、13、14、15章由秦胜潮翻译，最后由我统一修改定稿，秦胜潮也参与了一些修订。蒲戈光还为这个工作实现了一个术语对照查询的帮助系统。本书译稿的每一章都经过至少两个人多遍阅读和修订。我们希望这个工作的结果能够使读者满意。


裘宗燕
2001年7月于北京大学

第一部分　 引言
第1章　 程序设计语言的位置 2
1.1　 走向高级语言 2
1.1.1　 机器语言是晦涩难懂的 3
1.1.2　 汇编语言是低级的 3
1.1.3　 高级语言的优点 5
1.2　 规模的问题 6
1.2.1　 人的错误因素 6
1.2.2　 程序设计语言扮演的角色 7
1.3　 程序设计范型 7
1.3.1　 命令式程序设计 8
1.3.2　 函数式程序设计 9
1.3.3　 面向对象的程序设计 11
1.3.4　 逻辑程序设计 12
1.3.5　 语言的选择 12
1.4　 语言实现：在裂谷上架桥 12
1.4.1　 编译 13
1.4.2　 解释 14
1.4.3　 编译器和解释器：对比 15
练习 15
引文注记 16
第2章　 语言的描述：语法结构 18
2.1　 表达式的记法 20
2.1.1　 前缀记法 20
2.1.2　 后缀记法 21
2.1.3　 中缀记法：优先级和结合性 21
2.1.4　 混合记法 22
2.2　 抽象语法树 22
2.3　 词语法 24
2.4　 上下文无关文法 25
2.4.1　 文法介绍 25
2.4.2　 上下文无关文法的定义 26
2.4.3　 BNF：Backus-Naur范式 26
2.4.4　 语法分析树描绘了具体语法 27
2.4.5　 语法的歧义性 28
2.4.6　 悬空的else的歧义性 28
2.4.7　 导出 29
2.5　 表达式的文法 30
2.5.1　 中缀表达式中的表列 30
2.5.2　 从抽象语法到具体语法 31
2.6　 文法的各种变形 33
2.6.1　 扩充的BNF 33
2.6.2　 语法图 35
练习 35
引文注记 38
第二部分　 命令式程序设计
第3章　 语句：结构化程序设计 41
3.1　 结构化程序设计的必要性 41
3.1.1　 静态程序和动态计算 41
3.1.2　 命令式语言的设计原则 42
3.1.3　 一个例子 42
3.1.4　 不变式：程序设计 43
3.2　 语法制导的控制流 44
3.2.1　 语句的复合 44
3.2.2　 选择：条件语句 45
3.2.3　 循环结构：while和repeat 46
3.2.4　 定性迭代：for循环 48
3.2.5　 选择：case语句 48
3.2.6　 case语句的实现 49
3.3　 设计考虑：语法 50
3.3.1　 序列：分隔符和终止符 50
3.3.2　 避免悬空的else 52
3.4　 处理循环中的特殊情况 53
3.4.1　 循环中的break和continue语句 54
3.4.2　 return语句 56
3.4.3　 goto语句 56
3.5　 使用不变式做程序设计 56
3.5.1　 前条件和后条件 57
3.5.2　 实例：线性搜索 58
3.6　 部分正确性的证明规则 60
3.6.1　 断言和公式 61
3.6.2　 复合语句的证明规则 61
3.6.3　 条件语句的证明规则 62
3.6.4　 有关while语句的规则 62
3.6.5　 关于赋值的规则 62
3.6.6　 化简规则 63
3.6.7　 Pascal中的语句 63
3.7　 C语言的控制流 63
3.7.1　 赋值运算符 64
3.7.2　 表达式里的赋值 65
3.7.3　 C语言的for循环：非定性迭代 65
3.7.4　 循环中的break和continue语句 66
练习 66
引文注记 70
第4章　 类型：数据表示 72
4.1　 类型的作用 72
4.1.1　 值和它们的类型 73
4.1.2　 类型表达式 73
4.1.3　 本章中的类型 73
4.1.4　 静态布局决策 74
4.1.5　 有关类型名、数组和记录的预览 75
4.2　 基本类型 76
4.2.1　 枚举 76
4.2.2　 整型和实型 77
4.2.3　 布尔表达式的短路求值 77
4.2.4　 子域 78
4.2.5　 基本类型的布局 78
4.2.6　 程序设计的风格：字符和类型转换 78
4.3　 数组：元素的序列 79
4.3.1　 数组类型 79
4.3.2　 数组的布局 81
4.3.3　 数组边界和存储分配 82
4.3.4　 数组的值和初始化 83
4.4　 记录：命名的域 84
4.4.1　 记录类型有一组特定的域 84
4.4.2　 变量声明分配存储空间 84
4.4.3　 对记录的操作 84
4.4.4　 数组和记录的比较 85
4.5　 联合和变体记录 85
4.5.1　 变体记录的布局 86
4.5.2　 变体记录损害类型安全 87
4.6　 集合 88
4.6.1　 集合的值 88
4.6.2　 集合类型 88
4.6.3　 集合类型的实现 88
4.6.4　 集合的运算 88
4.7　 指针：效率和动态存储分配 89
4.7.1　 指针类型 90
4.7.2　 指针操作 90
4.7.3　 数据结构的增长和缩减 90
4.7.4　 悬空指针和存储流失 91
4.7.5　 指针作为代理 92
4.8　 两种字符串列表 95
4.8.1　 Pascal的一种表示 95
4.8.2　 C语言的一种表示 96
4.9　 类型和错误检查 97
4.9.1　 变量约束：变量的类型 98
4.9.2　 类型系统：表达式的类型 98
4.9.3　 类型检查的基本规则 99
4.9.4　 类型名和类型等价 99
4.9.5　 静态和动态类型检查 101
练习 102
引文注记 104
第5章　 过程活动 105
5.1　 对过程的介绍 106
5.1.1　 过程调用 106
5.1.2　 过程的要素 106
5.1.3　 递归：过程的多个活动 109
5.1.4　 过程的价值 109
5.2　 参数传递方式 110
5.2.1　 值调用 110
5.2.2　 引用调用 111
5.2.3　 值结果调用 113
5.3　 名字的作用域规则 114
5.3.1　 词法作用域和动态作用域 114
5.3.2　 词法作用域与局部变量的重命名 115
5.3.3　 宏展开与动态作用域 116
5.3.4　 按名调用与词法作用域 117
5.4　 源文本中的嵌套作用域 118
5.4.1　 声明的作用域 118
5.4.2　 嵌套作用域：C中的变量声明 119
5.4.3　 嵌套作用域：Pascal中的过程声明 121
5.5　 活动记录 122
5.5.1　 活动间的控制流 122
5.5.2　 活动记录的元素 124
5.5.3　 堆存储分配和释放 127
5.5.4　 堆栈分配和释放 127
5.5.5　 在编译时分配静态变量 128
5.6　 词法作用域：在C中的过程 128
5.6.1　 C程序的存储布局 129
5.6.2　 局部变量的存储 129
5.6.3　 C的过程调用和返回 130
5.6.4　 运行时的变量访问 131
5.6.5　 过程作为参数 131
5.6.6　 悬空指针 132
5.6.7　 尾递归消除 132
5.7　 词法作用域：嵌套过程和Pascal 135
5.7.1　 可见性规则 135
5.7.2　 访问非局部变量：控制链和访问链 136
5.7.3　 过程的调用和返回 138
5.7.4　 过程作为参数 139
5.7.5　 用于快速访问的区头向量 139
练习 141
引文注记 143
第三部分　 面向对象程序设计
第6章　 数据和操作 147
6.1　 程序构造的结构 147
6.1.1　 过程：提高计算的层次 148
6.1.2　 程序静态文本的模块划分 149
6.1.3　 用户定义数据类型 150
6.1.4　 几种方法的比较 151
6.2　 信息隐藏 152
6.2.1　 动机：区分行为与实现 152
6.2.2　 数据不变式 154
6.2.3　 数据的可见性 154
6.2.4　 实现的隐藏和程序开发 154
6.3　 使用模块设计程序 155
6.3.1　 表达式求值程序的设计 155
6.3.2　 程序组织 157
6.3.3　 讨论：程序组织 161
6.4　 模块和用户定义类型 161
6.4.1　 导出名字和导入名字 161
6.4.2　 导出类型 162
6.5　 C++的类声明 164
6.5.1　 类声明中的数据和操作 164
6.5.2　 将类名作为定义的类型使用 166
6.5.3　 公用、私用和保护成员 167
6.6　 C++的动态存储分配 168
6.6.1　 指向对象的指针 168
6.6.2　 用建构函数和析构函数进行动态
存储分配 169
6.6.3　 链表的单元 169
6.7　 模板：参数化类型 172
6.8　 C++对象的实现 173
6.8.1　 一个简单实现 173
6.8.2　 函数体的在线展开 174
6.8.3　 类声明中的私用变量 174
练习 175
引文注记 178
第7章　 面向对象程序设计 179
7.1　 什么是对象 179
7.1.1　 对象的外部和内部视图 179
7.1.2　 形状的属性 180
7.2　 面向对象的思想 181
7.2.1　 将对象组织为类层次结构 181
7.2.2　 对象响应消息，对象具有状态 182
7.3　 继承 184
7.3.1　 接收者决定一个消息的含义 185
7.3.2　 信息隐藏是为了可扩充性 186
7.3.3　 添加子类 187
7.3.4　 对象和类 189
7.4　 用C++语言做面向对象的程序设计 189
7.4.1　 C++语言回顾 189
7.4.2　 基类和派生类 190
7.4.3　 公用基类 190
7.4.4　 虚函数 191
7.4.5　 C++中形状实例的细节 193
7.4.6　 初始化和继承 194
7.5　 一个扩充的C++例子 194
7.5.1　 素数筛 194
7.5.2　 基类 196
7.5.3　 派生类 196
7.5.4　 基类和派生类的初始化 196
7.5.5　 子类型和超类型 197
7.5.6　 虚函数 198
7.5.7　 生成过滤器对象 199
7.5.8　 剩余的程序 199
7.6　 派生类和信息隐藏 199
7.6.1　 公用和私用的基类 200
7.6.2　 私用性原理 200
7.6.3　 继承成员的可访问性 201
7.7　 Smalltalk中的对象 202
7.7.1　 系统类 202
7.7.2　 类定义中的元素 203
7.7.3　 消息语法 205
7.8　 Smalltalk对象的self 207
7.8.1　 发送给self的消息 208
7.8.2　 发送给super的消息 208
练习 209
引文注记 212
第四部分　 函数式程序设计
第8章　 函数式程序设计的要素 215
8.1　 一个很小的表达式语言 215
8.1.1　 Little Quilt操作什么 215
8.1.2　 为方便而做的扩充 217
8.1.3　 评论：Little　 Quilt的设计 219
8.2　 类型：值和运算 220
8.2.1　 构造和检查值的操作 221
8.2.2　 基本类型 221
8.2.3　 类型的积 221
8.2.4　 ML中的类型 223
8.3　 函数声明 224
8.3.1　 函数作为算法 225
8.3.2　 函数声明和应用的语法 225
8.3.3　 递归函数 226
8.4　 表达式的求值方式 226
8.4.1　 最内求值 227
8.4.2　 选择性求值 227
8.4.3　 递归函数的求值 228
8.4.4　 从左到右的最外求值 228
8.4.5　 短路求值 230
8.5　 词法作用域 231
8.5.1　 val约束 231
8.5.2　 fun约束 232
8.5.3　 嵌套的约束 233
8.5.4　 同时约束 233
8.6　 类型检查 234
8.6.1　 类型推理 234
8.6.2　 类型名和类型等价 235
8.6.3　 重载：多重含义 235
8.6.4　 强制：隐式类型转换 236
8.6.5　 多态性：参数化类型 236
练习 237
引文注记 240
第9章　 一个有类型语言中的函数式
程序设计 241
9.1　 表的探查 241
9.1.1　 表上的运算 242
9.1.2　 定义在表上的两个函数：append
和reverse 242
9.2　 函数的分情况声明 244
9.2.1　 函数应用 245
9.2.2　 模式 246
9.2.3　 模式和情况分析 246
9.3　 函数作为一级的值 248
9.3.1　 将函数映射到表的各个元素上 249
9.3.2　 匿名函数 251
9.3.3　 选择性复制 251
9.3.4　 积累结果 252
9.4　 ML：隐含类型 253
9.4.1　 类型推理 253
9.4.2　 参数化多态性 254
9.5　 数据类型 254
9.5.1　 值构造符 255
9.5.2　 微分：一个传统实例 257
9.5.3　 多态数据类型 258
9.5.4　 讨论 259
9.6　 ML的异常处理 259
9.7　 在Standard ML中实现Little Quilt 261
9.7.1　 一些辅助函数 262
9.7.2　 拼块的表示 263
9.7.3　 sew运算 263
9.7.4　 turn运算 264
9.7.5　 拼块的显示 266
9.7.6　 Little　 Quilt中的表达式 267
练习 269
引文注记 271
第10章　　　表的函数式程序设计 272
10.1　 Scheme，一种Lisp方言 272
10.1.1　 为什么用Scheme 273
10.1.2　 如何与Scheme解释器交互 273
10.1.3　 怎样写表达式 274
10.1.4　 怎样定义函数 275
10.1.5　 匿名函数值 275
10.1.6　 条件式 275
10.1.7　 let结构 276
10.1.8　 引号 277
10.2　 表的结构 278
10.2.1　 表元素 278
10.2.2　 表的运算 279
10.3　 表的操作 280
10.3.1　 一个有用的函数 281
10.3.2　 连接两个表 281
10.3.3　 将函数映射到表的所有元素上 282
10.3.4　 关联表 283
10.3.5　 子表达式的表 284
10.3.6　 一个参数化的函数 285
10.4　 启发性的实例：微分 286
10.4.1　 语法制导的微分 286
10.4.2　 常量 287
10.4.3　 变量 287
10.4.4　 对和式与乘积的微分规则 287
10.4.5　 和式的微分 287
10.4.6　 乘积的微分 289
10.4.7　 对微分程序的总结 289
10.5　 表达式化简 290
10.6　 表的存储管理 292
10.6.1　 cons分配单元 293
10.6.2　 相等的概念 293
10.6.3　 分配和释放 295
练习 296
引文注记 298
第五部分　　　其他范型
第11章　 逻辑式程序设计 300
11.1　 用关系做计算 301
11.1.1　 关系 301
11.1.2　 规则和事实 301
11.1.3　 查询 302
11.2　 Prolog初步 304
11.2.1　 项 304
11.2.2　 与Prolog交互 305
11.2.3　 存在性查询 305
11.2.4　 全称性的事实和规则 306
11.2.5　 否定作为失败 307
11.2.6　 合一 308
11.2.7　 算术 309
11.3　 Prolog的数据结构 309
11.3.1　 Prolog中的表 309
11.3.2　 项作为数据 310
11.4　 程序设计技术 312
11.4.1　 猜测和验证 312
11.4.2　 用变量作为项里的占位符 314
11.4.3　 差表 317
11.5　 Prolog的控制 318
11.5.1　 合一和替换 319
11.5.2　 将规则应用于目标 320
11.5.3　 Prolog搜索树 322
11.5.4　 目标的顺序将改变解 323
11.5.5　 规则顺序影响对解的搜索 324
11.5.6　 出现检查问题 326
11.6　 割 326
11.6.1　 割作为第一个条件 327
11.6.2　 割的作用 328
11.6.3　 应用割的程序设计 329
11.6.4　 否定等同于失败 332
练习 333
引文注记 334
第12章　 并发程序设计导引 336
12.1　 硬件的并行性 336
12.1.1　 输入/输出的并行执行 336
12.1.2　 中断和分时 337
12.1.3　 多处理器组织结构 338
12.1.4　 反应式系统 338
12.2　 流：隐式的同步 338
12.2.1　 进程网络 339
12.2.2　 管道实例 339
12.3　 作为交错的并发性 340
12.3.1　 线程的交错 341
12.3.2　 Ada中的并发作业 341
12.4　 进程的活性性质 343
12.4.1　 资源共享限制并发性 343
12.4.2　 哲学家就餐问题 343
12.4.3　 死锁：无法继续 344
12.4.4　 活锁：没有进程能够取得进展 344
12.4.5　 公平性 344
12.4.6　 避免死锁的发生 345
12.5　 共享数据的安全访问 345
12.5.1　 “非确定”的进程 345
12.5.2　 临界区和互斥 346
12.5.3　 可串行化与安全性 347
12.6　 Ada中的并发性 348
12.6.1　 握手式同步 348
12.6.2　 同步通信 349
12.6.3　 有选择的接收 352
12.7　 共享变量的同步访问 353
12.7.1　 对缓冲区的直接访问 353
12.7.2　 信号量：互斥 355
练习 359
引文注记 362
第六部分　　　语言的描述
第13章　 语义方法 366
13.1　 综合属性 368
13.1.1　 求值顺序 369
13.1.2　 总结 369
13.2　 属性文法 370
13.3　 自然语义 372
13.3.1　 一个计算器 372
13.3.2　 环境为名字约束值 373
13.3.3　 let约束 373
13.3.4　 基于Prolog的实现 375
13.4　 指称语义 376
13.5　 一个Scheme计算器 377
13.6　 词法作用域中的lambda表达式 378
13.6.1　 lambda表达式的自然语义 379
13.6.2　 环境的一种实现 380
13.7　 一个解释器 381
13.7.1　 常量 381
13.7.2　 加引号项 381
13.7.3　 变量 382
13.7.4　 条件表达式 382
13.7.5　 let表达式 382
13.7.6　 lambda表达式 383
13.7.7　 函数应用 384
13.7.8　 初始化环境 384
13.7.9　 解释器的使用 385
13.8　 一个扩充：递归函数 386
13.8.1　 作为值的递归函数 386
13.8.2　 对解释器的修改 387
练习 388
引文注记 389
第14章　 静态类型和Lambda演算 390
14.1　 纯lambda演算中的相等 391
14.1.1　 语法约定 392
14.1.2　 自由变量和约束变量 392
14.1.3　 替换 393
14.1.4　 beta-相等 394
14.2　 再论替换 395
14.3　 纯lambda项的计算 396
14.3.1　 归约 397
14.3.2　 不终止的归约 398
14.3.3　 Church-Rosser定理 398
14.3.4　 计算规则 399
14.4　 作为lambda项的程序设计结构 400
14.4.1　 一个应用lambda演算 400
14.4.2　 Curry化 401
14.4.3　 常量的归约规则 401
14.4.4　 语言ML0 402
14.4.5　 不动点算子 403
14.5　 带类型的lambda演算 404
14.6　 多态类型 406
14.6.1　 取自标准ML的例子 406
14.6.2　 显式的多态性 407
14.6.3　 单态与多态 408
14.6.4　 Core-XML的类型规则 409
练习 411
引文注记 412
第15章　 语言概览 414
15.1　 Pascal：一种教学语言 414
15.1.1　 Pascal的程序结构 415
15.1.2　 声明 415
15.1.3　 类型 416
15.1.4　 表达式 416
15.1.5　 语句 416
15.2　 C：系统程序设计 417
15.2.1　 C语言程序结构 417
15.2.2　 C的函数 418
15.2.3　 C的变量声明 419
15.2.4　 表达式 419
15.2.5　 C的控制流 420
15.2.6　 指针和数组 420
15.2.7　 头文件 421
15.2.8　 标准输入/输出 422
15.3　 C++：多种程序设计风格 422
15.3.1　 C++中的类 422
15.3.2　 C++的继承 424
15.4　 Smalltalk语言 424
15.4.1　 表达式 426
15.4.2　 类和实例方法 426
15.4.3　 系统类 427
15.5　 Standard ML 428
15.5.1　 与ML解释器交互 428
15.5.2　 基于模式匹配的函数定义 430
15.5.3　 数据类型 430
15.5.4　 异常 430
15.6　 Scheme：一种Lisp方言 431
15.6.1　 基本结构 432
15.6.2　 表操作　 433
15.7　 Prolog 434
15.7.1　 项 435
15.7.2　 与Prolog交互 436
15.7.3　 规则 436
15.7.4　 查询 436
15.7.5　 算术 436
15.7.6　 作为数据的项 437
参考文献 438
索引 450