Monday, April 30, 2012

Multiple Inheritance: Comparing Scala, Java, and C++

Apparently my last post on operator overloading in Scala and the comparison to C++ managed to ruffle a few feathers and got some discussion time at Reddit. There were some who felt that I just have a problem with C++. It should be known that I use C++. Most of my research code is written in C++. As it stands, if you want to get close to the machine and use a non-managed language, C and C++ are pretty much the only broadly used options out there.

The reality is that there is no perfect language, and adding features to languages often has the impact of making the syntax dirty. C++ happens to be a language with a rich history and a lot of added features. Java is moving that way as well. Currently Scala isn't there. Time will tell how Scala evolves. Being born with things like type parameters and function literals is helpful, but I fully expect our understanding of what makes for the ideal programming language to continue to grow. That will drive new language development and push existing languages to include new features.

The topic of this post is another feature that really struck me when I was reading "Programming in Scala". One of the other features that the creators of Java left out, partially based on lessons learned from C++, was multiple inheritance of classes. C++ gives programmers the ability to inherit from classes in any way they want. This causes problems in at least two ways. First, any time you inherit from more than one class, you have the possibility for ambiguity. Class D below inherits from both B and C. As such, it inherits a bar method from both so calls to bar on an instance of D are ambiguous by default. The result is lots of use of the scoping operator.

This figure shows an inheritance diamond. The definition of bar in both B and C also illustrates ambiguity without the diamond. This figure appears in my book.

The bigger problem arises when you have a diamond in your inheritance structure. The C++ model of inheritance gives subtypes a full copy of the supertype. So if there are two path to a supertype from a subtype, there will normally be two copies of that supertype in the subtype, and any reference to it will have to be disambiguated through the scoping operator. To get around this, C++ includes virtual inheritance. This can all be implemented in a manner that preserves speed, but it adds some complex details to the language, which a programmer can trip upon just by trying to set up what seems like a perfectly logical type hierarchy. Full discussion of these matters and how they can be implemented can be found in Multiple Inheritance for C++.

The reaction to this complexity in Java was to simply disallow multiple inheritance of classes. This approach had also been taken in Modula-3. Unlike Modula-3, the Java creators added a construct called an interface, which is basically a completely abstract class. This was done not only because of experience with C++, but also because researchers (such as Snyder) had pointed out that inheritance actually provides two separate features to a language. It doesn't just give implementations to the inheriting classes, it provides a common supertype for polymorphism. An interface only helps with the subtyping for polymorphism because it doesn't contain any implementation code.

This fixes all potential problems with the figure above as the only way to get such a setup requires that A is an interface and at least one of B and C is an interface. So implementations can only come from a single parent, and there are no ambiguities. You retain the ability to express that a type is a subtype of two supertypes, so it seems like all is good.

One of the things that happens with language development is that it often takes a long time to learn exactly what impact any given design decision will have. In the case of Java interfaces, there is a subtle nudge toward making thin interfaces, or interfaces that have few methods in them. The reason is that no one wants to use an interface with a lot of methods. When you implement in interface, you have to implement every method in it. If the interface includes 50 methods, that is a lot of coding. You can make a subclass with generally valid default implementations, but that can cause challenges later as the general advice is to program to an interface (from Effective Java), and it is easy for the abstract subclass to gain a few helpful methods that aren't in the interface. Things go downhill from there.

The creators of Scala went with a different approach. There is still only single inheritance of classes, but the interfaces are converted to traits, which do not have to be completely abstract. Like Java, you can inherit from many traits. To prevent the ambiguity problems of multiple inheritance in C++, traits are linearized, so that there is specific order of resolution. (This is not unique to Scala, though Scala might well be the most broadly used, statically typed language to do this.) The benefit of this approach over Java is that it is easy to create traits that have rich interfaces (lots of methods) where most are based on a small number of abstract methods. Anyone implementing the trait need only provide implementations of those few abstract methods. They can override others if desired for performance reasons, but they don't have to.

What is more, the approach taken in Scala opens up possibilities for new techniques. Traits can be constructed in ways that pass calls up to the supertype so that implementations can be mixed and matched, and changing the ordering of inheritance provides different behaviors. This is probably an example where a strength is also a weakness. Most developers today would not expect behavior to change based on the order of inheritance. That turns situations were it does into a "gotcha" logic error. It is still early days for Scala, so we will have to see how this shakes out. Unless you make calls on super, inheritance order doesn't matter one bit, and from my experience the benefits of rich interfaces have outweighed the downsides. However, I would still consider this something of an open question for Scala as a language.