Types and Programming Languages (The MIT Press)

A comprehensive introduction to type systems and programming languages. A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems—and of programming languages from a type-theoretic perspective—has important applications in software engineering, language design, high-performance compilers, and security. This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material. The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages. A Type System Is A Syntactic Method For Automatically Checking The Absence Of Certain Erroneous Behaviors By Classifying Program Phrases According To The Kinds Of Values They Compute. The Study Of Type Systems--and Of Programming Languages From A Type-theoretic Perspective -- -has Important Applications In Software Engineering, Language Design, High-performance Compilers, And Security. This Text Provides A Comprehensive Introduction Both To Type Systems In Computer Science And To The Basic Theory Of Programming Languages. The Approach Is Pragmatic And Operational; Each New Concept Is Motivated By Programming Examples And The More Theoretical Sections Are Driven By The Needs Of Implementations. Each Chapter Is Accompanied By Numerous Exercises And Solutions, As Well As A Running Implementation, Available Via The Web. Dependencies Between Chapters Are Explicitly Identified, Allowing Readers To Choose A Variety Of Paths Through The Material. The Core Topics Include The Untyped Lambda-calculus, Simple Type Systems, Type Reconstruction, Universal And Existential Polymorphism, Subtyping, Bounded Quantification, Recursive Types, Kinds, And Type Operators. Extended Case Studies Develop A Variety Of Approaches To Modeling The Features Of Object-oriented Languages. 1. Introduction -- 2. Mathematical Preliminaries -- [pt]. 1. Untyped Systems -- 3. Untyped Arithmetic Expressions -- 4. An Ml Implementation Of Arithmetic Expressions -- 5. The Untyped Lambda-calculus -- 6. Nameless Representation Of Terms -- 7. An Ml Implementation Of The Lambda-calculus -- [pt]. 2. Simple Types -- 8. Typed Arithmetic Expressions -- 9. Simply Typed Lambda-calculus -- 10. An Ml Implementation Of Simple Types -- 11. Simple Extensions -- 12. Normalization -- 13. References -- 14. Exceptions -- [pt]. 3. Subtyping -- 15. Subtyping -- 16. Metatheory Of Subtyping -- 17. An Ml Implementation Of Subtyping -- 18. Case Study : Imperative Objects -- 19. Case Study : Featherweight Java -- [pt]. 4. Recursive Types -- 20. Recursive Types -- 21. Metatheory Of Recursive Types -- [pt.]. 5. Polymorphism -- 22. Type Reconstruction -- 23. Universal Types -- 24. Existential Types -- 25. An Ml Implementation Of System F -- 26. Bounded Quantification -- 27. Case Study : Imperative Objects, Redux -- 28. Metatheory Of Bounded Quantification -- [pt]. 6. Higher-order Systems -- 29. Type Operators And Kinding -- 30. Higher-order Polymorphism -- 31. Higher-order Subtyping. Benjamin C. Pierce. Includes Bibliographical References (p. [567]-603) And Index. Contents 6 Preface 14 1 Introduction 24 2 Mathematical Preliminaries 38 I Untyped Systems 44 3 Untyped Arithmetic Expressions 46 4 An ML Implementation of Arithmetic Expressions 68 5 The Untyped Lambda-Calculus 74 6 Nameless Representation of Terms 98 7 An ML Implementation of the Lambda-Calculus 106 II Simple Types 112 8 Typed Arithmetic Expressions 114 9 Simply Typed Lambda-Calculus 122 10 An ML Implementation of Simple Types 136 11 Simple Extensions 140 12 Normalization 172 13 References 176 14 Exceptions 194 III Subtyping 202 15 Subtyping 204 16 Metatheory of Subtyping 232 17 An ML Implementation of Subtyping 244 18 Case Study: Imperative Objects 248 19 Case Study: Featherweight Java 270 IV Recursive Types 288 20 Recursive Types 290 21 Metatheory of Recursive Types 304 V Polymorphism 338 22 Type Reconstruction 340 23 Universal Types 362 24 Existential Types 386 25 An ML Implementation of System F 404 26 Bounded Quantification 412 27 Case Study: Imperative Objects, Redux 434 28 Metatheory of Bounded Quantification 440 VI Higher-Order Systems 460 29 Type Operators and Kinding 462 30 Higher-Order Polymorphism 472 31 Higher-Order Subtyping 490 32 Case Study: Purely Functional Objects 498 Appendices 514 A Solutions to Selected Exercises 516 B Notational Conventions 588 References 590 Index 628