Agda code accompanying the paper "Locally Nameless Sets"

© 2023 Andrew Pitts, University of Cambridge

Agda (version 2.6.2.2) was used to develop the theory of locally nameless sets and to check some of the proofs in the paper

Andrew M. Pitts. 2023. Locally Nameless Sets. Proc. ACM Program. Lang. 7, POPL, Article 17, pp 488-514, January 2023. https://doi.org/10.1145/3571210

The code mainly targets proofs that involve equational reasoning combined with the use of atoms and indices that are sufficiently fresh (via cofinite quantification). Some of these proofs involve a lot of nested case analysis on elements of sets with decidable equality (atoms and indices); some of the equational axioms are unfamiliar-looking and combinatorially complicated; and it is easy to forget to check necessary freshness conditions are satisfied when doing informal proofs. For all these reasons the use of an interactive theorem prover to produce machine-checked proofs was essential to gain assurance that the results in the paper are correct.

The Agda code is stand-alone: some standard definitions (that might otherwise be called from Agda's Standard Library) are collected in the file Prelude. The last part of the development requires function extensionality, which we postulate in the file FunExt. The root is the file Everything.