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, and not all of it has been especially careful.

There was a good discussion recently on the 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 it is hard to see how they could 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, so read the thread if you are curious.

The gist is that selective overriding of methods in inheritance can cause a lot of trouble. I recalled that Ionuț G. Stan blogged about this problem a couple of 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 the definition of type-class methods in terms of each other?

There was a timely tweet from @HaskellTips that illustrated just this point:

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

(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 are not unique to inheritance and apply to type classes too. Paul puts it more succinctly 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 possible directions:

  1. As recommended in Effective Java, design and document for inheritance, or prohibit it. Guava’s forwarder classes take this approach.
  2. Could we strengthen the “document” part of that advice with something “enforced with types”? I am not sure how that would work, though.
  3. Disallow overridable methods from calling others on the same instance? I am not sure about that either.
  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 do not know whether any language implements this.

This seems like a ripe area for research, and I hope to see more solutions aimed at the problem being discussed.

If you are wondering why I am comparing with type classes in particular, it is because many people seem to think of type classes as a perfect replacement for inheritance. I have been guilty of that too. When I saw SPJ’s “Classes, Jim, but not as we know them”, I found the idea deeply compelling. 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 Stack Overflow to get more views on the subject. I posted another question to Stack Overflow, which received some satisfactory answers, but I am still not entirely convinced there are enough reasons to avoid subtyping altogether.

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

I know there are other things on the horizon. Row polymorphism and extensible records in Ur show great promise. Multimethods, or their subsuming but still 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 of them.

Given Paul’s work and experience with the Scala platform, his criticism of Scala collections is worth taking seriously. But he may not really be criticising subtyping in particular, as many seem to have interpreted it.

In conclusion, inheritance by itself may not be the culprit. The problem of selective overriding is not unique to inheritance. Inheritance has also proven useful in software development, and it seems better to weigh its value, its costs, and its alternatives on a case-by-case basis than to lean too quickly on generalisations.

Criticism and contrarian opinions are always welcome, but they are most useful when grounded in objectivity, careful thought, and good information.