Object algebras in Xtend

I finally found/made some time to watch the InfoQ video shot during Tijs van der Storm‘s excellent presentation during the Dutch Joy of Coding conference 2014, on object algebras. Since Tijs uses Dart for his code and I’m a bit of an Xtend junkie, I couldn’t resist to port his code. Happily, this results in code that’s at least as short and readable as the Dart code, because of the use of Xtend-specific features.

Object algebras…

In my understanding, object algebras are a way to capture algebraic structures in object-oriented programming languages in a way that allows convenient extensibility in both the algebra (structure) itself as well as in the behavior/semantics of that algebra – at the same time, even.

Concretely, Tijs presents an example where he defines an initial algebra, consisting of only integer literals and + operations. This allows you to encode simple arithmetic expressions inside of the host programming language – i.e., as an internal DSL. Note that these expressions result in object trees (or ASTs, if you will). Also, they can be seen as an example of the Builder Pattern. For this initial algebra, Tijs provides the typical print and evaluation semantics. Next, he extends the algebra with multiplication and also provides the print and evaluation semantics for that.

All of this comes at a cost. In fact, two costs: a syntactical one and a combinatorial one. The syntactical cost is that “1 + 2” is encoded as “a.plus(a.lit(1), a.lit(2))” – at least in the Dart code example. Luckily, Xtend can help here – see below. The combinatorial cost (which seems to be intrinsic to object algebras) is that for every combination of algebra concept (i.c.: literal, plus operation, multiplication operation) and semantics (i.c.: print, evaluation) we need an individual class – although these can be anonymous if the language allows that.

Despite the drawbacks, object algebras do the proverbial trick in case you’re dealing with object trees/builders/ASTs in an object-oriented, statically-typed language and need extensibility, without needing to revert to the “mock extensibility” of the Visitor Pattern/double dispatch.

…in Xtend

…it looks like this. Go on, click the link – I’ll wait 🙂 Note that GitHub does not know about Xtend (yet?) so the syntax coloring is derived from Java and not entirely complete – most notably, the Xtend keywords def, override and extension are not marked as such.

To start with the biggest win, look at lines 80 and 142. Instead of the slightly verbose “a.plus(a.lit(1), a.lit(2))” you see “lit(1) + lit(2)”. This is achieved by marking the function argument of type ExpAlg/MulAlg with the extension keyword. This has the effect that the public members of ExpAlg/MulAlg are available to the function body without needing to dereference them as “a.”. In general, Xtend’s extension mechanism is really powerful especially when used on fields in combination with dependency injection. In my opinion, it’s much better than e.g. mucking about with Scala’s implicit magic, precisely because of the explicitness of Xtend’s extension.

Another win is the use of operator overloading so we can redefine the + and * operators in the context of ExpAlg/MulAlg, even usual the actual tokens: see lines 18 and 105. Further nice features are:

• The use of the @Data annotation on classes to promote these to Value Objects, with suitable getters, setters and constructors generated automatically. Unfortunately, the use of the @Data annotation does not play nice with anonymous classes which were introduced in Xtend 2.6. So in this case, the trade-off would be to have less explicit classes versus more code in each anonymous class. In the end, I chose to keep the code close to the Dart original.
• No semicolons 😉
• Parentheses are not required for no-args function calls such as constructor invocations; e.g., see lines 39, 45 and 90.
• Nice templating using decidedly non-Groovy syntax that is less likely to require escaping and also plays nice with indentation; see e.g. line 39.

All in all, even though I liked the Dart code, I like the Xtend version more.

Addendum: now with closures

As Tijs himself pointed out on Twitter, we can also use closures to do away with classes, whether they are explicit or anonymous depending on your choice of implementation language or style. This is because closures and objects are conceptually equivalent and concretely because the Xtend compiler does three things:

• It turns closures into anonymous classes.
• It tries to match the type of the closure to the target type, i.e.: it can coerce to any interface or abstract class which has declared only one abstract method. In our case that’s the print and eval methods of the respective interfaces.
• It declares all method arguments to be final to match the functional programming style. As a result, the parameters of the factory methods are effectively captured by the closure.

(Incidentally, I’ve made examples of this nature before.)

The resulting code can be found here. It completely does away with explicit and anonymous classes apart from the required factory classes, saving 40 lines of code in the process. (The problem with the @Data annotation naturally disappears with that as well.) Note that we have to make explicit that the closures take no explicit arguments, only arguments captured from the scope, by using the “[| ]” syntax (nothing before |) or else Xtend will infer an implicit argument of type Object – see e.g. line 31.

A slight drawback of the closure approach is that it not only seals the details (i.e., the properties’ values – this is a good thing) but also hides them and that it limits extensibility to behavior that can be expressed in exactly one method. E.g., to do introspection on the objects one has to define a new extension: see lines 124-. Note that this make good use of the @Data annotation after all: both the constructor and a useful toString method are generated.