Java Posse, .Equals(), Inheritance, and the Liskov Substitution Principle

Continuing the conversation had by Raganwald, me, and a lot of the rest of the blogosphere:

The Java Posse Responds to My #Equals Issue
(If you don’t know the Java Posse, check out their website/blog/podcast. It’s good stuff.)

The answer they gave was an interesting one, which I’m still sitting on and working in my head. Here is Martin OConnor’s response, for those too lazy to read the (very interesting) thread:

Your class hierarchy is flawed. ThreeDeePoint does not naturally extend TwoDeePoint, because a Three Dimiensional point is not a kind of Two Dimensional point. They represent two very distinct concepts. Essentially, when you extend TwoDeePoint with ThreeDeePoint, you are saying that ThreeDeePoint is a special kind of TwoDeePoint. I would submit, therefore that the problems you are observing are less due to the impelmentation of Object.equals(), and more as a result of your chosen class hierarchy design.
[...]
What I was trying to explain, (although poorly), or more precisely hinting at, is The Liskov Substitution Principle. This is an Object Oriented design principle that states that any reference to a base class should be replaceable with a reference to a derived class without affecting functionality. What my previous post had attempted to say is that since the TwoDeePoint and ThreeDeePoint classes do not adhere to The Liskov Substitution Principle, the design, in this particular case is flawed.

(For those that don’t remember my “TwoDeePoint” and “ThreeDeePoint” example, check my post, “A Java Gotcha”, where I first get into the #equals/#compareTo issue.)

So, is it invalid for a 3DPoint to inherit from a 2DPoint? The general way this is phrased is “is it legitimate to say 3DPoint is-a 2DPoint”? Well, that depends on what your definition of “is-a” is.

After all, the semantics behind a 3DPoint imply it is a 2DPoint, as it has all the same qualities of a 2DPoint: it simply adds the idea of a third dimension to the existing definition. Semantically, a three dimensional point is a two dimensional point residing on a particular point in the three-dimensional axis, and it has all the capabilities of a two dimensional point on that particular plane.

On the other hand, the Liskov Substitution Principle gives a much stricter definition of “is-a”. I’d like to look at a colloquial definition of the principle, and then a formal definition, because there is a huge gulf between these things.

Colloquially, it basically says that Foo should not inherit from Bar unless Foo is-a-specialization-of Bar: that is, Foo is a limitation upon Bar. So the inheritance in that example is invalid: 3DPoint is not taking 2DPoint and limiting it, but it’s taking 2DPoint and extending it.

Adopting this approach to inheritance will substantially limit its use, and is going to lead to some repetitive code — in my example, all the 2DPoint methods would have to be re-implemented as 3DPoint methods. But it does side-step the #equals/#compareTo problem, in that a specialization will have to rely on the same #equals/#compareTo definition as its parent class.

And that’s where the rub is. Using the cite by way of Wikipedia, let’s look at the formal definition of this principle:

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

My rub is with the phrase “a property provable about”. Consider a type of a matrix (M) and a diagonally symmetrical matrix (S). Specifically, there exists M#setXY that sets the item at [X,Y] to a vaue. In S#setXY, we override it so that it also sets the item at [Y,X] to the same value as [X,Y] was set to (thereby maintaining symmetry). Now, S is a colloquial specialization of M, but it could be a violation of the substution principle, since it changes the postcondition of M#setXY: is the fact that the rest of the matrix remains unchanged in M#setXY constitute “a provable property”?

Assuming that “a provable property” is basically analogous to the precondition/postcondition properties, I suppose there is no reason that M#setXY has to specify that the rest of the matrix remains unchanged. What we would basically be arguing in this case is a very liberal interpretation of the role of preconditions/postconditions: the postconditions of M#setXY need not specify everything that M#setXY does, and the preconditions of M#setXY might not need be all true.

If this is the case, then calling a method becomes a very, very scary thing. It is now legitimate for me to implement M#setXY to set every item in the matrix to NaN, delete your hard drive, send out 3000 spam mails a second, and make some coffee. As long as M#setXY ends by setting [X,Y] to the given value, it is an acceptable implementation of inheritance.

So, if we deny this liberal interpretation, and then S is not a legitimate case for inheritance of M, because S#setXY does something which M#setXY doesn’t specify. So the specialization we’re talking about by way of the substitution princple is extremely limiting: basically, all you can do is throw a different sub-class of already-declared exceptions, return subclasses of already-declared return values, and add methods which do not intersect/interefere with the provable properties of any other method, including #equals/#compareTo.

This limits inheritance to very few cases. Certainly, the implementations of abstract class are allowed, assuming that the abstract class leaves enough breathing room (e.g. vague enough declared exceptions) for an underlying implementation. This can be seen, for instance, in Java’s AbstractCollection. Anything which tacks on a piece of non-identifying information or non-interfering functionality works just fine, too, although I’m having trouble coming up with a good example for either of those.

Some people older and wiser than me once asserted that no inheritance should be done on anything other than classes explicitly defined for inheritance (i.e. abstract classes). At the time, I thought that was extreme, and so I discounted the position. I’m increasingly starting to understand it, though, and I think I may be signing on.

Related posts:

1. Another Person Bit by Java Exposing the Implementation through Inheritance
2. A Java Gotcha
3. Commons-Lang and the equals()/compareTo() Debacle
4. Implementation Exposure Through Inheritance
5. Another solution to the Java equals/compareTo Problem (More or Less)