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.

High-level signatures and initial semantics / Benedikt Ahrens, André Hirschowitz, Ambroise Lafont, Marco Maggesi. - STAMPA. - 119:(2018), pp. 1-22. (Intervento presentato al convegno ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC tenutosi a gbr nel 2018) [10.4230/LIPIcs.CSL.2018.4].

High-level signatures and initial semantics

AHRENS, BENEDIKT;Marco Maggesi
2018

Abstract

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.
2018
ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC
ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC
gbr
2018
Benedikt Ahrens, André Hirschowitz, Ambroise Lafont, Marco Maggesi
File in questo prodotto:
File Dimensione Formato  
LIPIcs-CSL-2018-4.pdf

accesso aperto

Tipologia: Pdf editoriale (Version of record)
Licenza: Creative commons
Dimensione 584.26 kB
Formato Adobe PDF
584.26 kB Adobe PDF
1805.03740.pdf

accesso aperto

Descrizione: Versione ArXiv 2020-03-26
Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Open Access
Dimensione 719.62 kB
Formato Adobe PDF
719.62 kB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1138278
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact