Algebraic Effects

Origin. Plotkin and Power introduced algebraic effects (2001-2003). Pretnar developed handlers (2010). Effects as operations with equations. Handlers as interpreters for effects. Foundation for effect systems in programming languages.

Models. Computational effects algebraically. Monad: encapsulate effects (IO, state, exceptions). Algebraic effects: effects as operations, handlers as interpretations. More modular than monads. Separate effect signatures from implementations.

Formalism.

Effect signature: Σ = {opᵢ: Aᵢ → Bᵢ} Operations with parameter and return types.

Example operations:

get: 1 → S (state)
put: S → 1 (state)
raise: E → 0 (exceptions)
choice: 1 → Bool (nondeterminism)

Free monad: Free(Σ, A): computations using ops from Σ returning A. Tree of operations with A at leaves.

Handlers: handler H { return x → e_ret; op(x, k) → e_op }

H interprets operations:

return: what to do with final value
op: how to handle operation (k is continuation)

Effect types: A ! {op₁, ..., opₙ} Computation returning A, may use ops.

Example (state handler): handler { return x → λs. (x, s); get((), k) → λs. k(s)(s); put(s', k) → λs. k(())(s') }

Equations: get; put(s); m = m (put after get irrelevant if not using value) Operations may satisfy algebraic equations.

Symbols.

Symbol	Unicode	Name	Meaning
op	—	Operation	Effect operation
!	—	Effect annotation	May perform
k	—	Continuation	Rest of computation
handler	—	Handler	Interpreter
return	—	Return	Pure value case
Free	—	Free monad	Uninterpreted effects

Metatheory. Algebraic effects = free monads for signature. Handlers = algebras for free monad. Effect polymorphism: abstract over effects. Row types for effect tracking. Denotational semantics well-understood.

Applies to. Programming language design (Eff, Koka, OCaml 5). Effect systems. Exception handling. Async/await. Generators. Delimited continuations. Modular interpreters.

Limitations. Control flow can be complex. Performance overhead (naively). Effect inference tricky. Multiple handler interaction. Learning curve from monads. Ecosystem still developing.