![Barbara Liskov MIT computer scientist 2010](https://upload.wikimedia.org/wikipedia/commons/3/38/Barbara_Liskov_MIT_computer_scientist_2010.jpg)
The Liskov substitution principle (LSP) is a particular definition of a subtyping relation, called
strong behavioral subtyping, that was initially introduced by
Barbara Liskov
Barbara Liskov (born November 7, 1939 as Barbara Jane Huberman) is an American computer scientist who has made pioneering contributions to programming languages and distributed computing. Her notable work includes the development of the Liskov ...
in a 1988 conference
keynote
A keynote in public speaking is a talk that establishes a main underlying theme. In corporate or commercial settings, greater importance is attached to the delivery of a keynote speech or keynote address. The keynote establishes the framework fo ...
address titled ''Data abstraction and hierarchy''. It is based on the concept of "substitutability" a principle in
object-oriented programming
Object-oriented programming (OOP) is a programming paradigm based on the concept of "objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of pr ...
stating that an
object
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ...
(such as a
class
Class or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used differentl ...
) may be replaced by a sub-object (such as a class that extends the first class) without breaking the program. It is a
semantic
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and comput ...
rather than merely syntactic relation, because it intends to guarantee semantic interoperability of
types
Type may refer to:
Science and technology Computing
* Typing, producing text via a keyboard, typewriter, etc.
* Data type, collection of values used for computations.
* File type
* TYPE (DOS command), a command to display contents of a file.
* Typ ...
in a hierarchy, object types in particular. Barbara Liskov and
Jeannette Wing
Jeannette Marie Wing is Avanessians Director of the Data Science Institute at Columbia University, where she is also a professor of computer science. Until June 30, 2017, she was Corporate Vice President of Microsoft Research with oversight of i ...
described the principle succinctly in a 1994 paper as follows:
''Subtype Requirement'': Let be a property provable about objects of type . Then should be true for objects of type where is a subtype of .
Symbolically:
:
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
Hoare logic (also known as Floyd–Hoare logic or Hoare rules) is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs. It was proposed in 1969 by the British computer scientist and log ...
, which bears a certain resemblance to
Bertrand Meyer
Bertrand Meyer (; ; born 21 November 1950) is a French academic, author, and consultant in the field of computer languages. He created the Eiffel programming language and the idea of design by contract.
Education and academic career
Meyer recei ...
's
design by contract in that it considers the interaction of subtyping with
precondition
In computer programming, a precondition is a condition or predicate that must always be true just prior to the execution of some section of code or before an operation in a formal specification.
If a precondition is violated, the effect of the s ...
s,
postcondition In computer programming, a postcondition is a condition or predicate that must always be true just after the execution of some section of code or after an operation in a formal specification. Postconditions are sometimes tested using assertions wit ...
s 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
In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutabilit ...
defined in
type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundat ...
, which relies only on the
contravariance of parameter types and
covariance
In probability theory and statistics, covariance is a measure of the joint variability of two random variables. If the greater values of one variable mainly correspond with the greater values of the other variable, and the same holds for the les ...
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
A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...
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
In probability theory and statistics, covariance is a measure of the joint variability of two random variables. If the greater values of one variable mainly correspond with the greater values of the other variable, and the same holds for the les ...
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
Inheritance is the practice of receiving private property, Title (property), titles, debts, entitlements, Privilege (law), privileges, rights, and Law of obligations, obligations upon the death of an individual. The rules of inheritance differ ...
:
*
Precondition
In computer programming, a precondition is a condition or predicate that must always be true just prior to the execution of some section of code or before an operation in a formal specification.
If a precondition is violated, the effect of the s ...
s cannot be strengthened in the subtype.
*
Postcondition In computer programming, a postcondition is a condition or predicate that must always be true just after the execution of some section of code or after an operation in a formal specification. Postconditions are sometimes tested using assertions wit ...
s cannot be weakened in the subtype.
*
Invariant
Invariant and invariance may refer to:
Computer science
* Invariant (computer science), an expression whose value doesn't change during program execution
** Loop invariant, a property of a program loop that is true before (and after) each iteratio ...
s must be preserved 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
''Object-Oriented Software Construction'' is a book by Bertrand Meyer, widely considered a foundational text of object-oriented programming. The first edition was published in 1988; the second, extensively revised and expanded edition (more than 1 ...
''. Both Meyer, and later Pierre America, who was the first to use the term ''behavioral subtyping'', gave
proof-theoretic
Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Barwise (1978) consists of four corresponding parts, ...
definitions of some behavioral subtyping notions, but their definitions did not take into account
aliasing
In signal processing and related disciplines, aliasing is an effect that causes different signals to become indistinguishable (or ''aliases'' of one another) when sampled. It also often refers to the distortion or artifact that results when a ...
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.
Criticism
While widely used, the characterization of
behavioral subtyping In object-oriented programming, behavioral subtyping is the principle that subclasses should satisfy the expectations of clients accessing subclass objects through references of superclass type, not just as regards syntactic safety (such as the abse ...
as the ability to substitute subtype objects for supertype objects has been said to be flawed. It makes no mention of ''specifications'', so it invites an incorrect reading where the ''implementation'' of the supertype is compared to the ''implementation'' of the subtype. This is problematic for several reasons, one being that it does not support the common case where the supertype is abstract and has no implementation. Also, more subtly, in the context of object-oriented imperative programming it is difficult to define precisely what it means to universally or existentially quantify over objects of a given type, or to substitute one object for another.
When applying subtyping, generally we are not substituting subtype objects for supertype objects, we are simply using subtype objects as supertype objects. That is, it is the same objects, the subtype objects, that ''are also'' supertype objects.
In an interview in 2016, Liskov herself explains that what she presented in her keynote address was an "informal rule", that Jeannette Wing later proposed that they "try to figure out precisely what this means", which led to their joint publication
on behavioral subtyping, and indeed that "technically, it's called behavioral subtyping".
During the interview, she does not use substitution terminology to discuss the concepts.
See also
*
Composition over inheritance
Composition over inheritance (or composite reuse principle) in object-oriented programming (OOP) is the principle that classes should achieve Polymorphism (computer science), polymorphic behavior and code reuse by their object composition, compo ...
*
Program refinement
*
Referential transparency
In computer science, referential transparency and referential opacity are properties of parts of computer programs. An expression is called ''referentially transparent'' if it can be replaced with its corresponding value (and vice-versa) withou ...
*
Type signature
In computer science, a type signature or type annotation defines the inputs and outputs for a function, subroutine or method. A type signature includes the number, types, and order of the arguments contained by a function. A type signature is typ ...
*
SOLID
Solid is one of the State of matter#Four fundamental states, four fundamental states of matter (the others being liquid, gas, and Plasma (physics), plasma). The molecules in a solid are closely packed together and contain the least amount o ...
– the "L" in "SOLID" stands for Liskov substitution principle
References
Bibliography
Specific references
* A keynote address in which Liskov first formulated the principle.
*
General reference
* This paper surveys various notions of behavioral subtyping, including Liskov and Wing's.
*
An updated version appeared: The formalization of the principle by its authors.
* Contains a gentler introduction to behavioral subtyping in its various forms in chapter 2.
* An article popular in the object-oriented programming community that gives several examples of LSP violations.
* This paper discusses LSP in the mentioned context.
External links
*
Liskov Substitution Principle ExplainedSOLID Class Design: The Liskov Substitution PrincipleLSP: Liskov Substitution Principle
{{DEFAULTSORT:Liskov Substitution Principle
Object-oriented programming
Type theory
Programming principles
Formal methods
Programming language semantics