A Layered Approach to Intensional Analysis in Type Theory
Open Access
- 31 December 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 46 (4) , 1-43
Abstract
We introduce layering to modal type theory to support meta-programming and intensional analysis coherently. In particular, we demonstrate this idea by developing a 2-layered modal type theory. At the core of this type theory (layer 0) is a simply typed λ -calculus with no modality. Layer 1 is obtained by extending the core language with one layer of contextual ◻ types to support pattern matching on potentially open code from layer 0 while retaining normalization. Although both layers fundamentally share a uniform syntax and the same typing judgment, we only allow computation at layer 1. As a consequence, layer 0 accurately captures the syntactic representation of code in contrast to the computational behaviors at layer 1. Moreover, the uniform syntax at both layers enables quotation and code running. The system is justified by normalization by evaluation (NbE) using a presheaf model. The normalization algorithm extracted from the model is sound and complete and is implemented in Agda. Layered modal type theory provides a uniform foundation for meta-programming with intensional analysis. We see this work as an important step towards a foundational way to support meta-programming in proof assistants.Keywords
Funding Information
- Natural Sciences and Engineering Research Council of Canada (206263)
- German Federal Ministry of Education and Research (253521)
This publication has 38 references indexed in Scilit:
- Graded Modal Dependent Type Theory2021
- Semantical Analysis of Contextual Types2020
- Towards Certified Meta-Programming with Typed Template-Coq2018
- Fitch-Style Modal Lambda Calculi2018
- The Design and Implementation of BER MetaOCaml2014
- Engineering Proof by Reflection in Agda2013
- Polymorphic Multi-stage Language with Control EffectsLecture Notes in Computer Science, 2011
- On the Strong Normalization of Natural Deduction with Permutation-ConversionsLecture Notes in Computer Science, 1999
- Normalization by Evaluation1998
- Categorical reconstruction of a reduction free normalization proof1995