Saturday, January 19, 2013

Inheriting Class


I wanted to share a nice example of class hierarchy inheritance. Regular readers of this blog are no doubt familiar with the notion of virtual classes and class hierarchy inheritance. For those who aren’t, I’ll recap. Class hierarchy inheritance is exactly what it sounds like: the ability to inherit from an entire class hierarchy rather than a single class.   

Nested classes, as originally conceived in Beta, were treated as dynamically bound properties of instances, just like methods. If you do that, overriding classes (aka virtual classes) is an automatic consequence of nested classes.  If you miss this crucial point, you can easily end up with nested-classes design that has a great deal of complexity and almost no benefits (cf. Java).

The notion of class hierarchy inheritance has been around for many years, but has not yet caught on in the mainstream.  It is supported in a few languages: Beta, gBeta, Newspeak and several research projects.

Tangent:  Apologies to any languages I’ve not explicitly mentioned. This is a blog, not a scientific paper, and exhaustive citations should not be expected.

The research on this topic has too often been focused on typechecking, under the rubric of family polymorphism.  Fortunately, one can make excellent use of class hierarchy inheritance without worrying about complicated type systems.

Note:  Virtual classes are distinct from virtual types.

To be honest, while class nesting has proven to be useful on a daily basis, class hierarchy inheritance occurs pretty rarely. The biggest advantage of late binding nested classes is not class hierarchy inheritance, but polymorphism over classes (acting as instance factories, ergo constructors), which promotes modularity.   

Nevertheless, class hierarchy inheritance can be very useful at times. And since it comes for free, we might as well use it.

A classic example in the research literature is extending a class Graph that has nested classes like  Node and Edge. In Newspeak this would look roughly like this:
class Graph () (
   class Node ...
   class Edge ...
)

One can introduce a new subclass of GraphWeightedGraph, modifying Edge to hold the weight etc.

class WeightedGraph = Graph ()(
   class Edge = super Edge ( | weight ::= 0. | ) ()
)

In WeightedGraph, the class Edge inherits from the class Edge in the superclass GraphWeightedGraph’s Edge adds a slot (aka field), weight, initially set to zero.  Overriding of classes works just like overriding methods, so all the code that WeightedGraph inherited from Graph continues to work, except all uses of Edge refer to the weighted subclass.

In this post, I wanted to mention another nice example - one that arose in practice. Some former colleagues had implemented an external DSL on top of Newspeak, and naturally wanted to provide the nice IDE experience of Newspeak for their DSL as well. In particular, the debugger needed to support the DSL.

For the most part, the debugger is independent of the exact source language it is displaying. The system picks up the source code for each executing method and highlights the current call. However, difficulties arise because some methods created by the DSL implementation are synthetic. At run time, these methods have corresponding stack frames which should never be displayed. We need a small tweak to the debugger UI, so that these synthetic frames are filtered out.

The Newspeak debugger UI is implemented via a Newspeak module (a top level class) that contains classes responsible for the UI of the debugger, which in turn handles the UI of individual stack frames and of a stack as a whole. The debugger uses the Hopscotch UI framework; I’ll summarize salient characteristics here. Hopscotch applications consist of a presenter (the view of MVC), a subject of the presentation (roughly what some refer to as a ViewModel in MVVM) and model (a name everyone agrees on).  And so, our UI includes a ThreadPresenter and a ThreadSubject (whose model is the underlying thread) and a  number of ActivationPresenters and ActivationSubjects (whose model is the context object representing an individual stackframe). The presenters and subjects listed above are all declared within the Debugger class, which is nested in the top-level class (aka module definition) Debugging.

All we need then, is a slight change to ThreadSubject so it knows how to filter out the synthetic frames from the list of frames.  One might be able to engineer this in a more conventional setting by subclassing ThreadSubject and relying on dependency injection to weave the new subclass into the existing framework - assuming we had the foresight and stamina to use a DI framework in the first place. We’d also need to rebuild our system with two copies of the debugger code, and in general be in for a world of pain.

Fortunately,  the Newspeak IDE is written in Newspeak and not in a mainstream language, so these situations are handled easily.  Dependencies that are external to a module are always explicit, and internal ones can always be overridden via inheritance.

So you subclass the Debugging module and override the ThreadSubject class so that it filters its list of activations.

class FilteredDebugging = Debugging () (
   class Debugger = super Debugger () (
      class ThreadSubject = super ThreadSubject () (
        ... code to filter activations ...
     )
   )
)

You can define FilteredDebugging in the context of your complete DSL application.  Or you could define it is a mixin, and just apply it to Debugging in the context of the DSL application.

No DI frameworks, no copied code, no plugin architecture that nobody can understand, and no need to have foreseen this circumstance in advance. It really is quite simple.