Subtyping, Subclassing, and Trouble with OOP

An extensive discussion of subtyping, insidious problems with subclassing, and practical rules to avoid them.

Does OOP really separate interface from implementation?
The manifestation of a problem: an example of how an implementation inheritance prevents separation of interface and implementation
Subtyping vs. Subclassing
Explanation why the problem above happened
Subclassing errors, OOP style and practically checkable to prevent them
Demonstration how statically checkable rules can prevent the problem from occurring [a separate document]

A more formal and general presentation of this topic is given in a paper and a talk at a Monterey 2001 workshop (June 19-21, 2001, Monterey, CA):  Subtyping-OOP.ps.gz [35K]   and    MTR2001-Subtyping-talk.ps.gz [67K]
   

Does OOP really separate interface from implementation?

Decoupling of abstraction from implementation is one of the holy grails of good design. Object-oriented programming in general and encapsulation in particular are claimed to be conducive to such separation, and therefore to more reliable code. In the end, productivity and quality are the only true merits a programming methodology is to be judged upon. This article is to show a very simple example that questions if OOP indeed helps separate interface from implementation. The example is a very familiar one, illustrating the difference between subclassing and subtyping. The article carries this example of Bags and Sets one step further, to a rather unsettling result. The article set out to follow good software engineering; this makes the resulting failure even more ominous.

The article aims to give a more-or-less "real" example, which one can run and see the result for himself. By necessity the example had to be implemented in some language. The present article uses C++. It appears however that similar code (with similar conclusions) can be carried on in many other OO languages (e.g., Java, Python, etc).

Suppose I was given a task to implement a Bag -- an unordered collection of possibly duplicate items (integers in this example). I chose the following interface:

typedef int const * CollIterator;	// Primitive but will do
class CBag {
 public:
  int size(void) const;			// The number of elements in the bag
  virtual void put(const int elem);	// Put an element into the bag
  int count(const int elem) const;	// Count the number of occurrences
				        // of a particular element in the bag
  virtual bool del(const int elem);     // Remove an element from the bag
					// Return false if the element
					// didn't exist
  CollIterator begin(void) const;	// Standard enumerator interface
  CollIterator end(void) const;

  CBag(void);
  virtual CBag * clone(void) const;	// Make a copy of the bag
 private:
			// implementation details elided
};

Other useful operations of the CBag package are implemented without the knowledge of CBag's internals. The functions below use only the public interface of the CBag class:

// Standard "print-on" operator
ostream& operator << (ostream& os, const CBag& bag);

// Union (merge) of the two bags
// The return type is void to avoid complications with subclassing
// (which incidental to the current example)
void operator += (CBag& to, const CBag& from);

// Determine if CBag a is subbag of CBag b
bool operator <= (const CBag& a, const CBag& b);

inline bool operator >= (const CBag& a, const CBag& b)
{ return b <= a; }

// Structural equivalence of the bags
// Two bags are equal if they contain the same number of the same elements
inline bool operator == (const CBag& a, const CBag& b)
{ return a <= b && a >= b; }

 

It has to be stressed that the package was designed to minimize the number of functions that need to know details of CBag's implementation. Following good practice, I wrote validation code (file vCBag.cc [Code]) that tests all the functions and methods of the CBag package and verifies common invariants.

Suppose you are tasked with implementing a Set package. Your boss defined a set as an unordered collection where each element has a single occurrence. In fact, your boss even said that a set is a bag with no duplicates. You have found my CBag package and realized that it can be used with few additional changes. The definition of a Set as a Bag, with some constraints, made the decision to reuse the CBag code even easier.

class CSet : public CBag {
 public:
  bool memberof(const int elem) const { return count(elem) > 0; }

  // Overriding of CBag::put
  void put(const int elem)
  { if(!memberof(elem)) CBag::put(elem); }

  CSet * clone(void) const
  { CSet * new_set = new CSet(); *new_set += *this; return new_set; }
  CSet(void) {}
};

The definition of a CSet makes it possible to mix CSets and CBags, as in set += bag; or bag += set; These operations are well-defined, keeping in mind that a set is a bag that happens to have the count of all members exactly one. For example, set += bag; adds all elements from a bag to a set, unless they are already present. bag += set; is no different than merging a bag with any other bag.

You too wrote a validation suite to test all CSet methods (newly defined and inherited from a bag) and to verify common expected properties, e.g., a+=a is a.

In my package, I have defined and implemented a function:
// A sample function. Given three bags a, b, and c, it decides
// if a+b is a subbag of c
bool foo(const CBag& a, const CBag& b, const CBag& c)
{
  CBag & ab = *(a.clone());	// Clone a to avoid clobbering it
  ab += b;			// ab is now the union of a and b
  bool result = ab <= c;
  delete &ab;
  return result;
}

It was verified in the regression test suite. You have tried this function on sets, and found it satisfactory.

Later on, I revisited my code and found my implementation of foo() inefficient. Memory for the ab object is unnecessarily allocated on heap. I rewrote the function as
bool foo(const CBag& a, const CBag& b, const CBag& c)
{
  CBag ab;
  ab += a;			// Clone a to avoid clobbering it
  ab += b;			// ab is now the union of a and b
  bool result = ab <= c;
  return result;
}

It has exactly the same interface as the original foo(). The code hardly changed. The behavior of the new implementation is also the same -- as far as I and the package CBag are concerned. Remember, I have no idea that you're re-using my package. I re-ran the regression test suite with the new foo(): everything tested fine.

However, when you run your code with the new implementation of foo(), you notice that something has changed! You can see this for yourself: download the complete code from [Code]. make vCBag1 and make vCBag2 run validation tests with the first and the second implementations of foo(). Both tests complete successfully, with the identical results. make vCSet1 and make vCSet2 test the CSet package. The tests -- other than those of foo() -- all succeed. Function foo() however yields markedly different results. It is debatable which implementation of foo() gives truer results for CSets. In any case, changing internal algorithms of a pure function foo() while keeping the same interfaces is not supposed to break your code. What happened?

What makes this problem more unsettling is that both you and I tried to do everything by the book. We wrote a safe, typechecked code. We eschewed casts. g++ (2.95.2) compiler with flags -W and -Wall issued not a single warning. Normally these flags cause g++ to become very annoying. You didn't try to override methods of CBag to deliberately break the CBag package. You attempted to preserve CBag's invariants (weakening a few as needed). Real-life classes usually have far more obscure algebraic properties. We both wrote regression tests for our implementations of a CBag and a CSet, and they passed. And yet, despite all my efforts to separate interface and implementation, I failed. Should a programming language or the methodology take at least a part of the blame? [OOP-problems]

 
 

Subtyping vs. Subclassing

The problem with CSet is caused by CSet design's breaking of the Liskov Substitution Principle (LSP) [LSP]. CSet has been declared as a subclass of CBag. Therefore, C++ compiler's typechecker permits passing a CSet object or a CSet reference to a function that expects a CBag object or reference. However, it is well known [Subtyping-Subclassing] that a CSet is not a subtype of a CBag. The next few paragraphs give a simple proof of this fact, for the sake of reference.

One approach is to consider Bags and Sets as pure values, without any state or intrinsic behavior -- just like integers are. This approach is taken in the next article, Preventing-Trouble.html. The other point of view -- the one used in this article -- is Object-Oriented Programming, of objects that encapsulate state and behavior. Behavior means an object can accept a message, send a reply and possibly change its state. Let us consider a Bag and a Set separately, without regard to their possible relationship. Throughout this section we use a different, concise notation to emphasize the general nature of the argument.

We will define a Bag as an object that accepts two messages:

(send a-Bag 'put x)
puts an element x into the Bag, and
(send a-Bag 'count x)
gives the count of occurrences of x in the Bag (without changing a-Bag's state).
Likewise, a Set is defined as an object that accepts two messages:
(send a-Set 'put x)
puts an element x into a-Set unless it was already there,
(send a-Set 'count x)
gives the count of occurrences of x in a-Set (which is always either 0 or 1).
Let's consider a function
(define (fnb bag)
   (send bag 'put 5)
   (send bag 'put 5)
   (send bag 'count 5))

The behavior of this function can be summed as follows: given a Bag, the function adds two elements into it and returns
    (+ 2 (send orig-bag 'count 5))

Technically you can pass to fnb a Set object as well. Just as a Bag, a Set object accepts messages put and count. However applying fnb to a Set object will break the function's post-condition, which stated above. Therefore, passing a set object where a bag was expected changes behavior of some program. According to the Liskov Substitution Principle (LSP), a Set is not substitutable for a Bag -- a Set cannot be a subtype of a Bag.

Let's consider a function
(define (fns set)
   (send set 'put 5)
   (send set 'count 5))

The behavior of this function is: given a Set, the function adds an element into it and returns 1. If you pass to this function a bag (which -- just as a set -- replies to messages put and count), the function fns may return a number greater than 1. This will break fns's contract, which promised always to return 1.

Therefore, from the OO point of view, neither a Bag nor a Set are a subtype of the other. This is the crux of the problem. Bag and Set only appear similar. The interface or an implementation of a Bag and a Set appear to invite subclassingof a Set from a Bag (or vice versa). Doing so however will violate the LSP -- and you have to brace for very subtle errors. The previous section intentionally broke the LSP to demonstrate how insidious the errors are and how difficult it may be to find them. Sets and Bags are very simple types, far simpler than the ones you deal with in a production code. Alas, LSP when considered from an OOP point of view is undecidable. You cannot count on a compiler for help in pointing out an error. You cannot rely on regression tests either. It's manual work -- you have to see the problem [OOP-problems].

 

Subtyping and Immutability

One may claim that "A Set *is not a* Bag, but an ImmutableSet *is an* ImmutableBag." That is not correct. An immutability per se does not confer subtyping to "derived" classes of data. As an example, consider a variation of the previous argument. We will use a C++ syntax for a change. The examples will hold if re-written in Java, Haskell, Self or any other language with a native or emulated OO system.

class BagV {
  virtual BagV put(const int) const;
  int count(const int) const;
  ... // other similar const members
};
 
class SetV {
  virtual SetV put(const int) const;
  int count(const int) const;
  ... // other similar const members
};

 

Instances of BagV and SetV classes are immutable, yet the classes are not subtypes of each other. To see that, let us consider a polymorphic function
template <typename T> int f(const T& t)
{ return t.put(1).count(1); }

Over a set of BagV instances, the behavior of this function can be represented by an invariant
    f(bag) == 1 + bag.count(1)

If we take an object asetv = SetV().put(1) and pass it to f(), the invariant above will be broken. Therefore, by LSP, a SetV is not substitutable for BagV: a SetV is not a BagV.

In other words, if one defines
int fb(const BagV& bag) { return bag.put(1).count(1); }

he can potentially pass a SetV instance to it: e.g., either by making SetV a subclass of BagV, or by reinterpret_cast<const BagV&>(aSetV). Doing so will generate no overt error; yet this will break fb()'s invariant and alter program's behavior in unpredictable ways. A similar argument will show that BagV is not a subtype of SetV.

C++ objects are record-based. Subclassing is a way of extending records, with possibly altering some slots in the parent record. Those slots must be designated as modifiable by a keyword virtual. In this context, prohibiting mutation and overriding makes subclassing imply subtyping. This was the reasoning behind BRules [Preventing-Trouble.html].

However merely declaring the state of an object immutable is not enough to guarantee that derivation leads to subtyping: An object can override parent's behavior without altering the parent. This is easy to do when an object is implemented as a functional closure, when a handler for an incoming message is located with the help of some kind of reflexive facilities, or in prototype-based OO systems. Incidently, if we do permit a derived object to alter its base object, we implicitly allow behavior overriding. For example, an object A can react to a message M by forwarding the message to an object B stored in A's slot. If an object C derived from A alters that slot it hence overrides A's behavior with respect to M.

For example, http://okmij.org/ftp/Scheme/index.html#pure-oo implements a purely functional OO system. It supports objects with an identity, state and behavior, inheritance and polymorphism. Everything in that system is immutable. And yet it is possible to define something like a BagV, and derive SetV from it by overriding a put message handler. Acting this way is bad and invites trouble as this breaks the LSP as shown earlier. Yet it is possible. This example shows that immutability per se does not turn object derivation into subtyping.

 

The present page is a compilation and extension of two articles posted on comp.object, comp.lang.functional, comp.lang.c++.moderated newsgroups on Jun 18 and Jul 14, 2000.
Discussion thread: http://www.deja.com/viewthread.xp?AN=644379349.1&search=thread&recnum=%3c8katsh$fmf$1@nnrp1.deja.com%3e%231/5&group=comp.object&frpage=viewthread.xp  
 

Acknowledgment

Andy Gaynor has asked the right questions. This article is merely an answer.
 
 

Articles' Posting Headers

From: oleg
Message-ID: <8ijfn7$f6q$1@nnrp1.deja.com>
Subject: Does OOP really separate interface from implementation?
Date: Sun, 18 Jun 2000 21:42:00 GMT
Newsgroups: comp.object, comp.lang.c++.moderated
X-Article-Creation-Date: Sun Jun 18 21:42:00 2000 GMT

From: oleg
Subject: Re: Subclassing errors, OOP style and mechanical rules to prevent them
Date: 14 Jul 2000 00:00:00 GMT
Message-ID: <8ko1a8$1u0$1@nnrp1.deja.com>
References: <8katsh$fmf$1@nnrp1.deja.com> <8keh1t$1hs$1@nnrp1.deja.com>
X-Article-Creation-Date: Fri Jul 14 21:39:23 2000 GMT
Newsgroups: comp.object,comp.lang.functional


Last updated July 4, 2001

This site's top page is http://okmij.org/ftp/

oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!