Monday, February 25, 2008

Implementation Inheritance with Mixins - Some Thoughts

Eugene's post It is safer not to invent safe hash map / Java once again brings forth one of the most controversial topics in the OO space - public inheritance, in general and implementation inheritance, in particular. Inheritance is a hard problem to solve in OO programming. Anton Van Straaten says in this LtU thread ..
".. inheritance definitely seems to be an "unsolved problem" in OO languages. As already mentioned, it involves so many competing forces: typing, interface vs. implementation, single vs. multiple, etc. As a result, languages have typically picked some workable compromise, and lived with the limitations this produces."

And, so has Java. In Java, the recommended practice is to make heavy use of interfaces and design concrete classes using interface inheritance. But there is no elegant way to reuse interface implementations, unless you resort to tools like AOP that works on byte code weaving. People often try to use public inheritance on concrete classes in Java to add new behaviors or override existing ones and lands up losing extensibility in orthogonal directions.

Consider the abstraction java.util.Map<K,V>. The following are the various collaborations that the abstraction participates in.

  • It has subinterfaces like SortedMap<K,V>, ConcurrentMap<K,V>, which implies linear extension of the contract. That is, these subinterfaces add additional behavioral contracts (no implementation) to the generic map.

  • It has multiple implementations like HashMap<K,V>, TreeMap<K,V> etc.

Hence any added behavior to a generic component like Map<K,V> needs to work across all extension points of the abstraction. This is where the suggested implementations by the original authors of SafeHashMap<K,V> falls flat. As Eugene points out, extending java.util.HashMap<K,V> will result in the additional behavior NOT being implemented in other variants of Map<K,V>. While adopting a wrapper based implementation will not scale with SortedMap<K,V> and ConcurrentMap<K,V>.

And, of course, implementing the contract of Map<K,V< ground up with additional behavior will force a blatant copy-paste based implementation.

Eugene's implementation, based on static methods and camoflaged with static imports gives it the best possible shape in Java.

Can we do better ?

No, not in Java, unless you use tools like aspects, which may seem too magical to many, and of course, is never a substitute to better language features.

What we need is the ability to compose independent granular abstractions that can seamlessly mix in the main abstraction additively to introduce new behavior or override existing ones. CLOS refers to this technique as mixin based programming - Gilad Bracha, in his OOPSLA 90 paper defines a mixin as an abstract subclass that may be used to specialize the behavior of a variety of parent classes. It often does this by defining new methods that perform some actions and then calls the corresponding parent methods.

The example in CLOS, which the paper illustrates is ..

(defclass Graduate-mixin () (degree))

(defmethod display ((self Graduate-mixin))
  (display (slot-value self 'degree)))

In the above example, the mixin method display() invokes call-next-method despite the fact that the mixin does not have any explicit parent. The parent comes in implicitly when the mixin class is mixed-in with another abstraction that supports the same method display().

(defclass Graduate (Graduate-mixin Person)())

Here Person is the superclass of Graduate and Graduate-mixin mixes in with the hierarchy to provide the additional behavior. The mixin has no independent existence and cannot be instantiated on its own. It comes to life only when it is mixed in with an existing hierarchy. Hence the term abstract subclass.

Mixins provide a notion of compositional inheritance that allow sharing of implementations along with pure interface inheritance, without the noise of an intermediate abstract class - it is like being able to provide implementation to Java interfaces. There have been a few proposals in the recent past for adding mixins in Java.

Till we have mixins in Java 7 ..

Scala provides mixin implementations as traits. Reusable behaviors can be modeled as traits in Scala and mixed in with concrete classes during class definitions as well as object creation. The most commonly demonstrated use of a mixin in Scala is the use the Ordered trait, which implements total ordering of data for the class with which it is mixed in.

class Person(val lastName: String, val firstName: String)
extends Ordered[Person] {
  def compare(that: Person): Int = {
    //.. implementation

The parent class has to implement the compare method, but gets convenient comparison operators for free by mixing in with the trait. This is implementation inheritance without the abstract class. And the class designer can stack in multiple behaviors simultaneously by mixing in with many traits at the same time.

Scala traits also offer implementation inheritance also on an object basis, through mixins during object creation.

Consider adding a synchronized get method to Scala Maps as an additional behavior overriding the existing api. We can define a trait for this behavior ..

trait SynchronizedGet[A,B] extends Map[A, B] {
  abstract override def get(key: A): Option[B] = synchronized {

which overrides the get method of Map with a synchronized variant.

Now we can mix in this behavior with any variant of a Scala Map, irrespective of the underlying implementation ..

// Scala HashMap
val names = new HashMap[String, List[String]]
              with SynchronizedGet[String, List[String]]

//.. use names

// wrapper for Java Map
val stuff = new scala.collection.jcl.LinkedHashMap[String, List[String]]
              do SynchronizedGet[String, List[String]]

//.. use stuff

In fact Scala provides a complete trait SynchronizedMap[A,B] that synchronizes the Map function of the class into which it is mixed in.

Mixins provide the flexibility to add behaviors to existing abstractions through implementation inheritance without some of the drawbacks of existing mainstream languages as discussed above. Unlike CLOS mixins, Scala mixins do not support chaining of methods without a context. The above mixin SynchronizedGet needs to inherit from Map in order to have invocation of super in the overridden method. This takes away some of the flexibility and makes the mixin reusable only in the context of the abstraction that it inherits from. However, like CLOS, Scala mixins are also based on the linearization technique that allows users the flexibility to manipulate the order in which the behavior chains get invoked.

Overall, I think mixins are a useful feature to have in your language and mixins in Scala offer a better way to use implementation inheritance for code reuse than Java.