1 Abstract Machines
1.1 The Concepts of Abstract Machine and of Interpreter
1.1.1 The Interpreter
1.1.2 An Example of an Abstract Machine: The Hardware Machine
1.2 Implementation of a Language
1.2.1 Implementation of an Abstract Machine
1.2.2 Implementation: The Ideal Case
1.2.3 Implementation: The Real Case and The Intermediate Machine
1.3 Hierarchies of Abstract Machines
1.4 Chapter Summary
1.5 Bibliographic Notes
1.6 Exercises
References
2 How to Describe a Programming Language
2.1 Levels of Description
2.2 Grammar and Syntax
2.2.1 Context-Free Grammars
2.3 Contextual Syntactic Constraints
2.4 Compilers
2.5 Semantics
2.6 Pragmatics
2.7 Implementation
2.8 Chapter Summary
2.9 Bibliographical Notes
2.10 Exercises
References
3 Foundations
3.1 The Halting Problem
3.2 Expressiveness of Programming Languages
3.3 Formalisms for Computability
3.4 There are More Functions than Algorithms
3.5 Chapter Summary
3.6 Bibliographical Notes
3.7 Exercises References
4 Names and The Environment
4.1 Names and Denotable Objects
4.1.1 Denotable Objects
4.2 Environments and Blocks
4.2.1 Blocks
4.2.2 Types of Environment
4.2.3 Operations on Environments
4.3 Scope Rules
4.3.1 Static Scope
4.3.2 Dynamic Scope
4.3.3 Some Scope Problems
4.4 Chapter Summary
4.5 Bibliographical Notes
4.6 Exercises
References
5 Memory Management
5.1 Techniques for Memory Management
5.2 Static Memory Management
5.3 Dynamic Memory Management Using Stacks
5.3.1 Activation Records for In-line Blocks
5.3.2 Activation Records for Procedures
5.3.3 Stack Management
5.4 Dynamic Management Using a Heap
5.4.1 Fixed-Length Blocks
5.4.2 Variable-Length Blocks
5.5 Implementation of Scope Rules
5.5.1 Static Scope: The Static Chain
5.5.2 Static Scope: The Display
5.5.3 Dynamic Scope: Association Lists and CRT
5.6 Chapter Summary
5.7 Bibliographic Notes
5.8 Exercises
References
6 Control Structure
6.1 Expressions
6.1.1 Expression Syntax
6.1.2 Semantics of Expressions
6.1.3 Evaluation of Expressions
6.2 The Concept of Command
6.2.1 The Variable
6.2.2 Assignment
6.3 Sequence Control Commands
6.3.1 Commands for Explicit Sequence Control
6.3.2 Conditional Commands
6.3.3 Iterative Commands
6.4 Structured Programming
6.5 Recursion
6.5.1 Tail Recursion
6.5.2 Recursion or Iteration?
6.6 Chapter Summary
6.7 Bibliographical Notes
6.8 Exercises
References
7 Control Abstraction
7.1 Subprograms
7.1.1 Functional Abstraction
7.1.2 Parameter Passing
7.2 Higher-Order Functions
7.2.1 Functions as Parameters
7.2.2 Functions as Results
7.3 Exceptions
7.3.1 Implementing Exceptions
7.4 Chapter Summary
7.5 Bibliographical Notes
7.6 Exercises
References
8 Structuring Data
8.1 Data Types
8.1.1 Types as Support for Conceptual Organisation
8.1.2 Types for Correctness
8.1.3 Types and Implementation
8.2 Type Systems
8.2.1 Static and Dynamic Checking
8.3 Scalar Types
8.3.1 Booleans
8.3.2 Characters
8.3.3 Integers
8.3.4 Reals
8.3.5 Fixed Point
8.3.6 Complex
8.3.7 Void
8.3.8 Enumerations
8.3.9 Intervals
8.3.10 Ordered Types
8.4 Composite Types
8.4.1 Records
8.4.2 Variant Records and Unions
8.4.3 Arrays
8.4.4 Sets
8.4.5 Pointers
8.4.6 Recursive Types
8.4.7 Functions
8.5 Equivalence
8.5.1 Equivalence by Name
8.5.2 Structural Equivalence
8.6 Compatibility and Conversion
8.7 Polymorphism
8.7.1 Overloading
8.7.2 Universal Parametric Polymorphism
8.7.3 Subtype Universal Polymorphism
8.7.4 Remarks on the Implementation
8.8 Type Checking and Inference
8.9 Safety: An Evaluation
8.10 Avoiding Dangling References
8.10.1 Tombstone
8.10.2 Locks and Keys
8.11 Garbage Collection
8.11.1 Reference Counting
8.11.2 Mark and Sweep
8.11.3 Interlude: Pointer Reversal
8.11.4 Mark and Compact
8.11.5 Copy
8.12 Chapter Summary
8.13 Bibliographic Notes
8.14 Exercises
References
9 Data Abstraction
9.1 Abstract Data Types
9.2 Information Hiding
9.2.1 Representation Independence
9.3 Modules
9.4 Chapter Summary
9.5 Bibliographical Notes
9.6 Exercises
References
10 The Object-Oriented Paradigm
10.1 The Limits of Abstract Data Types
10.1.1 A First Review
10.2 Fundamental Concepts
10.2.1 Objects
10.2.2 Classes
10.2.3 Encapsulation
10.2.4 Subtypes
10.2.5 Inheritance
10.2.6 Dynamic Method Lookup
10.3 Implementation Aspects
10.3.1 Single Inheritance
10.3.2 The Problem of Fragile Base Class
10.3.3 Dynamic Method Dispatch in the JVM
10.3.4 Multiple Inheritance
10.4 Polymorphism and Generics
10.4.1 Subtype Polymorphism
10.4.2 Generics in Java
10.4.3 Implementation of Generics in Java
10.4.4 Generics, Arrays and Subtype Hierarchy
10.4.5 Covariant and Contravariant Overriding
10.5 Chapter Summary
10.6 Bibliographical Notes
10.7 Exercises
References
11 The Functional Paradigm
11.1 Computations without State
11.1.1 Expressions and Functions
11.1.2 Computation as Reduction
11.1.3 The Fundamental Ingredients
11.2 Evaluation
11.2.1 Values
11.2.2 Capture-Free Substitution
11.2.3 Evaluation Strategies
11.2.4 Comparison of the Strategies
11.3 Programming in a Functional Language
11.3.1 Local Environment
11.3.2 Interactiveness
11.3.3 Types
11.3.4 Pattern Matching
11.3.5 Infinite Objects
11.3.6 Imperative Aspects
11.4 Implementation: The SECD Machine
11.5 The Functional Paradigm: An Assessment
11.6 Fundamentals: The λ-calculus
11.7 Chapter Summary
11.8 Bibliographical Note
11.9 Exercises
References
12 The Logic Programming Paradigm
12.1 Deduction as Computation
12.1.1 An Example
12.2 Syntax
12.2.1 The Language of First-Order Logic
12.2.2 Logic Programs
12.3 Theory of Unification
12.3.1 The Logic Variable
12.3.2 Substitution
12.3.3 Most General Unifier
12.3.4 A Unification Algorithm
12.4 The Computational Model
12.4.1 The Herbrand Universe
12.4.2 Declarative and Procedural Interpretation
12.4.3 Procedure Calls
12.4.4 Control: Non-determinism
12.4.5 Some Examples
12.5 Extensions
12.5.1 Prolog
12.5.2 Logic Programming and Databases
12.5.3 Logic Programming with Constraints
12.6 Advantages and Disadvantages of the Logic Paradigm
12.7 Chapter Summary
12.8 Bibliographical Notes
12.9 Exercises
References
13 A Short Historical Perspective
13.1 Beginnings
13.2 Factors in the Development of Languages
13.3 1950s and 60s
13.4 The 1970s
13.5 The 1980s
13.6 1990s
13.7 Chapter Summary
13.8 Bibliographical Notes
References
Index
