Effects
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 + LogandLog + Asyncare the same. doescomes before a body,=andwhere:fn f[T](x: T) -> T does Log where Show[T] = ….- In a function type,
doesis part of the type:f: fn(A) -> B does Log, n: i32. It belongs to the nearestfn, sofn(A) -> fn(B) -> C does Logis a function that returns a function withLog. - A closure writes
doesafter 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
doeslike 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:
| Written | Result | Effects |
|---|---|---|
fn f(x: i32) -> i32 | i32 | none |
fn f(x: i32) does Async | inferred | exactly Async |
fn f(x: i32) -> i32 does Async | i32 | exactly Async |
fn f(x: i32) | inferred | inferred |
- A written result type without
doesmeans the function has no effects, as in Koka [Leijen 2014]. Iftotalcalledlog, that would be an error at its signature. - A written
doesis all the function does, also when the result type is inferred. Ifis_upcalledlog, that would be an error too. A function that hasAsyncand 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 anymatch. 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.kis the continuation: the rest of the scrutinee, paused where it performed the operation. resume(k, v)continues the scrutinee withvas the result of the operation. It returns what the wholematchgives for the rest of the scrutinee. Sox + resume(k, ())addsxto the sum of what's yielded after it, and the value arm gives0at 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
. With _, they can return different types, like raise and fail
above.
Typing
Say the scrutinee has type and does ,
where the are the effects with arms, and the match has
type :
- The value arms have patterns of type , and must be exhaustive.
- An arm for an operation
fn op(a: A) -> Bof has patterns of type , and bindskto aCont[B, U, R], whereRis what resuming the continuation does.Ris of kind . Handlers are deep: resuming runs the rest of the scrutinee, still handled, so its next operation runs an arm again.Ris the row of the enclosing function or closure, which the arms run with and which has in it. That's also the row Conduit gives a continuation: its handler's. Just plus what the arms do would be more precise (#370). resume(k, b)has type and doesR.- The
matchdoes , 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
printandpanichave. - How to give
doesto the outer function offn(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.