Why isn't mutable a subtype of immutable, or vice versa?

The piece explains why mutable and immutable variants must be distinct types rather than forming a subtype relationship, grounding the argument in the Liskov substitution principle: a subtype must be usable in every context that expects the supertype. An immutable pair lacks mutator operations, so it cannot stand in where a mutable pair is required. Conversely, a mutable pair cannot safely replace an immutable one because callers of immutable pairs rely on an implicit contract that repeated reads return the same values (enabling hashing, hash consing, stable keys, etc.). The example of pairs contrasts operations like icons/icar/icdr for immutable pairs with mcons/mcar/mcdr/set-mcar!/set-mcdr! for mutable pairs and shows that allowing either direction of subtyping would break the guarantees clients depend on.

Languages address the practical need to use the same read operations across both kinds without making them subtypes through ad hoc polymorphism. In statically typed systems, type classes (Wadler and Blott), interfaces, traits, or roles let both mutable and immutable pairs implement a common pair abstraction that offers car/cdr semantics while preserving mutator separation; the type system enforces what contracts a function expects. Dynamically typed languages rely on duck typing and runtime checks, but checking for absence of mutators is uncommon and error-prone, which is why explicit polymorphic abstractions are safer for preserving guarantees.