Advanced Programming I Lecture Notes

25 April 2006 • Liskov-Wing Substitution

Outline

• Review: ADTs, objects, and design by contract.

• A parent-child problem.

• Liskov-Wing substitution.

• Behavioral subtyping and design by contract.

Objects and ADTs

• Objects support inheritance, which ADTs don't.

• Inheritance specifies relations between classes.

  • Several relations: uses, is a, is more specific than.

• Is-a inheritance is the current favorite.

  • Is-a inheritance leads to subtype polymorphism.

  • Subtype polymorphism supports good system design and implementation.

Design by Contract

• Is-a inheritance requires some complex machinery: virtual methods, method redefinition, dynamic binding.

• Design by contract describes what the machinery should acheive.

• Contracts are assertions in the form of pre- and postconditions and class invariants.

• Parent-child relations are described by logcial relations between parent and child contracts.

Polymorphism

• What, exactly, is subtype polymorphism?

• Do we know enough mechanisms to understand it and use it effectively?

• Liskov and Wing suggest no.

  • There's at least one more piece required: the Liskov-Wing Substitution Principle.

Squares and Rectangles

• What's the relation between squares and rectangles?

  • Both are quadrilaterals.

• A square is a more constrained rectangle.

  • A rectangle has independent height and width.

  • A square has equal height and width.

Implementing Rectangles

class rectangle

  double h, w

  rectangle(h, w) : h(h), w(w) { }

  virtual set_ht(h) { h = h }
  virtual set_wd(w) { w = w }
  double get_height() { return h }
  double get_wd() { return w }

  double area() { return h*w }

Implementing Squares

• Squares are a rectangle, except special.

  • The invariant h == w.

class square : rectangle

  square(s) : h(s), w(s) { }

  set_ht(ht)
    h = w = ht

  set_wd(wd)
    h = w = wd

Class Invariants

• Two important rectangle invariants are

  • Height is independent of width.

  • Area = height × width.

• Two important square invariants are

  • Height = width.

  • Area = height × width = height².

Testing Invariants

void test(rectangle r)

  r.set_wd(4)
  r.set_ht(5)
  assert 4 == r.get_wd() ∧ 5 == r.get_ht()
  assert 20 == r.area()

  r.set_wd(4)
  r.set_ht(3)
  assert 4 == r.get_wd() ∧ 3 == r.get_ht()
  assert 12 == r.area()

Testing the Test

int main()
  test(new rectangle(1, 1))  // pass.
  test(new square(1))	     // fail.

• What happened? Why did the test fail for a square.

  • A square is a rectangle, isn't it?

  • Is-a inheritance (subtype polymorphism) lets me use a square as if it were a rectangle, doesn't it?

The Principle

• Liskov and Wing (and others) suggest no: a square is-not-a rectangle.

  • Is-a relations are not strong enough to specify correct polymorphic behavior.

• The Liskov-Wing Substitution Principle:

  A class C is a child of class P if and only if a C instance can replace any P instance without semantic change.

The Principle Unpacked

• The Liskov-Wing Substitution Principle breaks up into two rules:

  1. If a class C is a child of class P
     then a C instance can be used as a P instance without semantic change.

     • This is subtype polymorphism.

  2. If a C instance can replace any P instance without semantic change
     then a class C can be a a child of class P.

Rectangle-Square Reconsidered

• Replacing a rectangle instance with a square instance causes a semantic change in test().

• By the Liskov-Wing Substitution Principle, squares are not (should not be) children of rectangles.

• Violating the Principle can cause obscure errors when using subtype polymorphism.

  • Leading to fragile and complex inheritance hierarchies.

Consequences

• The Liskov-Wing Substitution Principle is strong.

  • Any possible P instance can be replaced by a C instance without semantic change.

• There are infinitely many P instances.

  • A C instance must be able to replace every one of them without change.

  • Otherwise no P-C inheritance.

Behavioral Subtyping

• Liskov-Wing Substitution uses class behavior to constrain is-a inheritance.

  • A child instance's behavior must be indistinguishable from its parent's behavior.

  • As a child instance it may behave differently, but as a parent instance (under subtype polymorphism) it must not.

• This relation is sometimes called behavioral subtyping.

Some Issues

• The Principle raises (at least) two issues:

  1. What is this behavior and how is it specified?

     • Looking at the code is not helpful during design.

  2. What does it mean to replace one behavior set with another?

     • Exact equality works, bit is there something more flexible?

Design by Contract

• Design by contract deals with these issues.

  1. Class contracts specify behavior.

     • The class invariant and method pre- and postconditions.

     • Contracts are drawn up during design.

  2. The contract-subcontract relation defines behavioral substitution.

     • A child may do more than an parent, and require less.

The Rectangle Contract

• The rectangle invariant is

    // Inv: 
    //   h and w are independent ∧ 
    //   area == h*w ∧ 
    //   whatever...
  

• The contract for rectangle::set_width() is

  set_width(wd)
    // Inv ∧ w == W ∧ h == H
    w = wd
    // Inv ∧ w == wd ∧ h == H
  

The Square Contract

• The square invariant is

    // Inv: 
    //   h == w ∧ 
    //   area == h*w ∧ 
    //   whatever...
  

• The contract for square::set_width() is

  set_width(wd)
    // Inv ∧ w == W
    w = h = wd
    // Inv ∧ w == wd
  

Parent-Child Contracts

• A child contract must not require more than the parent's contract requires.

  • The child-method precondition must be no stronger than the corresponding parent-method precondition.

References

• A Behavioral Notion of Subtyping by Barbara Liskov and Jeannette Wing in ACM Transactions on Programming Languages and Systems, November, 1994.

• The Liskov Substitution Principle by Robert Martin, www.objectmentor.com.