OO Concept: Liskov Substitution Principle

Discussion in 'Java' started by howa, May 30, 2008.

  1. howa

    howa Guest

    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
    howa, May 30, 2008
    #1
    1. Advertising

  2. howa

    Stefan Ram Guest

    howa <> 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, May 30, 2008
    #2
    1. Advertising

  3. howa

    Stefan Ram Guest

    -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 ); }

    .
    Stefan Ram, May 30, 2008
    #3
  4. -berlin.de (Stefan Ram) writes:

    > howa <> 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 -
    DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
    'Faith without judgement merely degrades the spirit divine.'
    Lasse Reichstein Nielsen, May 30, 2008
    #4
  5. howa

    Tom Anderson Guest

    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
    definition is mind-numbingly bad:

    "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/Covariance_and_contravariance_(computer_science)

    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.

    Anyway, to answer your question, i'd descend Square from Rectangle, and
    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) ;
    }
    }

    Dead simple.

    tom

    --
    A military-industrial illusion of democracy
    Tom Anderson, May 30, 2008
    #5
  6. howa

    Daniel Pitts Guest

    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
    FordModelTWithRedPaintAndLeatherSeatsAndPowerWindows. 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
    plenty already :)
    --
    Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
    Daniel Pitts, May 30, 2008
    #6
  7. howa

    Stefan Ram Guest

    Tom Anderson <> 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
    additional global invariants). In Java, one should use JavaDoc
    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).
    Stefan Ram, May 30, 2008
    #7
  8. 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
    Joshua Cranmer, May 30, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. CW

    Webmessenger principle

    CW, Sep 22, 2004, in forum: ASP .Net
    Replies:
    5
    Views:
    682
    Steven Cheng[MSFT]
    Sep 23, 2004
  2. Replies:
    11
    Views:
    605
  3. Aries Sun
    Replies:
    4
    Views:
    317
    Joel Yliluoma
    Nov 29, 2007
  4. George2

    Liskov substitution principle

    George2, Feb 25, 2008, in forum: C Programming
    Replies:
    0
    Views:
    274
    George2
    Feb 25, 2008
  5. Steven D'Aprano

    Barbara Liskov wins Turing Award

    Steven D'Aprano, Jun 25, 2009, in forum: Python
    Replies:
    3
    Views:
    398
    Martin v. Löwis
    Jun 25, 2009
Loading...

Share This Page