Agda code accompanying the paper "Locally Nameless Sets"

No Thumbnail Available
Change log

The zip archive contains code for Agda (version that 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 (January 2023), 27 pages.

The root is the file Everything.agda (for browsable code start at html/Everything.html).

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 the Agda Standard Library) are collected in the file Prelude.agda. The last part of the development requires function extensionality, which we postulate in the file FunExt.agda.

Software / Usage instructions
Agda (version
Agda, locally nameless, name binding, metatheory of syntax, cofinite quantification, category theory, initial algebra