Why can't a mutable interface/class inherit from an immutable one?

Question

I've heard people say things like "B can't inherit from A because A is immutable and B is mutable".

My understanding of inheritance in Object-Oriented Programming is that you use it to add behaviors/methods, such as set methods.

interface A {
   getX(): X
}

interface B extends A {
   setX()
}

You can't remove methods/functionality inherited from other interfaces/classes, only override them. Mutability seems like added functionality (e.g. adding setters). Adding mutability may be unwise in general, but it's making a subclass do something the parent cannot, which is how OOP is supposed to work, no? Is there something special about mutability that changes that?

I assume I'm hearing the above statement from smart people. Am I misinterpreting something? What am I missing? I usually deal in the context of the JVM (Java/Kotlin), if that makes any difference.

Answer 1

Adding mutability may be unwise in general, but it's making a subclass do something the parent cannot, which is how OOP is supposed to work, no?

A key concept in OOP is that of substitutability: if I promise you that I will give you an object of class A, I can safely substitute any sub-class of A, and your code will still behave as expected. This is often summed up by referencing the "Liskov substitution principle":

Let ϕ(x) be a property provable about objects x of type T. Then ϕ(y) should be true for objects y of type S where S is a subtype of T.

To paraphrase to your example:

Anything you can prove about the behaviour of class A should also be true of sub-class B.

As you rightly say, that means you can't remove methods, only add new ones; similarly, you can't narrow the input allowed in those methods, only widen it. Less obviously, it means that you can't widen the output of those methods: there is a provable behaviour of A that getX will return an instance of X; if B::getX returned a value that is not an instance of X, it would violate that behaviour, so B would not be substitutable for A.

This concept of "contravariance of input, covariance of output" is one example of substitutability, but more broadly we can talk about behavioural sub-typing: the idea that code relies not just on the structure of the types it works with, but general behavioural properties. Changing these behaviours in sub-types, even if the language does not provide tools to enforce them, is generally a bad idea.

To return to the question then: if immutability is a "provable property" of class A, then it should also be true for sub-class B. To make it less abstract, we can try to think of a scenario where code might rely on this property:

• Consider a container object which has a large list of objects.
• If two objects are identical and immutable, you can save memory by storing two pointers to the same object, rather than two copies.
• If you know that class A is immutable, and your list only accepts instances of class A, you can implement this optimisation unconditionally.
• Since B is a sub-class of A, two currently-identical instances of B can be added to the list. They will be de-duplicated, and only one instance stored.
• However, since B is mutable, one of those instances can be mutated from outside the list. When they are retrieved, they should now be different, but the list will return one of them twice.

Answer 2

My understanding of Inheritance in Object-Oriented Programming is that you use it to add behaviors/methods, such as set methods.

A lot of mainstream object-oriented languages, and Java and Kotlin are no exception, lump multiple separate things together under the single mechanism of Inheritance.

So, in some sense you are right: inheritance is used to add behaviors, in particular add behaviors in such a way that you only need to describe the difference between the behaviors of the subclass to the superclass. This is sometimes called Differential Code Re-Use.

However, the problem is that this is not the only thing inheritance does. Inheritance also does something else: it creates a Subtyping relationship between the superclass and the subclass. In other words, B is not just a subclass of A, it is also a subtype of A. Which means inheritance is not just used to add behaviors, it is also used to add contracts.

There are languages where those two aspects are separate, where there are separate mechanisms for differential code re-use and subtyping. But they are not mainstream.

(Unless you count dynamic languages which only have differential code re-use as part of the language, and the typing only happens in the programmer's head.)

You can't remove methods/functionality inherited from other interfaces/classes, only override them. Mutability seems like added functionality (e.g. adding setters). Adding mutability may be unwise in general, but it's making a subclass do something the parent cannot, which is how OOP is supposed to work, no? Is there something special about mutability that changes that?

If you are looking at it only from the point of view of differential code re-use, then you are correct: this is exactly what it is designed for. You can re-use the code from A and you only define what are the differences between B and A. But the problem is that the only way to achieve differential code re-use in Java and/or Kotlin is inheritance, but inheritance also creates a subtyping relationship. And that means, that B needs to obey all the rules for subtyping.

So, what are those rules for subtyping?

Today, the best way we know how to characterize subtyping, especially in the presence of mutability and aliasing, is what is commonly called the Liskov Substitution Principle or LSP.

The LSP was introduced by Barbara Liskov in a keynote address at the OOPSLA conference 1987, titled Data Abstraction and Hierarchy:

If for each object o₁ of type S there is an object o₂ of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o₁ is substituted for o₂, then S is a subtype of T.

A similar definition is also given in A Behavioral Notion of Subtyping (1994):

Let ϕ(x) be a property provable about objects x of type T. Then ϕ(y) should be true for objects y of type S where S <⦂ T.

Now, these are some pretty abstract definitions. The main advantage of these definitions, which are based on the behavior of the programs, is that these definitions also work for mutability and aliasing. Earlier approaches were less precise, e.g. the co- and contra-variance rules for functions do not work with mutability or aliasing, and the proof-theoretic approach by Bertrand Meyer only works for mutability.

Thankfully, we can derive some rules which are simpler to interpret than those abstract definitions:

There are three static restrictions for subroutine signatures:

1. Subroutines are contravariant in their parameter types.
2. Subroutines are covariant in their result types.
3. Subroutines in a subtype can only throw exceptions which are subtypes of the supertype's subroutine's exceptions.

#1 and #2 are not new, they are simply the standard variance rules for functions – they had been known for decades. #3 was already stated by Meyer, and is actually the same thing as #2 if you consider exceptions part of the result type of a subroutine.

So far, none of this should be surprising.

What's more interesting, are the four behavioral restrictions. These are restrictions on the runtime behavior of instances of subtypes. They are stated in the form of invariants (statements that must always be true, where "always" means "after construction and before and after every subroutine call"), preconditions (statements that must be true before every subroutine call), and postconditions (statements that must be true after every subroutine call):

1. Preconditions cannot be strengthened in a subtype.
2. Postconditions cannot be weakened in a subtype.
3. Invariants must be preserved in a subtype.
4. The History Constraint.

#1 and #2 are again just re-statements of the signature constraints #1 and #2 (which are just the variance rules for functions) in terms of behavioral contracts expressed as preconditions and postconditions. #3 was already known to Meyer.

One of the two big things and big innovations about Liskov's and Wing's way of phrasing this, is the History Constraint. The history constraint says that, an observer who observes an instance of the subtype through the interface of the supertype must not be allowed to observe a history that he could not observe of an instance of the supertype. (The other bing thing is the idea of "substitutability", i.e. that B is a subtype of A IFF instances of B can be substituted by instances of A.)

There's a lot to unpack here. So, we have "an observer", which is simply a program O. This program is passed an instance of A, and it can call any subroutine it wants, however often it wants, whenever it wants. Now, you pass it an instance of B, which is perfectly fine, since B is a subtype of A, and thus, any instance of B is also an instance of A.

We also have a different program, the "manipulator" M, which gets passed the same instance of B, and which can use any subroutine of B to manipulate this instance.

What the history constraint says, is that no matter what crazy things M does to the instance and no matter what clever tricks O uses to inspect the instance, it must be impossible for O to observe a history that it could not observe if M only knew about A.

And that is the problem with your code. Your code does not violate any of the signature constraints and it does not violate any precondition or postcondition, i.e. it does not violate the first two behavioral constraints.

It may or may not violate behavioral constraint #3 regarding invariants. Unfortunately, you have not really shown how your interfaces are used and what your requirements are, so we don't actually know what the invariants of A are. But it is possible that A could have the invariant that X never changes after construction. If that were the case, then B would violate the constraint that invariants must be preserved.

This, BTW, demonstrates an important lesson about practical implications of the LSP. The LSP itself talks about "for all programs the behavior is unchanged" and it simply mentions "provable properties". But in a real world, that is too restrictive. For example, an important reason for subtyping is that subtypes being special cases may allow more efficient implementations of subroutines. But, being faster is technically a changed behavior, and thus the LSP wouldn't allow you to make specialized, faster, subtypes.

Similarly, "any provable property" is incredibly broad, since there may be a lot of weird, obscure properties that are provable about a program.

That's why, in the real world, when we analyze whether a subtype violates the LSP, we must always look at the contract of the supertype. In other words, instead of looking at all possible programs and all possible provable properties, we are only looking at the subset of programs that we actually want to write and we are only looking at the subset of desirable, relevant properties. And the way we do that, is by specifying the contract of the supertype. Ideally, in some formal language, but more often than not simply in the documentation, or even implicitly, i.e. without even stating the contract out loud.

Since you don't specify the contract of A, in particular not its invariants, we can't really tell whether or not B violates them or not. The only thing we can tell is that it would be possible to specify an invariant that is guaranteed to hold for A but is violated by B. In the pure phrasing of Liskov, this is enough to be a violation, but in reality, we would look at what the actual guarantees are that A makes in its documentation.

However, whether or not B violates the invariant constraint is irrelevant, because it definitely violates the history constraint, in a rather trivial manner: since A is immutable, it is impossible to construct a history where X has different values at different points in time, yet, that is possible with B. Therefore, B violates the history constraint, which means B is not a subtype of A. (Or, since Kotlin is not actually able to prevent you from doing this, we should alternately say that it is not type-safe to make B a subtype of A.)

This shows why Liskov's and Wing's innovation was so important. The old variance rules for functions could not deal with mutability. The proof-theoretic approach of Meyer could not deal with aliasing. Only the behavioral approach plus the history constraint can actually deal with the problem caused by mutability plus aliasing.

Why is this important? Where can this break?

Imagine, A is written in 2018 by a programmer in Brazil. In 2019, a programmer in New Zealand writes a nifty library foolib which uses A. Because A is immutable, this programmer can use some clever tricks to speed up their library, like memoizing the value of X and never ask for it again. In 2020, a programmer in Hungary writes B. In 2021, a programmer in Canada writes a nifty library barlib which uses B. Since B is mutable, they can do some nifty tricks like storing intermediate results in X to speed up their library. In 2022, you write some program using B which uses both theses nifty libraries. So, you construct a single instance of B and pass that to both libraries to do their nifty processing.

Boom. foolib blows up because barlib is manipulating what foolib thinks is a perfectly safe immutable A instance behind its back.

Even worse: foolib doesn't blow up, but gives wrong results!

Problems like this can only happen when you have aliasing (i.e. different pieces of code referring to the same instance) and mutability. And only the history constraint can protect you from this.

Let's examine one of your questions again:

it's making a subclass do something the parent cannot, which is how OOP is supposed to work, no? Is there something special about mutability that changes that?

Now we can look at this a bit more precisely. The problem is not that B can do something that A cannot do. The problem is that B can do something that breaks A's contract. The problem is not "doing something that A cannot do", but "doing something that A shouldn't be able to do".

You are not merely adding new behavior. You are also changing existing behavior. For example, adding a new, mutable field, would have been perfectly fine. The precise problem is that through allowing to mutate X, you have not only added the subroutine setX, you have also implicitly changed the behavior of getX, which before had the guarantee that it always returns the same value, and you have now removed this guarantee.

Answer 3

Adding setters is neither always strictly adding functionality, nor removing it. Not even if it is for additional state. Rather, it modifies pre-existing functionality.

The crucial point is whether you subvert the inherited contract, which can only be answered by looking at it. Also, most classes are not designed for inheritance, as that is considerable added and often wasted effort.

If the parent guarantees that certain state of the object, as observed through the interface, or the object itself, is immutable, you are stuck with that.
On the other hand, if it only doesn't provide the interface to modify it itself, you might be able to provide an expanded/additional interface for modification.

Beware of implicit, assumed, or vague contracts though. "I never actually said" will rarely satisfy users.

Answer 4

An interface is a collection of methods, but it is also a promise about behaviour. The specificity of that promise may vary massively of course.

There is a big difference between

• You can't mutate x.
• Noone can mutate x.

If the documentation for a class or interface says that it is immutable you are breaking that "contract" by creating a mutable subclass or implementing the interface for a mutable class. Implementing a subinterface implies implementing the parent interface, so defining a mutable subinterface of an immutable interface generally makes no sense, there would be no way to implement the interface correctly.

If the documentation for the class or interface does not say anything about mutability then you are not breaking any contract by creating an implementation that allows mutation.

Answer 5

What exactly is “immutability”? As an example, Objective-C has many classes that just have no methods to explicitly modify their instances. These classes, like NSString, are not immutable as a language feature, but through a lack of mutating accessors. In C++, the same class can have const and non-const instances, with some methods marked so they can be used for const objects. The declaration that the compiler sees does not necessarily match whether the object is actually const or not.

Now take a string class with an expensive hash function whose value is cached after the first use. Caching that value modifies the object, but not the behaviour except for speed. Does that affect mutability?

There may be languages that have explicitly “mutable” and “immutable” classes and don’t allow deriving a mutable from an immutable class. In other languages, you can do this but it is “asking for trouble” so you don’t.

Again, in Objective-C, NSMutableString is a subclass of NSString. You are supposed to know the consequences and avoid them. (Making a copy of a String often avoids problems at zero cost for immutable strings, because copy for immutable strings just increases the reference count. If you try to use a mutable string as a dictionary key, an immutable copy will created).

Answer 6

You can use goto in many modern OO languages like Java, C#, and C++. Just don't though, mkay?

In your example though the interface just specifies that you can get a value 'X'. It shouldn't matter to the caller whether the value is mutable or not, or if it's computed from two other values, or reads it from a file, or anything else. If it provides the ability to get an 'X' value, that fulfils the contract. Interfaces by their definition aren't immutable, they have to be implemented and the values have to come from somewhere. Passing around an interface that doesn't include setters to methods that have no reason to be changing the properties makes sense to me.

Immutability makes sense if you want to write programs in a functional style and there are benefits to that approach, but it isn't the only way to program and not the end-all-be-all. I wouldn't go inheriting interfaces and adding setters for the values if there wasn't a good reason for it though.