Level 5 · Research· Lesson 1 of 9 · 45 min
The type theory of ownership
Substructural logics, affine types, regions, and the intellectual lineage of Rust — from linear logic and Cyclone to formal calculi such as Oxide.
Level 5 changes register. The earlier levels taught you to use Rust; this one teaches you to reason about it, in the vocabulary of programming-language research. Each lesson is a guided entry to a body of literature, with the primary sources named so that you can go and read them.
Structural rules
In a conventional type system, the typing context — the set of variables in scope with their types — behaves like a set. Three structural rules make that so:
| Rule | Says | In programming terms |
|---|---|---|
| Exchange | The order of assumptions is irrelevant | Variables may be used in any order |
| Weakening | An assumption may go unused | A variable may be ignored |
| Contraction | An assumption may be used twice | A variable may be duplicated |
A substructural type system drops one or more of them:
| System | Drops | Each variable is used |
|---|---|---|
| Unrestricted (ML, Java) | nothing | any number of times |
| Affine | contraction | at most once |
| Relevant | weakening | at least once |
| Linear | contraction and weakening | exactly once |
| Ordered | all three | exactly once, in order |
These systems descend from Girard’s linear logic (1987), in which hypotheses are resources consumed by the proofs that use them. Wadler’s “Linear types can change the world!” (1990) drew the programming conclusion: if a value has exactly one reference to it, it can be updated in place and freed deterministically, with no garbage collector and no observable aliasing.
Rust is affine
A move is the consumption of an affine resource:
fn consume(s: String) -> usize { s.len() }
fn main() {
let s = String::from("resource");
let n = consume(s); // s is used once: fine
// let m = consume(s); // contraction: ❌ would not compile (use of moved value)
let t = String::from("unused"); // never used again: weakening is allowed
println!("{n}");
}
Three refinements make this practical:
Copytypes are unrestricted.Copyre-enables contraction for types where duplication is harmless. In linear-logic terms it plays the role of the exponential!A.Dropis implicit weakening with an effect. When an affine value is discarded, the compiler inserts its destructor. This is what makes RAII work, and it is why Rust is not linear: the type system cannot force you to callfile.close()and handle its error.- Leaking is permitted.
mem::forgetandRccycles mean even the destructor is not guaranteed. A truly linear type — one that must be consumed explicitly — cannot be expressed, though it can be approximated with#[must_use]and aDropthat panics. Adding real linear or “must-move” types is an open design problem that interacts badly with panics and with every existing generic API.
The problem with pure linearity, and borrowing
A purely linear language is painful: to read a value you must thread it through every function and get it back. Lesson 1.4 showed the shape — fn length(s: String) -> (String, usize).
The literature offers several ways to relax linearity temporarily:
- Wadler’s
let!permitted read-only access within a delimited scope. - Fractional permissions (Boyland, 2003): a full permission can be split into fractions; any fraction allows reading, only the whole allows writing, and fractions can be recombined. This is precisely the logic of
&Tversus&mut T. - Ownership types (Clarke, Potter and Noble, 1998) restricted aliasing structurally in object-oriented languages.
- Regions — below.
Rust’s answer is the borrow: a reference is a non-owning, time-limited capability derived from an owner. During the loan the owner’s rights are suspended (wholly for &mut, partially for &), and they are restored when the loan ends. Formally, &'a mut T is an affine capability to a T valid for region 'a; &'a T is a duplicable (Copy) one.
Reborrowing is what makes mutable references usable despite being affine: passing r: &mut T to a function does not consume r; it creates &mut *r, a sub-loan with a shorter lifetime, and suspends r for its duration.
fn bump(x: &mut i32) { *x += 1; }
fn main() {
let mut v = 0;
let r = &mut v;
bump(r); // implicitly `bump(&mut *r)`: a reborrow, not a move
bump(r); // so `r` is still usable
let moved = r; // an explicit binding to the same type DOES move
bump(moved);
println!("{v}");
}
Regions
Region-based memory management (Tofte and Talpin, 1997) gave every allocation a statically inferred region; all memory in a region is freed together. The type of a pointer names its region, functions are polymorphic over regions, and the type system guarantees no pointer outlives its region.
Cyclone (Jim, Grossman, Morrisett and colleagues, 2002), a safe dialect of C, combined regions with unique pointers and explicit region subtyping (an outlives relation). The relationship to Rust is direct:
| Cyclone / region calculi | Rust |
|---|---|
Region variable ρ |
Lifetime parameter 'a |
| Region polymorphism | Lifetime-generic functions |
Region outlives ρ1 :> ρ2 |
'a: 'b |
| Unique pointers | Box<T>, moves |
| Region subtyping | Variance and lifetime subtyping |
The crucial difference: in the classical work a region is a place where memory is allocated. In Rust a lifetime is the span during which a loan is live. Allocation is governed by ownership instead. That shift — from “where does this live” to “how long is this borrowed” — is Rust’s central design insight, and it is why Rust lifetimes can be inferred within function bodies and need not correspond to any runtime structure.
What the type system proves
The standard formal statement of type safety has two parts (Wright and Felleisen, 1994):
- Progress: a well-typed program is either a value or can take a step — it is never stuck (never reaches undefined behaviour).
- Preservation: if a well-typed program takes a step, the result is well typed.
For Rust, the theorem one wants is stronger and has an unusual shape: a program whose unsafe blocks are encapsulated in sound libraries never exhibits undefined behaviour. A purely syntactic proof cannot handle that, because unsafe code is by definition code the syntactic rules do not check. Lesson 5.6 (RustBelt) shows the semantic technique that does.
Formal models of (parts of) Rust worth knowing:
- Patina (Reed, 2015) — an early formalisation of the borrow checker.
- λRust (RustBelt; Jung et al., POPL 2018) — a continuation-passing core calculus close to MIR, with a machine-checked semantic soundness proof in Coq/Iris that extends to unsafe libraries.
- Oxide (Weiss, Gierczak, Patterson and Ahmed, 2019) — a calculus close to surface Rust in which lifetimes are replaced by provenances: sets of loans a reference may derive from. It presents borrow checking as an ordinary syntactic type system, and its view of regions as sets of loans is the same idea that underlies Polonius.
- FR / KRust / RustSEM / Aeneas’ LLBC — executable or translation-oriented semantics.
- a-mir-formality — the Rust types team’s own in-progress executable model of MIR’s type system, written with the intention of becoming normative.
Parametricity and free theorems
A generic Rust function cannot inspect its type parameter (there is no instanceof, and specialization is unstable). Reynolds’ parametricity then yields “theorems for free” (Wadler, 1989): from the type alone,
fn mystery<T>(x: T) -> T { x }
must be the identity (or diverge or panic), and any fn f<T>(v: Vec<T>) -> Vec<T> can only rearrange, drop or — if T: Clone — duplicate elements; it cannot invent one. Ownership sharpens this: without T: Clone, the result contains each input element at most once. Parametricity is a reason to keep trait bounds minimal, and its interaction with features such as specialization and Any/TypeId (which deliberately break it) is a recurring topic in language design discussions.
Reading list
- Wadler, “Linear types can change the world!” (1990).
- Walker, “Substructural Type Systems”, in Advanced Topics in Types and Programming Languages (2005) — the standard tutorial.
- Tofte and Talpin, “Region-Based Memory Management” (1997).
- Grossman et al., “Region-Based Memory Management in Cyclone” (PLDI 2002).
- Boyland, “Checking Interference with Fractional Permissions” (2003).
- Clarke, Potter and Noble, “Ownership Types for Flexible Alias Protection” (OOPSLA 1998).
- Weiss et al., “Oxide: The Essence of Rust” (2019).
- Jung, Understanding and Evolving the Rust Programming Language (PhD thesis, 2020) — the best single document on Rust’s foundations.
- Pierce, Types and Programming Languages — if progress, preservation and typing judgements are unfamiliar, start here.
Exercises
- Write typing rules (as inference rules, on paper) for a tiny affine lambda calculus with
let, pairs and function application. Show how the context is split between the two premises of application. - Extend it with a
Copykind. Which rule changes? - In Rust, approximate a linear type: a
struct MustClosewhoseDroppanics unlessclose(self)was called. List three ways safe code can still avoid closing it. - Read the Oxide paper’s section on loans and provenances. Explain in your own words how a provenance differs from a lexical lifetime.
- State the free theorem for
fn f<T>(a: T, b: T) -> T. How many distinct total, non-panicking implementations exist?
Check your understanding
Pick an answer to see the explanation.
1.Which structural rule does an *affine* type system reject?
2.Why is Rust described as affine rather than linear?
3.What did region-based memory management (Tofte and Talpin; Cyclone) contribute to Rust?