(Monadic) Reflections on Concurrency

13 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.

Monadic Reflection

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 reflect goes the other way. In multicore OCaml, we can implement monadic reflection for any monad as¹:

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 computation. reify wraps the direct-style computation with an effect handler that handles E m and binds the monadic computation m to the rest of the direct-style computation. 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 here in a single-self contained file. We implement both versions as functors (direct-style is 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 are:

Using monadic reflection on the monadic scheduler SchedM and MVar MVarM implementations, we can instantiate the direct-style functor ChameneosD:

We can even instantiate the direct-style functor ChameneosD with Lwt with no extra effort:

Thus, monadic reflection lets you utilize Lwt and Async in direct-style. Importantly, one gets back backtraces and the use of raise and try...with 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:

Performance

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.

Conclusion

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.

Footnotes