On this page:
Notes on PLFA
8.1

Notes on PLFA

\(\newcommand{\la}{\lambda} \newcommand{\Ga}{\Gamma} \newcommand{\ra}{\rightarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\La}{\Leftarrow} \newcommand{\tl}{\triangleleft} \newcommand{\ir}[3]{\displaystyle\frac{#2}{#3}~{\textstyle #1}}\)

(Prabhakar Ragde, 2021)

These notes provide additional commentary (or gloss, or a remix) on/of the textbook "Programming Language Foundations in Agda" by Wadler, Kokke, and Siek, in the context of CS 747 at the University of Waterloo in Winter 2022.

Thanks to Wen Kokke and David Darais for helpful discussions and answers to my questions, and to the students of CS 842 who provided useful feedback, particularly Miti Mazumdar.

    1 Demo: Agda in Action

    2 Preface

    3 Getting Started

    4 Naturals

      4.1 Prelude

      4.2 Unpacking the inference rules

      4.3 Operations on naturals

      4.4 Multiplication

      4.5 Monus

    5 Induction

      5.1 Properties of operators

      5.2 Associativity

      5.3 Commutativity

      5.4 Building proofs interactively

    6 Relations

      6.1 Defining relations

      6.2 Implicit arguments

      6.3 Inversion

      6.4 Properties of relations

      6.5 Reflexivity

      6.6 Transitivity

      6.7 Anti-symmetry

      6.8 Total

      6.9 Monotonicity

      6.10 Strict inequality

      6.11 Even and odd

    7 Equality

      7.1 Equality is an equivalence relation

      7.2 Congruence and substitution

      7.3 Rewriting expanded

      7.4 Leibniz equality

    8 Isomorphism

      8.1 Lambda expressions

      8.2 Function composition

      8.3 Extensionality

      8.4 Introducing isomorphism

      8.5 Isomorphism is an equivalence

      8.6 Embedding

    9 Connectives

      9.1 Conjunction is product

      9.2 Truth is unit

      9.3 Disjunction is sum

      9.4 False is empty

      9.5 Implication is function

      9.6 Distribution

    10 Negation

      10.1 Intuitive and Classical Logic

    11 Quantifiers

    12 Decidable

      12.1 Relating evidence and computation

      12.2 The best of both worlds

      12.3 Logical connectives

      12.4 Proof by reflection

    13 Lists

      13.1 List syntax

      13.2 Append

      13.3 Reasoning about length

      13.4 Faster reverse

      13.5 Map

      13.6 Monoids

      13.7 All

      13.8 Any

      13.9 All and append

    14 Lambda

      14.1 Syntax of terms

      14.2 Example terms

      14.3 Bound and free variables

      14.4 Values

      14.5 Substitution

      14.6 Reduction

      14.7 Reflexive and transitive closure

      14.8 Confluence

      14.9 Examples of reductions

      14.10 Typing

      14.11 Typing judgment

    15 Properties

      15.1 Values do not reduce

      15.2 Progress

      15.3 Prelude to preservation

      15.4 Evaluation

      15.5 Reduction is deterministic

    16 DeBruijn

    17 More

    18 Bisimulation

    19 Inference

      19.1 Inference rules as algorithms

      19.2 Synthesizing and inheriting types

      19.3 Soundness and completeness

    20 Untyped

      20.1 Untyped is uni-typed

      20.2 Neutral and normal terms

      20.3 Reduction step

      20.4 Natural numbers and fixpoints

    21 Confluence, BigStep, and Part 3