Liskov Substitution Principle

Barbara Liskov, 1988
(received the ACM Turing Award)

We identified class inheritance and subtype polymorphism as primary mechanisms for supporting the open-closed principle in object-oriented designs.

The Liskov Substitution Principle:

• gives us a way to characterize good inheritance hierarchies,
  
• increases our awareness about traps that will cause us to create hierarchies that do not conform to the open-closed principle.

Substitutability in object-oriented programms

void clientMethod(SomeClass sc) {
  …
  sc.someMethod();
  …
}

Liskov Substitution Principle by Example

Assume, we have implemented a class Rectangle in our system.

class Rectangle {
  public void setWidth(int width) {
    this.width = width;
  }
  public void setHeight(int height) {
    this.height = height;
  }
  public void area() {return height * width;}
  …
}

Let's now assume that we want to implement a class Square and want to maximize reuse.

Implementing Square as a subclass of Rectangle:

class Square extends Rectangle {
  public void setWidth(int width) {
  	super.setWidth(width);
  	super.setHeight(width);
  }
  public void setHeight(int height) {
  	super.setWidth(height);
  	super.setHeight(height);
  }
  …
}

With this overriding of setHeight and setWidth – to set both dimensions to the same value – instances of Square remain mathematically valid squares.

This model is self-consistent!

We can pass Square wherever Rectangle is expected.

A client that works with instances of Rectangle, but breaks when instances of Square are passed to it:

void clientMethod(Rectangle rec) {
  rec.setWidth(5);
  rec.setHeight(4);
  assert(rec.area() == 20);
}

Software Is All About Behavior

Validity is not Intrinsic

Inspecting the Square/Rectangle hierarchy in isolation did not show any problems. In fact it even seemed like a self-consistent design.
We had to inspect the clients to identify problems.

• A model viewed in isolation can not be meaningfully validated!
  The validity of a model depends on the clients that use it.

• Hence, the validity of a model must be judged against the possible uses of the model.
  We need to anticipate the assumptions that clients will make about our classes.

Rectangles and Square - LSP Compliant Solution

It’s not enough that instances of SomeSubclass1 and SomeSubclass2 provide all methods declared in SomeClass. These methods should also behave like their heirs.

A client method should not be able to distinguish the behavior of objects of SomeSubclass1 and SomeSubclass2 from that of objects of SomeClass.

Behavioral Subtyping

The Relation between LSP and OCP

Consider a function f parameterized over type T

• S is a derivate of T.
• when passed to f in the guise of objects of type T, objects of type S cause f to misbehave.
• S violates the Liskov Substitution Principle.

The class Properties inherits from Hashtable

From the JavaDoc:

Because Properties inherits from Hashtable, the put and putAll methods can be applied to a Properties object. Their use is strongly discouraged as they allow the caller to insert entries whose keys or values are not Strings. The setProperty method should be used instead. If the store or save method is called on a "compromised" Properties object that contains a non-String key or value, the call will fail.

Implementing a Persistent Set

Situation: We have implemented a library of container classes, including the interface Set (e.g. using Java 1.4). We want to extend the library with support for persistent sets.

A third-party container class capable of persistence, PersistentSet, is available. It accepts objects of type PersistentObject.

Implementing a Persistent Set

Implementing a Persistent Set

A client that breaks our design

A client method:

public void fill(Set s) {
  fill-the-set-with-arbitrary-objects
}

Somewhere else:

Set s = new PersistentSetAdapter(); // Problem!

fill(s);

Implementing a Persistent Set

A Liskov Substitution Principle compliant solution

Recall:

A model viewed in isolation cannot be meaningfully validated with respect to LSP! Validity must be judged from the perspective of possible usages of the model.

Solution to the validation problem: A technique for explicitly stating what may be assumed.

Two main aspects of design-by-contract:

• We can specify contracts using Pre-, Post-Conditions and Invariants.
  They must be respected by subclasses and clients can rely on them.
• Contract enforcement (behavioral subtyping).
  Tools to check the implementation of subclasses against contracts of superclasses.

Contract for Rectangle.setWidth(int)

(one possible)

public class Rectangle implements Shape {
  private int width;
  private int height;

  public void setWidth(int w) {
    this.width = w;
  }
}

Contract Enforcement

Subclasses must conform to the contract of their base class!

This is called behavioral subtyping.

It ensures that clients won’t break when instances of subclasses are used in the guise of instances of their heirs!

Behavioral Subtyping

Rule for Preconditions

• Preconditions may be replaced by (equal or) weaker ones.
• Preconditions of a class imply preconditions of its subclasses.

Behavioral Subtyping

Rule for Postconditions

• Postconditions may be replaced by (equal or) stronger ones.
• Postconditions of a class are implied by those of its subclasses.

"Standard" Subtyping

“Standard” subtyping relies on contra-variance of the argument types and covariance of the return type for enforcing “pre- and post-conditions on signatures”.

f:		T1  → T2
f’:		T1’ → T2’ 
	
f’ <: f	<=>	T1 <: T1’ and T2’ <: T2  (f' is a subtype of f)

Scala's Type Hierarchy

Scala's Type Hierarchy

"Standard" Subtyping in Scala

val f: (Seq[_]) ⇒ Boolean 
    = (s) ⇒ { s eq null }

val af1: (Object) ⇒ Boolean 
    = null // = f ?

val af2: (List[_]) ⇒ Boolean 
    = null // = f ?

val af3: (Seq[_]) ⇒ Any 
    = null // = f ?

val af4: (Seq[_]) ⇒ Nothing 
    = null // = f ?

Behavioral and Standard Subtyping in OO

Behavioral subtyping is a stronger notion than subtyping of functions defined in type theory.

LSP imposes some standard requirements on signatures that have been adopted in OO languages:

• contra-variance/covariance of method argument/return types.
• no new (checked) exceptions should be thrown by methods of the subtype, except for those exceptions that are subtypes of exceptions thrown by the methods of the super-type.

In addition, there are a number of conditions that behavioral subtypes must meet concerning values (rather than types) of input and output.

Behavioral subtyping is undecidable in general.

Languages and Tools for Design-by-Contract

• Contracts as comments in code or in documentation.
• Unit-tests as contracts.
• Formalisms and tools for specifying contracts in a declarative way and enforcing them.

Java Modeling Language

A behavioral interface specification language that can be used to specify the behavior of Java modules.

public class Rectangle implements Shape { 
	private int width;
	private int height;
	
	/*@

	  @ requires w > 0;
	  @ ensures height = \old(height) && width = w; 

	  @*/
	public void setWidth(double w)  {
		this.width = w;
	} 	
} 

Contracts in Documentation

The Contract of Object.equals(...)

The documentation consists almost entirely of restrictions on how it may be overridden.

The Contract of Object.equals(...)

In the following, we will discuss two restrictions on overriding equals from chapter 3 of the book.

Example Implementation of Object.equals(Object o)

/** 
* Case-insensitive string. Case of the original string is 
* preserved by toString, but ignored in comparisons. 
*/ 
public final class CaseInsensitiveString { 
   private String s; 
   public CaseInsensitiveString(String s) { 
        if (s == null) throw new NullPointerException(); 
        this.s = s; 
   } 
  
   public boolean equals(Object o) { 
      if (o instanceof CaseInsensitiveString) 
         return s.equalsIgnoreCase(((CaseInsensitiveString)o).s); 
      if (o instanceof String)  
         return s.equalsIgnoreCase((String)o); 
      return false; 
   } 
...// Remainder omitted 
}  

Example Usage of CaseInsensitiveString

CaseInsensitiveString cis = new CaseInsensitiveString("Polish"); 
List list = new ArrayList(); 
list.add(cis);

return list.contains("polish"); // true or false ?

The Implementation of java.net.URL.equals

Enforcing Documented Contracts

• Maybe hard when done manually …
• May require very powerful tooling (theorem proving) …
  
• Is un-decidable in general.

The Imperative of Documenting Contracts

Example:

package java.lang;
class Object {
  public boolean equals(Object ob ) { return this == ob; }
}

(Recall equals's contract!)

The Imperative of Documenting Contracts

Example:

/** 
 * Subclasses should override... 
 * Subclasses may call super...
 * New implementation should call addPage...
 */ 
 public void addPages() {...}

On the Quality of the Documentation

Takeaway

• Behavioral subtyping extends “standard” OO subtyping.
  Additionally ensures that assumptions of clients about the behavior of a base class are not broken by subclasses.

• Behavioral subtyping helps with supporting OCP.
  Only behavioral subclassing (subtyping) truly supports open-closed designs.
  

• Design-by-Contract is a technique for supporting LSP.
  Makes the contract of a class to be assumed by the clients and respected by subclasses explicit (and checkable).