Co)algebraic Foundations for Effectful Recursive Definitions
Sergey Goncharov, Lutz Schröder, Christoph Rauch · arXiv (Cornell University) · 2014
A pervasive challenge in programming theory and practice are feature combinations. Here, we propose a semantic framework that combines monad-based computational effects (e.g. store, nondeterminism, random), underdefined or free operations (e.g. actions in process algebra and automata, exceptions), and recursive definitions (e.g. loops, systems of process equations). The joint treatment of these phenomena has previously led to models tending to one of two opposite extremes: extensional as, e.g., in domain theory, and intensional as in classical process algebra and more generally in universal coalgebra. Our metalanguage for effectful recursive definitions, designed in the spirit of Moggi's computational metalanguage, flexibly combines these intensional and extensional aspects of computations in a single framework. We base our development on a notion of complete Elgot monad, whose defining feature is a parametrized uniform iteration operator satisfying natural axioms in the style of Simpson and Plotkin. We provide a mechanism of adjoining free operations to such monads by means of cofree extensions, thus in particular allowing for a non-trivial semantics of non-terminating computations with free effects. Our main result states that the class of complete Elgot monads is closed under such cofree extensions, which thus serve as domains for effectful recursive definitions with free operations. Elgot monads do not require the iterated computation to be guarded, and hence iteration operators are not uniquely determined by just their defining fixpoint equation. Our results however imply that they are uniquely determined as extending the given iteration in the base effect and satisfying the axioms. We discuss a number of examples formalized in our metalanguage, including (co)recursive definitions of process-algebraic operations on side- effecting processes.