To const or not to const – the Liskov substitution principle

The Liskov priniple


When inheritance comes to play, it is not always clear how to design interfaces of classes to make reasonable and safe use of it. Most textbooks mention the Liskov substitution principle in this context. Informally speaking, it says that objects of derived classes must be transparently usable wherever objects of the base class are. In this article I try to get to the ultimate conclusions of this rule that I can think of. The ideas here are not entirely new, I admit I just reinvented them, (see for instance Kazimir Majorinc, Ellipse-Circle Dilemma and Inverse Inheritance), but, unfortunately, most discussions end prematurely in my opinion, and I was missing an exhaustive text to organize my thoughts and for teaching. I beg for your patience while reading this lengthy post. It is written with examples in C++11, but I believe it may be relevant to any language with inheritance.

The circle-ellipse dillema


A standard illustration of what can go wrong is the circle-ellipse dillema. We’re told at school that a circle is a particular kind of ellipse (I was, at least). So let’s try to leverage this knowledge and write

class Ellipse
  {
    double r1_, r2_;
  public:
    Ellipse(double r1, double r2) 
      : r1_(r1), r2_(r2)
      { 
      assert(r1 >= 0.0 && r2 >= 0.0);
      }
    auto GetR1(void) const -> double
      {
      return r1_;
      }
    auto Getr2(void) const -> double
      {
      return r2_;
      }
    virtual auto SetR1(double r1) -> void
      {
      assert(r1 >= 0.0);
      r1_ = r1;
      }
    virtual auto SetR2(double r2) -> void
      {
      assert(r2 >= 0.0);
      r2_ = r2;
      }
    virtual ~Ellipse(void) {}
  };

The getters are not virtual, since nothing in their working is supposed to change, but the setters are virtual in anticipation of the circle class:

class Circle : public Ellipse
  {
  public:
    Circle(double r)
      : Ellipse(r,r)
      {}
    auto GetR(void) const -> double
      {
      return GetR1();  // GetR2() would do also
      }
    virtual auto SetR(double r) -> void
      {
      assert(r >= 0.0);
      Ellipse::SetR1(r);
      Ellipse::SetR2(r);
      }
    auto SetR1(double r) -> void override
      {
      assert(r >= 0.0);
      Ellipse::SetR1(r);
      Ellipse::SetR2(r);
      }
    auto SetR2(double r) -> void override
      {
      assert(r >= 0.0);
      Ellipse::SetR1(r);
      Ellipse::SetR2(r);
      }
  };

At first look, everything in this naive example seems to work according to school mathematics intuitions. A circle is an ellipse with both radii equal, so in setters we set both the same, the getters for ellipse radii return accordingly, and the getter for the unique circle radius is free to pick any of the ellipse radii, since they’re equal anyway.
Unfortunately, this fails miserably at the substitution principle. Suppose we had, as part of our functionality, the following function

auto test(Ellipse& e) -> void
  {
  e.SetR1(17.0);
  e.SetR2(34.0);
  assert(e.GetR1()*2 == e.GetR2());
  }
auto main(void) -> int
  {
  Ellipse e(1.0,2.0);
  test(e);              // ok
  Circle c(1.0);
  test(c);              // fails
  return 0;
  }

The function test legitimately expects that it will be able to do anything that is legal on the reference to the Ellipse that it gets. But that leads to disaster. A behavioural invariant of Ellipse is violated by the use of Circle in its place.
So they lied to us in school! A circle is not a specific kind of ellipse. That’s where discussion in most textbooks ends, but there’s more to it than meets the eye.

Not entirely a lie


If we look closely at the code, we may notice that there would have been no such problem if our test code had used only the getters. Let me try to code it down:

class Ellipse
  {
    double r1_, r2_;
  public:
    Ellipse(double r1, double r2)
      : r1_(r1), r2_(r2)
      {
      assert(r1>=0.0 && r2>=0.0);
      }
    auto GetR1(void) const -> double
      {
      return r1_;
      }
    auto GetR2(void) const -> double
      {
      return r2_;
      }
    virtual ~Ellipse(void) {}
  };

class Circle : public Ellipse
  {
  public:
    Circle(double r)
      : Ellipse(r,r)
      {}
    auto GetR(void) const -> double 
      {
      return GetR1();    // GetR2() would do also
      }
  }; 

So we consider circles and ellipses as values, we only create their objects in constructors, and do not provide any state modifying methods (apart from the compiler-provided assignment, which is ok). It is easy to see that in this setup no behavioural invariants will be violated by using circles where ellipses are expected, by pointer or reference. However, we lost mutability of the objects. And that’s what maths teachers meant, there is no mutability in mathematics, so they did not lie after all, and a circle is a subclass of ellipse.

Programmingwise though, this is still an unsatisfactory answer. Until functional programming style dominates, we have to deal with mutable objects. Let us try to look again carefully at listing 1. What we see is that Circle has all the getters of Ellipse, plus some more. With setters, the converse could be true: SetR1 and SetR2 make sense only for Ellipse, whereas SetR makes perfect sense for both. But this would imply that the inheritance order should be reversed, that ellipse is a kind of circle, that is, Ellipse should inherit from Circle.

Two distinct interfaces


We have just discovered, that the restriction const on methods is not merely a convenience that allows us to push some bugs from the category of logic (hard, need debugging) into syntax (easy, compiler finds them). const and non-const methods define two fundamentally different interfaces to a class, different by the order they generalize in class hierarchy.

That may be a relevant bit of observation, but how do we translate that into code? We cannot do it in a straightfoward way, but there are workarounds. Let me essentially keep the immutable classes of listing 2, they are valuable classes that model mathematical objects quite well so deserve life, with the only difference in turning double r1_,r2_; of Ellipse into protected attributes rather than private:

class Ellipse
  {
  protected:
    double r1_, r2_;
  public:
    Ellipse(double r1, double r2)
      : r1_(r1), r2_(r2)
      {
      assert(r1>=0.0 && r2>=0.0);
      }
    auto GetR1(void) const -> double
      {
      return r1_;
      }
    auto GetR2(void) const -> double
      {
      return r2_;
      }
    virtual ~Ellipse(void) {}
  };

class Circle : public Ellipse
  {
  public:
    Circle(double r)
      : Ellipse(r,r)
      {}
    auto GetR(void) const -> double 
      {
      return GetR1();    // GetR2() would do also
      }
  }; 

Now, complete the picture with MutableCircle and MutableEllipse. What may we reasonably require from them? First, they should be usable wherever their immutable counterparts are, which translates into MutableCircle inheriting from Circle and MutableEllipse inheriting from Ellipse. Second, we would like to express the inverse order of generalization of the mutable interface. We cannot do that directly on the level of MutableEllipse and MutableCircle, because they also feature the const interface, and are already bound by the const order through inheritance. What we can do, though, is to use interface classes. Let me write:

class MutableCircleInterface
  {
  public:
    auto virtual SetR(double r) -> void = 0;
    virtual ~MutableCircleInterface(void) {}
  };

class MutableEllipseInterface : public MutableCircleInterface
  {
  public:
    auto virtual SetR1(double r1) -> void = 0;
    auto virtual SetR2(double r2) -> void = 0;
    auto SetR(double r) -> void override
      {
      assert(r >= 0.0);
      SetR1(r);
      SetR2(r);
      }
  };

class MutableCircle final 
  : public Circle, public MutableCircleInterface
  {
  public:
    MutableCircle(double r)
      : Circle(r)
      {}
    auto SetR(double r) -> void override 
      {
      assert(r >= 0.0);
      r1_ = r;
      r2_ = r;
      }
  };

class MutableEllipse final 
  : public Ellipse, public MutableEllipseInterface
  {
  public:
    MutableEllipse(double r1, double r2)
      : Ellipse(r1,r2)
      {}
    auto SetR1(double r1) -> void override
      {
      assert(r1 >= 0.0);
      r1_ = r1;
      }
    auto SetR2(double r2) -> void override
      {
      assert(r1 >= 0.0);
      r2_ = r2;
      }
  };

With this code, behavioural invariants are kept. As we already know, one cannot expect to use a MutableCircle where a MutableEllipse is expected, but it’s okay to use an object featuring a MutableEllipseInterface where MutableCircleInterface is expected. I also made the classes final. This is necessary to avoid a situation, when someone inherits from your MutableEllipse class to produce, say, HalfHeightEllipse with radii in 1 to 2 proportion, which would yield the same set of problems as did our original Circle in listing 1.

There are two things that I find bothering about this code. One is that Circle by inheriting from Ellipse wastes space, as it does not need two radii. Second is that it is asymmetric in treatment of the const and mutable interfaces. There are no such things as ConstCircleInterface and ConstEllipseInterface. It would be intersting to at least see it done with asymmetry in the other direction, and without asymmetry altogether.

Asymmetry in the opposite order


So let me try to write the solution with opposite order of asymmerty.

class PureMutableCircle
  {
  protected:
    double r_;
  public:
    PureMutableCircle(double r)
      : r_(r)
      {
      assert(r >= 0.0);
      }
    virtual auto SetR(double r) -> void
      {
      assert(r >= 0.0);
      r_ = r;
      }
    virtual ~PureMutableCircle(void) {}
  };

There is no way we can avoid protected for double r_; while sticking to pure setters interface, as otherwise there would be no way to write getters in the class with complete features. The same applies to ellipse:

class PureMutableEllipse : public PureMutableCircle
  {
  protected:
    double r1_,r2_;
  public:
    PureMutableEllipse(double r1, double r2)
      : PureMutableCircle(0.0), // whatever, ignored elsewhere
        r1_(r1), r2_(r2)
      {
      assert(r1>=0.0 && r2>=0.0);
      }
    auto SetR1(double r1) -> void 
      {
      assert(r1 >= 0.0);
      r1_ = r1;
      }
    auto SetR2(double r2) -> void 
      {
      assert(r2 >= 0.0);
      r2_ = r2;
      }
    auto SetR(double r) -> void override 
      {
      assert(r >= 0.0);
      SetR1(r);
      SetR2(r);
      }
};

For the PureMutableEllipse, we had two choices. Above, I opted for wasting the radius attribute that PureMutableEllipse inherits from PureMutableCircle. The other choice would be to change its meaning and reuse it for one chosen radius of the ellipse. Ugly as it is, this choice is displayed further below in listing 5, as my goal here is to explore all possibilities.

Whatever that choice is, we already see that setting out with pure mutable classes as the backbone for the solution gives us classes that are essentially useless. We can create such objects, sure, but the only use for them is in classes that will inherit from them and get access to stored values through the protected feature. This is in contrast to the previous solution of listing 3, where setting out with immutable classes gave us useful objects with value-semantics.

Carrying on with the choices above we come up with the following:

class ConstEllipseInterface
  {
  public:
    virtual auto GetR1(void) const -> double = 0;
    virtual auto GetR2(void) const -> double = 0;
    virtual ~ConstEllipseInterface(void) {}
  };

class ConstCircleInterface : public ConstEllipseInterface
  {
  public:
    virtual auto GetR(void) const -> double = 0;
    virtual auto GetR1(void) const -> double override
      {
      return GetR();
      }
    virtual auto GetR2(void) const -> double override
      {
      return GetR();
      }
  };

class MutableCircle final 
  : public PureMutableCircle, public ConstCircleInterface
  {
  public:
    MutableCircle(double r)
      : PureMutableCircle(r)
      {}
    auto GetR(void) const -> double override
      {
      return r_;
      }
  };

class MutableEllipse final 
  : public PureMutableEllipse, public ConstEllipseInterface
  {
  public:
    MutableEllipse(double r1, double r2)
      : PureMutableEllipse(r1,r2)
      {}
    auto GetR1(void) const -> double override
      {
      return r1_;
      }
    auto GetR2(void) const -> double override
      {
      return r2_;
      }
  };

It is now clear that, although in this version MutableCircle and MutableEllipse kind of meet our expectations, if we wanted to also have the immutable versions, we would have to re-implement them separately, since the implementations in the PureMutable variants come with the mutable interface that we do not want:

class Circle : public ConstCircleInterface
  {
    double r_;
  public:
    Circle(double r)
      : r_(r)
      {
      assert(r>=0.0);
      }
    auto GetR(void) const -> double override
      {
      return r_;
      }
  };

class Ellipse : public ConstEllipseInterface
  {
    double r1_, r2_;
  public:
    Ellipse(double r1, double r2)
      : r1_(r1), r2_(r2)
      {
      assert(r1>=0.0 && r2>=0.0);
      }
    auto GetR1(void) const -> double override
      {
      return r1_;
      }
    auto GetR2(void) const -> double override
      {
      return r2_;
      }
  };

We are now in clear violation of the Don’t Repeat Yourself rule, as most of that code is copypasted. We also lost the natural possibility of passing a MutableCircle where a Circle is expected, since the former does not inherit from the latter, but this is minor, since given the interface classes, we may expect that functions will expect pointers and references to the interface rather than to the concrete class. With this solution, we also still did not solve the waste-of-memory problem, as MutableEllipse now carries a spurious double inherited indirectly from PureMutableCircle. Let me now explore the other design option that I mentioned above, of reusing the circle’s radius in implementation of ellipse. Lines that are different are annotated with comments:

class PureMutableCircle
  {
  protected:
    double r_;
  public:
    PureMutableCircle(double r)
      : r_(r)
      {
      assert(r >= 0.0);
      }
    virtual auto SetR(double r) -> void
      {
      assert(r >= 0.0);
      r_ = r;
      }
    virtual ~PureMutableCircle(void) {}
  };

class PureMutableEllipse : public PureMutableCircle
  {
  protected:
    double r2_;
  public:
    PureMutableEllipse(double r1, double r2)
      : PureMutableCircle(r1), // reusing base class attribute for sthg else
        r2_(r2)
      {
      assert(r1>=0.0 && r2>=0.0);
      }
    auto SetR1(double r1) -> void 
      {
      assert(r1 >= 0.0);
      PureMutableCircle::SetR(r1); // forcing r1 onto base class attribute
      }
    auto SetR2(double r2) -> void 
      {
      assert(r2 >= 0.0);
      r2_ = r2;
      }
    auto SetR(double r) -> void override 
      {
      assert(r >= 0.0);
      SetR1(r);
      SetR2(r);
      }
};

class ConstEllipseInterface
  {
  public:
    virtual auto GetR1(void) const -> double = 0;
    virtual auto GetR2(void) const -> double = 0;
    virtual ~ConstEllipseInterface(void) {}
  };

class ConstCircleInterface : public ConstEllipseInterface
  {
  public:
    virtual auto GetR(void) const -> double = 0;
    virtual auto GetR1(void) const -> double override
      {
      return GetR();
      }
    virtual auto GetR2(void) const -> double override
      {
      return GetR();
      }
  };

class MutableCircle final 
  : public PureMutableCircle, public ConstCircleInterface
  {
  public:
    MutableCircle(double r)
      : PureMutableCircle(r)
      {}
    auto GetR(void) const -> double override
      {
      return r_;
      }
  };

class MutableEllipse final 
  : public PureMutableEllipse, public ConstEllipseInterface
  {
  public:
    MutableEllipse(double r1, double r2)
      : PureMutableEllipse(r1,r2)
      {}
    auto GetR1(void) const -> double override
      {
      return r_;       // reused base class attribute with no getter
      }
    auto GetR2(void) const -> double override
      {
      return r2_;
      }
  };

class Circle : public ConstCircleInterface
  {
    double r_;
  public:
    Circle(double r)
      : r_(r)
      {
      assert(r>=0.0);
      }
    auto GetR(void) const -> double override
      {
      return r_;
      }
  };

class Ellipse : public ConstEllipseInterface
  {
    double r1_, r2_;
  public:
    Ellipse(double r1, double r2)
      : r1_(r1), r2_(r2)
      {
      assert(r1>=0.0 && r2>=0.0);
      }
    auto GetR1(void) const -> double override
      {
      return r1_;       
      }
    auto GetR2(void) const -> double override
      {
      return r2_;
      }
  };

To comment on that code I will take the liberty of quoting Venkat Subramaniam, whose two great and inspiring lectures I had a chance to attend a couple of days ago (http://codedive.pl/live.html): “How do you feel writing that code? You feel dirty! Seriously, don’t you?” […] “It’s even worse! Anybody who works from home? You got about 10 seconds to close the monitor otherwise the kids look at this and say: THAT’S what you do for a living?”. Although we avoided the memory waste, we did this at the expense of writing extremely bad code, that still has all the remaining problems of listing 4. Clearly, there is no symmetry in choosing the backbone of the solution, both listing 4 and listing 5 have bigger problems than listing 3. But what if the memory expense is unbearable for us, do we have to go along the lines of listing 5, or is there a better way?

Symmetric solution


A fully symmetric solution is going to have interface classes on both const and non-const sides. We’ve already seen most of the bits that make up this solution, let me gather them together:

class MutableCircleInterface
  {
  public:
    auto virtual SetR(double r) -> void = 0;
    virtual ~MutableCircleInterface(void) {}
  };

class MutableEllipseInterface : public MutableCircleInterface
  {
  public:
    auto virtual SetR1(double r1) -> void = 0;
    auto virtual SetR2(double r2) -> void = 0;
    auto SetR(double r) -> void override
      {
      assert(r >= 0.0);
      SetR1(r);
      SetR2(r);
      }
  };

class ConstEllipseInterface
  {
  public:
    virtual auto GetR1(void) const -> double = 0;
    virtual auto GetR2(void) const -> double = 0;
    virtual ~ConstEllipseInterface(void) {};
  };

class ConstCircleInterface : public ConstEllipseInterface
  {
  public:
    virtual auto GetR(void) const -> double = 0;
    virtual auto GetR1(void) const -> double override
      {
      return GetR();
      }
    virtual auto GetR2(void) const -> double override
      {
      return GetR();
      }
  };

We now need to build the respective concrete classes out of these interfaces:

class Ellipse : public ConstEllipseInterface
  {
  protected:
    double r1_, r2_;
  public:
    Ellipse(double r1, double r2)
      : r1_(r1), r2_(r2)
      {
      assert(r1>=0.0 && r2>=0.0);
      }
    auto GetR1(void) const -> double override
      {
      return r1_;
      }
    auto GetR2(void) const -> double override
      {
      return r2_;
      }
  };

class Circle : public ConstCircleInterface
  {
  protected:
    double r_;
  public:
    Circle(double r)
      : r_(r)
      {
      assert(r>=0.0);
      }
    auto GetR(void) const -> double override
      {
      return r_;
      }
  }; 

In this picture, immutable circle is not a kind of immutable ellipse, since they do not share their implementation, but the circle’s interface is a kind of ellipse’s interface. Completing the story with the mutable counterparts is straightforward:

class MutableEllipse final 
  : public Ellipse, public MutableEllipseInterface
  {
  public:
    MutableEllipse(double r1, double r2)
      : Ellipse(r1,r2)
      {}
    auto SetR1(double r1) -> void override
      {
      assert(r1 >= 0.0);
      r1_ = r1;
      }
    auto SetR2(double r2) -> void override
      {
      assert(r2 >= 0.0);
      r2_ = r2;
      }
  };

class MutableCircle final 
  : public Circle, public MutableCircleInterface
  {
  public:
    MutableCircle(double r)
      : Circle(r)
      {}
    auto SetR(double r) -> void override
      {
      assert(r >= 0.0);
      r_ = r;
      }
  };

Looks like all the problems are gone, except that the sheer size of the code in the whole solution looks like massive overkill. Unfortunately, that’s what it takes if you really must do with both mutable/immutable virtual interfaces in a safe and memory efficient manner.

This is not just academic nonsense


You might say the above is not relevant to real life, after all, who cares about circles and ellipses? But you’d be wrong. It is true that this example is very special, in that the notion of circle imposes constraints on the axes of the underlying ellipse by its mere existence, without introducing new data. Usually, when we inherit in code, we introduce new data.

Let’s take a concrete example. Suppose you write a class for representing names. They will have given names and family names. You want to be nice to others and make every accessor in every class virtual. Now, create a class for persons, let it inherit from names and add date of birth. The two sets of attributes in this example are not related at all, mathematically speaking we would use the term ‘cartesian product’. The derived class can support both the mutable and the immutable interfaces of the base with no problem. The base class would also able to support the mutable interface introduced in the derived class, by providing setters and happily not doing anything in them. This is a case when the two oposite directions of generalizations of interfaces take a break and stay level for a while.

Later on, your colleague decides person is a great base class for the class representing residents. A resident’s a person right? Doing that, it will be possible to reuse all the code written for persons using residents instead, right? Well, kind of. A resident in Poland has a given official number, called PESEL, so the class will have to contain that. And the date of birth is encoded in that number. As a result, there appears a constraint on the date-of-birth feature of these objects, as it must be consistent with PESEL. Therefore, the interface of the resident class is only able to consistently support the const interface of person. Any call to the date-of-birth setter will be broken with resident objects, and it is even impossible to write a meaningful override. It seems counterintuitive, at first sight, to say that the base class could support the mutable interface of the derived, that person would be able to support the entire mutable interface of resident, after all there is no PESEL data in person. But it is ok, if you were to write a setter that would just set the date of birth based on a given PESEL number, you would be able to. This case was again special in that new data contained an exact copy of an attribute in the base class.

It won’t be long before someone else decides resident is a great base class for passport holder, and will need to store that id machine readable string that contains the names, but with diacritic letters converted to plain roman, and date-of-birth again, but not the rest of PESEL. Now again we see that parts of mutable interfaces of base classes are not sustainable, while entire immutable interfaces pose no problem. Now it’s even less intuitive to see that base classes could support the entire mutable interface of passport holder, but everything becomes clear when you realize that the setter there has to get all dependent data at once, names with diacritics, PESEL and the machine id, otherwise it would not be able to assert consistency. So in the base classes you would just pick what you needed out of that.

I have abused you patience enough not to provide sample code for the efficient memory usage problem. Let me just say that you might add data to descendent classes, as above, or start on the other end, with the one with richest data set, and proceed by using only parts of it, wasting space, which would be the scenario if you opted for the mutable backbone version, the converse of what happened to the cricles and ellipses. In this section, the scenario from the above paragraphs but without virtual setters, that is immutable backbone, or the symmetric solution would save the day.

Practical suggestions


Remember that const and non-const methods are parts of two fundamentally different interfaces to a class, even if you do not declare them virtual. Do not forget the qualifier where it belongs. Beware of virtual interfaces containing both const and non-const methods that are open to be inherited from. You may live with some of them if you must, provided you know what you’re doing, but if you don’t declare them final, someone will misunderstand you and will break behavioural invariants. It is way easier to reason about interfaces that are of just one type. And likely, most of the time, if you consider what you really need from your objects, you will find out your are going to need just one type anyway.

Advertisements

3 Responses to To const or not to const – the Liskov substitution principle

  1. Sebastian says:

    Very interesting article for someone who merely started to write programs. On the other way i must add that there is a slip in the title. Should be “The Liskov principle”. Best regards.

    • Sebastian says:

      @ up I’m sorry I misunderstood the real meaning of the title.

      • ljwo says:

        Thanks. In fact, it’s an extended version of a lecture that I give in the second semester of a programming course. It’s more or less understood by seasoned programmers, but I think having it written down can help to organize one’s thoughts.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: