The logic programming paradigm provides a flexible setting for representing, manipulating, checking, and elaborating proof structures. This is particularly true when the logic programming language allows for bindings in terms and proofs. In this paper, we make use of two recent innovations at the intersection of logic programming and proof checking. One of these is the foundational proof certificate (FPC) framework which provides a flexible means of defining the semantics of a range of proof structures for classical and intuitionistic logic. A second innovation is the recently released Coq-Elpi plugin for Coq in which the Elpi implementation of λProlog can send and retrieve information to and from the Coq kernel. We illustrate the use of both this Coq plugin and FPCs with two example applications. First, we implement an FPC-driven sequent calculus for a fragment of the Calculus of Inductive Constructions and we package it into a tactic to perform property-based testing of inductive types corresponding to Horn clauses. Second, we implement in Elpi a proof checker for first-order intuitionistic logic and demonstrate how proof certificates can be supplied by external (to Coq) provers and then elaborated into the fully detailed proof terms that can be checked by the Coq kernel.
Two Applications of Logic Programming to Coq / M. Manighetti, D. Miller, A. Momigliano - In: 26th International Conference on Types for Proofs and Programs (TYPES 2020) / [a cura di] U. de’Liguoro, S. Berardi, T. Altenkirch. - [s.l] : LIPICS, 2021. - pp. 10:1-10:19 (( Intervento presentato al 26. convegno TYPES tenutosi a Torino nel 2020.
|Titolo:||Two Applications of Logic Programming to Coq|
MOMIGLIANO, ALBERTO (Corresponding)
|Parole Chiave:||Proof assistants; logic programming; Coq; λProlog; property-based testing|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
Settore MAT/01 - Logica Matematica
|Data di pubblicazione:||2021|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.4230/lipics.types.2020.10|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|