第0章 绪论 1
0.1 语言的一般性质 1
0.2 程序设计语言的一般性质 3
0.3 为什么要研究程序设计语言 5
0.4 程序设计语言定义与处理器 7
0.5 21世纪程序设计语言的发展及未来发展趋势 8
0.6 本书的目的与组织 10
第1章 历史的回顾与程序设计语言分类 11
1.1 程序设计语言简史 11
1.1.1 20世纪50年代高级语言出现 11
1.1.2 20世纪60年代奠基性研究 12
1.1.3 20世纪70年代完善的软件工程工具 14
1.1.4 20世纪80年代的面向对象发展 18
1.1.5 20世纪90年代网络计算语言 19
1.2 程序设计语言的分类 21
1.2.1 按对机器依赖程度 21
1.2.2 按应用领域 21
1.2.3 按实现计算方式 22
1.2.4 按使用方式 22
1.2.5 按程序设计范型 22
1.2.6 按断代划分 23
1.3 本章小结 24
习题 24
第2章 程序设计语言的设计概述 27
2.1 表示与抽象（representation&abstraction） 27
2.1.1 上层抽象可用多种下层抽象实现程序设计的四个世界 28
2.1.2 显式表示和隐式表示 28
2.1.3 聚合表示和分散表示 29
2.2 程序设计语言的设计目标 29
2.3 设计准则 30
2.4 程序设计语言的规格说明 33
2.4.1 语法的规格说明 33
2.4.2 语义规格说明 39
2.4.3 上下文规格说明 42
2.5 小结 42
习题 43
第3章 值与类型 45
3.1 值 45
3.1.1 值与类型 46
3.1.2 字面量、变量与常量 46
3.1.3 程序中的求值方式 47
3.1.4 值应是头等程序对象 48
3.2 类型 49
3.2.1 基本类型 49
3.2.2 复合类型 51
3.2.3 递归类型 58
3.2.4 类型系统初步 61
3.3 表达式 65
3.3.1 表达式表示法 65
3.3.2 表达式种类 66
3.3.3 优先级和结合性 68
3.3.4 类型兼容性 69
3.4 小结 70
习题 70
第4章 存储 74
4.1 程序变量的时、空特性 74
4.1.1 引用和指针 74
4.1.2 递引用 75
4.1.3 变量的时态 76
4.1.4 可存储值 77
4.2 组织存储对象的存储模型 78
4.2.1 存储对象的生命期 78
4.2.2 静态存储对象 78
4.2.3 动态存储对象 79
4.2.4 动态堆栈存储 80
4.2.5 动态堆存储 82
4.3 悬挂引用 84
4.4 变量更新 85
4.4.1 变量初始化 85
4.4.2 动态更新 86
4.5 有副作用的表达式 87
4.5.1 块表达式 88
4.5.2 命令表达式 88
4.6 小结 88
习题 89
第5章 束定 94
5.1 名字与束定 94
5.2 各种束定机制 95
5.2.1 静态束定 95
5.2.2 动态束定 95
5.2.3 块结构束定 96
5.2.4 无类型语言的束定 97
5.3 声明 98
5.3.1 声明的种类 99
5.3.2 声明的作用域 102
5.3.3 块声明 103
5.4 束定的作用域与释义 103
5.4.1 束定与环境 104
5.4.2 词法作用域与动态作用域 104
5.4.3 词法作用域和动态作用域的求值差异 106
5.4.4 作用域与生命期匹配的问题 107
5.5 束定机制与语言翻译器 107
5.6 小结 108
习题 109
第6章 函数和过程 112
6.1 函数和过程抽象 112
6.1.1 函数定义与引用 112
6.1.2 过程定义与调用 115
6.1.3 无参过程 117
6.2 参数机制 117
6.2.1 传值调用 118
6.2.2 传名调用 119
6.2.3 引用调用 120
6.2.4 参数模式与返回调用 121
6.2.5 值——返回调用 122
6.2.6 指针参数 122
6.3 变元求值策略 124
6.4 高阶函数 126
6.4.1 函数作为变元 126
6.4.2 函数作为返回值 128
6.5 小结 129
习题 130
第7章 程序控制 133
7.1 一般概述 133
7.2 顺序控制 134
7.3 条件选择控制 136
7.3.1 结构式条件控制 136
7.3.2 case和switch 137
7.3.3 以条件表达式实现选择控制 138
7.4 迭代控制 138
7.4.1 显式迭代控制 139
7.4.2 隐式迭代控制 143
7.5 异常处理 145
7.5.1 异常定义与异常处理段 145
7.5.2 异常引发与异常传播 146
7.6 小结 149
习题 150
第8章 程序的抽象与封装 153
8.1 模块和包 154
8.1.1 模块的一般形式 154
8.1.2 模块程序的结构 156
8.2 抽象数据类型 157
8.2.1 数据抽象与抽象数据类型 157
8.2.2 利用抽象数据类型构造新类型 158
8.2.3 构造函数和析构函数 160
8.2.4 以分别编译文件实现抽象数据类型 161
8.3 类属 163
8.3.1 类属定义一般形式 164
8.3.2 类属参数 165
8.3.3 类属实现的静态性 166
8.4 对象和类 166
8.4.1 对象 168
8.4.2 类和实例 168
8.5 小结 170
习题 170
第9章 类型系统 173
9.1 类型表示和实现 173
9.1.1 有限类型 174
9.1.2 约束类型 174
9.1.3 指针类型 175
9.1.4 复合类型 176
9.2 复合对象上的操作 181
9.2.1 构造子 181
9.2.2 选择子 183
9.2.3 用户定义的构造子和析构子 184
9.2.4 复合对象操作之间的关系 185
9.2.5 对类型的操作 186
9.3 类型的语义 187
9.3.1 域的一致性 188
9.3.2 构造域的一致性 189
9.3.3 类型的换型、变换和强制 192
9.4 类型检查 195
9.5 类属域 199
9.5.1 类型的多态性 199
9.5.2 类属多态的类别 200
9.5.3 设定多态 202
9.5.4 通用多态 204
9.5.5 多类型 206
9.6 类型推理 208
9.6.1 单态类型推理 209
9.6.2 多态类型推理 209
9.7 小结 209
习题 211
第10章 面向对象程序设计语言 215
10.1 Smalltalk语言 215
10.1.1 Smalltalk系统 216
10.1.2 用户界面模型 216
10.1.3 语言核心 217
10.1.4 Smalltalk文件系统与虚机 221
10.1.5 Smalltalk程序设计范型 222
10.1.6 Smalltalk程序设计系统 226
10.2 Smalltalk的对象、类、方法的实现 228
10.2.1 类的存储 228
10.2.2 实例对象的存储 229
10.2.3 活动记录 229
10.3 面向对象的基本特征 230
10.3.1 封装与继承带来的问题 231
10.3.2 强类型语言的动态多态问题 232
10.4 Ada95的面向对象机制 234
10.4.1 定义类和实例对象 234
10.4.2 以类宽类型实现多态 236
10.4.3 扩充程序包机制实现继承的类体系 238
10.4.4 其他面向对象扩充 240
10.5 Eiffel 241
10.5.1 Eiffel的对象 242
10.5.2 抽象数据类型 242
10.5.3 Eiffel的类和程序运行 244
10.5.4 Eiffel的继承与多态 248
10.5.5 指定动态类型和动态束定 251
10.6 java语言的面向对象机制 253
10.6.1 java基于C＋＋的面向对象特征的改进 253
10.6.2 Java的面向对象技术 257
10.7 小结 262
习题 263
第11章 函数式程序设计语言 266
11.1 过程式语言存在的问题 266
11.1.1 易变性难于数学模型 266
11.1.2 顺序性更难于数学模型 267
11.1.3 理想的改变途径 267
11.2 λ演算 268
11.2.1 术语和表示法 269
11.2.2 约束变量和自由变量 270
11.2.3 基本函数 270
11.2.4 归约与范式 271
11.2.5 Church-Rosser定理 274
11.2.6 增强λ演算 275
11.3 函数式语言怎样克服命令式语言的缺点 277
11.3.1 消除赋值 277
11.3.2 以递归代替while_do 278
11.3.3 消除顺序 279
11.3.4 输出问题 280
11.4 函数式语言Miranda 281
11.4.1 数据结构 281
11.4.2 内定义操作 283
11.4.3 定义函数 283
11.4.4 表闭包 285
11.4.5 无限表 287
11.5 问题与讨论 287
11.5.1 模拟状态不易 287
11.5.2 效率还是问题 288
11.5.3 并发性 288
11.6 小结 289
习题 289
第12章 逻辑式程序设计语言 294
12.1 谓词演算 294
12.1.1 谓词演算诸元素 294
12.1.2 谓词演算的等价变换 296
12.2 自动定理证明 297
12.2.1 证明系统 297
12.2.2 模型 298
12.2.3 证明技术 298
12.2.4 归结定理证明 300
12.2.5 Horn子句实现超级归结 301
12.3 逻辑程序的风格 302
12.4 典型逻辑程序设计语言Prolog 303
12.4.1 Prolog的环境 303
12.4.2 数据对象和项 303
12.4.3 Prolog程序结构 304
12.4.4 封闭世界内的演绎过程 306
12.4.5 函数和计算 306
12.4.6 cut和not谓词 308
12.5 Prolog评价 310
12.6 小结 311
习题 312
第13章 程序的并发性和进程交互原语 316
13.1 基本概念 316
13.1.1 程序与进程 317
13.1.2 并行程序的模式 317
13.1.3 线程与进程 318
13.1.4 原子动作 319
13.1.5 进程交互 320
13.2 并发程序带来的问题 321
13.2.1 速度依赖 321
13.2.2 输入值依赖 321
13.2.3 不确定性 322
13.2.4 死锁（deadlock） 322
13.2.5 死等（starvation） 322
13.3 并发程序的性质 323
13.4 低级并发机制和并发原语 323
13.4.1 基于共享变量的同步机制 323
13.4.2 基于通信的原语 330
13.5 小结 331
习题 332
第14章 进程交互机制和并发程序设计语言 334
14.1 基于变量共享的高层并发机制 334
14.1.1 条件临界区 334
14.1.2 监控器 337
14.1.3 路径表达式 343
14.2 基于信息传递的高层并发机制 344
14.2.1 异步信息传递 344
14.2.2 同步消息传递 348
14.3 远程过程调用和会合 354
14.3.1 远程过程调用RPC 355
14.3.2 会合 357
14.3.3 Ada的任务 359
14.4 多原语的并发机制 363
14.4.1 进程交互主要技术的回顾 363
14.4.2 多原语并发程序表示法 364
14.4.3 SR语言 366
14.5 并发程序设计语言 367
14.6 小结 370
习题 372
第15章 描述性程序设计语言 375
15.1 概述 375
15.2 置标语言 378
15.2.1 SGML 379
15.2.2 HTML 385
15.2.3 XML 388
15.3 脚本语言 395
15.3.1 JavaScript 396
15.3.2 Perl 403
15.3.3 PHP 405
15.3.4 C Shell 408
15.4 小结 409
习题 410
第16章 指称语义的原理与应用 412
16.1 指称语义原理 412
16.1.1 语义函数和辅助函数 412
16.1.2 语义域 415
16.1.3 命令式语言的特殊域 416
16.2 指称语义示例 418
16.2.1 过程式小语言IMP 419
16.2.2 IMP的语义域、语义函数和辅助函数 419
16.2.3 IMP的指称语义 420
16.3 程序抽象的语义描述 422
16.3.1 函数抽象 423
16.3.2 过程抽象 424
16.3.3 参数机制的语义描述 425
16.4 复合类型 427
16.4.1 最简单的复合变量的语义描述 428
16.4.2 数组变量的语义描述 430
16.5 程序失败的语义描述 433
16.6 指称语义应用 433
16.6.1 指称语义用于设计语言 434
16.6.2 指称语义用于程序性质研究 437
16.6.3 语义原型 440
16.7 小结 443
习题 444
第17章 代数语义学 448
17.1 代数基础 448
17.1.1 抽象代数 448
17.1.2 ∑-代数 451
17.1.3 全等类 454
17.1.4 泛同构映射 456
17.2 代数规格说明 457
17.2.1 Sp代数公理 459
17.2.2 隐式算子与条件公理 459
17.2.3 保留、完整性和一致性 461
17.3 数据类型的代数规格说明 461
17.3.1 简单类型的代数规格说明 462
17.3.2 参数化规格说明 464
17.4 λ演算的代数规格说明 469
17.5 小结 471
附录 472
参考文献 500