PartⅠConcepts 1
1 The Study of Programming Languages 2
1.1 Why Study Programming Languages? 2
1.2 A Short History of Programming Languages 5
1.2.1 Development of Early Languages 5
1.2.2 Role of Programming Languages 9
1.3 What Makes a Good Language? 12
1.3.1 Attributes of a Good Language 12
1.3.2 Application Domains 16
1.3.3 I anguage Standardization 19
1.4 Effects of Environments on Languages 23
1.4.1 Batch-Processing Environments 23
1.4.2 Interactive Environments 24
1.4.3 Embedded System Environments 25
1.4.4 Programming Environments 26
1.5 Suggestions for Further Reading 30
1.4.5 Environment Frameworks 30
1.6 Problems 31
2 Language Design Issues 33
2.1 The Structure and Operation of a Computer 33
2.1.1 The Hardware of the Computer 35
2.1.2 Firmware Computers 39
2.1.3 Translators and Software-Simulated Computers 41
2.2 Virtual Computers and Binding Times 45
2.2.1 Syntax and Semantics 46
2.2.2 Virtual Computers and Language Implementations 47
2.2.3 Hierarchies of Computers 48
2.2.4 Binding and Binding Time 50
2.3 Language Paradigms 55
2.4 Suggestions for Further Reading 59
2.5 Problems 59
3.1 Programming Language Syntax 61
3 Language Translation Issues 61
3.1.1 General Syntactic Criteria 62
3.1.2 Syntactic Elements of a Language 66
3.1.3 Overall Program-Subprogram Structure 69
3.2 Stages in Translation 72
3.2.1 Analysis of the Source Program 74
3.2.2 Synthesis of the Object Program 77
3.3 Formal Translation Models 79
3.3.1 BNF Grammars 80
3.3.2 Finite-State Automata 89
3.3.3 Pushdown Automata 93
3.3.4 Efficient Parsing Algorithms 95
3.3.5 Semantic Modeling 98
3.4 Suggestions for Further Reading 102
3.5 Problems 103
4.1.1 Data Objects, Variables, and Constants 107
4.1 Properties of Types and Objects 107
4 Data Types 107
4.1.2 Data Types 112
4.1.3 Specification of Elementary Data Types 113
4.1.4 Implementation of Elementary Data Types 117
4.1.5 Declarations 119
4.1.6 Type Checking and Type Conversion 121
4.1.7 Assignment and Initialization 127
4.2.1 Numeric Data Types 130
4.2 Elementary Data Types 130
4.2.2 Enumerations 137
4.2.3 Booleans 139
4.2.4 Characters 140
4.2.5 Internationalization 141
4.3 Structured Data Types 142
4.3.1 Structured Data Objects and Data Types 142
4.3.2 Specification of Data Structure Types 143
4.3.3 Implementation of Data Structure Types 145
4.3.4 Declarations and Type Checking for Data Structures 149
4.3.5 Vectors and Arrays 151
4.3.6 Records 160
4.3.7 Lists 167
4.3.8 Character Strings 172
4.3.9 Pointers and Programmer-Constructed Data Objects 175
4.3.10 Sets 178
4.3.11 Executable Data Objects 181
4.3.12 Files and Input-Output 181
4.4 Suggestions for Further Reading 187
4.5 Problems 187
5 Abstraction I: Encapsulation 195
5.1 Abstract Data Types 196
5.1.1 Evolution of the Data Type Concept 197
5.1.2 Information Hiding 198
5.2.1 Subprograms as Abstract Operations 200
5.2 Encapsulation by Subprograms 200
5.2.2 Subprogram Definition and Invocation 203
5.2.3 Subprogram Definitions as Data Objects 208
5.3 Type Definitions 209
5.3.1 Type Equivalence 211
5.3.2 Type Definitions with Parameters 215
5.4 Storage Management 216
5.4.1 Major Run-Time Elements Requiring Storage 217
5.4.2 Programmer-and System-Controlled Storage Management 219
5.4.3 Static Storage Management 220
5.4.4 Stack-Based Storage Management 221
5.4.5 Heap Storage Management: Fixed-Size Elements 223
5.4.6 Heap Storage Management: Variable-Size Elements 231
5.5 Suggestions for Further Reading 234
5.6 Problems 234
6 Sequence Control 238
6.1 Implicit and Explicit Sequence Control 238
6.2 Sequencing with Arithmetic Expressions 239
6.2.1 Tree-Structure Representation 240
6.2.2 Execution-Time Representation 248
6.3 Sequencing with Nonarithmetic Expressions 253
6.3.1 Pattern Matching 253
6.3.2 Unification 257
6.3.3 Backtracking 263
6.4 Sequence Control Between Statements 264
6.4.1 Basic Statements 264
6.4.2 Structured Sequence Control 270
6.4.3 Prime Programs 279
6.5 Suggestions for Further Reading 284
6.6 Problems 284
7 Subprogram Control 286
7.1 Subprogram Sequence Control 286
7.1.1 Simple Call-Return Subprograms 288
7.1.2 Recursive Subprograms 292
7.2 Attributes of Data Control 294
7.2.1 Names and Referencing Environments 295
7.2.2 Static and Dynamic Scope 300
7.2.3 Block Structure 303
7.2.4 Local Data and Local Referencing Environments 305
7.3 Shared Data in Subprograms 311
7.3.1 Parameters and parameter Transmission 312
7.3.2 Explicit Common Environments 330
7.3.3 Dynamic Scope 333
7.3.4 Static Scope and Block Stucture 337
7.4 Suggestions for Further Reading 344
7.5 Problems 345
8 Abstraction Ⅱ: Inheritance 350
8.1 Abstract Data Types Revisited 351
8.2 Inheritance 358
8.2.1 Derived Classes 359
8.2.2 Methods 362
8.2.3 Abstract Classes 364
8.2.4 Objects and Messages 366
8.2.5 Abstraction Concepts 370
8.3 Polymorphism 372
8.4 Suggestions for Further Reading 373
8.5 Problems 374
9 Advances in Language Design 375
9.1 Variations on Subprogram Control 377
9.1.1 Exceptions and Exceptions Handlers 377
9.1.2 Coroutines 382
9.1.3 Scheduled Subprograms 383
9.1.4 Nonsequential Execution 385
9.2 Parallel Programming 385
9.2.1 Concurrent Execution 387
9.2.2 Guarded Commands 388
9.2.3 Tasks 391
9.2.4 Synchronization of Tasks 393
9.3 Formal Properties of Languages 404
9.3.1 Chomsky Hierarchy 405
9.3.2 Undecidability 408
9.3.3 Algorithm Complexity 413
9.4 Language Semantics 416
9.4.1 Denotational Semantics 416
9.4.2 Program Verification 423
9.4.3 Algebraic Data Types 428
9.4.4 Resolution 431
9.5 Hardware Developments 433
9.5.1 Processor Design 433
9.5.2 System Design 436
9.6 Software Architecture 438
9.6.1 Persistent Data and Transaction Systems 438
9.6.2 Networks and Client/Server Computing 440
9.6.3 Desktop Publishing 441
9.7 Suggestions for Further Reading 444
9.6.4 Programming Language Trends 444
9.8 Problems 445
PartⅡ Paradigms and Languages 449
10 Simple Procedural Languages 451
10.1 FORTRAN 451
10.1.1 History 452
10.1.2 Hello World 452
10.1.3 Brief Overview of the Language 453
10.1.4 Data Objects 457
10.1.5 Sequence Control 462
10.1.6 Subprograms and Storage Management 468
10.1.7 Abstraction and Encapsulation 470
10.1.8 Language Evaluation 471
10.2 C 471
10.2.2 Hello World 472
10.2.3 Brief Overview of the Language 472
10.2.1 History 472
10.2.4 Data Objects 477
10.2.5 Sequence Control 482
10.2.6 Subprograms and Storage Management 485
10.2.7 Abstraction and Encapsulation 489
10.2.8 Language Evaluation 489
10.3 Suggestions for Further Reading 490
10.4 Problems 490
11 Block-Structured Procedural Languages 492
11.1 Pascal 492
11.1.1 History 493
11.1.2 Hello World 494
11.1.3 Brief Overview of the Language 494
11.1.4 Data Objects 498
11.1.5 Sequence Control 505
11.1.6 Subprograms and Storage Management 509
11.1.8 Language Evaluation 516
11.1.7 Abstraction and Encapsulation 516
11.2 Suggestions for Further Reading 518
11.3 Problems 518
12 Object-Based Languages 520
12.1 Ada 520
12.1.1 History 520
12.1.2 Hello World 522
12.1.3 Brief Overview of the Language 522
12.1.4 Data Objects 527
12.1.5 Sequence Control 536
12.1.6 Subprograms and Storage Management 540
12.1.7 Abstraction and Encapsulation 547
12.1.8 Language Evaluation 549
12.2 C++ 550
12.2.1 History 550
12.2.3 Brief Overview of the Language 551
12.2.2 Hello World 551
12.2.4 Data Objects 556
12.2.5 Sequence Control 561
12.2.6 Subprograms and Storage Management 562
12.2.7 Abstraction and Encapsulation 564
12.2.8 Language Evaluation 564
12.3 Smalltalk 565
12.3.1 History 565
12.3.3 Brief Overview of the Language 566
12.3.2 Hello World 566
12.3.4 Data Objects 570
12.3.5 Sequence Control 572
12.3.6 Subprograms and Storage Management 574
12.3.7 Abstraction and Encapsulation 577
12.3.8 Language Evaluation 577
12.4 Suggestions for Further Reading 578
12.5 Problems 579
13.1 LISP 581
13 Functional Languages 581
13.1.2 Hello World 582
13.1.1 History 582
13.1.3 Brief Overview of the Language 583
13.1.4 Data Objects 587
13.1.5 Sequence Control 589
13.1.6 Subprograms and Storage Management 593
13.1.7 Abstraction and Encapsulation 599
13.1.8 Language Evaluation 599
13.2.2 Hello World 600
13.2 ML 600
13.2.1 History 600
13.2.3 Brief Overview of the Language 601
13.2.4 Data Objects 603
13.2.5 Sequence Control 607
13.2.6 Subprograms and Storage Management 611
13.2.7 Abstraction and Encapsulation 613
13.3 Suggestions for Further Reading 616
13.2.8 Language Evaluation 616
13.4 Problems 617
14 Logic Programming Languages 620
14.1 Prolog 620
14.1.1 History 621
14.1.2 Hello World 621
14.1.3 Brief Overview of the Language 622
14.1.4 Data Objects 625
14.1.5 Sequence Control 626
14.1.6 Subprograms and Storage Management 628
14.1.7 Abstraction and Encapsulation 629
14.1.8 Language Evaluation 630
14.2 Suggestions for Further Reading 630
14.3 Problems 630
References 632
Index 641