What's proven
Each section below is one promise of the mutability rules, with the theorems that prove it, and Bolt code that shows what it means. The theorems are about the model, so a Bolt program is covered by a theorem through the way it maps to the model.
Most theorems start from a well-typed program, a heap that matches its
typing (HeapOk), and well-typed functions (FnsOk), and say something
about every run.
Programs don't get stuck
| Theorem | File |
|---|---|
progress, preservation | Soundness.lean |
safety | Immutability.lean |
A well-typed program that isn't done can take a step (progress), and a
step keeps it well-typed, in a heap typing that only grows
(preservation). Together, however many steps a program takes, it never
gets stuck (safety). So reading an element always reads an array, and
calling a value always calls a closure:
fn peek(xs: ro [i32]) -> i32 = xs[0];
fn apply(f: fn(mut [i32]) -> i32) -> i32 = f(mut [1]);
let n = apply(peek);
That holds with every kind of subtyping in the model: apply is given a
fn(ro [i32]) -> i32 where it expects a fn(mut [i32]) -> i32, and the
call in its body passes a mut [i32] to peek. Preservation's case for a
call shows the argument fits what the closure takes, and what it gives
fits what's expected (Sub.fn).
imm values never change
| Theorem | File |
|---|---|
imm_never_changes | Immutability.lean |
reaches_only_imm | Immutability.lean |
reachable_from_imm_never_changes | Immutability.lean |
program_imm_never_changes | Immutability.lean |
This is the promise that sharing makes hard: every name for an array is the same array, so an array that can't be changed through one name must not be changeable through any.
let xs = [1, 2];
let ys = xs;
ys[0] = 3; // E0221
-
imm_never_changes: however many steps a program takes, animmlocation holds the same value. The only step that writes isset, and it needs amutcell. -
reaches_only_imm: everything reachable from animmlocation isimm, also through what its closures captured. That's what E0223 is for:let xs = mut [1];let nested = [xs]; // E0223: else `nested[0]` could changelet c = mut [0];let fs = [|| { c[0] = 1; }]; // E0223: the closure changes `c` -
reachable_from_imm_never_changes: the two together, nothing reachable from animmlocation ever changes. -
program_imm_never_changes: the same for a whole program, run from an empty heap.
What a call can change
| Theorem | File |
|---|---|
steps_clean | Purity.lean |
changes_only_frame, changed_is_in_frame_and_mut | Frame.lean |
call_changes_only_what_args_reach | Frame.lean |
imm_fn_changes_only_what_it_is_given | Frame.lean |
imm_fn_changes_nothing | Frame.lean |
imm_fn_changes_only_through_handler | Frame.lean |
A program changes only what's reachable from the locations in it that
aren't imm, its frame (changes_only_frame). For a call, that's
what the function and its argument reach, and what's imm all the way
down adds nothing. So the types of a call say what it can change:
fn fill(xs: mut [i32], ys: imm [i32]) { xs[0] = ys[0]; }
let a = mut [0];
let b = [1];
fill(a, b); // only what `a` reaches can change
-
imm_fn_changes_only_what_it_is_given: animmfunction, given a pair whose second part isimmall the way down, changes only what the first part reaches. -
imm_fn_changes_nothing: animmfunction given an argument that'simmall the way down changes nothing that existed before the call.fn total(xs: imm [i32]) -> i32 = xs[0];let n = total([1, 2]); // changes nothing -
imm_fn_changes_only_through_handler: the same, with a handler as an extra argument, which is how an effect whose operations resume right away compiles. Only what the handler can reach changes.effect Log { fn log(n: i32); }fn total(xs: imm [i32]) -> i32 does Log = { log(xs[0]); xs[0] };Calling
totalchanges only what the handler ofLogcan reach. The reactive design needs this: while drawing, a component can only affect the world through its effects.
steps_clean is the invariant behind all of them: every location a
program can reach is imm, new, or allowed, and a step only writes to
locations that are new or allowed.
imm values can be copied or shared
| Theorem | File |
|---|---|
Freeze.typed, Freeze.exists | Soundness.lean |
steps_sim | Sharing.lean |
imm_copy_changes_nothing | Sharing.lean |
imm_merge_changes_nothing | Sharing.lean |
imm e copies each mut object that e's value reaches, once, and
shares what's imm. Freeze.typed: the copy has e's type with each
object imm. Freeze.exists: the copy can always be made. Together they
give progress and preservation for imm e.
let xs = mut [mut [1]];
let ys = imm xs; // `imm [imm [i32]]`: both arrays copied
Since an imm value never changes, a copy of it can't be told apart from
it. So the code generator may store small imm structs by value,
and make imm literals constants that are shared:
let a = [1, 2];
let b = [1, 2]; // may be the same object as `a`
steps_sim: two runs whose heaps differ only in howimmvalues are stored, with eachmutlocation one in both, take the same steps, with results that correspond.imm_copy_changes_nothing: using a copy of animmlocation in place of it computes the same.imm_merge_changes_nothing: using one of twoimmlocations that hold the same value for both computes the same.
imm e without the copy
| Theorem | File |
|---|---|
Freeze.keys, Freeze.fresh, Freeze.shape | Region.lean |
region_freeze_step, toImms_in_place_change_nothing | Unique.lean |
checked_toImms_in_place_change_nothing | UniqueCheck.lean |
Building an array and then making it imm is common:
fn fill(xs: mut [i32]) { xs[0] = 1; }
let xs = mut [0];
fill(xs);
let frozen = imm xs;
The copy imm xs makes is wasted here: nothing else has xs, so it could
be made imm where it is.
Region.leansays what the copy does: it copies exactly themutobjects the value reaches, its region (Freeze.keys), each to a location of its own (Freeze.fresh), and each copy holds what its original does, with the region's objects replaced by their copies (Freeze.shape).toImms_in_place_change_nothing: if whenever a program gets to animm e, nothing outside the region has its objects, then the program with everyimm edone in place computes what it does.region_freeze_stepis the step itself.checked_toImms_in_place_change_nothing(#284): a check of the program as written gives that premise. Animm xis in place whenxis a newmutobject that's only read, written, or given to functions that borrow it, likefillabove, before it's madeimm. That it holds only what'simmalready is still a premise (Shallow).
It doesn't hold when something else has the object:
let xs = mut [0];
let ys = xs;
let frozen = imm xs; // must copy: `ys` can still change `xs`
ys[0] = 1;
Read-only views
| Theorem | File |
|---|---|
Sub.to_ro, Sub.trans | Subtyping.lean |
HasType.newRo, HasType.newRo_tparam | ReadOnly.lean |
HasType.lit_ro, HasType.lit_imm_fits, HasType.new_param_none | Literals.lean |
A mut or imm value can be seen as ro, and the view is deep:
fn first(xs: ro [[i32]]) -> ro [i32] = xs[0];
let xs = mut [mut [1]];
let ys = first(xs);
ys[0] = 2; // E0221: what's read through `ro` is `ro` too
The theorems about imm values hold with ro in the model, so seeing a
value as ro can't be used to change an imm one. Sub.to_ro: every type
fits its ro view. Sub.trans: subtyping composes.
ReadOnly.lean and Literals.lean are groundwork for literals whose
mutability is inferred (#415).
A tuple of generic values can't be imm, since its parts may be mut,
which is why the checker rejects this today:
enum Opt[T] { No, Yes(T) }
fn same[T](a: Opt[T], b: Opt[T]) -> Bool = match (a, b) { // E0230
(Opt.No, Opt.No) => True,
_ => False,
};
HasType.newRo_tparam: a ro literal holding a T is a ro (ro T),
with nothing assumed. At run time, a ro literal makes a mut object,
which the program only sees as ro.
Nothing is mut unless it's asked for. A literal is mut only if its
mutability is written: as mut [x], or as a mutability parameter of its
function, like 'n [x], which a call can make mut. A literal without a
written mutability is only imm or ro, the least that works, and in an
inferred signature that can be a parameter at most ro:
fn mk(x) = [x]; // fn mk['m ⊑ ro, T ⊑ 'm](x: T) -> 'm [T]
fn mkAny['n, T: 'n](x: T) -> 'n [T] = 'n [x];
let a = mkAny(mut [1]); // 'n = mut: mut [mut [i32]]
a[0] = mut [2];
In the model, a literal's mutability is a written one or a mutability
parameter in scope (Mu.Lit). That an unwritten one is only imm or
ro is a rule of inference, which Problem.principal_lit_ir covers.
HasType.lit_ro: a literal can always bero, with what it holds seen asro, andHasType.lit_immimmwhen that'simmall the way down.HasType.lit_imm_fits: making itimmwhen it can be loses nothing, since theimmliteral fits wherever theroone does. So the least mutability is the one to infer.mkcan be called atimmand atro, with amutargument seen asro, but not atmut, and its body can't change what it makes.mkAnycan be called atmuttoo, and its caller can then change what it returns.HasType.new_param_none: a program that runs has no mutability parameters in scope, so none of its literals has one.
Function subtyping and variance
| Theorem | File |
|---|---|
Sub.fn, Sub.immCell, Sub.imm | Subtyping.lean, Soundness.lean |
Ty.sub_var, StructDecl.sub_view, StructDecl.sub_imm | Variance.lean |
A function that takes ro fits where one that takes mut is expected
and what an imm array holds can be seen as a supertype of its
type. The checker allows both:
fn reads(xs: ro [i32]) -> i32 = xs[0];
fn call_all(fs: imm [fn(mut [i32]) -> i32]) -> i32 = fs[0](mut [1]);
let n = call_all([reads]);
Sub.imm: the copy imm e makes of a value seen at a supertype fits the
copy of that type, which is why imm arrays need to be covariant once
functions are.
Variance.lean proves when a struct's type arguments can change.
A parameter can change as it is where it's only held, like T in
struct Box[T] { item: T }, the other way round in a function's
parameters, like T in struct Handler[T] { f: fn(T) -> () }, and not at
all in a mut object. The checker follows it (adt_variance in
crates/boltlang-hir-ty/src/variance.rs):
struct Box[T] { item: T }
struct Handler[T] { f: fn(T) -> () }
fn peek(b: ro Box[ro [i32]]) {}
fn call(h: imm Handler[mut [i32]]) {}
fn go(b: mut Box[mut [i32]], h: imm Handler[ro [i32]]) {
peek(b); // fine: `T` is only held
call(h); // fine: `T` is only in a closure's parameters
}
Ty.sub_var: a type with its arguments changed as their variance allows
is a subtype of it. StructDecl.sub_view: so mut Box[mut [i32]] can be
seen as ro Box[ro [i32]]. StructDecl.sub_imm: and an
imm Handler[ro [i32]] used as an imm Handler[mut [i32]].
Least solutions
| Theorem | File |
|---|---|
Ty.lub_sound, Ty.lub_least | Least.lean |
Ty.least_ro, Sub.no_fn_join | Least.lean |
Problem.principal, Problem.principal_lit, no_least_lit | Principal.lean |
Problem.principal_lit_ir | Principal.lean |
LinkedProblem.principal, Sub.none_meet, Sub.none_meet_upper | Linked.lean |
At a call, a type parameter gets the types of the arguments, which must fit it, and what it must be at most. It should be given the least type that all of them fit, within its bound:
fn pass[T: ro](x: T) -> T = x;
pass(mut [1]); // T = ro [i32]
pass([1]); // T = imm [i32]: already at most ro
pass(mut ([1], mut [2])); // T = ro (imm [i32], ro [i32])
fn both[T](a: T, b: T) -> T = a;
both([1], mut [2]); // T = ro [i32], whichever comes first
Ty.lub finds that type for two types, and for one type with a bound of
ro. Ty.lub_sound: what it finds is above both. Ty.lub_least: it's
below every other type that is, so if there's any solution, it finds the
least one. Ty.least_ro: there's always a least type at most ro above a
type. It isn't the view: what's already at most ro, like an imm array,
is kept.
Ty.lub_least needs that function types in the same place take the same
parameters. Two closures of different mutabilities have no type above both
(Sub.no_fn_join). The checker doesn't find least types yet: it takes the
first argument's type, and sees all of it as ro once anything in it may
change.
A solution that's below every other is principal: taking it never rules out what another would allow.
Problem.principal: what a call says about one type variable, what flows into it, where its value goes, what it must be exactly and whether it's at mostro, has a least solution whenever it has one, if something flows in or it's given exactly, and no function type flows in.Problem.principal_lit: so does an inferred literal, its type and its mutability together, with nothing assumed. The mutability isimmwhen the least type isimmall the way down, androotherwise.no_least_lit: but not with what a function assumes. Infn f['a, 'b, 'c, 'd]with'aand'bbelow both'cand'd, and both of those belowro, the literal(x, y)of anx: 'a [i32]and ay: 'b [i32]can be'cor'd, and nothing it can be is below both.Problem.principal_lit_ir: if a literal's mutability can only beimmorro, not any mutability belowro, there's a least one again, whatever the function assumes:immandroare in a line. Inf,(x, y)is thenro.
A signature links variables. In fn f[T](a: [T], b: [T]), the array's
mutability and T must be solved together:
f(mut [mut [1]], mut [[1]]); // T = ro [i32], so the array must be ro too:
// a mut [mut [i32]] doesn't fit a mut [ro [i32]]
-
LinkedProblem.principal: withTgiven the shape of what it's given, and a variable for each mutability in it, what a call says about the mutabilities of its signature has a least solution whenever it has one. Each variable is what it's given, orroonly where it must be. -
Sub.none_meet: that's because below any two solutions there's another, which takes each variable from one where it isn'tro. -
Sub.none_meet_upper: where the call's value goes keeps that so. Where it'sro, any choice fits, and elsewhere a choice that fits is exactly what's there. So the least solution can take it into account:fn longer(a: 'm [i32], b: 'm [i32]) -> 'm [i32] = a;let l = longer(mut [1], [2]); // 'm = rolet k: mut [i32] = longer(mut [1], [2]); // no solution: [2] isn't mutlet j: mut [i32] = longer(mut [1], mut [2]); // 'm = mut
This is with nothing assumed, and without function types. Constraints
between two type variables, and a type parameter given as both T and
ro T, aren't covered.
The checker's solver
| Theorem | File |
|---|---|
atMost_iff_split | Solver.lean |
Le.eq_immutable, Le.eq_mutable | Solver.lean |
le_iff_leSearch | Solver.lean |
The checker's solver (crates/boltlang-hir-ty/src/solve.rs) doesn't
search for derivations of "at most". It takes shortcuts, and these prove
them right:
-
atMost_iff_split: splitting "a type is at mostμ" into the mutabilities it holds, each at most the one around it, and its type parameters, says exactly what "at most" does (Solver::solve_at_most). -
Le.eq_immutable,Le.eq_mutable: an unknown mutability that must be at mostimmcan be madeimmright away, and one abovemutmademut, unless an assumption ends atimmor starts atmut. That's how the checker decides the hidden mutability parameters of a signature early:fn keep(x) = [x]; // `fn(x: a) -> imm [a]`, with `a ⊑ imm` -
le_iff_leSearch: following assumptions like'v ⊑ 'mfrom a mutability finds every chain that holds, once it can take as many steps as there are assumptions (Solver::mutability_le).
Struct types
| Theorem | File |
|---|---|
StructDecl.atMost_ty_iff | Structs.lean |
A struct type with arguments is well-formed exactly when its arguments
meet what its fields imply. For VecIter, that's 'v ⊑ m and T ⊑ 'v:
struct VecIter[T, 'v] { data: 'v [T], index: i32 }
fn f(it: mut VecIter[mut [i32], imm]) = (); // E0223: `data` would be an
// `imm` array of `mut` ones
The checker does the same, where a value is made and wherever it splits a
struct type (struct_atoms_of in holds.rs).
Examples
Examples.lean shows what the rules accept and reject, each as a proof
about a small program:
- changing a
mutobject, but not animmone; - an
immobject can't hold amutone; - a generic function that reads what it's given, but can't change it;
- an
immobject can't hold a closure that changes what it captured; Line { a: l.a, n: 5 }with amutlcan't be animm Line, since it would sharel.a, amut Point;- an
imm Boxholding aTneedsT ⊑ imm; - an iterator whose array has a mutability
'vof its own; fn peek(xs: ro [i32])taking amutand animmarray,fn total(xs: 'm [i32]) = peek(xs)passing what it's given on asro, and one type parameter for amutand animmvalue, asro [i32].