Why mutable and immutable types can never be subtypes of each other
Why isn't mutable a subtype of immutable, or vice versa?
A common question in programming language forums: why aren't mutable and immutable variants of a data structure subtypes of one another? The answer lies in Liskov's substitution principle, which requires that a subtype be usable in every context where its supertype is expected. An immutable pair lacks mutating operations, so it can't substitute for a mutable pair. Conversely, a mutable pair can't substitute for an immutable pair because it doesn't guarantee the contract that repeated reads return the same value—a contract essential for hash consing. Thus they must be separate types. Ad hoc polymorphism (type classes, interfaces, duck typing) can provide shared read operations without a subtype hierarchy.
Because of this, immutable and mutable pairs have to be completely different types.
- bruce343434
So really there are 2 orthogonal axes:
- A: can I change the value
- B: can something else change the value (can I depend on a predictable stable value)
Because the axes are orthogonal, hierarchical based subtyping (inheritance) breaks, but type classes (interfaces), ad hoc polymorphism, would work.
In C, const answers A
In rust, due to pointer aliasing restrictions (either one mut pointer xor any amount of read only pointers), (lack of) mut answers both A and B
- js8
I feel like the explanation is overcomplicated. Types are properties of values, not variables. Mutability is a property of variable, not of a value.
So it's kind of a categorical error. (I want to joke here that all categorical errors are just type errors in category theory.) When we speak of "type of a variable", we mean this variable can only be assigned (bound to) values of certain type. This has nothing to do with whether it can be reassigned (i.e. mutability).
So you don't even need the notion of subtyping to explain this.
Also, one could probably define variable as a monad over its type.
- BlackFly
If you pair mutability with exclusive access then you have handled the objection raised by the (some may say overly) strict definition of subtyping here and also the attempt to argue over the objection. No code which asks for an immutable instance will ever observe the mutability because the ask for an immutable reference is exclusive. Therefore, you could pass the mutable reference but so long as something holds onto that reference the mutability is no longer available to other code.
So mutability xor aliasing provides this strict subtyping relation. Of course, you also then need ways of loosening this by providing objects without such a contract and you enter the land of interior mutability, where again the mutable methods can be understood as a part of a subtype because a holder of the reference without mutable methods was explicitly told that there was no the guarantee that the object wouldn't change.
- Sharlin
As a total aside, the names `car` and `cdr` for "head" and "tail" are honestly some of the most baffling historical relics in all of computing.
- raffael_de
as far as my set theoretical intuition goes, immutable has to be a subtype of mutable, if anything.