Mutability
The design was decided in #196 and implemented in #195.
Arrays and structs are shared: let ys = xs makes ys
another name for the same array, and let q = p another name for the same
struct, as in JavaScript, Java and OCaml. Passing one to a function passes
a pointer, and a function can fill in what it's given.
Sharing breaks what mut on a variable promises:
let mut xs = [1, 2];
let ys = xs; // not `mut`
xs[0] = 9;
ys[0]; // 9: `ys` changed anyway
This chapter describes how the type checker keeps a promise that sharing can't break. Whether an array or a struct can be changed is part of its type, and every name for it has the same type, so they all agree.
Arrays and structs have a mutability
The type of an array or a struct has a mutability, which is Mut or
Imm:
Mut and Imm are types of their own kind. A mutability
can be an inference variable, like any type, and it's unified and
generalized like one. That's all the type checker needs: no subtyping, and
no new kind of constraint. A struct's mutability isn't one of its type
arguments, so it doesn't change its kind: Box is still of kind
.
In source code, and when types are shown:
| Written | Means |
|---|---|
mut [i32], mut Point, mut (i32, i32) | can be changed |
imm [i32], imm Point, imm (i32, i32) | can never be changed, by anyone |
[i32], Point, (i32, i32) | either: see annotations |
Only arrays, structs and tuples have a mutability. A tuple works like a
struct with numeric fields: t.0 = 1 needs t to be a mut tuple, like
let t = mut (1, 2), and the variable it's in doesn't matter. The unit
type () is always imm. An enum can't be changed in place: match gives
the values of its fields, and there's no way to assign to one. mut before
anything else, like mut i32 or mut Option[i32], is an error (E0222).
Something can be changed only if its type is mut:
fn push[T](xs: mut [T], x: T); // in `std`
let xs = mut [1, 2];
xs.push(3); // fine
xs[0] = 9; // fine
let p = mut Point { x: 0, y: 0 };
p.x = 5; // fine
let ys = [1, 2];
ys[0] = 9; // error: `ys` is `imm [i32]`, which can't be changed
Assigning to an element, xs[i] = e, needs xs to be a mut array, and
assigning to a field, p.x = e, needs p to be a mut struct. So does
calling a function whose parameter is mut, like push. What decides is
the innermost array or struct of the place that's assigned to: in
l.a.x = 1, it's l.a, and in xs[0].x = 1, it's xs[0].
Where the mutability comes from
The expression that makes an array or a struct decides whether it can be changed. Variables only pass it on:
-
[1, 2],(1, 2)andPoint { x: 0, y: 0 }can't be changed:imm [i32],imm (i32, i32)andimm Point. -
mut [1, 2],mut [],mut (1, 2),mut Point { x: 0, y: 0 }and, for a tuple struct,mut Meters(1.0)can be changed. -
A function's result has the mutability of its type:
Vec.new()could returnmut [T], andxs.copy()a newmut [T]. -
mutbefore a variant's literal, likemut Shape.Circle { radius: 1.0 }, is an error (E0222). -
mutbefore anything else, like a variable or the call of a function, is an error (E0222). A copy that can be changed is a call:to_mut(e)copies the value itself and shares what it holds, andto_mut_deep(e)copies all of it. Each type says how with an impl ofToMutorToMutDeep, so aVeccopies only its elements, not the room it has to grow.imm estays built in, since it must be deep: it copies what'smut, with the type's impl ofToImmDeep, which it needs: a type without one, or aVec[Point]withoutToImmDeep[Point], is an error, unlessimmdoesn't change it.to_imm_deep(e)calls the impl itself.A literal is told apart by the checker, not the parser:
mutbefore an array, a struct literal or a call of a tuple struct's constructor makes that onemut.mutbinds like-, somut [1].len()ismutof the length, and(mut [1]).len()that of amutarray.
let mut no longer has anything to do with the contents of an array or a
struct. It only means the variable can be assigned again:
let xs = mut [1];
xs.push(2); // fine: the array is `mut`
xs = mut [3]; // error: `xs` isn't `mut`
let mut ys = [1];
ys = [2, 3]; // fine: the variable is `mut`
ys.push(4); // error: the array isn't
Aliases share the mutability
let ys = xs unifies the types of ys and xs, mutability included. So an
alias of a mut array or struct is mut too, without saying so:
let xs = mut [1, 2];
let ys = xs; // `mut [i32]`, like `xs`
ys.push(3); // fine, and `xs` sees it
Since this is unification, it works however the alias is made: through a function, a branch, a struct or a closure.
fn id(x) = x;
let a = id(xs); // `mut [i32]`
let b = if c { xs } else { mut [] }; // `mut [i32]`
let get = || xs; // `mut fn() -> mut [i32]`
An alias can't change the mutability. Unifying Mut with Imm is an error:
let xs = mut [1, 2];
let ys: imm [i32] = xs; // error: expected `imm [i32]`, found `mut [i32]`
S { ..base } copies the fields it doesn't give from base, so it can
make a struct of another mutability from it, like a mut Point from an
imm one. But the copy is shallow: an array, struct or function in a field
is shared with base, which would make it an alias with another
mutability. So when a field that's copied holds one with the struct's own
mutability, base must have the same mutability as the struct:
let q = mut Point { ..p }; // fine, whatever `p` is: the fields are numbers
let l = mut Line { a: mut Point { x: 1, y: 2 }, b: mut Point { x: 3, y: 4 } };
Line { ..l } // error: expected `imm Line`, found `mut Line`
Line { a: Point { x: 0, y: 0 }, b: Point { x: 0, y: 0 }, ..l } // fine: nothing is copied
Deep imm
What an imm value holds can't be changed either. Otherwise an
imm Line could hold a mut Point, and the line would change after all.
The tutorial shows the rules
from a user's side; this section is about how the checker applies them.
A field has the mutability of its struct. An array or struct in a
field without mut or imm has the struct's own mutability, which is a
hidden parameter of the struct: struct Line { a: Point, b: Point } is
Line^m with a: Point^m. A field can be imm, but not mut (E0224),
since a mut field in an imm struct would break the rule. The fields of
an enum, which has no mutability, are imm.
In a field like imm [Point], the Point is imm too, since an imm
array can only hold imm ones.
An imm value can't hold a mut one through a type parameter
(E0223): Box { item: mut Point { .. } } is an imm Box[mut Point]. What
a struct holds is what its fields hold, not its type arguments: with
struct Handler[T] { f: fn(T) -> () }, an imm Handler[mut [i32]] is
fine, since a closure doesn't hold what it takes, and with
struct Frozen[T] { items: imm [T] }, only an imm T can be held, in
a Frozen of either mutability. That's the same as Rust inferring
T: 'a from a struct's fields, and it's what makes a struct type
well-formed (StructDecl.atMost_ty_iff in lean/BoltMut/Structs.lean).
Unification can't express this, since it's about a type and what's
inside it. It's an "at most" constraint instead, with imm ⊑ mut: an array or struct
holds only what's at most its own mutability. So [x] needs nothing in
the type of x to be more mut than imm. What an array or struct holds
must in turn be at most its mutability, and a function's mutability
covers what it captured; what it takes and gives isn't looked into, so an
imm [fn(mut [i32]) -> ()] is fine.
The constraint decides what's unknown when only one choice works: a
mutability that must be at most imm is imm, and one that something
mut must be below is mut. What's left about a function's parameters
becomes part of an inferred function's type, and its callers must meet it,
like class constraints:
fn wrap(x) = Box { item: x }; // forall a. a: imm => fn(a) -> imm Box[a]
wrap(mut [1]); // error (E0230): expected a type that's at most `imm`, found `mut [i32]`
A signature says it with a bound, T: imm, read as "nothing in T is
more mut than imm", like Rust's T: 'a for lifetimes. It can be
written next to the parameter or in a where clause, and a mutability
can be bounded too, as in 'v: 'm:
fn wrap[T: imm](x: T) -> imm Box[T] = Box { item: x };
fn reader(xs: 'v [i32]) -> 'f fn() -> i32 where 'v: 'f = || xs[0];
impl[T: imm] ToImm[[T]] { ... } // checked where the impl is chosen
struct Frozen[T: imm] { item: T } // checked where a value is made
Without the bound, a complete signature is an error where it needs one:
in fn hide[T](x: T) -> i32 { let b = Box { item: x }; 0 }, T may be
mut. A mut struct can hold anything, so mut Box { item: x } needs
nothing. A mutability on its own isn't a type: let x: imm = 1 is an error
(E0231). A mut array or struct inside an imm one is still also
caught once the types are known (E0223), which shows the whole type.
imm e of a type parameter has the type imm T: what imm makes of
T once it's known. The checker gives imm of a known type as that type,
with its arrays and structs imm, so imm T only stays for types it can't
take apart: type parameters, associated types like C.Item, and types
still unknown when an inferred function is generalized. So imm e never
needs a constraint:
fn h(x) = imm x; // forall a. fn(a) -> imm a
h(mut [mut [1]]); // imm [imm [i32]]
fn g[T: imm](x: T) -> T = imm x; // imm T is T when T is imm
fn f[T](x: T) -> T = imm x; // error: expected T, found imm T
Like an associated type, imm T only equals itself, since two types can
have the same imm: imm (mut [i32]) and imm [i32] are both imm [i32]. In a body, the checker replaces each written imm T by a variable
and the same constraint as imm e, which is how imm T becomes T under
T: imm. Written imm keeps its meaning before an array, a struct or a
function, and is imm T only before a type parameter or an associated
type.
mut T and 'm T give a type parameter a mutability (#459). Before a
type parameter or an associated type, mut or a name is the T with that
outer mutability, whatever its own: mut T with T = imm [i32] is
mut [i32], and for a type without a mutability, like i32, it's the type
itself. With 'm = ro, 'm T is ro T. A caller that only gives a
mut T decides T without its outer mutability:
fn count[I](it: mut I) -> i32 = 0; // count(mut [1]): I is [i32]
fn pick[T](a: 'm T, b: 'm T) -> 'm T = a; // pick(mut [1], mut [2]): mut [i32]
fn leak[T](x: ro T) -> mut T = x; // error: expected mut T, found ro T
Like imm T, it only equals itself, and in a body the checker replaces
it by a variable and a constraint, which T decides once it's known, or
what the variable is unified with while it isn't. What a 'm T holds is
at most 'm, as for a literal of a named mutability; for a T that isn't
known, the checker asks for T ⊑ 'm, which is more than needed, but never
less.
A closure that can change what it captured is mut. A function type
has a mutability like an array's. A closure is mut if it captures a
let mut variable, even only to read it, or a value that holds something
mut: a mut array, struct or function. Otherwise it's imm, and so is
a named function, which captures nothing. By the rules above, an imm
value can't hold a mut fn.
Calling a function doesn't need it to be mut, unlike Rust's FnMut: a
mut fn can't be reached from an imm value anyway. So a function type
written without mut or imm in a signature takes either, like [T],
and higher-order functions need no annotations. An imm fn is shown as
just fn, since most are, unless that would make two types in a message
look the same.
What a closure captures is at most its mutability, by the same "at most"
constraint, and a let mut variable makes it mut. So a generic function
that makes a closure says how the closure's mutability depends on what it
captured:
fn reader(xs: [i32]) = || xs[0]; // 'm: 'n => fn('m [i32]) -> 'n fn() -> i32
fn always[T](x: T) -> fn() -> T = || x; // forall T. T: 'm => fn(T) -> 'm fn() -> T
fn compose(f, g) = |x| f(g(x)); // forall a b c. 'm: 'o => 'n: 'o => fn('m fn(a) -> b, 'n fn(c) -> a) -> 'o fn(c) -> b
In std, an FnIter whose function counts is mut, like the one that
for x in xs uses for an array or a Vec.
What this guarantees
An imm value, and everything it holds, never changes. All the names
for a value have the same type, so if one of them can't change it, none
can, and an imm value only holds imm ones. A mut value can't be seen
as imm, which is what makes imm worth having:
- code can rely on an
immvalue it's given staying the same; - values that can't be changed can be shared freely, and their literals can be constants: a data segment in Wasm, made once;
- an
immstruct can't be told apart from a copy, so the code generator can store small ones by value; - the reactive design knows what can change, and which calls change it, from the types.
It doesn't guarantee what Rust does, that nothing else changes a mut
value while you have it. mut values are shared on purpose.
Read-only views: ro
ro is a view of a value that may or may not change, through which it
isn't changed.
Without it, a function that only reads takes values of one mutability per
call, and two values of different mutabilities can't meet: if c { a } else { b } with a mut and an imm Money is an error. With ro,
imm ⊑ ro and mut ⊑ ro: a value of either mutability can be given where
a ro one is received.
A ro view is deep. ro [[i32]] is ro [ro [i32]], so a
mut [mut [i32]] can be seen as one, and nothing in it can be changed
through it. That's sound only because nothing is written through ro:
inside a mut value, where an element is both read and written, the
mutabilities must be the same, so a mut [mut [i32]] isn't a
mut [ro [i32]]. The same goes for function types: a function that takes
ro fits where one that takes mut is expected, but not the other way.
ro isn't imm. A ro value can be changed by whoever has it as
mut, so an imm value can't hold one (E0223), and imm e of a ro
value is a copy. A closure in a ro struct can still be called, since a
ro value promises nothing about what its closures change.
ro T is a type parameter seen as ro. A T fits where a ro T is
expected, but a ro T isn't a T, so a generic function can't give back
what it read through ro [T] as a T. Once T is known, ro T is its
view: ro (mut [i32]) is ro [i32], and ro i32 is i32.
A struct's arguments change as its fields use them, its variance. The T of
struct Box[T] { item: T } is only held, so a mut Box[mut [i32]] can be
seen as a ro Box[ro [i32]], and a written ro Box[[i32]] is that type.
The T of struct Handler[T] { f: fn(T) } is in a closure's parameters,
so it changes the other way round: an imm Handler[ro [i32]], whose closure
only reads, can be used as an imm Handler[mut [i32]], but not the other
way, which would give an imm array to a function that changes it. A
parameter that's both held and taken can't change at all. A mut struct
keeps its arguments as they are, like the elements of a mut array, since
what it holds is read and written.
A ro value can't hold a mut one (E0223). Otherwise what's
read through it could be changed: through a ro (mut [i32], i32), t.0
would be a mut [i32], and through a ro Box[mut [i32]], so would
b.item. Seen as ro, both are ro [i32] instead. A written
ro Box[mut [i32]] stays an error, and so does a T that can't be seen
as ro, like that of a ro Both[mut [i32]] for
struct Both[T] { item: T, f: fn(T) }. A mut closure can still be held,
as above.
The rules are proven in lean/BoltMut: in Syntax.lean, Ty.ro is the
view and Ty.roParam is ro T; in Subtyping.lean, Sub says where a
type fits, and Sub.to_ro that a type fits its view. ReadOnly.lean has
the examples.
Variance.lean proves when a struct's arguments can change. A parameter in a
tuple, or in an object that's imm, ro, or whose mutability is a
parameter that becomes ro, is covariant, like the T of
Box[T] { item: T }: mut Box[mut [i32]] can be seen as
ro Box[ro [i32]]. One in a function's parameters is contravariant, like
the T of Handler[T] { f: fn(T) }: an imm Handler[ro [i32]] can be
used as an imm Handler[mut [i32]]. One in a mut object, or in one whose
mutability is a parameter that's kept, is invariant. The model has
function subtyping (Sub.fn), and what an imm object holds can be seen
as a supertype of its type (Sub.immCell), as the checker does for an
array that isn't mut.
Conduit has a ReadOnly mutability too, which is deep in the same way: under it, an
array's elements and a data type's fields fit covariantly, and so does
what an imm object holds, while a closure takes its parameters
contravariantly. A function called at ro gets an instance of its own,
since Conduit doesn't take ReadOnly as a mutability argument.
Named mutabilities
A name like 'm, written where mut or imm would be, is a mutability
that's the same wherever the name is. The
tutorial
shows how to use them; this section is about how the checker treats them.
' marks the name, as for labels and Rust's lifetimes: without it,
m [i32] would be the type m applied to i32.
-
A name is a parameter of the function or impl whose signature it's in, like a hidden one, but shared: every
'min the signature, itswherepredicates and its body is the same. Names don't need declaring: using one is enough. Like a hidden parameter, the caller chooses it, so the function can't change what has it, andfn make() -> 'm [i32] = [1]is an error. -
A name can be written before a literal, as
mutcan:'m [1],'m (a, b)and'm Point { x: 1 }are of mutability'm, which the caller may makemut. Nothing ismutunless it's asked for, and writing the name asks for whatever the caller gives. What the literal holds must be at most'm. Before anything but a literal, a name is an error, asmutis (E0222). -
A class declares its names (#453), after its type parameters, as a struct does. A name written in a class method's signature must be one of them: it never appears from nowhere.
class Default[T, 'm] { fn default() -> 'm T; }impl[T] Default[[T], 'm] { fn default() = 'm []; } // the impl's 'mimpl[T] Default[Vec[T], mut] { fn default() = Vec.new(); }An impl gives them, as it gives types, and an instance matches them exactly, so an impl for
mutalone, like that ofVec, is only formut, andimpl Default[[i32], imm]andimpl Default[[i32], mut]don't overlap. An impl that leaves one out, likeimpl Default[Bool], is for any. The types the class gives an impl's method are well-formed there, so that'm []may hold aT: a call checks that what a'm Tholds is at most'mwhere it chooses'm.A bound that leaves one out is for any mutability.
fn fresh[T: Default]() -> mut T = default()may useDefault[T, m]for everym, and a call needs an impl for each, sofreshworks for[i32]but not forVec[i32]. An associated type can depend on the name, soC.Itemneeds it written, as inwhere Get[C, 'm].A function whose class constraint has one of its mutabilities, like
where Freeze[C, 'v], gets an instance for each mutability it's called with, since that can choose the impl. -
Only functions, impls, classes and structs have names. An impl's associated types can use its names too:
impl[T] Iterable['m FnIter[T]] { type Iter = 'm FnIter[T]; ... }is for anFnIterof either mutability, and itsIterhas the same one. An impl's names, like its type parameters, must be in its instance, since that's all choosing the impl decides:impl[T, 'v] Iterable[Vec[T]]is an error (E0234), andimpl[T] Iterable['v Vec[T]]is what's meant. A name elsewhere, like in a const, a type alias outside an impl, a body that isn't its function's or a field whose struct doesn't declare it, is an error (E0225). A name before a type that can't have a mutability, like'm i32, is E0222. -
Types show names, and a name for a mutability that's shared but not written: one that a body decides, or a variable of an inferred function. Such names start at
'm, so that they don't read like the type variablesa,b, ...:fn pick(c, a, b) = if c { array_len(a); a } else { b }; // forall a. fn(Bool, 'm [a], 'm [a]) -> 'm [a]fn same(xs: [i32]) -> [i32] = xs; // fn('m [i32]) -> 'm [i32]fn size(xs) = array_len(xs); // forall a. fn([a]) -> i32A mutability that appears once isn't named: it's either, and it isn't linked to anything.
Names in structs
A struct declares its names after its type parameters, like
struct VecIter[T, 'v] { data: 'v Vec[T], index: i32 }. A type gives
them after its type arguments, like VecIter[i32, imm]. One that isn't
given is decided like the mutability before a type: a parameter in a
function's signature, an unknown in a body, and the struct's own in a
field. More than the struct declares is an error (E0232), and so is a
name declared by an item that isn't a struct, a function or an impl
(E0233). A function or an impl can declare its names too, but doesn't
have to.
A name is at most its struct's mutability. An imm VecIter[i32, mut]
would hold a mut Vec, which imm being deep rules out. So making a
struct adds 'v ⊑ m for each name its fields have, where m is its
mutability, and what a field with a name holds is at most that name:
T ⊑ 'v for data: 'v Vec[T]:
mut VecIter { data: mut_vec, index: 0 } // fine: mut VecIter[i32, mut]
VecIter { data: mut_vec, index: 0 } // error (E0223): an `imm VecIter[i32, mut]` can't have a `mut` mutability argument
fn frozen[T](v: 'v Vec[T]) -> imm VecIter[T, 'v] where 'v: imm = VecIter { data: v, index: 0 };
The last one needs 'v: imm, or 'v could be mut. It doesn't need
T: imm: v is a 'v Vec[T], so T ⊑ 'v, which it can assume, since
v exists. A struct can bound its names, like its type parameters, which
is checked where a value is made: struct Frozen['v: imm] { data: 'v [i32] }.
A struct update, VecIter { index: 1, ..it }, keeps the names of it,
since the fields it doesn't give are shared. Types show a name that's
known, like VecIter[i32, imm], and leave one out that's generic and
appears once, like the mutability before a type: VecIter[T]. One that's
left out before one that's shown is '_.
Related pages
- Prior art: other languages and papers that track whether a value can change.
- How the checker does it: inferred functions and
annotations, what
[T]means in a signature, and return types; where each rule is in the checker, the tests and the Lean proof; and the errors. - Leaving out the copy of
imm e: Conduit's region analysis (Conduit).
Open questions
- A name used once says nothing that leaving it out doesn't, and could be a warning.
- Impls for struct type constructors.
impl Functor[Box]is for boxes of either mutability, sofmapmust return aBoxwith the mutability of the one it's given, which it can't make:Box { item: f(b.item) }isimm. Higher-kinded types tie the mutability of the result to that of the argument, and what that should mean isn't decided.imm egives animmone, but not one of a caller's mutability. - Enums with a mutability, so that a variant can hold something that can be changed without a type parameter, and so that an enum can be changed in place.