从为什么学习程序设计语言入手，深入细致地讲解了命令式语言的主要结构及其设计与实现，内容涉及变量、数据类型、表达式和赋值语句、控制语句、子程序、数据抽象机制、对面向对象程序设计的支持（继承和动态方法绑定）、并发、异常处理和事件处理等方面。

第1章　预备知识1
1.1　学习程序设计语言原理的原因2
1.2　程序设计领域5
1.3　语言评估标准7
1.4　影响语言设计的因素17
1.5　程序设计语言的分类20
1.6　语言设计中的权衡21
1.7　实现方法22
1.8　程序设计环境29
小结·复习题·习题30
第2章　主要程序设计语言发展简史33
2.1　Zuse研制的Plankalkül语言36
2.2　伪代码37
2.3　IBM 704计算机和Fortran40
2.4　函数式程序设计语言：Lisp45
2.5　迈向成熟的第一步：ALGOL 6050
2.6　计算机化的商业记录：COBOL56
2.7　分时处理的开始：Basic61
访谈：Alan Cooper—用户设计与语言设计64
2.8　满足所有人的需求：PL/I66
2.9　两种早期的动态语言：APL 和SNOBOL69
2.10　数据抽象的开端：SIMULA 6770
2.11　正交设计：ALGOL 6871
2.12　ALGOL系列语言的早期后代语言73
2.13　基于逻辑的程序设计：Prolog77
2.14　历史上规模最大的语言设计工作：Ada79
2.15　面向对象程序设计：Smalltalk83
2.16　结合命令式和面向对象的特性：C++85
2.17　基于命令式的面向对象语言：Java89
2.18　脚本语言92
2.19　.NET旗舰语言：C#98
2.20　混合标记程序设计语言100
小结·文献注记·复习题·习题·程序设计练习102
第3章　语法和语义描述109
3.1　概述110
3.2　语法描述的一般问题111
3.3　语法描述的形式化方法113
3.4　属性文法128
历史注记128
3.5　描述程序的含义：动态语义134
历史注记142
小结·文献注记·复习题·习题155
第4章　词法和语法分析161
4.1　概述162
4.2　词法分析163
4.3　语法分析问题171
4.4　递归下降的语法分析175
4.5　自底向上的语法分析183
小结·复习题·习题·程序设计练习191
第5章　名字、绑定和作用域197
5.1　概述198
5.2　名字199
历史注记199
5.3　变量200
5.4　绑定的概念203
5.5　作用域211
5.6　作用域和生存期222
5.7　引用环境223
5.8　命名常量224
小结·复习题·习题·程序设计练习227
第6章　数据类型235
6.1　概述236
6.2　基本数据类型238
6.3　字符串类型242
历史注记243
6.4　枚举类型247
6.5　数组类型250
历史注记251
历史注记251
6.6　关联数组261
6.7　记录类型263
6.8　元组类型266
6.9　列表类型268
6.10　联合类型270
6.11　指针和引用类型273
历史注记276
6.12　可选类型285
6.13　类型检查286
6.14　强类型化287
6.15　类型等价288
6.16　理论和数据类型292
小结·文献注记·复习题·习题·程序设计练习294
第7章　表达式和赋值语句301
7.1　概述302
7.2　算术表达式302
7.3　重载运算符311
7.4　类型转换313
历史注记315
7.5　关系表达式和布尔表达式316
历史注记316
7.6　短路求值318
7.7　赋值语句319
历史注记323
7.8　混合方式赋值324
小结·复习题·习题·程序设计练习324
第8章　语句级控制结构329
8.1　概述330
8.2　选择语句332
8.3　迭代语句343
8.4　无条件分支355
历史注记356
8.5　防护命令356
8.6　结论359
小结·复习题·习题·程序设计练习360
第9章　子程序365
9.1　概述366
9.2　子程序基础366
9.3　子程序的设计问题374
9.4　局部引用环境375
9.5　参数传递方法376
历史注记384
历史注记384
9.6　子程序作为参数392
历史注记394
9.7　子程序间接调用394
9.8　函数设计问题396
9.9　重载子程序397
9.10　类属子程序398
9.11　用户定义的重载运算符404
9.12　闭包405
9.13　协同程序407
小结·复习题·习题·程序设计练习410
第10章　子程序实现417
10.1　调用和返回的一般语义418
10.2　“简单”子程序的实现419
10.3　具有栈动态局部变量的子程序实现421
10.4　嵌套子程序429
10.5　程序块436
10.6　动态作用域的实现437
小结·复习题·习题·程序设计练习441
第11章　抽象数据类型和封装结构447
11.1　抽象的概念448
11.2　数据抽象概述449
11.3　抽象数据类型的设计问题452
11.4　语言示例453
访谈：Bjarne Stroustrup—C++的诞生、广泛应用及受到的质疑454
11.5　参数化的抽象数据类型466
11.6　封装结构471
11.7　命名封装474
小结·复习题·习题·程序设计练习478
第12章　对面向对象程序设计的支持483
12.1　概述484
12.2　面向对象程序设计485
12.3　面向对象语言的设计问题489
12.4　特定语言对面向对象程序设计的支持494
访谈：Bjarne Stroustrup—关于程序设计范型和更好的程序设计 498
12.5　面向对象结构的实现519
12.6　反射522
小结·复习题·习题·程序设计练习528
第13章　并发533
13.1　概述534
13.2　子程序级并发概述539
13.3　信号量544
13.4　管程549
13.5　消息传递551
13.6　Ada对并发机制的支持552
13.7　Java线程560
13.8　C＃线程570
13.9　函数式语言中的并发处理575
13.10　语句级并发578
小结·文献注记·复习题·习题·程序设计练习580
第14章　异常处理和事件处理587
14.1　异常处理概述588
历史注记592
14.2　C++中的异常处理594
14.3　Java中的异常处理598
14.4　Python和Ruby中的异常处理605
14.5　事件处理概述608
14.6　Java中的事件处理609
14.7　C#中的事件处理613
小结·文献注记·复习题·习题·程序设计练习616
第15章　函数式程序设计语言623
15.1　概述624
15.2　数学函数625
15.3　函数式程序设计语言基础628
15.4　第一个函数式程序设计语言：Lisp629
15.5　Scheme概述633
15.6　Common Lisp651
15.7　ML653
15.8　Haskell658
15.9　F#663
15.10　主要命令式语言对函数式程序设计的支持666
15.11　函数式语言和命令式语言的比较669
小结·文献注记·复习题·习题·程序设计练习671
第16章　逻辑程序设计语言679
16.1　概述680
16.2　谓词演算概述680
16.3　谓词演算和定理证明 684
16.4　逻辑程序设计概述686
16.5　Prolog的起源688
16.6　Prolog的基本元素688
16.7　Prolog的缺点703
16.8　逻辑程序设计的应用709
小结·文献注记·复习题·习题·程序设计练习710
参考文献715



Contents
Chapter 1 Preliminaries 1
1.1 Reasons for Studying Concepts of Programming Languages..............2
1.2 Programming Domains.........................................................................5
1.3 Language Evaluation Criteria...............................................................7
1.4 Influences on Language Design .........................................................17
1.5 Language Categories...........................................................................20
1.6 Language Design Trade-Offs..............................................................21
1.7 Implementation Methods....................................................................22
1.8 Programming Environments ..............................................................29
Summary . Review Questions . Problem Set ...............................................30
Chapter 2 Evolution of the Major Programming Languages 33
2.1 Zuse’s Plankalkül ...................................................................36
2.2 Pseudocodes.........................................................................................37
2.3 The IBM 704 and Fortran ..................................................................40
2.4 Functional Programming: Lisp...........................................................45
2.5 The First Step Toward Sophistication: ALGOL 60...........................50
2.6 Computerizing Business Records: COBOL.......................................56
2.7 The Beginnings of Timesharing: Basic...............................................61
Interview: ALAN COOPER—User Design and Language Design.........64
2.8 Everything for Everybody: PL/I.........................................................66
2.9 Two Early Dynamic Languages: APL and SNOBOL........................69
2.10 The Beginnings of Data Abstraction: SIMULA 67 ...........................70
2.11 Orthogonal Design: ALGOL 68 ........................................................71
2.12 Some Early Descendants of the ALGOLs..........................................73
2.13 Programming Based on Logic: Prolog ...............................................77
2.14 History’s Largest Design Effort: Ada..................................................79
2.15 Object-Oriented Programming: Smalltalk.........................................83
2.16 Combining Imperative and Object-Oriented Features: C++.............85
2.17 An Imperative-Based Object-Oriented Language: Java.....................89
2.18 Scripting Languages...........................................................92
2.19 The Flagship .NET Language: C#.....................................................98
2.20 Markup-Programming Hybrid Languages.......................................100
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises .......................102
Chapter 3 Describing Syntax and Semantics 109
3.1 Introduction.......................................................................110
3.2 The General Problem of Describing Syntax ....................................111
3.3 Formal Methods of Describing Syntax.............................................113
3.4 Attribute Grammars ..........................................................128
History Note .........................................................................128
3.5 Describing the Meanings of Programs: Dynamic Semantics...........134
History Note ..................................................................................142
Summary . Bibliographic Notes . Review Questions . Problem Set ........155
Chapter 4 Lexical and Syntax Analysis 161
4.1 Introduction....................................................................162
4.2 Lexical Analysis...............................................................163
4.3 The Parsing Problem ............................................................171
4.4 Recursive-Descent Parsing................................................................175
4.5 Bottom-Up Parsing ...........................................................183
Summary . Review Questions . Problem Set . Programming Exercises ................................191
Chapter 5 Names, Bindings, and Scopes 197
5.1 Introduction....................................................................198
5.2 Names ......................................................................199
History Note ............................................................................199
5.3 Variables..........................................................................200
5.4 The Concept of Binding ...................................................................203
5.5 Scope................................................................................211
5.6 Scope and Lifetime...........................................................222
5.7 Referencing Environments ...............................................................223
5.8 Named Constants................................................................224
Summary . Review Questions . Problem Set . Programming Exercises ..................................227
Chapter 6 Data Types 235
6.1 Introduction.....................................................................236
6.2 Primitive Data Types..............................................238
6.3 Character String Types.....................................................242
History Note ...............................................................................243
6.4 Enumeration Types ............................................................247
6.5 Array Types.........................................................................250
History Note ...........................................................................251
History Note .......................................................................251
6.6 Associative Arrays ...............................................................261
6.7 Record Types ..................................................................263
6.8 Tuple Types....................................................................266
6.9 List Types........................................................................268
6.10 Union Types .......................................................................270
6.11 Pointer and Reference Types ............................................................273
History Note ...............................................................................276
6.12 Optional Types .....................................................................285
6.13 Type Checking......................................................................286
6.14 Strong Typing.......................................................................287
6.15 Type Equivalence...................................................................288
6.16 Theory and Data Types.....................................................................292
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises ...........294
Chapter 7 Expressions and Assignment Statements 301
7.1 Introduction........................................................................302
7.2 Arithmetic Expressions.............................................................302
7.3 Overloaded Operators.......................................................................311
7.4 Type Conversions .................................................................313
History Note ...............................................................................315
7.5 Relational and Boolean Expressions .................................................316
History Note ..............................................................................316
7.6 Short-Circuit Evaluation.............................................................318
7.7 Assignment Statements .....................................................................319
History Note ............................................................................323
7.8 Mixed-Mode Assignment..................................................................324
Summary . Review Questions . Problem Set . Programming Exercises ....324
Chapter 8 Statement-Level Control Structures 329
8.1 Introduction.......................................................................330
8.2 Selection Statements ............................................................332
8.3 Iterative Statements..............................................................343
8.4 Unconditional Branching..................................................................355
History Note ...............................................................................356
8.5 Guarded Commands .........................................................................356
8.6 Conclusions ...........................................................................359
Summary . Review Questions . Problem Set . Programming Exercises ....360
Chapter 9 Subprograms 365
9.1 Introduction......................................................................366
9.2 Fundamentals of Subprograms .........................................................366
9.3 Design Issues for Subprograms.........................................................374
9.4 Local Referencing Environments .....................................................375
9.5 Parameter-Passing Methods..............................................................376
History Note ............................................................................384
9.6 Parameters That Are Subprograms ..................................................392
History Note ................................................................................394
9.7 Calling Subprograms Indirectly........................................................394
9.8 Design Issues for Functions ..............................................................396
9.9 Overloaded Subprograms..................................................................397
9.10 Generic Subprograms........................................................................398
9.11 User-Defined Overloaded Operators ...............................................404
9.12 Closures ..........................................................................405
9.13 Coroutines ..........................................................................407
Summary . Review Questions . Problem Set . Programming Exercises .....410
Chapter 10 Implementing Subprograms 417
10.1 The General Semantics of Calls and Returns...................................418
10.2 Implementing “Simple” Subprograms..............................................419
10.3 Implementing Subprograms with Stack-Dynamic Local Variables...........................421
10.4 Nested Subprograms .............................................................429
10.5 Blocks..............................................................................436
10.6 Implementing Dynamic Scoping ......................................................437
Summary . Review Questions . Problem Set . Programming Exercises .....441
Chapter 11 Abstract Data Types and Encapsulation Constructs 447
11.1 The Concept of Abstraction .............................................................448
11.2 Introduction to Data Abstraction......................................................449
11.3 Design Issues for Abstract Data Types .............................................452
11.4 Language Examples..............................................................453
Interview: BJARNE STROUSTRUP—C++: Its Birth,
Its Ubiquitousness, and Common Criticisms............................454
11.5 Parameterized Abstract Data Types..................................................466
11.6 Encapsulation Constructs..................................................................471
11.7 Naming Encapsulations ....................................................................474
Summary . Review Questions . Problem Set . Programming Exercises .....478
Chapter 12 Support for Object-Oriented Programming 483
12.1 Introduction.......................................................................484
12.2 Object-Oriented Programming ........................................................485
12.3 Design Issues for Object-Oriented Languages.................................489
12.4 Support for Object-Oriented Programming in Specific Languages ...........................494
Interview: BJARNE STROUSTRUP—On Paradigms and Better Programming..............................498
12.5 Implementation of Object-Oriented Constructs..............................519
12.6 Reflection ..........................................................................522
Summary . Review Questions . Problem Set . Programming Exercises .....528
Chapter 13 Concurrency 533
13.1 Introduction.......................................................................534
13.2 Introduction to Subprogram-Level Concurrency............................539
13.3 Semaphores...........................................................................544
13.4 Monitors ............................................................................549
13.5 Message Passing .................................................................551
13.6 Ada Support for Concurrency...........................................................552
13.7 Java Threads .....................................................................560
13.8 C# Threads..........................................................................570
13.9 Concurrency in Functional Languages.............................................575
13.10 Statement-Level Concurrency..........................................................578
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises ..........580
Chapter 14 Exception Handling and Event Handling 587
14.1 Introduction to Exception Handling ................................................588
History Note .....................................................................592
14.2 Exception Handling in C++ ..............................................................594
14.3 Exception Handling in Java...............................................................598
14.4 Exception Handling in Python and Ruby.........................................605
14.5 Introduction to Event Handling .......................................................608
14.6 Event Handling with Java .................................................................609
14.7 Event Handling in C# .......................................................................613
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises .........................616
Chapter 15 Functional Programming Languages 623
15.1 Introduction.........................................................................624
15.2 Mathematical Functions....................................................................625
15.3 Fundamentals of Functional Programming Languages ...................628
15.4 The First Functional Programming Language: Lisp .......................629
15.5 An Introduction to Scheme...............................................................633
15.6 Common Lisp............................................................................651
15.7 ML .......................................................................................653
15.8 Haskell ..................................................................................658
15.9 F# ............................................................................663
15.10 Support for Functional Programming in Primarily Imperative Languages ....................666
15.11 A Comparison of Functional and Imperative Languages.................669
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises ...........................671
Chapter 16 Logic Programming Languages 679
16.1 Introduction.................................................................680
16.2 A Brief Introduction to Predicate Calculus ......................................680
16.3 Predicate Calculus and Proving Theorems ......................................684
16.4 An Overview of Logic Programming................................................686
16.5 The Origins of Prolog.......................................................................688
16.6 The Basic Elements of Prolog ..........................................................688
16.7 Deficiencies of Prolog .......................................................................703
16.8 Applications of Logic Programming.................................................709
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises .......710
Bibliography ............................................................................715