Liskov substitution principle: clarification about the "history rule"

Question

I`m trying to understand the LSP History rule. I have read Wikipedia entry which states the requirement and provides an example:

History constraint (the "history rule"). Objects are regarded as being modifiable only through their methods (encapsulation). Because subtypes may introduce methods that are not present in the supertype, the introduction of these methods may allow state changes in the subtype that are not permissible in the supertype. The history constraint prohibits this. It was the novel element introduced by Liskov and Wing.
A violation of this constraint can be exemplified by defining a mutable point as a subtype of an immutable point. This is a violation of the history constraint, because in the history of the immutable point, the state is always the same after creation, so it cannot include the history of a mutable point in general. Fields added to the subtype may however be safely modified because they are not observable through the supertype methods. Thus, one can derive a circle with fixed center but mutable radius from immutable point without violating LSP.

In my opinion, there is a problem with this example. Inducing the subtype Mutable point to the supertype Immutable Point breaks the invariant requirement.

Invariants of the supertype must be preserved in a subtype.

Can you think of a more suitable example of a bad OO design that does not comply with the history rule but nevertheless satisfies the invariant requirement?

Alternatively can you provide another explanation for why this requirement is necessary?

Answer 1

You are right: the example of a mutable point derived from an immutable point is not the best and most convincing one. It's not from Liskow and Wing: they used stacks and bags as example, in their article.

Fortunately, yes, there are plenty of examples of bad design that respects LSP spirit and the invariants but not the history rule.

In his book "The design and evolution of C++" (page 301-302), Bjarne Stroustrup explains why protected members were introduced in the language, why it appeared to be a nice feature in the first place, and how it turned up a couple of years later to be a very bad idea in view of all the nasty bugs it created. He explicitly referred to Barbara's Liskov work and her seminal article about type hierarchies. He even advised not to use protected members.

Based on this input you can find examples yourself in code where a derived class accesses protected members directly.

Example: Let's imagine a super-simple robot that just maintains position and moves to another position:

class Robot {
protected:
    int x, y, z;  // 3D coordinates of the robot
    // invariant:  x and y are between 0 and 1000, and Z between 0 and 10
public:
    virtual void move(int newx, int newy, int newz);  // to change coordinates
    virtual ~Robot();
};

And imagine a couple of subtypes:

class SpeedyRobot: public Robot {
public:
    void goback_to_base();
};

class SuperSpeedyBot : public SpeedyBot {
public:
    int move(int newx, int newy, int newz) override; // does additional things
};

Now imagine that goback_to_base() does not use move() as it should but that it directly changes x,y,z. All the invariants may be ok. The post-condition may be ok as well. But it did not use the right way to achieve its goal. So tests may be succeed but the whole thing could fail because: the robot doesn't move (e.g. move not just updates the position but also activates servos). The change in the state of the super-type shall be fully explainable with the use of super-type operations.

Imagine that the SuperSpeedyRobot overrides move(), to extend the feature in a way to be compliant with the history rule (i.e. it would call Robot::move()) but with some additional behavior, like logging the movements. Everything would work fine, until someone calls goback_to_base() because that special movement would be logged. Note that this issue is not a problem with history rule, but a consequence of it.

Answer 2

Invariance is just one type of history.

It all comes down to the "is-a" principle. This is why I do not agree with the statement

Thus, one can derive a circle with fixed center but mutable radius from immutable point without violating LSP.

The coordinates of the point are hacked for a new purpose. The fact that the center of a circle is a point does not make a circle a point. This way you could descend anything that just happens to have two numbers as properties from Point and claim you are good. This is a too technical approach, we should respect semantics as well.

But, you may argue, my program won't break if I were to use circles (with a default radius I do not care about) for all my points. That is only true as long as you do not draw anything.

This may be the example you asked for. Invariance is satisfied if you only look at the data. However, if you bring in semantics and behavior, things will fall apart.