Why mutable and immutable types are never subtypes of each other

Anyone migrating from Java, Python, or JavaScript to Rust quickly runs into an oddity: why can't a &mut T reference simply "be" a &T in any context, and vice versa? Intuitively, mutable data seems to have everything immutable data has, and then some. A post on the blog crumbles.blog, which climbed to the top of Hacker News in September, tackles this question head-on, without mentioning Rust even once, yet answers exactly what trips up the language's type system for newcomers.

The principle most people learned wrong

The answer starts with the Liskov substitution principle, but not the simplified version that usually shows up in object-oriented programming courses. Formally, a type S is a subtype of T if a value of S can be used in every context where a value of T is expected. The post insists on the strictness of the word "every": it's not "in most cases," it's always, without exception, because that's what a static type checker has to prove before accepting your program.

This requirement changes what counts as a type's contract. It's not enough to compare the list of available operations; you have to compare the guarantees each operation promises to uphold.

The immutable-and-mutable pair experiment

The author uses the simplest possible example: a pair (cons/car/cdr, the two-value construct from the Lisp/Scheme tradition). The immutable version offers three operations: building the pair and reading each of its two fields. The mutable version adds two more: set-car! and set-cdr!, to swap the values after creation.

It's obvious that an immutable pair won't work where a mutable one is expected: it lacks set-car!/set-cdr!, and the code breaks on the first attempt to call them. The subtle point is the reverse path. A mutable pair has all the operations of the immutable one, so why couldn't it replace an immutable pair anywhere?

The answer lies in the implicit contract of car and cdr on an immutable pair: called twice on the same pair, the result is always equal. This contract makes it possible, for instance, to compute the pair's hash once and safely reuse that value (the hash consing technique the post cites). A mutable pair can't make that promise: someone might call set-car! between the two reads. That's why the two have to be completely separate types, even though they share read operations.

What this explains about &T and &mut T

Rust doesn't model Lisp pairs, but it solves exactly this problem with its two forms of references. A &T (shared reference) carries the same contract as the post's immutable pair: while it exists, the borrow checker guarantees no one else will mutate the value it points to. A &mut T (exclusive reference) is the mutable pair: it grants write access, but in exchange demands total exclusivity, no other reference, mutable or not, can coexist with it.

This explains why the compiler accepts passing a &mut T where a &T is expected (the so-called reborrow, something like &*minha_ref_mut), but never the other way around without unsafe:

fn le(valor: &i32) -> i32 { *valor }
fn escreve(valor: &mut i32) { *valor += 1; }

let mut x = 10;
let r = &mut x;
le(r); // ok: &mut i32 becomes &i32 at this point
// escreve would need &mut i32; a &i32 never becomes that again

This isn't classical subtyping in the sense the post uses (Rust has no class hierarchy for primitive types), but the contract-based reasoning is the same: whoever holds a &mut T can temporarily give up the ability to write and behave like a &T, because that only restricts what it can do. The reverse path would violate the guarantee every &T carries, that the value won't change while the reference exists. It's the same rule as the post's car/cdr, with different names.

A practical effect of this rule shows up in HashMap. If the key uses RefCell or some other form of interior mutability and someone changes the value after it's inserted, the hash computed at insertion time no longer matches the hash recalculated during lookup, and the entry silently disappears. The std documentation itself warns about this: it's the post's hash consing breaking down in practice, decades later, in a container far more modern than a Scheme pair.

Traits instead of hierarchy: the way out the post already anticipates

The original article also explains why this doesn't condemn mutability and immutability to live with no shared code at all: statically typed languages solve this with type classes (Wadler and Blott's work is cited directly), which the post equates to interfaces, traits, or roles depending on the language. Traits in Rust are exactly this mechanism. A trait can declare a method that takes &self, and another, in a separate trait, that takes &mut self, without either depending on the other to form a subtyping chain.

Index and IndexMut from the std library are the most direct example: Vec implements both, but they're distinct traits, and a function that only receives &Vec can never index through IndexMut, because the compiler doesn't even offer that signature. It's the same design as the post, with car/cdr playing the role of Index::index and set-car!/set-cdr! playing the role of IndexMut::index_mut.

What this leaves for those coming from another language

In Java or TypeScript, it's common to treat a "read-only view of a mutable object" as if it were a subtype by convention, a Readonly that developers themselves promise to respect, with the compiler proving nothing. Rust refuses that shortcut: the separation between &T and &mut T is enforced by the borrow checker, not by good intentions, and it's what underpins the promise of data-race-free concurrency the language sells.

It remains open, and the post doesn't get into it, how this reasoning interacts with lifetime variance, where Rust does allow a kind of subtyping (&'long T can replace &'short T). That's a different axis from mutability, but it's the obvious next place to dig deeper for anyone who wants to understand how Rust's type system formally decides what can replace what.