Liskov substitution principle
Encyclopedia
Substitutability is a principle in object-oriented programming
. It states that, in a computer program
, if S is a subtype
of T, then objects of type T may be replaced with objects of type S (i.e., objects of type S may be substitutes for objects of type T) without altering any of the desirable properties of that program (correctness, task performed, etc.). More formally, 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 entitled Data abstraction and hierarchy. It is a semantic
rather than merely syntactic relation because it intends to guarantee semantic interoperability of types
in a hierarchy, object type
s in particular. Liskov and Jeannette Wing
formulated the principle succinctly in a 1994 paper as follows:
In the same paper, Liskov and Wing detailed their notion of behavioral subtyping in an extension of Hoare logic
, which bears a certain resemblance with Bertrand Meyer
's Design by Contract
in that it considers the interaction of subtyping with pre- and postconditions.
Behavioral subtyping is a stronger notion than typical subtyping of functions defined in type theory
, which relies only on the contravariance
of argument types and covariance
of the return type. Behavioral subtyping is trivially undecidable
in general: if q is the property "method for always terminates
", then it is impossible for a program (compiler) to verify that it holds true for some subtype S of T even if q does hold for T. The principle is useful however in reasoning about the design of class hierarchies.
Liskov's 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):
In addition to these, there is a number of behavioral conditions that subtype must meet. These are detailed in a terminology resembling that of design by contract
methodology, leading to some restrictions on how contracts can interact with inheritance
:
that may occur in programming language that supports 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 MutablePoint would be a behavioral subtype of ImmutablePoint, whereas LSP forbids this.
s for the Rectangle setters, which state that dimensions can be modified independently. Violations of LSP, like this one, may or may not be a problem in practice, depending on the postconditions or invariants that are actually expected by the code that uses classes violating LSP. Mutability is a key issue here. If Square and Rectangle had only getter methods (i.e., they were immutable objects), then no violation of LSP could occur.
Object-oriented programming
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
. It states that, in a computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
, if S is a subtype
Subtype
In programming language theory, subtyping or subtype polymorphism is a form of type polymorphism in which a subtype is a datatype that is related to another datatype by some notion of substitutability, meaning that program constructs, typically subroutines or functions, written to operate on...
of T, then objects of type T may be replaced with objects of type S (i.e., objects of type S may be substitutes for objects of type T) without altering any of the desirable properties of that program (correctness, task performed, etc.). More formally, 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
Barbara Liskov is a computer scientist. She is currently the Ford Professor of Engineering in the MIT School of Engineering's Electrical Engineering and Computer Science department and an Institute Professor at the Massachusetts Institute of Technology.-Life and career:She earned her BA in...
in a 1987 conference keynote address entitled Data abstraction and hierarchy. It is a semantic
Formal semantics of programming languages
In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation...
rather than merely syntactic relation because it intends to guarantee semantic interoperability of types
Data type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
in a hierarchy, object type
Object (computer science)
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
s in particular. Liskov and Jeannette Wing
Jeannette Wing
Jeannette Marie Wing is a computer science professor at Carnegie Mellon University, Pittsburgh, Pennsylvania, United States, and assistant director for Computer and Information Science and Engineering at the NSF....
formulated the principle succinctly in a 1994 paper as follows:
- Let
be a property provable about objects 
of type 
. Then 
should be provable for objects 
of type 
where 
is a subtype of 
.
In the same paper, Liskov and Wing detailed their notion of behavioral subtyping in an extension of Hoare logic
Hoare logic
Hoare logic 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 logician C. A. R. Hoare, and subsequently refined by Hoare and other researchers...
, which bears a certain resemblance with Bertrand Meyer
Bertrand Meyer
Bertrand Meyer is an academic, author, and consultant in the field of computer languages. He created the Eiffel programming language.-Education and academic career:...
's Design by Contract
Design by contract
Design by contract , also known as programming by contract and design-by-contract programming, is an approach to designing computer software...
in that it considers the interaction of subtyping with pre- and postconditions.
Principle
Liskov's notion of a behavioral subtype defines a notion of substitutability for mutable 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).Behavioral subtyping is a stronger notion than typical subtyping of functions defined in type theory
Type theory
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
, which relies only on the contravariance
Covariance and contravariance (computer science)
Within the type system of a programming language, covariance and contravariance refers to the ordering of types from narrower to wider and their interchangeability or equivalence in certain situations ....
of argument types and covariance
Covariance and contravariance (computer science)
Within the type system of a programming language, covariance and contravariance refers to the ordering of types from narrower to wider and their interchangeability or equivalence in certain situations ....
of the return type. Behavioral subtyping is trivially undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
in general: if q is the property "method for always terminates
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
", then it is impossible for a program (compiler) to verify that it holds true for some subtype S of T even if q does hold for T. The principle is useful however in reasoning about the design of class hierarchies.
Liskov's 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):
- ContravarianceCovariance and contravariance (computer science)Within the type system of a programming language, covariance and contravariance refers to the ordering of types from narrower to wider and their interchangeability or equivalence in certain situations ....
of method arguments in the subtype. - CovarianceCovariance and contravariance (computer science)Within the type system of a programming language, covariance and contravariance refers to the ordering of types from narrower to wider and their interchangeability or equivalence in certain situations ....
of return types in the subtype. - No new exceptions should be thrown by methods of the subtype, except where those exceptions are themselves subtypes of exceptions thrown by the methods of the supertype.
In addition to these, there is a number of behavioral conditions that subtype must meet. These are detailed in a terminology resembling that of design by contract
Design by contract
Design by contract , also known as programming by contract and design-by-contract programming, is an approach to designing computer software...
methodology, leading to some restrictions on how contracts can interact with inheritance
Inheritance (computer science)
In object-oriented programming , inheritance is a way to reuse code of existing objects, establish a subtype from an existing object, or both, depending upon programming language support...
:
- PreconditionPreconditionIn 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....
s cannot be strengthened in a subtype. - PostconditionPostconditionIn 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 within the code itself...
s cannot be weakened in a subtype. - InvariantInvariant (computer science)In computer science, a predicate is called an invariant to a sequence of operations provided that: if the predicate is true before starting the sequence, then it is true at the end of the sequence.-Use:...
s of the supertype must be preserved in a subtype. - History constraint (the "history rule"). Objects are regarded as being modifiable only through their methods (encapsulation). Since 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 MutablePoint as a subtype of an ImmutablePoint. 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 MutablePoint in general. Fields added to the subtype may however be safely modified because they are not observable through the supertype methods. One may derive a CircleWithFixedCenterButMutableRadius from ImmutablePoint without violating LSP.
Origins
The rules on pre- and postconditions are identical to those introduced by Bertrand Meyer in his 1988 book. 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 aliasingAliasing (computing)
In computing, aliasing describes a situation in which a data location in memory can be accessed through different symbolic names in the program. Thus, modifying the data through one name implicitly modifies the values associated to all aliased names, which may not be expected by the programmer...
that may occur in programming language that supports 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 MutablePoint would be a behavioral subtype of ImmutablePoint, whereas LSP forbids this.
A typical violation
A typical example that violates LSP is a Square class that derives from a Rectangle class, assuming getter and setter methods exist for both width and height. The Square class always assumes that the width is equal with the height. If a Square object is used in a context where a Rectangle is expected, unexpected behavior may occur because the dimensions of a Square cannot (or rather should not) be modified independently. This problem cannot be easily fixed: if we can modify the setter methods in the Square class so that they preserve the Square invariant (i.e., keep the dimensions equal), then these methods will weaken (violate) the postconditionPostcondition
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 within the code itself...
s for the Rectangle setters, which state that dimensions can be modified independently. Violations of LSP, like this one, may or may not be a problem in practice, depending on the postconditions or invariants that are actually expected by the code that uses classes violating LSP. Mutability is a key issue here. If Square and Rectangle had only getter methods (i.e., they were immutable objects), then no violation of LSP could occur.
See also
- Refinement
- SOLID The L in SOLID stands for Liskov substitution principle
- Type signatureType signatureIn computer science, a type signature or type annotation defines the inputs and outputs for a function, subroutine or method. A type signature includes at least the function name and the number of its arguments...
- Composition over inheritance
External links
- The Liskov Substitution Principle, T. S. Norvell, 2003
- The Liskov Substitution Principle, Robert C. Martin, 1996]