A modal analysis of staged computation
Authors:
Top Cited Papers
Open Access
- 1 May 2001
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 48 (3) , 555-604
Abstract
We show that a type system based on the intuitionistic modal logic S4 provides an expressive framework for specifying and analyzing computation stages in the context of typed λ-calculi and functional languages. We directly demonstrate the sense in which our λ e →□ -calculus captures staging, and also give a conservative embeddng of Nielson and Nielson's two-level functional language in our functional language Mini-ML □ , thus proving that binding-time correctness is equivalent to modal correctness on this fragment. In addition, Mini-ML □ can also express immediate evaluation and sharing of code across multiple stages, thus supporting run-time code generation as well as partial evaluation.Keywords
This publication has 29 references indexed in Scilit:
- A judgmental reconstruction of modal logicMathematical Structures in Computer Science, 2001
- Programming languages capturing complexity classesACM SIGACT News, 2000
- Modal types as staging specifications for run-time code generationACM Computing Surveys, 1998
- Computational types from a logical perspectiveJournal of Functional Programming, 1998
- Propositional Lax LogicInformation and Computation, 1997
- Monad as modalityTheoretical Computer Science, 1997
- On the unity of logicAnnals of Pure and Applied Logic, 1993
- Logic programming in the LF logical framework1991
- A partial evaluator for the untyped lambda-calculusJournal of Functional Programming, 1991
- Semantical Analysis of Modal Logic I Normal Modal Propositional CalculiMathematical Logic Quarterly, 1963