License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2020.34
URN: urn:nbn:de:0030-drops-123562
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12356/
Go to the corresponding LIPIcs Volume Portal

Cohen, Cyril ; Sakaguchi, Kazuhiko ; Tassi, Enrico

Hierarchy Builder: Algebraic hierarchies Made Easy in Coq with Elpi (System Description)

pdf-format:
LIPIcs-FSCD-2020-34.pdf (0.6 MB)

Abstract

It is nowadays customary to organize libraries of machine checked proofs around hierarchies of algebraic structures. One influential example is the Mathematical Components library on top of which the long and intricate proof of the Odd Order Theorem could be fully formalized.
Still, building algebraic hierarchies in a proof assistant such as Coq requires a lot of manual labor and often a deep expertise in the internals of the prover. Moreover, according to our experience, making a hierarchy evolve without causing breakage in client code is equally tricky: even a simple refactoring such as splitting a structure into two simpler ones is hard to get right.
In this paper we describe HB, a high level language to build hierarchies of algebraic structures and to make these hierarchies evolve without breaking user code. The key concepts are the ones of factory, builder and abbreviation that let the hierarchy developer describe an actual interface for their library. Behind that interface the developer can provide appropriate code to ensure backward compatibility. We implement the HB language in the hierarchy-builder addon for the Coq system using the Elpi extension language.

BibTeX - Entry

@InProceedings{cohen_et_al:LIPIcs:2020:12356,
  author =	{Cyril Cohen and Kazuhiko Sakaguchi and Enrico Tassi},
  title =	{{Hierarchy Builder: Algebraic hierarchies Made Easy in Coq with Elpi (System Description)}},
  booktitle =	{5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-155-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{167},
  editor =	{Zena M. Ariola},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12356},
  URN =		{urn:nbn:de:0030-drops-123562},
  doi =		{10.4230/LIPIcs.FSCD.2020.34},
  annote =	{Keywords: Algebraic Hierarchy, Packed Classes, Coq, Elpi, Metaprogramming, λProlog}
}

Keywords: Algebraic Hierarchy, Packed Classes, Coq, Elpi, Metaprogramming, λProlog
Collection: 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)
Issue Date: 2020
Date of publication: 28.06.2020
Supplementary Material: Coq package source: https://github.com/math-comp/hierarchy-builder

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI