Copying EMF models with Henshin

Copying arbitrary EMF models is an easy task using the EMF utils class: a simple EcoreUtil.copy(obj) does the job. This method uses the reflective API of EMF to copy EObjects including their type information and all their features. In Henshin, model transformations are statically typed. Therefore, it is not obvious how to realize such a generic copy functionality that works for any EObject. One way to do it anyway is using the recently introduced wrapper model. The idea is that every EObject is wrapped by a WObject which contains metadata information as normal structural features. This allows us to set and modify the type of a WObject without the need to know its type at design time. In a similar way, we can access and change the types and values of structural features. We can use the wrappers to specify a copy-transformation as follows.

We first create for every WObject another WObject of the same type. We then copy all WValues of the WObjects, and then all the WLinks between the WObject. The wrapper objects automatically reflect these changes in the wrapped EObjects. In this way, we realized a generic copy function in Henshin. Note that the goal was not to implement a better copy method than provided in EcoreUtil (I don't think that's actually possible). We just want to show how dynamic typing in Henshin truely increases the expressiveness and the flexibility of the language. The copy transformation can be found in Henshin's examples plug-in.

Dynamic Adaptation in Ant Colonies and Robot Swarms

A particular interesting engineering discipline is the area of materials and technologies that are inspired by nature, e.g. the surface of a Lotus flower or robots which look and behave like animals. For example, last X-mas I got this cute little robot bug which reacts on noises and tries to walk around obstacles on its path.

Interestingly, nature is an inspiration not only in technological areas, but also in theoretical computer science, specifically in the designing of algorithms. The first thing that comes to mind are of course evolutionary algorithms. Another area where ideas from nature are borrowed is swarm intelligence. One specific example of swarm intelligence are so-called ant colony optimization algorithms. The problem solved by such algorithms is that a colony of ants needs to find the shortest path from their nest (N) to a food place (F), as shown below.

Initially, all ants walk around randomly until some of them stumble on the food place, get some food and walk back to the nest. When moving around, the ants leave a pheromone trail. Other ants that pass such trails tend to give up there random exploration and follow the pheromone trail instead, thereby intensifying the trail. On the other hand the pheromones evaporate. That means the longer the path to the food place, the more time there is for the pheromones to evaporate. Thus, the percentage of ants taking the shorter path increases until eventually almost all ants use the shorter path. Using this simple trick, the ants manage to find the shortest path from the nest to the food place without any further coordination.

Such randomized optimization algorithms are also appealing for coordinating robots. But the immediate problem is that there is no equivalent notion for the pheromone trails produced by ants. One possible solution that works without pheromones is the so-called majority rule. The idea is that the robots travel around in teams of size 3. These teams are formed randomly in the nest. Every time a team is formed, they make a majority vote which path they should choose. All team members change their opinion to the elected path and travel to the food place and back. Since the teams are formed randomly, the system will reach a steady state where all robots agreed on one path. Similarly to the ant optimization algorithm, the shortest path has the highest probability to be chosen by the robot swarm. 

While this is a neat algorithm for finding an optimal path without any orchestration, there is one problem to it: it is not adaptable. That means, if due to some change in the environment suddenly the longer path becomes the shorter one, then the robot swarm will stick to its chosen path and not change to the new shorter one. This is because there is no robot left that could seed a drift to the new path.

We investigated two possibilities to make the majority rule adaptive. The first one is called the Switch scheme: if there is a team where all members already believe that the same path is the right one, they switch with a small probability to the other path. The second approach is the so-called MinPop scheme: a small population of the agents is stubborn, i.e. they take part in the voting, but they do not change their opinion. We modeled both approaches as discrete-time Markov chains (DTMCs) and fed the models into PRISM to analyze them. Below you can see the result.

One the top, you can see the efficiency of both schemes, i.e., what is the probability of an agent going down the right path. On the bottom, you can see the adaption times of both schemes, i.e., how much time it takes two turn a complete A-path population into a B-path population. The main thing to observe is that there is a trade-off between efficiency and adaptivity. The more adaptive a protocol is, the less efficient it is. We also compared Swtich and MinPop regarding this trade-off and it looks like the MinPop scheme performs better than the Switch scheme.

The details are described in a short paper by Erik and Pim de Vink and myself, which appeared in the pre-proceedings of QAPL 2013. I want to use the chance to thank Erik for pointing me to this very interesting research area.

Dynamic Types for Henshin

One of the great strengths of EMF is its reflective API and the fact that you can dynamically create models and instances of it without generating any code. Dynamic EMF is really powerful but there are some limitations and common pitfalls. For one, you should be careful when mixing dynamic and static models. Another thing to be careful about is that once you've defined a dynamic EMF model and you have created instances of it, you should beware of making any (structural) changes to the model because there is a good chance that it will invalidate your instances and maybe even cause run-time exceptions. Changing the model while working with instances of it seems to be something that you would not really do in practice, but there are actually applications where this is useful and desirable, e.g. metamodel evolution and instance model migration.

In Henshin, the metamodels are usually fixed and actually required to be known at design-time. That basically means that rules and transformations in Henshin are statically typed. To overcome this limitation, we recently came up with a new way to support dynamic types and metamodel changes. The idea is to use wrappers for instance models which allow us to connect the instance model and the metamodel levels using ordinary structural features. You should not be surprised that we defined these wrappers as yet another EMF model:

A WObject wraps an EObject, WLinks represent instances of EReferences, and WValues specific data values. The default implementation of the wrappers propagates all consistent changes to the wrappers or the metamodel down to the EObjects. Using this model in Henshin allows us to define dynamically typed transformation rules. Let's have a look at the following two example rules.

The first one is an ordinary (statically typed) rule which matches an object a of type A such that the name attribute of a is x and creates an object b of type B and a link of type ref from a to b. The second rule is semantically equivalent, but here we use wrappers. The top row matches the metamodel elements, i.e. two EClasses named "A" and "B", an EReference named "ref" and an EAttribute named "att". The lower part represents the instances of these metamodel elements (modeled using wrappers).

There are important differences in the expressive power between the two approaches: for statically typed rules, the metamodel is fixed and must be known at design-time. In the dynamic approach, the metamodel elements are matched at run-time. This allows us to dynamically create and modify instances, and even to make changes to the metamodel while there are instances of it, as done in the following rule:

This rule deletes the ref-EReference from the metamodel. In addition, all links of this type are removed from all instance models. The deletion of all links is realized using the *-operator (multi-rules in Henshin). Note that we did not connect the wrapper objects with the EClasses using type-references because we also want to handle instances of subclasses of A and B.

This is only a small example, but I think it already shows the potential of the approach. We have described this approach and its use for defining coupled metamodel and instance model evolution in a paper accepted for ICMT 2013. The wrapper model is shipped with the current release of Henshin (0.9.6) together with two examples: one for copying arbitrary EMF models and one on coupled evolution.