Ⅰ INTRODUCTION 1
1 The Role of Programming Languages 3
1.1 Toward Higher-Level Languages 4
1.2 Problems of Scale 8
1.3 Programming Paradigms 11
1.4 Language Implementation:Bridging the Gap 18
EXERCISES 21
BIBLIOGRAPHIC NOTES 23
2 Language Description:Syntactic Structure 25
2.1 Expression Notations 28
2.2 Abstract Syntax Trees 31
2.3 Lexical Syntax 33
2.4 Context-Free Grammars 35
2.5 Grammars for Expressions 41
2.6 Variants of Grammars 46
EXERCISES 49
BIBLIOGRAPHIC NOTES 52
Ⅱ IMPERATIVE PROGRAMMING 55
3.1 The Need for Structured Ptogramming 59
3 Statements:Structured Programming 59
3.2 Syntax-Directed Control Flow 63
3.3 Design Considerations:Syntax 72
3.4 Handling Special Cases in Loops 77
3.5 Programming with Invariants 80
3.6 Proof Rules for Partial Correctness 86
3.7 Control flow in C 90
EXERCISES 94
BIBLIOGRAPHIC NOTES 99
4 Types:Data Representation 101
4.1 The Role of Types 102
4.2 Basic Types 107
4.3 Arrays:Sequences of Elements 111
4.4 Records:Named Fields 117
4.5 Unions and Variant Records 120
4.6 Sets 123
4.7 Pointers:Efficiency and Dynamic Allocation 125
4.8 Two String Tables 133
4.9 Types and Error Checking 136
EXERCISES 143
BIBLIOGRAPHIC NOTES 146
5 Procedure Activations 147
5.1 Introduction to Procedures 148
5.2 Parameter-Passing Methods 155
5.3 Scope Rules for Names 160
5.4 Nested Scopes in the Source Text 166
5.5 Activation Records 172
5.6 Lexical Scope:Procedures as in C 181
5.7 Lexical Scope:Nested Procedures and Pascal 190
EXERCISES 198
BIBLIOGRAPHIC NOTES 202
Ⅲ OBJECT-ORIENTED PROGRAMMING 205
6 Groupings of Data and Operations 209
6.1 Constructs for Program Structuring 210
6.2 Information Hiding 217
6.3 Program Design with Modules 220
6.4 Modules and Defined Types 229
6.5 Class Declarations in C++ 232
6.6 Dynamic Allocation in C++ 238
6.7 Templates:Parameterized Types 244
6.8 Implementation of Objects in C++ 245
EXERCISES 248
BIBLIOGRAPHIC NOTES 251
7 Object-Oriented Programming 253
7.1 What is an Object? 253
7.2 Object-Oriented Thinking 256
7.3 Inheritance 260
7.4 Object-Oriented Programming in C++ 267
7.5 An Extended C++ Example 274
7.6 Derived Classes and Information Hiding 281
7.7 Objects in Smalltalk 285
7.8 Smalltalk Objects hava a Self 291
EXERCISES 294
BIBLIOGRAPHIC NOTES 299
Ⅳ FUNCTIONAL PROGRAMMING 301
8 Elements of Functional Programming 305
8.1 A Little Language of Expressions 306
8.2 Types:Values and Operations 313
8.3 Function Declarations 318
8.4 Approaches to Expression Evaluation 321
8.5 Lexical Scope 327
8.6 Type Checking 331
EXERCISES 335
BIBLIOGRAPHIC NOTES 339
9 Functional Programming in a Typed Language 341
9.1 Exploring a List 342
9.2 Function Declaration by Cases 346
9.3 Functions as First-Class Values 351
9.4 ML:Implicit Types 357
9.5 Data Types 360
9.6 Exception Handling in ML 367
9.7 Little Quilt in Standard ML 369
EXERCISES 380
BIBLIOGRAPHIC NOTES 383
10 Functional Programming with Lists 385
10.1 Scheme,a Dialect of Lisp 386
10.2 The Structure of Lists 392
10.3 List Manipulation 396
10.4 A Motivating Example:Differentiation 404
10.5 Simplification of Expressions 409
10.6 Storage Allocation for Lists 413
EXERCISES 417
BIBLIOGRAPHIC NOTES 421
Ⅴ OTHER PARADIGMS 423
11 Logic Programming 425
11.1 Computing with Relations 426
11.2 Introduction to Prolog 430
11.3 Data Structures in Prolog 438
11.4 Programming Techniques 442
11.5 Control in Prolog 450
11.6 Cuts 461
EXERCISES 470
BIBLIOGRAPHIC NOTES 472
12 An Introduction to Concurrent Programming 475
12.1 Parallelism in Hardware 476
12.2 Streams:Implicit Synchronization 478
12.3 Concurrency as Interleaving 482
12.4 Liveness Properties 485
12.5 Safe Access to Shared Data 489
12.6 Concurrency in Ada 491
12.7 Synchronized Access to Shared Variables 498
EXERCISES 507
BIBLIOGRAPHIC NOTES 510
Ⅵ LANGUAGE DESCRIPTION 513
13 Semantic Methods 515
13.1 Synthesized Attributes 517
13.2 Attribute Grammars 520
13.3 Natural Semantics 523
13.4 Denotational Semantics 529
13.5 A Calculator in Scheme 530
13.6 Lexically Scoped Lambda Expressions 532
13.7 An Interpreter 535
13.8 An Extension:Recursive Functions 542
EXERCISES 545
BIBLIOGRAPHIC NOTES 546
14 Static Types and the Lambda Calculus 547
14.1 Equallty of Pure Lambda Terms 549
14.2 Substitution Revisited 554
14.3 Computation with Pure Lambda Terms 556
14.4 Programming Constructs as Lambda-Terms 561
14.5 The Typed Lambda Calculus 566
14.6 Polymorphic Types 569
EXERCISES 576
BIBLIOGRAPHIC NOTES 577
15.1 Pascal:A Teaching Language 579
15 A Look at Some Languages 579
15.2 C:Syetems Programming 583
15.3 C++:A Range of Programming Styles 591
15.4 Smalltalk,the Language 594
15.5 Standard ML 598
15.6 Scheme,a Dialect of Lisp 602
15.7 Prolog 607
Bibliography 613
Credits 627
Index 629