On the Compositionality of Monads via Weak Distributive Laws

Abstract

Monads are widely used in computer science to model computational effects. To represent complex systems, compositionality of monads is therefore crucial. One can usually compose two monads using distributive laws. When no distributive law exists, it is sometimes still possible to recover what looks like a composite effect by using a weak distributive law. The phenomenon occurs when combining probabilistic choice with non-deterministic choice, or when combining non-deterministic choice with itself. This thesis leverages and enhances the framework of weak distributive laws towards applications in computer science. Firstly, we focus on the two most-known examples where distributive laws fail in the category of sets. The origin of scattered results of the literature is explained through the lens of weak distributive laws. This includes composition of equational theories for non-determinism and probability as well as coalgebraic constructions for probabilistic automata and alternating automata. Secondly, aiming at applications in the semantics of programming languages, we study how to obtain laws in other categories. Notably, we generalise weak self-distribution of non-deterministic choice to arbitrary toposes and compact Hausdorff spaces.

Alexandre Goy

Postdoc

I am interested in theoretical computer science, especially logic, category theory, coalgebra, and probabilistic aspects of these topics.