(Monadic) Reflections on Concurrency13 Jun 2017
We recently published a paper on concurrent system programming with effect handlers. In this paper, we show that with the help of effect handlers, we could express in direct-style, various interactions of a concurrent program with OS services that typically require callbacks. The question is what do we do about legacy code that uses monadic concurrency libraries such as Lwt and Async. Surely a wholesale rewrite of all Lwt and Async code is a no go. This post is an exploration of some ideas to make Lwt and Async compatible with direct-style code.
Andrzej Filinski introduced monadic reflection in his paper Representing Monads, characterizing the relationship between monadic style and continuation-passing style. Practically, in a language like multicore OCaml with native support for delimited continuations, any monadic style program can also be written in direct-style. Filinski introduces two operators to transform between the two styles:
reify transforms a direct-style computation to a monadic one and
goes the other way. In multicore OCaml, we can implement monadic reflection for
any monad as1:
We introduce an effect
E which is parameterized with the monadic computation.
When this effect is performed, it returns the result of performing this monadic
reify wraps the direct-style computation with an effect handler
E m and binds the monadic computation
m to the rest of the
reflect simply performs the given monadic
computation wrapped in
E. The idea here is that whenever the monad does
anything interesting, we perform the effect
E which delegates the handling of
interesting monadic behavior to the effect handler.
Monadic to Direct
We implement chameneos-redux benchmark
from the computer language benchmarks game in direct-style and using concurrency
monad. The benchmark is intended to evaluate the cost of context switching
between tasks. The source code is available
in a single-self contained file. We implement both versions as functors
ChameneosD (S : SchedD) (M : MVarD) and monadic-style is
ChameneosM (S : SchedM) (M : MVarM)) parameterized by a scheduler and an MVar
implementation. The signatures of direct and monadic style scheduler and MVars
Using monadic reflection on the monadic scheduler
SchedM and MVar
implementations, we can instantiate the direct-style functor
We can even instantiate the direct-style functor
ChameneosD with Lwt with no
Thus, monadic reflection lets you utilize Lwt and Async in direct-style.
Importantly, one gets back backtraces and the use of
for exception handling.
Direct to Monadic
Lwt and Async libraries provide strong guarantees on task interleavings. In particular, both libraries provide automatic mutual exclusion – context switches between tasks only occur at bind points. In other words, any non-monadic functions, such as calls to standard library functions, are guaranteed not to context switch. With effect handlers, this is no longer the case since effects are not tracked in the types in multicore OCaml.
We can recover the type level marker with a shallow embedding:
And we can go back to direct-style using monadic reflection:
We compared the performance of different configurations for running chameneos-redux for 1 million iterations:
The results show that monadic reflection has around 9% overhead on average over the baseline monadic implementations. This is a small price to pay for the advantage for programming in direct-style.
We have been prototyping a multicore-capable I/O library for OCaml called Aeio, with compatibility layer for Lwt and Async built on top of this library. Monadic reflection and other techniques can help resolve the schism between monadic libraries and direct-style code.