Modular specification of monads through higher-order presentations

DOI10.4230/LIPICS.FSCD.2019.6arXiv1903.00922MaRDI QIDQ6314958FDOQ6314958

Authors: Benedikt Ahrens, André Hirschowitz, Ambroise Lafont, Marco Maggesi 

Publication date: 3 March 2019

Abstract: In their work on second-order equational logic, Fiore and Hur have studied presentations of simply typed languages by generating binding constructions and equations among them. To each pair consisting of a binding signature and a set of equations, they associate a category of `models', and they give a monadicity result which implies that this category has an initial object, which is the language presented by the pair. In the present work, we propose, for the untyped setting, a variant of their approach where monads and modules over them are the central notions. More precisely, we study, for monads over sets, presentations by generating (`higher-order') operations and equations among them. We consider a notion of 2-signature which allows to specify a monad with a family of binding operations subject to a family of equations, as is the case for the paradigmatic example of the lambda calculus, specified by its two standard constructions (application and abstraction) subject to $$- and $eta$-equalities. Such a 2-signature is hence a pair $(Sigma,E)$ of a binding signature $Sigma$ and a family $E$ of equations for $Sigma$. This notion of 2-signature has been introduced earlier by Ahrens in a slightly different context. We associate, to each 2-signature $(Sigma,E)$, a category of `models of $(Sigma,E)$; and we say that a 2-signature is `effective' if this category has an initial object; the monad underlying this (essentially unique) object is the `monad specified by the 2-signature'. Not every 2-signature is effective; we identify a class of 2-signatures, which we call `algebraic', that are effective. Importantly, our 2-signatures together with their models enjoy `modularity': when we glue (algebraic) 2-signatures together, their initial models are glued accordingly. We provide a computer formalization for our main results.

Mathematics Subject Classification ID

Monads (= standard construction, triple or triad), algebras for monads, homology and derived functors for monads (18C15) Computer science (68-XX)

This page was built for publication: Modular specification of monads through higher-order presentations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6314958)