General Automation in Coq through Modular Transformations

Valentin Blot
(LMF, Inria, Université Paris-Saclay)
Louise Dubois de Prisque
(LMF, Inria, Université Paris-Saclay)
Chantal Keller
(LMF, Université Paris-Saclay)
Pierre Vial
(LMF, Inria, Université Paris-Saclay)

Whereas proof assistants based on Higher-Order Logic benefit from external solvers' automation, those based on Type Theory resist automation and thus require more expertise. Indeed, the latter use a more expressive logic which is further away from first-order logic, the logic of most automatic theorem provers. In this article, we develop a methodology to transform a subset of Coq goals into first-order statements that can be automatically discharged by automatic provers. The general idea is to write modular, pairwise independent transformations and combine them. Each of these eliminates a specific aspect of Coq logic towards first-order logic. As a proof of concept, we apply this methodology to a set of simple but crucial transformations which extend the local context with proven first-order assertions that make Coq definitions and algebraic types explicit. They allow users of Coq to solve non-trivial goals automatically. This methodology paves the way towards the definition and combination of more complex transformations, making Coq more accessible.

In Chantal Keller and Mathias Fleury: Proceedings Seventh Workshop on Proof eXchange for Theorem Proving (PxTP 2021), Pittsburg, USA, 11th July 2021, Electronic Proceedings in Theoretical Computer Science 336, pp. 24–39.
Published: 7th July 2021.

ArXived at: http://dx.doi.org/10.4204/EPTCS.336.3 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org