Focusing and higher-order abstract syntax
Open Access
- 7 January 2008
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 43 (1) , 359-369
Abstract
Focusing is a proof-search strategy, originating in linear logic, that elegantly eliminates inessential nondeterminism, with one byproduct being a correspondence between focusing proofs and programs with explicit evaluation order. Higher-order abstract syntax (HOAS) is a technique for representing higher-order programming language constructs (e.g., λ's) by higher-order terms at the"meta-level", thereby avoiding some of the bureaucratic headaches of first-order representations (e.g., capture-avoiding substitution). This paper begins with a fresh, judgmental analysis of focusing for intuitionistic logic (with a full suite of propositional connectives), recasting the "derived rules" of focusing as iterated inductive definitions . This leads to a uniform presentation, allowing concise, modular proofs of the identity and cut principles. Then we show how this formulation of focusing induces, through the Curry-Howard isomorphism, a new kind of higher-order encoding of abstract syntax: functions are encoded by maps from patterns to expressions. Dually, values are encoded as patterns together with explicit substitutions . This gives us pattern-matching "for free", and lets us reason about a rich type system with minimal syntactic overhead. We describe how to translate the language and proof of type safety almost directly into Coq using HOAS, and finally, show how the system's modular design pays off in enabling a very simple extension with recursion and recursive types.Keywords
This publication has 23 references indexed in Scilit:
- Contextual modal type theoryACM Transactions on Computational Logic, 2008
- Classical isomorphisms of typesMathematical Structures in Computer Science, 2005
- Pattern matching as cut eliminationTheoretical Computer Science, 2004
- Control categories and duality: on the categorical semantics of the lambda-mu calculusMathematical Structures in Computer Science, 2001
- Locus Solum: From the rules of logic to the logic of rulesMathematical Structures in Computer Science, 2001
- A judgmental reconstruction of modal logicMathematical Structures in Computer Science, 2001
- Higher-order abstract syntax in Coq1995
- Logic Programming with Focusing Proofs in Linear LogicJournal of Logic and Computation, 1992
- Explicit substitutionsJournal of Functional Programming, 1991
- Untersuchungen ber das logische Schlie en. IMathematische Zeitschrift, 1935