Why isn't mutable a subtype of immutable, or vice versa?
summary
Mutable and immutable data structures cannot be subtypes of each other because they violate the Liskov Substitution Principle. A true subtype must be usable in every context of its supertype, but mutable types break the implicit contract of immutability, such as the guarantee that a value remains constant for hashing. Therefore, these must be treated as distinct types to maintain formal type-checking guarantees and prevent runtime errors.
key points
- An immutable type cannot be a subtype of a mutable type because it lacks the necessary mutation operations required by the mutable contract.
- A mutable type cannot be a subtype of an immutable type because it violates the stability contract, where operations like hashing rely on the value never changing.
- Ad hoc polymorphism through type classes or interfaces allows functions to operate on both types using shared methods without incorrectly implying a subtype relationship.
who should read it
Software engineers and computer science students interested in type theory and the formal design of programming languages.
discussion positive
consensus
Commenters generally agree that mutability is a complex concept that can be treated as a property of a type, a variable, or a memory address depending on the language's design. There is a a broad consensus that 'read-only' and 'immutable' are distinct concepts, where the former refers to an access restriction and the latter refers to a state that cannot change. The discussion concludes that whether mutability belongs in a type system is a design choice often driven by the need to match hardware realities or prevent specific concurrency errors.
top insight
The most valuable insight is the distinction between mutability and aliasing, where pairing mutability with exclusive access (as seen in Rust) solves the subtyping objection. By ensuring that a mutable reference is exclusive, code requesting an immutable reference will never observe mutations, effectively creating a strict subtyping relationship. This perspective shifts the focus from whether a value is mutable to how access to that value is controlled.
Generated by an LLM from the article and thread. Check the sources before relying on it.