Effect handler

also: effect handlers, algebraic effects, effects, one-shot continuation

A construct that runs code which may perform an effect, and handles each effect by receiving it together with the continuation from the point where it was performed. OCaml 5 has them, with one-shot continuations: each can be resumed at most once.

Performing an effect is like raising an exception that carries a way back. The nearest enclosing handler for that effect gets the effect's value and a continuation, the rest of the computation up to the handler, and decides whether and how to resume it.

open Effect
open Effect.Deep
 
type _ Effect.t += Ask : int Effect.t
 
let run f =
  match_with f ()
    { retc = (fun x -> x);
      exnc = raise;
      effc = fun (type a) (eff : a Effect.t) ->
        match eff with
        | Ask -> Some (fun (k : (a, _) continuation) -> continue k 42)
        | _ -> None }
 
let n = run (fun () -> perform Ask + 1)   (* 43 *)

Generators, async I/O and schedulers are all handlers: the code that performs Yield or Read does not know which of them it is running under. Continuations are one-shot, so resuming the same one twice raises Effect.Continuation_already_resumed; that keeps them cheap, since a continuation is the suspended stack itself rather than a copy of it.

A handler is a delimited form of CPS: the continuation it receives is exactly what a CPS transform would have passed explicitly, except that the code performing the effect is written in direct style.

• CPSContinuation-passing style: instead of returning, a function takes an extra continuation argument and calls it with the result. Every call becomes a tail call, which is what lets a CPS-transformed program run in constant stack space wherever tail calls are eliminated, and it makes control flow a value that can be stored and resumed.
• Tail callA call whose result is returned directly, with nothing left for the caller to do. The caller's frame can be reused for it, so a loop written as tail recursion runs in constant stack space. OCaml guarantees this, and the [@tailcall] attribute makes the compiler warn when a call marked with it is not one.
• Chase-Lev dequeThe lock-free double-ended queue that work stealing is normally built on. The owner pushes and pops at the bottom with no atomic operation at all in the common case; thieves take from the top with a compare-and-swap; the two only contend when the deque is nearly empty, which is exactly the case the algorithm handles carefully.

• Effect Handlers in OCamlA command-first tour of OCaml 5 effects: perform, handlers, generators, and where domains and eio fit in.

• G. Plotkin, M. Pretnar, “Handlers of algebraic effects”, ESOP (2009).
• K. C. Sivaramakrishnan, S. Dolan, L. White, T. Kelly, S. Jaffer, A. Madhavapeddy, “Retrofitting effect handlers onto OCaml”, PLDI (2021).