Practical.Foundations.for.Programming.Languages.2nd

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