Liskov substitution principle

The Liskov substitution principle (LSP) is a particular definition of a subtyping relation, called strong behavioral subtyping, that was initially introduced by Barbara Liskov in a 1987 conference keynote address titled Data abstraction and hierarchy. It is based on the concept of "substitutability" – a principle in object-oriented programming stating that an object (such as a class) may be replaced by a sub-object (such as a class that extends the first class) without breaking the program. It is a semantic rather than merely syntactic relation, because it intends to guarantee semantic interoperability of types in a hierarchy, object types in particular. Barbara Liskov and Jeannette Wing described the principle succinctly in a 1994 paper as follows:^[1]

Subtype Requirement: Let ⁠ $\phi (x)$ ⁠ be a property provable about objects ⁠ $x$ ⁠ of type $T$ . Then ⁠ $\phi (y)$ ⁠ should be true for objects ⁠ $y$ ⁠ of type $S$ where $S$ is a subtype of $T$ .

Symbolically:

S\leq T\to (\forall x{:}T.\phi (x)\to \forall y{:}S.\phi (y))

That is, if S subtypes T, what holds for T-objects holds for S-objects. In the same paper, Liskov and Wing detailed their notion of behavioral subtyping in an extension of Hoare logic, which bears a certain resemblance to Bertrand Meyer's design by contract in that it considers the interaction of subtyping with preconditions, postconditions and invariants.

Principle

Liskov's notion of a behavioural subtype defines a notion of substitutability for objects; that is, if S is a subtype of T, then objects of type T in a program may be replaced with objects of type S without altering any of the desirable properties of that program (e.g. correctness).

Behavioural subtyping is a stronger notion than typical subtyping of functions defined in type theory, which relies only on the contravariance of parameter types and covariance of the return type. Behavioural subtyping is undecidable in general: if q is the property "method for x always terminates", then it is impossible for a program (e.g. a compiler) to verify that it holds true for some subtype S of T, even if q does hold for T. Nonetheless, the principle is useful in reasoning about the design of class hierarchies.

Liskov substitution principle imposes some standard requirements on signatures that have been adopted in newer object-oriented programming languages (usually at the level of classes rather than types; see nominal vs. structural subtyping for the distinction):

Contravariance of method parameter types in the subtype.
Covariance of method return types in the subtype.
New exceptions cannot be thrown by the methods in the subtype, except if they are subtypes of exceptions thrown by the methods of the supertype.

In addition to the signature requirements, the subtype must meet a number of behavioural conditions. These are detailed in a terminology resembling that of design by contract methodology, leading to some restrictions on how contracts can interact with inheritance:

Preconditions cannot be strengthened in the subtype.
Postconditions cannot be weakened in the subtype.
Invariants cannot be weakened in the subtype.
History constraint (the "history rule"). Objects are regarded as being modifiable only through their methods (encapsulation). Because subtypes may introduce methods that are not present in the supertype, the introduction of these methods may allow state changes in the subtype that are not permissible in the supertype. The history constraint prohibits this. It was the novel element introduced by Liskov and Wing. A violation of this constraint can be exemplified by defining a mutable point as a subtype of an immutable point. This is a violation of the history constraint, because in the history of the immutable point, the state is always the same after creation, so it cannot include the history of a mutable point in general. Fields added to the subtype may however be safely modified because they are not observable through the supertype methods. Thus, one can define a circle with immutable center and mutable radius as a subtype of an immutable point without violating the history constraint.

Origins

The rules on pre- and postconditions are identical to those introduced by Bertrand Meyer in his 1988 book Object-Oriented Software Construction. Both Meyer, and later Pierre America, who was the first to use the term behavioral subtyping, gave proof-theoretic definitions of some behavioral subtyping notions, but their definitions did not take into account aliasing that may occur in programming languages that support references or pointers. Taking aliasing into account was the major improvement made by Liskov and Wing (1994), and a key ingredient is the history constraint. Under the definitions of Meyer and America, a mutable point would be a behavioral subtype of an immutable point, whereas Liskov substitution principle forbids this.

References

^ Liskov, Barbara; Wing, Jeannette (1994-11-01). "A behavioral notion of subtyping". ACM Transactions on Programming Languages and Systems. 16 (6): 1811–41. doi:10.1145/197320.197383. S2CID 999172.

Bibliography

Specific references

Liskov, B. (1987). Keynote address — data abstraction and hierarchy. OOPSLA '87: Addendum to the Proceedings on Object-oriented Programming Systems, Languages and Applications (Addendum). pp. 17–34. doi:10.1145/62138.62141. ISBN 0897912667. A keynote address in which Liskov first formulated the principle.
Meyer, B. (1988). Object-oriented Software Construction. Prentice Hall. ISBN 0-13-629031-0.

General reference

Leavens, Gary T.; Dhara, Krishna K. (2000). "Concepts of Behavioral Subtyping and a Sketch of Their Extension to Component-Bases Systems". In Leavens, Gary T.; Sitaraman, Murali (eds.). Foundations of component-based systems. Cambridge University Press. ISBN 0-521-77164-1. This paper surveys various notions of behavioral subtyping, including Liskov and Wing's.
Liskov, B. H.; Wing, J. M. (November 1994). "A behavioral notion of subtyping". ACM Trans. Program. Lang. Syst. 16 (6): 1811–41. doi:10.1145/197320.197383. S2CID 999172.
An updated version appeared: Liskov, Barbara; Wing, Jeannette (July 1999). Behavioral Subtyping Using Invariants and Constraints (Technical report). Carnegie Mellon University. CMU-CS-99-156. The formalization of the principle by its authors.
Plösch, Reinhold (2004). Contracts, scenarios and prototypes: an integrated approach to high quality software. Springer. ISBN 3-540-43486-0. Contains a gentler introduction to behavioral subtyping in its various forms in chapter 2.
Martin, Robert C. (March 1996). "The Liskov Substitution Principle" (PDF). C++ Report. Archived from the original (PDF) on 2015-11-28. An article popular in the object-oriented programming community that gives several examples of LSP violations.
Majorinc, Kazimir. "Ellipse-Circle Dilemma and Inverse Inheritance". ITI 98, Proceedings of the 20th International Conference of Information Technology Interfaces, Pula, 1998. Information Technology Interfaces, 2009. Iti '09. Proceedings of the Iti 2009 31st International Conference on. pp. 627–632. ISSN 1330-1012. OCLC 894960131. This paper discusses LSP in the mentioned context.

External links

Norvell, T.S. "The Liskov Substitution Principle" (PDF). Engineering Memorial University.
Samokhin, Vadim (2018-06-06). "Liskov Substitution Principle". Medium.
"SOLID Class Design: The Liskov Substitution Principle". Tom Dalling. 21 Nov 2009.
Jobaer, Abu (2023-05-31). "LSP: Liskov Substitution Principle". The Startup. Medium.

[liskov1994-1] Liskov, Barbara; Wing, Jeannette (1994-11-01). "A behavioral notion of subtyping". ACM Transactions on Programming Languages and Systems. 16 (6): 1811–41. doi:10.1145/197320.197383. S2CID 999172.

[1]