Generalized Evidence Passing for Effect Handlers (or, Efficient Compilation of Effect Handlers to C)

See the ICFP’21 presentation.

Extended version available as a technical report.

This paper studies compilation techniques for algebraic effect handlers. In particular, we present a sequence of refinements of algebraic effects, going via multi-prompt delimited control, generalized evidence passing, yield bubbling, and finally a monadic translation into plain lambda calculus which can be compiled efficiently to many target platforms. Along the way we explore various interesting points in the design space. We provide two implementations of our techniques, one as a library in Haskell (called Mp.Eff), and one as a C backend for the Koka programming language. We show that our techniques are effective, by comparing against three other best-in-class implementations of effect handlers: multi-core OCaml, the Ev.Eff Haskell library, and the libhandler C library. We hope this work can serve as a basis for future designs and implementations of algebraic effects.