Substitution Without Copy and Paste
Defining substitution for a language with binders like the simply typed -calculus requires repetition, defining substitution and renaming separately.To verify the categorical properties of this calculus, we must repeat the same argument many times.We present a lightweight method that avoids repetition and that gives rise to a simply typed category with families (CwF) isomorphic to the initial simply typed CwF.Our paper is a literate Agda script.
Authors
- Philip Wadler (ORCID: https://orcid.org/0000-0001-7619-6378)
- Thorsten Altenkirch (ORCID: https://orcid.org/0000-0002-6582-5025)
- Nancy A. Burke
Institutions
- University of Nottingham (GB)
- Imperial College London (GB)
- University of Edinburgh (GB)
Publication Details
- Journal
- Electronic Proceedings in Theoretical Computer Science
- Published
- 2025-10-13
- DOI
- https://doi.org/10.4204/eptcs.431.5
- Primary Topic
- Logic, programming, and type systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00