A Magical Girl Simulation in Clojure (Yes, there was a point to doing this)

Recently I wrote a couple of Code Review.SE answers for games in Clojure. All the code I looked at was written essentially like C: data was stored in global variables or in “god” maps that were passed into every function. Entities were all modeled with plain maps or vectors. None of the code was bad per se, but everyone seemed to be ignoring Clojure’s object-oriented features, records, protocols, and multimethods, even though games and simulations are exactly where object-oriented programming really shines.

Since I didn’t have any real experience writing something like this in Clojure, I decided to write a very silly project: a simulation of a certain anime about magical girls and witches. I would try out the techniques I’d been recommending to other people, and find out if they really worked better than the bare-bones approach with global variables and built-in data structures.

The entities: exercising Clojure’s object-oriented features

I first put some thought into how I wanted to represent the entities: the magical girls, witches, familiars, and Incubators. (The familiars aren’t used in the final code, but they could be incorporated somewhere.) I knew I wanted to use the object-oriented features to do this, but Clojure gives you a ton of choices in how you organize that.

Which object-oriented feature?

Clojure has three major features which support object-oriented programming: records, protocols, and multimethods. Records and protocols together are closer to traditional classes like we have in Java and Python. A record is rather like a C struct: you can declare record types with the defrecord macro, and give a list of fields which are available on that record type. This causes a constructor function to be defined. The fields of a record are accessed just like a regular Clojure map; you can use get, or the names of the fields as keywords define functions which take the record as argument and return the value of the field. Unlike C structs, you can add fields to a record using Clojure’s assoc, just like you can with maps.

However, fields defined in the record actually become instance fields of a Java class which represents the record in the generated bytecode. The JVM is optimized around Java classes, so accessing instance fields is very fast. So records are sort of a performance enhancement.

Records are data holders. Since Clojure has first-class functions, you could theoretically have the data a record holds be functions, and then it would sort of feel like a class. But protocols and multimethods are better ways to get behavior on records; they permit polymorphism and limited types of inheritance.

Protocols are somewhat like Java interfaces. They’re lists of function names and signatures, defined with the defprotocol macro. When you define a record type, you can also have it adhere to a protocol, which is like implementing an interface: you give the bodies of the functions, which all take the record as the first argument. Different record types can adhere to the protocol in different ways, which gives you polymorphism in the same way interfaces do.

Multimethods are apparently a concept which originated in Common Lisp’s CLOS, although I have no familiarity with CLOS. They’re a little tricky to understand, but incredibly powerful.

In an object-oriented language like Java, you can have multiple classes implement the same method. When you call the method on some object, the runtime decides which version of the method to call based on the class of the calling object. Say we have a Goth class and a Beatnik class, which both inherit from Counterculturalist and both implement the method writePoetry from IPoetic. Given an object Counterculturalist c, we execute c.writePoetry(). Then, if c is an instance of Goth, we’ll get back something like “The world…is dark. Dark…like the depths…of my soul…”. If c is an instance of Beatnik, we’ll get back something like “Scabbidy dabbidy doo, blabbidy scabbidy doo”, accompanied by bongos.

Now, suppose we wanted to refine our criteria for choosing which version of writePoetry to execute. For example, suppose we wanted to distinguish GothFamiliarWithTheWorksOfWilliamWordsworth from GothUnfamiliarWithTheWorksOfWilliamWordsworth. In Java, we’d have to make two more classes, have each inherit from Goth, and have them override the writePoetry method again. That’s a lot of classes, and a lot of repeated code. Especially when we also need to distinguish GothWhoOnlyReadOnePoemByWilliamWordsworthAndHatedIt.

Wouldn’t it be nice if we could just add a field to the Goth class, familiarityWithTheWorksOfWilliamWordsworth, which would rate the familiarity on a scale of 0 to 100? Then have the writePoetry methods get progressively more Wordsworth-like as the familiarity rises?

Yeah, multimethods can do that. No ifs, &&s, or switches about it.

Specifically, multimethods can use whatever criteria you want to decide which version of a method to call, provided you can write a function to test those criteria. You call the multimethod with whatever data you want, and it uses the function you defined to decide which method to dispatch to. You can dispatch on multiple fields of a record or map. You can dispatch on functions of multiple arguments. You can get as crazy as you want. You can have a multimethod which decides how to dispatch based on whether the first argument is a map whose keys all start with s or not, and the second argument is a vector of vectors of maps whose values all implement java.lang.List.

Multimethods are much more powerful than protocols. They become even more powerful when you throw in the derive and isa? functions. I won’t go over those here, but you can read about them elsewhere. The Joy of Clojure covers them very thoroughly. With multimethods, derive, and isa?, you can basically implement your own form of object-oriented programming. You can combine records and multimethods and get some amazingly powerful designs.

With great power comes overly complex programs

I decided that I didn’t need so much power for this program. I went with protocols.

I made a record type for each of my entities, defined to hold the base-level fields. Fields which were less essential or prone to change were added later with assoc.

I made a Combatant protocol with various functions that define behaviors and properties of the entities: can-flee, blacken-soul-gem, increase-combat, won-battle, and fled-battle. Most of them only do anything interesting when called on a magical girl, but I implemented them for witches and familiars so that I could map them over a vector of entities of mixed types. Witches and familiars just get returned unchanged from their versions of the Combatant functions. This simplified my code for combat later on.

You can see that this is very similar to what you can do with an interface in Java. I could have written Java classes for each of my entities and had them implement an ICombatant interface. That’s why I didn’t need the power of multimethods.

Top-level architecture

Drawing Inspiration from Rich Hickey’s Ants Demo

I first planned my magical girl simulation as a discrete-time simulation; it would have turns or phases during which the entities would take actions, then stop to let the code update state. But ever since I read Seven Concurrency Models in Seven Weeks, I’ve been wanting to try out some concurrent programs, and this seemed like a good chance, so I decided to make the program a continuous-time simulation. But I had a hard time coming up with an architecture, until I remembered reading about Rich Hickey’s ant simulation. This is a demo Rich Hickey wrote early on in Clojure’s life to show how Clojure’s approach to concurrency works. Someone very helpfully made a literate programming version, so everything is thoroughly explained in text alongside the code.

If you don’t want to read the code, I’ll summarize. The ants move around on an 80 by 80 grid looking for food. As they explore, they leave pheromone trails for other ants to follow. When they find food, they bring a piece of it back to the nest. Other ants will reach the same source of food by following the pheromone trails. However, the trails decay and become weaker over time.

The ants are represented two ways: an ant struct (a record in modern Clojure) that tells us which direction the ant is heading, and how much food it’s carrying, if any; and a vector of ant agents. The world grid is a vector of vectors of refs to cell structs, which store how much food is on a square, how strong the pheromone mark on a square is, whether the square is part of the ants’ home, and the struct for any ant which is currently on the square. Making them refs lets the program update them concurrently, for example by moving an ant from one square to another, without worrying about another thread trying to access the same square before it’s done.

The ants’ behavior is implemented as the function behave. When the program starts, we send-off the behave function to all the ant agents. The ant agents only store the ants’ current locations, but with that information, we can look up the ant struct stored in the world grid and make any modifications we want. The behave function will make the ants move, pick up food, bring food home, and leave pheromone trails. It runs in an infinite loop by adding another invocation of itself to the ant agent’s work queue every time it’s called. Since each ant is an agent, and agents are concurrent, uncoordinated, and asynchronous, each ant behaves as an independent entity, in real time.

How does this work with magical girls?

My magical girl simulation is very similar to Rich Hickey’s ant simulation. Instead of ants, I have magical girls, and instead of food, I have witches. The magical girls search for the witches just like the ants search for food. Unlike the ants, the magical girls can sort of tell where the witches are because their soul gems will react to the presence of a witch; by contrast, the ants search for food at random, using the pheromones as a guide.

In the final version of my program, I used a continous world; instead of having discrete squares like a chess board, I used floating point numbers to approximate a realistic world. Each witch and magical girl has a detection radius. If the circles defined by the witch’s and magical girl’s detection radii overlap, the magical girl detects the witch and can choose to fight her. In a continuous world, you can’t wait for two entities to be on the same space before they can interact; there are just too many spaces.

What about core.async?

Seven Concurrency Models in Seven Weeks covers core.async, a new Clojure library whose premise is stolen from Go. (Rich Hickey himself says so, unabashedly.) I wanted to try out core.async too.

The ant demo code is pretty old as Clojure code goes. No one uses structs or the sync macro anymore, and there are easier ways to build a UI in Clojure than calling to AWT through Java interop. I wondered whether a modern version of the ant demo could use core.async to clean some things up.

I soon realized that there was no place for core.async in the ants demo, at least so far as I could see. Go, and core.async by merit of having stolen its premise from Go, implement CSP, a paradigm for concurrency invented by computer scientist Tony Hoare in the 1970s. CSP and actors (as seen in Erlang, Scala, and the Akka framework) are both models of concurrency based on message passing. They’re sort of like two sides of the same coin. Actors are a special kind of process which the system runs concurrently, set up with a mailbox and a PID so they can receive messages from other actors. Just how actors send and receive messages is transparent to the programmer. It’s an implementation detail. When an actor sends a message, it could be appending to a queue in the machine’s memory, or serializing the message and sending it to another machine in the same cluster, or it could be encoding the message as JSON and sending it to a web service running on a server on the other side of the planet. From the programmer’s perspective, these all look the same.

In CSP, there’s nothing special about the process. Processes in a CSP-based architecture can be threads, or actual OS processes, or they can just be separate functions operating in the same thread at different times. Where actors use a special abstraction for the process, CSP uses a special abstraction for how messages get passed: the channel. Any process which has a reference to a channel can write to that channel, and any other process can read from that channel, at any time. CSP still lets you run things across multiple machines, but the implementation of the channel will change.

As I was thinking about how to apply core.async to the ant program, I remembered that, hey, core.async is CSP, and CSP stands for communicating sequential processes. As soon as I thought that, I realized that core.async wasn’t really applicable to the ant demo. At first I thought this was because the ants don’t communicate with each other. But they do—through the pheromones. Modeling the pheromone trails with channels seemed pointless and overly complex. It’s just not a good fit. The way Rich Hickey modeled ant pheromone trails is a good way to model how ants communicate.

By the way, even though CSP and actors are closely related, there’s something in Clojure which behaves much more like an actor when it comes to entity modeling: agents. The ants are independent entities acting asynchronously. Agents are perfect to model that.

That means core.async would be an even worse fit for my simulation, because magical girls and witches don’t communicate with each other at all. They’re completely independent. But agents are still useful, because my magical girls are going to be independent entities acting asynchronously, just like the ants.

Agents of F.A.I.L.

Since I was heading into uncharted waters here, I did what I often do when I need to explore whether something works: I brutally stripped down the features to the bare essentials and implemented a prototype. In this case, I used Quil to make a display of pink and black dots. The pink dots represented magical girls, and the black dots were witches. I coded up something very similar to the ant demo. I used agents to represent the magical girls. Rather than use a discrete grid like the ants demo, I used a continuous world with floating point coordinates. I stored the witches in a vector and had each one hold onto its coordinates.

This worked pretty well as long as I only had about five or six magical girls. Above that, it pretty much broke down. Unlike actors in Erlang and Akka, Clojure agents aren’t designed so that you can have hundreds or thousands of them going at once. Brian Carper ran into similar problems when he wrote a game and tried to make every entity its own agent. I knew this problem was only going to get worse when I added the rest of the features. The prototype didn’t even have the magical girls searching for witches or engaging in battles; they just milled around at random, ignoring the witches. And the performance was still too lousy to allow more than five or six magical girls at a time.

I threw away that prototype and rewrote it to work like most real-time games do: some code runs every frame to update the state of the world. It’s still kind of turn-based, but it looks more or less real-time when it’s running. It was disappointing, but I learned a lot from looking at Rich Hickey’s ants code (including how to do literate programming in Emacs Org Mode), so I’m glad I gave it a try.

The rest of it

The rest of the code was pretty standard Clojure stuff, but it was fun and interesting to put my functional thinking powers to the test. Object-oriented and imperative programming fit games and simulations so well that it’s tempting to overuse Clojure’s imperative escape hatches. One CR.SE user whose code I looked at had done just that, using atoms as mutable variables and updating them in an imperative style. This user felt the design had gone wrong somewhere. I pointed out James Hague’s excellent Purely Functional Retrogames article as a good source of advice.

Now I had to follow that advice myself, and I thanked the Rich Hickey for destructuring, because this code would have been a nightmare without it.

The basic idea behind my design was to have my entities and other important state stored in a bundle of world state which would be passed around. Each frame, the top-level code would pass the state bundle through a pipeline of state update functions which would return “diff maps”—maps which contained the changes that needed to be reflected to the world state. The diff maps could be combined with the world state using Clojure’s merge and merge-with functions. This design was based on James Hague’s article.

Hague suggested that the code for state-updating functions is easier to read if you have the functions take separate arguments, instead of just passing in the whole state bundle, and unpack the values from the bundle at the call site. I didn’t do this. Thanks to destructuring, though, the state bundle gets unpacked in the function’s argument list, so it’s still informative to glance at the argument list to see what data the function uses, and I could name the arguments without having to do a let inside every function.

The final version of this code feels very clean and nice and purely functional, but it also feels fragile and somewhat restrictive. Although the functions themselves are nicely separated, and I can insert new stages in the pipeline if I want, I don’t feel like I can do anything that isn’t easily expressed by functions in a pipeline that return results.

I almost got myself in trouble with this. I organized the display code in Quil around the idea of turns / frames, with a certain number of frames per day. At the end of a day, the magical girls all get sent back to their home squares. This simulates magical girls returning home at night to sleep and spend time with their families.

I needed to begin a turn with a function that would move the magical girls to a new position, except when the day was over. When the day was over, they needed to go home. This would be easy to write in an imperative style: just something like

if turns % turns_per_day == 0:
    move_home(magical_girls)
else:
    move(magical_girls)

in pseudo-Python. I couldn’t do that here though; I had to somehow cause the move function to send the magical girls back to their home squares, and return the newly resting magical girls as part of a diff map to send into the next stage of the pipeline.

When I was writing the move function, I made it so a move on a magical girl with no defined position would place her at home. I did it so the function would be more robust and not crash if I forgot to set a position on some magical girl, but it turned out to be useful here. I mapped over the magical girls, using dissoc to remove their positions. Subsequently, when move was called, they would be moved home.

I ended up implementing this with the following code:

(defn before-combat
  "Creates new magical girls and moves the magical girls for this
  turn. Returns a diff map of changes. Meant to be called in pipeline
  with events/round-of-combat and events/spawn-witches."
  [{:keys [magical-girls witches incubators
           turns turns-per-day world-size] :as bundle}]
  {:magical-girls ((comp
                    (partial map #(events/move % (:within-world? bundle)))

                    (if (zero? (mod turns turns-per-day))
                      (partial map #(dissoc % :position))
                      identity)

                    (partial
                     concat (events/spawn-magical-girls
                             incubators
                             world-size)))

                   magical-girls)
   :witches witches})

That feels very complicated to me. There’s a lot of nesting and strange point-free-type stuff going on here. But I needed the function to return a diff map, because that’s what the next stage of the pipeline was expecting as input. I suppose I could have defined a name for the function I made with comp, but it’s only used once, and it’s so specific and in such violation of the single-responsibility principle that I don’t even know what I’d call it. So maybe it’s actually less confusing with a giant comp written out here, than it would be if I added some pointlessly specific function that’s only used once?

Overall, though, I was pretty satisfied with how the code turned out. For the most part, it felt like a confirmation that functional programming can be much easier and more elegant than imperative programming. I had a lot of fun writing it, too.

Tests

I wrote unit tests for almost everything in this project. This was where the advantages of functional programming became extremely obvious.

For one thing, since all my data was immutable, I didn’t need fixtures to refresh the state of my sample data. I could just make some top-level definitions and keep on reusing them.

Since I wrote all my functions without side effects, I could test practically everything in isolation, without having to build up a lot of infrastructure around it.

Early on, I realized that I couldn’t test things that used random numbers if I was getting my random numbers from Clojure’s rand and rand-int functions. Instead, I made an instance of java.util.Random inside my namespace. It was dynamic, so I could rebind it with binding to another instance with a known seed, and get deterministic tests.

Writing the tests for this project was a joy. I had almost no major bugs and never really felt the desire for a stepping debugger, all thanks to the tests. The only time I wished for a more powerful debugging tool, I found myself wishing for Typed Clojure. I got around this using Clojure’s precondition and postcondition facilities.

Incanter

Incanter is a pretty cool library. I used it for some of the stochastic and random number stuff in this project. It’s very easy to use and there’s a lot to it.

That said, I feel like Clojure lags behind Python in statistical and scientific computing. Incanter is easier to use than Numpy/SciPy/Matplotlib, but it’s missing quite a few things that the Python scientific stack has. I still had fun with it, though. I graphed a few circles to help me design one of the tests. It only took about four lines of code, and I had a nice-looking plot of four circles with a legend.

Quil

I love Quil. I looked at Processing a few times, but I was a little wary of learning a whole new language just for playing around with some graphics. Quil is great, in that it’s even easier to play around with graphics using Quil than using Processing, and I can do it from a language I already know, Clojure.

I took computer graphics at university and hated it. We did all raw OpenGL calls from C++, except on our last assignment, when everyone cheated and used game engines and 3D modeling programs to create nice things which they read in and rendered on screen with raw OpenGL calls. Except me, because I didn’t know about any of those programs because I wasn’t a PC gamer. I worked with a partner who did, so she created most of our assignment, but then it didn’t work and we couldn’t figure out why because the code was so disorganized. The construction of OpenGL actively fights any attempt to organize your code with object-orientation, so C++ was mostly just C with STL vectors. Which I guess is still better than C. But still disorganized.

The main thing I hated about computer graphics at university was the utter lack of fun. Graphics are supposed to be fun. You’re making cool things appear on screen. Nothing is less fun than OpenGL. OpenGL is so low-level it felt like writing assembly again at times. I stupidly made things hard on myself by using vertex buffer objects and shaders instead of just using the fixed function pipeline like everyone else, but even later when I tried the fixed function pipeline, there was just too much garbage to deal with. I understand that OpenGL is written that way for performance reasons so the guys making those fancy video games that us old timers who played the original Megaman X on the Super Nintendo don’t even know the names of can make them perform. But that’s not what I’m doing.

That’s why I love Quil. It makes graphics simple and fun. It removes a whole layer of pointless crap you don’t want to have to deal with when you’re just exploring and having fun. Sure, it doesn’t perform that great. Who cares. If I really need blazing fast performance, then I’ll move to C++ and OpenGL.

Conclusion

This was an interesting project, and I was able to exercise a lot of the things I’ve learned about Clojure and functional programming in the past few years.

Unfortunately, like many of my projects, it’s not really done. It reached a point where I’d pretty much learned what I wanted to know, and then I gave up on it.

As it is, you can start it up and see magical girls and witches moving around on screen, but there are a couple ways it fails to fulfill my original vision:

  • Magical girls don’t stop after killing one witch. They keep going. In the show, magical girls were never in the mood to go hunt down another witch after they’d managed to kill one. They do stop at the end of a day and go home, but I feel the witch attrition rate is much higher than it should be thanks to this.

    I did come up with a way to fix this: after a magical girl defeats a witch, unset her position so that she gets sent home on the next turn, and also set a waiting property. Have the move function ignore any magical girl who has the waiting property set. Unset waiting at the beginning of a day. I haven’t gotten around to implementing this, though.

  • The magical girls don’t really seek out the witches. They move around at random, stumbling on witches. The witches’ discovery radii are pretty large, so the girls don’t really have trouble finding witches to fight, though.
  • There were a lot of features I had planned that I never implemented. I was going to have familiars as extra impediments to the magical girls. I even wrote the familiar record and protocol code, but it’s not used anywhere in the program. I was going to have a giant fancy system of gradated discovery radii with different probabilities for discovering a witch.
  • There are probably still scalability problems. I used the equivalent of a nested loop to find pairs of witches and magical girls which were within each others’ ranges. I looked into quadtrees, but they seemed quite complicated.
  • It would be nice if there were more monitoring mechanisms, so you could check out how your magical girls are growing, and get stats like the conversion rate into witches and whether new magical girls are getting totally squeezed out by older, more powerful ones (like what happens in the programming world on a job search).
  • I may come back later and implement some of these things. Or not. After all, it’s not like simulations of magical girls in Clojure is going to get me a job.

    Advertisements

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.