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

The Beauty of C++

It’s pretty widely acknowledged that C++ is not a very nice language.

Some people hate that it still has pointers. Some people hate that it now has references. Some people hate that it now has pointers and references. It has just enough library support that some of the utilities are useful, yet professors can keep track of them all and specifically forbid you from using all the useful ones on programming assignments. It has nice features like templates and operator overloading, but makes them so painful to use that you almost wish it didn’t. (Did you know that the stream operators must be overloaded as stand-alone functions, not as member functions of the class? Otherwise you get bizarre, nonsensical compiler errors that can’t be fixed until you vaguely remember reading in your C++ textbook two years ago that the stream operators must be overloaded as stand-alone functions, and then dig out said book and look it up to confirm.)

In fact, it seems that there’s only one person in the world who didn’t get the memo about the uncool nature of C++, and that person happened to be sitting in front of me on the first day of my undergrad discrete math class.

At UC Davis, the first programming course for majors focuses on C, without worrying about object oriented anything. The second programming course for majors covers C++ and object oriented everything. I was also enrolled in the C++ class that term, and during the first session earlier that morning, the instructor (a hardassed security research guy) had finished his introduction to C++ by telling us that it was a horrible language.

See, he knows that C++ is uncool.

But the guy sitting in front of me in discrete math had a different opinion: he insisted to his friend in a loud voice that C++ was—well, if someone had a gun to your head and would shoot you unless you could say something positive about C++, what would you say?

Stroustrup tried his best. He came so close to incorporating object orientation into C.

He gave it the old college try.

It makes some things easier than C.

It’s better than Cobol.

It’s fast.

It’s fast.

It’s fast.

He didn’t say any of these things.

He said it was beautiful.

He said “Yeah, I’ve looked at some C++ code, and man, it’s beautiful.”

He didn’t say it sarcastically, like “It’s beautiful. Yeah, man. Just beautiful.

He said it passionately, like a hot-blooded young man swept off his feet by a beautiful and mysterious woman.

He said it as if he’d seen C++ at the masquerade, shared a flirtation, danced with C++, tangoed with C++, spun C++ around with a rose clenched in his teeth, and then when he was done he’d said “So, C++. Shall we meet again?” And C++ replied “At the next masquerade. Look for me at the rise of the full moon.”

Of course, some of us had a similar flirtation with C++ when we were young, hot-blooded, bucks who had just recently chosen the manliest major around and were feeling invincible. But a year or so of its prima donna antics convinced us to leave it. The drama C++ brings to a simple act like making sure the correct override of a derived class method gets called through a base class pointer, the hysterics around templates, the fights over accepting instances of the string class instead of pointers to char; sure, it adds spice at first, but eventually it just gets to be too much. Maybe you feel manly at first, like you’ve conquered the most desirable woman in the world, but eventually you just get tired of fighting with C++ over even the smallest things. Eventually you just want a safe, plodding, homely sort of language, like Java. Sure, it’s not too bright. You have to explain everything to it at untoward length. It lacks those spicy features like operator overloading, and it doesn’t always do things in the smartest or most efficient way. But it’s a hard worker and is biddable enough if you give it what it needs. It never does something so hotheaded as seg faulting.

At this point, I had already taken two semesters of C++ programming, one general introductory course and one data structures and algorithms course. For me, after a year, the romance with C++ was over, and I was starting to discover all the warts and moles and festering gumboils it keeps hidden under its flamenco gown. Probably the most festering of all the gumboils, at least as far as being the ugliest and most idiotic syntax I could possibly imagine to represent the concept, is the “virtual void belch() = 0” syntax for declaring pure virtual functions (“abstract methods” for Java people). Other genius syntax decisions were requiring a semicolon at the end of class and struct definitions and requiring a space between angle brackets in nested template declarations.

You also might expect a beautiful language to make it easy to write beautiful code—beautiful in the sense of shorter, simpler, easier to read, expressed at a higher level of abstraction. C++ does none of those things. If anything, it does the opposite; it’s frequently easier to write the ugliest, most godawful thing you can imagine than anything halfway decent, because the language contains no infrastructure to help you write the nicer solution. For example, I can’t even count the number of times I’ve dealt with text using some variation of reading a single character at a time, clumsily saving some number of them in an array, and examining the whole mess with a huge, ugly if-else if-else if-else if-else if-else if-else-if else-else statement. I could have taken the high road and written my own regular expression engine, but with C++, go too far and it could end up screaming at you for three hours and then storming off to stay with its lover, refusing to come back until your deadline has passed.

C++ has its uses. It’s fast. It’s better than Cobol. It supports object orientation somewhat better than C. But one thing it is not is beautiful.

Thus I fulfill my rite of passage. I have rejected C++. I pass the test, and remain a programming blogger.