mmmodularity!

» by Scott Kilpatrick

Today in our reading group we discussed William’s essay “On Understanding Data Abstraction, Revisited” (2009) and Odersky’s “Independently Extensible Solutions to the Expression Problem” (2005). Both papers discuss the expression problem to an extent, which is also a key subject of my research.

In his paper, Odersky gives a solution to the expression problem in Scala, the marvelous language that I adore so much. He highlights some of the key criteria for the problem, among them the independent extensibility principle, the ability to compose two independent extensions into a single module. This point hadn’t occurred to me before; it seems to suggest that you need some sort of mixin facility in your language, something he uses in his Scala solution.

The only problem I had with this paper — and it’s a big one — is how esoteric that solution is! He describes two dual frameworks for expressing the data and operation extension dimensions, and they both involve a “deep mixin” that complicate the code quite a bit. If this is such a fundamental issue, then it really needs some syntactic sugar. Why require programmers to follow a strict pattern outside the checkable bounds of the language if it’s so common and useful? This question is exactly what motivated me to seek an alternative way to express the Fortress library code that didn’t involve the self type idiom as in:

trait Eq[\T extends Eq[\T\]\] ... end

I had read William’s essay before, but I think I add a new layer to the onion of my head each time I read it; new issues about ADTs and objects seem to click each time. Today, mostly due to our visitor Manuel Serrano, the relevance of multimethods (i.e. multiple dynamic dispatch in Fortress) to the expression problem became apparent.

For example, in Java you commonly use the Visitor pattern to implement operations over [effectively] an algebraic data type. This pattern uses double dispatch: a node of class N has an `accept` method that takes in a Visitor object `v` and `N.accept` calls `v.forCaseN(this)` to perform the operation. Double dispatch is necessary because if we just wrote an overloaded `visit` method in the visitor and called `v.visit(node)`, the static dispatch of Java will dispatch to the code for the static type of the argument `node`, rather than its actual runtime type. In Fortress, it would indeed dispatch to the right code.