Programming Languages: Principles and Paradigms (2nd Edition)

Foreword to the First Edition
Preface to the Second Edition
Use of the Book
Acknowledgements
Preface to the First Edition
Acknowledgements
Contents
1 Abstract Machines
1.1 The Concepts of Abstract Machine and the 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 Summary
1.5 Bibliographical Notes
1.6 Exercises
2 Describing 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 Summary
2.9 Bibliographical Notes
2.10 Exercises
3 Foundations
3.1 The Halting Problem
3.2 Undecidable Problems
3.2.1 The Standard Model
3.2.2 More Undecidable Problems
3.3 Formalisms for Computability
3.4 There Are More Functions Than Algorithms
3.5 Summary
3.6 Bibliographical Notes
3.7 Exercises
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 Summary
4.5 Bibliographical Notes
4.6 Exercises
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 Summary
5.7 Bibliographical Notes
5.8 Exercises
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 Summary
6.7 Bibliographical Notes
6.8 Exercises
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.2.3 Anonymous Functions: Lambda Expressions
7.3 Exceptions
7.3.1 Implementing Exceptions
7.4 Summary
7.5 Bibliographical Notes
7.6 Exercises
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 Unit
8.3.8 Enumerations
8.3.9 Intervals
8.3.10 Ordered Types
8.4 Composite Types
8.4.1 Records
8.4.2 Unions
8.4.3 Tagged Unions
8.4.4 Arrays
8.4.5 Sets
8.4.6 Pointers
8.4.7 Sequences
8.4.8 Recursive Types
8.4.9 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 Assessment
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 Summary
8.13 Bibliographical Notes
8.14 Exercises
9 Data Abstraction
9.1 Abstract Data Types
9.2 Information Hiding
9.2.1 Representation Independence
9.3 Modules
9.4 Summary
9.5 Bibliographical Notes
9.6 Exercises
10 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 Summary
10.6 Bibliographical Notes
10.7 Exercises
11 Functional Programming Paradigm
11.1 Computing 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 Pattern Matching
11.3.4 Programming in a Functional Style
11.3.5 Types
11.3.6 Infinite Objects
11.3.7 Imperative Aspects
11.4 An Assessment
11.5 Implementation: The SECD Machine
11.6 Fundamentals: The λ-Calculus
11.7 Summary
11.8 Bibliographical Note
11.9 Exercises
12 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.6 Advantages and Disadvantages of the Logic Paradigm
12.7 Summary
12.8 Bibliographical Notes
12.9 Exercises
13 Constraint Programming Paradigm
13.1 Constraint Programming
13.1.1 Types of Problems
13.2 Constraint Logic Programs
13.2.1 Syntax and Semantics of CLP
13.3 Generate and Test Versus Constraint and Generate
13.3.1 A Further Example
13.4 MiniZinc
13.4.1 A MiniZinc CSP Model
13.4.2 A MiniZinc COP Model
13.5 Summary
13.6 Bibliographical Notes
13.7 Exercises
14 Concurrent Programming
14.1 Threads and Processes
14.2 A Brief Historical Overview
14.3 Types of Concurrent Programming
14.3.1 Communication Mechanisms
14.3.2 Synchronisation Mechanisms
14.4 Shared Memory
14.4.1 Busy Waiting
14.4.2 Scheduler-Based Synchronisation
14.5 Message Exchange
14.5.1 Naming Mechanisms
14.5.2 Asynchronous Communication
14.5.3 Synchronous Communication
14.5.4 Remote Procedure Call and Rendez-Vous
14.6 Non-determinism and Parallel Composition
14.6.1 Parallel Composition
14.7 Concurrency in Java
14.7.1 Creation of Threads
14.7.2 Scheduling and Termination of Threads
14.7.3 Synchronisation and Communication Between Threads
14.8 Summary
14.9 Bibliographical Notes
14.10 Exercises
15 Service-Oriented Programming Paradigm
15.1 Towards Services
15.1.1 Distributed Programs
15.1.2 Open Systems
15.1.3 Loose Coupling and Interoperability
15.1.4 Approaching Services
15.2 Elements of Service-Oriented Programming
15.2.1 Services, a Layered View
15.2.2 Data Types
15.2.3 Messaging Patterns
15.2.4 Operations and Interfaces
15.2.5 Behaviour
15.3 Service-Oriented Architectures
15.3.1 The First Generation: Web Services
15.3.2 Second Generation: Microservices and Serverless
15.4 Summary
15.5 Bibliographical Note
15.6 Exercises
16 Short Historical Perspective
16.1 Beginnings
16.2 Factors in the Development of Languages
16.3 1950s and 1960s
16.4 1970s
16.5 1980s
16.6 1990s
16.7 2000s
16.8 2010s
16.9 Summary
16.10 Bibliographical Notes
Index