Liskov Substitution Principle

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.³

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.¹ - 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 corollaries⁴:

Preconditions (conditions true prior to method execution) cannot be strengthened in the subtype. In other words, the subtype method’s domain (set of possible inputs) must be a superset of supertype method.
Postconditions (conditions true post method execution) cannot be weakened in the subtype. The subtype method’s range (set of possible outputs) must be a subset of supertype method.
Invariants (data that remains unchanged by the method) must be preserved in the subtype.

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 ¹

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 is¹⁴, 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

Liskov Substitution Principle says that subtypes should not alter expected behavior of supertypes.
Passing a subtype in lieu of a supertype should be totally transparent with no special handling required on the part of clients.
LSP implies that preconditions may not be tightened, postconditions not weakened, and invariants not modified by a subtyped method.
Violations of LSP may indicate a flawed hierarchy.
Since compilers can’t flag LSP violations, expected behavior of base classes/interfaces must be well documented in the code.