Effects
What effects are, with does, +, effects with parameters and handlers,
and why, is in the design of effects. This page
is how the checker infers and checks them.
Kind inference
Effects bring a new kind. The kinds are now:
is the kind of rows. A single effect is a row of one, so
Log, State[i32] and Async + Log are all of kind .
State is of kind , so State alone
isn't a row, as Option alone isn't a type. Koka has two kinds here, one
for single effects and one for rows. With one, an effect variable can stand
for any row, which is what map needs, and there's less to learn.
Kinds are still never written. Inference gets two new equations, next to those for types:
- Every term of a row after
doesis of kind . effect T[a_1, …, a_n]is of kind , where the come from the operations.
The rest is unchanged: an application gives , a parameter or field type is of kind , and the equations are solved by unification.
An effect declaration is a group of its own, with its operations, like a
class with its methods. So the kind of State's S comes from the types of
get and set.
For the map above:
| Parameter | Used as | Kind |
|---|---|---|
A | [A], fn(A) | |
B | -> B, [B] | |
E | does E |
A parameter of an effect can be a row too:
effect Spawn[E] {
fn spawn[T](task: fn() -> T does E) -> Task[T];
}
E is of kind , so Spawn is of kind
, and Spawn[Async + Log] is a row.
Defaulting
A kind variable that nothing decided becomes , as before.
An effect variable is always used after a does, so its kind is always
decided, and it's never defaulted. That holds for the parameters of types
and classes as well:
struct Button[E] { on_click: fn() -> () does E }
E is of kind from its use, so Button[Async] is a
button whose click can wait.
Errors
Kind errors are reported like they are now:
fn f(x: Log)expects a type and finds an effect: "expected a type of kindType, foundLogof kindEffect" (E0216).fn f() does i32expects an effect and finds a type: "expected a type of kindEffect, foundi32of kindType".fn f() does Statemisses an argument, likeOptionalone: "expected 1 type argument, found 0".- A parameter used both ways, like
Einfn f[E](x: E) does E, takes the kind of its first use, and lowering reports the second.
Applications with an unknown head
Kind inference allows a parameter of kind
, like the H in:
fn run[H, T](f: fn() -> T does H[T]) -> T;
But a row is unified by the names of its effects (see below), and H[T]
has no name until H is known. So for now, every effect in a row has to be
a known effect or an effect variable, and H[T] in a row is an error.
Rows as predicates
Rows follow Morris and McKinna's Rose [Morris & McKinna 2019]. A row in a
type has the effects that are known, like Log + State[i32], and can be
made of rows that stand for any row, like the E of Log + E: parameters,
and the variables of an inferred function's type. A row made of rows still
being inferred is a variable instead. How rows relate is a predicate on
them, which the solver defers until the rows are known well enough, as it
does for class constraints:
- Containment,
ρ₁ ≲ ρ₂: every effect ofρ₁is inρ₂, with the same arguments. A call addscallee ≲ body: the effects of what it calls must be effects of the code it's in. - Combination,
ρ₁ ⊙ … ⊙ ρₙ ~ ρ:ρhas the effects of all of them. Using a function whose type hasLog + EgivesEa new variable?e, and the row becomes a variable?rwithLog ⊙ ?e ~ ?r. Once?eis known,?ris too.
What the predicates mean is a row theory. Rose works with several; Bolt's
is consistent union: rows combine by union, and the same effect in both
must have the same arguments. So Log ⊙ Log ~ Log, but no row has both
State[i32] and State[String]. The paper's main example, simple rows, only
combines rows with no effect in common, which would make does Log + E fail
for an E that logs too.
Containment is checked like this:
- No effects fit in any row, a row fits in itself, and a row fits in a row
made of it, like
EinLog + E. - Two rows that aren't variables: each effect of the first must be in the
second, and its arguments are unified with those there. Each row the
first is made of, like
E, must be one the second is made of: a parameter stands for any row, so it isn't known to be in any other. - A variable on either side: the constraint waits.
Combination waits until its rows aren't variables, and then makes the goal their union.
The same check lets a function that does less fit where one that does more
is expected. When two function types meet and both of their rows are known,
the given function's row must fit in the expected one's, with containment
checked as above, so quiet can be passed for a fn() does Log:
effect Log { fn log(n: i32); }
fn run(f: fn() -> () does Log) does Log = f();
fn quiet() = ();
fn go() does Log = run(quiet);
The other way round, a function that does more where one that does less is
expected, is an error. In a function's parameters it's turned the other way
round, as for their types, and a row that's an argument of a struct or enum
fits as the argument's variance says, like the E of
struct Lazy[E] { run: fn() does E }. When either row is still a variable,
the two are made the same row, so that inferring one gives the other.
Least solutions
What a function does is the least row that holds what it calls. When a
function is generalized, each row variable that's only in positive
places, like the does of the function, of a closure it returns, or of a
struct it returns where the row's argument keeps its direction, gets the
union of the rows that must fit in it, or Nothing. That's as general as
leaving it open, since a smaller row fits wherever a bigger one does. A row that must hold exactly one unknown row becomes that row:
twice: forall a e. fn(fn() -> a does e) -> a does e
The rows of parameters stay variables, and a least row can be made of them:
noisy: forall a e. fn(fn() -> a does e) -> a does Log + e
compose: forall a b c e f. fn(fn(a) -> b does e, fn(c) -> a does f) -> fn(c) -> b does e + f
Rows that wait only for each other, like those of functions that call each other, have the same least solution, so they're made one. A row constraint that's still left becomes part of the function's type.
A row that nothing decides has no effects, like the row of a closure that calls nothing.
Implementation
Ty::Row in boltlang-hir-ty is a row's known effects and the rows it's
made of, both sorted so that equal rows are equal; a row that's one
parameter and nothing else is that parameter. Row variables are inference
variables of kind Effect, and row parameters are type parameters of kind
Effect. Containment and combination are RowConstraint in rows.rs,
solved by the solver like other deferred constraints. How one known row
fits in another is Ty::row_fit, which the solver uses for containment,
and the unifier where it meets two function types (Unifier::unify_contained). Instantiating a
scheme turns each row made of variables into a variable and a
combination (open_rows). A scheme keeps the row constraints left about
its rows. Instances don't keep rows: monomorphization skips row
parameters, since only the checker needs them.
Inferring effects
A body's effects are inferred like its types. The body starts with a fresh
row variable, and each call adds the effects of what it calls. A match
with effect arms takes the effects it handles out.
Closures get their effects the same way, and the calls in a closure's body
add to the closure's effects, not to those of the code around it: || fetch(x) is fn() -> Response does Async. A function without a written
result type gets the least row that holds what it
calls, so it's polymorphic in what its callbacks do:
fn twice(f) { f(); f() }
twice: forall a e. fn(fn() -> a does e) -> a does e
Handlers
A handler's typing rules are in the design.
The checker infers the scrutinee's row like the effects of a body, and adds a predicate for each effect with arms, solved once is known: is without , and the arguments of in must be those the arms use. When stays unknown, because it's the row of a parameter of an inferred function, becomes , as Rose and Koka have it:
fn quiet(f) = match f() {
v => v,
effect log(m), k => resume(k, ()),
};
// forall a e. fn(fn() -> a does Log + e) -> a does e
So quiet only takes functions that do Log. Keeping the predicate in
the type instead is discussed in
#358.
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.