Rust from First Principles
Rust began as a personal project by Graydon Hoare in 2006, became Mozilla Research-sponsored in 2009, and reached its 1.0 release in May 2015. The language was designed from the outset as a response to the memory safety failures endemic in C and C++: dangling pointers, use-after-free vulnerabilities, and data races that escape detection in large codebases. The stated goal was to deliver the same degree of systems-level control as C, with safety guaranteed by the type system and no need for programmer discipline or a garbage collector. That guarantee follows from a precise mathematical discipline: the type system is a substructural logic, the borrow checker is a constraint solver over region variables, and the async runtime is a state machine over poll-based future types. This post derives each from first principles: the structural rules of logic, the operational semantics of an abstract machine, affine ownership, the Pin invariant, the serde data model and the no_std embedded contract.
1. A Formal Account of Rust
1.1. Memory Safety Failures in C and C++
Memory safety failures in C and C++ are the dominant source of security vulnerabilities across the industry. The NSA/CISA "The Case for Memory Safe Roadmaps" report (2023) documented that approximately 70% of CVEs in major codebases, including those of Microsoft, Google Android, and Chrome, trace to memory safety issues.[1] The canonical failure modes are dangling pointers (accessing memory that has been freed), use-after-free (a specialisation with severe security implications, since freed memory is often reallocated and may contain attacker-controlled data), buffer overflows (reading or writing past the end of an allocation) and data races (two threads accessing the same location concurrently without synchronisation with at least one of them writing).
Consider the minimal C example:
// C: no safety net
char *p = malloc(8);
free(p);
char c = *p; // undefined behaviour: use-after-freeThe C compiler emits this without complaint. The standard calls the behaviour undefined: the compiler may assume it never occurs and optimise under that assumption. This can produce security vulnerabilities absent from a naive reading of the code. There is no runtime check, trap or diagnostic. The programme is wrong and the fault may not manifest until an attacker controls the freed memory.
Rust's type system makes all of these a compile-time impossibility in safe code. The compiler rejects the programme before it runs and adds no runtime overhead. The rest of this post starts from the mathematical structures that underlie the type system.
1.2. Rust among Go and Haskell on the Safety Spectrum
Four languages lie on the spectrum.
C and C++ offer maximum control. Memory management is entirely manual: the programmer allocates, manages and frees every resource. The language enforces no safety. The programmer is responsible for every invariant and decades of CVEs document the failures. C++ adds RAII and smart pointers as conventions that the type system does not enforce.
Go achieves safety through a garbage collector and a runtime scheduler. There is no manual memory management and no dangling pointer, because the collector never frees memory while a reference to it remains live. The price is a hidden runtime: a garbage collector with non-deterministic pauses, a memory model that gives no control over allocation layout and an M:N green thread scheduler between the programme and the OS. Go gives up control for simplicity.
Haskell achieves safety through purity and a strong type system. The IO monad separates effectful computation from pure computation, and lazy evaluation means values are only computed when demanded. There is no mutable state by default, which eliminates entire classes of error. The runtime has a garbage collector, memory layout is out of the programmer's hands and lazy evaluation makes performance reasoning subtle. Haskell suits correct programmes and was not designed to control hardware.
Rust offers safety and control together. There is no garbage collector, runtime scheduler or hidden allocation. The type system enforces safety entirely at compile time and the programmer controls memory layout and execution order. The type system in turn demands more of the programmer.
The spectrum runs from "enforce nothing at the language level" (C) through "enforce at runtime via a collector and a scheduler" (Go) to "enforce at compile time via a type system" (Rust, Haskell). Only Rust combines compile-time enforcement with zero runtime overhead.
1.3. Operational Meaning of Safety
The word "safe" needs a precise definition.
A language implementation is memory-safe if it guarantees, for all well-typed programmes, that: (1) no read occurs from uninitialised memory, (2) no pointer is dereferenced after the pointee's lifetime has ended, and (3) no two threads access the same memory location concurrently without synchronisation while at least one of them writes.
Rust's type system provides all three guarantees in safe code. The compiler requires definite assignment before use. Uninitialised memory therefore cannot be read. The borrow checker confines every reference's lifetime to the lifetime of the referent and thereby excludes dereferencing a dangling pointer. The type system separates exclusive mutable access () from shared read-only access () and never lets a mutable reference coexist with another reference to the same data. Together with the Send and Sync traits this rules out data races.
The unsafe keyword creates a bounded region in which the programmer re-assumes the proof obligation for memory safety. It leaves the borrow checker on and grants five additional capabilities: dereferencing raw pointers, calling unsafe functions, accessing or modifying mutable statics, implementing unsafe traits and reading fields of unions. The unsafety is local and auditable. Every unsafe block is a claim by the programmer that the invariants are true by reasoning outside the type system. A reviewer can check that claim in isolation.
2. Type System as a Logic
2.1. Substructural Logics
Classical propositional logic has three structural rules in addition to its logical axioms. Weakening permits unused hypotheses: from a proof of using hypothesis set we may conclude in any larger context even if is never used. Contraction permits hypotheses to be duplicated: if we can prove with two copies of then one copy suffices because we can always make two. Exchange permits hypotheses to be reordered freely. Together these rules make hypotheses behave like timeless facts: free, copyable and order-independent.
Substructural logics drop one or more of these rules and so can reason about resources. A resource is consumed by use, cannot be freely duplicated and may be order-sensitive.
Linear logic (Girard, 1987)[3] drops both weakening and contraction. Every hypothesis must be used exactly once. The connectives split into two families: multiplicatives (, ) for combining resources that coexist and additives (, ) for choosing between resources. A proof in linear logic describes how resources flow through a computation. No resource is created or destroyed outside the explicit rules.
Affine logic drops contraction but retains weakening. Every hypothesis is used at most once: it may be discarded (weakening is permitted) and may not be duplicated (contraction is forbidden). Affine logic models resources that can be abandoned and cannot be copied.
Relevant logic drops weakening but retains contraction. Every hypothesis must be used at least once: it cannot be ignored and may be used repeatedly. Relevant logic models resources that must be accounted for and are inexhaustible once present.
| Logic | Weakening | Contraction | Use constraint |
|---|---|---|---|
| Linear | No | No | Exactly once |
| Affine | Yes | No | At most once |
| Relevant | No | Yes | At least once |
| Classical | Yes | Yes | Any number |
Rust ownership lies in the affine row: values may be dropped (weakening) and may not be duplicated (no contraction). The Copy trait restores contraction for a class of types and returns them to classical behaviour.
2.2. Ownership as Affine Types
Every Rust value has exactly one owner at any point in time. When a non-Copy value is assigned to a new binding or passed to a function, ownership is moved: the source binding becomes inaccessible and the compiler rejects any later use of it. The value is dropped and its memory freed when the owner's scope ends. Ownership is thus the affine discipline in a systems language: every value is consumed at most once as an owner. It can be borrowed any number of times but a move is a one-way transfer.
Rust ownership is the affine fragment of linear logic in a systems programming language. The "consumption" of a value corresponds to its eventual deallocation. Moving a value consumes the affine resource. Dropping a value (letting it go out of scope without moving it) is weakening: the resource is abandoned.
In C++ std::unique_ptr approximates affine ownership through RAII and a deleted copy constructor: only one pointer owns the heap allocation at a time and the destructor runs exactly once. The class interface enforces this invariant by convention and the type system does not. A programmer can std::move a unique_ptr incorrectly, pass elsewhere a raw pointer extracted from it, or violate uniqueness in ways that no static analysis catches without specialised tooling. Rust enforces these constraints statically for every heap-allocated type in safe code.
Copy types (integers, booleans, , fixed-size arrays of Copy types) are exempt from the affine discipline. They implement the Copy trait, which tells the compiler that bitwise duplication is semantically sound. Assignment copies.
2.3. Curry-Howard Correspondence
The Curry-Howard correspondence (Howard, 1980)[4] identifies propositions with types and proofs with programmes. A function of type is a programme that maps values of type to values of type and also a proof that the proposition implies the proposition : applying the function to a proof (value) of yields a proof (value) of .
The correspondence extends to the logical connectives. Products (, encoded as structs in Rust) correspond to conjunction: a value of type is a proof of both and . Coproducts (, encoded as enums) correspond to disjunction: a value of type enum E { Left(A), Right(B) } is a proof of with the witness for whichever disjunct holds. The unit type () has exactly one value and corresponds to the trivially true proposition. The empty type ! (Rust's "never" type) has no values and corresponds to falsehood: from a value of type ! any type can be produced, the Curry-Howard image of ex falso quodlibet.
A value of an affine type is a proof of an affine proposition, one that can be used at most once. Moving the value uses the proof. The linear logic connectives govern how resources flow through the programme and the type checker's enforcement of ownership is the proof-checker's enforcement of the proof rules.
The ? operator in Rust (early return on Err) is the Curry-Howard image of the disjunction elimination rule with a fixed error channel. Given a value of type Result<T, E> (a proof of ) it either extracts the T (the left disjunct is true) or returns from the enclosing function with the E (the right disjunct is true and control exits immediately). The Try trait abstracts the desugaring.
2.4. Haskell LinearTypes and Rust Ownership
GHC 9.0 introduced the LinearTypes extension,[5] which adds multiplicity-annotated function arrows to Haskell: means the function consumes its argument exactly once (the linear arrow) and means it may consume the argument any number of times (the ordinary arrow). This realises linear logic directly in a mature production language and gives Haskell the same kind of resource-tracking guarantees in annotated code.
The systems differ in their defaults. In Haskell linearity is an opt-in annotation on function types in a language whose default is classical: values can be used any number of times and the programmer opts into linear discipline where precision is needed. The type checker enforces multiplicity constraints within annotated functions and the surrounding ecosystem is unaffected. In Rust affine ownership is the default for every non-Copy type. The programmer opts out by deriving Copy or calling .clone() explicitly. The burden of proof runs in opposite directions.
Both systems instantiate the same mathematical structure in a production compiler: the affine (Rust) and linear (Haskell LinearTypes) fragments of linear logic. Rust prioritises safety by default in a systems context where an accidental copy or use-after-free shows up as a security vulnerability. Haskell prioritises expressiveness and treats linearity as a precision tool because its primary concern is the correctness of functional programmes.
2.5. RustCell Use-After-Move Rejection
The compiler enforces the affine discipline on every non-Copy type. The following programme is rejected at compile time because s is moved into _t on the second line and the affine resource is consumed. The third line uses a resource that no longer exists.
fn main() {
let s = String::from("hello");
let _t = s; // s is moved into _t
println!("{s}"); // error[E0382]: borrow of moved value: `s`
}Affine enforcement through a move that makes s unavailable at its use site
The error message is error[E0382]: borrow of moved value: s. The compiler's dataflow analysis tracks ownership through every control-flow path and reports the exact location where the already-moved value is used. C and C++ have no analogous check. In Go and Java values are garbage-collected and can be used freely after assignment. Only a language with an affine type system produces this rejection and it adds no runtime overhead.
3. Lifetimes and the Region Calculus
3.1. Region Variables and Constraints
Every reference in Rust has a lifetime annotation, written 'a, 'b and so on. A lifetime is a region variable: it stands for a span of the programme's execution during which a reference is valid. The borrow checker is a constraint solver that generates and discharges a system of lifetime constraints. It reasons statically about spans of validity, represented as sets of programme points, and checks at compile time that no reference is used outside its span. A garbage collector tracks individual heap addresses at runtime and the borrow checker has no such need.
A lifetime 'a is a region variable denoting a set of programme points. A reference &'a T is valid precisely at the programme points in 'a. The outlives relation 'a: 'b (read: 'a outlives 'b) means every programme point in 'b is also in 'a: formally, .
For a programme to be accepted by the borrow checker, the compiler generates a set of constraints of the form 'a: 'b (region inclusion) and 'a ⊇ live(x) (the lifetime must cover the live range of value x). The borrow checker is satisfied when all constraints have a simultaneous solution under the subset partial order on regions.
The compiler solves this system by least fixed-point iteration: each region starts at the empty set and grows by union until a fixed point is reached. The minimal region satisfying all constraints gives each borrow the shortest possible live range. This accepts the largest set of well-formed programmes and rejects only those for which no valid assignment of regions exists. The Non-Lexical Lifetimes RFC (RFC 2094) formalised this construction.[6]
3.2. Non-Lexical Lifetimes and the Borrow Checker as Constraint Solver
Before NLL (pre-Rust 2018 edition) lifetimes were lexically scoped: a borrow lasted until the end of the enclosing block even if the borrowed value was unused after an earlier point in that block. This produced spurious rejections of sound programmes: the lexical lifetime of a borrow overlapped with a later operation that the compiler conservatively refused. NLL, stabilised in Rust 2018 via RFC 2094,[6] eliminates these false positives by computing lifetimes as the liveness of the borrow. A region is the set of programme points at which the reference may be used.
Formally, NLL computes liveness on the control-flow graph (CFG) of the function's MIR (mid-level intermediate representation). MIR is a simplified, explicitly typed IR produced after desugaring and type checking, with explicit basic blocks and explicit borrow annotations. A reference is live at a programme point if there exists a path from that point to a future use of the reference. The borrow checker then checks for each pair of potentially conflicting borrows that their regions do not overlap at any programme point. Mutable and shared borrows conflict if they alias the same memory. Two mutable borrows conflict unconditionally if they alias.
If the NLL borrow checker accepts a programme, then no two simultaneously live borrows alias the same memory with at least one being mutable. Jung et al. (POPL 2018)[7] prove the corresponding guarantee for λRust, a core calculus with Rust's ownership and lifetime discipline, in the RustBelt framework via a separation logic model in which the ownership discipline is an invariant on the resource algebra. No machine-checked proof covers rustc's NLL implementation itself.
The borrow checker is thus a dataflow analysis over the programme's CFG that computes the minimal region assignments satisfying all constraints. When it rejects a programme the constraints have no solution.
3.3. Variance
Subtyping for lifetimes is induced by the outlives relation: if 'a outlives 'b, written 'a: 'b, then &'a T is a subtype of &'b T, because a reference valid for the longer span is valid for the shorter one. The way the subtyping of a type constructor depends on the subtyping of its parameters is its variance.
A type constructor is covariant in a parameter if implies ; contravariant if the ordering reverses ( implies ); and invariant if neither implication holds in general. For lifetimes, the subtyping order is defined by the outlives relation: 'a: 'b.
The compiler determines the variance of Rust's built-in type constructors from their structure:
| Type | Variance in lifetime 'a | Variance in T |
|---|---|---|
&'a T | covariant | covariant |
&'a mut T | covariant | invariant |
*const T | n/a | covariant |
*mut T | n/a | invariant |
fn(T) -> U | n/a | contravariant in T, covariant in U |
Cell<T> | n/a | invariant |
The invariance of &'a mut T in T is non-obvious. Suppose &'a mut T were covariant in T. Then a &'a mut &'static str could be used where a &'a mut &'b str is expected with 'b shorter than 'static. Through the &'a mut &'b str reference one could write a short-lived 'b string slice into the slot. The slot was originally typed as &'static str and any code with the original &'a mut &'static str would read back a reference it believes to be 'static and which is only 'b. The Rustonomicon gives this as the canonical variance example.[16] Covariance for mutable references would let lifetimes shrink through indirection and produce dangling references.
3.4. Go Escape Analysis and Rust Static Lifetimes
Go achieves the same guarantee (no dangling pointers, no use-after-free) by escape analysis and a tracing garbage collector. The Go compiler determines at compile time whether a value's address escapes its allocating function. If it does the value is heap-allocated and the collector manages its lifetime. Otherwise the value lives on the stack and is reclaimed when the function returns.
The two approaches differ in where the work happens. Go needs no lifetime variables or borrow checker constraints and the programmer need not reason about validity spans. The work moves to runtime. The garbage collector traces the live heap concurrently with the programme and pauses all goroutines briefly (the stop-the-world phases) at the start and end of each marking cycle. Even with a low-latency collector the pause times are non-deterministic. Escape analysis is also conservative: values may be heap-allocated when stack allocation was possible and the programmer has no recourse. Memory layout is opaque to the programmer.
Rust does all of this work at compile time. The borrow checker verifies every lifetime constraint before the programme runs. At runtime there is no collector, no scheduler overhead from GC cooperation points and no hidden allocation. The programmer provides lifetime annotations where necessary to help the constraint solver. These annotations are checkable evidence and not comments. Both approaches are sound: neither permits dangling pointer dereferences in code written to the respective language's safety rules. They differ on three axes: annotation burden (Rust: higher), runtime overhead (Go: higher) and control over memory layout (Rust: complete, Go: limited).
3.5. RustCell Dangling Reference Rejection
The lifetime constraint system rejects programmes where a reference would outlive its referent. In the canonical form a function returns a reference to a local variable that is dropped at the end of the function's scope. The returned reference's lifetime cannot be satisfied because the referent does not outlive the function call. The compiler rejects the programme with a missing lifetime specifier error.
fn first_word(s: &str) -> &str {
&s[..s.find(' ').unwrap_or(s.len())]
}
fn dangle() -> &str { // error[E0106]: missing lifetime specifier
let s = String::from("hello world");
first_word(&s) // s is dropped at end of this scope
} // but the returned reference would outlive it
fn main() {
println!("{}", dangle());
}Lifetime constraint violated by a returned reference that outlives its referent
No lifetime annotation makes this programme well-typed. The local variable s ends its life when dangle returns and the return type &str must outlive the call site. The constraint has no solution. In C the analogous code compiles without warning and produces a dangling pointer at runtime.
4. Operational Semantics and the MiniRust Model
4.1. Small-Step Operational Semantics
Type systems give a static account of what programmes are: they classify expressions into types and enforce structural invariants. Operational semantics gives a dynamic account of what programmes do by describing step-by-step execution on an abstract machine. The standard tool is a small-step reduction relation on configurations, where each step models one primitive computation. An execution is a sequence of configurations linked by reduction steps that ends in a final value or diverges.
A MiniRust configuration is a triple where is the heap (a partial function from addresses to typed values), is the call stack (a list of frames, each a partial function from variable names to addresses), and is the expression currently being evaluated. MiniRust is the formal operational model for Rust developed by Ralf Jung[17] as a proposed reference for what Rust programmes mean. It is not yet an official specification.
Three reduction rules show how ownership manifests operationally. Variable lookup is : x is resolved by looking up its address in the top stack frame and retrieving the value at that address from the heap. A move of the value of variable x into variable y removes the entry for x from the current frame and creates a new entry for y. The heap cell at x's address is marked invalid (or the entry is removed from the frame's domain) so any later lookup of x is an error. The move rule is the operational form of the affine discipline: the move is a one-way transfer and the source is invalidated. When a variable goes out of scope the drop rule calls the value's destructor (Drop::drop), frees the memory at the variable's address and removes the frame entry. Reclamation is deterministic and immediate.
For any well-typed λRust configuration , either is a value (progress: evaluation has reached a final result), or there exists a configuration such that and is well-typed (preservation: the reduction step produces a configuration that satisfies the type invariants). Jung et al. (POPL 2018)[7] prove the corresponding safety theorem for λRust in Coq: well-typed programmes do not get stuck. Their proof is semantic. It builds a logical-relations model in the Iris separation logic and has no syntactic progress and preservation lemmas. λRust covers a substantial fragment of safe Rust. MiniRust[17] is a later and separate project designed as a complete operational specification. The RustBelt proof is for the λRust core calculus.
The formal model of Rust's operational semantics is the specification against which compiler optimisations are judged: an optimisation is valid if and only if it preserves the observable behaviour of every programme under the abstract machine's semantics. Without a formal model the boundary between defined and undefined behaviour is informal and contested.
4.2. Stacked Borrows Aliasing Discipline
The borrow checker enforces a static aliasing discipline at compile time. The permissible aliasing patterns also have an operational answer: the programmer can write unsafe code that bypasses the borrow checker. What invariant must hold at runtime for that code to be well-defined? Stacked Borrows, developed by Jung et al. (POPL 2020),[8] provides this operational model. It defines for each memory location a dynamic invariant that tracks the current aliasing state. The Miri interpreter implements it and detects violations on actual executions.
Each memory location maintains a borrow stack: an ordered list of items, each being either a Unique tag (representing a live mutable reference to that location) or a SharedReadOnly tag (representing a live shared reference). When a mutable reference is created, a new Unique tag is pushed onto the stack. When that reference is written through, all items above it are invalidated (popped) because the write asserts exclusive ownership of the location at that point. A read through it pops only the Unique items above it. When a shared reference is created, a SharedReadOnly tag is pushed above the existing Unique tag. A later write through the Unique tag pops the SharedReadOnly items above it. The write itself is permitted. Any later use of the popped shared reference is undefined behaviour.
This model formalises the intuition behind the borrow checker's rules. Two simultaneous mutable borrows of one owner are unsound because creating the second is an access through the owner's tag. That access pops the first borrow's Unique tag. Any later use of the first borrow is undefined behaviour and Miri reports it. The operational model makes the violation detectable on actual executions and complements the static check.
C++ has a strict aliasing rule: objects of distinct types may not alias the same memory (with explicit exceptions such as char and std::byte). Violations are undefined behaviour but only the abstract machine model enforces the rule and compilers may assume it holds when optimising. C++ has no runtime enforcement mechanism analogous to Stacked Borrows and no standard tool equivalent to Miri. Stacked Borrows is therefore a more precise and operationally checkable aliasing discipline than C++'s strict aliasing rule.
4.3. Undefined Behaviour as a Semantic Gap
Undefined behaviour is routinely misunderstood. A programme crash and an error report are two of many possible outcomes and neither is guaranteed. Undefined behaviour means an execution to which the abstract machine's semantics assigns no defined meaning.
Undefined behaviour (UB) is any execution that falls outside the domain of the abstract machine's semantics. The compiler may assume that UB never occurs in a well-formed programme. Any code path that would lead to UB may therefore be pruned, reordered or transformed in ways that are locally sound under the no-UB assumption and globally surprising. UB produces no trap, signal or diagnostic. The programme's execution has no defined meaning from the point of UB onwards.
Rust's UB surface in safe code is minimal. The Rust Reference[2] gives a non-exhaustive list of the sources. It includes data races (concurrent unsynchronised accesses to the same location with at least one write), dereferencing a null or dangling raw pointer, violating the pointer aliasing rules (not yet settled in the Reference; Miri checks the candidate Stacked Borrows model), producing a value of an invalid type via transmute or pointer arithmetic (for instance a bool with a bit pattern other than 0 or 1) and calling a function with the wrong call ABI. In safe code the type system prevents all of these: raw pointers cannot be dereferenced without unsafe, the Send and Sync traits prevent data races and transmute is an unsafe function.
C++ has a much larger UB catalogue: signed integer overflow, shifting by a negative amount or by at least the operand's bit width, reading from uninitialised memory (any variable not explicitly initialised), violations of the strict aliasing rule, null pointer dereference, out-of-bounds pointer arithmetic (even with no dereference), lifetime extension violations through incorrect use of references and many corner cases in the object model. Many C++ programmes contain latent UB that current compiler behaviour masks and a future optimisation may expose. Rust confines UB to unsafe blocks. Integer overflow in debug builds panics and in release builds wraps by definition. A programme with no unsafe blocks has a UB surface that is empty for the correctness invariants that matter most in practice.
4.4. RustCell Rejection of Two Simultaneous Mutable Borrows
Exclusive mutable access is a theorem of the type system: no well-typed safe Rust programme has two simultaneously live mutable references aliasing the same location. The following programme violates this constraint and is rejected at compile time.
fn main() {
let mut v = vec![1, 2, 3];
let r1 = &mut v;
let r2 = &mut v; // error[E0499]: cannot borrow `v` as mutable more than once
r1.push(4);
r2.push(5);
}Borrow-checker rejection of two simultaneous mutable borrows of v
The compiler reports error[E0499]: cannot borrow . The NLL analysis finds v as mutable more than once at a timer1 live where r2 is created (because r1 is used on the line after r2's creation) so the regions of the two borrows overlap and violate the constraint that no two mutable borrows alias simultaneously. In the Stacked Borrows model creating r2 from v pops r1's Unique tag. The call r1.push(4) then uses a tag that is no longer on the stack. That is undefined behaviour. The borrow checker catches this statically before any code runs.
5. Type-Class Semantics of Traits and Generics
5.1. Traits as Bounded Universal Quantification
A trait bound T: Trait expresses bounded universal quantification: for all types T satisfying the Trait interface. The bound is a formal statement about the set of types that may be substituted at a call site. The compiler enforces it by requiring a proof of satisfaction, an impl block, before accepting the substitution.
A trait defines an interface: a set of associated types and method signatures. Formally, a trait is a record of typed declarations where each is a type scheme that may mention Self (the implementing type) and the associated types of . Wadler and Blott compile a Haskell type class to the same structure: a record of methods, the dictionary, passed as an extra argument to each overloaded function.[9]
A trait bound T: Trait is a bounded universal quantification over all types T that possess an implementation of Trait. An impl Trait for Type block is a witness: it provides definitions for every method and associated type declared by Trait, and the compiler accepts it as proof that Type satisfies the bound. A generic function fn f<T: Trait>(...) is a function parametrised over all types T for which such a witness exists.
Coherence is the property that at most one impl exists per (trait, type) pair in a compiled programme. It excludes conflicting implementations from different crates, which would make trait dispatch ambiguous. The orphan rule enforces coherence at the crate boundary: an impl Trait for Type is permitted only if at least one of Trait or Type is defined in the current crate. A crate that defines neither may not provide an impl between them. A unique crate therefore determines the set of impls for any (trait, type) pair and no two crates can conflict.
5.2. Monomorphisation and Dynamic Dispatch
Generic functions over trait bounds are compiled by monomorphisation: the compiler emits one specialised copy of the function for each type that appears at a call site. The machine code is identical to hand-written specialised code and adds no abstraction penalty at runtime.
A dyn Trait value is a fat pointer: a pair of a data pointer (pointing to the value) and a vtable pointer (pointing to a statically allocated table of function pointers). The vtable contains the underlying type's drop glue, size and alignment and one function pointer per method of Trait in a fixed order. Calling a method through dyn Trait loads the function pointer from the vtable and calls it. C++ virtual dispatch uses a table of the same kind and stores its pointer inside the object. The overhead per call is one load and one indirect call. The indirect branch may be mispredicted and the callee cannot be inlined.
Rust makes the dispatch choice explicit in the type. A bound T: Trait or an argument-position impl Trait in a function signature produces static dispatch via monomorphisation. A dyn Trait type produces dynamic dispatch via a fat pointer and vtable. C++ has the same distinction (templates for static, virtual for dynamic) and does not encode it in the type: the programmer must remember to mark methods as virtual and callers cannot see which regime applies. Go interfaces are always dynamically dispatched: every interface value is a fat pointer and static dispatch cannot be requested. Rust's encoding exposes the runtime overhead at the type level.
5.3. Higher-Kinded Patterns via GATs
Generic Associated Types (GATs, stabilised in Rust 1.65) allow type constructors as associated items in a trait. This enables higher-kinded patterns without first-class higher-kinded types (HKT) in the language. The canonical example is a lending iterator, which yields items whose lifetimes are tied to the borrowing of the iterator itself:
trait LendingIterator {
type Item<'a> where Self: 'a;
fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}Here Item is a type constructor parametrised by a lifetime 'a. Without GATs this pattern cannot be expressed because the associated type cannot depend on a lifetime introduced at the method level. With GATs the trait can express that the item borrows from the iterator and so allows zero-copy iteration over data structures without heap allocation.
Rust has no first-class HKT. The kind * -> * required to abstract over a type constructor F uniformly is not representable in the trait system. GATs are a targeted workaround for the patterns that arise most often (lifetime-parametrised and type-parametrised associated types) and avoid the full complexity of a higher-kinded type system.
5.4. Haskell Type Classes and Go Interfaces
Three systems address ad-hoc polymorphism in different ways.
Haskell type classes are nominal: a type must be declared an instance of a class to use class methods with that type. Resolution is at compile time by default (dictionary-passing style: the compiler selects and threads the appropriate dictionary implicitly and each method call dispatches through the dictionary at runtime). Haskell has first-class HKT: Functor f and Monad m range over type constructors of kind * -> *. Rust cannot express the Functor abstraction directly because its trait system lacks the kind * -> *. Haskell's coherence is weaker: orphan instances (instances defined in a module that owns neither the class nor the type) are permitted with a warning and silent priority issues can arise when two libraries define conflicting orphan instances that a third library combines.
Go interfaces use structural typing. A type implicitly satisfies an interface if it provides the required methods with no explicit declaration. There is no impl block and no orphan rule. Every interface value is dynamically dispatched via a fat pointer and static dispatch is unavailable. Go interfaces are simpler to use and impose the vtable overhead on all interface abstraction.
Rust traits are nominal (explicit impl required), static by default (monomorphised) and dynamic on explicit opt-in (dyn Trait). The coherence and orphan rules keep conflicting impls out of a linked programme: any conflict is a compile-time error in the crate that introduces it. Rust thus detects conflicting implementations at compile time, Haskell defers to linking and convention, and Go avoids the problem with structural typing and no global coherence to maintain.
5.5. RustCell Static and Dynamic Dispatch
The following programme uses the Display trait by two paths: a generic function monomorphised at each call site and a function that accepts a dyn Display fat pointer. Both print the same output. The compiler emits two specialised copies of print_static (one for i32, one for &str) and one copy of print_dynamic that dispatches via the vtable at runtime.
use std::fmt::Display;
// Static dispatch: monomorphised, zero-cost
fn print_static<T: Display>(val: T) {
println!("static: {val}");
}
// Dynamic dispatch: fat pointer + vtable
fn print_dynamic(val: &dyn Display) {
println!("dynamic: {val}");
}
fn main() {
print_static(42_i32);
print_static("hello");
print_dynamic(&42_i32);
print_dynamic(&"hello");
}Static dispatch by monomorphisation and dynamic dispatch by vtable pointer behind one interface
6. Categorical Structures
Sections 2 and 3 showed that Rust's type system is a substructural logic and that lifetimes are region variables in a constraint system. Category theory states these structures precisely and makes their connections derivable. The objects of the type category are types, the morphisms are functions, composition is function composition and the identity morphism at each type is the identity function. Every design decision in Rust's standard library that governs how types compose has an exact categorical explanation: why match must cover all constructors, why fold is the canonical operation on recursive types, why Iterator::zip and futures::future::join have different semantics from and_then and why Copy is a separate trait. The subsections below treat initial algebras for ADTs (§6.1), terminal coalgebras for iterators (§6.2), natural transformations and parametricity for generic APIs (§6.3), the Kleisli category for the ? operator and async/await (§6.4), and symmetric monoidal categories for the ownership discipline (§6.5).
6.1. ADTs as Initial Algebras
Algebraic data types have a precise categorical interpretation as initial algebras of polynomial functors. A polynomial functor is built from constants, the identity, products and coproducts. Its initial algebra is up to isomorphism the least fixed point: the smallest type closed under the functor's constructors with a unique structure-preserving map (a fold) to any other algebra of the same functor. The compiler's requirement that match be exhaustive and that every ADT have a finite case analysis states that the programmer is constructing the unique catamorphism out of an initial algebra.
Let be a functor. An -algebra is a pair where is a set and is the structure map. The initial -algebra is the algebra such that for every -algebra there exists a unique algebra homomorphism (catamorphism) .[11]
Thus Option<T> is the initial algebra of the functor , the coproduct of the unit type and a fixed type . Its least fixed point is None | Some(T): a value is either nothing (the summand) or a wrapped value (the summand). Likewise Result<T, E> is the initial algebra of , the coproduct of and . Both are non-recursive so their least fixed point is the type itself. The framework matters most for recursive types such as List<T>, where the fixed-point computation is non-trivial. Structs are products of their field types (record types, the categorical product). Enums are coproducts of their variant types (sum types, the categorical coproduct).
Pattern matching on an ADT is the unique fold (catamorphism) out of its initial algebra. A match expression on Option<T> that provides a branch for None and a branch for Some(v) is the unique -algebra homomorphism from to the result type. The existence and uniqueness of this homomorphism is the universal property of the initial algebra. Exhaustive pattern matching is thus a categorical necessity: to consume an initial algebra one must provide exactly one handler per constructor.
The structure map of the initial -algebra is an isomorphism. Its inverse is the unique catamorphism from to the algebra .
Proof. The pair is an -algebra with structure map . By initiality of there exists a unique -algebra homomorphism , satisfying the homomorphism condition
where the second equality is functoriality of .
Step 2 (). An -algebra endomorphism must satisfy . For :
where the last equality uses [eq:out-hom]. So is an -algebra endomorphism. Since is also one, initiality (which asserts a unique homomorphism from to any algebra) forces .
Step 3 (). Applying [eq:out-hom] and the result of Step 2:
Both compositions are identities, so is an isomorphism with two-sided inverse . □
Lambek's lemma says that every recursive type can be unrolled one step without loss of information. The list functor makes this precise: its initial algebra has structure map sending the left summand to Nil and the right summand to Cons(n, xs), while is the inverse operation that peels off the outermost constructor. One checks directly and for any . Hence . The reverse, , follows by equation [eq:out-hom] and the Step 2 uniqueness argument. The isomorphism for is the fold and unfold of a linked list: every list is either empty or a head-tail pair and the decomposition is lossless and invertible. For Option<T> (a non-recursive fixed point where is true by type isomorphism) the result is immediate. In the recursive case Lambek's lemma gives the one-step decomposition that structural recursion uses. Termination comes from initiality: in every element of is built by finitely many applications of . Each recursive call on a subterm exposed by therefore descends a well-founded order. The dual statement is that the observation map of the terminal -coalgebra is also an isomorphism. The stream type from §6.2 satisfies this and so coinductive proofs over streams are permitted: each proof step applies once to observe one element and the process continues productively.
6.2. Iterator as a Coalgebra
ADTs are initial algebras (inductive, built up from constructors) and iterators are coalgebras (coinductive, torn apart by destructors). A coalgebra of a functor is a pair where is the state space and is the observation map.
The Rust Iterator trait is a coalgebra of the functor . The state type is Self. The observation map is fn next(&mut self) -> Option<Self::Item>, which takes the current state and either produces a pair of an item and the next state (wrapped in Some) or signals exhaustion by returning None. This is the stream coalgebra: a potentially infinite sequence torn down one element at a time.[11]
Haskell lazy lists are also a coalgebra of the same functor but are memoised via thunks: each unevaluated tail is a heap-allocated closure and a lazy spine allocates a heap cell for each element it produces unless list fusion removes the intermediate list. Rust iterators add no runtime overhead: the compiler keeps the iterator state in registers or on the stack and compiles the adapter chain to a single tight loop with no allocation. The coalgebraic structure is the same and the operational overhead differs.
6.3. Natural Transformations and Parametricity
A natural transformation between functors is a family of morphisms , one for each object in , satisfying the naturality condition: for every morphism in ,
In Rust, any fully parametric function of type for functor-shaped generic types is a natural transformation, by Reynolds's parametricity theorem.[10] The naturality condition is a free theorem and needs no proof obligation. A generic function cannot inspect through its values. Safe Rust still has type-level escape hatches: std::mem::size_of::<T>() and std::any::type_name::<T>() need no bound and TypeId::of::<T>() needs only T: 'static. A function that branches on one of them, reads global state or panics can break naturality.
Let and be functor-shaped generic types with map implementations satisfying the functor laws. Any function of type that does not use unsafe, type inspection (TypeId, type_name, size_of and similar), global state or panics satisfies the naturality square [eq:naturality-square] for all functions .
Proof. Fix . Define the graph relation by . Reynolds's abstraction theorem assigns a relation to each type constructor by structural induction on the type. For a covariant functor the relational lifting is
The abstraction theorem states that any parametric term of type preserves these relations: if then .
Instantiate with and , which satisfies by definition. Relation preservation gives , which unpacks to . Since was arbitrary, this is [eq:naturality-square] at every point of .
The exclusions are necessary: std::any::TypeId::of::<T>() observes the identity of at runtime and invalidates the relational interpretation. A term branching on can map to and to via different code paths and so break relation preservation. The same holds for size_of and type_name, both safe and unbounded. Under the exclusions [eq:naturality-square] holds for all terms of the stated type. □
The parametric endomorphisms of Option<T> in safe Rust are exactly two: the identity (pass through every value unchanged) and the constant-None map (discard any value). These are the only candidates up to naturality: the identity satisfies [eq:naturality-square] trivially and const None satisfies it because both sides of the square evaluate to None regardless of . No third parametric endomorphism exists because producing a Some from a None would require a value of an unknown type , which safe Rust cannot construct. Parametricity thus classifies the natural transformations between common generic types completely.
The functor laws for Option::map are: identity, , and composition, . These are semantic invariants that the compiler does not verify. A map implementation violating either behaves unexpectedly when composed with generic adapters that depend on them.
The monad unit (defined as Some) and the multiplication (defined as flatten, i.e., opt.and_then(|x| x)) are both natural transformations. One verifies directly from the definition: flatten does not inspect the value of so the order in which map and flatten are applied is irrelevant. A case analysis on None and Some gives the unit laws and the associativity law . Thus is a monad in the categorical sense: a monoid in the monoidal category of endofunctors on with multiplication and unit .
6.4. Kleisli Category
Given a monad on a category , the Kleisli category has the same objects as and morphisms defined as maps in . The identity morphism at is the unit , and Kleisli composition of with is
The monad laws are exactly the category axioms for : left identity (), right identity () and associativity (). In Rust these read f(a).and_then(Ok) == f(a) (left identity), Ok(a).and_then(f) == f(a) (right identity) and (f(a).and_then(g)).and_then(h) == f(a).and_then(|b| g(b).and_then(h)) (associativity). Haskell names the two identity laws the other way round, after the side of >>= on which return appears.
For , a Kleisli morphism is a fallible computation . The ? operator chains such morphisms via Kleisli composition: a sequence of ?-terminated expressions is an unambiguous morphism in and the associativity law makes the chain's result independent of how it is parenthesised. The programmer works in a well-defined category whose composition law captures the intended semantics.
The async case is analogous. A morphism is a function returning impl Future<Output = B>. Kleisli composition is sequenced .await: the state machine generated by the compiler (§7.1) is this composition at the level of the abstract machine: each await point is a Kleisli composition step in the implicit Future monad. Rust lacks higher-kinded types (§5.3) so this monad cannot be named at the type level. Its operational structure (identity, sequencing, associativity) is fully present.
6.5. Symmetric Monoidal Categories and Linear Types
The structural rules of substructural logic (§2.1) correspond precisely to properties of the monoidal structure on the type category. A symmetric monoidal category equips a category with a bifunctor , a unit object , coherence isomorphisms , , , and a symmetry satisfying Mac Lane's pentagon, triangle and hexagon coherence conditions and .
The affine fragment of Rust's type system forms a symmetric monoidal category in which objects are types, morphisms are move-consuming functions, the tensor product is the pair type , the unit is , and the symmetry is the swap isomorphism . The affine discipline corresponds to the presence of discard maps (the drop function) for every type and the absence of diagonal maps for non-Copy types.
The distinction between Copy and non-Copy types is categorical. The Copy trait identifies a full sub-category in which the diagonal map exists for every object. The monoidal structure is therefore cartesian on this sub-category. A cartesian monoidal category has the categorical product as tensor product with projection maps. Primitive scalars and types composed entirely of them are the example. Outside for types owning heap resources, file descriptors or locked mutexes no diagonal exists. The borrow checker enforces this at compile time: the morphism does not typecheck.
A lax monoidal functor from to consists of a functor equipped with a natural transformation and a unit map , subject to associativity and unit coherence conditions. Lax monoidal functors are the categorical signature of the Applicative type class: an applicative functor is a lax monoidal functor. In Rust Iterator::zip witnesses the lax monoidal structure of the iterator functor: the transformation combines two independent iterators into an iterator of pairs with no causal ordering. futures::future::join is the analogous structure for the Future functor: two independent futures may execute concurrently and their results are combined once both resolve. The distinction between zip/join (lax monoidal, no sequencing) and and_then/.await (Kleisli, sequential) formulates the concurrency/sequencing boundary that async Rust makes syntactically explicit.
6.6. Monad-Like Patterns Without HKT
Rust cannot abstract over a generic Monad m constraint because the trait system lacks the kind * -> * required to write trait Monad: for<T> Functor<T> in a type-safe way. Option, Result and Future each implement their own and_then (bind) method. The monadic structure is present and fully usable but cannot be abstracted over an arbitrary Monad parameter.
The ? operator is syntactic sugar for the monadic bind pattern applied to fallible types. For Result<T, E> in a function returning Result<U, E>, the desugaring is:
expr?becomes:
match expr {
Ok(v) => v,
Err(e) => return Err(e.into()),
}For Option<T>, the analogous desugaring returns None on the absent case. The Try trait (currently unstable) generalises this to arbitrary types and abstracts the short-circuiting behaviour without a full Monad abstraction.
The ? operator is Haskell's >>= (bind) specialised to Result and Option. In Haskell do { v <- expr; rest } desugars to expr >>= \v -> rest for any Monad instance. Rust's ? has the same effect for the two most important monadic types in systems programming with no runtime overhead and no heap allocation. It cannot abstract over the monad parameter.
6.7. Haskell do-notation and Monadic IO
Haskell's do-notation desugars to >>= (bind) and >> (sequence) for any type with a Monad instance. IO a is the monad for effectful computation: a value of type IO a is an action that, when executed by the runtime, produces a value of type a. Any type with a Monad instance can use do-notation, including user-defined types: parsers, state machines, error accumulators, probability distributions. The abstraction is fully general.
Rust's ? is specialised to Result, Option and types implementing the Try trait. It cannot be used with an arbitrary user-defined monad. Haskell is more general: a single abstraction (Monad) covers all compositional fallible or effectful computations. Rust is more explicit: each type defines its own and_then and the compiler emits the same machine code as a hand-written sequence of match expressions and early returns with no allocation. Both compose fallible computations without deeply nested match expressions. Haskell's generality enables polymorphic libraries (a parser combinator written generically over any monad) and Rust's specialisation keeps the runtime behaviour transparent.
6.8. RustCell Iterator Adapter Chain
The following programme is the stream coalgebra in action. Each adapter (filter, map, take, fold) wraps the previous iterator in a new state type. The compiler fuses all adapters into a single loop with no intermediate vectors and no heap use. The generated code is equivalent to a hand-written for loop with a running accumulator.
fn main() {
// Coalgebra in action: a chain of zero-cost iterator adapters.
// The compiler fuses all adapters into a single loop with no allocation.
let result: i64 = (1_i64..=100)
.filter(|n| n % 2 == 0) // keep evens: 2, 4, 6, ...
.map(|n| n * n) // square: 4, 16, 36, ...
.take(10) // first 10 squared evens
.fold(0, |acc, n| acc + n); // sum
println!("{result}"); // 1540 (4+16+36+64+100+144+196+256+324+400)
}Iterator adapter chain of filter, map, take and fold compiled to a single zero-allocation loop
7. Async Rust and Tokio
7.1. Futures as State Machines
An async fn is desugared by the compiler into an anonymous struct that implements the Future trait. Each .await point inside the function becomes a variant in an internal state-machine enum for the suspension point where the future yielded.
The Future trait is defined as:
fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>Poll<T> has two variants: Poll::Ready(T), returned when the computation is complete, and Poll::Pending, returned when the computation has not yet completed and the future has arranged for the executor to be notified via the Waker stored in cx. A Waker is a handle to a task scheduler: calling waker.wake() instructs the executor to re-poll the future.[13]
The desugaring makes suspension explicit at every step. A function containing two .await points is compiled into an enum with a variant for the unresumed start, one variant for each of the two suspension points (containing the locals live across it) and terminal variants for a returned or panicked future. Each call to poll advances the state machine to the next suspension point or returns Poll::Ready when the computation has completed. No OS thread is blocked between suspension points. The entire state of the computation lives in this enum. It sits on the heap once the future is boxed or spawned and its size is that of its largest variant.
7.2. Waker Protocol
When Future::poll returns Poll::Pending, the future is contractually required to have stored (cloned) the Waker from the supplied Context<'_>. The future must then arrange for waker.wake() to be called when the awaited resource becomes available. The executor need not re-poll the future until wake() is called. Spurious polls are permitted and the future must tolerate them. Under this contract the executor never spins (busy-waiting on an unready future) and never loses track of a pending task.[13]
In practice, when an underlying I/O source becomes ready (a socket is readable, detected by epoll on Linux or kqueue on macOS), the OS notifies Tokio's reactor, which looks up the Waker registered for that I/O source and calls waker.wake(). This re-queues the waiting task on a worker thread's run queue. No OS thread is blocked during the wait. A task suspends and resumes with a single heap dereference and a queue push and needs no kernel context switch.
7.3. Pin and Structural Pinning
A Future state machine may contain self-referential pointers: an internal reference to a local variable that is itself stored in the same state-machine struct. If the struct were moved (copied to a new address) that internal reference would point to the old location and dangle. Pin<P> prevents this.
Unpin is a marker trait. A type that implements Unpin is safe to move even when it is accessed through a Pin pointer, because it makes no self-referential use of its own address. Most types in Rust implement Unpin automatically. Compiler-generated async state machines do not implement Unpin, because they may contain self-referential fields across .await points.
The Pin<P> invariant: if P is a pointer type and T = *P does not implement Unpin, then once a value of type T is placed behind a Pin<P>, it will not be moved or invalidated until it is dropped, even after the pin itself has expired. As an example, Pin<Box<T>> means "the T at this address will not move until the Box is dropped."[20]
The poll signature takes self: Pin<&mut Self> precisely because the executor must be able to call poll repeatedly on the same future without moving it between calls. A future that is not Unpin can only be polled through a pinned pointer. Once it is pinned for its first poll safe code cannot move it again.
7.4. Tokio's Work-Stealing Scheduler
Tokio uses an M:N threading model: M OS threads (one per logical CPU core by default) run N async tasks, where N can be millions. Each worker thread maintains a local run queue of ready tasks. When a thread's local queue is empty it checks a shared injection queue and then steals half of the tasks in another worker's local queue. The Go runtime scheduler steals in the same way and the Rayon data-parallelism library uses work-stealing deques. The local queues need no lock.[12]
A Tokio task has zero stack overhead. Its state is a single heap-allocated Future struct, the state machine described in section 7.1, which needs only as much memory as the live locals at the current suspension point. There is no per-task stack, stack-growth check or sentinel page. A million idle Tokio tasks with small futures occupy a few hundred megabytes.
The macro #[tokio::main] expands to code that builds a runtime with tokio::runtime::Builder::new_multi_thread().enable_all() and calls block_on(async { ... }) on it. The runtime spawns the worker threads and block_on blocks the main OS thread until the async entry point returns Poll::Ready.
7.5. Go Goroutines and the Go Runtime Scheduler
Go goroutines and Tokio tasks solve the same problem (M:N concurrency on top of OS threads) by different designs. Three differences matter.
Stack allocation. A goroutine begins with a minimum 2 KB stack that grows dynamically as needed, up to a default limit of 1 GB. The Go runtime manages growth: when a goroutine's stack overflows it allocates a new, larger stack and copies the goroutine's frames to it. A Tokio task has no stack. Its state is entirely contained in the Future enum on the heap, sized at compile time to contain the live locals at each .await point. Tokio needs no stack management and no copying.
Scheduling discipline. Go has used asynchronous preemption since Go 1.14. The runtime preempts a goroutine that has run for more than about 10 ms by signalling its thread. Even a tight loop with no function calls can then be suspended. Tokio is cooperative: a task runs until it returns Poll::Pending. A task that computes intensively without awaiting blocks its worker thread for the duration of the computation and starves other tasks on that thread. CPU-bound work in Tokio must therefore run on a dedicated blocking thread pool (tokio::task::spawn_blocking) and not directly on the async executor.
Visibility of asynchrony. In Go, every blocking call (channel receive, network I/O, a time.Sleep) is transparently a goroutine yield: the programmer writes synchronous-looking code and the runtime handles the scheduling. In Rust, every yield is an explicit .await. The asynchronous structure of the programme is visible in the type system: an async fn returns a Future, and that Future must be driven by an executor. Every suspension point is named.
Go's design is simpler to use, with no async/await syntax, no Future types and no Pin. Rust's has zero overhead (no hidden stack allocation, no runtime stack management) and is auditable because every suspension point is explicit and reviewable.
7.6. Polybius Async Order Execution over WebSockets
The Polybius trading engine uses Tokio for all network I/O. Each market feed runs as a tokio::spawn-ed task that maintains a persistent WebSocket connection to Polymarket's CLOB and parses order-book updates into shared state via Arc<RwLock<State>>. The design uses tokio::sync::RwLock for read-heavy shared state and tokio::sync::Mutex for write-critical sections, and avoids an actor model in favour of explicit lock-based coordination. The execution path is the Waker protocol in production: when a WebSocket frame arrives the OS notifies Tokio's reactor via epoll, the reactor calls waker.wake() on the waiting task, and the task is re-queued on a worker thread's run queue and re-polled to completion.
7.7. RustCell async/await with Tokio
The following programme shows the core async pattern. A producer task is spawned with ownership of the sender half of an mpsc channel (transferred via move into the async block) and the main task consumes messages from the receiver half using rx.recv().await. The main task suspends at each .await, which lets the scheduler drive the producer task forward, and resumes when the channel delivers a message. The programme exits when the channel is closed: the sender is dropped at the end of the producer task, rx.recv() returns None and the while let loop terminates.
use tokio::sync::mpsc;
#[tokio::main]
async fn main() {
let (tx, mut rx) = mpsc::channel::<String>(8);
// Spawn a producer task
tokio::spawn(async move {
for i in 0..3 {
tx.send(format!("message {i}")).await.unwrap();
}
});
// Consume on the main task
while let Some(msg) = rx.recv().await {
println!("{msg}");
}
}Tokio async/await with a producer task and an mpsc channel receive
8. Zero-Cost Abstractions and the FFI Bridge
8.1. Formal Meaning of Zero-Cost
Bjarne Stroustrup articulated the zero-cost abstraction principle as: "What you don't use, you don't pay for. And further: What you do use, you couldn't hand-code any better."[18] In Rust the principle has a precise operational meaning in terms of monomorphisation and LLVM IR.
A generic abstraction is zero-cost if after monomorphisation and inlining the generated machine code is identical to hand-written specialised code. For example the generic function fn add<T: std::ops::Add<Output=T>>(a: T, b: T) -> T { a + b } instantiated at i64 produces LLVM IR identical to the non-generic fn add_i64(a: i64, b: i64) -> i64 { a + b }. The generic version has zero overhead: the compiler erases the type parameter and emits the same integer addition instruction.
The principle applies to safe, statically dispatched code paths. Two exceptions apply. First, unsafe blocks transfer the proof obligation for memory safety to the programmer. The compiler trusts the programmer's claims and may optimise less aggressively. Second, dynamic dispatch (dyn Trait) is not zero-cost: every call through a fat pointer incurs a vtable lookup (one indirect branch) and prevents inlining in exchange for runtime flexibility. Choosing between impl Trait (monomorphised) and dyn Trait (vtable, runtime overhead) is therefore a deliberate performance decision.
8.2. LLVM IR and the Compilation Pipeline
rustc lowers Rust source through a sequence of intermediate representations before producing machine code. Each IR stage has a distinct purpose:
- AST: the surface syntax after parsing, as a tree of syntactic forms.
- HIR (high-level IR): lowered from the AST after macro expansion and name resolution. Type checking and trait resolution run on HIR.
- MIR (mid-level IR): a control-flow graph of typed basic blocks with explicit borrow annotations. The borrow checker and lifetime analysis operate entirely on MIR. Monomorphisation also occurs at this stage.
- LLVM IR: produced from MIR after optimisation passes specific to Rust. LLVM then applies its own optimisation pipeline: inlining, loop-invariant code motion, auto-vectorisation, dead code elimination and others.
- Machine code: architecture-specific assembly, emitted by LLVM's back end for the target triple.
MIR makes the control-flow structure of a programme explicit. In simplified form a loop that accumulates a sum has four basic blocks. bb0 initialises the accumulator and index and jumps to bb1. Block bb1 tests i < len and branches to bb2 or to bb3 (the exit). Block bb2 performs one iteration (read v[i], add to sum, increment i) and jumps back to bb1. The borrow checker verifies at every edge in this graph that the aliasing and lifetime invariants are satisfied. The CFG is explicit so the analysis is decidable and fast.
Rust's safety guarantees are checked on MIR. The RustBelt soundness theorem[7] proves memory safety for the MIR-like calculus λRust. It supports the discipline that the MIR borrow checker enforces and does not verify rustc's implementation.
8.3. rayon and Data-Parallelism
rayon provides a fork-join, work-stealing parallel iterator that mirrors the sequential iterator API exactly. A computation expressed as v.iter().filter(...).map(...).reduce(...) becomes parallel by replacing .iter() with .par_iter(). The parallelism is entirely behind the API boundary: rayon divides the iterator into chunks, distributes them across a thread pool using work-stealing deques (each thread maintains a deque and steals from the far end of another thread's deque when its own is empty) and joins the results. Tokio's multi-threaded scheduler also uses work stealing for I/O-bound tasks.
The pathwise project (PyPI; an open-source Rust SDE solver described in §8.5) uses rayon internally to parallelise Monte Carlo path batches across CPU cores. With four rayon threads it runs about four times as fast as a vectorised NumPy Euler loop on the same problem (§8.5), with no change to the Python-facing API.
8.4. PyO3 and maturin
PyO3 provides safe Rust bindings to the CPython C API.[14] A Rust function annotated #[pyfunction] is compiled into a CPython extension module: a native shared object (.so on Linux, .pyd on Windows) that Python loads at import time. maturin is the build tool that orchestrates this pipeline: it compiles the Rust crate into an extension module and produces a Python wheel. On Linux and macOS the module does not link against libpython: the interpreter supplies the Python symbols at load time.[15] A pip install of that wheel drops the native extension into the Python environment with no further configuration.
Python calls the Rust function via the C ABI: one pointer dereference into the extension module's function table and then native Rust execution at full machine speed. There is no interpretation layer and no serialisation overhead for numeric types (PyO3 converts Python floats and integers to Rust primitives at the boundary).
The PyO3 0.21+ API replaced the deprecated &PyModule argument type with &Bound<'_, PyModule>. The Bound type makes the relationship between the Rust reference and the Python GIL explicit in the type system and PyO3 enforces GIL handling at compile time.
Hand-written C extensions use the same mechanism but need substantial boilerplate (PyArg_ParseTuple, reference counting, method table definitions) and are entirely unsafe. ctypes performs FFI at the Python level and is considerably slower because each call crosses from the CPython interpreter into C with none of the native compilation that PyO3 performs.
8.5. pathwise SDE Solver as a Python Extension
pathwise is an open-source Rust SDE solver that exposes Euler, Milstein and SRI schemes and a set of built-in processes to Python via PyO3. A user calls pathwise.simulate(pathwise.gbm(mu=0.05, sigma=0.2), scheme=pathwise.euler(), n_paths=10_000, n_steps=252, t1=1.0, x0=100.0) and receives a NumPy array of simulated paths. The Rust implementation uses rayon internally to parallelise batch path simulation across CPU cores. For that call (geometric Brownian motion, Euler, 10,000 paths of 252 steps) pathwise-sde 0.2.0 takes 6.7 to 8.9 ms with RAYON_NUM_THREADS=4 against 30 to 35 ms for a NumPy loop that advances all paths one step per iteration: a speedup of 3.9 to 4.5x. On one thread the speedup is 1.5x (best of seven runs, AMD Ryzen 9 8940HX). pathwise applies the pattern of §8.4 in a real project: Python provides the calling convention, Rust provides the compute and PyO3 bridges the two with a single function-table indirection.
8.6. inferCNAsc Copy Number Alteration Inference
inferCNAsc (PyPI) is an open-source Rust crate for inferring chromosomal copy number alterations (CNAs) from single-cell RNA-sequencing (scRNA-seq) expression matrices. It uses a structural pattern absent from pathwise: a Cargo feature flag makes the entire PyO3 dependency optional. The Rust library builds and ships independently of any Python ABI and the Python bindings are compiled only when the
python feature is enabled.
The pipeline is a sequential three-stage computation over a cells × genes expression matrix represented as ndarray::Array2<f64>. The first stage, smooth_expression, applies a sliding-window mean within each chromosome and resets at chromosome boundaries to prevent smoothing across genomically discontinuous regions. The second stage, find_cnas, computes z-scores per gene across cells and thresholds them into two indicator matrices for gains and losses. The third stage, assign_cnas_to_cells, applies a run-length scan over consecutive flagged genes on the same chromosome and merges them into CnaRecord structs that record the chromosome, genomic coordinates, flagged gene names and alteration direction.
At the Python boundary, the numpy PyO3 extension handles zero-copy array bridging: PyReadonlyArray2<'py, f64> borrows a NumPy array without copying its data, and Array2<f64>::into_pyarray(py) transfers ownership of the output array back to Python. The Rust find_cnas returns Array2<bool> indicator matrices. The Python binding converts them to Array2<u8> (values 0 or 1) for the FFI boundary because u8 is the portable wire dtype across platforms. The Python layer reinterprets them with a zero-copy .view(np.bool_).
The feature-flag design uses the same idiom as the alloc feature in cartan-manifolds (§10.2) on a different axis: it makes an entire foreign-language ABI optional where alloc does so for heap-allocation types. Without the python feature cargo build produces a standard Rust library with no link-time dependency on libpython. With it maturin compiles the crate into a Python wheel via the pipeline of §8.4. Every #[pyfunction] wrapper and the module registration function are annotated with #[cfg(feature = "python")], and the boundary is explicit and auditable like an unsafe block: a demarcated region where the proof obligations for correct behaviour across a foreign calling convention rest with the programmer.
8.7. RustCell Structural PyO3 Module Example (non-runnable)
The snippet below shows the structural pattern. #[pyfunction] marks a Rust function as directly callable from Python. #[pymodule] registers functions in the Python module object. wrap_pyfunction! generates the glue code that bridges the Python and Rust calling conventions: it produces a PyCFunction descriptor that the CPython runtime can invoke and handles argument parsing and return-value conversion automatically.
// This snippet is structural only and cannot run on the Playground.
// PyO3 requires a Python interpreter and the maturin build pipeline.
// Uses the PyO3 0.21+ API: Bound<'_, PyModule> replaces the deprecated &PyModule.
use pyo3::prelude::*;
#[pyfunction]
fn euler(mu: f64, sigma: f64, x0: f64, dt: f64, n: usize) -> Vec<f64> {
// ... SDE integration ...
vec![x0; n] // placeholder
}
#[pymodule]
fn pathwise(m: &Bound<'_, PyModule>) -> PyResult<()> {
m.add_function(wrap_pyfunction!(euler, m)?)?;
Ok(())
}PyO3 module structure with #[pyfunction] exposed via #[pymodule] (not runnable on the Playground)
9. Serialisation and the serde Data Model
9.1. serde Data Model
serde defines a universal intermediate representation between Rust types and serialisation formats.[19] This intermediate representation, called the serde data model, consists of 29 types organised into two conceptual groups. The first group covers primitives: the boolean, signed and unsigned integers from 8 to 128 bits, 32- and 64-bit floats, char, string and byte sequences. The second group covers composite containers: option (presence or absence of a value), unit types (zero-sized structs, unit enum variants, the unit value itself), newtype wrappers (single-field structs and newtype enum variants), sequences, tuples and tuple structs, tuple enum variants, maps, named structs, and named enum variants. Every Rust type that serde can handle maps to exactly one of these 29 forms.
The serde data model is a set of 29 abstract types that forms the universal intermediate representation for Rust serialisation. A Serializer is a mapping from the data model to a wire format (JSON, TOML, Bincode, MessagePack, and others). A Deserializer is the inverse mapping from a wire format back to the data model. Because every format communicates through this shared IR a Rust type that implements Serialize and Deserialize is automatically compatible with every format that provides a conforming Serializer or Deserializer and needs no format-specific code.
9.2. Derive Macros for Zero-Cost Serialisation
Annotating a struct or enum with #[derive(Serialize, Deserialize)] makes the Rust compiler expand a complete type-specific implementation of the Serialize and Deserialize traits at compile time. There is no reflection and no runtime type information (RTTI). The generated code calls the serialiser's methods directly. It names each field by its string representation and dispatches to the exact data-model type for each field's Rust type. The result is structurally identical to what a programmer would write by hand. The zero-cost abstraction principle from §8.1 thus extends to serialisation: the derive macro adds no overhead to the hot path.
#[derive(Serialize)] is a procedural macro (proc-macro) that runs as part of compilation. It receives the token stream of the annotated type definition and emits a token stream containing a complete, type-specific impl Serialize block. The output contains no generic dispatch, vtable or type-erased container. The generated impl names every field explicitly, calls the serialiser's typed methods (serialize_struct and one serialize_field per field, which reach serialize_f64 or serialize_str through each field's own impl), and does so in the same order and with the same calling convention that a hand-written impl would use. All generic overhead is eliminated before the LLVM IR stage.
9.3. Custom Serialisers and Deserialise-with Patterns
serde provides three mechanisms for overriding the default derived behaviour. The #[serde(with = "module")] attribute delegates both serialisation and deserialisation for a field to free functions defined in a named module, which must expose serialize and deserialize functions with the expected signatures. For finer control, #[serde(serialize_with = "fn")] and #[serde(deserialize_with = "fn")] allow per-field overrides of one direction only and leave the other direction to the derived implementation. For types that cannot be derived at all (for example, a duration value encoded on the wire as an ISO 8601 string such as "PT1H30M"), serde provides the Visitor pattern: the programmer implements a stateful Visitor struct that receives a sequence of events from the format driver (one event per token, analogous to a SAX parser for XML) and accumulates them into the target Rust value. The Visitor approach handles arbitrarily complex wire representations without sacrificing type safety.
9.4. C/C++ and Go Serialisation
C/C++: nlohmann/json uses runtime polymorphism and type erasure: values are stored in a variant container and dispatched at runtime. protobuf requires a separate schema file (.proto) and a dedicated code-generation step before any C++ code can be compiled; the schema and the C++ struct are two artefacts that must be kept in sync by the programmer. Manual struct serialisation with memcpy is entirely unsafe: it relies on platform-specific layout assumptions, breaks on any struct with padding and is undefined behaviour if alignment is incorrect. None of these approaches provide compile-time type-safe serialisation without either extra tooling or unsafe code.
Go: encoding/json uses the reflect package to introspect field names, types and struct tags at runtime. No code generation is required, which simplifies the toolchain, but the reflection path is slower than compile-time dispatch and all serialised fields must be exported (capitalised). Go's JSON layer enforces type safety at runtime: a type mismatch surfaces as an error value or a silent zero-value assignment during json.Unmarshal.
Rust/serde: compile-time code generation via proc-macro derive; reflection, schema files for JSON or TOML, user-written unsafe code and exported-field constraints are all absent. LLVM fully inlines and optimises the generated code so the hot path has zero overhead. Format support is open-ended: any crate that implements Serializer or Deserializer against the serde data model is immediately compatible with all existing types.
9.5. RustCell serde_json Round-Trip
The demo below shows all three phases of serde. #[derive(Serialize, Deserialize)] generates all serialisation and deserialisation code for Point at compile time with no runtime type lookup. serde_json::to_string maps the struct through the serde data model to a JSON string via the serde_json Serializer. serde_json::from_str runs the inverse path through the Deserializer and reconstructs the struct. The final assert_eq! verifies that the round-trip preserves the value exactly: the derive-generated paths are inverses of one another.
use serde::{Deserialize, Serialize};
#[derive(Debug, Serialize, Deserialize, PartialEq)]
struct Point {
x: f64,
y: f64,
label: String,
}
fn main() {
let p = Point { x: 1.5, y: -2.3, label: String::from("origin") };
// Struct -> JSON string (zero-copy serialisation path)
let json = serde_json::to_string(&p).unwrap();
println!("{json}");
// JSON string -> Struct (derive-generated Deserialize)
let p2: Point = serde_json::from_str(&json).unwrap();
assert_eq!(p, p2);
println!("round-trip OK: {p2:?}");
}serde_json round-trip of a struct to a JSON string and back through the derive-generated path
10. Rust in Constrained Environments with no_std
10.1. no_std Contract
Adding #![no_std] to a crate removes the implicit link against Rust's standard library. This lets Rust programmes target bare-metal microcontrollers, operating system kernels and other environments where no OS is present to provide the services on which std depends.
What is lost: heap allocation (Box, Vec, String and all types that allocate dynamically) and OS abstractions (threads, file I/O, networking). What remains: the full Rust language, the core crate (iterators, Option, Result, all primitive types, the fmt infrastructure and since Rust 1.81 the Error trait) and optionally the alloc crate if a global allocator is provided.
Two additional obligations arise for a bare no_std binary. The programmer must provide a #[panic_handler]: a function that takes a &PanicInfo and diverges (-> !). It replaces the default panic runtime. If heap allocation is desired, the programmer must also provide a #[global_allocator]: a static value that implements the GlobalAlloc trait and supplies alloc and dealloc for the runtime.
The analogous contract in C bare-metal is to avoid all calls to malloc, free and the C standard library's I/O functions. The difference is enforcement: in C an accidental #include <stdio.h> followed by a printf call compiles silently and then fails at link time or at runtime on a target with no libc. In Rust #![no_std] is a compile-time directive and any use std::... is an immediate compile error that catches the mistake before the linker.
A Rust crate annotated with #![no_std] links against core (and alloc if declared) and not against std. The crate therefore has no access to OS-backed services: no heap allocator, thread primitives, file system or network stack, unless these are provided explicitly by the programmer through a #[global_allocator], a platform-specific runtime crate, or direct hardware register access. A no_std binary must also define a #[panic_handler]. The boundary is enforced at compile time: any reference to an item in std that does not exist in core or alloc is a compile error.
10.2. alloc Crate
The alloc crate is a subset of std that provides heap-using types (Box, Vec, String, Arc, Rc, BTreeMap, and others) without requiring a full OS. To use it in a no_std crate, the programmer declares extern crate alloc (or exposes it via a Cargo feature) and provides a #[global_allocator] that implements GlobalAlloc. On embedded targets the allocator is typically backed by a fixed-size static byte array, for example via the embedded-alloc crate, which implements a simple heap within a region of RAM chosen at link time.
cartan-manifolds follows this pattern. Grassmann needs heap-allocated matrices and sits behind #[cfg(feature = "alloc")]. Spd, Corr and the other manifolds that use nalgebra's symmetric eigendecomposition sit behind #[cfg(feature = "std")]. Without these features they are not compiled and the rest of the crate remains usable on targets with no heap. A single codebase thus serves embedded and hosted environments with no code duplication or runtime branching.
10.3. libm
In a std-linked binary, functions such as f64::sin, f64::sqrt and f64::exp delegate to the platform's maths library (libm on Linux, compiler-rt intrinsics on LLVM targets). A no_std environment has no such library. The libm crate provides pure-Rust implementations of the C99 floating-point maths functions with no OS dependency and so makes trigonometric and transcendental functions available to no_std crates. cartan-core lists libm as an unconditional dependency and calls its functions (libm::sin, libm::cos, libm::sqrt, and others) wherever float maths is required outside std.
10.4. cartan Geometry on the Edge of no_std
cartan-core is no_std-compatible. Its crate root declares #![cfg_attr(not(feature = "std"), no_std)], uses libm for all float maths and puts any heap-using code behind the alloc feature. This pattern is the standard idiom for conditional no_std: the crate compiles with std by default for ergonomics and test support and becomes no_std when the std feature is disabled via cargo build --no-default-features. cartan-manifolds follows the same idiom. It enables the libm feature of nalgebra so that f64: RealField is available without std. Only the eigendecomposition-based manifolds require std.
10.5. RustCell Structural no_std Example (non-runnable)
The snippet below shows the cfg_attr idiom in its minimal form. The crate is no_std when the std feature is disabled. libm::sin replaces the OS maths library for the exponential normalisation calculation on the sphere. The #[panic_handler] is the minimal obligation that a no_std binary must fulfil: without it the crate will not link on a bare-metal target. With the std feature enabled the crate is an ordinary binary with a main and prints sin(0.5)/0.5 = 0.958851. With the feature disabled it builds for thumbv7em-none-eabihf, but a flashable image also needs an entry point and a linker script, which the Playground cannot supply. The snippet illustrates the pattern used in cartan-core.
// The cfg_attr pattern mirrors cartan-core: the crate is no_std when the
// "std" feature is disabled and std-linked otherwise. With "std" enabled it
// builds and runs as an ordinary binary. Without it a bare-metal target also
// needs an entry point and linker configuration that this snippet omits.
#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(not(feature = "std"), no_main)]
// libm provides sin and other float maths without linking the OS maths library.
fn sphere_exp_norm(v_norm: f64) -> f64 {
// Taylor expansion for small v_norm; libm::sin for large values.
if v_norm < 1e-7 {
1.0 - v_norm * v_norm / 6.0
} else {
libm::sin(v_norm) / v_norm
}
}
#[cfg(feature = "std")]
fn main() {
println!("sin(0.5)/0.5 = {:.6}", sphere_exp_norm(0.5));
}
#[cfg(not(feature = "std"))]
#[panic_handler]
fn panic(_info: &core::panic::PanicInfo) -> ! {
loop {}
}no_std with libm and the cfg_attr pattern used in cartan-core for embedded targets
11. Network I/O and Zero-Cost Buffering
11.1. Packet Buffering over Sockets
In the OS model a network socket is a file descriptor backed by a kernel receive queue. When a UDP datagram arrives at the NIC, the driver DMAs the packet bytes into a kernel buffer and appends a metadata record to a per-socket receive queue. When the user process calls recv(), the kernel copies the datagram bytes into the user-supplied buffer, removes the record from the queue and returns the byte count. If no datagram is available and the socket is non-blocking the call returns immediately with WouldBlock. The async Tokio layer (§7.2) arranges for epoll to notify the executor when the socket becomes readable again and no thread is blocked during the wait.
UDP has three structural properties that matter for buffering. First, discreteness: recv() delivers exactly one datagram per call. There is no API to read half a datagram or two datagrams atomically. The kernel's receive queue is a sequence of discrete, bounded chunks. Second, unknown size at call time: the application must supply a buffer large enough to contain the largest possible datagram before calling recv(). If the buffer is too small, the OS silently truncates the datagram and the excess bytes are permanently lost. The maximum UDP payload is 65,507 bytes (the IP maximum minus 20-byte IP header minus 8-byte UDP header), though Ethernet-constrained networks cap practical datagrams at 1,472 bytes (1,500-byte MTU minus headers). Third, arrival unpredictability: datagrams arrive at times that the network determines. A high-frequency publisher (a market data feed, a sensor bus, a game server) can burst thousands of datagrams in a millisecond. If the application processes each datagram synchronously before calling recv() again the kernel queue fills and the OS begins silently dropping packets. The bottleneck is the application's processing loop and the loss is self-inflicted.
The buffering goal follows from these three constraints. Given datagrams of variable unknown size arriving at an unpredictable rate, store them in a fixed pre-allocated memory region with constant-time insert and remove, copy each byte at most once and make no per-datagram heap allocation. A naive implementation that allocates a fresh Vec<u8> per received datagram is correct but calls the allocator on every receive and every consume. Under load this is measurable: the allocator must maintain free lists, acquire locks and occasionally ask the OS to map new pages. On a 10 Gbps link sustaining 8 million datagrams per second this means millions of allocator calls per second in what should be a memory-copy pipeline.
The solution is a ring buffer: a statically allocated circular array in which the producer (the receive loop) and the consumer (the processing loop) advance independent pointers around the same contiguous memory and wrap modulo the capacity. No allocation occurs after startup because the memory is fixed. Insert and remove are constant time. Two complications remain that a plain ring buffer cannot address: variable-length datagrams (a plain ring buffer has a fixed element type) and fallible I/O (the receive may fail and the buffer must remain consistent). The designs below resolve both.
11.2. Ring Buffer Structure and Correctness
A ring buffer of capacity over a type is a triple where is the backing array, is the head index (the position of the oldest unconsumed element), and is the current occupancy. The tail index (the first free slot) is . This representation is equivalent to the two-pointer representation and resolves its classical ambiguity: in the two-pointer form with both the empty and the full buffer have . Implementations therefore sacrifice one slot and call the buffer full when . In the representation empty is and full is with no wasted slot.
Let be a ring buffer of capacity . For any , the index of the -th occupied element (counting from the head) is . The buffer is nonempty iff . A push onto a buffer with increments by 1 and writes to index (the tail). A pop from a buffer with decrements by 1 and increments by 1 modulo .
Proof. The invariant holds initially (empty buffer, ). Suppose it is satisfied before a push. The new element is written to the tail index and is incremented. For (old elements), the index is unchanged. For (the new element), the index is as specified. The invariant is preserved. For a pop, advances to and decrements. For , the new index of the -th element is , which equals the old : each element that was at position is now at position under the new head, consistent with the invariant at the new . □
A ring buffer with the operations defined above implements a first-in-first-out queue: elements are dequeued in the same order they were enqueued.
Proof. Denote the sequence of enqueue operations as writing values at times . By the wrapping invariant, at any point in time the occupied slots are exactly those at indices for , in the order they were written. The oldest element (smallest enqueue time among those not yet consumed) is always at index , since each pop advances by 1 and decrements by 1 without disturbing any other element. Therefore each pop returns the least recently enqueued of the remaining elements. This is FIFO ordering. □
A representative implementation represents the buffer as:
pub struct Ring<'a, T> {
head: u32,
len: u32,
buffer: &'a mut [T],
}The lifetime ties the buffer borrow to the caller's scope: the ring does not own its backing memory and performs no heap allocation. The backing slice is typically a Box<[T]> or a stack-allocated array allocated once at startup. All subsequent operations are pure arithmetic on head and len with index computations modulo buffer.len().
The following implementation uses an owning Vec for clarity on the Playground (the production version borrows a pre-allocated slice). It demonstrates the wrapping invariant via get(k), forces the array boundary crossing by popping two elements before refilling and ends with a drain that is the coalgebra morphism into a finite stream:
struct Ring<T> {
buf: Vec<Option<T>>,
head: usize,
len: usize,
}
impl<T> Ring<T> {
fn new(capacity: usize) -> Self {
let buf = (0..capacity).map(|_| None).collect();
Ring { buf, head: 0, len: 0 }
}
fn capacity(&self) -> usize { self.buf.len() }
fn is_full(&self) -> bool { self.len == self.capacity() }
fn is_empty(&self) -> bool { self.len == 0 }
fn push(&mut self, val: T) -> bool {
if self.is_full() { return false; }
let tail = (self.head + self.len) % self.capacity();
self.buf[tail] = Some(val);
self.len += 1;
true
}
fn pop(&mut self) -> Option<T> {
if self.is_empty() { return None; }
let val = self.buf[self.head].take();
self.head = (self.head + 1) % self.capacity();
self.len -= 1;
val
}
// k-th element from the head; directly encodes the wrapping invariant
fn get(&self, k: usize) -> Option<&T> {
if k >= self.len { return None; }
self.buf[(self.head + k) % self.capacity()].as_ref()
}
// Drain: the unique coalgebra morphism Ring<T> -> Vec<T> (finite stream prefix)
fn drain(mut self) -> Vec<T> {
let mut out = Vec::with_capacity(self.len);
while let Some(v) = self.pop() { out.push(v); }
out
}
}
fn main() {
let mut ring: Ring<i32> = Ring::new(4);
ring.push(10); ring.push(20); ring.push(30);
assert_eq!(ring.get(0), Some(&10));
assert_eq!(ring.get(1), Some(&20));
assert_eq!(ring.get(2), Some(&30));
// Pop two: head advances, next pushes wrap past the array boundary
assert_eq!(ring.pop(), Some(10));
assert_eq!(ring.pop(), Some(20));
ring.push(40); ring.push(50); ring.push(60);
assert!(ring.is_full());
// Drain proves FIFO holds across the wrap boundary
let out = ring.drain();
assert_eq!(out, vec![30, 40, 50, 60]);
println!("drain (forced wrap): {:?}", out);
println!("Ring invariants hold.");
}Ring<T> wrapping invariant, forced boundary crossing and FIFO drain as coalgebra morphism
The pair , where if and otherwise (with the ring after advancing the head), is a coalgebra of the functor , the same functor whose terminal coalgebra is the stream type from §6.2. Every -coalgebra admits a unique coalgebra morphism into the terminal coalgebra; here that morphism is the drain function that repeatedly applies until the buffer empties and produces a finite prefix of the stream. The ring is a finite bounded approximation to the infinite stream coalgebra and this finiteness makes it useful as a buffer: an infinite stream accumulates without bound, while the ring refuses new data when full.
11.3. Views as Linear Borrows
The variable-length receive problem requires a more subtle interface than a plain push. The application must hand the OS a pointer into the ring's free region, let the kernel write directly into that region (eliminating one copy) and only then tell the ring how many bytes were written. If the interface exposed a mutable slice and required the caller to return the written count separately, nothing would prevent the caller from forgetting to commit and the ring's occupancy count would fall out of sync. The view types resolve this by encoding the protocol in the type system.
The view types form a capability hierarchy. RingView<'a, T> has a shared reference (&[T]) into the occupied region: multiple views can coexist and none can mutate. RingMutView<'a, 'b, T> has an exclusive reference (&mut T) into a single occupied slot: it grants mutation of an existing element and cannot extend the buffer's length. RingManyMutView<'a, 'b, T> has an exclusive reference to the largest contiguous free region at the tail: it grants mutation of uninitialised slots and commits a length increment of to the ring via set_modified(n).
At any instant, at most one RingManyMutView exists for a given Ring. While a RingManyMutView is live no other reference (shared or exclusive) to the ring's interior can be created.
Proof. RingManyMutView is constructed by a method taking &mut Ring<T>. By the aliasing rules of §3.2 the view requires an exclusive borrow of the ring for its lifetime and the borrow checker enforces it. A second &mut Ring<T> borrow cannot be created while the first is live (the diagonal map does not exist for a non-Copy type, as discussed in §6.5). Therefore no second view can be constructed. A shared borrow &Ring<T> would also conflict with the outstanding exclusive borrow and is rejected at compile time as well. □
The view obeys affine logic (§2.1). A RingManyMutView is an affine resource: it is consumed at most once by calling set_modified to commit, and dropping it unused rolls back the pre-allocation. Rust's ownership system enforces this without any runtime check. The view cannot be shared because the ring's wrapping position depends on exactly how much was written and only the caller (the recv() call) determines that.
The following example shows the pattern. push_with accepts a closure over the free tail of a byte ring. The closure receives exclusive access to the write window. On Ok(n) exactly bytes are committed. On Err the ring state is unchanged. The borrow checker enforces that no second reference to the ring's interior exists while the closure has the slice. Rollback is therefore automatic and zero-cost:
struct ByteRing {
buf: Vec<u8>,
head: usize,
len: usize,
}
impl ByteRing {
fn new(capacity: usize) -> Self {
ByteRing { buf: vec![0u8; capacity], head: 0, len: 0 }
}
fn capacity(&self) -> usize { self.buf.len() }
// Closure owns the write window exclusively. Ok(n) commits n bytes.
// Err leaves the ring unchanged; no explicit rollback needed.
fn push_with<E, F>(&mut self, f: F) -> Result<usize, E>
where
F: FnOnce(&mut [u8]) -> Result<usize, E>,
{
let cap = self.capacity();
let tail = (self.head + self.len) % cap;
let window = (cap - self.len).min(cap - tail);
let result = f(&mut self.buf[tail..tail + window]);
if let Ok(n) = result { self.len += n; }
result
}
fn pop_bytes(&mut self, n: usize) -> Vec<u8> {
let cap = self.capacity();
let out = (0..n).map(|i| self.buf[(self.head + i) % cap]).collect();
self.head = (self.head + n) % cap;
self.len -= n;
out
}
}
fn main() {
let mut ring = ByteRing::new(16);
// Successful write: closure fills the slice and commits 5 bytes
let n = ring.push_with::<&str, _>(|buf| {
buf[..5].copy_from_slice(b"hello");
Ok(5)
}).unwrap();
println!("committed {} bytes; ring.len = {}", n, ring.len);
assert_eq!(ring.len, 5);
// Failed write: Err propagates, ring is untouched
let err: Result<usize, &str> = ring.push_with(|_buf| Err("WouldBlock"));
assert!(err.is_err());
assert_eq!(ring.len, 5); // unchanged; automatic rollback
println!("after failed write: ring.len = {} (unchanged)", ring.len);
// Second successful write
ring.push_with::<&str, _>(|buf| { buf[..5].copy_from_slice(b"world"); Ok(5) }).unwrap();
let p0 = ring.pop_bytes(5);
let p1 = ring.pop_bytes(5);
println!("p0 = {:?}, p1 = {:?}",
std::str::from_utf8(&p0).unwrap(),
std::str::from_utf8(&p1).unwrap());
}ByteRing::push_with with a closure-owned write window, commit on Ok and automatic rollback on Err
11.4. UnorderedBuffer Phase-Commit as Kleisli Composition
The UnorderedBuffer lifts the ring from a typed element store to a variable-length byte store by maintaining two rings in tandem: a data ring of u8 containing raw datagram bytes and a metadata ring of packet descriptors each with a byte offset, a byte length and a padding count. The metadata ring is indexed by packet number; the data ring is indexed by byte position. A reader reconstructs datagram by looking up its descriptor in the metadata ring and slicing the data ring at the recorded offset and length.
The receive operation follows a three-phase commit protocol. In the first phase (allocation) the buffer checks whether the data ring's free tail has room for the maximum possible datagram. If not it pads the remaining tail bytes to force the next allocation to the head. All datagram bytes are thus contiguous (no packet straddles the wrap boundary). In the second phase (receive) the buffer hands a RingManyMutView over the allocated region to the caller via a closure that calls socket.recv_from(view.data_mut()) and reports the number of bytes written via view.set_modified(n). In the third phase (commit) and only if the receive succeeded the metadata ring appends a descriptor for the new packet and the data ring advances its tail by bytes.
Let be an error type. Define:
- as the allocation step (always succeeds unless the buffer is full),
- as the receive step (may fail with an I/O error),
- as the metadata commit (infallible once the receive succeeds).
The composed operation in the Kleisli category satisfies: (i) if any step returns , the chain short-circuits with and no subsequent step executes; (ii) the metadata ring is updated if and only if both and succeed; (iii) the observable packet sequence seen by a concurrent reader is unchanged unless the full chain returns .
Proof. By the Kleisli composition law ([eq:kleisli-comp]) and by the associativity law the chain may be read as . Property (i) is the left-zero law of the Result monad: Err(e).and_then(f) = Err(e) for any . A failure in any step therefore propagates without calling subsequent steps. Property (ii) follows because is only reached if returned (providing the view) and returned (providing the byte count); the metadata ring's is incremented only inside . Property (iii) follows from property (ii): a concurrent reader traverses the metadata ring's occupied slots, whose count changes only at the step. Since is not reached on failure the reader observes no new packet. Within safe Rust the chain runs under &mut self and the view uniqueness theorem excludes any reader for its duration. A lock-free reader on another thread also needs the occupancy count published by a release store and read by an acquire load. □
The following programme implements the three-phase structure. Each phase is its own function returning Result and the receive method chains them with ?. A simulated WouldBlock short-circuits at phase 2 and leaves the committed packet count unchanged. The programme prints the committed packets in the order they arrived:
#[derive(Debug)]
enum NetError { BufferFull, WouldBlock }
struct PacketBuffer {
data: Vec<u8>,
write_pos: usize,
packets: Vec<(usize, usize)>, // (offset, len)
}
impl PacketBuffer {
fn new(capacity: usize) -> Self {
PacketBuffer { data: vec![0u8; capacity], write_pos: 0, packets: Vec::new() }
}
// Phase 1: reserve space; the only phase that checks buffer capacity
fn alloc(&self, max_size: usize) -> Result<usize, NetError> {
if self.write_pos + max_size > self.data.len() {
return Err(NetError::BufferFull);
}
Ok(self.write_pos)
}
// Phase 2: write into the reserved region; simulates recv_from
fn recv_into(&mut self, offset: usize, payload: Option<&[u8]>)
-> Result<(usize, usize), NetError>
{
let bytes = payload.ok_or(NetError::WouldBlock)?;
self.data[offset..offset + bytes.len()].copy_from_slice(bytes);
Ok((offset, bytes.len()))
}
// Phase 3: commit the descriptor; only reached if both prior phases succeeded
fn commit(&mut self, offset: usize, len: usize) -> Result<(), NetError> {
self.write_pos = offset + len;
self.packets.push((offset, len));
Ok(())
}
// The ? chain: alloc >>= recv_into >>= commit
fn receive(&mut self, payload: Option<&[u8]>) -> Result<(), NetError> {
let offset = self.alloc(1472)?;
let (off, len) = self.recv_into(offset, payload)?;
self.commit(off, len)?;
Ok(())
}
fn read(&self, i: usize) -> &str {
let (off, len) = self.packets[i];
std::str::from_utf8(&self.data[off..off + len]).unwrap()
}
}
fn main() {
let mut buf = PacketBuffer::new(4096);
buf.receive(Some(b"market-tick-001")).unwrap();
println!("packet 0: {}", buf.read(0));
// WouldBlock: ? short-circuits at phase 2, commit is never reached
let err = buf.receive(None);
assert!(matches!(err, Err(NetError::WouldBlock)));
assert_eq!(buf.packets.len(), 1); // unchanged
println!("after WouldBlock: {} packet(s) committed (unchanged)", buf.packets.len());
buf.receive(Some(b"market-tick-002")).unwrap();
buf.receive(Some(b"market-tick-003")).unwrap();
println!("packet 1: {}", buf.read(1));
println!("packet 2: {}", buf.read(2));
println!("Total committed: {}, left-zero law holds.", buf.packets.len());
}Three-phase commit as a ? chain of alloc, recv_into and commit with WouldBlock short-circuit
The ? operator from §6.4 is the surface syntax for this chain. The closure passed to push_with uses ? to propagate any I/O error from recv_from. push_with returns the closure's Result unchanged and the enclosing function surfaces it to the caller with one more ?. The three-phase protocol takes three lines of application code. The type system guarantees commit on success and no commit on failure and the generated machine code is identical to a hand-written match chain with no allocation and no overhead.
Three of the abstract structures from §6 are present in these twenty lines of API: the ring buffer's state is a finite -coalgebra (§6.2), the view types are affine resources enforced by the affine monoidal structure (§6.5), and the three-phase commit is a Kleisli chain (§6.4) whose short-circuit property is the left-zero law of the Result monad. The API was designed for engineering reasons without appeal to category theory. These properties follow from the type system's rules.
References
- National Security Agency / Cybersecurity and Infrastructure Security Agency. The Case for Memory Safe Roadmaps. December 2023.
- The Rust Reference, §"Behavior considered undefined". doc.rust-lang.org/reference/behavior-considered-undefined.html. Accessed 2026.
- Girard, J.-Y. "Linear Logic." Theoretical Computer Science 50(1):1-101, 1987.
- Howard, W.A. "The formulae-as-types notion of construction." In To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism. Academic Press, 1980.
- GHC LinearTypes extension. GHC User's Guide. downloads.haskell.org. Accessed 2026.
- Matsakis, N.D. RFC 2094: Non-Lexical Lifetimes. rust-lang.github.io/rfcs/2094-nll. 2017.
- Jung, R., Jourdan, J.-H., Krebbers, R., and Dreyer, D. "RustBelt: Securing the Foundations of the Rust Programming Language." POPL 2018.
- Jung, R., Dang, H.-H., Kang, J., and Dreyer, D. "Stacked Borrows: An Aliasing Model for Rust." POPL 2020.
- Wadler, P. and Blott, S. "How to Make Ad-hoc Polymorphism Less Ad hoc." In POPL 1989, 60-76. ACM, 1989. doi:10.1145/75277.75283
- Reynolds, J.C. "Types, Abstraction and Parametric Polymorphism." In Information Processing 83, 513-523. North-Holland, 1983.
- Jacobs, B. Introduction to Coalgebra: Towards Mathematics of States and Observation. Cambridge University Press, 2017.
- Tokio contributors. Tokio: An asynchronous Rust runtime. tokio.rs. Accessed 2026.
- Rust Language Team. Asynchronous Programming in Rust. rust-lang.github.io/async-book. Accessed 2026.
- PyO3 contributors. PyO3 documentation. pyo3.rs. Accessed 2026.
- maturin contributors. maturin documentation. maturin.rs. Accessed 2026.
- The Rust Programming Language Team. The Rustonomicon: The Dark Arts of Unsafe Rust. doc.rust-lang.org/nomicon. Accessed 2026.
- Jung, R. MiniRust specification. github.com/RalfJung/minirust. Accessed 2026.
- Stroustrup, B. "Foundations of C++." In ESOP 2012, LNCS 7211, 1-25. Springer, 2012.
- serde contributors. serde documentation. serde.rs. Accessed 2026.
- The Rust standard library. Module
std::pin. doc.rust-lang.org/std/pin. Accessed 2026.