Title:
Modular specification of monads through higher-order presentations
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, and this 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 $\beta$- and $\eta$-equalities. Such a 2-signature is hence a pair (Σ,E) of a binding signature Σ and a family E of equations for Σ. This notion of 2-signature has been introduced earlier by Ahrens in a slightly different context.
We associate, to each 2-signature (Σ,E), a category of `models of (Σ,E); and we say that a 2-signature is `effective’ if the associated category of models 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.
Title: 
Beniamino Accattoli
Sarah Winkler
Amy Felty