LNgen: Tool Support for Locally Nameless Representations

Stephanie Weirich and Brian Aydemir

Abstract: Given the complexity of the metatheoretic reasoning involved with current programming languages and their type systems, techniques for mechanical formalization and checking of the metatheory have received much recent attention. In previous work [1], we advocated a combination of locally nameless representation and cofinite quantification as a lightweight style for carrying out such formalizations in the Coq proof assistant. As part of the presentation of that methodology, we described a number of operations associated with variable binding and listed a number of properties, called ``infrastructure lemmas,'' about those operations that needed to be shown. The proofs of these infrastructure lemmas are generally straightforward, given a specification of the binding structure of the language.

In this work, we present LNgen [2], a prototype tool for automatically generating these definitions, lemmas, and proofs from Ott-like language specifications [3]. Furthermore, the tool also generates a recursion scheme for defining functions over syntax, which was not available in our previous work. We also show the soundness and completeness of our tool's output. For untyped lambda terms, we prove the adequacy of our representation with respect to a fully concrete representation, and we argue that the representation is complete--- that we generate the right set of lemmas---with respect to Gordon and Melham's ``Five Axioms of Alpha-Conversion.'' Finally, we claim that our recursion scheme is simpler to work with than either Gordon and Melham's recursion scheme or the recursion scheme of Nominal Logic.

[1] Engineering Formal Metatheory, POPL '08. With Arthur Charguéraud, Benjamin C. Pierce, Randy Pollack, and Stephanie Weirich.
[2] http://www.cis.upenn.edu/~baydemir/papers/lngen/
[3] http://www.cl.cam.ac.uk/~pes20/ott/