Scala collections library has been receiving a lot of criticism of late. One of the reasons, among many, is its use of inheritance as a primary means of code reuse. This has led to some uproar (a misguided one IMO).

There was a good discussion recently on scala-internals mailing list about a new collection class called AnyRefMap. It brought out many good points. Rex Kerr remarks in one of his posts,

Any method where the call-chain isn’t obvious is unsafe to override. For example, HashMap has -= overridden 7 times and += 8 times in the library scan I did. Update was overridden 0 times. put was overridden 0 times. Now, does += call update, or does update call +=, or neither call the other, or what? In AnyRefMap, += calls update, but put has its own implementation. In HashMap, update calls put, but += has its own implementation.

How is anyone supposed to keep this straight? So in the wild we have 8 implementations of maps that are probably inconsistent because people didn’t override all the necessary methods (and how could they have known?).

To which, Rüdiger Klaehn responds:

There are a lot of methods in scala collections, and it is easy to introduce inconsistencies by overriding some methods and not others. That is why advice to java programmers these days is “Design and document for inheritance or else prohibit it”. (Joshua Bloch, Effective Java). This is basically gospel in java land these days. One of the few things that C# got right was to not make virtual the default for methods.
But how would you design and document for inheritance with scala collections? You could make every method final that is difficult to override because it has to be consistent with other methods. That would be basically all of them except for default in case of AnyRefMap. And then you have to make sure to also do final overrides in case new methods are introduced in one of the traits you inherit from.

(There were many other good points made during the course of the discussion. Read the thread if curious.)

The gist is that the selective overriding of methods in inheritance can cause a lot of trouble. I recalled Ionuț G Stan blogged about this problem a couple years ago, with a very illustrative example. This set me thinking - Wouldn’t type-classes suffer from the same problem, since they too allow selective overriding, and defining of type-class methods in terms of each other?

There was a timely tweet from @HaskellTips (hat tip!), which illustrated just the same point:

Prelude> data Foo = Foo 
Prelude> instance Eq Foo 
Prelude> Foo == Foo  
*** Exception: stack overflow 

(Type-class Eq defines (==) and (/=) in terms of each other.)

Paul pointed out that this problem has a name - fragile base class. We concluded that the problems with selective overriding aren’t unique to inheritance, and apply to type-classes too. Paul puts it much better than I could, so here are the original tweets:

@missingfaktor You’re right that the key dangerous feature is selective overriding, which needs not inheritance.
— Paul Phillips (@contrarivariant)

@missingfaktor The problem is one of preserving atomicity; people write code which implicitly assumes it, then it happens otherwise.
— Paul Phillips (@contrarivariant)

So what could we do about the problem of selective overriding? Here are some potential solutions:

  1. As recommended in Effective Java, “design and document for inheritance or prohibit it”. Guava’s Forwarder classes take this approach.
  2. Could we enhance the “document” part of above advice with “enforced with types”? Not sure how that could be done though.
  3. Disallow overridable methods from calling others on the same instance? Umm… not sure about that.
  4. The Wikipedia page on “fragile base class” suggests “defaulting method invocations on this to closed recursion (static dispatch, early binding) rather than open recursion (dynamic dispatch, late binding)”. I don’t know if any language implements this.

This seems like a ripe area for research, and I hope to see some solutions coming up to address the problem being discussed.

If you’re wondering why I am comparing with type-classes in particular, it’s because many seem to think of type-classes as a perfect replacement for inheritance. I myself have been guilty of it. When I saw SPJ’s “Classes, Jim, but not as we know them”, I was dazzled. I thought type-classes was the best thing since sliced bread. Paired with existentials, they can even do many of the things subtyping can. However, as we just saw, they too suffer from the insidious problem of fragile base class.

SPJ’s presentation poses an open question, “In a language with generics and constrained polymorphism, do you need subtyping too?”. I posted it to stackoverflow to get more views on the subject. I posted this another question to stackoverflow, which received some satisfactory answers, but I am still not entirely convinced there are enough reasons to entirely avoid using subtyping.

As Steve Dekorte and Manuel Simoni are fond of pointing out, there are some great examples of inheritance in wild, and there are ongoing advancements in the area, from the likes of Gilad Bracha and Martin Odersky. People like Daniel Spiewak too seem to think there’s a definite value in subtyping. If I am to borrow Daniel Yokomizo’s words, I would put it this way: Subtyping, to me, gives an easy way of establishing morphisms, which I find hard to achieve with type-classes and such.

I know there are other things on the horizon. Row polymorphism and extensible records in Ur show great promise. Multimethods or its subsuming but immature cousin Predicate Dispatch could be another answer. I do not have enough experience with any of these to have formed a well-informed view on them.

Given Paul’s work and experience with Scala platform, it’s safe to assume that his criticism of Scala collections is very much valid. But he may not really be criticizing subtyping in particular, as seemingly misinterpreted by many.

In conclusion, inheritance by itself may not be the culprit. The problem of “selective overriding” is not unique to inheritance. Inheritance has proven to be a useful technique in software development. We should give a careful consideration to the value it adds, the problems it brings, its net utility, and other factors on a case-to-case basis, without unnecessary generalizations.

Criticism and contrarian opinions are always welcome, but they should be founded on objectivity, careful thought, and right information. Mere passive aggressiveness and loudness does not a valuable opinion make.