Sparkles

Appearance

Evolution of Algebraic Effect Systems ​

How the field moved from monads to modern handlers, and what changed by February 2026.

Timeline ​

PeriodMilestoneWhy It Matters
1991Moggi's monadic metalanguageUnified view of computational effects in typed lambda calculi
2001-2003Plotkin and Power's algebraic view of effectsConnected effect operations to algebraic theories and free models
2009Plotkin and Pretnar: handlers of algebraic effectsEstablished handlers as a general programming abstraction
2013-2017Effekt/Eff/Koka eraPractical effect languages and row-polymorphic typing became real
2014-2015Higher-order handlers and fusion (Wu, Schrijvers, Hinze)Scoped effects and performance techniques for handlers
2015Freer monads in HaskellExtensible effects with open unions and practical APIs
2020-2021Evidence-passing compilationO(1) operation dispatch and stronger implementation story
2021OCaml handlers in a mainstream runtimeIndustrial language runtime adopts native handlers
2022+GHC delimited continuation primops usable in releasesRuntime substrate for continuation-based effect libraries
2023Hefty AlgebrasModular and sound account of higher-order effect elaboration
2023WasmFX (typed continuations for WebAssembly)Cross-language low-level target for control effects
2024-2025Parallel/affine/temporal research waveFocus shifts to multicore, resource sensitivity, and richer semantics

Phase 1: Monadic Foundation (1991) ​

The modern story starts with monads: effects are represented by a type constructor T and sequencing laws. This gave a precise semantic framework but made effect composition difficult in practice.

Key result: monads made effects first-class in denotational semantics, but did not by themselves solve modular combination of independent effects.

Phase 2: Algebraic Characterization (2001-2003) ​

Plotkin and Power showed that many common effects can be described as algebraic operations with equations, and that free constructions provide canonical semantics.

Key result: this reframed effects from ad hoc monadic plumbing to a uniform algebraic theory, setting up handlers naturally.

Phase 3: Handlers as Programming Abstraction (2009) ​

Plotkin and Pretnar introduced handlers explicitly as interpreters for effect operations and resumptions. This became the conceptual core of almost all later handler systems.

Key result: programs can describe effects abstractly; handlers define concrete behavior locally.

Phase 4: Practical Languages and Libraries (2013-2017) ​

Two streams matured:

  1. Language designs (Eff, Koka, later Effekt/Frank) demonstrated usable effect syntax and typing.
  2. Library encodings (especially in Haskell) explored free/freer and higher-order effect encodings.

Row-polymorphic effect types and type-directed compilation were major breakthroughs in this period.

Phase 5: Performance and Compilation Discipline (2020-2021) ​

Evidence-passing semantics (ICFP 2020, 2021) gave a concrete answer to a long-standing concern: handlers can be compiled efficiently without abandoning type precision.

Key implementation lesson:

  • Keep effect dispatch as direct indexed lookup (evidence vectors/environments)
  • Capture continuations only when necessary
  • Treat tail-resumptive operations as a fast path

This strongly influenced practical systems and narrowed the performance gap with direct-style code.

Phase 6: Runtime Integration (2021-2025) ​

OCaml ​

  • PLDI 2021 formalized the retrofit strategy.
  • OCaml 5 delivered one-shot handlers in the runtime.
  • OCaml 5.3 (released January 8, 2025) added direct deep-handler syntax (match ... with effect ...).
  • OCaml 5.4 (released October 9, 2025) continues maturation of the runtime/tooling release train.
  • Eio provides effects-based direct-style I/O built on OCaml 5's runtime.

GHC ​

Delimited continuation primops from Proposal #313 became available in released toolchains (notably the 9.6 line), enabling library experimentation with runtime-backed control operations for libraries like eff and bluefin-algae.

WebAssembly ​

WasmFX (OOPSLA 2023) and the stack-switching proposal line position typed continuations/stack control as a cross-language compilation substrate.

Phase 7: Current Research Frontier (2023-2025) ​

Recent work shifts from "can handlers work?" to "which guarantees and performance envelopes can we prove?"

1. Sound higher-order effects ​

  • Hefty Algebras (POPL 2023) separates higher-order elaboration from first-order interpretation, implemented in the heftia library.
  • Theseus (2025) provides an alternative approach to sound higher-order effects using higher-order Freer monads.
  • Follow-up work studies abstractions over handler frameworks and modularity properties.

2. Parallelism and multicore semantics ​

  • Parallel Algebraic Effect Handlers (ICFP 2024) introduces lambda^p and a path to parallel handling.
  • Work on asymptotic speedups through handlers and multicore runtime models expands this direction.

3. Resource-sensitive effects ​

  • Affine/linear handling and temporal effects papers (2025) focus on stronger control over resource usage and ordering guarantees.

4. Better cross-framework understanding ​

  • New frameworks compare and abstract over effect systems rather than proposing isolated encodings.

Haskell-Specific Generational Evolution ​

The Haskell ecosystem provides the clearest case study of how effect encodings evolved in a single language, because each generation directly addressed limitations of its predecessor.

Generation 1: Monad Transformers (mtl, ~1995+) ​

Monad transformers compose effects by stacking transformer layers. The mtl library provides typeclasses (MonadState, MonadReader, MonadError) that abstract over the concrete stack.

Strengths: Well-understood; decades of use; good GHC optimization.

Limitations: O(n²) instances (every new transformer requires instances for every existing transformer); lifting overhead accumulates; stack ordering changes semantics.

Generation 2: Free and Freer Monads (~2008-2015) ​

Free monads represent effects as data, building a syntax tree interpreted by handlers. The freer monad (Kiselyov, Ishii 2015) removed the Functor constraint and introduced open unions for extensible effects, later popularized in libraries like freer-simple.

Strengths: Effects as inspectable data; clean syntax/semantics separation; no O(n²) instance problem.

Limitations: ~30x slower than mtl for short stacks in benchmarks; no support for higher-order effects (scoped operations).

Generation 3: Fused Effects and Higher-Order Effects (~2018-2019) ​

fused-effects encoded effects as higher-order functors and fused sequential handlers at compile time via typeclass instances. polysemy (2019) added higher-order effects via the Tactics API but prioritized ergonomics over performance.

Key data point: The GitHub Semantic team reported a 250x improvement switching from free monads to fused-effects. Sandy Maguire later documented polysemy's performance issues in "Polysemy: Mea Culpa."

Generation 4: ReaderT IO (~2020+) ​

effectful and cleff embraced IO as the base monad, building extensible environments on top with O(1) integer-indexed dispatch.

Key insight: Michael Snoyman's observation that most Haskell applications end up in IO anyway, so making the base monad concrete enables dramatic optimizations. effectful's static dispatch is on par with hand-written ST code. This generation essentially closed the performance gap.

Limitation: Cannot capture delimited continuations (no NonDet, Coroutine); cannot interpret effects purely.

Generation 5: Delimited Continuations and Sound HO Effects (~2022+) ​

Alexis King's GHC Proposal #313 added prompt# and control0# primops. The eff library demonstrated native continuation performance wins. heftia (2024) implemented hefty algebras for fully sound higher-order + algebraic effects. bluefin-algae uses the primops to add algebraic effects to Bluefin's value-level handles.

Current landscape (2026): The Haskell ecosystem now offers four distinct strategies:

  1. effectful/cleff: Maximum performance, pragmatic IO-based semantics, no algebraic effects
  2. heftia: Sound semantics, all features, prioritizes theoretical rigor
  3. bluefin + bluefin-algae: Simple mental model (handles), algebraic effects via primops
  4. eff: Demonstrates native continuation performance (development stalled, but primops continue to be used)

What Is "State of the Art" in 2026? ​

State of the art is now best understood as a combination of four properties:

  1. Semantic clarity: precise meaning of handlers/resumptions, especially with higher-order effects
  2. Compilation efficiency: evidence passing, selective continuation capture, and runtime support
  3. Concurrency story: structured concurrency plus emerging parallel-handler models
  4. Adoption path: workable ergonomics in production ecosystems

Different ecosystems currently optimize different subsets of these properties.

Open Problems ​

  1. Typed effects in mainstream runtimes: especially the OCaml path from untyped runtime handlers to typed surface systems.
  2. Stable, ergonomic higher-order abstractions: balancing formal guarantees with developer usability.
  3. Parallel handlers in production: moving from calculi/prototypes to robust multicore implementations.
  4. Interop and compilation targets: proving and engineering reliable lowering to common targets (native, JVM, Wasm).

Sources ​