程序设计语言——实践之路 (2008 年度畅销榜NO.302 )

这是一本很有特色的教材，其核心是讨论程序设计语言的工作原理和技术。本书融合了传统的程序设计语言教科书和编译教科书的有关知识，并增加了一些有关汇编层体系结构的材料，以满足没学过计算机组织的学生们的需要。书中通过各种语言的例子，阐释了程序设计语言的重要基础概念，讨论了各种概念之间的关系，解释了语言中许多结构的形成和发展过程，以及它们演化为今天这种形式的根源。书中还详细讨论了编译器的工作方式和工作过程，说明它们对源程序做了什么，以及为什么要那样做。书的每章最后附有复习题和一些更具挑战性的练习。这些练习的特别价值在于引导学生进一步深入理解各种语言和技术。
本书在美国大学已有使用了十余年，目前被欧美许多重要大学用于“程序设计语言”或者“软件系统”课程。本书适合高年级本科生或者一年级研究生使用，许多内容对专业程序员也很有价值。本书作者Micheal Scott 是计算机领域的著名学者，译者是北京大学的裘宗燕教授，他熟悉专业，译笔流畅，是一本难得的著、译双馨的佳作。

前言 xvii
第1章 引言 1
1.1 语言设计的艺术 3
1.2 程序设计语言的谱系 5
1.3 为什么研究程序设计语言 7
1.4 编译和解释 9
1.5 程序设计环境 14
1.6 编译概览 15
1.6.1 词法和语法分析 16
1.6.2 语义分析和中间代码生成 18
1.6.3 目标代码生成 22
1.6.4 代码改进 24
1.7 总结和注记 24
1.8 复习 25
1.9 练习 26
1.10 有关参考文献 28
第2章 程序设计语言的语法 31
2.1 描述语法：正则表达式和上下文无关文法 32
2.1.1 单词和正则表达式 33
2.1.2 上下文无关文法 34
2.1.3 推导和语法分析树 36
2.2 识别语法：扫描器和语法分析器 39
2.2.1 扫描 40
2.2.2 自上而下和自下而上的语法分析 48
2.2.3 递归下降 51
2.2.4 语法错误* 57
2.2.5 表格驱动的自上而下语法分析 62
2.2.6 自下而上的语法分析 75
2.3* 理论基础 87
2.3.1 有穷自动机 88
2.3.2 下推自动机 92
2.3.3 文法和语言类 93
2.4 总结和注记 94
2.5 复习 97
2.6 练习 98
2.7 有关参考文献 102
第3章 名字、作用域和约束 105
3.1 约束时间的概念 106
3.2 对象生存期和存储管理 108
3.2.1 基于堆栈的分配 111
3.2.2 堆分配 113
3.2.3 废料收集 114
3.3 作用域规则 115
3.3.1 静态作用域 116
3.3.2 动态作用域 129
3.3.3 符号表 132
3.3.4 关联表和中心引用表列 137
3.4 引用环境的约束 139
3.4.1 子程序闭包 141
3.4.2 一级和二级子程序 143
3.5 重载和相关概念 144
3.6 语言设计中与名字有关的缺陷 149
3.6.1 作用域规则 149
3.6.2* 分别编译 151
3.7 总结和注记 155
3.8 复习 157
3.9 练习 158
3.10 有关参考文献 162
第4章 语义分析 165
4.1 语义分析器所扮演的角色 166
4.2 属性文法 168
4.3 属性流 170
4.4 动作例程 179
4.5* 属性的空间管理 180
4.5.1 自下而上求值 181
4.5.2 自上而下求值 186
4.6 语法树的标注 191
4.7 总结和注记 197
4.8 复习 198
4.9 练习 199
4.10 有关参考文献 202
第5章 汇编层计算机体系结构 203
5.1 工作站的微体系结构 204
5.2 存储器层次结构 207
5.3 数据表示 209
5.3.1 整数算术 211
5.3.2 浮点算术 212
5.4 指令集的体系结构 214
5.4.1 寻址模式 215
5.4.2 条件分支 217
5.5 处理器体系结构的演化 218
5.5.1 两个实例体系结构：680x0和MIPS 220
5.5.2 伪汇编记法形式 225
5.6 为新型处理器做编译 227
5.6.1 维持流水线满 227
5.6.2 寄存器分配 234
5.7 总结和注记 242
5.8 复习 243
5.9 练习 244
5.10 有关参考文献 247
第6章 控制流 249
6.1 表达式求值 250
6.1.1 优先级和结合性 251
6.1.2 赋值 254
6.1.3 表达式里的顺序 262
6.1.4 短路求值 265
6.2 结构化和非结构化的流程 267
6.3 顺序复合 270
6.4 选择 271
6.4.1 短路条件 272
6.4.2 分情况/开关语句 275
6.5 迭代 280
6.5.1 枚举控制的循环 280
6.5.2 组合循环 286
6.5.3* 迭代器 287
6.5.4 逻辑控制的循环 294
6.6 递归 297
6.6.1 迭代和递归 297
6.6.2 应用序和正则序求值 301
6.7* 非确定性 303
6.8 总结和注记 308
6.9 复习 310
6.10 练习 311
6.11 有关参考文献 316
第7章 数据类型 319
7.1 类型系统 320
7.1.1 类型的定义 322
7.1.2 类型的分类 323
7.2 类型检查 330
7.2.1 类型等价 330
7.2.2 类型变换和转换 334
7.2.3 类型相容和强制 337
7.2.4 类型推理 341
7.2.5 ML的类型系统 344
7.3 记录（结构）与变体（联合） 351
7.3.1 语法和操作 351
7.3.2 存储布局和紧缩 353
7.3.3 With语句 355
7.3.4 变体记录 358
7.4 数组 365
7.4.1 语法和操作 365
7.4.2 维数、上下界和分配 369
7.4.3 数组的布局 373
7.5 字符串 379
7.6 集合 381
7.7 指针和递归类型 382
7.7.1 语法和操作 383
7.7.2 悬空引用 391
7.7.3 废料收集 395
7.8 表 401
7.9* 文件和输入/输出 403
7.9.1 交互式I/O 404
7.9.2 基于文件的I/O 405
7.9.3 正文I/O 407
7.10 相等检测和赋值 414
7.11 总结和注记 416
7.12 复习 418
7.13 练习 420
7.14 有关参考文献 425
第8章 子程序和控制抽象 427
8.1 重温堆栈布局 428
8.2 调用序列 431
8.2.1 实例研究：在MIPS上实现C 434
8.2.2 实例研究：在680x0上实现Pascal 437
8.2.3 在线展开 441
8.3 参数传递 442
8.3.1 参数模式 443
8.3.2 专用的参数 453
8.3.3 函数返回 457
8.4 通用型过程和模块 459
8.5 异常处理 464
8.5.1 异常的定义 466
8.5.2 异常的传播 468
8.5.3 实例：递归下降语法分析中的短语层恢复 470
8.5.4 异常的实现 471
8.6 协作程序 474
8.6.1 堆栈分配 476
8.6.2 转移 478
8.6.3* 迭代器 479
8.6.4* 实例：离散事件模拟 480
8.7 总结和注记 484
8.8 复习 485
8.9 练习 486
8.10 有关参考文献 489
第9章 构造可运行程序 491
9.1 后端编译器结构 491
9.1.1 一个实例 492
9.1.2 阶段和遍 496
9.2 中间形式 496
9.2.1* Diana 498
9.2.2* GNU的RTL 499
9.3 代码生成 503
9.3.1 一个属性文法实例 504
9.3.2 寄存器分配 504
9.4 地址空间组织 507
9.5 汇编 510
9.5.1 指令发射 511
9.5.2 为名字指定地址 514
9.6 连接 515
9.6.1 重定位和名字解析 515
9.6.2 类型检查 516
9.7* 动态连接 518
9.7.1 与定位无关的代码 519
9.7.2 完全动态连接（惰性连接） 521
9.8 总结和注记 522
9.9 复习 523
9.10 练习 524
9.11 有关参考文献 527

第10章 数据抽象和面向对象 529
10.1 面向对象的程序设计 530
10.2 封装和继承 539
10.2.1 模块 539
10.2.2 类 542
10.2.3 类型扩展 544
10.3 初始化和终结处理 546
10.3.1 构造函数的选择 547
10.3.2 引用和值 550
10.3.3 执行顺序 551
10.3.4 废料收集 553
10.4 动态方法约束 554
10.4.1 虚函数和非虚函数 555
10.4.2 抽象类 557
10.4.3 成员查找 557
10.4.4 相关概念 561
10.5* 多重继承 564
10.5.1 语义歧义性 568
10.5.2 复本式继承 570
10.5.3 共享继承 572
10.5.4 混入式继承 573
10.6 重温面向对象的程序设计 574
10.6.1* Smalltalk的对象模型 577
10.7 总结和注记 580
10.8 复习 582
10.9 练习 583
10.10 有关参考文献 586
第11章 非命令式程序设计模型： 函数式和逻辑式语言 589
11.1 历史渊源 590
11.2 函数式程序设计 592
11.2.1 Scheme简介 594
11.2.2 重温求值顺序 604
11.2.3 高阶函数 609
11.2.4 理论基础 612
11.2.5 函数式程序设计展望 622
11.3 逻辑式程序设计 624
11.3.1 Prolog 625
11.3.2* 理论基础 641
11.3.3 逻辑式程序设计的展望 646
11.4 总结和注记 648
11.5 复习 650
11.6 练习 651
11.7 有关参考文献 657
第12章 并发 659
12.1 基础和动力 660
12.1.1 简单历史 660
12.1.2 多线程程序的不同情况 663
12.1.3 多处理器体系结构 667
12.2 并发程序设计基础 670
12.2.1 通信和同步 671
12.2.2 语言和库 672
12.2.3 创建线程的语法 673
12.2.4 线程的实现 682
12.3 共享存储器 687
12.3.1 忙等待同步 688
12.3.2 调度器的实现 692
12.3.3 基于调度的同步 694
12.3.4 隐式同步 703
12.4 消息传递 706
12.4.1 通信对方的命名 706
12.4.2 传送 710
12.4.3 接收 714
12.4.4 远程过程调用 719
12.5 总结和注记 722
12.6 复习 724
12.7 练习 725
12.8 有关参考文献 730
第13章 代码改进 733
13.1 代码优化的阶段 735
13.2 窥孔优化 737
13.3 基本块内的冗余删除 740
13.4 全局冗余删除和数据流分析 745
13.4.1 静态单赋值形式和全局值编号 746
13.4.2 全局公共子表达式删除 750
13.5 循环改进 I 755
13.5.1 循环不变量 755
13.5.2 归纳变量 756
13.6 指令调度 759
13.7* 循环改进 II 763
13.7.1 循环展开和软件流水线 763
13.7.2 循环重排 767
13.8 寄存器分配 775
13.9 总结和注记 778
13.10 复习 780
13.11 练习 781
13.12 有关参考文献 785
附录A 本书中提到的程序设计语言 787
附录B 语言设计和语言实现 795
参考书目 801
索引 827

Michael Scott的《Programming Language Pragmatics》是一本很有趣，也非常有价值的新教科书，它颠覆了传统意义上的“程序设计语言”课程的组织体系，其内容涵盖程序设计语言、编译技术、软件系统的许多方面，甚至延伸到硬件体系结构等许多领域。实际上，出现这一情况的根源也很明显：程序设计语言在计算机科学技术领域居于一种中心地位。程序是计算机科学技术中最核心的概念，而作为描述程序的语言，集中表现了人们由程序设计和软件开发实践中获得的最有价值、最具普遍性的认识和技术。程序设计语言下接硬件体系结构，上承丰富多彩的计算机应用需求，反映了开发者专业能力的发展和局限性，又受到实现的理论和技术的制约。这样，程序设计语言中，自然浓缩了许多相关领域中的知识和技术精华，要理解其发展和演化的现状和趋势，一定会涉及与之相关的各个领域。本书作者对与语言有关的众多领域有着深刻的认识，在其中纵横驰骋，为我们展现了一幅生动、全面，而又非常深刻的画卷。 本书系统地介绍了程序语言领域的各种基本概念，如语法和语义，数据、操作和控制，类型和抽象等等，介绍了许多有关语言处理的知识，不同的语言范型，以及相关的理论和实践情况。在学习各种语言特征时，我们还能看到今天人们对许多语言特征的评价和反思，了解为什么一些特征的设计在不断变化，看到理论和技术发展对语言形态和细节的影响。与此同时，本书还深入介绍了这个领域里的许多新发展、新问题和新技术。例如，作者用了很长的一章深入探讨了面向对象语言的问题，不仅介绍了这类语言的外在形式特征及其价值，还特别仔细地讨论了这类语言中各种新的重要机制的实现技术，例如动态方法约束，多重继承等等。书中还用很大篇幅讨论程序的静态连接和动态连接，帮助读者理解高级语言的加工和执行。作者在书中既强调了重要的概念和理论，也特别重视语言的各方面实现技术，还深入探讨了实现技术发展进步对语言的影响。应该看到，语言实现方面的许多技术都是最重要的程序技术，作者的这些想法也使本书成为一部很有价值的软件技术书籍（有趣的是，作者确实用这些材料讲授一门名为“软件系统”的课程）。 总而言之，本书在许多方面有鲜明的特色，是最新的“程序设计语言”教科书的代表。正因为这样，它出版的时间虽然不长，就已经被世界各国的许多重要大学选为“程序设计语言”或相关课程的教科书或者最重要的参考书。本书不仅值得计算机专业的本科生或者研究生学习或阅读，也值得在计算机领域中的实践工作者们阅读。对本书的学习能帮助我们理解现有的各种程序设计语言，大大提高学习和掌握新语言的能力，还能帮助我们看清隐藏在高级语言的各种机制背后的秘密，明白各种重要语言特征的价值、缺陷和使用它们的代价。对程序设计语言的深入理解，对于计算机专业工作者深刻理解相关的理论和实践，灵活高效地运用程序语言和相关工具，都可能起到非常重要的作用。 我非常赞赏电子工业出版社引进这本很有价值的著作，也很高兴能在把本书介绍给国内读者方面做一些力所能及的工作。我要感谢出版社周筠女士的远见卓识和以她为首的编辑团队的辛勤工作，还要感谢夏萍和丛欣对我的一贯支持和帮助。本书涉及的领域广泛，其中许多都不是我的专长。虽然我在翻译过程中已经尽可能地查阅了一些相关材料，但书中难免还会留下许多缺陷，希望得到同行和读者的指教。

Michael Scott的《Programming Language Pragmatics》是一本很有趣，也非常有价值的新教科书，它颠覆了传统意义上的“程序设计语言”课程的组织体系，其内容涵盖程序设计语言、编译技术、软件系统的许多方面，甚至延伸到硬件体系结构等许多领域。实际上，出现这一情况的根源也很明显：程序设计语言在计算机科学技术领域居于一种中心地位。程序是计算机科学技术中最核心的概念，而作为描述程序的语言，集中表现了人们由程序设计和软件开发实践中获得的最有价值、最具普遍性的认识和技术。程序设计语言下接硬件体系结构，上承丰富多彩的计算机应用需求，反映了开发者专业能力的发展和局限性，又受到实现的理论和技术的制约。这样，程序设计语言中，自然浓缩了许多相关领域中的知识和技术精华，要理解其发展和演化的现状和趋势，一定会涉及与之相关的各个领域。本书作者对与语言有关的众多领域有着深刻的认识，在其中纵横驰骋，为我们展现了一幅生动、全面，而又非常深刻的画卷。 本书系统地介绍了程序语言领域的各种基本概念，如语法和语义，数据、操作和控制，类型和抽象等等，介绍了许多有关语言处理的知识，不同的语言范型，

关于计算机程序设计的课程给了普通学生有关计算机领域的第一个印象。大多数学生在这样的课程之前对于计算机已经有了一些接触，例如以计算机游戏或者其他个人应用的形式，在他们还没有写出自己的程序之前，就已经开始意识到这些应用的工作方式了。在获得了作为程序员的一定能力之后（假定已经学过很好的有关数据结构和算法的课程），很自然的下一步就是想知道程序设计语言是如何工作的。本书将对此提供一个解释。 在常规的有关“系统”的教学计划里，数据结构（或者再加上计算机组织）之后的内容被分门别类归入属于一些子领域的一批课程，如程序设计语言、编译、计算机体系结构、操作系统、数据库管理系统，可能还有软件工程、图形学或者用户界面系统。这种安排方式存在一个缺点：有关计算机科学的最有趣的东西，许多都处于这些子领域的边界上。例如，RISC革命推动了计算机体系结构和编译器构造之间的结盟，微内核的出现使得操作系统和语言运行库之间的界限变得模糊起来，基于Java的系统以类似形式模糊了编译器和运行库之间的分野。超级计算机里功能强大的存储器系统正在重新定义操作系统、编译器和硬件之间的相对作用。而程序设计语言的设计也始终受到实现问题的重要影响。越来越多的教育工作者和研究者逐渐认识到关注这些相互关系的重要性。 分门别类的教学计划的另一个问题是提供的课程太多，本科学生没有足够时间去学完它们。如果一个学生希望在理论、人工智能、数值方法或者其他独立领域里打下坚实的基础，那么就可能没时间去上5门系统方面的高级课程。我的认识是，与给予学生对两个或者三个子领域的深入讨论相比，集中提供一些横跨这些子领域的最基本材料可能更有意义。 《程序设计语言——实践之路》一书的核心，就是讨论程序设计语言如何工作的问题。从某种角度看，它是程序设计语言和编译的传统教科书的混合，再加上一些有关汇编层体系结构的材料，以满足那些没有学过计算机组织的学生的需要。它不是综述性的语言教科书，其中没有列举许多不同语言的细节，而是集中关注学生们可能遇到的作为所有语言之基础的一批概念，并通过各种语言的例子阐释这些概念。它也不是一本有关编译器构造的教科书，其中没有去解释如何构造一个编译器（那只是很少数的程序员最终需要整个参与的一种工作，虽然许多其他工具也会使用其前端技术），而是解释编译器如何工作，它对源程序做了什么事情，以及为什么要那样做。语言的设计和实现在这里被放在一起考察，其中特别强调它们之间相互作用的各种方式。在讨论迭代的时候（6.5.1节），我们可以看到语义问题（什么是指标变量的作用域？如果循环的体要修改循环指标或者界的时候会出现什么问题？）与实际的问题（循环的每次迭代中必须执行多少条分支指令？更新指标时如何避免算术溢出）相互作用，造就了循环结构的演化和发展。在讨论面向对象的程序设计时，我们可以看到在语义优雅与实现速度之间的紧张关系，看到它怎样影响着如Smalltalk、Eiffel、C++和Java等语言的设计。 在典型的本科生教学计划里，我们希望将本书用于程序设计语言课程。与其他教科书相比，这本书中稍微少了一点综述风格的细节，但也覆盖了同样广泛的语言和概念，并包含了更多有关实现问题的信息。对于那些在语言设计方面有强烈兴趣的学生，可以鼓励他们去进一步学习形式语义、类型理论或者面向对象的设计方面的课程。对那些在语言实现方面有着强烈兴趣的学生，应该鼓励他们去学习编译器构造方面的进一步课程。有了这本书作基础，有关编译器的课程就可以把更多的时间用在代码生成和优化方面，这些问题也是今天的大部分有趣工作之所在。 在Rochster大学里，本书的材料已经被使用了十多年，用于教授一门名为“软件系统”的课程。这一课程吸引着中高年级的本科生和一年级的研究生。本书对于专业程序员和其他实际工作者也同样很有价值，如果他们希望对自己所喜爱的程序设计语言“背后”的情况有一个更好的理解。通过把有关语法、语义和实际（实现）方面的问题集中到一起讨论，本书企图对语言的设计问题提供一个比其他教科书更完整和平衡的处理，希望能帮助学生理解为什么各种语言特征被设计成现在的样子，使程序员能针对具体应用选择合适的语言，更容易学好新的语言，更清晰高效地使用任何语言。 在多数章的最后作为总结的一节里，我们都回到了有关设计与实现的问题，其中特别强调两者在前面各节里所表现出的相互作用。此外，附录B列出了一个表，总结了这些相互作用，其中还包括了讨论它们的章节索引。这些相互作用被分为几类，包括今天的大多数语言设计师认为是错误的语言特征，至少部分原因是实现很困难；一些可能有用的特征在有些语言里没有，主要是考虑它们的实现可能很困难或者很慢；某些语言特征被引入，至少部分地是由于它们能高效而优美地实现等等。 有些章（第2、4、5、9和13章）比其他的章更着重强调实现问题。这些章与其他更多关注语言设计的章之间的顺序可以在一定限度内调整，但一定要保证第5章或者与之相当的内容出现在第6、7、8章之前。许多读者可能已经熟悉了第5章的大部分或者全部材料，多半是来自一个有关计算机组织的课程。在这种情况下就可以简单地跳过这一章。请注意，后面各章都假定了对于新型（即RISC）微处理器的汇编层体系结构的理解。有些读者可能已经熟悉了第2章的一些材料，可能是来自一门有关自动机的课程。在这种情况下，该章的内容可以很快读过去，只是可能要在某些实际问题上（例如从语法错误中恢复）多停留一下。 作为自学，或者作为一个整整一年的课程，我建议从头到尾使用这本书。在Rochster作为一学期的课程时，我们也覆盖了本书的大部分内容。课程里集中讨论教师们从下面章节里选出的材料：第1章，1.2节到2.2.3节，第3、4、6、7、8章，9.1到9.3节，第10到第12章。同时要求学生阅读本书里所有材料，除了标星号的各节。还要求他们跳过第5章，主要是因为已经学过有关计算机组织的课程。 如果作为更传统的程序设计语言课程，那么可以排除2.2节和第4、5、9章，减少对其他章节里与实现有关的材料的重视程度，把更多时间用到仔细考察语义问题和不同的程序设计范型（例如，第11章里的一些理论基础材料）。对那些采用4学期制的学校，一种明显选择方案是开一学期的导引性课程和两个随后的选修课程。导引性课程可以覆盖下面章节：第1章，2.1节到2.2.3节，第3、6、7章，8.1节到8.4节。后一学期的面向语言的课程可以覆盖8.5节到8.6节，第10到12章，以及另外的有关形式语义学、类型系统或其他相关论题的补充材料。后一学期面向编译器的课程可以包含2.2.4节到2.3节，第4、5（如果需要）、9和13章，以及某些有关自动代码生成、更富进取性的代码优化、程序设计工具等等方面的材料。对这种安排的反对意见可能是认为它没有把有关面向对象、函数式和逻辑式程序设计的内容包括在导引部分。另一种选择就是从更广更具针对性的基于设计的观点出发，把1.4节到1.6节和2.2.1节到2.2.3节移到面向编译器的课程中，减少第6章到第8章里与实现有关的材料，加入10.1节到10.4节和10.6节，以及第11章里理论基础之外的部分。 我假定典型的读者已经对至少一种高级命令式程序设计语言有了相当的经验。具体是哪种语言并没有关系。书中例子取自各种不同的语言，但总是带有足够的说明和其他讨论，使不熟悉该语言的读者也能比较容易地理解它们。在需要时，算法都是采用自明的非形式的伪代码给出。真正的程序设计语言代码用的字体是this font（Computer Modern），伪代码用的字体是this font（UniversLight）。 每章最后都有一些复习题和一些更具挑战性的练习。这些练习的特别价值在于引导学生理解各种语言或者技术，其中许多都是他们不大会在其他地方遇到的，或者不会很快遇到的。我建议程序设计作业用C++或者Java；Scheme、ML或者Haskell；以及Prolog。布置一个有关异常处理的题目也是非常好的想法，它可以用Ada、C++、Java、ML或者Modula-3写。如果课程里包含了并行性，作业应该在SR、Java、Ada或者Modula-3里给，可以根据本地的条件选择。在附录A里给出了各种语言实现的资源信息。 除了这种小型课题之外（或者在那些希望的地方），教师还可能希望学生做一些语言实现方面的工作。由于从空白开始做一个小编译器也是一个学期的工作，Rochester采用的方式是给学生提供能工作的编译器的代码，要求他们做些修改。对于其中的许多人，这是他们第一次阅读、理解和修改一个大的实在的程序——就其本身而言也是非常有价值的练习。Rochester的PL/0编译器把一个归功于Wirth [Wir76，307-347页] 的小语言翻译到MIPS I汇编语言，这一汇编语言被广泛认为是商品的RISC指令集中“最友好的”。威斯康星大学计算机系提供了一个非常好的MIPS解释器（“SPIM”，www.cs.wisc.edu/~larus.spim.html）。编译器本身可以从Rochester得到（ftp://ftp.cs.rochester.edu/pub/packages/plzero/）。它是用C++写的，仔细划分了各个编译阶段，并有很详尽的文档。