A reading of Extensibility for the Masses by Mark Seemann
A paper read and translated to C#.
When I have the time (and I do make this a priority) I set aside an hour every day to study. Lately I've been using these time slots to read and reproduce the code in the 2012 paper "Extensibility for the Masses. Practical Extensibility with Object Algebras" by Bruno C. d. S. Oliveira and William R. Cook. As is often common with academic papers, they don't have a single, authoritative address on the internet. You can find the paper in various places. I've used a copy hosted by University of Texas, which is the institution with which William R. Cook is associated.
While the example code in the paper is in Java, the authors claim that it translates easily to C#. I decided to give this a try, and found it to be true.
Git repository #
From the beginning I created a Git repository with an eye to publishing it in case anyone was interested in looking over my shoulder. Not only can you see the 'final' translation, but you can also follow along with each commit.
I committed each time I had something that seemed to work. When I struggled to understand how to interpret some of the code, I left detailed commit messages describing my doubts, and explaining why I had chosen to interpret things in a particular way.
Along the way I also added automated tests, because I found that the paper lacked examples. Those tests represent my own interpretation of the code in the paper, and how one is supposed to use it. In total, I wrote 75 test cases.
Help from one of the authors #
At one time I hit a snag that I couldn't readily resolve. After searching the web in vain, I posted a question on Stack Overflow. After a few days, I got an answer from Bruno C. d. S. Oliveira, one of the authors of the paper!
It turns out that some of my confusion stemmed from an otherwise inconsequential error in the paper. We shouldn't be shocked that an academic paper contains errors. One of many things I learned from reading Charles Petzold's excellent book The Annotated Turing was that later researchers found several errors in Turing's 1936 paper, but none that changed the overall conclusion. So it seems to be here as well. There's at least one confirmed error (and another one that I only suspect), but it's inconsequential and easily corrected.
It does, however, raise a point about scientific papers in general: Even if they're peer-reviewed they may contain errors. I'm much in favour of scientific knowledge, but also sceptical about some claims about computer science and software engineering.
Readability #
The paper's title claims to give extensibility to the masses, but will 'the masses' be able to read the paper? As papers go, I found this one quite readable. While other papers present their examples in Haskell, this one uses Java. If you're comfortable with Java (or C#), you should be able to follow the code examples (or my C# translation).
You won't entirely escape Greek letters or other abstruse nomenclature. This is, after all, an academic paper, so it can't be lucid all the way through. There's a section called Algebraic Signatures, F-Algebras, and Church Encodings that is definitely not for 'the masses'. I understand enough about F-algebras and Church encodings to follow the outline of this section, but I didn't find it helpful.
If you're interested in the overall article, but don't know what these words mean, I suggest you skim those parts and pay as much attention to the details as when Geordi La Forge spews technobabble. In other words, I think you can follow the rest of the article just was well, even if ChurchΣ = ∀A.(T1 → A) × ... × (Tn → A) → A makes no sense to you.
Conclusion #
Does the paper deliver on its promise? Yes and no. Formally, I think that it does. In the beginning, it establishes some criteria for a successful solution, and as far as I can tell, it can check off all of them.
It's also true that the proposed solution requires only intermediary language features. Generics and inheritance, as they're available in C# and Java, is all that's required.
On the other hand, I don't find the paper's examples compelling. Few 'mass developers' are tasked with implementing a simple expression-based language. I can't shake the feeling that most of what the paper accomplishes could be handled with tasty application of composition and the Adapter pattern.
Still, I'll keep this paper in mind if I ever have to publish a reusable and extensible, type-safe software library.
Comments
I was intrigued by the paper's abstract, but then it turned out it's just about implementing Oleg Kiselyov's final (typed, tagless) encoding in plain boring Java/C# — the most surprising thing is that it doesn't really mention Kiselyov's work which predates this paper by 3-4 years. And Kiselyov in his writings moslty used really basic Haskell features so translating it to Java/C# is pretty straightforward, I actually did with it the last Autumn, toying with the idea, so I feel this paper could very well have been a (small) blog post, really. Anyway, let's talk about the proposed solution itself.
And the solution is actually pretty ingenious! The conventional approach to representing AST and writing interpreters (in broad sense) for it is to represent AST as a tree of objects, and interpret it by walking this tree over, doing the work in the process. The problem is that to add a new kind of node to AST you need to patch all existing intepreters, and writing an interpreter involves either manual dynamic dispatch on the node types in the interpreter's code, or trying to shift it onto the nodes itself somehow (cf. Visitor pattern).
The proposed solution neatly side steps the whole problem of representing an AST by simply not representing it as a piece of data at all, it instead interprets a (would-be) AST right at the moment of the construction. And so the interpreters — instead of being written as vistors — are written as builders that build the resulting value.
As I said, it's very ingenious but it is also, sadly, largely pointless. You see, it all largely started with the Haskell programmers trying to make ASTs more statically typed to get rid of as many runtime checks and "this case is impossible" in switches in the interpreters: you have to check that e.g. the
if's condition (which is usually just a plainExpr) must evaluate to boolean, but if you make its type some sort ofExpr<BoolType&rt;, the Haskell's typechecker won't allow you to build a malformed AST in the first place! It led to introduction of GADTs, then to extending GADTs even further, and I guess at some point some people started feeling kinda uneasy about going this close to the full-blown dependent types, and so the tagless final encoding was born: as I said in the beginning, it uses very boring and straightforward Haskell features — parametric polymorphism and typeclasses — or, as they're more widely known, generics and interfaces. But then again, as it evolved, it too started require language extensions although not as radical as in previous cases, and at some point waded into the esoteric type-level meta-programming territory.So here's the pointless part: the initial goal was to push type-checking of the (mini-)language being implemented onto the Haskell's typechecker, and it makes implementing small, typed mini-languages that are essentially Haskell's subset very easy, but... if you program in Haskell, what do you need this toy of a language for? And do its types/semantics really align that well with Haskell's? If they don't, this whole ordeal becomes very difficult: imagine a language with three variables (
A,B, andC) that can hold either integers or booleans, constants, assignments, basic arithmetic and comparison operators,if-then-elsestatement andwhileloop. Trying to encode it in Haskell type-safely (so that variables would have consistent types after all branches/loops' ends) is pretty non-trivial, whether you use GADTs or the approach from the paper. I've seen a blogpost where this exact excercise was done, and it was done in Coq, with essential use of dependent typing.And trying to pull this off in a language like Java/C# with much more limited type-system is, I would argue, fundamentally misguided. Eric Lippert has summed it quite well in his "Wizards and warriors, part five":
Then, of course, there is a problem that in this approach, AST does not actually exist as an object: it's represented as a function/method. If the interpreter you write needs multiple passes over AST, I am afraid you'll have to materialize your AST and AFAIK you can't really fine-tune or optimize the representation of closures in Java/C#. Of course, if you don't need multiple passes, then this approach is perfectly fine, and in fact, that's actually how one-pass compilers are usually structured: the parser straight up calls the code-generating hooks, and when it's done, the code-gen is done.
And when it comes down to actual extensibility, that is, the case when a new node type is added to AST, this approach really doesn't win much compared to conventional visitors: ideally, since interfaces should be immutable, such addition means that a new visitor interface is declared (an extension of the old one) which can be implemented by inheriting from the old interpreter, or by Adapting it — just the same that would be done in the proposed approach.
So, my conclusion: this paper tries to solve the problem of AST representation/interpretation by telling us to essentially write one-pass compilers, in the name of not writing semantic checking code for AST ourselves but instead of shifting it onto the shoulders of Java/C# type checker. No, sorry, but that's not a solution to the actual problem.