An extensive discussion of subtyping, insidious problems with subclassing, and practical rules to avoid them.
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]
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
};
|
// 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;
} |
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;
} |
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]
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)
(send a-Bag 'count x)
(send a-Set 'put x)
(send a-Set 'count x)
(define (fnb bag) (send bag 'put 5) (send bag 'put 5) (send bag 'count 5)) |
(+ 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)) |
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].
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); } |
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); } |
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
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
oleg-at-okmij.org