Velocity Reviews > Java > OO Concept: Liskov Substitution Principle

# OO Concept: Liskov Substitution Principle

howa
Guest
Posts: n/a

 05-30-2008
Hi,

Just read an article talking about the LSP in term of OO design:
http://www.objectmentor.com/resources/articles/lsp.pdf

The article said Rectangle class should not be a superclass of Square
class.

Okay, so how you would design the Rectangle & Square class?

The article did not cover that, so what are your opinion?

Howard

Stefan Ram
Guest
Posts: n/a

 05-30-2008
howa <(E-Mail Removed)> writes:
>The article said Rectangle class should not be a superclass of Square
>class.
>Okay, so how you would design the Rectangle & Square class?
>The article did not cover that, so what are your opinion?

The whole rectangle square discussion only stems
from insufficiant care to distinguish between
value and storage objects.

Let Q be the set of »quarternary digits« {0,1,2,3},
its subset {0,1} is called B; B is »the set of
binary digits«. The inclusion

B c Q (B is a subset of Q)

is valid.

A quartary storage q* can store a quartary digit. It
also might be used to store a binary digit. However, one
can not use any binary storage to store any quartenary digit.

So, for the set of binary storages B* and the set of
quartary storages Q*:

Q* c B* (Q* is a subset of B*)

In general, if every B value is a Q value, then every Q storage
is a B storage.

If one now does not care to distinguish between values and
memories, this would be worded as »If every B is a Q, then
every Q is a B«, which is false.

The rectangle square problem only exists as long as one does
not make it clear whether one wants to model rectangle and
square /values/ or rectangle and square /storages/.

Stefan Ram
Guest
Posts: n/a

 05-30-2008
http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Stefan Ram) writes:
>The rectangle square problem only exists as long as one does
>not make it clear whether one wants to model rectangle and
>square /values/ or rectangle and square /storages/.

So,

interface rectangleValue
{ int getHeight();
int getWidth(); }

interface squareValue extends rectangleValue {}

. But,

interface squareBuffer
{ int getHeight();
void setHeight( final int height ); }

interface rectangleBuffer extends squareBuffer
{ int getWidth();
int setWidth( final int width ); }

.

Lasse Reichstein Nielsen
Guest
Posts: n/a

 05-30-2008
(E-Mail Removed)-berlin.de (Stefan Ram) writes:

> howa <(E-Mail Removed)> writes:
>>The article said Rectangle class should not be a superclass of Square
>>class.
>>Okay, so how you would design the Rectangle & Square class?
>>The article did not cover that, so what are your opinion?

>
> The whole rectangle square discussion only stems
> from insufficiant care to distinguish between
> value and storage objects.

Too true.
Whether something is a subclass of something else depends on the
operations on the class as much as it does on the concept.

In mathematics, every square is a rectangle. However, in mathematics,
you don't usually assign to the length of a side of an existing
rectangle.

This also gives us extra complexity wrt. generics.

If Foo is a class, and Bar is a properly designed subclass (so that
anywhere a Foo is expected, a Bar can be used instead), then we
would like to think that a parameterized Baz<T> class would satisfy
that Baz<Foo> was a proper super-type of Baz<Bar>.

This is not the case in Java, and for exactly the reason Stefan
was describing: it matters what operations are on the type.

The simplest "storage" class that displays the problem is something
like:

public class Box<T> {
private T value;
public T get() { return value; }
public void set(T value) { this.value = value; }
}

If Box<Foo> was a supertype of Box<Bar>, then everywhere a
Box<Foo> was expected, a Box<Bar> could be used. However, that
fails for:

public void doSet(Box<Foo> box, Foo foo) { box.set(foo); }

Calling this with a Box<Bar> and a Foo would try to store a Foo
in a Box<Bar>, but the Foo is not a Bar.

The other direction doesn't work either. A Box<Bar> is not a supertype
of Box<Foo>, because then the following method would be acceptable:

public Bar doGet(Box<Bar> box) { return box.get(); }

Passing a Box<Foo> as argument would be able to return a Foo, which
is not allowed.

The "Box" class displays both types of behavior: value (get method)
and storage (set method). Trying to specialize on the property being
gotten and set shows the problem in both directions.

Another example of how getting and setting vary (co- and contra-variantly,
respectively):

public interface Setter<T> {
set(T value);
}
public interface Getter<T> {
T get();
}

class Example {
public <T> void doSet(Setter<? super T> setter, T value) {
setter.set(value);
}
public <T> void doGet(Getter<? extends T> getter) {
return getter.get();
}
}

Notice the difference: super vs extends.

For a setter, you can allow a supertype as parameter, because it can
still receive all the values of the subtype.

For a getter, you can allow a subtype as parameter, because it can
still only produce values of the subtype.

If you need both a getter and a setter for the same property, you can't
allow anything but the exact type.

Which is also why a Collection<Foo> is not a Collection<Bar>, or the
other way around. Instead we use Collection<? super Foo> where we can
only add values, or Collection<? extends Foo> where we can only
extract values.

/L
--
Lasse Reichstein Nielsen - http://www.velocityreviews.com/forums/(E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Tom Anderson
Guest
Posts: n/a

 05-30-2008
On Fri, 30 May 2008, howa wrote:

> Just read an article talking about the LSP in term of OO design:
> http://www.objectmentor.com/resources/articles/lsp.pdf

Okay, firstly that article is crap.

> The article said Rectangle class should not be a superclass of Square
> class.
>
> Okay, so how you would design the Rectangle & Square class?

I'd start by going back in time and giving Barbara Liskov a sound kicking.

I mean, she's bang on about how subclasses must be able to stand in for
superclasses and fulfil the same contracts. That's a fundamental principle
of type theory. More than type theory - type law! But her classic

"What is wanted here is something like the following substitution
property: 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 o2 is substituted for o1 then S is a subtype of T."

If the instance being of a different class doesn't change the behaviour,
then there's no point in having that class, is there? What she meant was
that it should obey the same contracts, but she didn't say that, and
ludicrous quantities of arguments about the matter filled up most of the
1990s. She later stated it much more clearly:

"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."

Which, as long as you understand 'property' to mean 'contractually defined
property', is bang on.

A more general, and to my mind useful, way of thinking about
substitutability is in terms of covariance and contravariance. I don't
have time to explain this right now, so have a read (this is not a great
article, but it's a start):

http://en.wikipedia.org/wiki/Covaria...ter_science%29

I note that Jon Postel actually beat Barbara Liskov, and the category
theorists, to the punch with his famous law about protocols:

http://en.wikipedia.org/wiki/Robustness_Principle

Which is, when you think about it, exactly the requirement that is
incumbent upon subtypes.

make them both immutable.

If you need to be able to resize Rectangles, i'd have a method like:

public Rectangle setWidth(int w)

Which returns a new rectangle. Square implements this by returning a
Rectangle, and all is well.

public class Rectangle {
private double w ;
private double h ;
public Rectangle(double w, double h) { ... }
public Rectangle scale(double scaleFactor) {
return new Rectangle((w * scaleFactor), (h * scaleFactor)) ;
}
public Rectangle setWidth(double w) {
return new Rectangle(w, this.h) ;
}
}

public class Square extends Rectangle {
private double s ;
public Square(double s) { ... }
public Rectangle scale(double scaleFactor) {
return new Square(s * scaleFactor) ;
}
public Rectangle setWidth(double w) {
return new Rectangle(w, this.s) ;
}
}

tom

--
A military-industrial illusion of democracy

Daniel Pitts
Guest
Posts: n/a

 05-30-2008
howa wrote:
> Hi,
>
> Just read an article talking about the LSP in term of OO design:
> http://www.objectmentor.com/resources/articles/lsp.pdf

This is the second time I've seen reference to this paper, but I haven't
yet looked at it. I'm working offline now, but when I reconnect, I'll
check it out.
>
> The article said Rectangle class should not be a superclass of Square
> class.
>
> Okay, so how you would design the Rectangle & Square class?
>
>
> The article did not cover that, so what are your opinion?
>
>
> Howard

Like I said, I haven't read that article. I'm just thinking out loud
here, so bare with me.

The distinction between a Rectangle and a Square is the constraint that
the sides on a Square are equal. So you might think "Square" is a
"Rectangle". But at the same time, you could consider a Rectangle as a
Square with (possibly) different size sides. To through even more
confusing into the mix, Rectangles and Squares are (mathematically) all
Rhombuses, Parallelograms, Quadrilaterals, etcetera and so forth, but
lets not confuse things

Squares have no behavior that a Rectangle doesn't have, therefor they
aren't separate types.

If I had use for Rectangles and Squares, I would probably design a
Rectangle class, and have a predicate isSquare which checks the length
of the sides for equality. I might have a factory method called
makeSquare(SideType side) to ease the creation of Squares.

I personally would probably make Rectangles immutable, which would allow
me to have a private subclass of Rectangle which is a Square
specialization that has optimizations. I would only do this if a
profiler told me I had a lot of Rectangles that we're isSquare() and the
fact that other calculations on those specific rectangles were taking a
significant amount of time.

Back to the question, but in another tangent. A common example used in
OO is Cars. Humans associate "A Ford is a Car" so they make Ford extend
Car. They also then say "ModelT is a Ford", so ModelT extends Ford.
The mistake is confusing Make (Brand) with Type (Class), and further
confusing Model with Type. This kind of mistake can lead to a very ugly
class hierarchy when you end up with classes like
FordModelTWithRedPaintAndLeatherSeatsAndPowerWindo ws. A better
hierarchy would be to have a Car that "has a" Make (Ford is a Make),
"has a" Model, "has some" Options (SeatMaterial is an Option) and "has
a" Paint.

The point is, don't confuse "'is an' X that 'has a property' Y" with
"'Is an' XWithPropertyY". A Square is a Rectangle with the property
"Sides are the same." In particular, if your Rectangle is mutable, the
"squareness" property depends on current state of your object, not the
type.

I believe that is the idea behind the principal "Composition over
Inheritance." Not to be confused with "Delegation over Inheritance",
which is related, but different.

Hmm, I ought to write a book on this subject, but I think there are
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

Stefan Ram
Guest
Posts: n/a

 05-30-2008
Tom Anderson <(E-Mail Removed)> writes:
>"What is wanted here is something like the following substitution
>property: 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 o2 is substituted for o1 then S is a subtype of T."

Liskov actually seems to give Leavans

Gary T. Leavens, Verifying Object-Oriented Programs that use Subtypes. Massachusetts Institute of Technology, Laboratory for Computer Science, Technical Report TR-439, February 1989.

as a source for the above definition. So it is not clear,
whether she really made up this wording or copied it from
Leavens.

>it should obey the same contracts,

Yes, this wording is more useful.

A method needs to have a contract (and the type might have
to state the contract.

Every implementation of the method in a subtype needs to obey
this contract (and the subtype needs to obey the global
invariants of the type).

Joshua Cranmer
Guest
Posts: n/a

 05-30-2008
howa wrote:
> Hi,
>
> Just read an article talking about the LSP in term of OO design:
> http://www.objectmentor.com/resources/articles/lsp.pdf
>
> The article said Rectangle class should not be a superclass of Square
> class.
>
> Okay, so how you would design the Rectangle & Square class?
>
>
> The article did not cover that, so what are your opinion?

First things first, I am going to stop talking about a hierarchy whose
practical importance is practically nil and bring in a more useful example.

Let us assume we are writing a linear algebra package. Quite naturally,
at some point we have a Matrix class. While writing
Matrix.determinant(), we realize that it may be to our advantage to
refactor said method into a SquareMatrix.determinant() for ease of
design. Should we do so, i.e., should we create a SquareMatrix class
that descends from Matrix?

I propose the following answer: yes, since Matrix here is assumed to be
immutable. The problem with compatibility is that SquareMatrix assumes
that its two dimensions are equal; since these dimensions can only be
affected at initialization, thereby rendering this contractual
incompatibility moot.

However, in the end, we decide that requiring a separate SquareMatrix
class is pointless since a 3x2 matrix multiplied by a 2x3 matrix is a
square matrix even if its type is merely a banal Matrix, rendering the
entire discussion moot.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth