Normalization by evaluation for modal dependent type theory
Open Access
- 2 October 2023
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of Functional Programming
- Vol. 33, e7
Abstract
We present the Kripke-style modal type theory, Mint , which combines dependent types and the necessity modality. It extends the Kripke-style modal lambda-calculus by Pfenning and Davies to the full Martin-Löf type theory. As such it encompasses dependently typed variants of system K , T , K 4, and S 4. Further, Mint seamlessly supports a full universe hierarchy, usual inductive types, and large eliminations. In this paper, we give a modular sound and complete normalization-by-evaluation (NbE) proof for Mint based on an untyped domain model, which applies to all four aforementioned modal systems without modification. This NbE proof yields a normalization algorithm for Mint, which can be directly implemented. To further strengthen our results, our models and the NbE proof are fully mechanized in Agda and we extract a Haskell implementation of our NbE algorithm from it.Keywords
This publication has 47 references indexed in Scilit:
- Type Theory Should Eat ItselfElectronic Notes in Theoretical Computer Science, 2009
- On equivalence and canonical forms in the LF type theoryACM Transactions on Computational Logic, 2005
- Primitive recursion for higher-order abstract syntaxTheoretical Computer Science, 2001
- A modal analysis of staged computationJournal of the ACM, 2001
- A judgmental reconstruction of modal logicMathematical Structures in Computer Science, 2001
- A general formulation of simultaneous inductive-recursive definitions in type theoryThe Journal of Symbolic Logic, 2000
- A sound reduction semantics for untyped CBN multi-stage computation. Or, the theory of MetaML is non-trivalACM SIGPLAN Notices, 1999
- Intuitionistic model constructions and normalization proofsMathematical Structures in Computer Science, 1997
- An Intuitionistic Theory of Types: Predicative Part1975
- Semantical Analysis of Modal Logic I Normal Modal Propositional CalculiMathematical Logic Quarterly, 1963