A Categorical Normalization Proof for the Modal Lambda-Calculus
Authors:
- Jason Z. S. HuJHJason Z. S. Hu
- Brigitte PientkaBPBrigitte Pientka
Preprint
Abstract
We investigate a simply typed modal $\lambda$-calculus, $\lambda^{\to\square}$, due to Pfenning, Wong and Davies, where we define a well-typed term with respect to a context stack that captures the possible world semantics in a syntactic way. It provides logical foundation for multi-staged meta-programming. Our main contribution in this paper is a normalization by evaluation (NbE) algorithm for $\lambda^{\to\square}$ which we prove sound and complete. The NbE algorithm is a moderate extension to the standard presheaf model of simply typed $\lambda$-calculus. However, central to the model construction and the NbE algorithm is the observation of Kripke-style substitutions on context stacks which brings together two previously separate concepts, structural modal transformations on context stacks and substitutions for individual assumptions. Moreover, Kripke-style substitutions allow us to give a formulation for contextual types, which can represent open code in a meta-programming setting. Our work lays the foundation for extending the logical foundation by Pfenning, Wong, and Davies towards building a practical, dependently typed foundation for meta-programming.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Modal dependent type theory and dependent right adjointsMathematical Structures in Computer Science, 2019
- Fitch-Style Modal Lambda Calculi2018
- Brouwer's fixed-point theorem in real-cohesive homotopy type theoryMathematical Structures in Computer Science, 2017
- Categorical and Kripke Semantics for Constructive S4 Modal Logic2001
- A judgmental reconstruction of modal logicMathematical Structures in Computer Science, 2001
- On the Strong Normalization of Natural Deduction with Permutation-ConversionsLecture Notes in Computer Science, 1999
- Explicit substitutitions for constructive necessity1998
- A Computational Interpretation of Modal Proofs1996
- On a Modal λ-Calculus for S4Electronic Notes in Theoretical Computer Science, 1995
- Semantical Analysis of Modal Logic I Normal Modal Propositional CalculiMathematical Logic Quarterly, 1963