Multi-level modeling: what, why and how

One of the arguably-classical problems of language engineering is literal notation. Basically, as soon as you can refer to (/name) types, you’d also want to be able to instantiate those types. As it so often happens, the nomer “classical problem” does not imply that is has been solved to some degree of satisfaction. Just look at Java which still lacks a good literal syntax for object and collection instantiation, even with a library like Google Guava. Only fairly recently have more main stream GPLs emerged which happened to have syntactically nice object and collection literals.

But in this blog I only will talk about multi-level modeling, which can be informally defined as being able to model “things” and to then also be able to model instances of those “things”. The multi-level aspect comes from the fact that instances of “things” live one meta level down from the “things” themselves. I will only consider 2-level modeling, i.e. we only “descend” one meta level. Arbitrarily-deeply nested multi-level modeling is certainly possible but is also a magnitude more difficult and for the purposes of our exposé not that relevant.

As an example, consider the archetypical data modeling DSL in which you can model entities having named features: attributes with a data type or references to other entities. It’s often handy to be able to instantiate those entities, e.g. as initialisation or test data, alongside the definition. (Admittedly, this particular example will only really start to liven up when you start referencing those entities in business logic.) This is entirely analogous to the GPL case. For an actual example, consider the following grammar of an Xtext implementation of this DSL.

Entity: 'entity' name=ID '{'
          features+=Feature*
        '}';

Feature: Attribute | Reference;

Attribute: name=ID ':' dataType=DataType;
enum DataType: string | integer;

Reference: name=ID '->' entity=[Entity];

One way to do provide some multi-level modeling capabilities is to include a concept EntityInstance in the abstract syntax, pointing to an Entity and containing FeatureValues which allow the user to put in literals or instances for each of the features. For the given Xtext example, this looks as follows:

EntityInstance:
  'instance-of' entity=[Entity] '{'
    values+=FeatureValue*
  '}';

FeatureValue: feature=[Feature] '=' value=Literal;

Literal:          AttributeLiteral | EntityInstance;
AttributeLiteral: StringLiteral | IntegerLiteral;
StringLiteral:    string=STRING;
IntegerLiteral:   integer=INT;

The main drawbacks to this approach are:

• It provides one generic (i.e., uncustomisable) concrete syntax for literals.
• It requires quite some constraints to get this to work correctly.

In our simple case, this last point boils down to:

1. feature must be one of parent(EntityInstance).entity.features

2. type(value) must match type of feature

3. every feature may only receive one value

The implementation of the scoping (constraint 1) and the validations (constraints 2 and 3) is not too problematic, but this language happens to be tiny. In general, an implementation of a type system, scoping, validations, content assist, etc. tends to be superlinear in the grammar’s size, so we can only expect this to get worse.

Wouldn’t it be nicer if each occurrence of Entity would automagically and dynamically be transformed into a concept in the abstract syntax? In our case, if we start with

entity MarkdownDialect {
  ^name : string
  ^author : string
}

then this would be expanded into

MarkdownDialect:
  'markdown-dialect' '{'
      ('name' '=' name=STRING)
    & ('author' '=' authorName=STRING)
  '}';

We see two challenges with this: both the abstract syntax/meta model as well as the concrete syntax have to be expanded on-the-fly. The concrete syntax is by far the biggest problem. For a textual (i.e., parsed) situation it is difficult as it would mean extending the grammar according to some user-defined scheme and re-generating the parser and other artefacts. It’s not impossible as e.g. SugarJ proves, but it’s not exactly mainstream. For projectional editing, it tends to be easier as the concrete syntax then is typically more fluid and described in terms of simple templates, instead of grammars.

But to do this, we will need to be able to transform relevant parts of the DSL prose into “dynamic parts” of the abstract + concrete syntax. This is a matter of a fairly simple transformations -one for abstract, one for concrete- provided we don’t introduce the chance of infinite recursion. However, there’s a bit of a challenge with regards to the dynamic nature of the syntaxes: if entities are changed/removed, the corresponding instances become invalid. This means that the editor must be aware -at least to some extent- of the fact that this might happen and consequently shouldn’t break.

Ambiguitiy in Xtext grammars – part 2

In this continuation of the previous instalment, we’re going to take an ambiguous grammar and resolve its ambiguity.

As an example, consider the situation that we have a (arguably slightly stupid) language involving expressions and statements, two of which are variable declaration and assignment. (Let’s assume that all other statements start off by consuming an appropriate keyword token.) So, the following is valid, Java-like syntax (SomeClass is the identifier of a class thingy defined elsewhere):

SomeClass.SomeInnerClass localVar := ...
localVar.intField := 42

Now, let’s implement a “naive” Xtext grammar fragment for this:

Variable: name=ID;

Statement: VariableDeclaration | Assignment;

VariableDeclaration: typeRef=ClassRef variable=Variable (':=' value=Expression)?;
ClassRef:            type=[Class] tail=FeatureRefTail?;

Assignment:     lhs=AssignableSite ':=' value=Expression;
AssignableSite: var=[VariableDeclaration] tail=FeatureRefTail?;

FeatureRefTail: '.' feature=[Feature] tail=FeatureRefTail?;

Here, Class and Feature are quite standard types that both have String-valued ‘name’ features and have corresponding syntax elsewhere. Expression references an expression sub language which is at least able to do integer literals. Note that a Variable is contained by a VariableDeclaration so you can refer to a variable without needing to refer to its declaration. (You can find this grammar on GitHub.)

Now, let’s run this through the Xtext generator:

error(211): ../nl.dslmeinte.xtext.ambiguity/src-gen/nl/dslmeinte/xtext/ambiguity/parser/antlr/internal/InternalMyPL.g:415:1: [fatal] rule ruleStatement has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
error(211): ../nl.dslmeinte.xtext.ambiguity.ui/src-gen/nl/dslmeinte/xtext/ambiguity/ui/contentassist/antlr/internal/InternalMyPL.g:472:1: [fatal] rule rule__Statement__Alternatives has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

Even though Xtext itself doesn’t warn us about any problem (upfront), ANTLR spits out two errors back at us, and flat-out refuses to generate a parser after which the Xtext generation process crashes completely. The problem is best illustrated with the example DSL proza: its first line corresponds to a token stream ID-Keyword(‘.’)-ID-Keyword(‘:=’)-… while the second line corresponds to a stream ID-Keyword(‘.’)-ID-Keyword(‘:=’)-INT(42). (Note that whitespace is usually irrelevant and therefore, typically hidden which is Xtext’s default anyway.) Both lines start with consuming an ID token and because of the k=1 lookahead, the parser doesn’t stand a chance of distinguishing the variable declaration parser rule from the assignment one: only the fourth token reveals the distinction ID vs. Keyword(‘:=’). Note that since the nesting can be arbitrarily deep, any finite lookahead wouldn’t suffice meaning that we’d have to switch on the backtracking – one could think of this as setting k=∞.

To recap the situation with the token streams in comments:

SomeClass.SomeInnerClass localVar := ...  // ID-Keyword('.')-ID-[WS]-ID-[WS]-Keyword(':=')-[WS]-...
localVar.intField := 42                   // ID-Keyword('.')-ID-[WS]-Keyword(':=')-INT(42)

So, how do we deal with this ambiguity? One answer is to left-factor(ize) the grammar – as is already suggested by the ANTLR output. The trade-off is that our grammar becomes more complicated and we might have to do some heavy lifting outside of the grammar. But that is only to be expected since the grammar deals first and foremost with the syntax – what Xtext provides extra has everything to do with inference of the Ecore meta model (to which the EMF models conform) and only marginally so with semantics, by means of the default behavior for lazily-resolved cross-references.

Analogous to the left-factorized pattern for expression grammars, we’re going to implement the lookahead manually and rewrite nodes in the parsing tree to have the appropriate type. First note that our statements always begin with an ID token which either equals a variable name or a class name. After that any number of Keyword(‘.’)-ID sequences follow (we don’t care about whitespace, comments and such for now) until we either encounter an ID-Keyword(‘:=’) sequence or a Keyword(‘:=’) token, in both cases followed by an expression of sorts.

So, the idea is to first parse the ID-(Keyword(‘.’)-ID)* token sequence (which we’ll call the head) and then rewrite the tree according to whether we encounter an ID or the Keyword(‘:=’) token first. In Xtext, there’s a distinction between parser and type rules but only type rules give us code completion through scoping out-of-the-box, so we would like to use a type rule for the head. The head starts with either a reference to a Class or to a VariableDeclaration. Unfortunately, we can’t distinguish between these two at parse level so we have to have a common super type:

HeadTarget: Class | Variable;

However, due to the way that Xtext tries to “lift” or automatically Refactor identical features (having the same name, type, etc.), we need to introduce an additional type (that’s used nowhere) to suppress the corresponding errors:

Named: Class | Variable | Attribute;

Now we can make the Head grammar rule, reusing the FeatureRefTail rule we already had:

Head: target=[HeadTarget] tail=FeatureRefTail?;

And finally, the new grammar rule to handle both Assignment and VariableDeclaration:

AssignmentOrVariableDeclaration:
  Head (
    ({VariableDeclaration.assignableSite=current} name=ID ':=' (value=Expression)?) |
    ({Assignment.lhs=current} ':=' value=Expression)
  );

This works as follows:

1. Try to parse and construct a Head model element without actually creating a model element containing that Head;
2. When the first step is successful, determine whether we’re in a variable declaration or an assignment by looking at the next tokens;
3. Create a model element of the corresponding type and assign the Head instance to the right feature.

This is commonly referred to a “tree rewriting” but in the case of Xtext that’s actually slightly misleading, as no trees are rewritten. (In fact, Xtext produces models which are only trees as long as there are no unresolved references.)

To complete the example, we have to implement the scoping (which can also be found on GitHub). I’ve already covered that (with slightly different type names) in a previous blog post, but I will rephrase that here. Essentially, scoping separates into two parts:

1. Determining the features of the type of a variable. This type is specified by the typeRef feature (of type Head) of a VariableDeclaration. This is a actually a type system computation as the Head instance in the VariableDeclaration should already be completely resolved.
2. Determining the features of the previous element of a Head instance as possible values of the current FeatureRefTail.feature. For this we only want the “direct features” since we’re actively computing a scope.

(The scoping implementation uses a type SpecElement which is defined as a super type of Head and FeatureRefTail, but this is merely for convenience and type-safety of said implementation.)

In conclusion, we’ve rewritten an ambiguous grammar as an unambiguous one so we didn’t need to use backtracking with all its associated disadvantages: less performance, ANTLR reports no warnings about unreachable alternatives, “magic”, etc. We also found that this didn’t really complicate the grammar: it expresses intent and mechanism quite clearly and doesn’t feel like as kluge.

 

Ambiguities in Xtext grammars – part 1

In this blog in two instalments, I’ll discuss a few common sources of ambiguity in Xtext grammars in the hopes that it will allow the reader to recognise and fix these situations when they arise. This instalment constitutes the theoretical bit, while the next one will discuss a concrete example.

By default (at least: the default for the Itemis distro) Xtext relies on ANTLR to produce a so-called LL(k) parser, where LL(k) stands for “Left-to-right Leftmost-derivation with lookahead k“, where k is a positive integer or * = ∞ – see the Wikipedia article for more information (with a definite “academic” feel, so be warned). This means that grammars which are not LL(k) yield ANTLR errors during the Xtext generation stating that certain alternatives of a decision have been switched off. These are actual errors: the generated parser quite probably does not accept the full language as implied by the grammar (disregarding the fact that it’s not actually LL(k)) because the parser doesn’t follow certain decision paths to try and parse the input. We say that this grammar is ambiguous.

Xtext and “LL(1) conflicts”

Remember that first of all that the parser tokenizes its input into a linear stream of tokens (by default: keywords, IDs, STRINGs and all kinds of white space and comments) before it parses it into an EMF model (in the case of Xtext, but into an AST for general parsers). The problem is that an Xtext grammar specifies more than just the tokenizing and parsing behavior: it also specifies cross-references whose syntax often introduce an ambiguity on the parsing level by consuming the same token (ID, by default). The second parsing phase (still completely generated by ANTLR from an ANTLR grammar) only uses information on the token type, but doesn’t use additional information, such as a symbol table it may have built up. Such a strategy wouldn’t work with forward references anyway as the parser is essentially one-pass: references are resolved lazily only after parsing. This means that we have to beware especially of language constructs which start off by consuming the same token types (such as IDs) left-to-right but whose following syntax are totally different. This is a typical example of the FIRST/FIRST conflict type for a grammar; see also the Wikipedia article. The other non-recursive conflict type is FIRST/FOLLOW and is a tad more subtle, but it can be dealt with in the same way as the FIRST/FIRST conflict: by left-factorization.

Left-recursion

A grammar is left-recursive if (and only if) it contains a parser rule which can recursively call itself without first consuming a token. A left-recursive grammar is incompatible with LL(k) tech and Xtext or ANTLR will warn you about your grammar being left-recursive: Xtext detects left-recursion at the parser rule level while ANTLR detects left-recursion at the token level. Expression languages provide excellent examples of left-recursive grammars when trying to implement them in Xtext naively. For expression languages there’s a special pattern (ultimately also based on left-factorization) to deal both with the left-recursion, the precedence levels and creating a useable expression tree at the same time: see Sven’s oft-referenced blog and two of my blogs.

Backtracking

There are several ways to deal with ambiguities, one of which is enabling backtracking in the ANTLR parser generator. To understand what backtracking does, have a look at the documentation: essentially, it introduces a recovery strategy to try other alternatives from a parser rule, even if the input already matched with one alternative based on the specified lookahead. (See also this blog for some examples of the backtracking semantics and the difference with the grammar being LL(*).) I’m not enamored of backtracking because ANTLR analysis doesn’t report any errors anymore during analysis, so while it may resolve some ambiguities, it will not warn you about other/new ones. (It also tends to cause a bit of a performance hit, unless memoization is switched on using the memoize option.) In case you do really need backtracking, you should have a good language testing strategy in place with both positive and negative tests to check whether the parser accepts the intended language.

It’s my experience that very few DSLs actually require backtracking. In fact, if your DSL does really need it, chances are that you’re actually implementing something of a GPL which you should think about twice anyway. A quite common case requiring backtracking is when your language uses the same delimiter pair for two different semantics, e.g. expression grouping and type casting in most of the C-derived languages. Using different delimiters is an obvious strategy, but you might as well think hard about why you actually need to push something as unsafe as type casting on your DSL users.

Configuring the lookahead

To manually configure the lookahead used in the ANTLR grammar generated Xtext fragment (instead of relying on ANTLR’s defaults), you’ll have to do a bit of hacking: you have to create a suitable custom implementation of such a fragment, because MWE2 doesn’t have syntax for integer literals or revert to using MWE(1) to configure that. I’ll present a good illustration of this in the worked example in the next instalment which contains nested type specifications (or “path expressions”, as I called them in an earlier blog) which can have an arbitrary nesting depth. Using left-factorization we can rewrite the grammar to be LL(1), at the cost of some extra indirection structure in the meta model and some extra effort in implementing scoping and validation.

The Dangling Else-problem

A(nother) common source of ambiguity is known as The Dangling Else-problem (see the article for a definition) which is a “true” ambiguity in the sense that it doesn’t fall in one of the LL(1) conflicts categories described above. The only way to deal with that type of ambiguity in Xtext 1.0.x is to have a language (unit) test to check whether the dangling else ends up in the correct place – “usually”, that’s as else-part for the innermost if. Note that Xtext 2.0 has (some) support for syntactic predicates which allow you to deal with this declaratively in the grammar.

Next time, a concrete, worked example!

A Generic Application Language

This blog is a follow-up to a previous one with, as promised, some of my thoughts on a Generic Application Language (GAL). This is about what I personally would like to see in a modeling/programming language and its tooling, based on my experience actually building applications. As a consequence, the following will be extremely opinionated and in places downright rude. Deal with it or go away! 😉

I’ll start with pitching a few terms which I would have apply to the GAL. Some of these are purely oriented towards functionality, some are technical, some none of the previous. Here goes…

TL;DR: this explains what a language for application development and its IDE should look like

The tooling actually supports software development

Many IDEs are essentially not much more than glorified file tree navigators that open files in editors, with a lot of micro services tacked on top of it. This is great for configurability, but that also means that you actually have to configure it. It typically takes an inordinate amount of work to marry up your team’s/company’s workflow (version control, reviews, Agile, etc.) and the particular architecture of your code base to the IDE. So much even, that I’ve never seen it done to any degree of intimate satisfaction – wait, that sounds wrong, doesn’t it? Usually, this results in many manual actions and/or lengthy and cumbersome build cycles, hindering feedback/validation for the developer. (In all fairness, IDEs on the level of IDEA/IntelliJ provide reasonably smooth sailing these days.)

So, some features I want to see (roughly in that order):

1. Truly smooth integration (and configuration of, if/when required) with workflow, including Continuous Build and Deployment.
2. Live coding everywhere. Point to some code, give it some input, see what happens, debug it. No mucking about with making tests, providing all dependencies by hand  or running the entire application, setting a breakpoint and hoping for the best. Upgrade a live coding session to a test afterwards – unit or integrated, whatever you wanna call it; I don’t care.
3. Being able to reason about the code base within the tool itself. Run a query that’s language- and context-aware on your code base. Define code conventions and  architecture that way. Do impact analyses. Verify assumptions and invariants. Also: these things should be part of the code base itself, versioned and all.
4. Advanced and automatic Refactoring suggestions. If you have two sub classes with identical members, surely an IDE should be able to inform you of that and offer help? Recognise an Anti-Pattern as soon as it crops up. The possibilities are effectively endless, especially when you get to add your own wizard thingies.

Static typing

I know a lot of people experience pronounced localised vascular throbbing because of thinking dynamic languages are intrinsically way better than statically-typed ones, but I’m entirely willing to call those out as innophobic, pseudo-religiously insane bastards (m/f). Static typing helps. A lot. No amount of TDD can compensate for the lack of API discovery, content assist and avoiding stupid-but-hard-to-detect bugs – all things made possible by having a real type system. Studies show it, so get over it.

Sure, you need the following to be in place:

1. A healthy type system. This means reified generics. It does, however, not mean full recursiveness. Because that’s called Reflection-induced Hell in actual practice. Because someone will use it – probably yourself, thinking you’re smart. Same goes for meta programming: easy to abuse, hard to maintain by the rookie once the meta cowboy has moved on to fresher pastures, makes reasoning about your code base nigh impossible. ‘Nough said.
2. A good type inference engine. Reduce syntactic noise: no-one wants another Java. Scala and Xtend already show the way.
3. Polymorphism. Comes quite naturally for dynamic languages but is actually not so hard for statically-typed ones. (Xtend puts it on top of Java essentially effortlessly, e.g.)
4. Tags/tagged values/annotations. A lightweight, orthogonal way of tagging parts of your code and adorning them with extra info. Crucial to those LISP-like macros I’m going to be talking about later.

As long as you can keep the type system reasonable (Scala not being a good example), this is something that’s somewhat tedious and not trivial but also not frightfully difficult. Once you have these you can start thinking about using proof assist software such as Coq could help to reason about null safety, arguments validity, reachability and such. This ties in naturally with points 3 and 4 of the previous section.

Integration of front- and backend

Most applications today are Web applications. Typically, this means that front- and backend run on platforms that are technologically effectively disjoint: e.g. HTML5 vs. JEE. Equally typically, front- and backend are blissfully unaware of their respective details and any change to either requires patches up the other (1) by hand and (2) in several places.

To add insult to injury: if the architecture is set up with this in mind, the code on either end will look quite similar which begs the question why you can’t transpile from say, Java to JavaScript. (If it isn’t: well, good luck with the mess you got yourself in…) Also: tests are confined to their platforms, so these will not alert you to the fact that you’ve missed something.

Surely, in this day and age we can create a language that unifies both aspects using static typing. Google’s Web Toolkit got this, as does Safely-Typed JavaScript. Oh, this also means you could do tests that cross over that Great Divide.

Projectional editing

If you want to play around with a rectangular grid of characters, go play WordFeud™ (or Scrabble™). If you think free form text is the best thing since sliced bread, break out and dust off your grandfather’s type writer and bash out a novel.

In order to make my case, let’s consider changing exactly one character in the entire code base and assume that your entire application is not immediately breaking either because it doesn’t compile anymore or because it plainly blows up in your or someone else’s face when running it. Then, in decreasing order of likelihood:

1. You’re replacing whitespace with whitespace. This means you’re either a fascist or you’ve got a severe case of OCD. Go see either a criminal court or an episode of tBBT.
2. It’s inside a comment. Why is that comment there? And why isn’t it statically checked? In any case, probably endemic of a bigger problem.
3. You’re commenting out code. Planning to commit that, ‘guv?
4. It’s inside a text that’s purely for human consumption. Is it internationalised? Are you secretly writing a novel after all? If so, better go and search for that Underwood.
5. It’s inside a magic value. Hopefully you made that fact explicit. Otherwise, good luck with detecting and fixing the bugs that will inevitably result from that magic.
6. It’s inside dead code (provided the code even compiles). Why is it still there? Why didn’t your IDE alert you to that?
7. You’re just lucky. Well, for now at least. You’ll have some Heisenbugs later on, don’t worry.

So, why going to the trouble of give your developers the freedom to type in essentially random characters in random places, slapping them on the wrist through validation or trying to make up for the mess by means of syntax checking, highlighting, content assist, etc. after the fact? What more is an IDE than an application that visualises a code base and provides editability and other micro services with a defined behaviour on it? Is editor behaviour then not a matter of UX design? Even the command line guys are exploring that  direction.

(Another disadvantage of the textual format is that it leads to code layout wars – see also point 1 above. This applies less to Go and Python, and not at all to Brainf*ck, though.)

Oh, and you could even consider text to be a projection of the original code’s AST to some extent.

Once you’ve got projectional editing working as such, the following features are fairly easy to pull off (and although not impossible, extremely difficult to do for purely textual notations):

1. Multiple projections. The same AST can be visualised in different ways, with altering behavior of the micro services.
2. Great syntax and layout. Once you get started, there’s no end to how good you can make code look. Goodbye to mono-spaced fonts and CGA-era colour schemes.
3. Language embedding. Really difficult for the textual case – I know of only one tool that’s able to do that and it’s pretty much academic in every sense. Much, much easier for projectional editing. One especially important use case for this is LISP-like macros/templates. More on that below.
4. Context-aware editing. Got to put in a date here? Date picker! Same for colours, easy. This often obviates the need for language embedding.

Creating DSLs with macros/templates

I already alluded to this in a previous post, but this requires more explanation and examples. The general idea here is to be able to create code from code, in a way that allows you to gradually move from the level of abstraction that you want to the level that you (or the platform) need. (I guess you could also call this “desugaring”.) I’m going to talk about it in another post, because this post is long enough as it is and I think the idea deserves its own podium.

Functional programming

This is a bit of a no-brainer these days, luckily. Many GPLs are already firmly going that way, with 1st-class support for immutability, closures (I guess “lexically-scoped coroutines” to some), lazy evaluation, etc.. To me the most important take-aways from FP are (in that order!):

1. A good expression sub-language that also innately covers querying and comprehending of collections(/streams), is extremely powerful – essential, even.
2. Expressions are easier than statement (block)s. “Everything is an expression” is easy to achieve. Expressions can easily be upgraded to closures.
3. Pure functions are easy to reason about.
4. Pure functions are trivial to parallelise. In fact, it’s pretty much the only productive way to do actual concurrency/parallelism.

(Note that there’s a distinction between expressions and functions.) In fact, you can view an(y) application as a function of a stream of inputs to a stream of outputs/effects. This notion might not help matters when applying it to the application as a whole, but it certainly can when applied to individual layers of it. E.g., a UI is for the most part a function of application (its data) and client-specific state (which screen, etc.).

Things that are less important to me:

1. Monads. If you need them to make software development easier, you’re missing the point. That a lot of things are easier to reason about once you realise they’re monads, does not imply that you need to forcefully make everything a monad before they could be made to work. Use/apply them where it makes sense, don’t where it doesn’t. “But: side effects!”, you say. “Where?”, I say. It’s extremely useful to make side effects explicit. So much so that you should really consider creating a 1st-class language construct (with decent, non-leaky semantics) for that, instead of providing your developers with a cabinet full of Hello Kitty!™-themed bandage to plaster them over with.
2. While we’re at it, and pretty much for the same reasons: category theory. I know Erik Meijer does magical things with it, but face it: he’s pretty much the only guy that knows how to do that in real life. Again: use/apply it where useful, don’t where it doesn’t and certainly don’t make it a prerequisite for joining ye’olde Clubb.
3. Immutability as an opt-in concept. I see more value in explicitly specifying lifecycle and mutability only where it’s intrinsically relevant (e.g., in the data model). In expressions, immutability is the default and lifecycle irrelevant.
4. Whatever you can name as “super important, enabling concept that can only be found in Our Tool™”. (With the exception, of course, of anything intrinsic about the GAL ;)) I’ll be eternally puzzled by product descriptions along the lines of: “Our Tool™ allows business users to do X. That’s because we’ve built it according to vary-vague-and-academic-principle Y!” Huh? Interest in X and understanding of Y is mutually exclusive, so who should be enthused by this pitch, exactly? Exactly…

Reactiveness

Hey, there’s Erik Meijer again! 🙂 To me, reactiveness is several things at the same time:

• A philosophy.
• An extension of FP: everything is a stream of things and functions thereof.
• An implementation detail of FP: there’s an obvious mapping between pure functions on data to reactive streams of “delta events” on that data.

The latter two points especially pertain to modeling UIs – more on that in a later blog post (perhaps).

 

An incovenient dichotomy: specific vs. generic

Recently, I had a bit of a realisation: the LISPers of this world have a point.

But before explaining that, a question: how much of your application is really specific to your business domain? The meat of the realisation is that the answer typically is: not all that much.

This is because by the nature of applications and how they are embedded in their environments, they are not purely descriptions of the business domain but rather transformations of that domain interspersed with more “mundane” details like UX (design, style, layout, navigation, etc.), authentication, authorisation, validation, persistence, external interfaces, internationalisation, concurrency (these days: asynchrony), error handling, etc. So, however you measure the size of your application’s code base (lines of code, zipped megabytes, etc.), either a very small portion of it will actually represent your business domain authoritatively or the details of the business domain are duplicated and spread out across the entire code base.

Consider as an example a Web application to sell financial products. Such products typically come with a lot of details and business rules, such as applicability (essentially validations on who can buy a product), their actual semantics (i.e., a specification of what should happen when someone buys that product), etc., adorned with “stuff” that exists primarily for people to read. The majority of the Web application does not pertain to any of that, but is rather about guiding prospective customers in some way to the product they want/need, providing general information about the company, points of contact, etc. As for the financial products themselves: the semantics will only be executed on a mainframe backend, while the applicability would translate into some kind of questionnaire checking for that.

So, on the one hand modeling the financial products provides all kind of benefits since you can derive the questionnaire and semantics from the model. Having a DSL to do that modeling makes sense since each financial business domains typically use very specific concepts and jargon. On the other hand, creating a Web application is hardly domain-specific in any way: the number of concepts involved is quite large, but they hardly vary in essence over a broad range of applications. Of course, how these concepts are applied in a specific application should be quite restricted by means of a uniform/house style and an application architecture.

In my experience, it does not pay to create app-specific DSLs capturing this generic range of concepts. (*gasp* Did I just say: “Don’t build DSLs.”?! Yes, I did.) It is simply a lot of work: you have to determine which concepts to capture, taking into account possible extensions, changes to the technology stack, etc. You typically also need an underlying type system and powerful expressions sub-language. Then you need a generator or interpreter tying in with the underlying architecture, technology stack and application environment. This is not trivial stuff and certainly not for the general developer, even with the capabilities of modern language workbenches.

Instead, creating applications should be done through a generic application language which supports raising levels of abstractions essentially continuously. And this is where LISP comes in: not that LISP is this GAL (or should be), but we could, and should, be inspired by the concept of macros. (I say levels of abstraction, since I also realised that there is not one level to abstract over. Rather, at various points in your code there are various axes to abstract over.)

A lot of constructs in general purpose languages are essentially about raising that level of abstraction, or can be used in that way. E.g., (non-polymorphically called) methods/functions are just code blocks with a name to them, inheritance is another way to avoid duplicating code, etc. These constructs force you to raise the level of abstraction by reasoning from the GPL constructs towards the intended, or naturally-suited level of abstraction.

LISP-style macros, on the other hand, work in the opposite direction: they are effectively templates transforming some code into code that exhibits a lower level of abstraction. Provided that you can chain such transformations together to arrive at code that’s actually executable, you can vary the level of abstraction incrementally and essentially continuously. Note that I say “code”, not “data”: making a distinction there would force us to choose where data ends and where code starts – not only is that a hard topic, it’s also not relevant for our purposes!

To go back to our example: the financial products could be modeled as GAL code which is then transformed into parts of the Web application. You can view the modeling GAL code as an internal DSL. The GAL tooling could even help to expose this internal DSL as an external DSL.

So, is LISP this GAL? No. LISP is a very nice language but no amount of tooling is going to be able to general developer to become productive with it while also keeping the LISP community itself on board. In a next blog, I’ll try to say more about what this GAL and its tooling should look like.

In conclusion: specific vs. generic is a false dichotomy. Rather, we need to be able to raise levels of abstraction in a meaningful way, i.e. incrementally and essentially continuously. That way, we can leverage genericity while still embracing specificity.

 

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.

The practical value of category theory (and art)

After my presentation “A category-theoretic view of model-driven” (slides forthcoming through the conference web site) during this year’s Code Generation conference, I got the question what the practical value of category theory was. In the heat of the moment, I chanced upon an analogy with art which very soon found its way to Twitter as:

This got some retweets and also some responses to the tune of me being completely wrong. Although the above is what I said, my actual opinion on this is a bit more nuanced. (As an aside: Félienne was kind enough to write a live-blog post about my presentation.)

First of all, art has quite some practical value: it improves people’s lives in a myriad ways by triggering deeply-felt emotional responses. Category theory (or CT, in short) doesn’t quite work like that in general although for some of its practitioners it might come close. CT certainly has value in providing its practitioners a mental framework which guides them to the sort of abstractions that work really well in mathematics and, increasingly, in functional programming to think and reason more effectively.

What didn’t quite made it to the tweet was my assertion that in practice CT does not relieve you of the hard work. Or to put in another way: there’s no substitute for thought. Framing something in the CT language and framework doesn’t “magically” give you the answers for the questions you might have. It can certainly help in reaching those answers more efficiently and phrasing them (much) more elegantly – which is precisely what proper abstraction should achieve. But at the same time, once you have these answers, it’s perfectly possible to “desugar away” from the use of CT. At the end of the day, everyone has to consider his/her ROI on learning enough CT to be able to take this route.

For the same reason I have a problem with the tendency in certain circles to outright declare adequate knowledge of CT as a criterion for admittance to those circles. (I hinted somewhat obliquely and humorously to this in my presentation.) It’s an entirely artificial entry barrier with those enforcing it doing so for not entirely autarkic reasons.

In conclusion: yes, CT can certainly have practical value but it requires the right context and considerable upfront effort to achieve that and does not constitute a prerequisite.

Using Xtend with Google App Engine

I’ve been using Xtend extensively for well over a year – ever since it came out, basically.

I love it as a Java replacement that allows me to succinctly write down my intentions without my code getting bogged down in and cluttered with syntactic noise – so much so that my Xtend code is for a significant part organized as 1-liners. The fact that you actually have closures together with a decent syntax for those is brilliant. The two forms of polymorphic dispatch allow you to cut down on your OO hierarchy in a sensible manner. Other features like single-interface matching of closures and operator overloading are the proverbial icing on the cake. The few initial misgivings I had for the language have either been fixed or I’ve found sensible ways to work around them. Over 90% of all my JVM code is in Xtend these days, the rest mostly consisting of interfaces and enumerations.

One of the things I’ve been doing is working on my own startup: Más – domain modeling in the Cloud, made easy. I host that on Google App Engine so I’ve some experience of using Xtend in that context as well. Sven Efftinge recently wrote a blog on using Google Web Toolkit with Xtend. Using Xtend in the context of GWT requires a recent version of Xtend because of the extra demands that GWT makes on Java code (which is transpiled from Xtend code) and Java types in order to ensure it’s possible to transpile to JavaScript and objects are serializable. However, when just using Xtend on the backend of a Google App Engine, you don’t need a recent version. However, you do need the “unsign” a couple of Xtend-related JAR files because otherwise the hosted/deployed server will trip over the signing meta data in them.

To use Xtend in a Google Web Application, do the following:

1. After creating the Web Application project, create an Xtend class anywhere in the Java src/ folder.
2. Hover over the class name to see the available quickfixes. Alternatively, use the right mouse click menu on the corresponding error in the Problems view.
3. Invoke the “Add Xtend libs to classpath” quickfix by selecting it in the hover or by selecting the error in the Problems view, pressing Ctrl/Cmd 1 and clicking Finish.
4. At this point, I usually edit the .classpath file to have the xtend-gen/ Java source folder and Xtend library appear after the src/ folder and App Engine SDK library entry.
5. Locate the com.google.guava, org.eclipse.xtext.xbase.lib and org.eclipse.xtend.lib JAR files in the plugins/ folder of the Eclipse installation.
6. Unsign these (see below) and place the unsigned versions in the war/WEB-INF/lib/ folder of the Web Applcation project.

Now, you’re all set to use Xtend in a GAE project and deploy it to the hosted server. In another post, I’ll discuss the benefits of Xtend’s rich strings in this context.

Unsigning the Xtend libs

The following (Bourne) shell script (which kinda sucks because of the use of the cd commands) will strip a JAR file of its signing meta data and create a new JAR file which has the same file name but with ‘-unsigned’ postfixed before the extension. It takes one argument: the name of the JAR file without file extension (.jar).

#!/bin/sh
unzip $1.jar -d tmp_jar/
cd tmp_jar
rm META-INF/ECLIPSE_.*
cp MANIFEST.MF tmp_MANIFEST.MF
awk '/^$/ {next} match($0, "(^Name:)|(^SHA1-Digest:)") == 0 {print $0}' tmp_MANIFEST.MF > MANIFEST.MF
# TODO  remove empty lines (1st clause isn't working...)
rm tmp_MANIFEST.MF

zip -r ../$1-unsigned.jar .
cd ..
rm -rf tmp_jar/

# Run this for the following JARs (with version and qualifier):
#    com.google.guava
#    org.eclipse.xtend.lib
#    org.eclipse.xtext.xbase.lib

Note that using the signed Xtend libs (placing them directly in war/WEB-INF/lib/) isn’t a problem for the local development server, but it is for the (remote) hosted server. It took me a while initially to figure out that the cryptic, uninformative error message in the logs (available through the dashboard) actually mean that GAE has a problem with signed JARs.

And yes, I know the unsign shell script is kind-of ugly because of the use of the cd command, but hey: what gives…

In the trenches: MDSD as guerilla warfare

However much I would’ve liked for things to be different, adoption of MDSD is still quite cumbersome, even though it has been around for quite some time in different guises and various names. Particularly, the MDA variant may have caused more damage than brought goodwill because of its rigidity and reliance on UML which, frankly and paradoxically, is both unusably large and largely semantics-free at the same time.

Therefore, it’s “somewhat” unlikely that you’ll be able to ride the silver bullet train and introduce MDSD top-down as a project- or even company-wide approach to doing software. This means you’ll have to dig in and resort to guerilla tactics, so be prepared to have a lot of patience as well as suffer frustration, boredom and even a number of casualties – doing all this in the knowledge that if/when you succeed, you will have furthered the MDSD Cause and made the world a ever-so-slightly better place.

Remarkably, opposition to MDSD has -at least in my experience- equally come from both non-techies as well as techies alike but with very differing concerns. From the managers’ viewpoint, you’re introducing yet another “technology”, or more accurately: methodology, so you’ll have to convince them of the gains (e.g., increase of productivity, longer-term reliability) and placate them regarding the risks (e.g., ramp-up costs, specialty knowledge). That to be expected, as well entirely reasonable.

Your colleague developers, on the other hand, are a tougher crowd to convince and any manager or team/project lead worth his or her salt is going to take a team’s gut feeling into account when deciding on proclaiming yay or nay on adopting MDSD in a given project. What struck me, at first, as extremely odd is the reluctance of the “average developer” to use MDSD. This was at a point in my career that I still had to find out that most developers were much more interested in prolonging the usefulness of their current skill set than in acquiring new skills, and much less seeing that same skill set become much less valuable because of something that’s not a buzz word (which MDSD isn’t). From a personal economic viewpoint this makes imminent sense as it makes for a steady and predictable longer-term income.

“Unfortunately,” that’s not the way I work: I have a fair bit of Obsessive Compulsive Disorder which leaves me quite incapable of not continuously improving a code base and encourages me to find ever better ways of succinctly expressing intent in it. I stand by Ken Thompson’s quote: “One of my most productive days was throwing away 1000 lines of code.” In hindsight, it is no surprise that I immediately gravitated towards MDSD when I came to know it.

But enough about me: what would the Average Developer™ think about MDSD? As already mentioned: it can easily be perceived as a threat because adoption usually means that less of total developer time is spent on using an existing skill set (never mind that that skill set comes with dull, tedious and repetitive tasks!) which begs the question what the remainder of the developer time is spent on. The answer can be: on something which requires a new skill set or it is not spent at all because the work can be done in less hours which amounts to another blow to one’s job security.

The other reason that our AD doesn’t like MDSD is that they are, well…average, meaning that it’s probably a bit of leap for him/her to get used to it and especially to acquire some of the required skill set to actively participate in it. Meta modeling comes natural to some of us, but these people tend to occupy the far right of the bell curve of the normal distribution. So, MDSD is also a threat to one’s occupational pride and confidence.

A useful approach to convincing the AD that MDSD might hold some sway and can make life easier, is by “doing it from the inside out”: instead of converting the entire project to an MDSD approach, convert a small part of it, focusing on a low-hanging fruit which comes with a lot of daily pain for the developers involved. A fruit that usually hangs within grabbing range is the data model, together with all its derived details in the various application layers: DB schema, ORM configuration, DTOs, views, etc. It’s convenient that it’s already called a data model, so it’s not a big leap to formalize/”modelize” its description sufficiently, e.g. using a DSL, and to write a generator to generate the tedious bits of code.

It’s important to pick your battles intelligently: don’t try and subjugate entire regions of the existing code base to an MDSD regime, even if you already could with the current state-of-the-art of the model. This is for two reasons: any conversion will have impact on the project and have some unforeseen consequences, but more importantly, you’re effectively throwing away someone’s code and replacing it with generated code – most developers are uneasy with that and if you do this too harshly you will not gain traction for MDSD.

An important ingredient of guerilla tactic in general is to appease the local population: “The people are the key base to be secured and defended rather than territory won or enemy bodies counted”. For MDSD it’s no different which means it’s crucial to keep responsibility in the same place. As Daniel Pink explains, autonomy, mastery and purpose are crucial to anyone’s motivation. So, make the original developer of the replaced code responsible for the MDSD solution as well: show him/her how to change the model, the generator and (even) the DSL and demonstrate how this makes life easier.

Once small parts of a project are model-driven, you can stimulate growth in two directions: (1) “conquer” more areas of the project, and (2) glue parts together. E.g., if at first you’re only generate the DB schema from the data model, then start generating the DTOs/POJOs as well, after which you naturally can generate the ORM configuration as well. If you’ve also got a model for the backend services, you could now start writing down contracts for those services in terms of the data model.

Again, you’ll have to keep track of how your fellow programmers are doing, where you can help them with MDSD (and where you can’t), whether you can “hide” the ramp-up costs enough to not be considered a cost center, and whether they are adopting the MDSD way as their own.

A trick for speeding up Xtend building

I love Xtend and use it as much as possible. For code bases which are completely under my control, I use it for everything that’s not an interface or something that really needs to have inner classes and such.

As much as I love Xtend, the performance of the compilation (or “transpilation”) to Java source is not quite on the level of the JDK’s Java compiler. That’s quite impossible given the amount of effort that has gone into the Java compiler accumulated over the years and the fact that the team behind Xtend is only a few FTE (because they have to take care of Xtext as well). Nevertheless, things can get out of hand relatively quickly and leave you with a workspace which needs several minutes to fully build  and already tens of seconds for an incremental build, triggered by a change in one Xtend file.

This performance (or lack thereof) for incremental builds is usually caused by a lot of Xtend source  interdependencies. Xtend is an Xtext DSL and, as such, is aware of the fact that a change in on file can make it necessary for another file to be reconsidered for compilation as well. However, Xtend’s incremental build implementation is not (yet?) always capable of deciding when this is the case and when not, so it chooses to add all depending Xtend files to the build and so forth – a learned word for this is “transitive build behavior”.

A simple solution is to program against interfaces. You’ve probably already heard this as a best practice before and outside of the context of Xtend, so it already has merits outside of compiler performance. In essence, the trick is to extract a Java interface from an Xtend class, “demote” that Xtend class to an implementation of that interface and use dependency injection to inject an instance of the Xtend implementation class. This works because the Java interface “insulates” the implementation from its clients, so when you change the implementation, but not the interface, Xtend doesn’t trigger re-transpilation of Xtend client classes. Usually, only the Xtend implementation class is re-transpiled.

In the following I’ll assume that we’re running inside a Guice container, so that the Xtend class is never instantiated explicitly – this is typical for generators and model extensions, anyway. Perform the following steps:

1. Rename the Xtend class to reflect it’s the implementation class, by renaming both the file and the class declaration itself, without using the Rename Refactoring. This will break compilation for all the clients.
2. Find the transpiled Java class corresponding to the Xtend class in the xtend-gen/ folder. This is easiest through the Ctrl/Cmd-Shift-T (Open Type) short cut.
3. Invoke the Extract Interface Refactoring on that one and extract it into a Java interface in the same package, but with the original name of the Xtend class.
4. Have the Xtend implementation class implement the Java interface. Compilation should become unbroken at this point.
5. Add a Guice annotation to the Java interface:

   @com.google.inject.ImplementedBy(...class literal for the Xtext implementation class...)
   

Personally, I like to rename the Xtend implementation class to have the Impl postfix. If I have more Xtend classes together, I tend to bundle them up into a impl sub package.

Of course, every time the effective interface of the implementation class changes, you’ll have to adapt the corresponding interface as well – prompted by compilation errors popping up. I tend to apply this technique only as soon as the build times become a hindrance.