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 .......................................................19
1.5 Language Categories .......................................................................22
1.6 Language Design Trade-Offs ............................................................24
1.7 Implementation Methods ................................................................25
1.8 Programming Environments ............................................................32
Summary * Review Questions * Problem Set .............................................33
Chapter 2 Evolution of the Major Programming Languages 37
2.1 Zuse's Plankalkul ...........................................................................38
2.2 Minimal Hardware Programming: Pseudocodes ...............................41
2.3 The IBM 704 and Fortran ..............................................................44
2.4 Functional Programming: LISP ......................................................49
2.5 The First Step Toward Sophistication: ALGOL 60 ............................54
2.6 Computerizing Business Records: COBOL ........................................60
2.7 The Beginnings of Timesharing: BASIC ............................................65
Interview: ALAN COOPER-User Design and Language Design..................68
2.8 Everything for Everybody: PL/I .......................................................70
2.9 Two Early Dynamic Languages: APL and SNOBOL .........................73
2.10 The Beginnings of Data Abstraction: SIMULA 67 ............................74
2.11 Orthogonal Design: ALGOL 68 ........................................................75
2.12 Some Early Descendants of the ALGOLs ......................................... 77
2.13 Programming Based on Logic: Prolog ............................................. 81
2.14 History's Largest Design Effort: Ada .............................................. 83
2.15 Object-Oriented Programming: Smalltalk ........................................ 87
2.16 Combining Imperative and Object-Oriented Features: C++ ................ 90
2.17 An Imperative-Based Object-Oriented Language: Java ...................... 93
2.18 Scripting Languages ....................................................................... 97
2.19 A C-Based Language for the New Millennium: C# ......................... 103
2.20 Markup/Programming Hybrid Languages ....................................... 106
Summary * Bibliographic Notes * Review Questions * Problem Set * Programming Exercises..... 108
Chapter 3 Describing Syntax and Semantics 115
3.1 Introduction ................................................................................. 116
3.2 The General Problem of Describing Syntax .................................... 117
3.3 Formal Methods of Describing Syntax ........................................... 119
3.4 Attribute Grammars ..................................................................... 134
History Note......................................................................................... 135
3.5 Describing the Meanings of Programs: Dynamic Semantics ............ 141
History Note........................................................................................ 156
Summary * Bibliographic Notes * Review Questions * Problem Set ...........163
Chapter 4 Lexical and Syntax Analysis 171
4.1 Introduction ................................................................................. 172
4.2 Lexical Analysis ........................................................................... 173
4.3 The Parsing Problem .................................................................... 182
4.4 Recursive-Descent Parsing ............................................................ 185
4.5 Bottom-Up Parsing ...................................................................... 194
Summary * Review Questions * Problem Set * Programming Exercises......202
Chapter 5 Names, Bindings, and Scopes 207
5.1 Introduction ................................................................................. 208
5.2 Names ......................................................................................... 208
History Note.........................................................................................209
History Note.........................................................................................210
5.3 Variables ......................................................................................211
History Note.........................................................................................212
5.4 The Concept of Binding .................................................................214
Interview: RASMUS LERDORF-Scripting Languages and Other Examples of Slick Solutions .......218
5.5 Scope ...........................................................................................225
History Note.........................................................................................227
5.6 Scope and Lifetime .......................................................................234
5.7 Referencing Environments .............................................................235
5.8 Named Constants ........................................................................237
Summary * Review Questions * Problem Set * Programming Exercises ... 239
Chapter 6 Data Types 247
6.1 Introduction .................................................................................248
6.2 Primitive Data Types .....................................................................250
6.3 Character String Types ..................................................................254
History Note.........................................................................................255
6.4 User-Defined Ordinal Types ............................................................259
6.5 Array Types ..................................................................................263
History Note.........................................................................................264
History Note.........................................................................................267
6.6 Associative Arrays ........................................................................277
Interview: ROBERTO IERUSALIMSCHY-Lua ................................280
6.7 Record Types ................................................................................282
6.8 Union Types ..................................................................................287
6.9 Pointer and Reference Types ..........................................................291
History Note.........................................................................................294
6.10 Type Checking ..............................................................................304
6.11 Strong Typing ...............................................................................305
6.12 Type Equivalence ..........................................................................306
6.13 Theory and Data Types .................................................................. 310
Summary * Bibliographic Notes * Review Questions * Problem Set * Programming Exercises ......312
Chapter 7 Expressions and Assignment Statements 319
7.1 Introduction ................................................................................. 320
7.2 Arithmetic Expressions ................................................................. 321
7.3 Overloaded Operators ................................................................... 330
7.4 Type Conversions .......................................................................... 331
History Note......................................................................................... 334
7.5 Relational and Boolean Expressions .............................................. 335
History Note......................................................................................... 335
7.6 Short-Circuit Evaluation .............................................................. 337
7.7 Assignment Statements ................................................................ 339
History Note......................................................................................... 343
7.8 Mixed-Mode Assignment .............................................................. 343
Summary * Review Questions * Problem Set * Programming Exercises .... 344
Chapter 8 Statement-Level Control Structures 349
8.1 Introduction ................................................................................. 350
8.2 Selection Statements .................................................................... 352
History Note......................................................................................... 352
History Note......................................................................................... 354
8.3 Iterative Statements ..................................................................... 365
History Note......................................................................................... 365
Interview: LARRY WALL-Part 1: Linguistics and the Birth of Perl ........ 370
History Note......................................................................................... 378
8.4 Unconditional Branching .............................................................. 380
8.5 Guarded Commands ..................................................................... 381
8.6 Conclusions .................................................................................. 383
Summary * Review Questions * Problem Set * Programming Exercises..... 384
Chapter 9 Subprograms 391
9.1 Introduction .................................................................................392
9.2 Fundamentals of Subprograms ......................................................392
9.3 Design Issues for Subprograms .....................................................403
9.4 Local Referencing Environments ...................................................404
9.5 Parameter-Passing Methods .........................................................406
Interview: LARRY WALL-Part 2: Scripting Languages in General and Perl in Particular ........408
History Note.........................................................................................416
History Note.........................................................................................416
History Note.........................................................................................420
9.6 Parameters That Are Subprograms ................................................427
History Note.........................................................................................429
9.7 Overloaded Subprograms ..............................................................429
9.8 Generic Subprograms ...................................................................431
9.9 Design Issues for Functions ...........................................................438
9.10 User-Defined Overloaded Operators ...............................................439
9.11 Coroutines ....................................................................................440
History Note.........................................................................................440
Summary * Review Questions * Problem Set * Programming Exercises .....442
Chapter 10 Implementing Subprograms 449
10.1 The General Semantics of Calls and Returns .................................450
10.2 Implementing Simple Subprograms ..........................................451
10.3 Implementing Subprograms with Stack-Dynamic Local Variables ...............453
10.4 Nested Subprograms ...................................................................462
Interview: NIKLAUS WIRTH-Keeping It Simple ............................464
10.5 Blocks ........................................................................................470
10.6 Implementing Dynamic Scoping ...................................................472
Summary * Review Questions * Problem Set * Programming Exercises ....475
Chapter 11 Abstract Data Types and Encapsulation Constructs 481
11.1 The Concept of Abstraction ......................................................... 482
11.2 Introduction to Data Abstraction ................................................. 483
11.3 Design Issues for Abstract Data Types .......................................... 486
11.4 Language Examples .................................................................... 487
Interview: BJARNE STROUSTRUP-C++: Its Birth, Its Ubiquitousness, and Common Criticisms ....... 490
11.5 Parameterized Abstract Data Types .............................................. 504
11.6 Encapsulation Constructs ............................................................ 508
11.7 Naming Encapsulations ............................................................... 512
Summary * Review Questions * Problem Set * Programming Exercises .... 517
Chapter 12 Support for Object-Oriented Programming 523
12.1 Introduction ................................................................................ 524
12.2 Object-Oriented Programming ...................................................... 524
12.3 Design Issues for Object-Oriented Languages ................................ 527
12.4 Support for Object-Oriented Programming in Smalltalk ................ 532
12.5 Support for Object-Oriented Programming in C++ ........................ 535
Interview: BJARNE STROUSTRUP-On Paradigms and Better Programming ........ 536
12.6 Support for Object-Oriented Programming in Java ........................ 546
12.7 Support for Object-Oriented Programming in C# .......................... 550
12.8 Support for Object-Oriented Programming in Ada 95 .................... 552
12.9 Support for Object-Oriented Programming in Ruby........................ 557
12.10 Implementation of Object-Oriented Constructs .............................. 560
Summary * Review Questions * Problem Set * Programming Exercises..... 564
Chapter 13 Concurrency 569
13.1 Introduction ................................................................................ 570
13.2 Introduction to Subprogram-Level Concurrency ............................ 574
History Note ....................................................................................... 577
13.3 Semaphores ................................................................................ 578
13.4 Monitors .....................................................................................583
13.5 Message Passing .........................................................................585
13.6 Ada Support for Concurrency .......................................................587
13.7 Java Threads ...............................................................................598
13.8 C# Threads ..................................................................................606
13.9 Statement-Level Concurrency ......................................................608
Summary * Bibliographic Notes * Review Questions * Problem Set * Programming Exercises .....610
Chapter 14 Exception Handling and Event Handling 615
14.1 Introduction to Exception Handling ..............................................616
History Note........................................................................................620
14.2 Exception Handling in Ada ..........................................................622
14.3 Exception Handling in C++ ..........................................................629
14.4 Exception Handling in Java ..........................................................634
Interview: JAMES GOSLING-The Birth of Java .............................636
14.5 Introduction to Event Handling ....................................................643
14.6 Event Handling with Java ............................................................644
Summary * Bibliographic Notes * Review Questions * Problem Set * Programming Exercises ..... 650
Chapter 15 Functional Programming Languages 655
15.1 Introduction ................................................................................656
15.2 Mathematical Functions ..............................................................657
15.3 Fundamentals of Functional Programming Languages ..................659
15.4 The First Functional Programming Language: LISP .....................661
15.5 An Introduction to Scheme ..........................................................664
15.6 COMMON LISP ..........................................................................682
15.7 ML .............................................................................................682
15.8 Haskell .......................................................................................686
15.9 Applications of Functional Languages ..........................................691
15.10 A Comparison of Functional and Imperative Languages ................692
Summary * Bibliographic Notes * Review Questions * Problem Set * Programming Exercises ....694
Chapter 16 Logic Programming Languages 701
16.1 Introduction ................................................................................ 702
16.2 A Brief Introduction to Predicate Calculus ................................... 702
16.3 Predicate Calculus and Proving Theorems .................................... 706
16.4 An Overview of Logic Programming ............................................. 708
16.5 The Origins of Prolog .................................................................. 710
16.6 The Basic Elements of Prolog ...................................................... 711
16.7 Deficiencies of Prolog .................................................................. 725
16.8 Applications of Logic Programming ............................................ 731
Summary * Bibliographic Notes * Review Questions * Problem Set * Programming Exercises.... 733
Bibliography ...............................................................................737
Index ..........................................................................................747
