Liskov substitution principle

Revision as of 09:09, 6 October 2008 (view source) Jason Clutterbuck (Talk | contribs) ← Older edit		Latest revision as of 03:22, 25 November 2010 (view source) WikiSysop (Talk | contribs) m (Reverted edits by Ebybymic (Talk); changed back to last version by Joey Scarr)
(5 intermediate revisions by 5 users not shown)
Line 1:		Line 1:
−	The Liskov substitution principle (LSP) is a particular definition of subtype that was introduced by Barbara Liskov, in 1987. Succinctly, it states	+	The Liskov substitution principle (LSP) is a particular definition of subtype that was introduced by Barbara Liskov in her OOPSLA 1987 keynote address {{Ref|1}}:
−	:''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.''	+	<blockquote> "If for each object O<sub>1</sub> of type S there is an object O<sub>2</sub> of type T such that for all programs P defined in terms of T, the behaviour of P is unchanged when O<sub>1</sub> is substituted for O<sub>2</sub>, then S is a subtype of T."</blockquote>It is worth noting that in the published address, Liskov cites a number of other references in connection with this, and in particular [http://www.eecs.ucf.edu/~leavens/homepage.html Gary Leaven's] (then unpublished) PhD thesis {{Ref|2}}.
−	In English, this means that if S is a subclass of T, then any objects of type T in a program can be replaced by object of type S, without changing the correctness of the system. Basically, subclasses should behave exactly like base classes, except with a little '''extra''' functionality, but no less.	+	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:<blockquote>"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."</blockquote>
		+	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":<blockquote>"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".  {{Ref|3}}, {{Ref|4}}</blockquote>  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.
−	Or as Robert Martin might say it <Big>"</Big>every functiona which operates upon a reference or pointer to a base class, should be able to operate upon derivatives of that base class without knowing.<Big>"</Big> [[Robert Cecil Martin 1996c]]	+	In the object-oriented world, the Liskov Substitution Principle is usually interpreted in relation to inheritance and class hierarchies, as illustrated by [[Bob Martin|Robert Martin's]] paraphrase of the Liskov Substitution Principle:<blockquote>"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]] </blockquote>
−		+	In this inheritance context the Liskov Substitution principle is closely related to [[Design by contract|design by contract]], which states that
−	This is closely related to [[Design by contract]], which states that	+
	* Preconditions cannot be strengthened in a subclass.		* Preconditions cannot be strengthened in a subclass.
	* Postconditions cannot be weakened in a subclass.		* Postconditions cannot be weakened in a subclass.
−	A violation of this principle will occur when a class uses a reference to a base class, but has some knowledge of the subclass(s).	+	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=====	+
−	<big>"</big> The Liskov Substitution Principle (A.K.A Design by Contract) is an important feature of all	+	=== A quote to sum it all up ===
−	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. <big>"</big> [[Robert Cecil Martin 1996e]]	+
		+	<blockquote>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]]</blockquote>
−	==See Also==	+	== See also ==
		+	* [[Barbara Liskov]]
	* [[Design by contract]]		* [[Design by contract]]
	* [[Open closed principle]]		* [[Open closed principle]]
		+	* [[Circle-ellipse problem]]
		+	* [[Bob Martin's principles]]
		+
		+	== References ==
		+	#{{Note|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.
		+	#{{Note|2}}Leavens, G.T (1989) ''Verifying object-oriented programs that use subtypes''. Massachusetts Institute of Technology, Laboratory for Computer Science, Technical Report TR-439.
		+	#{{Note|3}}Liskov, B., and Wing, J. (1994) A Behavioral Notion of Subtyping, ''ACM transactions on programming Languages and systems'', 16(6), pp.1811-1841.
		+	#{{Note|4}}Liskov, B., and Wing, J. (1999) ''Behavioral Subtyping using Invariants and Constraints'', [http://reports-archive.adm.cs.cmu.edu/anon/1999/abstracts/99-156.html Carnegie-Mellon University Technical Report CMU-CS-99-156].
		+
		+	[[Category:Bob Martin's principles]]

---

Latest revision as of 03:22, 25 November 2010

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 O₁ of type S there is an object O₂ of type T such that for all programs P defined in terms of T, the behaviour of P is unchanged when O₁ is substituted for O₂, 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

• Barbara Liskov
• Design by contract
• Open closed principle
• Circle-ellipse problem
• Bob Martin's principles

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.