Zero-cost Effect Handlers by Staging (Technical Report)
by Philipp Schuster, Jonathan Immanuel Brachthäuser, and Klaus Ostermann
In Under consideration for publication in Proc. Conf. Programming Language Design and Implementation (PLDI). ACM Press, 2019.
This publication is related to the Effekt: Algebraic Effect Handlers research project.
Effect handlers offer ways to structure programs with complex control-flow patterns. Yet, current implementations of effect handlers incur a significant price in performance for doing so. We present a language that makes it possible to eliminate the overhead introduced by using effect handlers to abstract over effect operations. We present a translation of this language to simply typed lambda calculus in continuation passing style that preserves the well-typedness of terms. We present a second translation that, guided by automatically inserted staging annotations, guarantees to eliminate abstractions and applications related to effect handlers. We implement the translations and generate code in multiple languages. We validate the efficiency of the generated code theoretically, by proving that the use of certain language constructs never leads to run-time reductions, and practically, with a suite of benchmarks comparing with existing implementations of effect handlers and control operators.