0

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?

  • 1
  • 1
  • 1
    The history requirement is also a kind of an invariant (in the informal sense); in the original 1994 paper by Liskov & Wing, they make a formal distinction between (1) invariants (in a more narrow sense) - which are true for each individual state considered in isolation (e.g. given some stack implementation, the size of the stack is always < capacity; you can determine this by examining property values on a single state), and (2) history properties, which are invariant across sequences of states (e.g. capacity only grows - you need to compare two states in a time sequence to verify this). – Filip Milovanović Apr 12 at 1:17
  • 1
    So I guess an example wold be; your size is, say 5, and capacity 50; you then reduce the capacity to 10 - this breaks the history property, but maintains the size < capacity invariant. It's perhaps a bit trickier to see how the mutable point example represents a history rule violation - but, if you examine it a bit more closely, you can't determine that a state mutation has happened by just looking at a single state and comparing field values on that state; you have to know two states - the previous one & the current one, to know that there was a state change. – Filip Milovanović Apr 12 at 1:22
4

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.

| improve this answer | |
  • The quote you linked to only says that using protected is generally too open, not always. Thus, the feature is not an error. Remember, all those corner-cases are important too! – Deduplicator Apr 12 at 19:41
  • @Deduplicator unfortunely, I have no link to the book with the exact quotation. So I linked to a discussion with a similar quote. The real quote is "Fortunately, you don't have to use protected data in C++; private is the default in classes and is usually the better choice" and "In retrosepect, I think that protected is a case where good arguments and fashion overcame my better judgement". He nevertheless states that protected is fine for operations. – Christophe Apr 12 at 20:15
3

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.

| improve this answer | |
  • "program won't break" really means that the procedure (or a collaboration of objects) that uses the type in that particular role won't break. I do agree that the point-circle example is confusing; perhaps a better arrangement that would make more sense semantically would be something like: there's a role interface AnchorPointSource (a thing that can provide an (X, Y) pair to serve as an anchor point), and then have both point and circle (and some other types) implement that - assuming this serves some purpose in the domain. LSP essentially defines "is-a" as a behavior-based relationship. – Filip Milovanović Apr 12 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.