Initial Semantics for higher-order typed syntax in Coq

Authors

  • Benedikt Ahrens
  • Julianna Zsido Universite' Montpellier II, France

DOI:

https://doi.org/10.6092/issn.1972-5787/2066

Abstract

Initial Semantics aims at characterizing the syntax associated to a signature as the initial object of some category. We present an initial semantics result for typed higher-order syntax together with its formalization in the Coq proof assistant. The main theorem was first proved on paper in the second author’s PhD thesis in 2010, and verified formally shortly afterwards. To a simply–typed binding signature S over a fixed set T of object types we associate a category called the category of representations of S. We show that this category has an initial object Sigma(S), i.e. an object Sigma(S) from which there is precisely one morphism i_R : Sigma(S) -> R to any object R of this category. From its construction it will be clear that the object Sigma(S) merits the name abstract syntax associated to S: it is given by an inductive set – parametrized by a set of free variables and dependent on object types – the type of whose constructors are each given by the arities of the signature S. Our theorem is implemented and proved correct in the proof assistant Coq through heavy use of dependent types. The approach through monads gives rise to an implementation of syntax where both terms and variables are intrinsically typed, i.e. where the object types are rejected in the meta–level types. Terms are implemented as a Coq data type – which play the role of sets – dependent on an object type as well as on a type family of free variables. This article is to be seen as a research article rather than about the formalization of a classical mathematical result. The nature of our theorem – involving lengthy, technical proofs and complicated algebraic structures – makes it particularly interesting for formal verification. Our goal is to promote the use of computer theorem provers as research tools, and, accordingly, a new way of publishing mathematical results: a parallel description of a theorem and its formalization should allow the verification of correct transcription of definitions and statements into the proof assistant, and straightforward but technical proofs should be well–hidden in a digital library. We argue that Coq’s rich type theory, combined with its various features such as implicit arguments, allows a particularly readable formalization and is hence well–suited for communicating mathematics.

Downloads

Published

2011-09-08

How to Cite

Ahrens, B., & Zsido, J. (2011). Initial Semantics for higher-order typed syntax in Coq. Journal of Formalized Reasoning, 4(1), 25–69. https://doi.org/10.6092/issn.1972-5787/2066

Issue

Section

Articles
{"cc_re__cc_re__cc_by_3_0": ["section class=\"sub_item\">\n\t\t\t\t\t\t\t<h2 class=\"label\">\n\t\t\t\t\t\t\t\tSection\n\t\t\t\t\t\t\t</h2>\n\t\t\t\t\t\t\t<div class=\"value\">\n\t\t\t\t\t\t\t\tArticles\n\t\t\t\t\t\t\t</div>\n\t\t\t\t\t\t</section>\n\t\t\t\t\t\t\t\t\t</div>\n\t\t\t\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t<div class=\"item copyright\">\n\t\t\t\t\t<h2 class=\"label\">\n\t\t\t\t\t\tLicense\n\t\t\t\t\t</h2>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<p>Copyright (c) 2011 Benedikt Ahrens, Julianna Zsido</p>\n\t\t\t\t\t\t\t\t\t\t\t\t<p>Copyrights and publishing rights of all the texts on this journal belong to the respective authors without restrictions.</p><div><a href=\"http://creativecommons.org/licenses/by/3.0/\" rel=\"license\"><img src=\"https://i.creativecommons.org/l/by/3.0/88x31.png\" alt=\"Creative Commons License\" /></a></div><p>This journal is licensed under a <a href=\"http://creativecommons.org/licenses/by/3.0/\" rel=\"license\">Creative Commons Attribution 3.0 Unported License</a> (<a href=\"http://creativecommons.org/licenses/by/3.0/legalcode\">full legal code</a>). <br />See also our <a href=\"/about/editorialPolicies#openAccessPolicy\">Open Access policy</a></p>\n\t\t\t\t\t\t\t\t\t</div>\n\t\t\t\n\t\t\t\n\n\t\t</div><!-- .entry_details --", "class=\"item copyright\">\n\t\t\t\t\t<h2 class=\"label\">\n\t\t\t\t\t\tLicense\n\t\t\t\t\t</h2>\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<p>Copyright (c) 2011 Benedikt Ahrens, Julianna Zsido</p>\n\t\t\t\t\t\t\t\t\t\t\t\t<p>Copyrights and publishing rights of all the texts on this journal belong to the respective authors without restrictions.</p><div><a href=\"http://creativecommons.org/licenses/by/3.0/\" rel=\"license\"><img src=\"https://i.creativecommons.org/l/by/3.0/88x31.png\" alt=\"Creative Commons License\" /></a></div><p>This journal is licensed under a <a href=\"http://creativecommons.org/licenses/by/3.0/\" rel=\"license\">Creative Commons Attribution 3.0 Unported License</a> (<a href=\"http://creativecommons.org/licenses/by/3.0/legalcode\">full legal code</a>). <br />See also our <a href=\"/about/editorialPolicies#openAccessPolicy\">Open Access policy</a></p>\n\t\t\t\t\t\t\t\t\t</div>\n\t\t\t\n\t\t\t\n\n\t\t</div><!-- .entry_details -->\n\t</div><!-- .row -->\n\n</article>\n\n\t\n\n</div><!-- .page -->\n\n\t</div><!-- pkp_structure_main -->\n\n\t\t\t\t\t\t\t\t\t<div class=\"pkp_structure_sidebar left\" role=\"complementary\" aria-label=\"Sidebar\">\n\t\t\t\t<div class=\"pk"], "cc_re__cc_re__cc_by_3_0_le": ["hrens, Julianna Zsido</p>\n\t\t\t\t\t\t\t\t\t\t\t\t<p>Copyrights and publishing rights of all the texts on this journal belong to the respective authors without restrictions.</p><div><a href=\"http://creativecommons.org/licenses/by/3.0/\" rel=\"license\"><img src=\"https://i.creativecommons.org/l/by/3.0/88x31.png\" alt=\"Creative Commons License\" /></a></div><p>This journal is licensed under a <a href=\"http://creativecommons.org/licenses/by/3.0/\" rel=\"license\">Creative Commons Attribution 3.0 Unported License</a> (<a href=\"http://creativecommons.org/licenses/by/3.0/legalcode\">full legal code</a>). <br />See also our <a href=\"/about/editorialPolicies#openAccessPolicy\">Open Access policy</a></p>\n\t\t\t\t\t\t\t\t\t</div>\n\t\t\t\n\t\t\t\n\n\t\t</div><!-- .entry_details -->\n\t</div><!-- .row -->\n\n</article>\n\n\t\n\n</div><!-- .page -->\n\n\t</div><!-- pkp_structure_main -->\n\n\t\t\t\t\t\t\t\t\t<div class=\"pkp_structure_sidebar left\" role=\"complementary\" aria-label=\"Sidebar\">\n\t\t\t\t<div class=\"pkp_block block_information\">\n\t<h2 class=\"title\">Information</h2>\n\t<div class=\"content\">\n\t\t<ul>\n\t\t\t\t\t\t\t<li>\n\t\t\t\t\t<a href"], "copyright__copyright__copyright": ["fs should be well\u2013hidden in a digital library. We argue that Coq\u2019s rich type theory, combined with its various features such as implicit arguments, allows a particularly readable formalization and is hence well\u2013suited for communicating mathematics.\n\nDownloads\n\nPublished\n\n2011-09-08\n\nHow to Cite\n\nAhrens, B., & Zsido, J. (2011). Initial Semantics for higher-order typed syntax in Coq. Journal of Formalized Reasoning, 4(1), 25\u201369. https://doi.org/10.6092/issn.1972-5787/2066\n\nIssue\n\nSection\n\nArticles", "fs should be well\u2013hidden in a digital library. We argue that Coq\u2019s rich type theory, combined with its various features such as implicit arguments, allows a particularly readable formalization and is hence well\u2013suited for communicating mathematics.\n\nDownloads\n\nPublished\n\n2011-09-08\n\nHow to Cite\n\nAhrens, B., & Zsido, J. (2011). Initial Semantics for higher-order typed syntax in Coq. Journal of Formalized Reasoning, 4(1), 25\u201369. https://doi.org/10.6092/issn.1972-5787/2066\n\nIssue\n\nSection\n\nArticles", "fs should be well\u2013hidden in a digital library. We argue that Coq\u2019s rich type theory, combined with its various features such as implicit arguments, allows a particularly readable formalization and is hence well\u2013suited for communicating mathematics.\n\nDownloads\n\nPublished\n\n2011-09-08\n\nHow to Cite\n\nAhrens, B., & Zsido, J. (2011). Initial Semantics for higher-order typed syntax in Coq. Journal of Formalized Reasoning, 4(1), 25\u201369. https://doi.org/10.6092/issn.1972-5787/2066\n\nIssue\n\nSection\n\nArticles", "fs should be well\u2013hidden in a digital library. We argue that Coq\u2019s rich type theory, combined with its various features such as implicit arguments, allows a particularly readable formalization and is hence well\u2013suited for communicating mathematics.\n\nDownloads\n\nPublished\n\n2011-09-08\n\nHow to Cite\n\nAhrens, B., & Zsido, J. (2011). Initial Semantics for higher-order typed syntax in Coq. Journal of Formalized Reasoning, 4(1), 25\u201369. https://doi.org/10.6092/issn.1972-5787/2066\n\nIssue\n\nSection\n\nArticles"]}