Many developers will have heard of Barbara Liskov, through her appearance in Robert C. Martin’s SOLID list of design principles. The abstract of her 1994 paper with Jeanette Wing, A Behavioral Notion of Subtyping, makes the principle sound easy in, well, in principle:
This paper takes the position that the relationship [between supertype and subtype] should ensure that any property proved about supertype objects also holds for its subtype objects.
Then it becomes a little more opaque when written in the body of the paper:
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.
People often stop here, which doesn’t really give enough information to effectively apply the principle, though it certainly gives enough information to sagely quote an academic “principle” while trashing someone in a code review. Such treatments are unfair representations of a 31-page paper which gives two different descriptions of the relationship between supertype and subtype, along with a discussion of which is preferable and why. Computer programming is a complex activity, and sometimes its ideas need space to be conveyed well.
The first (and preferred, according to Liskov and Wing) formulation says this. Imagine that a type is defined with a Bertrand Meyer-style contract, explaining the type’s name, values, and its methods along with their preconditions and postconditions. In addition to invariants – predicates that are always true whatever methods are applied to a type, there are constraints: predicates that restrict the historical relationship between states of a type instance. A constraint might be something like:
for all stacks s,
s.size > 0.
Now, no matter how much you call s.pop(), you’re never going to get a stack of size -1.
The subtype property says that S is a subtype of T if these things hold, for all s that are members of the subtype S:
- the invariants of S applied to s imply the invariants of T applied to (s treated as a member of T).
- there is a method on S with the same number of arguments as a corresponding method on T, where:
– each argument in the T version is a subtype of the corresponding argument in the S version;
– the return value of the S version is a subtype of the return value of the T version, or neither method returns a value;
– the set of exceptions raised by the S version is a subset of the exceptions raised by the T version;
– the preconditions of the T version applied to (s treated as a member of T) imply the preconditions of the S version;
– the postconditions of the S version imply the postconditions of the T version applied to (s treated as a member of T).
3. the constraints of S applied to s imply the constraints of T applied to (s treated as a member of T).
Notice that the methods don’t need to have the same name on both types! If you have a renaming operation such that “s treated as a member of T” maps all of the T method names onto the S method names, and otherwise the rules hold, then you still have a subtype. Also there’s no mention of inheritance. One of the biggest reasons programmers using OOP get into a pickle is using inheritance for multiple purposes. In a Smalltalk program, inheritance is simply a way to access method implementations from one class in another class. In Java, the compiler enforces properties that are an incomplete subset of the subtype rule, so inheritance is kinda code reuse and kinda subtyping, and hilarity ensues. Particularly if you use Java’s arrays anywhere in a method signature.
One of the things that makes Liskov such an influential author is that she believes that academic software engineering needs to be applicable to practice to be of any value. As she said in Barbara Liskov on Programming, Career, and the Future:
In my research area of software systems, it’s also very important to reduce ideas to practice. This means that the solutions I invent need to be “sufficient” to solve the problem; they should be as simple as possible, but the system has to really run, and it has to run with good enough performance.
So she is also co-author, with John Guttag, of Program Development in Java: Abstraction, Specification, and Object-Oriented Design in which a practical, modular approach to designing software through specification is expounded. Yes, the subtype principle is given nine pages.
While this article has focussed on Barbara Liskov’s contribution to type theory and program design, she’s had a varied career working on programming languages, concurrent systems, error correction, and information security. People are still debating the principles outlined in the 1994 paper on subtypes, and in her words (the IEEE interview again):
Actually, I think research does have an impact on industry. The problem is that the time lag can be quite long.
So look out for more articles in De Programmatica Ipsum in the 2040s about how Barbara Liskov revolutionised distributed systems theory.
Cover photo by Adrian Kosmaczewski.
