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 Graph, WeightedGraph, 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 Graph. WeightedGraph’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.
If I understand correctly, nested classes in Beta are not necessary dynamic -- there are non-virtual and virtual classes, just like methods.
ReplyDeleteVirtual classes should work in any dynamically-typed (more strictly late-bound) language where classes are first-class values. Mainstream-ish Python and Ruby come to mind (and -ish-ish Lua), though I haven't seen that style used much.
Eugene:
ReplyDeleteYes, in Beta all patterns (whch encompass methods, classes, types) can be either virtual or not.
As for your second point: you can obtain a similar effect if you support first class classes, but it isn't quite the same. You need to support nested classes with appropriate scope rules, and you need the late binding to work for these nested classes without special effort on the part of the programmer. Otherwise it is just too difficult to work with.
These things don't hold in other languages, which is perhaps why you don't see virtual classes being used.
Gilad, this is sort of my point -- if you have first class classes there isn't much you can screw up to make virtual classes not work. E.g. in Python this works as expected:
ReplyDeleteclass Graph:
class Node:
...
class Edge:
...
...
def addEdge(self):
self.edges.append(self.Edge())
class WeightedGraph(Graph):
class Edge(Graph.Edge):
def __init__(self):
super().__init__()
self.weight = 0
Note the only caveat is using self.Edge instead of just Edge to refer to the class. This is the same as you access any other instance and class attributes. Just Edge will raise NameError, so it won't cause subtle bugs.
So, whatever the reason is for not using this style, it isn't the effort required to make this work.
In Ruby class names are constants, so similar code eagerly binds Edge to Graph::Edge. One can explicitly do late binding, and maybe even some metaclass magic to use late binding by default.
I suspect that to solve the problem with Debugger most rubyist would extend IDE classes in-place, rather than creating a parallel hierarchy and making IDE use it.
Eugene:
ReplyDeleteOn the contrary, there is plenty one can screw up. First, you have to have nested classes in the first place. Having first class classes does not imply that.
Next, you need to have the correct scope rules. As you note, in Ruby the class Edge will be statically bound, so that means that one needs to plan ahead for this to work.
In Python, if you did not plan ahead, you'd probably write Graph.Edge explicitly - again preventing subclasses from overriding Edge as desired.
The same issue comes up in Scala with the Cake pattern. You must ensure all your instances get created via a factory method you can override.
Also, if Graph defines subclasses of Edge, these also need to have their superclass reference be late bound.
Another issue is that nested classes need convenient access to the enclosing instance. I seem to recall that doesn't work in Python by default either.
I'm not saying you can't do it - you can get Python to do almost anything as long as you don't need it to be fast. I'm saying it does not work smoothly out of the box. Which (at least to me) explains why it doesn't get used as much.
Gilad:
ReplyDeleteI think our disagreement is whether support for virtual classes means that they are reasonably easy to use, or that everything you write effectively uses virtual classes.
If you're prepared to write code in a certain way to use virtual classes, first-class and late binding are probably all you need.
If there's no syntax to declare a nested class, one can declare it at top level and assign to a class or instance attribute. Doing this also works around name lookup in Ruby (there are may be better ways of doing this in Ruby, I'm not an expert).
In Python, if one uses a nested class at all, which is not common, I can't think of a reason to use Graph.Edge instead of self.Edge. The latter is shorter, faster and more extensible. I suspect the former is mostly used by people coming from static languages.
Python indeed doesn't provide implicit reference to the outer class. If needed, one has to pass self explicitly. I think this is actually better than implicit reference. E.g. in the Graph example one likely doesn't need all nodes and edges to point back to the graph.
Good point on subclasses of Edge defined in the base Graph. In Python one would need to manually redefine those in subclasses of Graph to (possibly empty) derivations of both base subclass and derived edge, e.g.
class Graph:
class Edge:
...
class SubEdge(Edge):
...
class WGraph(Graph):
class Edge(Graph.Edge):
...
class SubEdge(Graph.SubEdge, Edge):
pass
How is this handled in NewSpeak?
Interestingly, in Scala the use of virtual classes seems to be much more widespread that in Python, even though it requires more effort to make it work. My guess is that this is because many Scala programmers come from Java, who find virtual classes a simpler way to do Dependency Injectoin (compared with Java frameworks). Python and Ruby programmers often would often use monkey patching to solve similar problems.
Eugene:
ReplyDeleteI think we understand each other pretty well now, yes.
To answer your question, in Newspeak (note the spelling) all names are late bound, including references to superclasses. So everything just works (tm). I believe that is critical to fully support class hierarchy inheritance.
Your point about lexical scoping is interesting. Most non-academic examples take advantage of the lexical scoping pervasively. Overall it is a huge win.
It is true that you run some risk of memory leaks, but this is arguably an optimization issue.
Scala does not really have virtual classes, but the cake pattern is widely used there, and it leverages nested classes and mixin composition to come quite close.
Gilad:
ReplyDeleteI agree that Newspeak model is quite nice. I presume it relies on the implicit reference to the outer module, and translates name lookups into attribute lookups on that reference.
I believe making outer class a part of nested class's scope is somewhat controversial. E.g. it's not copied in C#, even though it copied many quirks.
If I understand correctly, Scala will have true virtual classes any day now(tm). In the meantime, it has virtual types with bounds, inner classes and self type annotation, which gets you pretty close: http://www.scala-lang.org/node/124
Eugene:
ReplyDeleteYes, the Newspeak implementation defines an accessor method for every nested class as you describe.
As for lexical scoping of nested classes - I confess I am not concerned with other's opinion. In the case of C#, it was probably clear that the Java nested class model was unattractive. Unless you replace it with full fledged virtual classes, you probably don't want to pay the price of lexically nested classes (though it is quite similar to what one does with closures). By the same token, if you don't have virtual classes, maybe nested classes are not worthwhile in the first place.
Of course, that depends on what other features you have available,as Scala shows.
I'd strengthen your comment about type checking, Gilad: if you try to type check virtual classes, you end up wanting to make the virtual classes very restrictive, thus losing much of the benefit. Virtual classes and type checking are in considerable tension.
ReplyDeleteAlso agreed about the overemphasis on type checking in PL research. Conceptual analysis matters, but it's hard to do, and it's even harder for a paper committee to review it.
I last looked into virtual classes as part of GWT and JS' (the efforts tended to go in tandem). Allow me to add to the motivation you provide. A real problem faced by Google engineers is to develop code bases that run on multiple platforms (web browsers, App engine, Windows machines) and share most of the code. The challenge is to figure out how to swap out the non-shared code on the appropriate platform. While you can use factories and interfaces in Java, it is conceptually cleaner if you can replace classes rather than subclass them. More prosaically, this comes up all the time in regression testing; how many times have we all written an interface and a factory just so that we could stub something out for unit testing?
I found type checking virtual classes to be problematic, despite having delved into a fair amount of prior work on the subject. From what I recall, you end up wanting to have *class override* as a distinct concept from *subclassing*, and for override to be much more restrictive. Unlike with subclassing, you can't refine the type signature of a method from the class being overridden. In fact, even *adding* a new method is tricky; you have to be very careful about method dispatch for it to work.
To see where the challenges come from, imagine class Node having both an override and a subclass. Let's call these classes Node, Node', and LocalizedNode, respectively. Think about what virtual classes mean: at run time, Node' should, in the right circumstances, completely replace class Node. That "replacement" includes replacing the base class of LocalizedNode!
That much is already unsettling. In OO type checking, you must verify that a subclass conforms to its superclass. How do you do this if you can't see the real superclass?
To complete the trap, imagine Node has a method "name" that returns a String. Node' overrides this and--against my rules--returns type AsciiString, because its names only have 7-bit characters in them. LocalizedNode, meanwhile, overrides the name method to look up names in a translation dictionary, so it's very much using Unicode strings. Now imagine calling "name" on a variable of static type Node'. Statically, you expect to get an AsciiString back. However, at run time, this variable might hold a LocalizedNode, in which case you'll get a String. Boom.
Given all this, if you want type checking, then virtual classes are in the research frontier. One reasonable response is to ditch type checking and write code the way you like. Another approach is to explore alternatives to virtual classes. One possible alternative is to look into "coloring", as in Colored FJ.
Hi Lex,
ReplyDeleteGreat comments. Having spent too much of my life on types, I decided I would not allow them to constrain Newspeak's design or usage.
I have though a bit about how to typecheck it though. One possibility is, like Dart, to abandon soundness and treat typechecking as a helpful heuristic.
Another tack is to do concrete type inference on the ready to deploy application, where we can pin down all the classes involved. You'd know more about how to do that than me.
Your examples of coding problems are also spot on. Newspeak handles all these well - not only (o reven mainly) using class hierarchy inheritance. The fact that all modules are first class and parametric, and that the platform itself is a first class object, eliminate the need for DI frameworks and make sure you never get stuck.
Lex:
ReplyDelete"That much is already unsettling. In OO type checking, you must verify that a subclass conforms to its superclass. How do you do this if you can't see the real superclass?"
But as I can see you can know when if some class was overriden on other hieratchy and typecheck as if Node' is a Node type. So in this cases we need to do several independent typechecks - one for case where the LocalizedNode is a subclass of Node and one for the case LocalizedNode is a subclass of Node'. So in case "Node' overrides this and--against my rules--returns type AsciiString" the typecheck should fail as LocalizedNode couldn't subclass Node'. I suspect that problem with this is that we make system more fragile as you grow number dependencies but in general it doesn't differ much with single inheritance as you also contained in what you can change in superclass if you don't want to break existing subclasses.
That's true, Aliaksandr, and it's one of the suggestions Gilad made. If you don't insist on *separately compiled* type checking, then it seems like the compiler knows what it needs to do the appropriate checks.
ReplyDeleteI'm not sure exactly how it would work, but it seems doable.
Hey Gilad, if you ever get a chance, check out my latest onward paper. There I introduce something like "extend on need" in an OO trait system, where rather than construct the right object from day one, traits are added to the object as they are needed. So say you have a Button object, but a Button in a Canvas supports the "SetPosition" method. You merely call "SetPosition", the object extends the "WidgetInCanvas" trait, and the parent of button object must already extend or be made to extend the "Canvas" trait (if the parent cannot extend Canvas, then there is a type error). Same result as virtual classes but coming from a completely different direction. Of course, there are problems with type constraint propagation and...what if the trait you want to add has abstract method or constructor argument requirements.
ReplyDeleteScala's cake pattern is incredibly non-modular (no separate compilation, everything depends on everything), which is why I ported Jiazzi's open class pattern to Scala while I was writing code there (OOPSLA 2001, the open class pattern is simply a way of doing layered class hierarchy refinement using units and mixins, you might remember?).
Hi Sean,
ReplyDeleteThanks for the pointer. I downloaded the paper and will read it by Onward (hopefully much sooner).
The cake pattern is simply mixin composition of mixins with nested classes, no? The use of inheritance as a modularity mechanism was a big part of my thesis work. Combining that with nesting gives you the cake pattern, and I discussed it (not under that name) under future work 21 years ago, noting that typechecking was a big problem.
Newspeak relies much less on that pattern for its modularity (being more Unit like if you will), but still I don't see the cake pattern as "incredibly non-modular".
Any use of inheritance makes clients subject to breakage when conflicting elements are added higher in the inheritance graph, but other than that, I don't see a modularity problem. Module dependencies can be declared on an as needed basis. In Scala this is done by adjusting the type of self. This is analogous to declaring imports. In practice, it may be that the typechecker imposes too much a burden and one tends to over-import(basically importing all layers of the cake in each layer). I'm on record saying that types undermine modularity more than they help it (to much disaprobation :-) ) and this may be another example.
The way Martin used the cake pattern in Scalac, he basically had every trait's self type constrained to the type of the "final" trait that composes all of the other traits! So basically, in your inheritance graph, everything just depends on everything; e.g.
ReplyDeletetrait Foo0 { self : Foo3 => ... }
trait Foo1 : Foo0 { self : Foo3 => ... }
trait Foo2 : Foo0 { self : Foo3 => ... }
trait Foo3 : Foo1, Foo2 { ... }
Everyone depends on Foo3, so everyone depends on everyone. It is really not much better than partial classes in C#, which I would consider completely non-modular with respect to type checking.
With the open class pattern, separate type members (in Scala, or import in Jiazzi) are used to represent final "self" types, they are bound by the current refinement trait; e.g.,
trait FooContainer0 {
type Foo <: FooImpl;
trait FooImpl { def self : Foo; ... }
}
trait FooContainer1 : FooContainer0 {
override type Foo <: FooImpl;
trait FooImpl : FooContainer0.FooImpl { ... }
}
trait FooContainer2 : FooContainer0 {
override type Foo <: FooImpl;
trait FooImpl : FooContainer0.FooImpl { ... }
}
trait FooContainer3 : FooContainer1, FooContainer2 {
override type Foo = FooImpl;
trait FooImpl : FooContainer1.FooImpl, FooContainer2.FooImpl;
}
No one depends on the final FooContainer3, so we have much more flexibility in mixing and matching our refinements. We get modularity since everything doesn't depend on everything anymore. One of the big deals of the Jiazzi paper was just identifying and explaining this pattern. The Jiazzi paper also dealt with detecting name collisions in a modular way (with alpha renaming to avoid collisions between members used in different scopes, something we couldn't do in Scala).
I agree that types often do undermine modularity, but not in this case, where the modular solution is actually very easy.
Sean,
ReplyDeleteYes, this is what I was trying to convey. However, if the only reason for a more complex pattern is the typechecking, I find it hard to justify the types at all.
In Newspeak I've moved from the pure inheritance based approach I used in my thesis to relying mainly on parameterization of modules, with inheritance as an additional option when unanticipated changes are needed. Hence, as I said in my post, class hierarchy inheritance is not very frequent. It is still worth having in my view, so that you never get stuck.
Of course, this requires first class modules and is challenging to typecheck, as I discussed with Lex above. I think it's doable, but I don't feel typechecking should dictate how to handle modularity or delay/prevent us from building the systems we want. So I'm very comfortable with the Newspeak approach.
Gilad,
ReplyDeleteI've also changed my thinking since the Jiazzi paper or my time at EPFL, but I'm still a big believer in inheritance. If you take a look at my Onward paper, the focus is not on type checking but on code completion, which is the really important semantic feedback we need for using today's humongous libraries. Ask not what your code can do for your types, but what your types can do for your code as I call it.
I find the ability to reason about an entire object graph, which is what class hierarchy inheritance really gives you, to be very powerful when it comes to suggesting code completion options, along with some trait extension inference to list what you could call if only some object extended some trait (which is why I've flipped my emphasis from checking to inference).
Gilad, you earlier said that imports in scala were the path of least resistance. But I don't see the alternative. Is it type memebers? Anyway how we can completely eliminate imports in a static type system? Should we take the dependencies definitions out of the language as a special metadata to a compiler? So we can achieve more modularity at the compile time. In this model a given module could be recompiled and typechecked in different context without source code modifications (only compiler metadata modifications which take global namespace out of language).
ReplyDeleteAliaksandr,
ReplyDeleteDefinitely not type members! But class members, certainly. Then, as you suggest, type information is just metadata, and typechecking is performed by tools outside the compiler. You can use one during library development that gives an approximation based on limited knowledge, and a different analysis when a complete application is ready, where you can give a fully accurate analysis.
Someday, when I run out of things to do (or the right volunteer or student appears) we'll try this out in Newspeak.
This approach also deals with the absence of a global namespace in Newspeak. The typechecker can look at the IDE namespace as a whole, even though the Newspeak modules can't.
Sean:
ReplyDeleteLove the slogan!