Multiple Inheritance, the Diamond Problem, and Why Java has Interfaces

You usually learn pretty early on in your time with Java that multiple inheritance is EVIL, and that it’s a good thing Java doesn’t have it, and that Java instead has interfaces, which are not evil, or maybe they’re evil like the villains on Space Ghost. The villains on Space Ghost always had some diabolical plan to destroy the universe, but they never got anywhere with it because they were totally ineffectual. That’s interfaces. They’re the Brak, the Moltar, the Lokar, of evil, while multiple inheritance is a powerful and convincing Emperor Palapatine sort of evil.

I attended a fourth-year university course with a student who had absolutely no idea why Java has interfaces or what they’re good for. At first I thought “Geez, how could he not know this?” Then I realized that it’s actually not that surprising that he didn’t know this, because interfaces are totally stupid and don’t make any sense at all, unless you understand why Java doesn’t have multiple inheritance, and no one ever really talks about this. (Actually, my programming languages professor did talk about this, but his course was at eight in the morning, so most of us were barely awake when he talked about it.)

Java doesn’t have multiple inheritance because of things like the diamond problem. There are other problems created by multiple inheritance, but the diamond problem is a big one, it’s easy to explain, and there are lots of nice intuitive examples of where it comes up.

Imagine you’re making a game in a language which supports multiple inheritance. You have a Lion class, and you have an Eagle class, and you want to make a Griffin class which inherits from both of them, since a Griffin is half lion and half eagle. The Lion and Eagle both inherit from Creature, which has an abstract cry() method that each of its subclasses overrides. The Lion’s cry() method roars, while the Eagle’s emits a piercing shriek.

The question is, if you don’t override the cry() method in the Griffin class, which version should the Griffin inherit? Should it inherit the Lion’s? The Eagle’s? Both? Neither? This is the diamond problem: how do you handle this situation? It’s called the diamond problem because you can draw a diagram of it, and the lines of inheritance between the classes make a diamond shape. The diamond problem is not the sort of problem that prevents you from designing a perfectly respectable object system that uses multiple inheritance. Rather, it’s a problem because any solution to it is likely to be confusing, weird, and full of leaky abstractions. This leads many otherwise competent programmers to mess up the design of their systems using multiple inheritance, because they overlooked some dimension of how the language handles the diamond problem.

C++ and Python both support multiple inheritance, but they address the diamond problem in different ways. Take the following Python code:

class Creature:
    def cry(self):
        pass

class Lion(Creature):
    def cry(self):
        print("Roar!")

class Eagle(Creature):
    def cry(self):
        print("Emit a piercing shriek!")

class Griffin(Lion, Eagle):
    pass

g = Griffin()
g.cry()   # What gets printed?

In Python, “Roar!” gets printed. However, if we had reversed the order of the classes in the inheritance list (if we’d written class Griffin(Eagle, Lion)), then “Emit a piercing shriek!” would be printed. This is because Python uses a convention called the method resolution order to figure out what method to call in situations like this. It basically does a breadth-first search of the inheritance graph, starting from the current class, then going through all the parent classes in the inheritance list (in the order they appear), then all of the parents’ parents, and so on, until it finds the method it’s looking for. In the case of the Griffin class, Python searches for an implementation of cry() in the Griffin; not finding one, it searches the first parent, Lion, finds the version of cry() that prints “Roar!”, and calls it. Guido van Rossum wrote a blog about this on his History of Python page.

I find it interesting that Python solves the diamond problem with implicit behavior, in sharp contrast to our next example. Even though Python is the language of “Explicit is better than implicit”, GVR evidently didn’t think this was worth making explicit. Bjarne Stroustrup had a different opinion. Check out the following C++ code.

#include <iostream>
using std::cout;
using std::endl;

class Creature {
  public:
    virtual void cry() = 0;
};

class Lion : Creature {
  public:
    virtual void cry() {
        cout << "Roar!" << endl;
    }
};

class Eagle : Creature {
  public:
    virtual void cry() {
        cout << "Emit a piercing shriek!" << endl;
    }
};

class Griffin : public Lion, public Eagle { };

int main(void) {
    Griffin g;
    g.cry();   // What gets printed?

    return 0;
}  

In C++, this code does not compile. GCC flags an error and notes that “request for member ‘cry’ is ambiguous”. If you want to call the cry() method on a Griffin instance, you have to specify which superclass has the version you want, like this:

Griffin g;
g.Lion::cry();    // Prints "Roar!"
g.Eagle::cry();   // Prints "Emit a piercing shriek!"

You can do this in Python, using its various powers of reflection, but Python also gives you the option of letting the method resolution order algorithm sort it out. In C++, as far as I can tell (this is C++, after all), you must specify which base class’s version of the method to call.

Since the Griffin has an eagle’s head, you probably want it to emit a piercing shriek. You can either constantly write Eagle::cry() instead of just cry(), or you can have the Griffin override cry() and delegate to the Eagle’s method.

Java’s way of solving the diamond problem was to ban all diamonds by disallowing multiple inheritance. In Java, you’d have to write code something like this:

// In Lion.java.
class Lion extends Creature implements Crier {
    @Override
    public void cry() {
        System.out.println("Roar!");
    }
}

// In Eagle.java
class Eagle extends Creature implements Crier {
    @Override
    public void cry() {
        System.out.println("Emit a piercing shriek!");
    }
}

// In Crier.java
interface Crier {
    public void cry();
}

Java then has all sorts of conventions for how you would create the Griffin class to be a blend of an Eagle and a Lion. Suppose we also had a Clawer interface with a claw() method that specified how various creatures tear things open. We could use delegation to create the Griffin, like this:

class Griffin implements Crier, Clawer {
    private Lion innerLion = new Lion();
    private Eagle innerEagle = new Eagle();

    @Override
    public void cry() {
        // Griffin has an eagle's head, so it should emit a piercing shriek.
        innerEagle.cry();
    }

    @Override
    public void claw(Creature target) {
        // Griffin has lion's paws.
        innerLion.claw(target);
    }
}       

We have private instances of Lion and Eagle inside the Griffin class; we override the interface methods in Griffin to call the method on either the Lion or the Eagle, as appropriate. There are other ways you could do this too. Design patterns often come in handy at times like this.

What good are interfaces?

You might have noticed that in the Java version of the Griffin class with delegation, implementing the Crier and Clawer interfaces doesn’t seem to be doing much for us. In the C++ and Python versions with multiple inheritance, we got the code for our cry() method for free just by inheriting from Eagle and Lion. And we could have added a claw() method to Creature and also gotten that for free. But in the Java version, having the methods in interfaces seems pretty pointless.

Inheritance of classes serves two separate, unrelated purposes in Java (and similar languages like C++ and C#): it allows you to reuse code from a base class by inheriting methods, but it also allows you to have a static type system which is simultaneously more flexible and able to verify more of your program at compile time. Interfaces don’t help you reuse code at all, but they are an important part of the type system.

Python and Ruby use a concept called duck typing. The saying goes “If it looks like a duck and quacks like a duck, it’s a duck”. A more accurate version is “If we’ll accept a duck because it has a bill and webbed feet, we should accept anything that has a bill and webbed feet, even if it’s actually a goose, or a platypus.”

Say we wrote this function in Python:

def claw_open_drunk_guy(clawer, drunk_guy):
    clawer.claw(drunk_guy)

Because Python uses duck typing, it doesn’t care what the actual type of the clawer argument is. It can be a Lion, an Eagle, a Griffin, or Freddy Kruger. As long as it has a claw() method, Python is happy.

Java, on the other hand, is not happy. Java isn’t willing to take your word for it that, hey, this guy has a claw() method; it needs to double check. Say we have this Java code:

void clawOpenDrunkGuy(Creature clawer, Human drunkGuy) {
    clawer.claw(drunkGuy);
}

Now along comes the Nightmare on Elm Street expansion pack. We want to pass Freddy Kruger as the first argument, but there’s a problem: Freddy Kruger doesn’t extend Creature, he extends Slasher. If we change the code so Freddy extends Creature, we have to reimplement all the methods that Freddy used to get for free from Slasher, and a bunch of other code which is expecting Freddy to be a Slasher now breaks.

This is where interfaces come in. If Clawer is an interface containing the method claw(), we can have both the Creature class and Freddy Kruger implement that interface and get a claw() method. Then we can write the method like this:

void clawOpenDrunkGuy(Clawer clawer, Human drunkGuy) {
    clawer.claw(drunkGuy);
}

Everything that implements the Clawer interface has a claw() method; the compiler guarantees it. So now Java is happy, knowing the compiler will reject any code that tries to pass in something without a claw() method.

Note that C++ also uses static typing and would have the same problem with this method as Java. However, in C++, you can solve it using multiple inheritance. Just make a Clawer class with a pure virtual function claw(), and make the method take a Clawer as an argument. Then, just make Freddy inherit from both Slasher and Clawer, and the compiler is happy.

When the designers of Java decided not to have multiple inheritance, they made it impossible to solve this problem as in C++. Being very smart guys, they realized they needed to make this solvable in some way, so they came up with interfaces: an imperfect solution, but better than nothing.

Isn’t there some sort of middle ground?

C++ and Python’s multiple inheritance can get very hard to understand. But Java’s interfaces are arguably too restrictive; they usually force you to write more code, just so you can achieve the effect of multiple inheritance with regard to the type system. And they’re pretty useless when it comes to code reuse. To get a Griffin that had the behavior of both a Lion and an Eagle, we had to resort to delegation, which is a lot of code. Interfaces were no help at all for that; they just let us make sure that we could use a Griffin anywhere the compiler expects a Crier or Clawer.

Ruby has something called modules, which are sort of like interfaces, but you can actually give the methods implementations, so they can facilitate code reuse. Modules have several uses in Ruby, but when they’re used like interfaces, they’re often called mixins. Since Ruby has duck typing like Python, it doesn’t need modules to satisfy the type system; they’re purely for semantic value and code reuse.

Scala has something called traits, which are similar to Ruby’s modules. But Scala is statically typed, so traits do interact with the type system. One interesting feature of traits and modules is that a single object can decide at the point of its creation to mix in the trait or module. It’s as if you could do this in Java:

Griffin g = new Griffin() implements Flier {
        @Override
        public void fly(int toXCoord, int toYCoord) {
            System.out.printf("Fly, on the wings of an eagle, to (%d, %d!)!\n",
                              toXCoord, toYCoord);
        }
    }

and get a single Griffin instance which implements Flier, without committing the entire class to implement Flier.

Java 8 now also allows you to give default implementations for the methods in an interface, so all the classes that implement an interface can share a generic version of the method. It doesn’t seem to be as extensive as what traits and modules offer, but it is a step towards making interfaces useful for code reuse.

I haven’t used either Ruby or Scala extensively, so I don’t know a lot about modules or traits. They seem like a good middle ground between multiple inheritance and interfaces. But, like multiple inheritance, they seem to also have lots of obscure corner cases and confusing rules.

Multiple inheritance has a nice intuitive appeal to it; it’s completely obvious that a Griffin is an Eagle plus a Lion, while it’s a little bit weird to think of a Griffin as a Crier, Clawer, and Flier with an inner lion and an inner eagle. On the other hand, traits and modules seem to do a better job leading you in the right direction for real life code. There are often times where you want a class to reuse a particular set of functionality, without wanting to add that class into a new branch of the type hierarchy. Nobody wants to rewrite those JSON serializer methods for every new class that needs to serialize to JSON. But there’s nothing inherent to a CustomerOrder saying that it “is a” JsonSerializable, which is the semantic reading of having the CustomerOrder class inherit from JsonSerializable. It is semantically sensible to say that a CustomerOrder has the trait of being JsonSerializable, though, or that we’ve mixed the JsonSerializable module into the CustomerOrder.

Advertisements