Concepts in Programming Languages

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 11
Acknowledgments......Page 12
PART 1 Functions and Foundations......Page 13
1.1 PROGRAMMING LANGUAGES......Page 15
1.2.1 General Goals......Page 17
1.3 PROGRAMMING LANGUAGE HISTORY......Page 18
1.4 ORGANIZATION: CONCEPTS AND LANGUAGES......Page 20
2.1.1 Expressions, Errors, and Nontermination......Page 22
2.1.2 Partial Functions......Page 24
Computable Functions......Page 25
Noncomputable Functions......Page 26
Applications......Page 27
2.1 Partial and Total Functions......Page 28
2.3 Halting Problem on All Input......Page 29
3.1 LISP HISTORY......Page 30
Program Execution Model......Page 32
Theoretical Foundations......Page 33
S-Expressions and Lists......Page 34
Evaluation of Expressions......Page 35
3.4.1 Statements and Expressions......Page 37
3.4.2 Conditional Expressions......Page 38
Cons Cells......Page 40
Representation of Lists by Cons Cells......Page 42
3.4.4 Programs as Data......Page 43
3.4.5 Function Expressions......Page 44
3.4.6 Recursion......Page 45
3.4.7 Higher-Order Functions......Page 46
3.4.8 Garbage Collection......Page 47
Mark-and-Sweep Garbage Collection......Page 48
3.4.9 Pure Lisp and Side Effects......Page 50
3.5 CHAPTER SUMMARY: CONTRIBUTIONS OF LISP......Page 51
3.2 Conditional Expressions in Lisp......Page 52
3.4 Lisp and Higher-Order Functions......Page 54
3.5 Definition of Garbage......Page 55
3.6 Reference Counting......Page 56
3.8 Concurrency in Lisp......Page 57
4.1.1 Structure of Simple Compiler......Page 60
Lexical Analysis......Page 62
Intermediate Code Generation......Page 63
Grammars......Page 64
Derivations......Page 65
Parse Trees and Ambiguity......Page 66
4.1.3 Parsing and Precedence......Page 67
4.2.1 Functions and Function Expressions......Page 69
Variable Binding......Page 71
Lambda Abstraction in Lisp and Algol......Page 72
Equivalence and Substitution......Page 73
4.2.3 Programming in Lambda Calculus......Page 74
Recursion and Fixed Points......Page 75
4.2.4 Reduction, Confluence, and Normal Forms......Page 77
Confluence......Page 78
4.3 DENOTATIONAL SEMANTICS......Page 79
Compositionality......Page 80
4.3.2 Denotational Semantics of Binary Numbers......Page 81
Expressions with Variables......Page 82
States and Commands......Page 83
Denotational Semantics......Page 84
4.3.4 Perspective and Nonstandard Semantics......Page 86
4.4.1 Imperative and Declarative Sentences......Page 88
4.4.2 Functional versus Imperative Programs......Page 89
Referential Transparency......Page 90
Historical Debate......Page 91
Functional Programming and Concurrency......Page 92
Practical Functional Programming......Page 93
4.5 CHAPTER SUMMARY......Page 94
4.4 Symbolic Evaluation......Page 95
4.7 Order of Evaluation......Page 96
4.10 Semantics of Type Checking......Page 97
4.11 Lazy Evaluation and Parallelism......Page 99
4.12 Single-Assignment Languages......Page 100
4.13 Functional and Imperative Programs......Page 101
4.14 Functional Languages and Concurrency......Page 102
PART 2 Procedures, Types, Memory Management, and Control......Page 103
5.1.1 Algol 60......Page 105
5.1.3 Pascal......Page 109
5.2 THE DEVELOPMENT OF C......Page 111
C Arrays and Pointers......Page 112
5.3 THE LCF SYSTEM AND ML......Page 113
5.4 THE ML PROGRAMMING LANGUAGE......Page 115
Expressions......Page 116
Declarations......Page 117
Bool......Page 119
Integers......Page 120
Real......Page 121
Records......Page 122
Lists......Page 123
Value Declarations......Page 124
Function Declarations......Page 125
5.4.4 ML Data-Type Declaration......Page 127
5.4.5 ML Reference Cells and Assignment......Page 129
Operations on Reference Cells......Page 130
5.5 CHAPTER SUMMARY......Page 133
5.2 Algol 60 Pass-By-Name......Page 134
5.3 Nonlinear Pattern Matching......Page 135
5.4 ML Map for Trees......Page 136
5.7 Disjoint Unions......Page 137
5.8 Lazy Evaluation and Functions......Page 138
6.1 TYPES IN PROGRAMMING......Page 141
6.1.2 Type Errors......Page 142
6.2.1 Type Safety......Page 144
6.2.2 Compile-Time and Run-Time Checking......Page 145
6.3.1 First Examples of Type Inference......Page 147
6.3.2 Type-Inference Algorithm......Page 148
6.4.1 Parametric Polymorphism......Page 157
C++ Function Templates......Page 158
Comparison with ML Polymorphism......Page 159
C++ Implementation......Page 160
ML Implementation......Page 161
6.4.3 Overloading......Page 162
6.5.1 Transparent Type Declarations......Page 163
6.5.3 ML Data-Type Declaration......Page 165
Type Inference......Page 167
6.2 Polymorphic Sorting......Page 168
6.5 Parse Graph......Page 169
6.6 Parse Graph......Page 170
6.9 Polymorphism in C......Page 171
6.11 Dynamic Typing in ML......Page 172
7.1 BLOCK-STRUCTURED LANGUAGES......Page 174
Simplified Machine Model......Page 176
7.2.1 Activation Records and Local Variables......Page 177
Intermediate Results......Page 178
Blocks and Activation Records for ML......Page 179
7.2.2 Global Variables and Control Links......Page 180
7.3.1 Activation Records for Functions......Page 182
7.3.2 Parameter Passing......Page 185
Semantics of Pass-by-Value......Page 186
Semantics of Pass-by-Reference......Page 187
7.3.3 Global Variables (First-Order Case)......Page 188
Access Links are Used to Maintain Static Scope......Page 190
7.3.4 Tail Recursion (First-Order Case)......Page 192
7.4.1 First-Class Functions......Page 194
7.4.2 Passing Functions to Functions......Page 195
Use of Closures......Page 196
7.4.3 Returning Functions from Nested Scope......Page 198
Solution to Storage Management Problem......Page 201
7.5 CHAPTER SUMMARY......Page 202
7.1 Activation Records for In-Line Blocks......Page 203
7.3 Time and Space Requirements......Page 205
7.4 Parameter Passing......Page 206
7.6 Pass-by-Value-Result......Page 207
7.8 Static and Dynamic Scope......Page 208
7.10 Eval and Scope......Page 209
7.12 Function Calls and Memory Management......Page 210
7.13 Function Returns and Memory Management......Page 211
7.14 Recursive Calls and Memory Management......Page 212
7.16 Closures and Tail Recursion......Page 213
7.17 Tail Recursion and Order of Operations......Page 214
8.1.1 Spaghetti Code......Page 216
8.1.2 Structured Control......Page 218
8.2.1 Purpose of an Exception Mechanism......Page 219
8.2.2 ML Exceptions......Page 221
8.2.3 C++ Exceptions......Page 223
8.2.4 More about Exceptions......Page 225
Exceptions for Efficiency......Page 226
Static and Dynamic Scope......Page 227
Typing and Exceptions......Page 228
Exceptions and Resource Allocation......Page 229
8.3.1 A Function Representing “The Rest of the Program”......Page 230
8.3.2 Continuation-Passing Form and Tail Recursion......Page 232
8.4 FUNCTIONS AND EVALUATION ORDER......Page 235
8.5 CHAPTER SUMMARY......Page 239
8.1 Exceptions......Page 240
8.3 Exceptions......Page 241
8.7 Control Flow and Memory Management......Page 242
8.9 Continuations......Page 243
PART 3 Modularity, Abstraction, and Object-Oriented Programming......Page 245
9.1 STRUCTURED PROGRAMMING......Page 247
9.1.1 Data Refinement......Page 250
9.1.2 Modularity......Page 251
Procedural Abstraction......Page 254
9.2.2 Abstract Data Types......Page 255
9.2.3 ML abstype......Page 256
Clu Clusters......Page 259
9.2.4 Representation Independence......Page 260
Partition Operations......Page 261
Induction over Constructors......Page 263
9.3 MODULES......Page 264
9.3.1 Modula and Ada......Page 265
9.3.2 ML Modules......Page 267
Simple Polymorphic Function......Page 271
Operations on Type Parameters......Page 272
Comparison with ML Polymorphism......Page 273
9.4.2 Standard ML Functors......Page 274
9.4.3 C++ Standard Template Library......Page 277
Language Support for Abstraction......Page 281
Modules and Generic Programming......Page 282
9.1 Efficiency vs. Modularity......Page 283
9.2 Equivalence of Abstract Data Types......Page 285
9.4 Modularity of Concrete Data Types......Page 286
9.5 Templates and Polymorphism......Page 288
10.1 OBJECT-ORIENTED DESIGN......Page 289
10.2 FOUR BASIC CONCEPTS IN OBJECT-ORIENTED LANGUAGES......Page 290
10.2.1 Dynamic Lookup......Page 291
10.2.2 Abstraction......Page 294
10.2.3 Subtyping......Page 296
Inheritance and Abstraction......Page 297
10.2.5 Closures as Objects......Page 298
10.2.6 Inheritance Is Not Subtyping......Page 299
10.3 PROGRAM STRUCTURE......Page 300
Comparison of Examples 10.1 and 10.2......Page 301
10.4 DESIGN PATTERNS......Page 302
Sample Code......Page 303
10.5 CHAPTER SUMMARY......Page 304
10.6 LOOKING FORWARD: SIMULA, SMALLTALK, C++, JAVA......Page 305
10.1 Expression Objects......Page 306
10.2 Objects vs. Type Case......Page 308
10.3 Visitor Design Pattern......Page 309
11.1.1 Object and Simulation......Page 312
11.1.2 Main Concepts in Simula......Page 314
11.2.1 Basic Object-Oriented Features in Simula......Page 315
Problem......Page 316
Line......Page 317
11.2.3 Sample Code and Representation of Objects......Page 318
11.3.1 Subclasses and Inheritance......Page 320
11.3.2 Object Types and Subtypes......Page 321
11.4 DEVELOPMENT OF SMALLTALK......Page 322
Dynabook......Page 323
11.5.2 Classes and Objects......Page 324
Run-Time Representation of Objects......Page 326
11.5.3 Inheritance......Page 327
Run-Time Structure to Support Inheritance......Page 328
11.6.1 Dynamic Lookup and Polymorphism......Page 330
11.6.2 Booleans and Blocks......Page 331
11.6.3 Self and Super......Page 332
11.6.4 System Extensibility: The Ingalls Test......Page 333
11.7.1 Interfaces as Object Types......Page 334
11.7.2 Subtyping......Page 335
11.7.3 Subtyping and Inheritance......Page 336
Smalltalk......Page 338
11.1 Simula Inheritance and Access Links......Page 339
11.2 Loophole in Encapsulation......Page 340
11.4 Smalltalk Run-Time Structures......Page 342
11.5 Smalltalk Implementation Decisions......Page 343
11.6 Protocol Conformance......Page 344
11.7 Removing a Method......Page 345
11.8 Subtyping and Binary Methods......Page 346
11.9 Delegation-Based Object-Oriented Languages......Page 347
12.1 DESIGN GOALS AND CONSTRAINTS......Page 349
12.1.1 Compatibility with C......Page 350
12.1.2 Success of C++......Page 351
Type bool......Page 352
Reference Type and Pass-By Reference......Page 353
User-Defined Overloading......Page 354
12.2.2 Object-Oriented Features......Page 355
Problem Areas......Page 356
12.3.1 C++ Classes and Objects......Page 358
12.3.2 C++ Derived Classes (Inheritance)......Page 360
12.3.3 Virtual Functions......Page 361
12.3.4 Why is C++ Lookup Simpler than Smalltalk Lookup?......Page 363
Arguments to Member Functions and this......Page 364
Nonvirtual and Overloaded Functions......Page 365
12.4.1 Subtyping Principles......Page 367
12.4.2 Public Base Classes......Page 368
12.4.3 Specializing Types of Public Members......Page 369
12.4.4 Abstract Base Classes......Page 370
12.5 MULTIPLE INHERITANCE......Page 371
12.5.1 Implementation of Multiple Inheritance......Page 372
Name Clashes......Page 374
Diamond Inheritance......Page 376
Virtual Base Classes......Page 377
12.6 CHAPTER SUMMARY......Page 378
12.1 Assignment and Derived Classes......Page 379
12.2 Function Objects......Page 380
12.4 Subtyping and Public Data......Page 385
12.5 Phantom Members......Page 386
12.6 Subtyping and Visibility......Page 387
12.8 “Like Current” in Eiffel......Page 388
12.9 Subtyping and Specifications......Page 389
12.10 C++ Multiple Inheritance and Casts......Page 391
12.11 Multiple Inheritance and Thunks......Page 392
12.12 Dispatch on State......Page 393
13 Portability and Safety: Java......Page 396
13.1.2 Design Decisions......Page 398
13.2.1 Classes and Objects......Page 401
13.2.2 Packages and Visibility......Page 403
13.2.3 Inheritance......Page 404
13.2.4 Abstract Classes and Interfaces......Page 406
13.3.1 Classification of Types......Page 408
13.3.3 Arrays, Covariance, and Contravariance......Page 409
13.3.4 Java Exception Class Hierarchy......Page 410
13.3.5 Subtype Polymorphism and Generic Programming......Page 413
13.4.1 Java Virtual Machine......Page 416
13.4.2 Class Loader......Page 417
13.4.4 Bytecode Interpreter and Method Lookup......Page 418
Finding a Virtual Method by Class......Page 420
Finding a Virtual Method by Interface......Page 422
13.5 SECURITY FEATURES......Page 424
13.5.1 Buffer Overflow Attack......Page 425
Class Loader......Page 426
The Security Manager......Page 427
13.5.3 Security and Type Safety......Page 428
Objects and Classes......Page 429
Inheritance......Page 430
Security......Page 431
13.3 Subtyping and Exceptions......Page 432
13.5 Array Covariance in Java......Page 433
13.6 Java Bytecode Analysis......Page 434
13.7 Exceptions, Memory Management, and Concurrency......Page 435
13.8 Adding Pointers to Java......Page 436
13.9 Stack Inspection......Page 437
PART4 Concurrency and Logic Programming......Page 441
14 Concurrent and Distributed Programming......Page 443
14.1.1 Execution Order and Nondeterminism......Page 445
14.1.2 Communication, Coordination, and Atomicity......Page 447
14.1.3 Mutual Exclusion and Locking......Page 448
Mutual Exclusion......Page 449
Locks and Busy Waiting......Page 450
Deadlock......Page 451
14.1.4 Semaphores......Page 452
14.2 THE ACTOR MODEL......Page 453
14.3.1 Threads and Channels......Page 457
Functions Using Threads and Channels......Page 459
14.3.2 Selective Communication and Guarded Commands......Page 460
14.3.3 First-Class Synchronous Operations: Events......Page 461
Selective Communication with Events......Page 463
14.4 JAVA CONCURRENCY......Page 466
14.4.1 Threads, Communication, and Synchronization......Page 467
Synchronization Primitives......Page 468
14.4.2 Synchronized Methods......Page 470
Concurrent Garbage Collection......Page 472
Java Memory Model......Page 473
Creating Remote Objects......Page 477
14.5 CHAPTER SUMMARY......Page 478
Actor Systems......Page 479
Distributed Java Programming and Remote Method Invocation......Page 480
14.2 Fairness......Page 481
14.5 CML Events......Page 482
14.6 Concurrent Access to Objects......Page 483
14.7 Java Synchronized Objects......Page 484
14.8 Resources and Java Garbage Collection......Page 485
14.10 Java Memory Model......Page 486
15.1 HISTORY OF LOGIC PROGRAMMING......Page 487
15.2 BRIEF OVERVIEW OF THE LOGIC PROGRAMMING PARADIGM......Page 488
15.2.2 Interactive Programming......Page 489
15.3.1 Terms......Page 490
15.3.2 Substitutions......Page 491
15.3.3 Most General Unifiers......Page 492
MARTELLI–MONTANARI ALGORITHM......Page 493
15.4 CLAUSES AS PARTS OF PROCEDURE DECLARATIONS......Page 494
15.4.2 Computation Process......Page 495
15.4.3 Clauses......Page 497
15.5.1 Multiple Uses of a Single Program......Page 498
A type assignment......Page 500
A Sequence Program......Page 502
Difference lists......Page 503
15.6.2 Arithmetic Comparison Relations......Page 504
15.6.3 Evaluation of Arithmetic Expressions......Page 507
15.7 CONTROL, AMBIVALENT SYNTAX, AND META-VARIABLES......Page 508
15.7.1 Cut......Page 509
15.7.2 Ambivalent Syntax and Meta-variables......Page 510
Disjunction......Page 511
If-then-else......Page 512
15.7.4 Negation as Failure......Page 513
15.7.5 Higher-Order Programming and Meta-Programming in Prolog......Page 514
Program manipulation facilities......Page 515
15.8 ASSESSMENT OF PROLOG......Page 517
Complex Semantics of Various Built-ins......Page 518
15.10 CHAPTER SUMMARY......Page 519
Acknowledgements......Page 520
A.1 PROCEDURAL AND OBJECT-ORIENTED ORGANIZATION......Page 521
A.1.1 Shape Program: Typecase Version......Page 522
A.1.2 Shape Program: Object-Oriented Version......Page 528
Glossary......Page 533
Index......Page 537