Skip to main content

Effects

Partly implemented

The type checker infers and checks effects: rows, does, containment, combination, Nothing and handlers, with their arms for every operation and for every value of its arguments. Operations and handlers run through Conduit (Conduit), and std has Fail and Async. What's left is in Still to decide. Algebraic effects are tracked in #40.

An effect is something a function can do besides returning a value: waiting, failing, reading some state, logging. A function's type says which effects it can have, after does:

fn fetch(url: String) -> Response does Async;
fn crawl(url: String) -> () does Async + Log;

The async and reactive UI designs build on this page.

Declaring an effect​

An effect is declared with its operations, the functions that perform it:

effect Log {
fn log(message: String);
}

effect State[S] {
fn get() -> S;
fn set(value: S);
}

An operation is called like any other function, by its bare name, as class methods are: log("hi"), get(). It's in scope wherever its effect is. If two effects in scope have an operation of the same name, a call writes the effect too: State.get().

Calling an operation gives the caller the effect: a function that calls log has Log in its type. A handler decides what an operation does, and takes the effect out of the type of the code it runs.

Writing effects​

Effects come after does, joined with +, after the result type if one is written:

fn crawl(url: String) -> () does Async + Log { … }
fn count(xs: [String]) -> i32 does State[i32] = …;
fn is_up(url: String) does Async = match fetch(url) { … };
fn total(xs: [i32]) -> i32 = …;
  • The order doesn't matter: Async + Log and Log + Async are the same.
  • does comes before a body, = and where: fn f[T](x: T) -> T does Log where Show[T] = ….
  • In a function type, does is part of the type: f: fn(A) -> B does Log, n: i32. It belongs to the nearest fn, so fn(A) -> fn(B) -> C does Log is a function that returns a function with Log.
  • A closure writes does after its parameters, or after its result type if it has one, and then its body must be a block, as with a result type: |x| -> i32 does Log { … }, |x| does Log { … }. Most closures don't write it: their effects are inferred.
  • A function the host provides says does like any function: #[link(wasm, module = "env")] fn log(message: String) does Console;. Without it, it has no effects.

Written or inferred​

A function's effects are inferred only when neither its result type nor does is written:

WrittenResultEffects
fn f(x: i32) -> i32i32none
fn f(x: i32) does Asyncinferredexactly Async
fn f(x: i32) -> i32 does Asynci32exactly Async
fn f(x: i32)inferredinferred
  • A written result type without does means the function has no effects, as in Koka [Leijen 2014]. If total called log, that would be an error at its signature.
  • A written does is all the function does, also when the result type is inferred. If is_up called log, that would be an error too. A function that has Async and whatever else its body does writes an effect variable: does Async + E.
  • Without either, the effects are inferred like the types (see Inferring effects).

So a complete signature, with every type and mutability written, tells callers what the function does without its body.

Function types follow the same rule: fn(A) -> B has no effects. So a parameter that takes a function with any effects needs an effect variable, as map has below.

The cost of this rule is that a new effect deep down a call chain, like a call of log, has to be added to each written signature above it. Signatures that are inferred, or that have an effect variable, don't need changing.

Nothing​

Nothing is the row without effects. It's for two places:

fn double(x: i32) does Nothing = x * 2; // no effects, result inferred
let b: Button[Nothing] = …; // a button whose click does nothing

The first is the only way to say "no effects" without writing the result type. The second gives an effect parameter no effects, like map[i32, i32, Nothing].

Nothing is a name of the prelude, of kind Effect, and capitalized like other effects. It isn't an effect without operations: Nothing + E is E, and does Nothing + Log is does Log, which the formatter writes instead. It was chosen over none, which is too close to Option's None, and over (), which is the unit type. A modifier like Koka's total or a pure fn would be a second place to write effects, and couldn't be a type argument.

The effects after does are a row. + was chosen over a list in delimiters because there's nothing to close, so it can't be mixed up with a body (does { Async } { … }) or the , between parameters. It also reads like the bounds that Bolt already joins with +.

Effects with parameters​

An effect can have parameters, like State[S] above. Its arguments are fixed for the whole row: every get() of a State[i32] returns an i32.

An operation can have parameters of its own as well. Each call picks its own arguments, and the effect doesn't need a parameter for them:

effect Raise[E] {
fn raise[T](error: E) -> T;
}

effect Wait {
fn suspend[T](start: fn(fn(T) -> ()) -> ()) -> T;
}

raise can stand where any type is expected, because it never returns, and every suspend waits for a value of a different type. std's Async keeps its operations untyped instead, and its tasks' results in a Task[T], for reasons its design gives.

Parameters can be types, effects and mutabilities. Mutability parameters work as they do for structs.

Effect variables​

A function that takes a function as a parameter often has the effects of that function. An effect variable says so:

fn map[A, B, E](xs: [A], f: fn(A) -> B does E) -> [B] does E;

map([1, 2, 3], |x| x * 2); // E is Nothing
map(urls, fetch); // E is Async

So there's one map for every function, whatever it does. An effect variable is one more term in a row:

fn retry[T, E](times: i32, f: fn() -> T does E) -> T does Log + E;

retry has the effects of f and Log too. Nothing marks E as an effect variable: it's one because of where it's used, by the kind inference below.

A row can have several effect variables, like does E + F for a function that calls two functions it's given. The checker writes such a row as a predicate (see Rows as predicates), so there's no guessing how to split a row between the variables.

No effect twice​

An effect can be in a row only once, with one list of arguments:

fn f() does State[i32] + State[String];
// error: `State` is in this row twice, with different arguments

Writing the same effect twice with the same arguments is fine, and so is getting it twice: a function that logs and calls a function that logs does Log once. Rows combine by union, and an effect in both rows must have the same arguments there. So the effects of all the calls in a function tie their arguments together: after set(1), a set("one") in the same function is an error, since both are State.

Some languages allow the same effect twice, like Koka, where the innermost handler of an effect wins and mask skips it. That's flexible, but hard to explain, and it makes inference guess which of the two a call means. So it's an error for now. Allowing it later won't break code that type-checks today. Code that needs two states can declare a second effect.

Effects in classes​

A class method could have effects too, and an impl could have effects its class doesn't name, like an Iterator whose next waits. One way is an effect parameter on the class:

class Iterator[T, E] {
fn next(self: mut Self) -> Option[T] does E;
}

That's the plan, but not part of the first version: there, the methods of classes and impls can't have effects.

Handlers​

A handler is a match with effect arms, as in OCaml 5 [Sivaramakrishnan et al. 2021]. The match runs its scrutinee under the handler:

effect Yield {
fn yield(value: i32);
}

fn sum(body: fn() does Yield) -> i32 =
match body() {
() => 0,
effect yield(x), k => x + resume(k, ()),
};
  • Value arms, like () => 0, match what the scrutinee returns when it's done, as in any match. They're what Koka and OCaml call the return clause.
  • Effect arms, like effect yield(x), k => …, match an operation and its arguments, with ordinary patterns. k is the continuation: the rest of the scrutinee, paused where it performed the operation.
  • resume(k, v) continues the scrutinee with v as the result of the operation. It returns what the whole match gives for the rest of the scrutinee. So x + resume(k, ()) adds x to the sum of what's yielded after it, and the value arm gives 0 at the end. There's no mutable state.

Handlers are deep: after a resume, the rest of the scrutinee is still handled by the same match. An arm itself isn't, so an operation performed in an arm goes to the next handler out.

Not resuming​

An arm that doesn't resume aborts: the scrutinee never continues, and the arm's value is the value of the match. That's how exceptions work:

effect Raise[E] {
fn raise[T](error: E) -> T;
}

fn catch[T, E, R](body: fn() -> T does Raise[E] + R) -> Result[T, E] does R =
match body() {
value => Ok(value),
effect raise(error), _ => Err(error),
};

Keeping the continuation​

k is a value like any other. It can be kept and resumed later, which is what a scheduler does:

match main() {
() => run_next(queue),
effect suspend(start), k => {
start(|value| queue.push(|| resume(k, value)));
run_next(queue)
},
}

Here each arm runs the next task itself, so the stack gets deeper with each switch. std's block_on puts the rest of the task on the queue and returns to a loop instead (see Async).

A continuation can be resumed once. Resuming it again stops the program, as in Conduit, whose continuations are one-shot because the code they run can change things, and running those changes twice would be wrong.

State​

With the value arm, state can be a function that each arm passes on:

fn run_state[S, T, R](init: S, body: fn() -> T does State[S] + R) -> (T, S) does R {
let f = match body() {
value => |s| (value, s),
effect get(), k => |s| resume(k, s)(s),
effect set(s), k => |_| resume(k, ())(s),
};
f(init)
}

A let mut variable that the arms change is simpler, and works as well:

fn run_state[S, T, R](init: S, body: fn() -> T does State[S] + R) -> (T, S) does R {
let mut state = init;
let value = match body() {
value => value,
effect get(), k => resume(k, state),
effect set(s), k => { state = s; resume(k, ()) },
};
(value, state)
}

Every operation needs an arm​

A match that has an arm for an operation of an effect handles that whole effect, and must have arms for all its operations:

error[E0249]: this match handles `State`, so it needs an arm for `set` too

Otherwise the effect couldn't leave the row, and whether it does would depend on whether an arm was forgotten. To handle one operation and pass another on to the next handler out, the arm performs it again:

match body() {
value => value,
effect get(), k => { log("get"); resume(k, get()) },
effect set(s), k => resume(k, set(s)),
}

The arms run outside of the match, so the get() and set(s) in them go to the next handler, and the match still has State in its row. Arms like these always resume at the end, so Conduit compiles them to plain calls. A shorthand for passing on the rest is still to decide.

The arms of each operation must be exhaustive, like value arms: effect yield(0), k alone doesn't handle yield(1).

Names​

An arm names its operation by its bare name. When the effects of a match have two operations of the same name, the arm writes the effect too: effect State.get(), k. An operation without arguments keeps its parentheses, as in effect get(), k; whether effect get, k should mean the same is open in #354.

Several operations in one arm​

An arm can handle several operations, separated by |, with one continuation:

match job() {
v => v,
effect info(m) | warn(m), k => { print(m); resume(k, ()) },
effect raise(e) | State.fail(e), _ => Err(e),
}

The operations are the alternatives of an or-pattern, and follow the same rules: a name bound in one alternative is bound in all of them, with the same type. That includes k: a named continuation has the type Cont[B, U, R] of each operation, so they must all resume with the same BB. With _, they can return different types, like raise and fail above.

Typing​

Say the scrutinee has type TT and does Op1+⋯+ρ\mathit{Op}_1 + \dots + \rho, where the Opi\mathit{Op}_i are the effects with arms, and the match has type UU:

  • The value arms have patterns of type TT, and must be exhaustive.
  • An arm for an operation fn op(a: A) -> B of Opi\mathit{Op}_i has patterns of type AA, and binds k to a Cont[B, U, R], where R is what resuming the continuation does. R is of kind Effect\mathsf{Effect}. Handlers are deep: resuming runs the rest of the scrutinee, still handled, so its next operation runs an arm again. R is the row of the enclosing function or closure, which the arms run with and which has ρ\rho in it. That's also the row Conduit gives a continuation: its handler's. Just ρ\rho plus what the arms do would be more precise (#370).
  • resume(k, b) has type UU and does R.
  • The match does ρ\rho, plus what its arms do.

So match takes the effects it has arms for out of the row, and nothing else.

How the checker solves this, and what a function that handles an unknown row gets, is in the checker's effects.

resume and Cont are names of the prelude, like Nothing, and not keywords.

An operation with type parameters of its own, like fn suspend[T](…) -> T, gives each of its arms a new type for T, equal to no other type. In the scheduler above, k can only be resumed with a value of that type, which only start provides. Existential types of GADTs are checked the same way.

A handler becomes a handle in Conduit, as Conduit describes.

Why match​

A handler could also be a handle { … } with { fn yield(x) { … } } block, as in Effekt, or a declaration like impl. match was chosen because it has a return clause, its value arms, and matches the arguments of operations with patterns, with the exhaustiveness checks and decision graphs that Bolt already has. It also reads like handling exceptions. The cost is that a match that only handles effects still needs a value arm like v => v, and , k is a form that nothing else in Bolt has.

How the checker does it​

The checker's effects has the Effect kind and its inference, rows as predicates and their least solutions, and how a body's effects are inferred.

Still to decide​

  • How effects in classes work, beyond the plan above.
  • Which effects the prelude's print and panic have.
  • How to give does to the outer function of fn(A) -> fn(B) -> C. (T) is a one-element tuple type, so parentheses don't group types today.
  • A shorthand for passing operations on in a handler (#347).
  • discontinue(k), to unwind a continuation instead of resuming it, for cancelling.
  • match { … } { … }, with a block as scrutinee: Bolt has record literals in braces, so the parser has to tell the two apart.
  • Effects twice in a row, if it turns out to be needed.
  • Applications like H[T] in a row.

References​

  • J. G. Morris and J. McKinna. Abstracting extensible data types: or, rows by any other name. POPL 2019. In papers/ of the repository.
  • D. Leijen. Koka: Programming with row polymorphic effect types. MSFP 2014.
  • G. Plotkin and M. Pretnar. Handlers of algebraic effects. ESOP 2009.
  • K. C. Sivaramakrishnan, S. Dolan, L. White, T. Kelly, S. Jaffer and A. Madhavapeddy. Retrofitting effect handlers onto OCaml. PLDI 2021.
  • J. I. Brachthäuser, P. Schuster and K. Ostermann. Effects as capabilities: effect handlers and lightweight effect polymorphism. OOPSLA 2020. The design of Effekt.