Summary
Description of Expression Families Problem: Expression Problem (extensible data types plus operations) plus preservation of distinct types, subtype relationships, maximize composability/decoupling. Two encodings: internal visitors (related to Church encodings of datatypes), external visitors (related to Parigot encodings of datatypes). Visitor methods factored into individual types/shapes, datatypes parametrized on shape of visitor via bounded type parameters. Variance annotations preserve subtypes between datatypes and visitors. Internal and external visitors demonstrated in turn using Scala. Evaluation of external visitors (expressiveness++, complexity++). Demonstration of component assembly. Comparison to multiple dispatch. Demonstration of Feature-Oriented Programming-like use case. Related work: extensible visitors + algebraic datatypes, multiple dispatch and open classes, generics, type classes and polymorphic variants, virtual types.
Comments
This is the first meaningful use of higher-kinded types that I’ve seen (not counting the fact that OO interfaces are basically higher-kinded types), which probably just demonstrates my lack of exposure to sophisticated type systems. I’m also not familiar with the literature on earlier attempted solutions to the expression problem, so this one looks surprisingly solid to me, but perhaps the earlier attempts looked just as solid and yet failed to sweep the nation for reasons unknown.
The internal visitors abstraction seem just barely tractable to programmers that are well versed in parametrized type systems. External visitors step pretty firmly over that line, and would probably not be usable without somehow hiding the machinery and just exposing the necessary knobs. There were at least three or four cases where I wasn’t sure if I was missing something or if the authors were making some sort of mistake in their examples. I may not be the best barometer, but one imagines that simple examples chosen specifically to explain the technique ought not to be fraught with such ambiguity.
I’d like to give it a whirl on Depot (which has a pretty classic expression problem) and see how neat and tidy everything turns out. We don’t strictly need the composability that this approach enables, but it might be nice just to split up FragmentVisitor using more than just well-placed comments. Of course, that’s currently written in Java, so I’d have to rewrite it in Scala. But hey, I’m an academic now, I should have plenty of time for these sorts of intellectual exercises.