Types and Programming Languages

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.

Table of Contents

1 Introduction

2 Mathematical Preliminaries

I 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

II 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

Ill Subtyping

15 Subtyping

16 Metatheory of Subtyping

17 An ML Implementation of Subtyping

18 Case Study: Imperative Objects

19 Case Study: Featherweight Java

IV Recursive Types

20 Recursive Types

21 Metatheory of Recursive Types

V 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

VI Higher-Order Systems

29 Type Operators and Kinding

30 Higher-Order Polymorphism

31 Higher-Order Subtyping

32 Case Study: Purely Functional Objects

Appendices

A Solutions to Selected Exercises

B Notational Conventions

Review

–Robin Milner, Computer Laboratory, University of Cambridge

” Types are the leaven of computer programming; they make it digestible. This excellent book uses types to navigate the rich variety of programming languages, bringing a new kind of unity to their usage, theory, and implementation. Its author writes with the authority of experience in all three of these aspects.” –Robin Milner, Computer Laboratory, University of Cambridge

& quot; Types are the leaven of computer programming; they make it digestible. This excellent book uses types to navigate the rich variety of programming languages, bringing a new kind of unity to their usage, theory, and implementation. Its author writes with the authority of experience in all three of these aspects.& quot; –Robin Milner, Computer Laboratory, University of Cambridge

“Types are the leaven of computer programming; they make it digestible. This excellent book uses types to navigate the rich variety of programming languages, bringing a new kind of unity to their usage, theory, and implementation. Its author writes with the authority of experience in all three of these aspects.”–Robin Milner, Computer Laboratory, University of Cambridge

About the Author

Benjamin C. Pierce is Professor of Computer and Information Science at the University of Pennsylvania.