Table of Contents
This book is an introduction to programming language theory using the proof assistant Agda.
Comments on all matters—organisation, material to add, material to remove, parts that require better explanation, good exercises, errors, and typos—are welcome. The book repository is on GitHub. Pull requests are encouraged. There is a private repository of answers to selected questions on github. Please contact one of the authors if you would like to access it.
Front matter
Part 1: Logical Foundations
- Naturals: Natural numbers
- Induction: Proof by Induction
- Relations: Inductive definition of relations
- Equality: Equality and equational reasoning
- Isomorphism: Isomorphism and Embedding
- Connectives: Conjunction, disjunction, and implication
- Negation: Negation, with intuitionistic and classical logic
- Quantifiers: Universals and existentials
- Decidable: Booleans and decision procedures
- Lists: Lists and higher-order functions
Part 2: Programming Language Foundations
- Lambda: Introduction to Lambda Calculus
- Properties: Progress and Preservation
- DeBruijn: Intrinsically-typed de Bruijn representation
- More: Additional constructs of simply-typed lambda calculus
- Bisimulation: Relating reduction systems
- Inference: Bidirectional type inference
- Untyped: Untyped lambda calculus with full normalisation
- Confluence: Confluence of untyped lambda calculus
- BigStep: Big-step semantics of untyped lambda calculus
Part 3: Denotational Semantics
- Denotational: Denotational semantics of untyped lambda calculus
- Compositional: The denotational semantics is compositional
- Soundness: Soundness of reduction with respect to denotational semantics
- Adequacy: Adequacy of denotational semantics with respect to operational semantics
- ContextualEquivalence: Denotational equality implies contextual equivalence
Appendix
- Substitution: Substitution in the untyped lambda calculus
Back matter
Related
Courses taught from the textbook
2024
2023
2022
- Andrej Bauer, University of Ljubljana
- Michael Shulman, University of San Diego
- Peter Thiemann, Albert-Ludwigs University
- Philip Wadler, University of Edinburgh
2021
- Favonia, University of Minnesota
- Prabhakar Ragde, University of Waterloo
- Jacques Carette, McMaster University (based on Prabhakar’s)
2020
- William Cook, University of Texas
- Maria Emilia Maietti and Ingo Blechschmidt, Università di Padova
- John Maraist, University of Wisconsin-La Crosse
- Jeremy Siek, Indiana University
- Ugo de’Liguoro, Università di Torino
2019
- Dan Ghica, University of Birmingham
- Adrian King, San Francisco Types, Theorems, and Programming Languages Meetup
- Prabhakar Ragde, University of Waterloo
- Philip Wadler, University of Edinburgh
- Philip Wadler, Pontifícia Universidade Católica do Rio de Janeiro
2018
- David Darais, University of Vermont
- Philip Wadler, University of Edinburgh
- John Leo, Google Seattle
Please tell us of others!