Skip to main content

Proofs

lean/ has a proof, in Lean 4, that the core of Bolt's mutability rules keeps its promises. The most important one: nothing reachable from an imm value ever changes, and a well-typed program never gets stuck.

let xs = [1, 2]; // `imm [i32]`
let ys = xs; // another name for the same array, also `imm`
ys[0] = 3; // E0221: rejected, so `xs` can't change through `ys`

The checker rejects the last line. The proof shows that rules like the one behind E0221 are enough: no program that passes them can change an imm array, through any name, however long it runs.

The proof isn't of the checker itself, which is Rust. It's of a small language with the same rules, the model. Each rule of the model is a rule the checker follows, and the pages here say which.

The pages​

  • The model: the small language, and how Bolt's arrays, structs, closures and generics map to it.
  • What's proven: each theorem, with Bolt code that shows what it means for a program.
  • Working on the proofs: building them, how they're organized, and what to do when a rule changes.

Building​

cd lean
lake build --wfail

It uses only Lean's standard library. CI builds it with --wfail, so a warning fails the build, and nothing is left as sorry. The theorems depend only on Lean's standard axioms (propext, Quot.sound and Classical.choice).

The files​

All are in lean/BoltMut/. Each depends only on the ones above it.

FileWhat's in it
Syntax.leanmutabilities, types, expressions, "at most" (AtMost) and what a function assumes (Assume)
Subtyping.leanwhere a type fits in place of another (Sub)
Typing.leanthe typing rules (HasType)
Semantics.leanhow a program runs, and the copy imm e makes (Step, Freeze)
Lemmas.leanweakening, inversion, canonical forms and substitution
Soundness.leanprogress and preservation
Immutability.leanimm values never change
Purity.lean, Frame.leanwhat a call can change
Examples.leanprograms the rules accept and reject
ReadOnly.lean, Literals.leanro literals, and literals whose mutability is inferred
Solver.leanthe shortcuts the checker's solver takes
Least.lean, Principal.lean, Linked.leanthe least type a type parameter can be given, and when there is one
Structs.leanstruct declarations, and which struct types are well-formed
Variance.leanhow a struct's arguments can change
Sharing.leanimm values can be copied or shared
Region.lean, Unique.lean, UniqueCheck.leanimm e without the copy

lean/README.md has a short version of these pages, for reading next to the code.