Friday, April 15, 2011

Overriding and Overloading

Two terms that sound similar and are sometimes confused are overriding and overloading.  The former is an essential part of inheritance, and therefore of object-oriented programming; the latter is a syntactic device that adds no expressive power to the language.

Overriding a method means providing a new implementation for it in an inheriting class.  This may be necessary because the subclass has a different representation, which has more information than the superclass.  For example, suppose you are programming an interactive game, in which characters lose health points as a result of exertion or by attacks by other players.  This is implemented through a method damage(int points), which inflicts the given amount of damage.  Now assume that you create a special kind of character, called Merlin, which can make itself invisible as well as operate a force shield that protects it from certain kinds of enemy actions.  However, it can't perform these new functions when its health is too low.  The class implementing the Merlin character inherits from the general character class.  It needs to override the implementation of the damage method, in order to disable invisibility and the force shield if the health level drops below the relevant thresholds.  When the damage method is called for any character, it decreases its health; for Merlin, it may additionally disable his special abilities.

The choice of which code runs for a particular invocation of the damage method is made at runtime.  If the character happens to be Merlin (that is, its type is the Merlin class), the code executed will come from the Merlin class.  If the character's type is another class, the code will be taken from that class, or from the closest ancestor class that provides an implementation of that method.  This is called dynamic dispatch, and is a cornerstone of object-oriented programming.

Merlin's special abilities can be damaged by special types of attacks, which do not otherwise damage his overall health.  It seems natural to add to Merlin's class a new method, damage(Ability ability), which damages the given ability but does not affect other abilities or the health measure.  This is a case of overloading: using the same name for two different methods.  Many, but not all, object-oriented languages support overloading.  Java, C#, and C++ all do, while Eiffel doesn't.  The choice of which code gets executed in a call to the overloaded damage method is made by the compiler: if the argument is an int, the general damage method will be called; if the argument is an Ability (that is, its type is the Ability class), the second will be called.  These types must be known at compile time; if they aren't, the program won't compile.

Because the decision of which overloaded method to call is static, it is known to the programmer writing the call.  Therefore, overloading can always be replaced by renaming methods.  In our example, the new method that damages Merlin's special abilities can be called damageAbility to remove the overloading.  In fact, overloaded methods are implemented using this technique; languages such as C++, Java, and C# have a special notion of method name, which attaches encoded information about argument types to the method name as defined by the programmer.

When used properly, overloading can make programs more understandable.  For example, the + operator is overloaded in Java to represent addition of integers as well as floating-point numbers.  That's perfectly understandable, since the mathematical addition operator applies to all these types and has the same properties for them (associativity, commutativity, etc.).  It would be perfectly fine to use + for adding complex numbers if Java allowed this (and is common in C++, which does).  However, Java overloads + to denote concatenation of strings as well.  This is confusing, and is a design error of the language.  This error is compouned by the fact that + coerces its arguments to more general types, so that x + y will denote floating-point addition if x is an int and y is a float, but string concatenation if x as an int and y is a string.  Worse yet, mathematical properties of addition don't hold for string concatenation, and as a result ("a" + 1) + 2 is "a12" while "a" + (1 + 2) is "a3".

Because overloading doesn't add to the expressive power of the language, and is a trap for the unwary, it should be removed from object-oriented languages.  Unfortunately, the C++/Java/C# family of languages encourage overloading, and even require it in the case of constructors, whose names must be the name of the class.  Suppose you want to create a complex-number class called Complex, and give it two constructors, one receiving the rectangular representation of the number (x and y for x+iy) while the other receives the polar representation (rho and theta for rho*e^(i*theta)).  You want to call these two constructors by descriptive names, such as complexFromRectangular and complexFromPolar.  But in C++/Java/C#, both must be called Complex!  Not only are the names non-descriptive, they also coincide, because both constructors take two arguments of the same types.  I won't describe the contortions that programmers of these languages have to go through to solve this problem.

My recommendation: avoid overloading altogether.  If you really feel it's essential in some case, at least make sure that the overloaded methods have the same semantics (as in the case of mathematical addition).  If you use overloading in other cases (such as addition and concatenation), you will have only yourself to blame when you get confused; and your users will be perfectly justified in blaming you when they, in turn, get confused.

Friday, April 8, 2011

Writing Contracts

In the best thriller tradition, we left our hero, the Set type, in an awkward position at the end of the last episode.  Because Set has a subtype, HashSet, that doesn't allow nulls as values, the method Set.add(Object x) needed to have a precondition x != null.  But Set has another subtype, ArraySet, which does allow null values.  Therefore, we couldn't put a postcondition on Set.get() that guarantees that the returned value won't be null.  The Set type now precludes null inputs, but may return null values; this seems inconsistent.  Yet both contract decisions seem to be forced by Liskov's Behavioral Subtyping Principle!

In such cases, it is often helpful to look for missing abstractions.  Here, there is an obvious correlation between null inputs and outputs: some sets support null values in both cases, and the others don't in either.  The Set type should clearly distinguish between the two types of sets, by means of a query such as supportsNullValues().  The precondition of Set.add(Object x) will now be:

!supportsNullValues() ==> x != null

where "==>" denotes logical implication.  The postcondition of Set.get() will be:

!supportsNullValues() ==> $ret != null

where "$ret" denotes the returned value.  The contract for Set is now consistent in both cases.  If supportsNullValues() is true, the precondition on add and postcondition on get are inactive; if it's false, both are active.

Furthermore, we can now add a postcondition to HashSet.supportsNullValues(): $ret == false (or, equivalently, !$ret).  As a result, developers using HashSet know, by examining the contract, that add must not be given null values and get will never return null.  Similarly, ArraySet.supportsNullValues() will have a postcondition $ret == true (or simply $ret).  Developers using ArraySet will now know that they can provide add with null inputs, and may receive nulls from get.  Developers who use the Set type without knowing the particular implementation can act in one of two ways.  First, they can be cautious and not insert any null values into the set.  Because Set.get will only return elements previously inserted into the set, it won't return null in this case.  (Note that this is part of the contract that is difficult to specify formally, since it involves conditions on the behavior of the set over time.  However, it is an important part of the contract, and should be documented as such, using natural language.)  The second option is to call supportsNullValues() and act according to the value returned.

In the example, Set.add had another precondition that stated that the client is not allowed to add to the set an element that is already in it.  This is legal but not recommended.  In general, preconditions should contain any conditions under which the action of the method is not well defined.  For example, it makes no sense to ask for an element of an empty set, which is why Set.get has a precondition that the set isn't empty.  But adding to the set an element that is already there is perfectly well defined; the set simply doesn't change.  Instead of requiring clients to check this condition before calling add, the implementation of the add method should simply do the right thing and not add the element if it already exists in the set.  A little effort on the part of the implementer can save much effort for clients.

Friday, April 1, 2011

The Correct Use of Inheritance

Perhaps the most subtle relationship in object-oriented programming is that of inheritance.  Many object-oriented languages, including Java, distinguish between classes and interfaces, as a reaction to the problems languages such as C++ faced with multiple inheritance.  This is a complex issue I will address in a later post.  Now I want to focus on the logical relationships involved in inheritance.  In order to avoid the class/interface dichotomy, I will use the notion of a subtype.  A type A is a subtype of B if it inherits from it, whether both A and B are classes, both are interfaces, or A is a class and B is an interface.  (Java uses the verb "extends" for the first two cases and "implements" for the third.)

An element of a subtype A may be used whenever an element of the supertype B is indicated.  For example, suppose we have a type called Set that represents mathematical sets.  It has a number of implementations inheriting from it, including ArraySet, which holds the elements of the set in an array, and HashSet, which holds the elements in a hash table.  The Set type has various methods, including add(Object x), which adds an element to the set; get(), which returns an arbitrary element of the set; and has(Object x), which returns true if and only if x is in the set.  Since a set can't contain the same object multiple times, we put a precondition on add(Object x) requiring that x is not already in the set: !has(x).

Unfortunately, our HashSet implementation doesn't support null as an element in the hash table, so we add another precondition to add(Object x), stating that x can't be null: x != null.  Now, suppose we have a client C that uses our code, and receives a parameter s of type Set.  When the programmer of the client code reads the contract for Set, he sees only one precondition: !has(x).  He will certainly be careful not to insert the same element twice, for example by using the following code:

if (!s.has(element)) s.add(element);

But he has perfect confidence in the following piece of code:

if (!s.has(null)) s.add(null);

He will be rudely surprised, therefore, when this actually bombs on him somewhere inside the call to add in our HashSet implementation.  He may not even have known about the existence of HashSet, since he received the object s, which happened to have this type, as a parameter.  He is the proverbial innocent bystander, and should be protected from this kind of problem.  After all, he kept his side of the contract, and has every right to expect us to keep our side!

This demonstrates a general problem, which will manifest itself whenever the precondition of a method in a subtype is stronger (that is, requires more) than that of the supertype.  The rule must therefore be that subtypes are not allowed to strengthen method preconditions.  We will have to add a precondition to Set.add, to warn potential users that some subtypes may not accept null as a parameter.  Our ArraySet implementation can now weaken the precondition by removing this requirement.  This is perfectly legal; clients that use ArraySet objects through the Set supertype will not be allowed to call add(null), but clients that use ArraySet directly will be able to enjoy the extended functionality.

Since we restrict Set.add not to accept null parameters, it looks like we can now put a postcondition on Set.get, stating that it will never return null.  This will work well for HashSet, but will fail for ArraySet, which does accept null elements.  By adding this postcondition to Set.get, we have again harmed innocent bystanders; in this case, a client of Set who happens to receive a HashSet object as its own parameter.  Such a client feels perfectly justified in writing the following code:

if (!s.isEmpty()) System.out.println(s.get().toString());

He is careful to check the precondition of get, which states that it can't be called when the set is empty, and he is therefore entitled to rely on get's postcondition and to expect that no NullPointerException will be raised on the call to toString.  He may not even be aware of the existence of ArraySet, and of the fact that it doesn't have this postcondition.  The rule for postconditions therefore must be that postconditions must not be weakened by subtypes, although they can be strengthened; this enables clients of the subtype to benefit from extra features it supports.

These rules are consequences of Liskov's Behavioral Substitution Principle, which states that properties of the supertype must still be true of subtypes.  This principle is true of all inheritance hierarchies which allow subtypes to be used as elements of their supertypes.  After all, this is what a subtype means: if A is a subtype of B then every instance of A is, by definition, also an instance of B.  (This does not apply to private inheritance in C++, which doesn't imply a subtype relationship, but it does apply to public inheritance in C++, as well as to all inheritance relationships in Java, C#, and similar languages.)  The principle is true whether or not the developer uses design by contract, and writes contracts explicilty; a violation of the principle is still a bug, and a nasty one at that.  Using design by contract makes it easier to prevent such violations in the first place.

Any developer who is ignorant of Liskov's Behavioral Substitution Principle can't claim to understand object-oriented programming, and should be prevented from writing any kind of inheritance relationship!