Skip to main content

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​

TheoremFile
progress, preservationSoundness.lean
safetyImmutability.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​

TheoremFile
imm_never_changesImmutability.lean
reaches_only_immImmutability.lean
reachable_from_imm_never_changesImmutability.lean
program_imm_never_changesImmutability.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, an imm location holds the same value. The only step that writes is set, and it needs a mut cell.

  • reaches_only_imm: everything reachable from an imm location is imm, also through what its closures captured. That's what E0223 is for:

    let xs = mut [1];
    let nested = [xs]; // E0223: else `nested[0]` could change
    let c = mut [0];
    let fs = [|| { c[0] = 1; }]; // E0223: the closure changes `c`
  • reachable_from_imm_never_changes: the two together, nothing reachable from an imm location ever changes.

  • program_imm_never_changes: the same for a whole program, run from an empty heap.

What a call can change​

TheoremFile
steps_cleanPurity.lean
changes_only_frame, changed_is_in_frame_and_mutFrame.lean
call_changes_only_what_args_reachFrame.lean
imm_fn_changes_only_what_it_is_givenFrame.lean
imm_fn_changes_nothingFrame.lean
imm_fn_changes_only_through_handlerFrame.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: an imm function, given a pair whose second part is imm all the way down, changes only what the first part reaches.

  • imm_fn_changes_nothing: an imm function given an argument that's imm all 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 total changes only what the handler of Log can 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​

TheoremFile
Freeze.typed, Freeze.existsSoundness.lean
steps_simSharing.lean
imm_copy_changes_nothingSharing.lean
imm_merge_changes_nothingSharing.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 how imm values are stored, with each mut location one in both, take the same steps, with results that correspond.
  • imm_copy_changes_nothing: using a copy of an imm location in place of it computes the same.
  • imm_merge_changes_nothing: using one of two imm locations that hold the same value for both computes the same.

imm e without the copy​

TheoremFile
Freeze.keys, Freeze.fresh, Freeze.shapeRegion.lean
region_freeze_step, toImms_in_place_change_nothingUnique.lean
checked_toImms_in_place_change_nothingUniqueCheck.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.lean says what the copy does: it copies exactly the mut objects 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 an imm e, nothing outside the region has its objects, then the program with every imm e done in place computes what it does. region_freeze_step is the step itself.
  • checked_toImms_in_place_change_nothing (#284): a check of the program as written gives that premise. An imm x is in place when x is a new mut object that's only read, written, or given to functions that borrow it, like fill above, before it's made imm. That it holds only what's imm already 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​

TheoremFile
Sub.to_ro, Sub.transSubtyping.lean
HasType.newRo, HasType.newRo_tparamReadOnly.lean
HasType.lit_ro, HasType.lit_imm_fits, HasType.new_param_noneLiterals.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 be ro, with what it holds seen as ro, and HasType.lit_imm imm when that's imm all the way down.
  • HasType.lit_imm_fits: making it imm when it can be loses nothing, since the imm literal fits wherever the ro one does. So the least mutability is the one to infer.
  • mk can be called at imm and at ro, with a mut argument seen as ro, but not at mut, and its body can't change what it makes. mkAny can be called at mut too, 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​

TheoremFile
Sub.fn, Sub.immCell, Sub.immSubtyping.lean, Soundness.lean
Ty.sub_var, StructDecl.sub_view, StructDecl.sub_immVariance.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​

TheoremFile
Ty.lub_sound, Ty.lub_leastLeast.lean
Ty.least_ro, Sub.no_fn_joinLeast.lean
Problem.principal, Problem.principal_lit, no_least_litPrincipal.lean
Problem.principal_lit_irPrincipal.lean
LinkedProblem.principal, Sub.none_meet, Sub.none_meet_upperLinked.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 most ro, 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 is imm when the least type is imm all the way down, and ro otherwise.
  • no_least_lit: but not with what a function assumes. In fn f['a, 'b, 'c, 'd] with 'a and 'b below both 'c and 'd, and both of those below ro, the literal (x, y) of an x: 'a [i32] and a y: 'b [i32] can be 'c or 'd, and nothing it can be is below both.
  • Problem.principal_lit_ir: if a literal's mutability can only be imm or ro, not any mutability below ro, there's a least one again, whatever the function assumes: imm and ro are in a line. In f, (x, y) is then ro.

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: with T given 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, or ro only 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't ro.

  • Sub.none_meet_upper: where the call's value goes keeps that so. Where it's ro, 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 = ro
    let k: mut [i32] = longer(mut [1], [2]); // no solution: [2] isn't mut
    let 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​

TheoremFile
atMost_iff_splitSolver.lean
Le.eq_immutable, Le.eq_mutableSolver.lean
le_iff_leSearchSolver.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 most imm can be made imm right away, and one above mut made mut, unless an assumption ends at imm or starts at mut. 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 ⊑ 'm from a mutability finds every chain that holds, once it can take as many steps as there are assumptions (Solver::mutability_le).

Struct types​

TheoremFile
StructDecl.atMost_ty_iffStructs.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 mut object, but not an imm one;
  • an imm object can't hold a mut one;
  • a generic function that reads what it's given, but can't change it;
  • an imm object can't hold a closure that changes what it captured;
  • Line { a: l.a, n: 5 } with a mut l can't be an imm Line, since it would share l.a, a mut Point;
  • an imm Box holding a T needs T ⊑ imm;
  • an iterator whose array has a mutability 'v of its own;
  • fn peek(xs: ro [i32]) taking a mut and an imm array, fn total(xs: 'm [i32]) = peek(xs) passing what it's given on as ro, and one type parameter for a mut and an imm value, as ro [i32].