Layered Modal Type Theory
Open Access
- 5 April 2024
- book chapter
- Published by Springer Nature
- p. 52-82
Abstract
We introduce layering to modal type theory to combine type theory with intensional analysis. 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 $$\lambda $$ -calculus with no modality. Layer 1 is obtained by extending the core language with one layer of contextual $$\square $$ types to support pattern matching on potentially open code from layer 0 while retaining normalization. Although both layers fundamentally share the same language 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. 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
All Related Versions
This publication has 54 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