CSC/ECE 517 Fall 2009/wiki3 20 i7

Liskov substitution principle

Definition

The Liskov substitution principle is a object oriented design principle was introduced by Barbara Liskov in 1987 and is concerned with subtyping and contractual adherence. This principle is part of the SOLID principles of object oriented design which is an acronym for the five basic class design principles and relates to many object oriented design principles. The basic idea behind the object oriented design principles is to create and apply proper abstractions. Based on a paper from 1994 the principle states,

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

This means that for every parent type T, subtype S should be able to be substituted in for it and the behavior of the program should remain exactly the same. Plainly, we want subtypes to be substitutable for their base types as Robert Martin put it. The following example in Java illustrates the principle.

public class MyClass {
    private final List<String> list;

    public MyClass(List<String> list) {
        this.list = list;
    }
    ....
}

public class TestRunner {
    public static void main ( String[] args ) {
        // If the List type follows Liskov substitution...
        List<String> arrayList = new ArrayList<String>();
        List<String> linkedList = new LinkedList<String>();

        // ...I should be able to use any subtype of List to create a new MyClass and observe identical behavior!
        MyClass this = new MyClass(arrayList);
        MyClass works = new MyClass(linkedList);
    }
}

Preconditions

When dealing with Liskov substitution, preconditions cannot be strengthened. Intuitively, the subtype cannot require anymore preconditions than the parent. This makes sense because if the subtype required more than the parent, then the subtype would not be able to be effectively substituted in for the parent transparently. There would need to be more preconditions satisfied after substituting in the subtype in this hypothetical situation. Take for instance this example in Java which illustrates this point.

interface LocationProvider {
    /**
     *
     * Preconditions: None
     *
     */
    public void getLocation();
}

class GpsLocationProvider implements LocationProvider {

    /**
     *
     * Preconditions: A GPS fix must be present.  -- Wait! I can't do that because I would be requiring more 
     *                                               than what the interface requires which 
     *                                               violates this principle.  Doing this would mean others 
     *                                               would need to know that the underlying implementation 
     *                                               of a LocationProvider is a GpsLocation provider and 
     *                                               to get a GPS fix before calling getLocation(), 
     *                                               we don't want that!
     *
     */
    public void getLocation() {
        ...
    }
}

In this example, a GpsLocationProvider is a subtype to LocationProvider. However, the GpsLocationProvider has a precondition which the LocationProvider does not which is that it requires a GPS fix to get a location. This creates a new precondition which LocationProvider does not require. Liskov substitution would not be possible here since you could not treat a GpsLocationProvider as a LocationProvider.

Postconditions

When dealing with Liskov substitution, postconditions cannot be weakened. Intuitively, the subtype cannot have fewer postconditions than the parent. This makes sense because if the subtype did not at least adhere to the postconditions of the parent, it could not be substituted for it simply because postconditions we assumed to be true would not be. Take for instance this example in Java which illustrates this point.

MyList<T> implements List<T> {
    ...
    public boolean contains(T element) {
        this.remove(t)
        // -- Wait!  I can't do that, a postcondition to calling contains is that the list is unmodified.
        //           The removal of this postcondition in this list would mean this class has less postconditions then the parent.
        //           This is not good!
        ...
    }
    ...
}

In this example, we have a MyList which is a subtype to List. For one reason or another we want to also remove the element if we call contains on it. This violates a postcondition that the list must remain unmodified when calling contains. Due to this violation, we would not be able to use Liskov substitution here. In fact, substituting this List implementation into a program which uses List could be disastrous!

Invariants

When dealing with Liskov substitution, invariants must be preserved. In other words, properties that are assumed to be true must always remain true. This property lends itself to being self explained by the quality of correctness. Take for instance this example in Java which illustrates this point.

class Rectangle {
    private double width;
    private double height;
    
    public Rectangle(double width, double height) {
        this.width = width;
        this.height = height;
    }

    public double getWidth() {return this.width;}
    public double getHeight() {return this.height;}

    public double setWidth(int width) {this.width= width;}
    public double setHeight(int height) {this.height = height;}
}

class Square extends Rectangle {
    private double width;
    private double height;
    
    public Square(double side) {
        super(side, side);
    }

    public double setSide(int side) {
        super.setWidth(side);
        super.setHeight(side);
    }
}

This example is a classic example used when discussing Liskov substitution. There is a Rectangle class which has two data members, the height and width, constructors, getters, and setters are provided. In the subtype, Square, we want to have the sides be equal, therefore we delegate calls to the parent in order to do so. In this naive example, if a programmer does not have access to the source code they can violate an invariant of the Square class which is that the sides must be equal. Continuing our example this would look like the following.

Rectangle square = new Square(1);
square.setSide(5); // This is ok, both our sides are equal to 5 now!
square.setWidth(2); // This is not ok, both height and width of the Square are not equal at this point.

Conclusion

The Liskov substitution principle is a guideline on subtyping existing classes. The purpose of Liskov substitution is to ensure that subtypes adhere to their contracts.

Concisely:

• Subtypes must not require anymore preconditions as it violates the contract they are based on.
• Subtypes must have at least the same set of postconditions to adhere to the contract they are based on.
• Subtypes must have the same invariants to ensure consistency.

Using these properties subtypes can be substituted for base types.

References

• http://en.wikipedia.org/wiki/Liskov_substitution_principle
• http://javaboutique.internet.com/tutorials/JavaOO/
• http://www.codingefficiency.com/2009/07/21/solid-l-liskov-substitution-principle/
• http://www.davidhayden.com/blog/dave/archive/2005/06/10/1226.aspx