Fusion for Free Efficient Algebraic Effect Handlers
📜 Abstract
Algebraic effect handlers are a recently popular approach for modelling side-effects that separates the syntax and semantics of effectful operations. The shape of syntax is captured by functors, and free monads over these functors denote syntax trees. The semantics is captured by algebras, and effect handlers pass these over the syntax trees to interpret them into a semantic domain. This approach is inherently modular: different functors can be composed to make trees with richer structure. Such trees are interpreted by applying several handlers in sequence, each removing the syntactic constructs it recognizes. Unfortunately, the construction and traversal of intermediate trees is painfully inefficient and has hindered the adoption of the handler approach. This paper explains how a sequence of handlers can be fused into one, so that multiple tree traversals can be reduced to a single one and no intermediate trees need to be allocated. At the heart of this optimization is keeping the notion of a free monad abstract, thus enabling a change of representation that opens up the possibility of fusion. We demonstrate how the ensuing code can be inlined at compile time to produce efficient handlers.
✨ Summary
Summary
The paper develops a fusion technique for algebraic effect handlers implemented with free monads. Its central observation is that a handler that constructs an intermediate syntax tree can be treated as a polymorphic builder rather than as a function tied to the concrete inductive representation of Free. The authors introduce term algebras and term monads to express this abstraction and use parametricity to derive a fold/build-style fusion law.
Because the result of a handler is not necessarily itself a monad, the paper uses the codensity monad to turn an arbitrary term algebra into a term monad. This makes the second handler a term-monad morphism, allowing the composition of handlers to be transformed into one traversal. The resulting implementation performs a single fold and avoids allocating intermediate abstract syntax trees. The approach also generalizes to pipelines of multiple handlers and can fuse through the construction of the initial computation.
The practical Haskell implementation relies on typeclass specialization and inlining in GHC. The evaluation reports that fused implementations substantially reduce the cost of effect handling: in the presented benchmarks, they are approximately 300 times faster than straightforward inductive or Church-encoded free-monad implementations for a state-counting workload, while matching or sometimes outperforming monad-transformer implementations. The paper notes that the technique is particularly suited to lazy languages such as Haskell; efficient application to strict languages remains unresolved.
Subsequent influence
A concrete later use is the Haskell fused-effects library, which explicitly identifies this paper as one of the works underlying its design. The library applies fusion laws to avoid intermediate representations between handlers and reports performance approximately on par with mtl; it is presented as suitable for research and industrial contexts and lists projects using it. (github.com)
The technique also continued to be cited in subsequent research on practical and compiled effect handlers, including work on capability-passing implementations. (link.springer.com)