// HACKER NEWS — CYBERSECURITY
Why isn't mutable a subtype of immutable, or vice versa?
I remember the moment when I learned about immutability. It changed everything.
Periodically, in various programming language forums, the discussion comes up of why a certain language doesn’t provide the immutable and mutable variants of some data structure as subtypes or supertypes of one another. Now, it’s not impossible to do this, but it’s actually not formally correct to do so, and by doing so you’ll lose at least some of the type checking guarantees your language can usually make for you.
To understand why this doesn’t work, you have to remember the definition of a subtype. Namely, Liskov’s subsitution principle: a type S is a subtype of T if a value of type S can be used in every context where a value of type T is expected.
As usual when dealing with formal matters, this definition is strictly interpreted. Every really does mean every, not just most. (You might have learned the substitution principle as a mere recommended design pattern for OO classes, but formally speaking a true subtype has to fulfil this criterion.) A static type system which supports subtyping will have to prove this for you in order to pass your program through its type checker.
To illustrate this, let’s take the simplest compound data structure imaginable: the humble pair. Here are our operations on an immutable version.
(And a new constructor, but we’ll deal with that below.)
Now, it should be obvious that an immutable pair can’t be provided where a mutable pair is expected. A place that needs a mutable pair will presumably try to use of these two operations on it, which aren’t defined on an immutable pair, so there will be a typing error.
But why couldn’t it be the other way around? All of the operations provided provided by an immutable pair are also provided by a mutable pair, so it seems like we should be able to use a mutable pair wherever an immutable pair is expected.
The reason is more subtle. The substitution principle extends beyond the set of operations (methods) a type provides to the implicit contract which comes with those operations.
When we take the car or cdr of an immutable pair, we can depend on a contract which says the result will always be the same every time we call it on that pair. This contract means that we can, for example, safely calculate the hash value of the pair based on its contents, store it away in another data structure, and know that it won’t be different when we recalculate it later to try to retrieve it. (In other words, immutability is a prerequisite for hash consing!)