This text develops a comprehensive theory of programming languages based on type systems and structural operational semantics. Language concepts are precisely defined by their static and dynamic semantics, presenting the essential tools both intuitively and rigorously while relying on only elementary mathematics. These tools are used to analyze and prove properties of languages and provide the framework for combining and comparing language features. The broad range of concepts includes fundamental data types such as sums and products, polymorphic and abstract types, dynamic typing, dynamic dispatch, subtyping and refinement types, symbols and dynamic classification, parallelism and cost semantics, and concurrency and distribution. The methods are directly applicable to language implementation, to the development of logics for reasoning about programs, and to the formal verification language properties such as type safety. This thoroughly revised second edition includes exercises at the end of nearly every chapter and a new chapter on type refinements.
Table of Contents
Part I Judgments and Rules
Chapter 1 Abstract Syntax
Chapter 2 Inductive Definitions
Chapter 3 Hypothetical and General Judgments
Part II Statics and Dynamics
Chapter 4 Statics
Chapter 5 Dynamics
Chapter 6 Type Safety
Chapter 7 Evaluation Dynamics
Part III Total Functions
Chapter 8 Function Definitions and Values
Chapter 9 System T of Higher-Order Recursion
Part IV Finite Data Types
Chapter 10 Product Types
Chapter 11 Sum Types
Part V Types and Propositions
Chapter 12 Constructive Logic
Chapter 13 Classical Logic
Part VI Infinite Data Types
Chapter 14 Generic Programming
Chapter 15 Inductive and Coinductive Types
Part VII Variable Types
Chapter 16 System F of Polymorphic Types
Chapter 17 Abstract Types
Chapter 18 Higher Kinds
Part VIII Partiality and Recursive Types
Chapter 19 System PCF of Recursive Functions
Chapter 20 System FPC of Recursive Types
Part IX Dynamic Types
Chapter 21 The Untyped λ-Calculus
Chapter 22 Dynamic Typing
Chapter 23 Hybrid Typing
Part X Subtyping
Chapter 24 Structural Subtyping
Chapter 25 Behavioral Typing
Chapter Part XI Dynamic Dispatch
Chapter 26 Classes and Methods
Chapter 27 Inheritance
Part XII Control Flow
Chapter 28 Control Stacks
Chapter 29 Exceptions
Chapter 30 Continuations
Part XIII Symbolic Data
Chapter 31 Symbols
Chapter 32 Fluid Binding
Chapter 33 Dynamic Classification
Part XIV Mutable State
Chapter 34 Modernized Algol
Chapter 35 Assignable References
Chapter 36 Lazy Evaluation
Part XV Parallelism
Chapter 37 Nested Parallelism
Chapter 38 Futures and Speculations
Part XVI Concurrency and Distribution
Chapter 39 Process Calculus
Chapter 40 Concurrent Algol
Chapter 41 Distributed Algol
Part XVII Modularity
Chapter 42 Modularity and Linking
Chapter 43 Singleton Kinds and Subkinding
Chapter 44 Type Abstractions and Type Classes
Chapter 45 Hierarchy and Parameterization
Chapter Part XVIII Equational Reasoning
Chapter 46 Equality for System T
Chapter 47 Equality for System PCF
Chapter 48 Parametricity
Chapter 49 Process Equivalence
Appendix A Background on Finite Sets
1