Game of Life in Java on Steroids

October 05, 2015

Written by Jens Nerche

Reading time ~8 minutes

Code Retreats and the Game of Life

Code Retreats are a good way to improve our skills as Software Craftsmen. Soon there is the #gdcr15, reason enough to make the Game of Life a topic of a blog post.

Here is an example in Java:

Game of Life in Java

Java. Java? Java + extensions!

Hm, Java? That is not Java. Well, it looks like somewhat like Java, but that tables, that colored constants, that initialization of the generation array, that operations? It’s not hard to notice: there are some extensions made to Java. That takes for sure some years or at least months for a single person to create such extensions! No, not really. Uh yeah, if you take the OpenJDK and put your extensions there - but we don’t. We take a Language Workbench. To be more precise: we take the MPS Language Workbench. Now it is easy to modularize and put together programming languages.

In the following sections we will have a closer look on each of the new language concepts. You can get the source on my GitHub account.

New Type: Coordinate

The Gol class starts like a quite normal Java class with a main method. But already the second method, run(), contains something special. As you see, Coordinate is like a build-in Java type. It could also be a class named Coordinate, but there is a tiny difference: look at the initialization of the arraylist. These are no calls to constructors, these are the notation (aka “Concrete Syntax”) of a Literal. Just like 5 for an integer or “foo” for a string.

What do we need to create a new type? Surprisingly not that much. Of course the type itself:

Coordinate Type

Note the little blue arrow. The CoordinateType extends something called “Type”. This is the exact Type all other Java types like integer, long etc. extend too. Because of that our new CoordinateType fits nicely into the existing Java type system.

Next there is the Literal:

Coordinate Literal

Note again the blue arrow. The CoordinateLiteral extends an Expression - yes, again the very same Expression which is the base for all Java expressions.

Now we only have to tell the type system, that our CoordinateLiteral is of type CoordinateType:

CoordinateLiteral is of type CoordinateType

With some MPS type system syntax, this basically declares the the type as described above.

That’s it. After five minutes or so we are able to use a new Java type. It does not yet do something useful, therefore we have to declare the semantics via a generator. But that is the topic of a different section down below.

Syntax sugar: alive and dead

In the next method, nextGeneration(…), a two colorful constants catch the eye. ‘alive’ and ‘dead’ are used like constants or enums, but have a custom color. We could also assign other properties like underlined text, italic or bold font, a different font size and so on. Can normal Java IDEs do that too? No - and perhaps that would be a nice issue to be filed in Eclipse, NetBeans or Intellij IDEAs backlogs: assigning representation properties to constants and enums.

And it’s really no big deal to get domain specific styled constants:

AliveExpression

Again we extend an Expression. But that does not explain the different style of the text. This leads to a topic I did not mention so far: every new language concept needs or may declare how it is presented. Needs or may, eh? Yes, if we inherit from a language concepts which provides a decent representation we can go with it. If we don’t inherit or want to override the inherited style, we need to define a so called ‘editor’. Let’s have a look at the editor for the alive expression:

Alive Expression Editor

Hm, not that impressive. We see that it’s the ‘editor for concept AliveConcept’. And it’s the default one. Yes, we may declare more than one representation for a concept, e.g. for color-blind people. But let’s focus for now on only one editor. We also see that the #alias# should be shown. Alias? Yes, please go back to the Alive Expression picture. There it is: ‘alias: alive’. But how comes the color in? We can declare styles in a different tool window:

Alive Expression Editor Style

And the same goes for Dead Expression with the style ‘text-foreground-color : red’.

Decision Table

Now we come to one of the most powerful and most interesting things of custom representations via own ‘editors’. We are not limited to text like in normal IDEs. We could define also - tables! And not only tables, but even Java Swing components are allowed. So we could replace the alive and dead concepts with checkboxes. Or add some JavaDoc with explaining pictures. But for now let’s focus on the tables. In the nextGeneration(…) method we see a decision table. A content cell from the middle is taken if the column header and the row header both evaluate to true. If no constellation evaluates to true, the default value is taken. In fact, this decision table represents the core algorithm of the Game of Life:

Decision Table

Depending on if the current generation contains a cell and how many neighbors it has, it will be added to the next generation or not. And because the decision table also extends the Expression and the Type is declared boolean, the table can be used as condition in a regular if statement.

Mapping Table

In the neighbors() method we see again a table. This time no decision table but a mapping table. A single cell and a table were combined:

Mapping Table

The bold plus sign indicates that it is no normal summation operation but an adapted version for the table: the left side of the plus - here a variable named ‘cell’ of type Coordinate - is added to every entry in the table. This results into nine new Coordinates. The middle one is the original cell itself, so it is no neighbor and will be subtracted again.

Extending Operations: plus and minus

Subtracted? A single value via minus operation from a collection in Java? This is only possible because we can also put additional semantics on operations as language extensions. Once again the type system feature of MPS comes to help and let’s us overload operations:

Overloaded Operations

The first of the two new rules declares for plus and minus operators that the summation and subtraction of two things of type Coordinate is allowed and results into a Coordinate type.

The second new rule declares that a subtraction of a Coordinate from a Coordinate array is allowed and results into a Coordinate array.

So far it’s very nice that we can program with the extensions. But until now that program does not run.

Generate Java code

To let a program run, it has to be compiled or interpreted. Java programs were compiled into byte code. Until now we did not define how the bytecode for our new language concepts has to be generated. But do we really want to generate bytecode directly like Java does for the built-in keywords?

Let’s take a step back first and see what we did: we stacked a new language on top of an existing one. We created a new layer. Our new language extends the Java language. We should not bypass layers on the language stack and generate code for the language layer direct below the new language. Not that we are not constrained to extend only one language. A new one can extend as many languages as it wants. That’s why I chose the term ‘language layer’.

That said, we don’t generate bytecode, instead we generate Java code. For ‘alive’ and ‘dead’ it’s dead simple: ‘alive’ is replaced by a boolean ‘true’ and ‘dead’ by a boolean ‘false’.

Not really surprising is what we generate for the Coordinate type. In Java we would represent it by a class named Coordinate and so we generate it. To make that work, we have the Runtime Solution named ‘gol.runtime’. It contains only one class - the Coordinate. Exactly that Coordinate class is used as the generation target for the Coordinate type.

So if the Coordinate type is translated to the Coordinate class, the Coordinate literals is translated to a constructor call of the Coordinate class. Quite natural.

The nice thing about having the Coordinate class in the runtime model is that we can use it’s ‘sum’, ‘minus’ and ‘removeFromArray’ methods as generation targets for our overloaded operations ‘plus’ and ‘minus’. It is exact the same thing as the ‘add’ and ‘subtract’ methods in BigInteger and BigDecimal.

Now we are nearly done. But the hardest part comes as last. Translating the decision and mapping tables to valid Java code is not that simple. Therefor I would suggest to watch that video for a good and extensive explanation.

Conclusions

What did we learn? It’s quite simple to extend Java. Why should we do this? Nearly every Java programmer has some favorite missing language features, don’t you?

But there is a second and for me the more important reason: domain concepts can be integrated into a Java dialect which is specially created for the project in that domain. For the Game of Life, we added ‘alive’, ‘dead’, the Coordinate. This may be seen only as some syntactic sugar. But look again at the program: the color- and meaningful ‘alive’ and ‘dead’ words catch the eye. There is no syntactic clutter around creating a new Coordinate - no verbose Java ‘new Coordinate(1, 1), just a (1, 1). Image you can write a math formula just as - a math formula and not as a long Java methods with many words an no single math symbol. Notation matters, and notation is nothing else than the concrete syntax of a language. With language extensions we can define our own concrete syntax. A program can be much more optimized for reading. And source code is ten times more read than written. Or even more often.

Managing Technical Debt with arc42 and jQAssistant: Building Block Dependencies

Making the build green again although there are dependencies in the wrong direction - and document them in the architecture documentation Continue reading

Combine jQAssistant with C++ (somehow)

Published on January 05, 2017