Programming Language Theory
Algebraic Effects
async/await is an algebraic effect. Exceptions are an algebraic effect. State is an algebraic effect. Algebraic effects are a single mechanism that unifies what used to require different language features.
- **OCaml 5.0**: algebraic effects power the new domain-based parallelism. Jane Street (a trading firm) uses OCaml in production. This is not academic
- **async/await in Kotlin**: coroutines are implemented via CPS transformation, which is the Async algebraic effect at the compiler level
- **WebAssembly Effect Handlers**: the WasmGC + effect handlers proposal brings algebraic effects to a future Wasm for managing GC and concurrency
Effect Handlers
Algebraic effects are a mechanism in which code declares effects (operations) and a handler higher in the stack defines their semantics. The separation: the code describes what to do (perform Effect), the handler decides how (with handle). More elegant than monads for many problems.
Algebraic effects = extensible effects. Monads for State, Maybe, IO require monad transformers to compose. Effects compose for free: you just add the effect you need to the function's signature.
What is the fundamental difference between algebraic effects and monads?
Resumable Computations
The key feature of algebraic effects: a computation can be suspended at an effect operation and the handler can resume it (`resume`) with a result. These are first-class continuations with a limited scope: delimited continuations.
How do algebraic effects let the same code run synchronously and asynchronously?
Koka
Koka is a language from Microsoft Research where algebraic effects are first-class in the type system. A function's type includes its effects: `fun f() : <State<Int>, Async> String`. The compiler checks that every effect is handled.
What does the type `fun f() : <State<Int>, Async, Raise> String` mean in Koka?
Unison
Unison is a language built around algebraic effects as the basis of its concurrency model. Abilities (Unison's term for effects) plus a fiber-based runtime. Key idea: code is identified by its hash (content-addressed), not by a filename.
OCaml 5 (2022) added algebraic effects as a first-class feature to implement a concurrent runtime. Effect handlers are the foundation of the new eio (effect-based IO) framework for OCaml.
Algebraic effects are an academic concept with no practical use
OCaml 5 (a production language at Jane Street), Koka (Microsoft Research), and Unison already use algebraic effects. async/await in JS is a special case
async/await is the Async algebraic effect without an explicit effect-type system. Effect handlers generalize this and let async, exceptions, state, and non-determinism be expressed uniformly
How do algebraic effects simplify testing compared with monads?
Takeaways
- **Algebraic effects**: code performs an operation, a handler higher in the stack defines its semantics. Separation of what from how
- **Resumable**: the handler can resume the computation via resume(value). First-class delimited continuations
- **Koka**: effects in the type system. The function type lists every effect. Compile-time verification
- **Unison/OCaml 5**: production languages with algebraic effects. async/await = an algebraic effect without an explicit effect system
Related Topics
Algebraic effects generalize many mechanisms:
- IO monads — The IO monad is a less flexible alternative for managing side effects
- Async/await and coroutines — Async/await is a special case of an effect handler for the Async effect
Вопросы для размышления
- async/await in JavaScript is an algebraic effect. Then why does async 'infect' the entire call chain (a function calling an async becomes async)? Do algebraic effects solve this?
- Algebraic effects let you test without mocks: the test handler replaces the production handler. How does this change application architecture compared with Dependency Injection?
- OCaml 5 added effects for multicore parallelism. How do effects help build a scheduler that does not block an OS thread on an IO operation?