1 Introduction 1
1.1 What Is a Programming Language? 2
1.2 Abstractions in Programming Languages 5
1.3 Computational Paradigms 13
1.4 Language Definition 20
1.5 Language Translation 22
1.6 Language Design 29
Exercises 30
Notes and References 33
2 History 34
2.1 Early History:The First Programmer 35
2.2 The 1950s:The First Programming Languages 37
2.3 The 1960s:An Explosion in Programming Languages 39
2.4 The 1970s:Simplicity,Abstraction,Study 42
2.5 The 1980s:New Directions and the Rise of Object-Orientation 43
2.6 The 1990s:Consolidation,the Internet,Libraries,and Scripting 46
2.7 The Future 49
Exercises 50
Notes and References 53
3 Language Design Principles 55
3.1 History and Design Criteria 57
3.2 Efficiency 59
3.3 Regularity 60
3.4 Further Language Design Principles 63
3.5 C++:A Case Study in Language Design 68
Exercises 72
Notes and References 76
4 Syntax 77
4.1 Lexical Structure of Programming Languages 78
4.2 Context-Free Grammars and BNFs 83
4.3 Parse Trees and Abstract Syntax Trees 89
4.4 Ambiguity,Associativity,and Precedence 92
4.5 EBNFs and Syntax Diagrams 97
4.6 Parsing Techniques and Tools 101
4.7 Lexics versus Syntax versus Semantics 113
Exercises 115
Notes and References 123
5 Basic Semantics 125
5.1 Attributes,Binding,and Semantic Functions 126
5.2 Declarations,Blocks,and Scope 130
5.3 The Symbol Table 139
5.4 Name Resolution and Overloading 152
5.5 Allocation,Lifetimes,and the Environment 159
5.6 Variables and Constants 167
5.7 Aliases,Dangling References,and Garbage 174
Exercises 180
Notes and References 187
6 Data Types 189
6.1 Data Types and Type Information 192
6.2 Simple Types 197
6.3 Type Constructors 200
6.4 Type Nomenclature in Sample Languages 215
6.5 Type Equivalence 218
6.6 Type Checking 225
6.7 Type Conversion 231
6.8 Polymorphic Type Checking 235
6.9 Explicit Polymorphism 244
Exercises 250
Notes and References 258
7 Control I-Expressions and Statements 260
7.1 Expressions 262
7.2 Conditional Statements and Guards 270
7.3 Loops and Variation on WHILE 276
7.4 The GOTO Controversy 280
7.5 Exception Handling 282
Exercises 299
Notes and References 307
8 Control II-Procedures and Environments 309
8.1 Procedure Definition and Activation 311
8.2 Procedure Semantics 313
8.3 Parameter Passing Mechanisms 317
8.4 Procedure Environments,Activations,and Allocation 325
8.5 Dynamic Memory Management 340
8.6 Exception Handling and Environments 344
Exercises 346
Notes and References 355
9 Abstract Data Types and Modules 356
9.1 The Algebraic Specification of Abstract Data Types 359
9.2 Abstract Data Type Mechanisms and Modules 364
9.3 Separate Compilation in C,C++ Namespaces,and Java Packages 368
9.4 Ada Packages 375
9.5 Modules in ML 381
9.6 Modules in Earlier Languages 385
9.7 Problems with Abstract Data Type Mechanisms 390
9.8 The Mathematics of Abstract Data Types 398
Exercises 402
Notes and References 407
10 Object-Oriented Programming 409
10.1 Software Reuse and Independence 410
10.2 Java:Objects,Classes,and Methods 413
10.3 Inheritance 419
10.4 Dynamic Binding 431
10.5 C++ 434
10.6 Smalltalk 446
10.7 Design Issues in Object-Oriented Languages 452
10.8 Implementation Issues in Object-Oriented Languages 456
Exercises 462
Notes and References 470
11 Functional Programming 471
11.1 Programs as Functions 473
11.2 Functional Programming in an Imperative Language 476
11.3 Scheme:A Dialect of LISP 481
11.4 ML:Functional Programming with Static Typing 494
11.5 Delayed Evaluation 507
11.6 Haskell-A Fully-Curried Lazy Language with Overloading 512
11.7 The Mathematics of Functional Programming I:Recursive Functions 520
11.8 The Mathematics of Functional Programming Ⅱ:Lambda Calculus 524
Exercises 529
Notes and References 537
12 Logic Programming 539
12.1 Logic and Logic Programs 541
12.2 Horn Clauses 545
12.3 Resolution and Unification 548
12.4 The Language Prolog 552
12.5 Problems with Logic Programming 563
12.6 Extending Logic Programming:Constraint Logic Programming and Equational Systems 568
Exercises 572
Notes and References 577
13 Formal Semantics 579
13.1 A Sample Small Language 581
13.2 Operational Semantics 585
13.3 Denotational Semantics 595
13.4 Axiomatic Semantics 604
13.5 Proofs of Program Correctness 611
Exercises 614
Notes and References 619
14 Parallel Programming 620
14.1 Introduction to Parallel Processing 622
14.2 Parallel Processing and Programming Languages 626
14.3 Threads 634
14.4 Semaphores 643
14.5 Monitors 648
14.6 Message Passing 654
14.7 Parallelism in Non-Imperative Languages 660
Exercises 665
Notes and References 671
Bibliography 673
Index 685