Liskov Substitution Principle: a misnomer?
In an influential keynote address on data abstraction and class hierarchies at the OOPSLA 1987 programming language research conference, Barbara Liskov said the following: “What is wanted here is something like the following substitution property: 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 behavior of P is unchanged when o₁ is substituted for o₂, then S is a subtype of T.” [1]
This characterisation has since been widely known as the Liskov Substitution Principle (LSP).
Unfortunately, though, it has several issues.
Firstly, in its original formulation, it is too strong: we rarely want the behavior of a subclass to be identical to that of its superclass; substituting a subclass object for a superclass object is often done with the intent to change the program’s behavior, albeit in a way that maintains the program’s desirable properties.
Secondly, it makes no mention of specifications, so it invites an incorrect reading where the implementation of type S is compared to the implementation of type T. This is problematic for several reasons, one being that it does not support the common case where T is abstract and has no implementation.
Thirdly, and most 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. [2]
Consider a program with an abstract superclass Bag and a concrete subclass Stack. In such a program, we are not substituting a Stack object for a Bag object; indeed, class Bag has no objects of its own. Instead, we are simply using a Stack object as a Bag object.
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. [3]
Indeed, in 1994 Liskov herself, together with her co-author Jeannette Wing, gave us the terminology we need to speak correctly about the semantic correctness of subclass relationships in object-oriented programming: behavioral subtyping.
Behavioral subtyping is the principle that properties that clients can prove 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. [4]
For example, consider a type Stack and a type Queue, that both have a put method to add an element and a get method to remove one. Suppose the documentation associated with these types specifies that type Stack’s methods shall behave as expected for stacks (i.e. they shall exhibit LIFO behavior), and that type Queue’s methods shall behave as expected for queues (i.e. they shall exhibit FIFO behavior). Suppose, now, that type Stack were declared as a subclass of type Queue. Most programming language compilers ignore documentation and perform only the checks that are necessary to preserve type safety. Since, for each method of type Queue, type Stack provides a method with a matching name and signature, this check would succeed. However, clients accessing a Stack object through a reference of type Queue would, based on Queue’s documentation, expect FIFO behavior but observe LIFO behavior, invalidating these clients’ correctness proofs and potentially leading to incorrect behavior of the program as a whole.
This example violates behavioral subtyping because type Stack is not a behavioral subtype of type Queue: it is not the case that the behaviors allowed by the specification of Stack are also allowed by the specification of Queue.
In contrast, a program where both Stack and Queue are subclasses of a type Bag, whose specification for get is merely that it removes some element, does satisfy behavioral subtyping and allows clients to safely reason about correctness based on the presumed types of the objects they interact with. Indeed, any object that satisfies the Stack or Queue specification also satisfies the Bag specification.
It is important to stress that whether a type S is a behavioral subtype of a type T depends only on the specification of type T; the implementation of type T, if it has any, is completely irrelevant to this question. Indeed, type T need not even have an implementation; it might be a purely abstract class. As another case in point, type Stack above is a behavioral subtype of type Bag even if type Bag’s implementation exhibits FIFO behavior: what matters is that type Bag’s specification does not specify which element is removed by method get. This also means that behavioral subtyping can be discussed only with respect to a particular (behavioral) specification for each type involved, and that if the types involved have no well-defined behavioral specification, behavioral subtyping cannot be discussed meaningfully.
In conclusion, I hope that I have convinced you that the correct terminology to use when discussing the correctness of subclass relationships in object-oriented programming is behavioral subtyping, not substitutability.
References
- Liskov, B. (May 1988). “Keynote address — data abstraction and hierarchy”. ACM SIGPLAN Notices. 23 (5): 17–34. doi:10.1145/62139.62141.
- Leavens, Gary T.; Naumann, David A. (August 2015). “Behavioral subtyping, specification inheritance, and modular reasoning”. ACM Transactions on Programming Languages and Systems. 37 (4). doi:10.1145/2766446.
- van Vleck, Tom (April 20, 2016). Interview with Barbara Liskov. ACM.
- Liskov, Barbara; Wing, Jeannette (1994–11–01). “A behavioral notion of subtyping”. ACM Transactions on Programming Languages and Systems. 16 (6): 1811–1841. doi:10.1145/197320.197383.
