第1章　預(yù)備知識(shí)1
1.1　學(xué)習(xí)程序設(shè)計(jì)語言原理的原因2
1.2　程序設(shè)計(jì)領(lǐng)域5
1.3　語言評(píng)估標(biāo)準(zhǔn)7
1.4　影響語言設(shè)計(jì)的因素17
1.5　程序設(shè)計(jì)語言的分類20
1.6　語言設(shè)計(jì)中的權(quán)衡21
1.7　實(shí)現(xiàn)方法22
1.8　程序設(shè)計(jì)環(huán)境29
小結(jié)·復(fù)習(xí)題·習(xí)題30
第2章　主要程序設(shè)計(jì)語言發(fā)展簡史33
2.1　Zuse研制的Plankalkül語言36
2.2　偽代碼37
2.3　IBM 704計(jì)算機(jī)和Fortran40
2.4　函數(shù)式程序設(shè)計(jì)語言：Lisp45
2.5　邁向成熟的第一步：ALGOL 6050
2.6　計(jì)算機(jī)化的商業(yè)記錄：COBOL56
2.7　分時(shí)處理的開始：Basic61
訪談：Alan Cooper—用戶設(shè)計(jì)與語言設(shè)計(jì)64
2.8　滿足所有人的需求：PL/I66
2.9　兩種早期的動(dòng)態(tài)語言：APL 和SNOBOL69
2.10　數(shù)據(jù)抽象的開端：SIMULA 6770
2.11　正交設(shè)計(jì)：ALGOL 6871
2.12　ALGOL系列語言的早期后代語言73
2.13　基于邏輯的程序設(shè)計(jì)：Prolog77
2.14　歷史上規(guī)模最大的語言設(shè)計(jì)工作：Ada79
2.15　面向?qū)ο蟪绦蛟O(shè)計(jì)：Smalltalk83
2.16　結(jié)合命令式和面向?qū)ο蟮奶匦裕篊++85
2.17　基于命令式的面向?qū)ο笳Z言：Java89
2.18　腳本語言92
2.19　.NET旗艦語言：C#98
2.20　混合標(biāo)記程序設(shè)計(jì)語言100
小結(jié)·文獻(xiàn)注記·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)102
第3章　語法和語義描述109
3.1　概述110
3.2　語法描述的一般問題111
3.3　語法描述的形式化方法113
3.4　屬性文法128
歷史注記128
3.5　描述程序的含義：動(dòng)態(tài)語義134
歷史注記142
小結(jié)·文獻(xiàn)注記·復(fù)習(xí)題·習(xí)題155
第4章　詞法和語法分析161
4.1　概述162
4.2　詞法分析163
4.3　語法分析問題171
4.4　遞歸下降的語法分析175
4.5　自底向上的語法分析183
小結(jié)·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)191
第5章　名字、綁定和作用域197
5.1　概述198
5.2　名字199
歷史注記199
5.3　變量200
5.4　綁定的概念203
5.5　作用域211
5.6　作用域和生存期222
5.7　引用環(huán)境223
5.8　命名常量224
小結(jié)·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)227
第6章　數(shù)據(jù)類型235
6.1　概述236
6.2　基本數(shù)據(jù)類型238
6.3　字符串類型242
歷史注記243
6.4　枚舉類型247
6.5　數(shù)組類型250
歷史注記251
歷史注記251
6.6　關(guān)聯(lián)數(shù)組261
6.7　記錄類型263
6.8　元組類型266
6.9　列表類型268
6.10　聯(lián)合類型270
6.11　指針和引用類型273
歷史注記276
6.12　可選類型285
6.13　類型檢查286
6.14　強(qiáng)類型化287
6.15　類型等價(jià)288
6.16　理論和數(shù)據(jù)類型292
小結(jié)·文獻(xiàn)注記·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)294
第7章　表達(dá)式和賦值語句301
7.1　概述302
7.2　算術(shù)表達(dá)式302
7.3　重載運(yùn)算符311
7.4　類型轉(zhuǎn)換313
歷史注記315
7.5　關(guān)系表達(dá)式和布爾表達(dá)式316
歷史注記316
7.6　短路求值318
7.7　賦值語句319
歷史注記323
7.8　混合方式賦值324
小結(jié)·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)324
第8章　語句級(jí)控制結(jié)構(gòu)329
8.1　概述330
8.2　選擇語句332
8.3　迭代語句343
8.4　無條件分支355
歷史注記356
8.5　防護(hù)命令356
8.6　結(jié)論359
小結(jié)·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)360
第9章　子程序365
9.1　概述366
9.2　子程序基礎(chǔ)366
9.3　子程序的設(shè)計(jì)問題374
9.4　局部引用環(huán)境375
9.5　參數(shù)傳遞方法376
歷史注記384
歷史注記384
9.6　子程序作為參數(shù)392
歷史注記394
9.7　子程序間接調(diào)用394
9.8　函數(shù)設(shè)計(jì)問題396
9.9　重載子程序397
9.10　類屬子程序398
9.11　用戶定義的重載運(yùn)算符404
9.12　閉包405
9.13　協(xié)同程序407
小結(jié)·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)410
第10章　子程序?qū)崿F(xiàn)417
10.1　調(diào)用和返回的一般語義418
10.2　“簡單”子程序的實(shí)現(xiàn)419
10.3　具有棧動(dòng)態(tài)局部變量的子程序?qū)崿F(xiàn)421
10.4　嵌套子程序429
10.5　程序塊436
10.6　動(dòng)態(tài)作用域的實(shí)現(xiàn)437
小結(jié)·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)441
第11章　抽象數(shù)據(jù)類型和封裝結(jié)構(gòu)447
11.1　抽象的概念448
11.2　數(shù)據(jù)抽象概述449
11.3　抽象數(shù)據(jù)類型的設(shè)計(jì)問題452
11.4　語言示例453
訪談：Bjarne Stroustrup—C++的誕生、廣泛應(yīng)用及受到的質(zhì)疑454
11.5　參數(shù)化的抽象數(shù)據(jù)類型466
11.6　封裝結(jié)構(gòu)471
11.7　命名封裝474
小結(jié)·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)478
第12章　對(duì)面向?qū)ο蟪绦蛟O(shè)計(jì)的支持483
12.1　概述484
12.2　面向?qū)ο蟪绦蛟O(shè)計(jì)485
12.3　面向?qū)ο笳Z言的設(shè)計(jì)問題489
12.4　特定語言對(duì)面向?qū)ο蟪绦蛟O(shè)計(jì)的支持494
訪談：Bjarne Stroustrup—關(guān)于程序設(shè)計(jì)范型和更好的程序設(shè)計(jì) 498
12.5　面向?qū)ο蠼Y(jié)構(gòu)的實(shí)現(xiàn)519
12.6　反射522
小結(jié)·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)528
第13章　并發(fā)533
13.1　概述534
13.2　子程序級(jí)并發(fā)概述539
13.3　信號(hào)量544
13.4　管程549
13.5　消息傳遞551
13.6　Ada對(duì)并發(fā)機(jī)制的支持552
13.7　Java線程560
13.8　C＃線程570
13.9　函數(shù)式語言中的并發(fā)處理575
13.10　語句級(jí)并發(fā)578
小結(jié)·文獻(xiàn)注記·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)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
小結(jié)·文獻(xiàn)注記·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)616
第15章　函數(shù)式程序設(shè)計(jì)語言623
15.1　概述624
15.2　數(shù)學(xué)函數(shù)625
15.3　函數(shù)式程序設(shè)計(jì)語言基礎(chǔ)628
15.4　第一個(gè)函數(shù)式程序設(shè)計(jì)語言：Lisp629
15.5　Scheme概述633
15.6　Common Lisp651
15.7　ML653
15.8　Haskell658
15.9　F#663
15.10　主要命令式語言對(duì)函數(shù)式程序設(shè)計(jì)的支持666
15.11　函數(shù)式語言和命令式語言的比較669
小結(jié)·文獻(xiàn)注記·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)671
第16章　邏輯程序設(shè)計(jì)語言679
16.1　概述680
16.2　謂詞演算概述680
16.3　謂詞演算和定理證明 684
16.4　邏輯程序設(shè)計(jì)概述686
16.5　Prolog的起源688
16.6　Prolog的基本元素688
16.7　Prolog的缺點(diǎn)703
16.8　邏輯程序設(shè)計(jì)的應(yīng)用709
小結(jié)·文獻(xiàn)注記·復(fù)習(xí)題·習(xí)題·程序設(shè)計(jì)練習(xí)710
參考文獻(xiàn)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