The expression problem, Scandinavian style

Erik Ernst, The expression problem, Scandinavian style. MASPEGHI 2004.

This paper explains how higher-order hierarchies can be used to handle the expression problem. The expression problem is concerned with extending both the set of data structures and the set of operations of a given abstract data type. A typical object-oriented design supports extending the set of data structures, and a typical functional design supports extending the set of operations, but it is hard to support both in a smooth manner. Higher-
order hierarchies is a feature of the highly unified, mixin-based, extension-oriented kind of inheritance which is available in the language gbeta, which is itself a language that was created by generalizing the language Beta.

MASPEGHI, in case you wonder, stands for MechAnisms for SPEcialization, Generalization and inHerItance. On the site you'll also find the presentation related to the paper. And oh, gbeta is here.

I wonder what the Scala guys have to say about all this...

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

gbeta and virtual classes

We discussed gbeta in a previous topic about a virtual class calculus developed by Erik Ernst and Klaus Osterman.


This is a refreshingly excellent paper! The solution is very intuitive, the exposition is very clear, up there with SPJ's work. I wish papers more were written like this: Here's the problem, here's an example of code that solves the problem using intuitive language constructs, and finally some discussion on theory. Too often, it's: Here's the problem, here are fifty pages of derivations, and finally a vague outline of how this might be applied in the real world.

The key detail here is that to compose a data structure extension with an operation extension, you need to create a third extension that defines the new operation for the new datatype. This way, the compiler can always verify that your program is sound is free of any data structures lacking operations, without any of that multimethod voodoo of determining which overload is the "best" match according to some obscure rules.