Implementing and reasoning about hash-consed data structures in Coq

Abstract : We report on four different approaches to implementing hash-consing in Coq programs. The use cases include execution inside Coq, or execution of the extracted OCaml code. We explore the different trade-offs between faithful use of pristine extracted code, and code that is fine-tuned to make use of OCaml programming constructs not available in Coq. We discuss the possible consequences in terms of performances and guarantees. We use the running example of binary decision diagrams and then demonstrate the generality of our solutions by applying them to other examples of hash-consed data structures.
Keywords : Hash-consing Coq BDD
Liste complète des métadonnées


https://hal.inria.fr/hal-00881085
Contributeur : David Monniaux <>
Soumis le : vendredi 25 septembre 2015 - 11:50:42
Dernière modification le : dimanche 27 septembre 2015 - 01:01:41
Document(s) archivé(s) le : mardi 29 décembre 2015 - 10:01:03

Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Thomas Braibant, Jacques-Henri Jourdan, David Monniaux. Implementing and reasoning about hash-consed data structures in Coq. Journal of Automated Reasoning, Springer Verlag, 2014, 53 (3), pp.271-304. <10.1007/s10817-014-9306-0>. <hal-00881085v4>

Partager

Métriques

Consultations de
la notice

422

Téléchargements du document

76