This is the sixth part of the Types and Programming Languages series. For your convenience you can find other parts in the table of contents in Part 1 — Do not return in finally

Today couple words about Liskov substitution princple (LSP for short). It is often misunderstood which leads to unclear directions how to apply it. I know there are multiple articles on the Internet explaining LSP, however, they often focus on incorrect examples and spread misinformation. In this post I’ll briefly cover the principle and common misconceptions I often see.

Table of Contents

Origins

It’s important to understand where the principle comes from. Many programmers learned LSP by example with Rectangle and Square types which at some point was almost everywhere on the Internet. For instance, you could find it on Wikipedia as a “typical violation”, in discussion on Stack Overflow, or even in Robert C. Martin’s article.

The example is typically stated as follows: we have a class Rectangle with two setters for setting side lengths. Then we derive with class Square which modifies both sides’ lengths at once when any of the setters is called. Explanation typically says that modifying both sides at once violates the LSP.

This example is flawed and completely misses the point. To see why we need to understand main point of LSP.

The principle comes from A Behavioral Notion of Subtyping paper from 1994. It considers issues with covariance, contravariance, subtyping, contracts, invariants, and history. I assume you understand what these things are as I won’t be defining them here. Important part is this requirement:

Subtype Requirement: Let $\phi(x)$ be a property provable about objects $x$ of type $T$ . The $\phi(y)$ should be true for objects $y$ of type $S$ where $S$ is a subtype of $T$ .

In short, we have a set of properties which we can prove for a base type. We require the same properties being provable for any instance of the subtype. This sounds simple but may actually be very misleading. Let’s take the following C# code:

class BaseType{
    public virtual void Foo(){
        Console.WriteLine("Literal");
    }
}

class BaseType{

public virtual void Foo(){

Console.WriteLine("Literal");

}

I compiled it using Sharplab and this is the machine code I obtained:

BaseType.Foo()
    L0000: mov ecx, [0x19d27e88]
    L0006: call System.Console.WriteLine(System.String)
    L000b: ret

BaseType.Foo()

L0000: mov ecx, [0x19d27e88]

L0006: call System.Console.WriteLine(System.String)

L000b: ret

Let’s get back to the Subtype Requirement. I can define $\phi(x)$ for $x$ of type BaseType as $\phi(x)= \text{method Foo executes the exact machine code I obtained in Sharplab}$ . Can I prove it for instances of type BaseType? Yes, I can. So according to the Subtype Requirement, all subtypes should define Foo in a way that it generates exactly the same machine code. Effectively this means that there is no use in overriding the method as it must work in the same way.

Clearly, this is very limiting as it effectively blocks logic overriding in subtypes. Is that what LSP says?

Contract — why is Rectangle Example completely broken

LSP is all about the contract we define. The paper discusses invariants, pre- and post- conditions, and history principle which all define how the type should behave. Important thing to understand here is that contract is given explicitly. It’s not something we assume because “it’s reasonable” or “it’s logical”. It must be clearly defined so users know what to expect.

Coming back to the Rectangle Example. The way it’s stated makes sense, Square modifies both sides at once so it “clearly” violates the principle. Let’s now consider a little more realistic example.

We have a type Component which represents an element of a user interface. It has two dimensions: width and height. Now, let’s introduce a RatioPreservingComponent which shows an image but preserves the ratio (e.g. 4:3) so when we modify one side then the other gets updated as well. Does it break LSP? If you answered “no” then explain how is it different from Rectangle Example? If you answered “yes” then think for a sec how to model your components so you don’t break the principle.

Just to be clear: RatioPreservingComponent does not break LSP nor does Square. But it’s not because “changing two fields instead of one doesn’t break LSP”. It’s because LSP considers contract only, not something which makes or doesn’t make sense. It covers contracts which are well defined and explicit. Even Robert C. Martin makes this mistake when discussing LSP as he says:

Was the programmer who wrote that function justified in assuming that changing the width of a Rectangle leaves its height unchanged?
Clearly, the programmer of g made this very reasonable assumption.

But the whole point of LSP is to not make “reasonable assumptions” but to define contracts. Otherwise we may assume that subtypes’ methods should have exactly the same machine code. If you think that it’s illogical (I agree) then how do we define which assumptions are “just right” and which should be ignored?

Now, how do we fix the Rectangle Example? We need to explicitly define the contract saying that setter for one side should never modify the other. Yes, that’s all we need, just one line of comment and then the contract is specified explicitly and we don’t need to wonder if “programmer made a reasonable assumption”.

And just to clarify one thing. I’m not saying that RationPreservingComponent is the right way to model that constraint nor that it’s a nice design. All I’m saying is that it doesn’t break LSP.

How to specify and validate a contract

How can we specify a contract? That depends a lot on the technology you use and what your platform supports. Let’s cover couple of mechanisms.

Type system

Probably the most powerful mechanism and most commonly used. By specifying variables’ types we can specify the contract (and often enforce it at the same time). For instance, if method of your type returns String then subtypes’ methods should return String as well (up to some covariance, obviously). Depending on the language it may not be possible to change return type in the subtype or it may be allowed with some techniques like bridge methods.

Some languages support dependent types and allow to define requirements even more. For instance, in Idris you can specify that returned list has the same number of elements as the list provided in the input parameter. Even nullability can be supported this way, for instance by using non-null types or type annotations.

Type system has yet another powerful feature. It is typically verified by the compiler which means that it’s “impossible” to generate a program which breaks the type system. We typically don’t even think about that as an LSP but that’s exactly it: an explicit specification of a type is a contract which must not be violated.

Signatures

It may sound like the same thing as in previous section but it includes couple more things. A signature of a function is something which uniquely identifies it in the codebase. Typically it includes function name and parameters. Depending on the language we may say that it includes returned type as well. However, it is much broader.

Signature specifies a way to call the method. If we have two methods matching the same signature then we may need some external rules to deciding which one to call (for instance depending on the operator overloading) but generally signature uniquely tells which method to call and how to do it. So it must include other things as well: calling convention (where to put parameters and how), marshalling (how to encode values), cleanup rules (who removes parameters from the stack), parameter mangling (whether to encode parameter types in the name), who deallocates memory and many more. This even covers the thing which we take for granted now — that the subtype even has the method. Something which wasn’t obvious in early days.

If all you do is call one Java method from another Java method then you don’t need to think about this at all as JVM takes care of that. But once you enter interop world and call native code from managed one then you need to think about all these little parts.

Documentation

Yes, this is yet another way to define a contract. This could be anything, unstructured comment in the codebase, javadoc, official documentation, internal wiki, or even well-known convention that functions like these in this org do something in this specific way.

This method may be a little brittle as we know that five hours of debugging can save you five minutes of reading the documentation. It typically cannot be verified automatically, not to mention that programmers often don’t even know where to find it. However, this is actually THE way to define the contract as most languages don’t allow to define all the requirements we may have using type system or with things verified by the compiler.

Unit tests

Yet another way to define a contract. Actually, according to “clean code” principles, unit tests can serve as documentation, tutorial, and automated way to verify contracts.

But how do you verify contracts with unit tests? One of the techniques is to tests your mocks with unit tests for production code. Imagine that you have a repository class which encapsulates some data collection. It may be backed by database or whatever else if you wish (I’m not going to discuss what repository is and whether it should have generic methods, not this time). At the same time you may have fake repository in your unit tests which holds objects in memory. Since it should mimic the real one, you should be able to test it with your tests as well.

So we can define unit tests to verify contracts. Coming back to Rectangle Example — we can actually write a unit test to verify that calling one setter doesn’t change the other side length and then run this test on all subtypes in our codebase.

Formal proofs

There are multiple things which we would like to hold but we can’t verify easily. This may include Coq proofs (like in Idris), declarative constraints (as in ILP), or consistency protocols (with TLA+). This is often used in a little different context, we typically have the contract and want to make sure it’s not violated by the type in any situation. It’s not like in unit tests where we verify examples. With formal proofs we want to provide guarantees that it works for all abstraction classes uniformly.

Hyrum’s Law

There is one more thing which we need to cover here. It’s called Hyrum’s Law and it says that once we have enough users then it doesn’t matter what we put in the contract as all observable behavior will be taken as a dependency at some point.

While this law is obviously correct, it’s beyond the scope of LSP. In theory we can always say that things not included in contracts can be changed freely. However, once our application is mature enough it may be just too expensive to change behavior which someone depends upon. Again, this is beyond the scope of LSP as Liskov principle talks about explicit contracts.

Misconceptions

And now couple misconceptions.

First, already mentioned Rectangle Example. Once again, it’s about saying explicitly that one setter cannot change the length of the other side.

Remove operation in java.util.List. It explicitly says that remove is an optional operation. It throws UnsupportedOperationException in that case which is clearly specified in the documentation. Some programmers think that if a subtype of List doesn’t implement removal operation then it breaks LSP. It’s exactly the opposite. Once again, LSP is not about some “reasonable assumptions”, it’s about explicitly defined contracts. Actually, similar thing is with putting to map as it is an optional operation.

Objects’ equality. We may try implementing equals as a mix of casting another variable to our type and comparing fields. However, this won’t work because it must be symmetric, so x.equals(y) must return true if and only if y.equals(x) does. However, even if we check inheritance hierarchy and cast to the base type, we break the transitivity. equals with subtypes adding more state must always return false.

It looks slightly different with equality operator for floating point numbers based on IEEE754. It is defined that NaN == NaN returns false. Equals and == are different.

Hash code implementation. We need to remember that hash code is not required to return distinct value when called on unequal objects. Specifically, hash code returning the same constant value for all instances is perfectly fine, even though not very practical. Another misconception is that hash code must be constant over object’s lifetime. It’s not true, hash code is allowed to change when fields used for equality change.

Another misconception is that interfaces do not take part in LSP as they don’t define any implementation so there is nothing to be broken in the subtype. I believe after reading this post it’s obvious how far from truth it is.