Wednesday, July 20, 2011

Kotlin, the Diamond Inheritance Problem, and a Provisional Solution

Yesterday afternoon at the JVM Language Summit brought a pleasant surprise in the form of the Kotlin language. The language itself is remarkably ambitious, if largely unfinished (one of the presenters informed us that the largest Kotlin codebase in existence was 250 lines). The language is charmingly expressive and contains some sophisticated concepts, including many of those found in Scala (Paul Phillips of the Scala team said it looked as if the Kotliners had gone through the Scala manual item line by line, checking off the features they wanted to keep or reject. It looks to me, though, that Kotlin has borrowed from more than one language).

Kotlin makes nullability annotations mandatory and easy to express: a type that can be null ends in a question mark. A Kotlin Int is a Java primitive int, never null; a Kotlin Int? is a java.lang.Integer that can be null.

Kotlin's pattern matching is prettier than Scala's; I've often resented having to waste four whole characters on the case keyword at every pattern.

Like Scala, Kotlin also variance at the declaration site of a class. But it also has use-site variance, and the compiler enforces the latter to ensure that you can't abuse the use-site type to violate the promises made in the class's declaration. This idea was clever enough to prompt Paul Phillips to burst out that he was going to steal it for Scala (although folks on the scala-debate mailing list have pointed out that there are already other ways to do this in Scala).

The Kotlin team took the most heat when they described their inheritance rules, which allow generalized multiple inheritance. They solve the diamond inheritance problem with duplicated superclasses, like C++. Multiple inheritance is obviously not a popular choice among language designers these days. There's no doubt that a number of languages have gotten multiple inheritance wrong, and that even where the language itself hasn't made some hideous blunder, an API designer can use multiple inheritance to make a bad design much worse.

But but but but but. All that said, when not abused, multiple inheritance is quite expressive. Java programmers use multiple inheritance of interfaces all the time, and nobody makes them wear scarlet letters “MI”. Purists will object that of course this is not inheritance; inheritance means inheritance of implementation, in the form of code or data, not just method signatures.

Well, whatever.

To be sure, Java-style multiple inheritance is virtual inheritance: if a class C inherits a method m from two interfaces A and B, C gets only one implementation of m; there is not a distinct A.m and B.m within C.

C++, by contrast, allows nonvirtual multiple inheritance that can pick up multiple distinct versions of inherited features (as well as virtual inheritance, in case you are insufficiently confused). Nonvirtual multiple inheritance may occasionally allow for some clever implementation tricks, but for those of us who are trying to cling to the shreds of our object-oriented faith that an object has sole control on how it responds to messages, nonvirtual inheritance (which allows a message sender to choose which inherited response it wants for a given message) is a heresy, an abomination, and by Turing, an affront to all that is good and decent.

Scala, of course, allows multiple (virtual, of course) inheritance of traits. Traits can, and often do, contain both code and data. Purists will object that of course this is not true multiple inheritance because, uh, well, the things being inherited are called traits, not classes. And multiple inheritance refers only to classes.

Well, whatever.

Scala traits may be well down the slippery slope of multiple inheritance, but they do differ from classes in that they can't have constructors. Or more precisely, they can't have constructors with arguments—but they can contain initialization code, which gives the effect of no-argument constructors.

Here's a question: ignoring for the moment the broadly agreed inadvisability of generalized multiple inheritance (I realize that asking you to ignore this may, in some cases, require a superhuman act of forbearance), what would such inheritance look like, if inheritance were virtual and constructor inheritance were allowed?

Consider the classic diamond:

/ \
Bird Cooing
\ /

Dove inherits directly from Bird and Cooing, each of which in turn inherits directly from Animal. Dove's constructor therefore has to invoke constructors for Bird and Cooing, and Bird's and Cooing's constructors each invoke an Animal constructor.

Remember now that we're aiming for inheritance from a single copy of Animal, lest we fall into the mortal sin of nonvirtual inheritance.

First, an easy case. What if Animal takes no constructor arguments (or more precisely, neither Bird nor Cooing invokes an Animal constructor with arguments, in the case that Animal has more than one constructor)? There's an obvious course of action: the first invocation of the Animal constructor is performed normally, and the second is intercepted and not done. This seems plausible on the basis that one Animal constructed with no arguments is likely to be more or less indistinguishable from another constructed with no arguments, so we fulfill our intention that Bird and Cooing are the same Animal—as long as Animal is constructed just once, our immortal souls are not imperiled.

The above scheme works even if the Bird and Cooing constructors take arguments. Constructors of immediate supertypes are performed in some order (presumably, by default, in reverse linearization order, on the principle that the type with the highest priority gets last say; in this case, this would mean Bird is constructed before Cooing). Dove just passes the respective arguments to each of the constructors in order (so that Bird's constructor constructs Animal) before embarking on its own constructor code.

The poop hits the scoop when Bird and Cooing invoke Animal constructors with arguments. How do we preserve the property that they construct the same Animal? One idea is, again, just to elide the second construction. However, if Cooing (whose construction of Animal would be skipped) wanted to specify an Animal with properties different from those specified by Bird, wouldn't that mess up Cooing? Cooing, after all, is well within its rights to depend on the property values that it sets in Animal.

The solution I've come up with is so obvious it's stupid: just check the constructor arguments. That is, firstly, if Bird and Cooing invoke different constructors of Animal from their constructors invoked by Dove, then Dove is illegal to begin with, and the compiler will complain (this has the possibly nasty side effect of requiring Bird and Cooing to expose to Dove precisely how they construct Animal; feel free to lie awake all night over this on my behalf). If Bird and Cooing invoke the same constructor, though, you're not yet free and clear; at runtime, you perform the first construction, but you redirect the second construction to a check that the arguments you pass to the second construction are the same as those you passed to the first construction. If the check fails, throw an exception so that the construction of Dove does not complete.

There is no shortage of hassles with this strategy, including actually writing the code to preserve the arguments passed to the first invocation of the Animal constructor long enough to be checked with those passed to the second, and choosing the appropriate definition of “same constructor arguments”. (As for efficiency, in practice, I would hope that a smart enough VM would usually observe statically that the same values are passed to the second constructor as to the first and thereby deduce that it could elide the check, since many constructors pass their own arguments unaltered to their superclass constructors.) Anyhow, this is the best solution to the generalized diamond inheritance problem I've managed to come up with. Let the hole-poking begin.

No comments:

Post a Comment