A Relational Theory of Monadic Rewriting Systems, Part I

Claudia Faggian (1) , Francesco Gavazzo (2, 3)

1 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
2 UNIBO - Alma Mater Studiorum Università di Bologna = University of Bologna
3 FOCUS - Foundations of Component-based Ubiquitous Systems

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.

Mots clés: Computer science; Sufficient conditions; Computer languages; Algebra; Computational modeling; Semantics; Focusing

Domaines: Informatique [cs]

Claudia Faggian, Francesco Gavazzo. A Relational Theory of Monadic Rewriting Systems, Part I. LICS 2021 - 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Jun 2021, Rome, France. pp.1-14, ⟨10.1109/LICS52264.2021.9470633⟩. ⟨hal-03455778⟩