LSP and programming by contract

[JosAH]

Greetings,

This tip of the week introduces a bit of theory when it comes to Object Oriented
programming. First we indroduce a little example project: a simple geometry
project. We want to define a bunch of classes that represent resizable shapes.
Nothing complicated much: we define an abstract Shape class and there we go:

public abstract class Shape { 
   abstract public double getArea();
   ... 
}
public class Rectangle extends Shape {
   // it's dimensions
   private double width, height;
   // contructor
   public Rectangle(double width, double height) {
      this.width= width;
      this.height= height;
   }
   // getters and setters:
   public double getWidth() { return width; }
   public double getHeight() { return height; }
   public void setWidth(double width) { this.width= width; }
   public void setHeight(double height) { this.height= height; }
   // get the area
   public double getArea() { return width*height; }
}

The abstract shape class doesn't know how to calculate an area, thus the method
is made abstract. The Rectangle defines this method. Because a Rectangle *is-a*
Shape, we extend from the abstract class shape. This little scenario can be
found in almost any beginner's textbook; it's almost boring to look at this
for the umptiest time.

We finish this boring little project by defining a Square. As we all know a Square
*is-a* special type of Rectangle, so we extend the Rectangle class:

public class Square extends Rectangle {
   // constructor
   public Square(double side) { super(side, side); }
   // getters and setters:
   public double getSide() { return getWidth(); } // or getHeight()
   public void setSide(double side) {
      super.setWidth(side);
      super.setHeight(side);
   }
   public void setWidth(double width) { this.setSide(side); }
   public void setHeight(double width) { this.setSide(side); }
}

So there: finished. We used most of the Rectangle code: we didn't even had to
define a new getArea() method and everything is fine. We wrap everything up,
build a .jar file, burn it on a CD (we even stick a nice label on it), send
the CD and the bill to our customer and we're going to enjoy the weekend.

That same day our customer receives the CD, installs everything and just
because he's a nasty nitpicker, he wants to test it:

public static void main(String[] args) {
   Rectangle r= new Rectangle(1.0, 0.0);
   for (int i= 1; i <= 10; i++) {
      r.setHeight(i);
      if (r.getArea() != i)
         System.err.println("This software is not correct!);
   }
}

Later that day our customer gives us a call and tells us that the tests had
passed fine so far. We know our software is fine and we congratulate our
customer with his new, fine, correct software.

Our customer also knows that a Square *is-a* special type of Rectangle so he
crafts his next test:

public static void main(String[] args) {
   Rectangle r= new Square(1.0);
   for (int i= 1; i <= 10; i++) {
      r.setHeight(i);
      if (r.getArea() != i)
         System.err.println("This software is not correct!);
   }
}

Guess what? Later that day our customer calls again: he's furious; nine out
of ten test runs failed; just the unit square test succeeded. All he did was
instantiating a Square instead of a Rectangle and because a Square *is-a*
Rectangle everything is supposed to work correctly but it doesn't.

We decide to skip that bill for the moment and have another look at our
classes; there goes the weekend.

Before midnight comes we realize that we're on the wrong track:
no matter what we do to keep the width and height have equal values, the
getArea() gives unexpected results if we consider our Square to be a special
kind of Rectangle. We can't do this either:

public class Square extends Rectangle {
   ...
   public void setWidth(double width) {
      throw IllegalArgumentException("Don't use this method for Squares!");
   }
   public void setHeight(double height) {
      throw IllegalArgumentException("Don't use this method for Squares!");
   }
}

This hack most certainly doesn't pass our customer's test suite. But a Square
*is-a* special kind of Rectangle. Or is it?

In 1988 Barabara Liskov made the following observation about this problem:

"What is wanted here is something like the following substitution property:
If for each object o2 of type D there is an object o1 of type B such that for
all programs P defined in terms of B, the behavior of P is unchanged when o2
is substituted for o1 then D can be a subtype of B."
- Data Abstraction and Hierarchy, SIGPLAN Notices, 23,5 (May, 1988).

Barabara Liskov was the mathematical kind of type and mathematicians are like
the Greek: you give them a problem, they translate it to their own language
and all of a sudden you don't understand your own problem anymore. (*)

For us regular folks who might wear tennis shoes or an occasional python boot,
she said this: the program P is our customer's test suite (see above). The o1
object is an object from the Rectangle class. Our customer's test suite works
fine with them (remember the first happy phone call?) If something wants to
be a derived class (object o2 from class D which in our example is a Square)
that same program should continue to work fine on it.

This is all fine and dandy but our Square class (which extends a Rectangle)
doesn't pass this substitution test. And that is what Barabara Liskov's LSP
is all about: if a derived class doesn't pass this test, it shouldn't be a
derived class at all.

But then again: a Square *is-a* Rectangle. In a mathematical sense yes it is,
but in our example where we can resize those things a Square isn't a Rectangle.
The *is-a* relation isn't a mathematical relation de facto. It is a behavioural
relationship and our attempts failed miserably in the LSP test drive.

That program P expects a Rectangle to operate on, no matter whether or not
they're "special" rectangles. If it runs fine on a rectangle it should run fine
of a special Rectangle. If it doesn't run fine, that special Rectangle is not
supposed to be a Rectangle at all and is not supposed to be a subclass of the
Rectangle class. That's what the LSP is all about. It's a sort of litmus test
for your inheritance tree: if a child class fails to behave as its parent:
don't make the class a child of that parent. (it normally doesn't work that
way in the real world ;-)

So finally, here's our redesigned Square class:

public class Square extends Shape {
   private double side;
   // constructor:
   public Square(double side) { this.side= side; }
   // getters and setters: 
   public double getSide() { return side; }
   public void setSide(double side) { this.side= side; }
   // the area implementation:
   public double getArea() { return side*side; }
}

Boring isn't it? But now it passes the LSP!

There's one thing left: why did Barbara Liskov write "then it *can be* a
subclass". The answer for Java is simple: if two classes implement the same
interface and that program P expects that interface, it should run fine
no matter which of the different implementations (classes) of that same
interface are passed to that program P.

A bit after the LSP was formulated, Bertrand Meyers came up with the
"Design By Contract" notion, which borders the LSP. Every method has its
preconditions and postconditions. When a method is invoked, its precondition
must hold; when a method completes, it promises that its postcondition holds.

As an example, the postcondition of the setWidth method in the Rectangle
class, is:

this.width == width && this.heigth == oldHeight

where oldHeight represents the value of height before the method was called.
As Meyers wrote:

"when rewriting a method (in a derived class), you may only replace the
precondition by a weaker one and replace the postcondition by a stronger one
w.r.t. the conditions of the superclass method".

A "weaker" precondition is true if the "stronger" precondition in the superclass
is true. In other words, when using an object through its base type, the user
(the program P in LSP) knows only the preconditions and postconditions of
the base class. Thus, derived objects must not expect such users to obey to
preconditions that are stronger than those required by the base class. That is,
they must accept anything that the base class would accept. Also, derived
classes must conform to all postconditions of the base, i.e. their behaviour
and outputs (side effects) must not violate the constraints imposed by the base class.

As can be clearly seen, the Rectangle/Square example violates the ‘stronger
postcondition’ in the Square class, i.e. the postcondition shown above for the
Rectangle class doesn’t hold in the derived Square class.

'till next time which will be "playtime": Sudoku solvers and all that.

kind regards,

Jos