Chandra Sivaraman
Programming/Software Engineering Notes

Liskov Substitution Principle26 Mar 2021

Liskov Substitution Principle Photo by Kaffee Meister on Unsplash

The Liskov Substitution Principle(LSP), also known as behavioral subtyping, was formulated by Turing Award winner Barbara Liskov, an accomplished computer scientist who also proposed the notion of Abstract Data Types among other things.

In the words of Liskov herself:

Objects of a subtype ought to behave the same as those of the supertype as far as anyone or any program using supertype objects can tell.3

In other words, it should be possible to drop in a subtype wherever a supertype is expected and the code should not just compile, but also function as expected at runtime.

I think I can safely say that of the SOLID principles, the Liskov principle is by far the least understood and applied.1 - Dino Esposito

This is a subtle principle that might seem trivial at first sight. Isn’t this just how polymorphism is supposed to work? Well, compilers can only validate polymorphism syntactically. They have no way of doing a semantic (meaning) check. It is this gap that the LSP seeks to redress. Subtypes can’t just override supertype methods willy nilly. They have to ensure that clients aren’t confused when a subtype instance is passed in where a supertype is expected.

Compilers cannot flag violations of the Liskov principle. The only way we can identify a violation is by validating the subtype’s behavior against the expected behavior of the supertype. The expected behavior of supertypes then, must be documented in the code, and implementors of subtypes must adhere to it, otherwise unexpected and hard-to-detect runtime errors might result. LSP violations usually indicate a problem with the type hierarchy. Perhaps the subtypes don’t truly satisfy the “is a” relation.

LSP implies the following corollaries4:

Intuitively, this makes sense. If the subtype can handle all the inputs that the supertype can (and some more), and output values that don’t exceed the range of values output by the supertype, and values that the supertype doesn’t change remain unchanged by the subtype, then clients that work with a supertype instance can be expected to work with a subtype instance as well.

The LSP can be better understood by looking at some examples of violations:

Missing implementations of supertype methods:

Subtype methods with missing implementations are a violation of the LSP. If the client expects the supertype to have a certain method and the subtype fails to implement it, then the subtype fails the “is a” supertype test. In the example below, ITicketingAgent represents an interface to a movie theater. Theaters can have auditoriums with reserved seating or general seating.

ITicketingAgent
+ bool IsShowSoldOut(IShow show)
+ string[] GetAvailableSeats(IReservedShow show)
+ ReserveSeats(IReservedShow show, string[] seatIds)
+ ReserveSeats(IShow show, int numSeats)

Bilbo’s theaters don’t support reserved seating. Hence the GetAvailableSeats and ReserveSeats method taking a list of seat ids is not implemented.

BilbosTicketingAgent : ITicketingAgent
+ bool IsShowSoldOut(IShow show)
+ string[] GetAvailableSeats(IReservedShow show) <= not impl
+ ReserveSeats(IReservedShow show, string[] seatIds)  <= not impl
+ ReserveSeats(IShow show, int numSeats)

Frodo’s theaters only have auditoriums with reserved seating. Hence, the methods for general seating auditoriums aren’t implemented. Both of these are violations of the LSP. It indicates our original ticketing agent abstraction may be too broad.

FrodosTicketingAgent : ITicketingAgent
+ bool IsShowSoldOut(IShow show)  <= not impl
+ string[] GetAvailableSeats(IReservedShow show)
+ ReserveSeats(IReservedShow show, string[] seatIds)
+ ReserveSeats(IShow show, int numSeats)  <= not impl

Pre-conditions violation:

The key point is that a derived class can’t just add preconditions. In doing so, it will restrict the range of possible values being accepted for a method, possibly creating runtime failures. - Dino Esposito 1

In this example, we have SimpleZip and AdvancedZip classes that compress a given string. They are both subtypes of the IZip interface. AdvancedZip adds the precondition that input should not be null, where the base interface specifies no such expectation. This is a violation of the LSP precondition rule. The thing to note here is that LSP depends on what expected behavior is specified in the base class. If the interface in this example had specified that null input would raise exception, then SimpleZip, not AdvancedZip would violate LSP.

interface IZip
{
    // returns null if input is null else returns compressed string
    string Zip(string input);
}

class SimpleZip : IZip
{
    public string Zip(string input)
    {
        if (input == null)
            return null;
        // compress spaces
        return Utils.CompressSpaces(input);
    }
}

class AdvancedZip : IZip
{
    public string Zip(string input)
    {
        if (input == null)
            throw new ArgumentException();
        return Utils.CompressRepeatingBlocks(Utils.CompressSpaces(input));
    }
}

Post-conditions violation:

The canonical example flogged to death by every other article discussing LSP is revisited here. Rectangle can be stretched by a multiplicative factor. Square rather unwisely piggybacks on Rectangle, and boxes the Height and Width to be always equal. HorizontalStretch is expected to only increase the Width and keep Height invariant. However, since Height and Weight move in concert for Square, Height is no longer invariant to HorizontalStretch. If the client was rendering the shapes and had sized the canvas expecting the Height to remain unchanged, part of the Square would now be clipped. If we overrode HorizontalStretch for Square to keep Height invariant, it would no longer remain a Square. Damned if you do, damned if you don’t. A good sign that the hierarchy isn’t sound.

class Rectangle
{
    public virtual int Height { get; set; }
    public virtual int Width { get; set; }

    // postcondition: width = factor * width
    // invariant: height
    public virtual void HorizontalStretch(int factor)
    {
        Width *= factor;
    }

    public virtual void Print()
    {
        Console.WriteLine($"Height = {Height}, Width = {Width}");
    }
}

class Square : Rectangle
{
    private int _height;
    public override int Height
    {
        get => _height;
        set => _height = _width = value;
    }

    private int _width;
    public override int Width
    {
        get => _width;
        set => _width = _height = value;
    }
}

All this is well and good, but who nowadays is using inheritance for code reuse? Is the LSP even relevant anymore? It very much is14, asserts Bob Martin, since the LSP was never about inheritance and all about subtyping. Implementing an interface is subtyping. Even in dynamic languages such as JavaScript with no formal notion of interfaces, duck typing (where an object just has the same methods as a base object’s and no formal hierarchy exists) implies an underlying interface with certain expected behavior. Subtypes violating that expected behavior pay the price in the form of runtime errors and/or code defecation in the form of if/else/switch statements with special logic for specific types.

There is a lot more to pre/post-condition violations than has been said here that requires a deeper dive into topics like covariance and contravariance. Eric Lippert has written a series of in-depth posts on this topic that should be well worth reading.

Takeaways

References

  1. ^ Cutting Edge - Code Contracts: Inheritance and the Liskov Principle
  2. Barbara Liskov: The Liskov Substitution Principle
  3. ^ A Behavioral Notion of Subtyping - B. Liskov, Jeannette Wing
  4. ^ Wikipedia: Liskov Substitution Principle
  5. SOLID Design Principles Explained: The Liskov Substitution Principle with Code Examples
  6. SOLID violations in the wild: The Liskov Substitution Principle
  7. Is this a violation of the LSP?
  8. Example of LSP Violation using vehicles
  9. Violating LSP
  10. Liskov Substitution Principle Violations
  11. How does strengthening of preconditions and weakening of postconditions violate Liskov substitution principle?
  12. How to verify the Liskov substitution principle in an inheritance hierarchy?
  13. SOLID principles – Part 3: Liskov’s Substitution Principle
  14. ^ SOLID Relevance