Tuesday, November 07, 2006

Flattening and class tables

Brief intro: a class table is (often) used when modelling OO languages to store the details of a class. Sometimes (I can't think of a paper off the top of my head) they store just the same information as is given syntactically in a class declaration. Sometimes (as is normally done with Traits and also in the Tribe paper by Clarke et al.) they do more than this: they store a flattened view of the classes. This means a class in the class table has all the methods and fields it has access to via inheritance. A class C with method m1() that extends a class D with method m2() would be represented in the class table as a method C with methods m1() and m2(). The inheritance hierarchy has been flattened.

The (uncovered) meat of this post: flattening is cool! First off I think it makes for slightly simpler formal systems, but more importantly it gives a formal defintion of the object model of a language.

A language's object model is the set of mechanisms (inheritance, trait composition, delegation, etc.) that allow a programmer to define objects and classes and their relationships. It is very often the most interesting part of a language. However, defining a language's object model is quite difficult. We generally resort to a core language that has a minimum of expressions but the important bits of the object model (for example Featherweight Java). Indeed we require such a language to prove type safety and other similar properties. However, the class table gives us a way to describe the object model without the baggage of expressions. The flattened classes are, in a way, the interface of a class - the set of methods and fields that can be called on an object of that class. The syntax of the language corresponds to an implementation - how the programmer can define which classes have which methods and fields in a succint and useful manner. The functions that do the flattening effectively describe the object model as a translation from the syntactic object model to its semantics (the flattened object model).

That isn't explained very well, but I hope it gives a glimmer of insight into why my formal systems will have flattened class tables in the future.