Skip to Main content Skip to Navigation
Journal articles

Mechanized metatheory revisited

Dale Miller 1 
1 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : When proof assistants and theorem provers implement the metatheory of logical systems, they must deal with a range of syntactic expressions (e.g., types, formulas , and proofs) that involve variable bindings. Since most mature proof assistants do not have built-in methods to treat bindings, they have been extended with various packages and libraries that allow them to encode such syntax using, for example, de Bruijn numerals. We put forward the argument that bindings are such an intimate aspect of the structure of expressions that they should be accounted for directly in the underlying programming language support for proof assistants and not via packages and libraries. We present an approach to designing programming languages and proof assistants that directly supports bindings in syntax. The roots of this approach can be found in the mobility of binders between term-level bindings, formula-level bindings (quantifiers), and proof-level bindings (eigenvariables). In particular, the combination of Church's approach to terms and formulas (found in his Simple Theory of Types) and Gentzen's approach to proofs (found in his sequent calculus) yields a framework for the interaction of bindings with a full range of logical connectives and quantifiers. We will also illustrate how that framework provides a direct and semantically clean treatment of computation and reasoning with syntax containing bindings. Some implemented systems, which support this intimate and built-in treatment of bindings, will be briefly described.
Complete list of metadata

Cited literature [171 references]  Display  Hide  Download
Contributor : Dale Miller Connect in order to contact the contributor
Submitted on : Sunday, September 30, 2018 - 10:07:36 AM
Last modification on : Tuesday, August 2, 2022 - 4:24:23 AM
Long-term archiving on: : Monday, December 31, 2018 - 12:40:50 PM


Files produced by the author(s)



Dale Miller. Mechanized metatheory revisited. Journal of Automated Reasoning, Springer Verlag, 2019, 63 (3), pp.625-665. ⟨10.1007/s10817-018-9483-3⟩. ⟨hal-01884210⟩



Record views


Files downloads