Editing Liskov substitution principle (section)

== 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 (computer science)|correctness]]).

Behavioural subtyping is a stronger notion than typical [[subtyping of functions]] defined in [[type theory]], which relies only on the [[covariance and contravariance (computer science)|contravariance]] of parameter types and [[covariance and contravariance (computer science)|covariance]] of the return type. Behavioural subtyping is [[Undecidable problem|undecidable]] in general: if ''q'' is the property "method for ''x'' [[halting problem|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 [[Type signature|signatures]] that have been adopted in newer object-oriented programming languages (usually at the level of classes rather than types; see [[Subtyping#Subtyping schemes|nominal vs. structural subtyping]] for the distinction):

* [[Covariance and contravariance (computer science)|Contravariance]] of method parameter types in the subtype.
* [[Covariance and contravariance (computer science)|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 (object-oriented programming)|inheritance]]:

* [[Precondition]]s cannot be strengthened in the subtype.
* [[Postcondition]]s cannot be weakened in the subtype.
* [[Class invariant|Invariants]] cannot be weakened in the subtype.
* History constraint (the "history rule"). Objects are regarded as being modifiable only through their methods ([[Encapsulation (computer science)|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 is, for example, defining a ''mutable point'' as a subtype of an ''immutable point''.<ref>{{Cite journal |last1=Kinsbruner |first1=Elad |last2=Itzhaky |first2=Shachar |last3=Peleg |first3=Hila |date=2024 |title=Constrictor: Immutability as a Design Concept |journal=38th European Conference on Object-Oriented Programming (ECOOP 2024) |series=Leibniz International Proceedings in Informatics (LIPIcs) |volume=313 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |pages=22:1–22:29 |doi=10.4230/LIPIcs.ECOOP.2024.22|doi-access=free |isbn=978-3-95977-341-6 }}</ref> 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.