OK, OK, so I used to controversial title to lure you in. After all, it's hard to disagree that inheritance in object oriented programming leads to greater code re-use, and it's hard to disagree that code re-use is a good thing.

Before we dig in, let's have a quick recap on how inheritance gives us greater code re-use. You can write a class, then inherit from it to create a more specialized subclass. In that subclass, you may implement some methods that the parent class did not have. You may also specialize the behaviour of some of the parent's methods by overriding them. Any method from the parent class that you did not override, you inherit. You also inherit the state of the parent class (fields, attributes, or whatever you call them in your language of choice). Therefore, the same bit of code can operate on many different data types (since a subclass can be used anywhere that a class is). This is called polymorphism, and it is what enables safe code re-use (safe because you know that subclasses will have at least the state and operations of the parent class).

This is all very familiar to anyone who has worked with an object-oriented language. The trouble is, when something becomes this popular and familiar, you can come to assume that it's the only option out there, or that it's the answer to all problems. We have ended up with some fairly purist OO languages in popular use and quite a few people thinking that single inheritance and object orientation is good, multiple inheritance is evil and procedural programming is an old and outdated approach - but without questioning why they are good or bad, or being unwilling to see the weaknesses in what they consider to be good.

In this article I'm going to talk about code re-use. I'm going to show that inheritance falls short of providing for all of the code re-use that we would like, then discuss a possible answer to this problem known as traits. On the way there, we'll take a peek at mix-ins and look at why they, along with multiple inheritance, are problematic.

The Problem

Suppose that I need to implement the animal kingdom in an object-oriented language. Let's start out with the Dog. We'll write a class for it in a C#-ish, Java-ish pseudocode. I'm too lazy to write all of the accessor methods, so I've used some "with" syntax to indicate that they are to be magically created for us.

class Dog inherits Animal
{
    private string name with get, set;
    private Color color with get;
    private Paw[] paws;
    private Tail tail;
    
    public void Bark()
    {
        print "WOOF!";
    }
    public void PlayInTheGarden()
    {
        color = Color.BLACK;
    }
}

Here I have inherited from some Animal class. If we wanted to implement Puppy, then we could inherit from the Dog class.

class Puppy inherits Dog
{
    public void Bark() // Override
    {
        print "w00f!";
    }
    public void Chew(Damagable item)
    {
        item.IncreaseDamage();
    }
}

So far so good, and inheritance is serving us well. However, now we want to implement the ability for some animals to walk. We can't put that in the Animal class because some animals don't walk (snakes, for example). We don't want to implement the walk method in every class that implements an animal that can walk because we lose out on code re-use.

One possible solution is to write a Walking class with a walk method. Then we can write a walk method in the class of each animal that can walk that simply calls the walk method in the Walking class. This is known as delegation (not to be confused with .Net delegates). The trouble is that you have to write the "forwarder method" in every class, and if you change the interface of the walk method (for example, you add an overloaded version that takes an amount of time to walk for rather than a number of steps), then you have to modify every class again.

Does Multiple Inheritance Help?

Multiple inheritance enables us to inherit from more than one base class. This means that we can get the methods and state of multiple classes, potentially enabling greater re-use. That sounds good, since now we can inherit from both the Animal and the Walking classes. The walk method need only be written once and if we write overloaded versions of it then all of the animals that inherit from the walk class get them automatically.

At this point you may be thinking, "so if multiple inheritance leads to better code re-use, as in this case, why do people dislike it so much?" The problems start to appear when you look start thinking about what happens in various "edge cases". For example, suppose that we wanted to implement remote monitoring of the body parts of all animals. That's essentially like walking a tree, so I create a class named BodyPartsWalker, which also has a "walk" method. Animal then inherits from it.

Now we have something of a problem. Our Dog class inherits from Animal, which has inherited a walk method from BodyPartsWalker. However, it also inherits from Walking, from which it gets a walk method. Which one should it call? Well, that's a language dependent question. If the language is defined as doing a depth-first search of the inheritance tree and we have placed Animal in our list of base classes before Walking, then we'll get the method from BodyPartsWalker. However, the behaviour of our class now changes if we re-order the list of classes that we are inheriting from. This makes for fragile hierarchies, and is one of the key problems with multiple inheritance.

The diamond problem is another commonly cited example of multiple inheritance creating confusion.



Here, classes B and C both inherit class A. Then class D inherits both classes B and C. Think about the issue of inheriting the state from class A. Do we get two copies of class A's fields/state? If they are totally private to A, it's not an issue. If they are public or available to subclasses (spelt protected in C# and Java), then do we get two copies of them or just the one? If we get just the one, and classes B and C rely on being able to do things with the state of A, there is no promise that they will use it in a compatible way. Worse, one of them may change in the future to not use it in a compatible way. If we have two copies, then which should we access if we refer to it inside class D?

Finally, there are implementation difficulties. Laying out objects in memory so they can cheaply be used polymorphically when only single inheritance is available is pretty trivial. For multiple inheritance, it's non-trivial, pushing up the runtime cost of accessing state.

Multiple inheritance clearly has some benefit, but there is a price to pay. Many language designers have decided that the price is too high, which is why you don't see it in Java and C#. I think that is a choice that fits well for these languages. So, what else could they do?

Mix-ins

Classes have been used in most languages to provide two different things. One of them is instance management - describing a set of state that a particular type of object will have and then allowing many objects to be created that have that state. The other thing is code re-use - the current topic at hand. Notice that instance management is mostly about state and code re-use is mostly about methods. What would happen if we tried to separate instance management and code re-use, though?

Clearly, some of our re-use depends on inherited state and polymorphism. Other times, all we really care about is being able to incorporate a certain method or group of methods into the current class. This is the case with our walk method for animals that can walk: we'd like to incorporate the method from Walking into many classes, but we don't care about the class inheriting from Walking.

A mix-in, like a class, can have one or more methods. Unlike a class, it cannot be instantiated. Rather than inheriting from it, you mix it in to a class. This involves "giving" the methods from the mix-in to the class. (Note that a language may provide inheritance as well as mixing in - the two are designed to work together). It is possible to mix in many mix-ins to a class.

The state issues with inheritance are resolved with mix-ins and methods can be re-used by many classes that need that functionality. Are our problems solved? Well, we're closer. Unfortunately, there are some subtle issues with how mix-ins are defined: in terms of inheritance. Consider the following diagram.



Here, class C has the mix-ins M1 and M2 mixed in to it. At compile time the notion of mix-ins disappears, however. You can view the actions of the compiler as roughly corresponding to these steps.

1. An anonymous class (we will refer to it as A1) is created consisting of the methods of M1. This anonymous class inherits from C.
2. Another anonymous class (we will refer to it as A2) is created consisting of the methods of M2. This anonymous class inherits from A1.
3. The name C is then taken and bound to the anonymous class A2 rather than C itself, so when you refer to C in the program you are actually talking about A2.

The good thing about this is that you can trivially compile the code down to run on, say, a .Net VM or the JVM, which support single inheritance. There is no need to extend them to support mix-ins. (Also note that the compiler could get mix-ins to be considered to define types by generating an interface with the name of the mix-in itself.)

The bad thing is that we're back to the fragile hierarchies problem once again, and on this front it's probably worse than multiple inheritance. Since we are defining mixing in using single inheritance, we can only mix in one mix-in at a time (sometimes known as linearization). Imagine that both M1 and M2 implemented a walk method. If you place M1 before M2 in the mix-in list, you would get the walk method from M2. If you change the order of them around, you get the method from M1.

While changing the order of the list is rare, deciding to mix another mix-in into a class later on probably is not. If the new mix-in has a method of the same name as an existing one, we get the method from the new mix-in. We may also run into issues like this if we modify a mix-in.

It gets worse than all of this, though. Because of the way mixing in takes place, the class itself (C) has no way to choose which method should be called. That in turn can lead programmers to start putting such code into mix-ins themselves, which is the road to a great deal of mess.

Inheritance Sucks!

The common theme in our problems is the inheritance mechanism. It does not scale well beyond single inheritance, leaving multiple inheritance with serious issues. Mix-ins try to get around this, but it turns out that the inheritance mechanism is less than ideal for building the mixing in mechanism on top of. The thing that makes inheritance so useful - method overriding in subclasses - doesn't work so well for mix-ins, where you'd actually like a super-class to have the final say (in our example, the class C itself).

It seems that the best way out is to put inheritance aside, leave it doing what it's good at, preferably keep it single and introduce another mechanism for having groups of methods placed into classes. Preferably, we'd like one that we can "compile away" so we can introduce it into languages and run them on, say, the .Net CLR or the JVM.

Traits And Flattening Composition

A fairly recent paper proposed a new mechanism: flattening composition of traits. A trait is just like a mix-in: it contains a group of methods and it cannot be instantiated on its own. As with mix-ins, we can write a Walking trait that contains our walk method.

What makes traits different from mix-ins is flattening composition. Composition, like mixing in, involves "giving" a class the methods from the trait. Flattening means that every trait that is being mixed in to a class is considered equally: the order that they are listed to be mixed in does not matter. There are two key rules for flattening composition.

If the class provides a method with the same name (and perhaps signature) as any of the methods provided by the traits, the class method will always win. That means that the class gets the final say - an improvement over mix-ins. If the first rule does not apply and there are two traits providing a method with the same name (and perhaps signature), it is an error. If trait composition can only happen at compile time (just as inheritance only happens at compile time in, say, C#), that means that these conflicts can all be detected at compile time. The programmer can then resolve them, and thanks to rule 1 can do so in the class itself, without having to change any of the traits. Extending my pseudocode language with traits could look like this:

trait Walking
{
    public void Walk(int Steps)
    {
        /* Walkies... */
    }
}
class Dog inherits Animal does Walking {
    ...
}
class Cat inherits Animal does Walking {
    ...
}

Notice the use of the new "does" keyword, which I have introduced to denote that flattening composition of the trait should take place. Also notice that I'm still inheriting from Animal. Traits comfortably work alongside classes to solve a different type of re-use problem.

Polymorphism And Safety

Traits actually give us parametric polymorphism - the same kind of polymorphism that generics provide. If you consider a method in a trait, what is the type of its invocant (the "this" variable in C# and Java)? It would be type variable, and composing a trait into a class would provide the type parameter: the type of the class itself. That is, the "this" variable inside the walk method in our previous example may be Cat or Dog. That we find polymorphism here is not surprising: it tends to go hand in hand with code re-use.

Finally, we need to consider the case where a method in a trait wants to call a method in the class that it is being composed in to. This is fine, provided that every class that the trait is composed into has that method. In static languages it will be possible to determine all of the methods that a trait tries to call outside of the trait itself. A list of methods that classes the trait is composed into can then be computed and checked at composition time (that is, compile time).

It's good that we can detect cases like this, but it's a little tricky to decide whether the fault is with the class that is using the trait (for not providing the required methods) or with the trait itself (maybe the method name was typo'd). I'd lean towards saying that it is the fault of the class itself, since traits are the things that will be re-used by many classes. Then it becomes similar to presenting a "the class did not provide a method required by an interface" style error.

An alternative that may fit well if traits were provided in C# or Java is to have the trait specify the interfaces that classes it is composed into should implement. That removes the ambiguity over whether the trait is at fault or the class.

What Next?

It would be interesting to prototype traits in C# to see how they feel to work with. In a future article (or series of articles) I hope to take the Mono Project's open source implementation of a C# compiler and set about implementing traits and flattening composition. For the time being, I hope you've found this informative and mind opening.

---

About The Author

Jonathan Worthington works at Programmer's Heaven, cutting code and writing articles. He's interested in programming language design and semantics, type theory and virtual machines. He hacks on the Parrot virtual machine, being developed to run Perl 6. In his free time he enjoys travelling, eating curry and walking amongst nice scenery.

---