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.

Abstraction sucks!

No, I’ve not gone mad: having obtained a Master’s Degree in Mathematics precludes me from saying such things in earnest. However, the title does seem to represent a sentiment that’s present throughout a large part of both the software developing community (especially, but not exclusively, including all the non-techie folks) and our community as a whole, which might be summed up as “abstraction means ‘more difficult’, right?“.

Wikipedia defines abstraction as “a process by which higher concepts are derived from the usage and classification of literal (“real” or “concrete”) concepts, first principles and/or other abstractions”. As a consequence, abstraction does not inherently add complexity to a situation; rather, it does quite the opposite: it reduces complexity (usually favoring the incidental part of that, thankfully) by condensing existing usage patterns into more compact wording which carries the same content and level of detail. So, when we do some Refactoring and reduce the overall size of a code base, chances are that we’re abstracting at the same time. Even when the code base grows in size, it might be because you’re introducing classes (e.g., through “Extract Interface”) which represent those higher concepts. In my own programming, I tend to search for usage patterns and other commonality which I can abstract/Refactor away so I can understand the domain better. The benefits for software creation of abstraction are: (1) gaining a better understanding of the domain as well as concepts for the ubiquitous language and (2) productivity gains through “doing more in less code” and more maintainable code, at that.

Now, it seems that there are 10 types of people: those who like abstraction and those who abhor it. That dichotomy seems to extend itself to the world of MDSD tools as well: on the one hand we have tools like Intentional, Xtext, MPS, Acceleo which allow you sculpt your modeling language (or in the case of Intentional: domain) to the n-th degree at the cost of meta-programmers’ hours, on the other hand there are tools like Mendix, BeInformed, Pega and all the BPMS, CASE, 4GL tools of old (and new) which come with their own pre-determined set of concepts and a lot out of the box-functionality (the semantics of those concepts plus a technical architecture) and which seems to have gained quite a bit of popularity, especially among the more business analysis-oriented folks. Having worked with some of these tools myself, I’m always struck by the inability of these tools to introduce new abstractions on top of the existing ones. You’re basically given the one modeling language and when you happen to see a usage pattern: well, you’d better make sure you stick to it. While I’ve reasoned earlier that architecture does have a place in modeling, I didn’t have this slightly mind-numbing variety in mind…

At the same time, there are arguments against abstraction which we’d better know in order to be able to understand why “the regular folks” like those fixed modeling language MDSD tools more than anything “us folks” care to cook up. The first one is that an abstraction has to be really, really good in order to be useful in practice. Joel Spolsky formulated the “Law of Leaky Abstractions” which says that however good your abstraction is, at some point in time you’ll going to have to know what’s going on “underneath”, i.e. the concepts the abstraction was derived from, in order to understand the abstraction itself. This is especially true in software where a minute leak can, and thus will, cause a bug which forces you to step down an abstraction level and learn about everything there before you’re able to solve the bug -which incidentally might very well be harder since you’ll have to solve it “through” the abstraction. (It’s also the reason why I’m not overly fond of internal DSLs: the host language will “shine through” at some point, anyway. Using a subset of UML + profiles also falls prey to this problem.)

The second argument is that, while abstraction can reduce the overall complexity, it does produce a bump in the learning curve: it’s one more term to learn about and remember, especially how it relates to all other concepts, making this a bit of a quadratic process. People generally like to stay in their comfort zones so it’s only natural that they don’t like being dragged out time and time again. The fixed modeling language tools excel in providing concepts and constructs which are at the right level of abstraction for a good deal of the business domains they’re aiming at, so once you’re intimate with those, there’s a lot of business value to be created with only that knowledge so there’s actually no need to be dragged out anyway.

The third argument is that it takes a special kind of software creators (developers/programmers) to go search for abstractions, find the right ones and reify them (implementation in the modeling language, education of modelers, adaptation of code generators/model interpreters, etc.), especially in a running project -this amount to the software equivalent of open heart-surgery where you’re also clobbering together the heart-lung machine on the spot.

The question is whether it’s bad that such different flavors of MDSD tools exist and whether there should be a prevalence for either one. In my opinion, it’s unfortunate that it’s hard to get users of the fixed modeling language tools to acknowledge that the fixed set of constructs and concepts is hurting them. Often, the 80/20-rule is applicable: 80% of the target application can be created in 20% of the time through modeling, while 20% of the application has to be created in a different way and at large costs since the tool doesn’t allow that part to be comfortably modeled. On the other hand, it’s at least as hard to get fans of non-fixed MDSD tools to acknowledge that these are actually not that simple to use.

To me, that is an incentive to see whether I can come up with something that enables easier meta programming (DSL creation, code generator/model interpreter implementation) and is capable of delivering those capabilities to a large audience. Stay tuned…

DSLs “versus” software engineering

(New Year’s resolution: blog more frequently ;))

One aspect of using DSLs for software development which seems to be a bit underplayed (IMHO) is the role of good-ole software engineering, by which I happen to mean the practice of creating software through a systematic approach involving analysis, design, implementation and testing in a controlled and predictable manner. It seems to me there’s something of a sentiment or expectation that with DSLs you don’t have to do software engineering anymore, as if everything that makes creating software difficult somehow instantly disappears when using DSLs to model the software to as large a degree as is desirable and productive.

There are two main reasons for using DSLs:

1. Empowering domain stakeholders (and other participants) by establishing an ubiquitous language for communication and providing them (and disciplines downstream) with dedicated tooling for that language;
2. Separating the essential complexity (the what and why) from the incidental complexity (the how) by focusing the language on the former and hiding the latter “somewhere else”. (This also means that the software model does the same with less “code”.)

So, how does software engineering come into play then? Well, as I see it, there are two sides to this equation: (1) the DSL itself and the way it’s used and (2) the “meta software”, i.e. the software (parser, editor, tooling, etc.) which brings the DSL to life.

Engineering a DSL

To me, the fundamental value of software engineering is the set of concepts such as Separation of Concerns, Loose Coupling, Strong Coherence, (Unit) Testing etc., which allow us to create quality software. I simply define software quality somewhat non-conventially as “it works as required plus it can be productively changed in case the requirements change”. (It’s interesting to see that Kent Beck defines the concepts Loose Coupling and Strong Coherence in terms of how change spreads through a code base.) A DSL can easily be said to “work” if the two advantages mentioned above are realized: stakeholder empowerment and separating essential from incidental complexity -essentially another incarnation of Separation of Concerns. Unfortunately, it’s almost impossible to make this S.M.A.R.T. so you’ll have to rely on your craftsmanship here.

The most obvious aspect of DSL design which contributes directly to the change part of quality is: modularization. This aspect has two directions: (1) how do you distribute different aspects across parts of the language and (2) how can you cut up the entire domain into manageable pieces. Both of these directions benefit directly from the application of concepts like Separation of Concerns, Loose Coupling and Strong Coherence. As an example, consider a (vertical) DSL for Web application development which would typically address data, screen and interaction modeling: Do you create a separate DSL for the data model? Can you divide that up as well? Do you separate screens and interaction/flow? Do you take the use case as unit of granularity? Etcetera… The answers to all these questions are “It depends…” and you’ll have to address these time and time again for each situation or change to that.

But software engineering on the DSL side doesn’t stop there: the DSL instance, i.e., the model that’s built using the DSL must be viewed as software as well -after all, it’s the center piece for the software creation. E.g., as soon as you can modularize your model, you’ll have to think about how to divide the DSL instance into several pieces. Questions which come into play here: How large should each piece be? What kind of inter-piece dependencies do I want to allow or minimize? (This already depends on how modularization is realized on the language level.) How does the versioning system you use affect these decisions? Again, Separation of Concerns, Loose Coupling and Strong Coherence are key concepts to keep in mind here.

You also might want to think about a way to (unit) test the instance. A famous example is business rules: it is very valuable to be able to test the execution of such rules in different scenarios to validate that the results are what your domain stakeholders are expecting. How you code such tests depend (as ever) on the situation: sometimes it’s better to code them against an the business rules’ execution engine (which is something different than testing that execution engine itself!), sometimes you enhance the DSL (or probably better: create a separate DSL) for this purpose.

Engineering the meta software

By “meta software” I mean all the software which is involved with the DSL and which is not directly contributing to the realization of requirements/business value. This ranges from parser definitions (when using a Parser Generator), parser implementations, model validators and model importers to code generators or model interpreters/execution engines. It’s important to realize that this software in the traditional sense as well -not just a bunch of “utility scripts” lying around. In fact, your meta software has to be at least as good as “regular” software since it typically has a large impact on the rest of the software development because the model does more in the same amount of “code”. Among other things, this warrants that you create automated tests for all components, that these tests are part of the continuous integration (automated build) and that everything is checked in into a versioning system. It also warrants that you design the meta software really well, e.g. with an eye towards Separation of Concerns, both inside components as well as across components. It’s advisable to choose a set of tools/frameworks which integrate well and offer as much IDE and compile-time support as possible, to make meta software development as productive, error- and care-free as possible. (I once did a project in which an UML model was fed directly into a combination of a dynamic language and StringTemplate: in the end you get used to it, but it’s painful all the way…)

If the DSL changes, then it might happen that the current model (DSL instance) breaks and must be repaired -depending on the amount of breakage you could do that manually or expend the effort to devise an automated migration facility. This also means that it should be clear at all times which version of the DSL a model requires: it’s usually best to explicitly version both the DSL as well as the model but you might be able get away with an incremental push from a DSL development branch to the modeling branch. In the latter case, you really need to make sure that you tag the meta software together with releases of the software in order to be able to go back in history reliably.

Using a DSL has a kind of a two- (or even multi-) step nature: the DSL instance is parsed first and then fed to either a code generator or a model interpreter. So, if you change the DSL you’ll probably have to change the second step as well. In fact, changes typically “flow backwards”: changes to or enhancement of the code generator or model interpreter often require a change to the DSL as well, e.g. in the form of a new language construct. This phenomenon is sometimes called coupled evolution. Again, having automated tests for all individual components/steps are really necessary to avoid running into problems. In case you use a model interpreter, it’s usually quite easy to write (unit) tests against that.

Change “versus” code generation

In case you have a code generator things are typically more difficult because (1) the generation often is target language-agnostic since most template engines (such as StringTemplate and Xpand) simply spit out “plain text” and (2) usually there’s non-generated code (either framework code or code behind the Generation Gap) as well which has to be integrated with the generated code. I’ve found that in these cases it’s extremely useful to use a relatively small reference application for the meta software discipline. Such a target application would consists of a smallish DSL instance/model which does, however, touch all language constructs in the DSL (especially the new ones) and a fair amount of combinations of those and non-generated code consisting of framework code, hand-crafted code behind the Generation Gap and –mui importante– unit tests to validate the reference application. As always, the process of generating from the reference model, the building of the reference application from generated + non-generated code and running of the unit tests should be automated to be able to verify the correctness of the meta software reliably and quickly.

Something which is very useful in this scenario, is traceability, i.e. being able to see where generated code came from. In particular, which template produced a particular piece of code and what model element was the primary input for that template. Realizing a modest but already quite useful form of traceability is to generate comments with tracing information along with the real code. This is reminiscent of logging, also because care must be taken that the tracing information is succinct without overly “littering” the actual code.

Wrapping up

I hope I’ve been able to make the case that “old-fashioned” software engineering has a definite merit in the DSL scenario. Of course, there’s a lot more to say on this topic. Personally, I’m hoping that the upcoming book on DSL Engineering by Eelco Visser and Markus Voelter treats this really well.

Going back to the source…

During a recent masterclass in the Netherlands, Neal Ford pointed to an article by Jack W. Reeves aptly titled “What is Software Design?” and even more aptly answering that question. (You can find the article online.) Its basic premise is that software design equals source code. In other words: it’s non-sensical to try and design software in a high-level fashion beforehand and expect that writing the actual source code is something that’s comparable to the ubiquitous factory line. Well, we all know how that turned out to work, right?…

The article touches on a lot of aspects of the software creation process, one of which is the assertion that software should be expressible on all levels of detail: “What we need is a unified design notation suitable for all levels of design. In other words, we need a programming language that is also suitable for capturing high level design concepts.” Obviously, I see a role for MDSD and DSLs here 😉

Now, the funny thing is that it was published (and presumably written) in 1992, but already seems to point towards a lot of “later findings” such as Agile (in terms of “excuses to start coding earlier in the life cycle”) and modeling (in particular the distinction between modeling in the problem and solution spaces). I had the same “déjà vu-in retrospective” feeling when reading Fred Brooks’ “The Mythical Man-month”, which acutely describes the software crisis as we’re still experiencing from a mid-70’s viewpoint based on experiences from the 60’s!

Do these guys have time machines, a crystal ball or is it simply that we haven’t gotten much (or even: any) smarter in 18, resp. 35 years? Why aren’t we much (or even: any) closer to solving the software crisis despite all those advances? Are we so non-rational that even we, as software engineering professionals or as an SE profession, are incapable of learning from the past? Do our managers get prepped in such a way that we’re doomed to repeat SE history over and over again?

What do you think?

When to solve stuff with a DSL

One of the great benefits of DSLs (textual or graphical alike), is that it allows you to separate essential complexity, i.e. complexity which is intrinsic to the problem you’re trying to solve, from incidental complexity, i.e. complexity which is caused by the approach chosen to solve that problem. This is certainly the case for external DSLs, since these often evolve from a ‘technical clean slate’. Whether you’re actually able to achieve that separation depends on a couple of things:

1. the measure in which you understand the problem space or domain;
2. the measure in which you understand the solution space;
3. your skill as a DSL/language designer.

But first and foremost, it depends on your ability to recognize a situation in which ‘death by incidental complexity’ is likely to occur or even already occurring which in turn depends on the quality of your communication with the project (team). During one of my recent projects, I found myself in the situation that I didn’t (allow myself to) recognize such a situation until it was almost too late and a lot of effort had been wasted.

A tale from the crypt

This particular project entailed building a custom middleware Web application, which we were luckily able to do rather successfully and efficiently using Model-Driven Software Development. The central use case for this application consisted of quite a lot of complicated screen, with one screen being extremely complex…and becoming more and more complex as time progressed, due to an liberal amount of change requests (scope creep, anyone?). The screen was complex for a number of reasons:

1. it was big: the number of possible input fields, buttons, etc. almost ran to the triple digits;
2. it was highly dynamic: depending on values of certain input fields, check boxes and such, other input fields were or were not visible and/or editable;
3. no roundtrips to the server were allowed for performance and usability reasons, which led to duplication of logic in both the server code (Java) as well as the client code (JavaScript);
4. the mapping from the object model to values on the screen and (especially) back, as well as roundtripping to other screens, was tedious;
5. testability was problematic and only partially automated.

To make matters worse: because it was one of the few screens which didn’t fit the modeling language used (UML2 + custom profiles), almost nothing of the screens functionality could be modeled so everything had to be hand-coded and hand-integrated with the rest of the application. In the process, the requirements for this screen were separated from the application model and documented in the usual amalgam of freeform Word and Excel documents.

So, over a period of about half a year a developer colleague of mine slaved away over this gargantuan screen for what must have been at least a full workload, guided and assisted much of the time by a business analyst colleague who was maintaining said Excel documents and who had previously come to like and rely on the rigor of modeling quite a lot. All this happened within eyeshot…which unfortunately didn’t actually prompt me to take some interest and see why this damned screen was taking a lot more time to complete than initially expected. To further implicate myself: I had implemented the initial version of the screen when it wasn’t very dynamic yet, and I didn’t really mind not being part of the actual developing effort. As karma usually has it: the developer colleague decided to continue his career with another company and ‘The Beast’ was handed back to me, together with a rather hefty bunch of change requests 😉 Despite being knowledgeable about our architecture, I couldn’t really make head or tails of the implementation which suffered from the essential and incidental complexities essentially being multiplied instead of added up -always a bad sign in (non-generated) code, as is an almost-exponential effort curve for implementing changes.

So there I was with a few hundred K’s of (not so homogeneous) Java and JSP code serving a Web page with a lot of JavaScript code, plus some change requests for which I had very little idea of implementing in said code base. The first thing I usually do in these circumstances, is to Refactor away. After about a week, this Refactoring hardly made a dint in reducing the total complexity and only increased the quality of the JavaScript code a bit. Time for plan B, which was to mentally throw the existing solution out of the window and think about how a DSL solution (which was plausible given that we already were an MDSD shop) would look.

The Solution

For a couple of days I feverishly but happily worked on implementing a textual DSL (using Xtext, obviously) to capture the screens’ requirements and generate a Web page mockup from it, as that would allow the business analyst to validate her DSL instance functionally on the push of a button (literally). In total, it took me about 1.5 week to implement the DSL, a half-working mockup generator (with the mockups already being quite close to an actual implementation inside the application’s architecture), a DSL instance capturing about 80% of the screen in all its dynamic and purely essential detail plus some additional stuff to be able to interact with the entity model (in UML). When I showed what I had to my colleagues, the business analyst said ‘Please move over, I have a screen to finish!’ which is by far the nicest response I’ve ever had to anything I’ve created. Unfortunately, the project was cancelled before we could progress from here, for reasons beyond our control, but not before having obtained a full GO from the project manager for replacing the existing implementation with a DSL-based one.

The most important thing I learned from this is that I should have taken an interest in what was going on a mere 1m from my desk which would have allowed me to recognize the potential of a DSL to help and get a grip on the complexity of the things at hand at an earlier stage which could have saved a lot of effort and head aches. Interesting is the fact that it took me only a few days to come up with a quite complex and rather mature DSL (having a sub-DSL for Boolean expressions, references of features of an entity model using path expressions, among various other not-so-trivial constructs) using Xtext even though it was my first DSL built with Xtext version 0.7.2 using not-so-trivial scoping -future posts will discuss and detail some of the features mentioned. This means that the ramp-up of a complete DSL+generator solution in these or similar circumstances can be measured in weeks rather than in months or longer. Also, progress was quite linear and number and complexity of features -no exponential curve or 20%-80%-rule in sight.

---

Addendum

Ron Kersic had already argued that ‘incidental complexity’ is a much better nomer than ‘accidental complexity’ since the primary semantics of incidental is ‘happening in connection with or resulting from something more important’ while that of accidental is ‘occurring by chance, unexpectedly, or unintentionally’. Although I agreed with him, ‘accidental complexity’ is a reasonably established concept…until Fred Brooks chose to forego on it and use ‘incidental complexity’ instead. So, I happily replaced all occurrences of ‘accidental’ with ‘incidental’ in the body of the blog. And thanks again to Ron for pointing this out 🙂