JavaWorld Forums: The most misleading article!

I will hereby conclude that using 'instanceof' is bad, and 'getClass()' is the only correct way of implementing equals. Less interested readers may want to skip to the conclusion at the end :-).

Pinocio's argument is based on the following assumptions:

A1. Equality needs to compare like-for-subtype.
A2. LSP holds when you use an instanceof implementation of .equals().
A3. LSP holds in general as a good design principle.
A4. That the Java programming language solely uses good design in its implementation, and thus reading examples of coding in the Java language will be examples of good design.

The following are unarguable statements of fact:

S1. Using '.getClass()' provides an implementation of a type-for-type comparison; specifically, it denies type-for-subtype comparisons.
S2. Using 'instanceof' provides behaviour where type-for-subtype comparison in one direction, as well as type-for-type comparisons.
S3. The equals contract indicates whether some other object is "equal to" this one. The contract is unambiguous in its specification: It provides an equivalence relation on non-null references [i.e., it is reflexive, symmetric, and transitive, and that equals(null) is false]
S3a. It is reflexive; i.e. x.equals(x) is always true
S3b. It is symmetric; i.e. x.equals(y) should return true IF AND ONLY IF y.equals(x) returns true
S3c. It is transitive; i.e. x.equals(y) and y.equals(z) implies x.equals(z)
S3d. It is consistent; that is, they return the same value over multiple calls with the same arguments
S3e. For any non-null x, x.equals(null) returns false.

S1 and S2 are observations about the behaviour of the code examples as shown. S3 is from the equals() method spec, as linked in the references.

I will conclude this argument by showing:

P1. Equality should only compare type-for-type; using type-for-subtype leads to a violation of the equality contract (either symmetry or transitivity).
P2. LSP isn't held for an implementation of 'instanceof', despite this being the main argument proposed for using it.
P3. LSP isn't held for a vast number of Java objects in any case.
P4. That LSP is not a proven theory; it was a postulated principle.
P5. The interpretation of LSP applying to Java classes and the extends relation is in fact false.

--- Proof follows ---

Pinocio wrote:
"You have described [the contract specifications] right, but you do not apply it correctly in your article. Your Point3D violates the contract in Point2D not just adds new behavior. Point2D equals() contract says when any two Point2D instance are equals, but Point3D (which IS Point2D) changed this contract."

No, it doesn't. You misunderstood the contract. Statements S1 and S2 describe two behaviours that are incompatible with each other. You cannot conclude that S1 is false because you assume S2 is true; conversely, it is not possible for me to conclude that S2 is true because I assume S1 to be false. All the description of the equality method is that it "indicates whether some other object is "equal to" this one." (S3), from which it is possible to prove neither S1 nor S2.

The contract, as shown by the good code example in the article, explicitly states that the two types must be the SAME (S1). Thus, Point2D can be compared with Point2D, and Point3D can be compared with Point3D, but it is never the case that Point2D can be compared with Point3D. In fact, this is clear from the definition of a point in 2-d space and one in 3-d space; a single (x,y) co-ordinate defines a line in 3-d space; and since a line and a point are different, they are incomparable. Your assumption A1 does negate S1, but you fail to show that your assumption A1 is valid.

You understood it as:

"If somewhere in the program you decide to pass an instance of Point3D (which extends Point2D) as the second parameter, paint() will not be called, because Point3D implementation violates the contact of Point2D." (A1)

An instance of Point2D can NEVER be equal to an instance of Point3D. For some strange reason, you are assuming (A1) that it can; then claiming that the code does not do what you expect (S2). You are correct in observing that .getClass() does not permit this; however, you never discharge your assumption A1.

Consider other implementations of Point/3D:

public class Point {
int points[];
public Point(int x, int y) {
points = new int[2];
points[0] = x; points[1] = y;
}
public Point3D(int x, int y, int z) {
points = new int[3];
points[0] = x; points[1] = y; points[2] = z;
}
}

-- OR --

public abstract class Point {
int x, y;
}

public class Point2D extends Point { }
public class Point3D extends Point { int z; }

(with obvious methods for constructors and so forth missed out).

In both these cases, regardless of whether 'instanceof' or '.getClass()' is used to compare them, an instance of a 2-D point will never be equal to a 3-D point. Why should it be any different when implemented as shown in the article? The answer; it shouldn't. They are DIFFERENT types, even though one inherits from another.

These examples, including the Point in the article, are all showing the same thing. Using an implementation of S1 will give consistent behaviour for any of these implementations; using S2 will result in inconsistencies depending on which implementation is chosen. Thus, S2 is negates the equality contract (S3d) if the implementation is refactored.

Let's take the devil's advocate approach. Assume A2, that your interpretation of LSP is correct, and that using instanceof will guarantee the LSP behaviour.

You cite as your example:

"void example(Point2D aFirstPoint, Point2D aSecondPoint)
if (aFirstPoint.equals(aSecondPoint))
paint();"

and then claim that using 'instanceof' is the only implementation that gives the same result substituting aSecondPoint with an instance of Point3D. Whilst this is true, the reverse is not; I can substitute aFirstPoint with an instance of Point3D (aSecondPoint being Point2D) and get different behaviour than if both were Point2D.

This is an example of the asymmetry implicit in the 'instanceof' operator, and this asymmetry violates S3b. This is enough to show that A1 and A2 do not hold.

Importantly, neither implementation (getClass/instanceof) gives the so-desired LSP property.

A counter example has been found that invalidates your assumption A2; using neither 'instanceof' nor '.getClass()' provides the behaviour of the LSP.

So now we know A2 to be false; this proves P2.

I go further to show that A3 is also false; that LSP holds as a good design for OO systems. I do so by again showing a counter example (of which there are many hundreds in the Java language). Recall again that Pinocio's interpretation of the LSP is:

"if you decide to create a class B extending the class A , then you must be able to SUBSTITUTE an instance of the class A with the instance of class B anywhere in the program"

I have shown above that this does not hold using implementation of 'instanceof' for equals (and acknowledge that using 'getClass()' it also does not hold). Now I will show that the LSP does not hold of many other objects:

o Object defines .toString()
o Object's default implementation of .toString() returns results similar to "123456@java.lang.Object"
o Non-object subclasses override .toString() to change behaviour to print out a more meaningful result

Thus, I can write a program:

public boolean LSPHoldsFor(Object object) {
return object.toString().contains("@");
}

When I call the code with:

LSPHoldsFor(new Object());

I get the desired result 'true'.

Now I replace it with an subtype of Object. I choose, at random, a String/Vector/LinkedList/ArrayList/HashSet/SortedSet/Component ...

LSPHoldsFor(new String() / new Vector() / new LinkedList() / new ArrayList() / ... )

ALL return false.

I can do the same thing using your 'compare' method, too:

compare(new Object(), new String()); -> returns false
compare(new String(), new String()); -> returns true

So, either A3 is correct, and that String/Vector/LinkedList/ArrayList... are all incorrectly implemented, or assumption A3 is incorrect and the code works correctly.

A3 is incorrect because (in general) every overridden method exists to change the behaviour of the superclass. Such behaviour would be visible to a caller; and since overridden methods are in classes that are a sub-type of an overridden class, the use of overriding will (in general) violate the LSP EVERY TIME. Note that the methods are not actually implemented incorrectly; but whereas the LSP assumes exactly the same behaviour, in actual fact they obey its contract. You can have two methods, implemented differently (and that give the same result), but that obey the same contract. (Consider the implementation of 'add' in 'HashSet' and 'TreeSet'. They both obey the same contract -- they are inserted into the collection without duplicates -- but they work in a different manner that is visible to the outside.)

You cannot even argue that Object should be considered a special case; there is nothing in your interpretation of the LSP that deals with special cases. Even if it did, you can come up with further counter-claims:

LSPHoldsFor(Component component) {
return component instanceof JComponent;
}

This returns true for some instances of Component, but not others.

LSPHoldsFor(new Component()); -> true
LSPHoldsFor(new JButton()); -> false

Two entirely unrelated examples disproving your interpretation of the LSP; and only one is needed to disprove your theory. Therefore A3 is proven false; point P3 is proven.

[As a note; the reason why this is the case is because (a) the LSP was never proven as a theory, only a postulated goal of something to work towards, and (b) that the LSP talked in terms of mathematical types, and defined a relation (<) between them. At no point did Liskov (or others) claim that these types were Java (or any OO language) classes, and they certainly did not state that the relation (<) was the 'extends' relationship with Java. Common mis-interpretations of the LSP statement have come to result in Pinocio's interpretation of the LSP, which has now been demonstrably falsified using Java classes with the (<) relation. The statement actually began: "What is wanted here is something like the following substitution property:" -- it was never proven, only postulated. Hence P4 and P5.]

We now have A1, A2 and A3 proven false.

You cite: "I would also recommend you to look into the code of JDK. They tend to use either instanceof or the runtime analog of instanceof." This is based on assumption A4, that the Java code libraries consist solely of good examples.

They don't. Some examples of bad code in the Java language:

o Stack is a subclass of Vector. It shouldn't be a subclass; it should be composition, with an instance of Vector being held in an instance of Stack.
o Date. Despite many pages of the virtues of UTC over GMT (despite the fact that most computers sync every few hours), they then go and make the hideous mistake of considering this the year '104', and indexing months from 0..11
o The AWT Thread being a non-daemon thread, despite the fact that (a) daemon thread capability is what lets a VM shut down after all non-user activity has finished, and (b) the fact that prior to Swing, the AWT was a daemon thread. That's why everyone has to call System.exit() when using a GUI, because of some fool's implementation issue, and not fixed (Java bug 4030718) despite implementations showing that it can occur. [I wrote a mechanism that loaded and re-wrote the classes.zip file at the time to show it was possible.]
o Inconsistent naming of 'size()' and 'length()' and '.length' instead of a consistent '.getSize()'

Here are four counter-examples of your assumption that Java = good design. I suggest that to become familiar with good design, you practice in other OO languages such as Eiffel or Objective C. Thus A4 is now falsified.

So, we have assumptions A1-A4 falsified.

On what grounds does the choice of 'instanceof' or 'getClass()' now reside?

instanceof provides LSP: proven false, not applicable
instanceof is asymmetric; proven true, a violation of the equals contract

These are the only two arguments that Pinocio has ever used to substantiate using instanceof. In both cases, these have been proven false.

Further, I have shown that using 'instanceof' results in an asymmetric behaviour; which is a violation of S3b. In fact, only '.getClass()' results in symmetric behaviour.

We now have the last point, P1. That is, the implementation of equals itself.

The SPEC just says "whether some other object is "equal to" this one".
The CONTRACT is listed above in S3.

The equals method therefore says nothing of the type of the argument; just whether it obeys the CONTRACT.

Point2D p2d = new Point2D(1,1);
Point3D p3d = new Point3D(1,1,1);
p2d.equals(p3d);

Any implementation (using getClass/instanceof/a new and funky method found in the future) that gives the result 'true' WILL VIOLATE symmetry. Thus;

assert(p2d.equals(p3d) == p3d.equals(p2d));

The only way this will work is if in BOTH cases 'false' is returned. If one returns true, the other will return false.

In fact, if it were possible to arrange this (and yes, I can see a way -- left for the reader as an exercise) then you could have:

Point2D p2d = new Point2D(1,1);
Point3D p3d1 = new Point3D(1,1,1);
Point3D p3d2 = new Point3D(1,1,2);

assert(p2d.equals(p3d1) == p3d1.equals(p2d)); // even if hypothetically true
assert(p2d.equals(p3d2) == p3d2.equals(p2d)); // even if hypothetically true
assert(p3d1.equals(p3d2)); // false
assert(p3d2.equals(p3d1)); // false

Thus breaking transitivity (S3c).

Note that this has appealed taking the two objects, without even relying on any particular hierarchy. It does not even matter which implementation of .equals() you use, because once you allow like-for-subtype comparisons, you break symmetry (S3b) OR transitivity (S3c).

Thus, the only way to provide both S3b and S3c is using an implementation which forbids like-for-subtype comparisons. This proves my final point P1; and therefore confirms that '.getClass()' is the only way that you can write the .equals() contract because of S1.

Conclusion
==========

I have now shown that arguments based on the LSP as a reason for bending the equality contract are false; because the LSP does not hold in general. I have also shown in any case that 'instanceof' does not obey the LSP in an equality relation; so even if the LSP were true in general, 'instanceof' is still not the solution. Further, I have shown by direct appeal of the equality contract that (regardless of implementation) it is not safe to compare like-for-subtype; as soon as you admit that, you break either symmetry or transitivity. And there is no way that breaking an object's contract can ever be seen as a correct implementation.

I'd like to thank Pinocio for delving deeper down into this thread, because it has made me work on expressing these ideas in a more detailed manner; hopefully this will stand as a record of the future for the correct implementation of the equals method. Of course, I invite you to expose any flaws in the reasoning; however, you will not find any logical flaws, just presentational ones.

public class Rectangle {
public int sideA;
public int sideB;

public Rectangle(int a, int b) { sideA=a;sideB=b; }

public boolean equals(Object o) {
if (o == null) return false;
if (!(o instanceof Rectangle) ) return false;

return ((Rectangle)o).sideA == sideA && ((Rectangle)o).sideB == sideB;
}
}

public class Square extends Rectangle {
public Square(int side) {
super(side,side);
}

public boolean equals(Object o) {
if (o == null) return false;
if (o instanceof Rectangle)
return ((Rectangle)o).sideA == sideA && ((Rectangle)o).sideB == sideB;
return false;
}
}

public class Icon extends Square {
public static final int ICON_SIZE = 32;

public Icon() {
super(ICON_SIZE);
}

public boolean equals(Object o) {
return super.equals(o) && ((Rectangle)o).sideA == ICON_SIZE;
}

}

InfoWorld: Modernizing IT

JavaWorld: Solutions for Java Developers