A Relational Theory of Monadic Rewriting Systems, Part I

Motivated by the study of effectful programming languages and computations, we introduce a relational theory of monadic rewriting systems. The latter are rewriting systems whose notion of reduction is effectful, where effects are modelled as monads. Contrary to what happens in the ordinary operational semantics of monadic programming languages, defining meaningful notions of monadic rewriting turns out to problematic for several monads, including the distribution, powerset, reader, and global state monad. This raises the question of when monadic rewriting is possible. We answer that question by identifying a class of monads, known as weakly cartesian monads, that guarantee monadic rewriting to be well-behaved. In case monads are given as equational theories, as it is the case for algebraic effects, we also show that a sufficient condition to have a well-behaved notion of monadic rewriting is that all equations in the theory are linear. Finally, we apply the abstract theory of monadic rewriting systems to the call-by-value λ-calculus with algebraic effects, this way obtaining effectful (surface) standardisation and confluence theorems.