Nested Multi-Rules in Henshin

Graph transformations become more and more popular in software engineering. This trend is somewhat surprising as their foundations were already developed in the 1970's (or even late 1960's). One reason for this is probably their appealing visual representation similar to Petri nets or UML diagrams. Graph transformations (and Reo) are also one of the few topics that my wife recalls when she is asked about what I work on.

One of the most popular applications of graph transformation is model-driven engineering and specifically model transformations. In Henshin, we develop a graph transformation based language targeting the Eclipse Modeling Framework.

A neat feature that we have in Henshin are so-called nested multi-rules which are formally based on a concept called amalgamation. It is essentially a concept for synchronized rule applications and it greatly increases the expressive power of the Henshin language compared to the standard graph transformation rule formats. Usually, graph transformation rules describe a pattern of fixed size and topology that should be matched and transformed. In Henshin, we can use nested multi-rules to match and transform patterns of unbounded size and a, let's call it regular, structure. Let s take a look at an example...

This rule models a simple broadcasting protocol in wireless sensor networks. It matches an active node x that has exactly one message. Now the multi-rule part of this rule are the elements on the right with the «...*» stereotypes. This part of the rule is matched and applied as often as possible. So when this rule is executed, a message object is created at all active neighbor nodes. This rule alone describes a non-trivial broadcast protocol completely independently of the topology of the network. Let's see another example...

This is an operational model of the so-called gossiping girls problem. In a nutshell, the problem is: there are n girls each of them knowing a piece of gossip. How many phone calls are required so that all girls know all secrets? The above rule models a phone call between two girls, say g1 and g2. The rule matches all secrets of g1 that g2 doesn't know and all secrets of g2 that g1 doesn't know. The rule then just creates the necessary edges so that after the rule has been applied both girls know all matched secrets. Neat, isn't it.

What we have seen so far are actually only rules with a single multi-rule. In Henshin, you can have in fact more than one multi-rule and even nest them. You can specify the different multi-rules and their nesting structure through a path concept in Henshin's actions (this is how we call the stereotypes on nodes and edges.) The rule below is a more complicated example which makes use of nested multi-rules. It is the first part of the classical OO2Rdb-example for exogenous model transformations. The rule translates a package to a database schema together with all its classes and attributes.

There are many more examples where nested multi-rules allow you to do fairly complex graph manipulations. From an operational point of view, a nice feature of such rules is not only their conciseness, but the fact that they are executed atomically.

In one of my next posts, I will tell you how to define and use dynamically typed rules. These can be used for example to copy arbitrary EMF models using Henshin. Stay tuned.