Thursday, June 7, 2007

more about lsp and equals

This post is related to a previous post, about relation between the "liskov substitution principle" and the technical methods choosen to implement equals.

Equals is a method derived from the Object class, that takes Object as parameter, and obviously can be overridden. If the method is not overridden, then the result is true if the two object are the same object. If the method is overridden, the comparison against any non null object returns true if the two object are to be considered equivalent for the domain of the program.
Only immutable objects should redefine equals.
A widely used technique to redefine equals is considering potentially equals only objects belonging to the same class (check is done using getClass()).

If the object belongs to subclasses? The fact that only object belonging to the same class, and not to subclasses, can be "equals" to an object, can be considered a violation of the Liksov substitution principle, so instead of getClass() the check can be done using instanceof.
However this can lead to an equals implementation that violates the equals contract.
There exists a workaround to this, explained here, that solves this issue, (without mentioning lsp).
There are few examples of code (and unit tests) implemented using this technique.

Angelika Langer, coauthor of the paper about the comparison strategy that I consider a solution, sent me a personal email telling me that this issue about "equals" has nothing to do with LSP: "Talking about LSP in conjunction with the implementation technique chosen for "equals" is a red herring".
In her opinion the big issue is just that Java forces you to redefine equals because of the way it works in conjunction with collections, and so you are forced to use different semantics comparisons using the same method name.
She told me that the issue is basically a java design flaw, and anything about LSP.
Moreover she invited me to take a look, for example, "at the containers in
the C++ standard library. They do not require any hard-wired function
names for equals or compareTo thereby allowing to avoid the problem of
different semantics under the umbrella of the same function name"

I would agree on that, however, I just think that LSP *has* to do with equals implementation because:
the principle has to do with object behavior and object behavior has to do with it's methods, including "equals".
This is my very humble opinion.

A way to define lsp is:
"function that uses pointers or references to base classes must be able to use objects of derived classes without knowing it" (http://www.objectmentor.com/resources/articles/lsp.pdf).

In any non final classes, equals method, if implemented via getClass(), always return false when applied to subclasses (unless it "knows" such subclasses i.e. coded so that the getClass() comparison is made also for all known subclasses of the class. This is a violation of lsp in those terms : "[if] a function does not conform to the LSP, then that function uses a pointer or reference to a base class, but must know about all the derivatives of that base class.")

If the comparison is made using instanceof, then class objects can be equal to subclass objects (without making the equals method having to know them, but there is the risk that the equals is not transitive, simmetric, and so violates the equals contract.
For examples see: http://angelikalanger.com/Articles/JavaSolutions/SecretsOfEquals/Equals.html)

For other references about the "instanceof" vs "getClass()" argument in implementing equals see also:
http://www.artima.com/intv/bloch17.html (curiusly Joshua Bloch is for "instanceof", to preserve the possibility to make comparison to subclass objects, and in the same time in his book the example is based on _final_ classes, that cannot be subclassed).

About examples that show when class/subclass equality has sense:

a Rectangle with only positive values of X and Y is subclassed with a Rectangle that can be instantiated with negative X and Y values as well.

(It is a subclass that weakens the "precondition" and thus, incidentally, is compliant by the design by contract specifications.)

If rectangle redefines equals by getClass() then RectangleWithNegatives(1,1) is not equals to RectangleImpl(1,1).

In this case instanceof solves the problem (and is compliant with equals contract).
getClass does not.

There are cases in witch subclasses extend other attributes (new dimension, color and so on...)
and in such cases instanceof does not respect equals contract (see, again http://angelikalanger.com/Articles/JavaSolutions/SecretsOfEquals/Equals.html)

You can simply avoid the problem considering rectangle with color not subclass of rectangle and rather a composition of rectangle and color.

However, if you do subclass it, then:

if
  • you want that your equals implementation will be able to return true if applied to object of the class and to object of a derived class as well.
and
  • in your domain there is an equivalence relation between (a subset of) subclass objects and class object and you look for an implementation of equals that fulfills this equivalence and equals contract
and
  • you want an "equals" solution "closed" against subclasses (i.e. does not need to know subclasses),
then


Possible critics:
a - "the lsp does not hold in java at all".
b - "avoid subclassing: it is dangerous. Use different solutions, like composition"
c - easy to talk about toy examples. And what about real problems?

a) yes. It is easy to say that "lsp does not hold in java". Lsp states that S is subtype of T if you can do some class/subclass substitution without changing the behaviour of any program.

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

It's easy to show programs that changes their behaviour making substitution.

example, all the programs that contain the statement: if myObject.getClass().equals(T.class).

It is defined in terms of T, and if it is applied to any different class, including subclass, returns always false, and if applied to any object of T returns true.
So for all object of any class different from T, there is no possibility to substitute such object with object of T, and thus in Java cannot exist any class that is subclass of T (!).
I.e. no class in java can be subclassed without violating LSP.

See also (http://alblue.blogspot.com/2004/07/java-liskov-substution-principle-does.html)

The interpretation is ok. Then: avoid subclassing.

Another approach is to weaken the lsp definition in the following way:

given that in our language "lsp does not hold strictly" then it is our option to implement our classes and subclasses in a way that if we use them in a clean object oriented approach, then lsp holds.
Using run time type information is not what we mean by clean object oriented approach.

So we can apply the statement in this way: "if you subclass, do it in a way that lsp holds if your object are used in a pure oo".

b) "avoid subclass". Avoid subclass when we know that is so dangerous.
Why is it dangerous? Because we cannot predict what happens during subclassing. Something unexpected happens because we do not comply with some principles like lsp? (Design by contract)? Sounds like "The chiken and the egg".
So: use object oriented, and follow design principles, and apply the same unit tests related of any class, to subclasses as well, then you will not be afraid of subclass.

c) what about real examples? I'm working on it. Any hint is welcome.

3 comments:

Anonymous said...

[u][b]Xrumer[/b][/u]

[b]Xrumer SEO Professionals

As Xrumer experts, we possess been using [url=http://www.xrumer-seo.com]Xrumer[/url] for the benefit of a large fix now and remember how to harness the titanic power of Xrumer and turn it into a Cash machine.

We also provide the cheapest prices on the market. Many competitors will charge 2x or temperate 3x and a end of the time 5x what we responsibility you. But we have faith in providing great help at a low affordable rate. The entire direct attention to of purchasing Xrumer blasts is because it is a cheaper surrogate to buying Xrumer. So we plan to support that mental activity in mind and outfit you with the cheapest rate possible.

Not solitary do we cause the most successfully prices but our turnaround time after your Xrumer posting is wonderful fast. We compel take your posting done ahead of you certain it.

We also produce you with a ample log of affluent posts on contrasting forums. So that you can catch a glimpse of also in behalf of yourself the power of Xrumer and how we have harnessed it to emoluments your site.[/b]


[b]Search Engine Optimization

Using Xrumer you can think to see thousands upon thousands of backlinks exchange for your site. Tons of the forums that your Place you force be posted on have high PageRank. Having your link on these sites can truly serve found up some crown dignity back links and as a matter of fact as well your Alexa Rating and Google PageRank rating through the roof.

This is making your put more and more popular. And with this increase in celebrity as superbly as PageRank you can envisage to see your area in effect superiority high-pitched in those Search Motor Results.
Above

The amount of see trade that can be obtained aside harnessing the power of Xrumer is enormous. You are publishing your situation to tens of thousands of forums. With our higher packages you may equivalent be publishing your position to HUNDREDS of THOUSANDS of forums. Ponder 1 collection on a all the rage forum disposition by cotton on to a leave 1000 or so views, with signify 100 of those people visiting your site. Modern imagine tens of thousands of posts on celebrated forums all getting 1000 views each. Your shipping longing withdraw sometimes non-standard due to the roof.

These are all targeted visitors that are interested or bizarre in the matter of your site. Envision how innumerable sales or leads you can achieve with this colossal number of targeted visitors. You are literally stumbling upon a goldmine friendly to be picked and profited from.

Keep in mind, Transport is Money.
[/b]

TRAVERSE B RECOVER YOUR CHEAPLY BURST TODAY:


http://www.xrumer-seo.com

Anonymous said...

Monitor up on Our Dastardly Prices at www.Pharmashack.com, The Unequalled [b][url=http://www.pharmashack.com]Online Chemist's shop [/url][/b] To [url=http://www.pharmashack.com]Buy Viagra[/url] Online ! You Can also Underline to Pre-eminent Deals When You [url=http://www.pharmashack.com/en/item/cialis.html]Buy Cialis[/url] and When You You [url=http://www.pharmashack.com/en/item/levitra.html]Buy Levitra[/url] Online. We Also Sector a Mammoth Generic [url=http://www.pharmashack.com/en/item/phentermine.html]Phentermine[/url] On account of Your Viands ! We Relate away Artfulness hear sort [url=http://www.pharmashack.com/en/item/viagra.html]Viagra[/url] and Also [url=http://www.pharmashack.com/en/item/generic_viagra.html]Generic Viagra[/url] !

Anonymous said...
This comment has been removed by a blog administrator.