Filip Koprivec: Efficient Compilation of Algebraic Effect Handlers

Datum objave: 22. 6. 2022
Seminar za temelje matematike in teoretično računalništvo
10.00 - 12.00

Algebraic effects and handlers are becoming more and more popular in both theoretical and practical circles. Great expressive power currently comes with performance implications, as programs with handlers are still much slower than hand written code without effect handlers. In this talk I will present ongoing work on efficient compilation from Eff language to OCaml (without native support for effect handlers).

Eff can be embedded in a free monad and compiled directly to OCaml, but this produces slow code with lot of unnecessary checking and binds. Performance can be drasticaly improved by type-and-effect directed optimization during the compilation. Our optimizing compiler uses multistage compilation process with explicitly typed intermediate language ExEff, optimizer that inlines and specializes handler function pairs and NoEff, a simple monadic calculus for final optimizations. The resulting OCaml can be as efficient as hand-written pure OCaml code where effecs are fully inlined, and is otherwise competitive in performance with MulticoreOcaml in both single and multi-shot scenarios.

Joint work with Matija Pretnar, Georgioe Karachaliars, Tom Schrijvers.