Liskov substitution principle

From CSSEMediaWiki
Revision as of 07:11, 7 October 2010 by Joey Scarr (Talk | contribs)
Jump to: navigation, search

The Liskov substitution principle (LSP) is a particular definition of subtype that was introduced by Barbara Liskov in her OOPSLA 1987 keynote address [1]:

"If for each object O1 of type S there is an object O2 of type T such that for all programs P defined in terms of T, the behaviour of P is unchanged when O1 is substituted for O2, then S is a subtype of T."
It is worth noting that in the published address, Liskov cites a number of other references in connection with this, and in particular Gary Leaven's (then unpublished) PhD thesis [2]. Liskov's original address was about the relationship between object oriented programming "as a data abstraction technique", "the elaboration of this technique with the notion of 'inheritance'", and in particular using an inheritance mechanism to implement a subtype hierarchy, while noting that "not all uses of type hierarchy require language support" (eg, an inheritance mechanism). Liskov discussed the distinction between the concept of a type hierarchy and inheritance:
"We are using the words 'subtype' and 'supertype' here to emphasize that we are talking about a semantic distinction. By contrast, 'subclass' and 'superclass' are simply linguistic concepts in programming languages that allow programs to be built in a particular way. They can be used to implement subtypes, but also, as mentioned above, in other ways."
Two important papers by Liskov and Jeannette Wing expanded and formalised the ideas discussed in this address. In these later versions, the substitution principle is defined as a requirement "that constrains the behavior of subtypes: properties that can be proved using the specification of an object's presumed type should hold even though the object is actually a member of a subtype of that type":
"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". [3], [4]
Liskov and Wing describe an approach to implementing requirement by using explicit predicates - invariants and contraints - to type specifications. They also discuss the implications of this for common forms of type hierarchies - extension hierarchies (subtypes add behaviour to the supertype) and constraint hierarchies (subtypes constrain behaviour of supertypes), concluding that the substitution requirement has most impact on the design of constraint hierarchies. In the object-oriented world, the Liskov Substitution Principle is usually interpreted in relation to inheritance and class hierarchies, as illustrated by Robert Martin's paraphrase of the Liskov Substitution Principle:
"Every function which operates upon a reference or pointer to a base class, should be able to operate upon derivatives of that base class without knowing." Robert Cecil Martin 1996c

In this inheritance context the Liskov Substitution principle is closely related to design by contract, which states that

  • Preconditions cannot be strengthened in a subclass.
  • Postconditions cannot be weakened in a subclass.

By adhering to these rules, we can ensure than an instance of a subclass (derived class) can be used in place of (substituted for) an instance of the superclass (base class) without any deviation from the behaviour expected from the object on the basis of the superclass contract.

A quote to sum it all up

The Liskov Substitution Principle (A.K.A Design by Contract) is an important feature of all programs that conform to the Open-Closed principle. It is only when derived types are completely substitutable for their base types that functions which use those base types can be reused with impunity, and the derived types can be changed with impunity. Robert Cecil Martin 1996e

See also

References

  1. ^Liskov, B. (1987). Keynote address - data abstraction and hierarchy, Addendum to the Proceedings on Object-Oriented Programming Systems, Languages and Applications (Addendum), pp 17-34.
  2. ^Leavens, G.T (1989) Verifying object-oriented programs that use subtypes. Massachusetts Institute of Technology, Laboratory for Computer Science, Technical Report TR-439.
  3. ^Liskov, B., and Wing, J. (1994) A Behavioral Notion of Subtyping, ACM transactions on programming Languages and systems, 16(6), pp.1811-1841.
  4. ^Liskov, B., and Wing, J. (1999) Behavioral Subtyping using Invariants and Constraints, Carnegie-Mellon University Technical Report CMU-CS-99-156.
Personal tools