The Correct Use of Inheritance

Perhaps the most subtle relationship in object-oriented programming is that of inheritance.  Many object-oriented languages, including Java, distinguish between classes and interfaces, as a reaction to the problems languages such as C++ faced with multiple inheritance.  This is a complex issue I will address in a later post.  Now I want to focus on the logical relationships involved in inheritance.  In order to avoid the class/interface dichotomy, I will use the notion of a subtype.  A type A is a subtype of B if it inherits from it, whether both A and B are classes, both are interfaces, or A is a class and B is an interface.  (Java uses the verb "extends" for the first two cases and "implements" for the third.)

An element of a subtype A may be used whenever an element of the supertype B is indicated.  For example, suppose we have a type called Set that represents mathematical sets.  It has a number of implementations inheriting from it, including ArraySet, which holds the elements of the set in an array, and HashSet, which holds the elements in a hash table.  The Set type has various methods, including add(Object x), which adds an element to the set; get(), which returns an arbitrary element of the set; and has(Object x), which returns true if and only if x is in the set.  Since a set can't contain the same object multiple times, we put a precondition on add(Object x) requiring that x is not already in the set: !has(x).

Unfortunately, our HashSet implementation doesn't support null as an element in the hash table, so we add another precondition to add(Object x), stating that x can't be null: x != null.  Now, suppose we have a client C that uses our code, and receives a parameter s of type Set.  When the programmer of the client code reads the contract for Set, he sees only one precondition: !has(x).  He will certainly be careful not to insert the same element twice, for example by using the following code:

if (!s.has(element)) s.add(element);

But he has perfect confidence in the following piece of code:

if (!s.has(null)) s.add(null);

He will be rudely surprised, therefore, when this actually bombs on him somewhere inside the call to add in our HashSet implementation.  He may not even have known about the existence of HashSet, since he received the object s, which happened to have this type, as a parameter.  He is the proverbial innocent bystander, and should be protected from this kind of problem.  After all, he kept his side of the contract, and has every right to expect us to keep our side!

This demonstrates a general problem, which will manifest itself whenever the precondition of a method in a subtype is stronger (that is, requires more) than that of the supertype.  The rule must therefore be that subtypes are not allowed to strengthen method preconditions.  We will have to add a precondition to Set.add, to warn potential users that some subtypes may not accept null as a parameter.  Our ArraySet implementation can now weaken the precondition by removing this requirement.  This is perfectly legal; clients that use ArraySet objects through the Set supertype will not be allowed to call add(null), but clients that use ArraySet directly will be able to enjoy the extended functionality.

Since we restrict Set.add not to accept null parameters, it looks like we can now put a postcondition on Set.get, stating that it will never return null.  This will work well for HashSet, but will fail for ArraySet, which does accept null elements.  By adding this postcondition to Set.get, we have again harmed innocent bystanders; in this case, a client of Set who happens to receive a HashSet object as its own parameter.  Such a client feels perfectly justified in writing the following code:

if (!s.isEmpty()) System.out.println(s.get().toString());

He is careful to check the precondition of get, which states that it can't be called when the set is empty, and he is therefore entitled to rely on get's postcondition and to expect that no NullPointerException will be raised on the call to toString.  He may not even be aware of the existence of ArraySet, and of the fact that it doesn't have this postcondition.  The rule for postconditions therefore must be that postconditions must not be weakened by subtypes, although they can be strengthened; this enables clients of the subtype to benefit from extra features it supports.

These rules are consequences of Liskov's Behavioral Substitution Principle, which states that properties of the supertype must still be true of subtypes.  This principle is true of all inheritance hierarchies which allow subtypes to be used as elements of their supertypes.  After all, this is what a subtype means: if A is a subtype of B then every instance of A is, by definition, also an instance of B.  (This does not apply to private inheritance in C++, which doesn't imply a subtype relationship, but it does apply to public inheritance in C++, as well as to all inheritance relationships in Java, C#, and similar languages.)  The principle is true whether or not the developer uses design by contract, and writes contracts explicilty; a violation of the principle is still a bug, and a nasty one at that.  Using design by contract makes it easier to prevent such violations in the first place.

Any developer who is ignorant of Liskov's Behavioral Substitution Principle can't claim to understand object-oriented programming, and should be prevented from writing any kind of inheritance relationship!