Deriving proved equality tests in Coq-elpi (Stronger induction principles for containers in Coq) - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

Deriving proved equality tests in Coq-elpi (Stronger induction principles for containers in Coq)

Enrico Tassi

Résumé

We describe a procedure to derive equality tests and their correctness proofs from inductive type declarations. Programs and proofs are derived compositionally, reusing code and proofs derived previously. The key steps are two. First, we design appropriate induction principles for data types defined using parametric containers. Second, we develop a technique to work around the modularity limitations imposed by the purely syntactic termination check Coq performs on recursive proofs. The unary parametricity translation of inductive data types turns out to be the key to both steps. Last but not least, we provide an implementation of the procedure for the Coq proof assistant based on the Elpi [3] extension language.
Fichier principal
Vignette du fichier
induction.pdf (167.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01897468 , version 1 (17-10-2018)
hal-01897468 , version 2 (08-04-2019)

Identifiants

  • HAL Id : hal-01897468 , version 1

Citer

Enrico Tassi. Deriving proved equality tests in Coq-elpi (Stronger induction principles for containers in Coq). 2018. ⟨hal-01897468v1⟩
692 Consultations
914 Téléchargements

Partager

Gmail Facebook X LinkedIn More