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.CSL.2018.4
URN: urn:nbn:de:0030-drops-96713
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9671/
Go to the corresponding LIPIcs Volume Portal

Ahrens, Benedikt ; Hirschowitz, André ; Lafont, Ambroise ; Maggesi, Marco

High-Level Signatures and Initial Semantics

pdf-format:
LIPIcs-CSL-2018-4.pdf (0.6 MB)

Abstract

We present a device for specifying and reasoning about syntax for datatypes, programming languages, and logic calculi. More precisely, we consider a general notion of "signature" for specifying syntactic constructions. Our signatures subsume classical algebraic signatures (i.e., signatures for languages with variable binding, such as the pure lambda calculus) and extend to much more general examples.
In the spirit of Initial Semantics, we define the "syntax generated by a signature" to be the initial object - if it exists - in a suitable category of models. Our notions of signature and syntax are suited for compositionality and provide, beyond the desired algebra of terms, a well-behaved substitution and the associated inductive/recursive principles.
Our signatures are "general" in the sense that the existence of an associated syntax is not automatically guaranteed. In this work, we identify a large and simple class of signatures which do generate a syntax.
This paper builds upon ideas from a previous attempt by Hirschowitz-Maggesi, which, in turn, was directly inspired by some earlier work of Ghani-Uustalu-Hamana and Matthes-Uustalu.
The main results presented in the paper are computer-checked within the UniMath system.

BibTeX - Entry

@InProceedings{ahrens_et_al:LIPIcs:2018:9671,
  author =	{Benedikt Ahrens and Andr{\'e} Hirschowitz and Ambroise Lafont and Marco Maggesi},
  title =	{{High-Level Signatures and Initial Semantics}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9671},
  URN =		{urn:nbn:de:0030-drops-96713},
  doi =		{10.4230/LIPIcs.CSL.2018.4},
  annote =	{Keywords: initial semantics, signatures, syntax, monadic substitution, computer-checked proofs}
}

Keywords: initial semantics, signatures, syntax, monadic substitution, computer-checked proofs
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018
Supplementary Material: Computer-checked proofs with compilation instructions on https://github.com/amblafont/largecatmodules

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