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

Finally writing something in Clojure: The Decision

I’ve been interested in functional languages for a while. My first exposure to functional programming was in Alan Gauld’s tutorial, where he introduced some of the ideas from functional programming used in Python. I’d like to say my mind was blown by this incredible new programming paradigm, but at that time I had been programming for all of three months and barely understood functions (and classes were right out) so it was more like my mind was a steel wall and functional programming was the ball from a medieval cannon. It just bounced right off.

But back when I was doing linguistics, I was always attracted to obscure languages, especially the ones with baroque, logical, and elegant grammars. I’m talking about Latin, Turkish, Lakhota, Sanskrit, that kind of thing: languages with complex yet consistent morphology, that combine a small number of concepts in a logical way to build up short, expressive sentences. Functional languages are sort of the programming language equivalent of that, so it was almost inevitable that I’d end up being attracted to them. (Perl fans apparently say that Perl is like the English of programming languages. You can take that comparison whatever direction you like.)

Anyway, I bought the book Seven Languages in Seven Weeks, which included four functional languages: Erlang, Scala, Clojure, and Haskell. Scala looked too much like Java crossed with Pascal for my tastes, and while Haskell seemed really cool, monads seemed really uncool. At first I liked the look of Erlang. I loved Prolog, also covered in the book, and Erlang is loosely based on Prolog, so it includes some of Prolog’s most ingenious ideas, like the atom datatype. The concurrency stuff was also pretty awesome. I had never done any concurrency before, aside from a few tiny book examples with Python’s threads, but I came to really like Erlang’s “smoke signals on a mountaintop” approach to representing synchronous processes.

There was just one problem: I write a lot of utility programs for working with text, for both my linguistics hobby and my writing hobby. Erlang is awful at dealing with text. Its strings are actually lists of characters, and its characters are actually integers. I thought about going for it anyway with Erlang, but then I read the chapter on Clojure. While I wasn’t too excited about Lisp and the explanation of concurrency in Clojure was total gibberish to me at the time, I decided it was probably the best way to go, since it has Java backing it up. Java is okay at dealing with text; it’s no Icon, but it does at least have a string type.

So that was that, and I learned Lisp, and everything was good.

NO! No one ever learns Lisp that easily! In fact, I had already been struggling for most of two years just to understand its syntax. Reading the Clojure chapter in the Seven Languages book (and learning more about prefix notation) made the syntax itself pretty clear, and I just pounded the concepts of s-expressions, macros, and working with lists into my heading by reading introductions to them in every book and on every website I could find. I later took a programming languages class at UC Davis where we used Common Lisp, and that made everything pretty clear (and also made me appreciate Clojure’s little bits of syntax, like [] for vectors and {} for hash maps). By the way, the professor was a total Java lover, so I’m surprised he didn’t have us use Clojure.

I installed Clojure, messed around with it, got bored, decided I’d better stop trying to learn functional languages and should focus on stuff that would get me a job, like PHP (ugh), and tried and failed several more times to do something with Clojure. I used it once to implement the Lucas-Lehmer algorithm for primality testing, but that was about it. (My number theory teacher had asked us to test some rather large numbers using Lucas-Lehmer. It would have been plausible to do it by hand with a calculator, but instead I had fun writing the algorithm in Clojure, and presented the code as my answer, along with its results for the given numbers. Full marks! If only the rest of my number theory homework could have been solved by Clojure.)

Recently I decided to publish a book to the Kindle Store. Amazon likes HTML in one big file. I had two problems:  I saved everything in separate ODT files (one per chapter), and Open Office spits out the most awful HTML ever, and includes formatting flaws caused by weird invisible control characters. As an example, if you hold down shift and hit return in Open Office, you get some kind of weird pseudo-newline. When viewing the file in Open Office, it’s indistinguishable from a newline; in the HTML output, it gets turned into a <br /> tag, whereas a normal newline becomes a <p> tag. So when you view the document in a browser, there’s an empty line between every paragraph, except for the ones where I was thinking about my writing and not whether Open Office was going to mangle my formatting later, and held down shift when I hit return.

I tried using PyUNO to make Open Office merge my chapters into one big file, but there’s barely any documentation on PyUNO (or any of the other options to access the API) that I could find, and even getting it to start was a challenge. When I did get it started, I had a fun API of funness to master, with all the functionality inside classes which were inside packages which were named with like five layers of qualification. (The API seems to be written in Java, and Java code is all like that.) I found some scripts that claimed to do what I wanted, but they all crashed when I ran them, so I gave up on PyUNO and decided to just convert the files to HTML using Libre Office’s command line batch conversion powers (which Open Office claims to also have, but which didn’t work for me) and work on them in that state.

A while ago I wrote a truly awful Python script to convert an HTML page into a PDF. I used Python’s built-in HTML parser class to massage the text into a usable form, and the ReportLab library to do the conversion. The script’s user interface was totally braindead. For a while you had to open the source code and change the value of a global variable to change the title. Yes, I know that you should never make your user modify your source code to get basic functionality, and using global variables is a slippery slope that will lead us back to the days of BASIC and goto statements. I had to interact with a ReportLab call which required a function as input; this function had to make some more API calls that would set various parameters, including the title. I couldn’t make a function that took the title as an argument because the ReportLab function was going to be the one calling it, so it had to conform to ReportLab’s expectations. Then my brain finally turned on and I remembered closures; I made a factory function that would take the title as an argument and close another function around it. That closure could then be passed to the ReportLab API.

I went into that story for two reasons: closures are useful after all (no other method could have solved this problem so cleanly), and in the end, no matter how awful it was, I got my HTML pages as PDFs, so I figured I could do that kind of thing again. I was going to use Python this time too, but I’d been thinking about picking up Clojure again, so I decided to put in some effort and try to do the project in Clojure. While I knew Python had the libraries and documentation to handle the problem, I felt pretty secure with Clojure because you can always dip into Java. So far I haven’t had to, though.