Agile Software Development# 10.LSP: The Liskov Substitution Principle

10.LSP: The Liskov Substitution Principle

SUBTYPES MUST BE SUBSTITUTABLE FOR THEIR BASE TYPES.

📌Barbara Liskov wrote this in 1988:

If for each object $o_1$ of type $S$ there is an object $o_2$ of type $T$ such that for all programs $P$ defined in terms of $T$, the behavior of $P$ is unchanged when $o_1$ is substituted for $o_2$ then $S$ is a subtype of $T$.

📌What does LSP solve?

OCP demonstrates inheritance is IMPORTANT.

LSP will introduce how to best use inheritance.

📌Example of a Violation of the LSP

A violation of LSP causing a violation of OCP!⚠

//A violation of LSP causing a violation of OCP.
struct Point {double x,y;};
struct Shape 
{
    enum ShapeType {square, circle} itsType;
    Shape(ShapeType t) : itsType(t) {}
};
struct Circle : public Shape
{
    Circle() : Shape(circle) {};
    void Draw() const;
    Point itsCenter;
    double itsRadius;
};
struct Square : public Shape
{
    Square() : Shape(square) {};
    void Draw() const;
    Point itsTopLeft;
    double itsSide;
};
void DrawShape(const Shape& s)
{
    if (s.itsType == Shape::square)
        static_cast<const Square&>(s).Draw();
    else if (s.itsType == Shape::circle)
        static_cast<const Circle&>(s).Draw();
}

Apparently, the DrawShape function is trying to use LSP which takes Shape as an argument. But it failed, and it is violating LSP and thus violating OCP as well... When a new shape comes in, we have to modify the DrawShape once again...

📌Potential problem of LSP and its solution

Problem

Since LSP asks for a BaseClass and DerivedClass relationship, a.k.a. IS-A relationship. Sometime, this kind of relationship would mislead ourself.

For example, we are known with common sense, Square is a Rectangle. Therefore, square is a subtype of rectangle.

​x
class Rectangle
{
    public:
        void SetWidth(double w) {itsWidth=w;}
        void SetHeight(double h) {itsHeight=w;}
        double GetHeight() const {return itsHeight;}
        double GetWidth() const {return itsWidth;}
    private:
        Point itsTopLeft;
        double itsWidth;
        double itsHeight;
};

class Square : public Rectangle{};

However, SetWidth , SetHeight, itsWidth, and itsHeight are redundant information since square is 1:1 size.

Drawback

• Memory Waste: Considering in a CAD/CAE product, millions of squares take redundant bits will cause memory waste.
• Confused API: These functions are inappropriate since width and height of a square are identical.

Solution

The solution is obvious. We could override the SetWidth and SetHeight function.

xxxxxxxxxx
void Square::SetWidth(double w)
{
    Rectangle::SetWidth(w);
    Rectangle::SetHeight(w);
}
void Square::SetHeight(double h)
{
    Rectangle::SetHeight(h);
    Rectangle::SetWidth(h);
}

📌Who is the boss of LSP?

The clients.

If we see it from the creator of Square and Rectangle

Everything seems pretty good so far.

If we see it from others, possible clients themselves

The test function will fail if we pass a Square inside.

xxxxxxxxxx
void g(Rectangle& r)
{
    r.SetWidth(5);
    r.SetHeight(4);
    assert(r.Area() == 20);
}

Therefore, there is nothing wrong of current design. It only smells when it encounters such situation. Therefore, the boss of LSP should only be expressed in terms of clients.

📌DBC - Design by Contract

Why DBC?

Since LSP is quite unpredictable and unquantified, developers refer to DBC - design by contract.

What is DBC?

The contract of that class is explicitly stated.

What does it state?

• precondition, must be true in order for the method to execute.
• postcondition, which is guaranteed to be true by method.

Example

precondition

xxxxxxxxxx
// A rectangle
Rectangle r;

method

xxxxxxxxxx
Rectangle::SetWidth(double w);

postcondition

xxxxxxxxxx
assert((itsWidth == w) && (itsHeight == old.itsHeight));

📌DBC meets changes

Rules

The precondition of derived class: can be stronger or normal ($\ge$)

The postcondition of derived class: can be weaker or normal ($\le$)

Example

Square is derived class of Rectangle.

The postcondition of Rectangle is assert((itsWidth == w) && (itsHeight == old.itsHeight));

The postcondition of Square is unset right now. Therefore, it is weaker.⚠❌

Therefore, it violates the LSP.

📌Example - Customized Set

✏Problem1

A commercial 3rd party library has container classes, e.g. Set. The Set has 2 following versions:

• BoundedSet, similar to array with fixed size memory allocation
• UnboundedSet, similar to dynamic array with no limit on the amount of elements

The author may 1️⃣in the future replace such class into a more appropriate and efficient container class.

🔨Solution1

Regarding the first problem, use ADAPTER method.

xxxxxxxxxx
template <class T>
class Set
{
    public:
        virtual void Add(const T&) = 0;
        virtual void Delete(const T&) = 0;
        virtual bool IsMember(const T&) const = 0;
};

By using the preceding interface, the client code needn't to care which set it used. They only focus on Add, Delete, etc.

✏Problem 2

Meanwhile, part of the 3rd party class 2️⃣doesn't support template programming. For example, if I want to use PersistentSet, I have to register PersistentObject first.

🔨Solution2

Therefore, we can take the following strategy - delegate the process.

xxxxxxxxxx
void PersistentSet::Add(const T& t)
{
    PersistentObject& p = dynamic_cast<PersistentObject&>(t);
    itsThirdPartyPersistentSet.Add(p);
}

⚒Solution1+Solution2 = All In One

It is to combine everything into a compact system.

📌Example - Line and LineSegment

The Line here is a mathematical line which can extend to infinity.

The LineSegment here is a geometrical line whose length can be measured.

Problem

With common sense, the LineSegment is a derived class of Line.

xxxxxxxxxx
class Line
{
    public:
        Line(const Point& p1, const Point& p2);
        double GetSlope() const;
        double GetIntercept() const;               // pay attention to here!! Y Intercept
        Point GetP1() const {return itsP1;};
        Point GetP2() const {return itsP2;};
        virtual bool IsOn(const Point&) const;     // pay attention to here!!
    private:
        Point itsP1;
        Point itsP2;
};

class LineSegment : public Line
{
    public:
        LineSegment(const Point& p1, const Point& p2);
        double GetLength() const;
        virtual bool IsOn(const Point&) const;
};

The LineSegment is a derivative of Line. The IsOn() method is set to virtual and everything seems ok. But if I do this on LineSegment will fail⚠❌:

xxxxxxxxxx
Assert(IsOn(Intercept()) == true);

Apparently, the intersection point(red🔴) of LineSegment may be not on itself.

Solution

Therefore, we could see a division here. Line cannot be the base class of LineSegment. Then the strategy shifts to segregate the Line into a LinearObject class.

xxxxxxxxxx
//------------linearobj.h------------//
#ifndef GEOMETRY_LINEAR_OBJECT_H
#define GEOMETRY_LINEAR_OBJECT_H
#include "point.h"

class LinearObject
{
        public:
                LinearObject(const Point& p1, const Point& p2);
                double GetSlope() const;
                double GetIntercept() const;
                Point GetP1() const {return itsP1;};
                Point GetP2() const {return itsP2;};
                virtual int IsOn(const Point&) const = 0; // abstract. (pure virtual function is abstract)

        private:
                Point itsP1;
                Point itsP2;
};

#endif


//------------lineseg.h------------//
#ifndef GEOMETRY_LINESEGMENT_H
#define GEOMETRY_LINESEGMENT_H
#include "point.h"
#include "linearobj.h"

class LineSegment : public LinearObject
{
        public:
                LineSegment(const Point& p1, const Point& p2);
                double GetLength() const;
                virtual bool IsOn(const Point&) const;
};

#endif


//------------line.h------------//
#ifndef GEOMETRY_LINE_H
#define GEOMETRY_LINE_H
#include "point.h"
#include "linearobj.h"

class Line : public LinearObject
{
    public:
        Line(const Point& p1, const Point& p2);
        virtual bool IsOn(const Point&) const;
};

#endif

📌Rules learned from previous example⭐⭐⭐

We can state that if a set of classes all support a common responsibility, they should inherit that responsibility from a common superclass. If a common superclass does not already exist, create one, and move the common responsibilities to it.

📌Heuristics and Conventions

A derivative that does less than its base is usually not substitutable for that base, and therefore violates the LSP. Base class should do more than derived class.

📌What is Degenerate function?

A function in Base Class while it won't be used in Derived Class.