License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2022.11
URN: urn:nbn:de:0030-drops-184548
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18454/
Dubois, Catherine ;
Magaud, Nicolas ;
Giorgetti, Alain
Pragmatic Isomorphism Proofs Between Coq Representations: Application to Lambda-Term Families
Abstract
There are several ways to formally represent families of data, such as lambda terms, in a type theory such as the dependent type theory of Coq. Mathematical representations are very compact ones and usually rely on the use of dependent types, but they tend to be difficult to handle in practice. On the contrary, implementations based on a larger (and simpler) data structure combined with a restriction property are much easier to deal with.
In this work, we study several families related to lambda terms, among which Motzkin trees, seen as lambda term skeletons, closable Motzkin trees, corresponding to closed lambda terms, and a parameterized family of open lambda terms. For each of these families, we define two different representations, show that they are isomorphic and provide tools to switch from one representation to another. All these datatypes and their associated transformations are implemented in the Coq proof assistant. Furthermore we implement random generators for each representation, using the QuickChick plugin.
BibTeX - Entry
@InProceedings{dubois_et_al:LIPIcs.TYPES.2022.11,
author = {Dubois, Catherine and Magaud, Nicolas and Giorgetti, Alain},
title = {{Pragmatic Isomorphism Proofs Between Coq Representations: Application to Lambda-Term Families}},
booktitle = {28th International Conference on Types for Proofs and Programs (TYPES 2022)},
pages = {11:1--11:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-285-3},
ISSN = {1868-8969},
year = {2023},
volume = {269},
editor = {Kesner, Delia and P\'{e}drot, Pierre-Marie},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18454},
URN = {urn:nbn:de:0030-drops-184548},
doi = {10.4230/LIPIcs.TYPES.2022.11},
annote = {Keywords: Data Representations, Isomorphisms, dependent Types, formal Proofs, random Generation, lambda Terms, Coq}
}
