If A is a subtype of B, then an reference of type A should be able to appear in any context where an reference of type B is expected without altering the correctness of the program.
Let's introduce the following notation:
A <: B means A is a subtype of B
x: A means x is a reference of type B
The subtype relationship is transitive:
A <: A
A <: B & B <: C => A <: C
The Subsumption Rule (which is followed to varying degrees by object-oriented languages) equates subtype with substitutability:
x: A & A <: B => x: B
In other words, if x is of type A, then x is also of type B. x is polymorphic.
Of course the Subsumption Rule only guarantees that the program won't contain any type errors if references of a subtype masquerade as references of a super type. There still may be logical errors. That's the point of LSP. Programmers need to insure the substitution doesn't inject any logical errors into the program.
In Java:
byte <: short <: int <: long <: float <: double
We can freely substitute ints for doubles:
double x = 0; // ok
How are the notions of type and class related? Intuitively:
class = type + implementation
We may take the type of a class to be the signatures of all of its public methods. (In Java, we might take the type of a class to be any interface it implements. )
Assume the type of class A is type(A) and the type of class B is type(B). Lets also assume that A extends B. Does it follow that type(A) <: type(B)? In other words, does it follow that a reference to A can masquerade as a reference to B?
In this example it appears that the answer is yes, subclass => subtype:
class Food { ... }
class Cheese extends Food { ... }
class Cheddar extends Cheese { ... }
class Havarti extends Cheese { ... }
Clearly we can use instances of Cheddar, Havarti, and Cheese in contexts where instances of Food are expected. For example:
Food f = new Cheese(); // ok
f = new Cheddar(); // ok
f = new Havarti(); // ok
If instances of A and B are mutable-- if they have methods that update their instance variables-- then subclass need not imply subtype. The problem arises if the state space of A is a subspace of the state space of B. Inherited mutator methods may allow changes to states outside of the subspace.
For example, a cheese sandwich contains a piece of cheese that can be updated:
class CheeseSandwich {
private Cheese filling;
public void setFilling(Cheese c) {
filling = c; }
public Cheese getFilling() { return
filling; }
}
A cheddar cheese sandwich only allows a cheddar cheese filling:
class CheddarSandwich extends CheeseSandwich {
public void setFilling(Cheddar c) {
filling = c; }
public Cheddar getFilling() { return
filling; }
}
A sandwich is both a supplier and receiver of its filling. But in order for a cheddar sandwich to masquerade as a cheese sandwich, it must be able to supply and receive cheese fillings:
CheddarSandwich s = new CheddarSandwich();
s.setFilling(new Cheddar());
Cheddar c = s.getFilling(); // ok
s.setFilling(new Havarti()); // ok calls inherited setFilling
c = s.getFilling(); // now this fails
Another Example: Conceptually, a square is a rectangle with identical height and width. The set of all squares is a subset of the set of all rectangles. This observation motivates the following definitions:
class Rectangle {
private int height, width;
public void setHeight(int h) { height =
h; }
public int getHeight() { return height;
}
public void setWidth(int h) { width =
h; }
public int getWidth() { return width; }
}
class Square extends Rectangle {
public void setSide(int s) {
setHeight(s);
setWidth(s);
}
public int getSide() { return height; }
}
But can a square be used in all contexts where a rectangle is expected? One thing is that squares allow us to independently set their height and width, so squares should allow this, too:
Square s = new Square();
s.setWidth(10);
s.setHeight(20);
int area = s.getSide() * s.getSide()); // right?
Both this example and the sandwich example suffer from the same defect. The state space of the subclass is a subspace of the state space of the super class, and the subclass attempts to enforce the additional constraint on the state space.
For example, the state space of CheeseSandwich is Cheese, while the state space of CheddarSandwich is Cheddar. The state space of Rectangle is the set of all pairs of ints, while the stare space of Square is the set of all pairs of equal ints. In both cases, inherited mutator methods allowed changes to states that were not in the required subspace.
A bag is a collection of values (ints in this example). A bag may hold multiple instances of a given value:
class Bag {
// add i to the bag
void add(int i) { ... }
// = # of occurances of i
int count(int i) { ... }
}
A set is a bag that does not allow multiple instances:
class Set extends Bag {
void add(int i) {
if (0 == count(i)) super.add(i);
}
}
Now consider the following function:
// pre-condition: bag.count(10) = n
// post-condition: bag.count(10) = n + 2
int add2(Bag bag) {
bag.put(10);
bag.put(10);
return bag.count(10);
}
Notice that the post condition fails if the argument is a set instead of a bag.
class Bag {
// returns a new bag like this but with
another i added
Bag add(int i) { ... }
// = # of occurances of i in this bag:
int count(int i) { ... }
}
class Set extends Bag {
Set add(int i) {
if (0 == count(i)) {
return super.add(i);
// pre-condition: bag.count(10) = n
// post-condition: bag.count(10) = n + 2
int add2(Bag bag) {
bag.put(10);
bag.put(10);
return bag.count(10);
}
The problem with mutable objects is that they are both suppliers and receivers of their state. Assume
class State { ... }
class SpecialState extends State { ... }
class Cell {
State state;
void setState(State s) { state = s; }
State getState() { return state; }
}
class SpecialCell extends Cell {
void setState(SpecialState s) { state =
s; }
SpecialState getState() { return
(SpecialState)state; }
}
We see that a cell is both a supplier and a receiver of a state. This means a special cell must also be a supplier and receiver of state if it is to be a subtype of Cell. A special cell supplies a special state. If SpecialState <: State, then this is okay. But a special cell also receives States. But if the received state doesn't happen to be a special state, then this breaks the class invariant for the special cell.
We might try to get a little more out of LSP by saying subtypes are substitutable for supertypes not just in programming contexts but also contexts such as correctness proofs and programmer's minds. In other words, can the subclass replace the superclass and still have the program compute the right answer?
We can get a little closer to this by demanding that every method have pre- and post-conditions. In java these could be introduced using assert statements or by throwing exceptions.
Assume m is a method. Let:
pre(m, e) = the pre-condition of m given environment e
post(m, e) = the post-condition of m given environment e
And so if pre(m, e) is true before m is called, then post(m, env) will be true when m terminates:
pre(m, e) => post(m, e) after m is called
Now suppose m is a method of class B, A extends B and overrides m:
class B {
S m(T t) { ... }
}
class A extends B {
S' m(T' t) { ... }
}
We know that if type(A) <: type(B), then
S' <: S & T <: T' if A and B are stateless
S' = S & T = T' if A and B are stateful.
In addition, we must also have:
pre(B.m, e) => pre(A.m, e) & post(A.m, e) => post(B.m, e)
Let's see why this is true. Assume:
B x = new A();
assert(pre(B.m, e)); // if true
x.m(t);
assert(post(B.m, e)); // then this is true
If pre(B.m, e) is true, then so is pre(A.m, e). This means post(A.m, e) should be true when x.m(t) terminates, but this implies post(B.m, e) should be true.