Programming Languages: Principles and Paradigms

Foreword......Page 7
Introduction......Page 8
 Acknowledgements......Page 10
Contents......Page 11
 The Concepts of Abstract Machine and of Interpreter......Page 18
  The Interpreter......Page 19
  An Example of an Abstract Machine: The Hardware Machine......Page 22
   The language of the physical machine......Page 23
   Interpreter......Page 24
  Implementation of an Abstract Machine......Page 26
   Implementation in Hardware......Page 27
   Emulation Using Firmware......Page 28
   Notation......Page 30
    Purely compiled implementation......Page 31
   Comparing the Two Techniques......Page 33
  Implementation: The Real Case and The Intermediate Machine......Page 34
 Hierarchies of Abstract Machines......Page 38
 Exercises......Page 41
 References......Page 42
 Levels of Description......Page 43
 Grammar and Syntax......Page 44
  Context-Free Grammars......Page 46
   BNF......Page 47
   Derivations and languages......Page 48
   Derivation Trees......Page 49
   Ambiguity......Page 52
 Contextual Syntactic Constraints......Page 55
  Lexical analysis......Page 57
  Syntactic analysis......Page 59
  Generation of intermediate forms......Page 60
 Semantics......Page 61
  State......Page 63
  Transitions......Page 64
  Command semantics......Page 65
  Computations......Page 66
 Implementation......Page 68
 Exercises......Page 69
 References......Page 70
 The Halting Problem......Page 72
 Expressiveness of Programming Languages......Page 74
 Formalisms for Computability......Page 75
 There are More Functions than Algorithms......Page 76
 Chapter Summary......Page 78
 Exercises......Page 79
 References......Page 80
 Names and Denotable Objects......Page 81
  Denotable Objects......Page 83
 Environments and Blocks......Page 84
  Blocks......Page 85
  Types of Environment......Page 86
  Operations on Environments......Page 89
 Scope Rules......Page 91
  Static Scope......Page 92
  Dynamic Scope......Page 94
  Some Scope Problems......Page 96
 Chapter Summary......Page 99
 Bibliographical Notes......Page 100
 Exercises......Page 101
 References......Page 104
 Techniques for Memory Management......Page 105
 Dynamic Memory Management Using Stacks......Page 107
  Activation Records for In-line Blocks......Page 110
  Activation Records for Procedures......Page 111
  Stack Management......Page 113
  Fixed-Length Blocks......Page 115
  Variable-Length Blocks......Page 117
   Single free list......Page 118
  Static Scope: The Static Chain......Page 119
  Static Scope: The Display......Page 123
  Dynamic Scope: Association Lists and CRT......Page 125
   Central Referencing environment Table (CRT)......Page 128
 Chapter Summary......Page 129
 Exercises......Page 130
 References......Page 132
 Expressions......Page 133
   Infix Notation......Page 134
   Prefix Notation......Page 135
   Postfix Notation......Page 136
   Infix Notation: Precedence and Associativity......Page 137
   Prefix Notation......Page 138
  Evaluation of Expressions......Page 139
   Subexpression Evaluation Order......Page 141
 The Concept of Command......Page 143
  The Variable......Page 144
  Assignment......Page 145
   Composite Command......Page 150
   Goto......Page 151
   Other sequence control commands......Page 153
   If......Page 154
   Case......Page 155
   Unbounded iteration......Page 158
   Bounded iteration......Page 159
   Expressiveness of bounded iteration......Page 161
   The for in C......Page 162
   For-each......Page 163
 Structured Programming......Page 164
 Recursion......Page 166
  Tail Recursion......Page 169
  Recursion or Iteration?......Page 173
 Chapter Summary......Page 174
 Exercises......Page 175
 References......Page 177
Control Abstraction......Page 178
  Parameters......Page 179
  Functional Abstraction......Page 180
   Call by value......Page 182
   Call by reference......Page 183
   Call by constant......Page 184
   Call by result......Page 185
   Call by value-result......Page 186
   Call by name......Page 187
 Higher-Order Functions......Page 191
  Functions as Parameters......Page 192
   Implementation of deep binding......Page 193
   Binding policy and static scope......Page 194
   What defines the environment......Page 196
  Functions as Results......Page 197
 Exceptions......Page 199
  Pragmatics......Page 202
  Implementing Exceptions......Page 203
 Chapter Summary......Page 204
 Bibliographical Notes......Page 206
 Exercises......Page 207
 References......Page 209
 Data Types......Page 210
  Types as Support for Conceptual Organisation......Page 211
  Types for Correctness......Page 212
  Types and Implementation......Page 213
 Type Systems......Page 214
  Static and Dynamic Checking......Page 215
 Scalar Types......Page 216
  Characters......Page 217
  Fixed Point......Page 218
  Complex......Page 219
  Enumerations......Page 220
  Intervals......Page 221
  Records......Page 222
  Variant Records and Unions......Page 224
   Unions in C......Page 225
   Variants and Security......Page 226
  Arrays......Page 229
   Checking......Page 230
   Storage and Calculation of Indices......Page 231
   Form of an Array: Where an Array is Allocated......Page 232
   Dope Vectors......Page 233
  Sets......Page 234
  Pointers......Page 235
   Pointer Arithmetic......Page 237
   Deallocation......Page 238
  Recursive Types......Page 240
  Functions......Page 242
 Equivalence......Page 243
  Equivalence by Name......Page 244
  Structural Equivalence......Page 245
 Compatibility and Conversion......Page 247
  Coercions......Page 248
 Polymorphism......Page 250
  Overloading......Page 251
  Universal Parametric Polymorphism......Page 252
   Implicit Polymorphism......Page 253
  Subtype Universal Polymorphism......Page 254
  Remarks on the Implementation......Page 255
 Type Checking and Inference......Page 257
 Safety: An Evaluation......Page 259
 Avoiding Dangling References......Page 260
  Tombstone......Page 261
  Locks and Keys......Page 262
 Garbage Collection......Page 263
  Reference Counting......Page 264
  Mark and Sweep......Page 266
  Interlude: Pointer Reversal......Page 267
  Copy......Page 268
 Chapter Summary......Page 271
 Exercises......Page 272
 References......Page 275
 Abstract Data Types......Page 277
 Information Hiding......Page 280
 Modules......Page 283
 Chapter Summary......Page 284
 Exercises......Page 287
 References......Page 288
 The Limits of Abstract Data Types......Page 289
 Fundamental Concepts......Page 293
  Objects......Page 294
  Classes......Page 295
   Objects in the heap and on the stack......Page 298
  Subtypes......Page 299
   Redefinition of a method......Page 300
   Abstract classes......Page 301
   The subtype relation......Page 302
   Constructors......Page 303
   Inheritance and visibility......Page 304
   Single and multiple inheritance......Page 305
  Dynamic Method Lookup......Page 309
  Objects......Page 313
  Classes and inheritance......Page 314
  Single Inheritance......Page 315
   Downcasting......Page 316
  The Problem of Fragile Base Class......Page 317
  Dynamic Method Dispatch in the JVM......Page 318
   Vtable Structure......Page 321
   Replicated multiple inheritance......Page 323
   Shared multiple inheritance......Page 324
 Polymorphism and Generics......Page 326
  Subtype Polymorphism......Page 327
  Generics in Java......Page 329
  Implementation of Generics in Java......Page 333
  Generics, Arrays and Subtype Hierarchy......Page 335
   Supertypes and Views......Page 337
 Bibliographical Notes......Page 340
 Exercises......Page 341
 References......Page 343
 Computations without State......Page 345
  Expressions and Functions......Page 347
  Computation as Reduction......Page 349
  The Fundamental Ingredients......Page 350
 Evaluation......Page 351
  Capture-Free Substitution......Page 352
  Evaluation Strategies......Page 353
   Evaluation by name......Page 354
  Comparison of the Strategies......Page 355
  Local Environment......Page 357
  Types......Page 358
  Pattern Matching......Page 359
  Infinite Objects......Page 361
  Imperative Aspects......Page 362
 Implementation: The SECD Machine......Page 365
 The Functional Paradigm: An Assessment......Page 367
  Program Correctness......Page 368
  Program schemata......Page 369
 Fundamentals: The lambda-calculus......Page 370
  Substitution......Page 371
  Normal forms......Page 372
  Fixpoint operators......Page 373
 Chapter Summary......Page 376
 Exercises......Page 377
 References......Page 378
 Deduction as Computation......Page 380
  Terminological Note......Page 381
  An Example......Page 382
   Alphabet......Page 385
   Terms......Page 386
  Logic Programs......Page 387
  The Logic Variable......Page 388
  Substitution......Page 390
  Most General Unifier......Page 392
  A Unification Algorithm......Page 394
   Martelli and Montanari\'s unification algorithm......Page 395
  The Herbrand Universe......Page 398
  Declarative and Procedural Interpretation......Page 399
  Procedure Calls......Page 400
   Evaluation of a non-atomic goal......Page 401
   Heads with arbitrary terms......Page 402
  Control: Non-determinism......Page 403
   Backtracking in Prolog......Page 404
  Some Examples......Page 406
  Prolog......Page 409
   Arithmetic......Page 410
   Cut......Page 411
   Negation......Page 412
  Logic Programming and Databases......Page 414
  Logic Programming with Constraints......Page 415
 Advantages and Disadvantages of the Logic Paradigm......Page 417
 Chapter Summary......Page 419
 Exercises......Page 420
 References......Page 422
 Beginnings......Page 423
 Factors in the Development of Languages......Page 425
  FORTRAN......Page 427
  Algol......Page 428
  LISP......Page 429
  Simula......Page 430
  C......Page 431
  Pascal......Page 432
  Declarative languages......Page 433
  PROLOG......Page 434
 The 1980s......Page 435
  C++......Page 436
  CLP......Page 437
  Java......Page 438
 Chapter Summary......Page 440
 References......Page 441
Index......Page 443