Path Constraints in Henshin

In our recent paper on the Giraph code generator in Henshin, we conducted some benchmarks using a real-data example. For this we used the publicly available data sets from the IMDB movie database. We parsed the movie, actor and actress records into an EMF model as shown below. Note that I omitted the attributes here for simplicity.

The goal of our transformation on the IMDB data set was to find all pairs of persons (actors or actresses) which starred together in at least three movies. For every such pair we want to create an instance of the Couple class. We used the Henshin rule below to do this. First, note that all nodes / edges have *-actions and thus the rule is applied to all found matches at once. Second, we used <<require*>>-actions for the movies, and not <<preserve*>>. This is important because we want to ensure the existence of these movies, but be don't want to generate separate matches for every combination of movies. There is only one small subtlety in this rule: due to the symmetry of person nodes, we will actually create two couple nodes for every pair. But this could be easily fixed by enforcing an alphabetical order of the persons' names using an attribute condition.

To compare the performance of the Giraph-based engine, we also tried to execute this example with the normal Henshin interpreter. To our surprise, even for a small part of the IMDB data set, the Henshin interpreter was not able to compute a match. To study the problem in a more controlled setting, we defined a small transformation that generates a synthetic test data set of variable size. We then ran the interpreter again and got the following numbers.

Nodes	Couples	Time (ms)
1,700	200	1,625
3,400	400	3,753
5,100	600	7,828
6,800	800	14,386
8,500	1,000	23,301

This looks pretty bad. The input graphs are very small (< 10,000 nodes) and it already takes more than 20 seconds. The main problem is that the execution time grows non-linearly (should be O(n²)) with the size of the input graph. What is the reason for this? Well, the Henshin interpreter first fixes a match for the LHS (<<preserve>> and <<delete>> elements), and after that it tries to match the application conditions (<<require>> and <<forbid>> elements). In our example, this means that it first picks to arbitrary persons, and then checks whether they starred together in 3 movies. Thus. it is basically a brute-force approach that the interpreter runs here.

The pattern matching is implemented in Henshin as a constraint-solving problem. To fix the bad performance of the movies example (and similar problems), we added a new type of constraint to the pattern matching algorithm: path constraints. Path constraints are internally used to check whether there exists a path between two EObjects along a given list of EReferences. The neat thing about these paths is that they can also go via <<require>> nodes. In our example, this indeed works because the movies-reference has an opposite reference: persons. If we now fix one of the two persons, the path constraint via the references [movies, persons] allows the match finder to restrict the solution set for the second person to only those persons who played together with the first one in at least one movie. This drastically prunes the search space which gives us a much better performance.

Nodes	Couples	Time (ms)
1,700	200	133
3,400	400	89
5,100	600	35
6,800	800	36
8,500	1,000	49
...	...	...
170,000	20,000	1,419
850,000	100,000	6,183
1,700,000	200,000	9,836

This looks much better: now we can process 1.7 million nodes in less than 10 seconds. This should be also enough to run the example on the original IMDB data set. The example including the benchmark is part of the examples plug-in of the development version of Henshin.

Henshin + Giraph: Enforced Parallelism

I recently announced the availability of a Giraph code generator for Henshin, which allows you to execute graph transformations in a parallel and distributed manner. It is important to know that there is a fundamental difference in the execution semantics of graph transformations in this approach. Concretely, the application of rules is always maximum parallel, i.e., every rule is always applied to all found matches in parallel. The idea behind this is that we want to enforce the use of parallelism already at the modeling level and to make it hard for developers to use conventional sequential algorithms that cannot be parallelized automatically. For example, the rule AddTriangles below would be applied to all found triangles in parallel. Executing the iterated unit BuildSierpinski to a 3-node triangle therefore generates the full Sierpinski triangle of depth N.

Due to the change in the execution semantics of rules, other existing and also some new modeling concepts specifically tailored for parallel graph transformations become important. For example, vertices and edges with <<require>> and <<forbid>> stereotypes are particularly useful to avoid overlapping matches which could result in inconsistent parallel rule applications. We also introduced concepts that allow you to aggregate over attribute values of all found matches. I will discuss this in more detail in another post.

Henshin + Giraph = Big Data Graph Transformations

Henshin is a graph and model transformation tool for Eclipse that lets you define rules and workflows for transformation in a graphical editor. By default, these transformations are executed using an interpreter on an in-memory EMF model.

Apache Giraph is a distributed and parallel graph processing framework built for high scalability. Giraph is for instance used at Facebook to analyze the underlying graphs of social networks.

So how do Henshin and Giraph fit together? Easy: Henshin provides an expressive graph transformation language with an intuitive graphical syntax. Giraph provides an infrastructure for highly parallel and distributed graph processing. The sort of obvious way of combining the two is to use Henshin as modeling tool and Giraph as execution engine. And that is what we are currently working on.

We implemented a code generator that produces Java code for Giraph from Henshin models. This generated code contains pattern matching code and graph manipulations for rules, and the required coordination to execute transformation units (workflows). The code generation is still an experimental feature but we plan to stabilize it and ship it with the next release of Henshin. We have already a small test suite and conducted some promising benchmarks. More details later.

The Giraph code generator is available in the development version of Henshin (for Eclipse Kepler). You can get it from our nightly build update site or by getting the source code directly.

Parallel State Space Exploration in Henshin

Back from the summer break, I read an interesting article on combining OCL expressions with CTL formulas. Apart from the modeling approach itself, it was interesting to me that the authors used Henshin to generate their state spaces and also compared their modeling and the performance of Henshin's state space generator with GROOVE.

While the GROOVE tool does not really provide an API for its simulator and state space generator, it is fairly easy to do this programmatically in Henshin:

// Set-up:
StateSpace stateSpace = new StateSpaceImpl();
stateSpace.getRules().addAll(rules);
StateSpaceManager manager = 
   new ParallelStateSpaceManager(stateSpace, 4);
manager.createInitialState(new ModelImpl(resource));

// Exploration:
StateSpaceExplorationHelper helper = 
   new StateSpaceExplorationHelper(manager);
helper.doExploration(-1, monitor);

That's it. After you have generated the state space, you can either save it or use a validator to check invariants or to do model checking etc.

The authors of the OCL-meets-CTL paper mention that there is room for improving the performance of Henshin's state space generator, which I fully agree to. Nevertheless, I want to show here that we have put a lot of effort to make Henshin's state space generator as fast as possible. A key difference to GROOVE is that state space generation in Henshin can be parallelized. Let me show you some numbers.

The chart shows the time needed to generate the state space of the dining philosophers example for 10 philosophers. What you can see is that by using multi-threaded state space generation, we obtain a speed-up of factor 3. In absolute numbers, the generator explores around 2000 states per second. That is just half a millisecond to find all rule matches for a state graph, make a copy and transform it for every match, and look up states and update the state space. If you compare it with the performance of the Henshin interpreter itself (see e.g. here), these numbers are top notch. Note also that the speed can be greatly improved simply by increasing the cache sizes of the state space generator (which requires more main memory though).

That being said, there is still of course room for improvement. For example, the scale-up for a high number of processors and threads is not as good as we have hoped. The required locking of the state space seems to be the main bottleneck. The performance can be probably tweaked but it will of course never be as fast as model checkers that work on vector-based data (as opposed to graphs).

Henshin 0.9.10 on its way. We are working on the new version of Henshin which we hope to release in November 2013. It will target and require Eclipse Kepler. The most exciting new feature will be a new execution platform for Henshin transformations. More on this later.

Henshin 0.9.8: Working with Lists

We are happy to announce the release of Henshin 0.9.8! Henshin is a graph-based model transformation language for EMF. Besides a number of bugfixes and performance improvements for the UI, the new version brings support for edge indices, which allow you to work with lists.

Since Henshin is based on graph transformations, it did not allow you to access and manipulate the order of elements in multi-valued references -- until now. This was in fact a design choice, because in most cases we do not care about the order of elements. There are models and applications though were the order matters and is in fact crucial for the semantics of the models. The standard example that comes to my mind is if you build a model from a textual language. There it is natural to represent the order of statements or commands in a list. For example, JaMoPP constructs models from Java source code and in these models, the order of, say, statements is crucial. And of course, we want to be able to apply Henshin to such models as well, e.g., to implement program transformations like refactorings, translations to other languages, or to define an operational semantics (essentially building an interpreter).

Henshin 0.9.8 comes with a new feature called edge indices, which allow you to access and manipulate the order of elements in multi-valued references. We added a new string attribute called index to the Edge class which you can use to specify an expression that evaluates to an integer. In the graphical editor, we use an array notation to specify the indices. For example, if you have an edge of type ref, you could write ref[0] to access the first element in the reference list. We adopted a notation from Python where negative indices can be used to access elements starting from the end of the list, e.g., ref[-1] matches the last element of any list.

If your rule has a parameter i, you can write ref[i] to match the i-th element. Note that if no value for i is passed as a parameter, the match finder will try to find a valid value for you such that a match of the graph pattern can be found. You can also define a change in the index, i.e., you can move elements in a list. For example, if you have parameters i and j, you can write ref[i->j] to move the element at position i to the position j. The rule swap in the screenshot shows an example for this. It matches two EClasses with names x and y in a package and swaps their positions in the eClassifiers reference list if (and only if) the condition (i<j) && (x>y) holds where (x>y) refers to the lexicographical order of strings (JavaScript syntax). Thus, if we apply this rule in a loop, we achieve a sorting of the EClasses in the package by their names. Note that the engine will match all parameters automatically.

Let me say that it is not our intent to implement sorting algorithms (or any other algorithms for that matter) in Henshin. Henshin rules are declarative in nature and not designed for doing such things. Nevertheless, it is important that we can deal with lists in Henshin in order to apply it to order-sensitive models like program models.

Henshin 0.9.8 is available at our release update site and the above sorting example can be found in the examples plugin shipped with the release (or as available in our source code repository).

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.

Take part in the Transformation Tool Contest 2013

The Transformation Tool Contest (TTC) workshop is going into its 6th round! This year it will be co-located with ICMT and other conferences and workshops as part of STAF. The aim of the TTC is to compare the expressiveness, the usability and the performance of graph and model transformation tools along a number of selected case studies. That is, we want to learn about the pros and cons of each tool considering different applications. A deeper understanding of the relative merits of different tool features will help to further improve graph and model transformation tools and to indicate open problems.

The Eclipse-based portion of the tools participating at the TTC is continuously increasing. At the TTC 2011, we had some great solutions of many EMF and Eclipse-based transformation tools, including Edapt, Epsilon, Henshin, MDELab, VIATRA2 and others. Maybe your tool should be in that list too!

This year we have three great cases to be solved by you: a Flow Graphs case (submitted by Tassilo Horn), a Class Diagram Restructuring case (submitted by Kevin Lano and Shekoufeh Kolahdouz Rahimi), and a Petri Nets to State Charts case (submitted by Pieter Van Gorp and Louis Rose). If you want to learn more about these cases, take a look at the introduction video by Louis Rose.

Hope to see you at the TTC 2013!

Henshin 0.9.6 released

We are happy to announce the release of version 0.9.6 of Henshin. If you don't know it yet, Henshin is a model transformation language for the Eclipse Modeling Framework (EMF) and is based on visual graph transformation rules. Below, you see two pretty much self-explaining example transformation rules in Henshin.

The Henshin transformation language itself is defined in EMF and provides you with powerful concepts including declarative rules, imparative control-flow constructs and attribute calculations in JavaScript. Transformations are executed using an interpreter engine with a stable light-weight API and can be analyzed using state space generation tools and a profiler.

Henshin 0.9.6 comes with lots of improvements in the graphical and the tree-based editors, including support for different color modes (essentially themes). Both the transformation language and the interpreter API are stable and thus fully backward compatible. The interpreter itself now understands expressions like "[a,b,c]" for multi-valued attributes. All in all, I think we are on a good way towards version 1.0!

Profiling in Henshin

Graph transformations are a powerful formalism for realizing any kind of pattern and rule-based modifications of high-level data structures. A lot of work has been done for the theoretical foundations of graph transformations and a large extent of this work is phrased in category theory. One of the nice things of category theory is that constructions and operations are not explicitly given -- instead, the results of operations are defined in terms of universal properties. For graph transformations this means for example that the result of a rule application exists and is uniquely defined (up to isomorphism). While this definition is useful from a theoretical perspective, it is not really helpful when you actually try to use graph transformations in practice, e.g., when you try to implement a graph transformation engine yourself. This is because the universal properties don't tell you anything about the algorithms and optimizations required for realizing the operations efficiently.

The most time-critical part when implementing a graph transformation engine such as the Henshin interpreter is the matching engine for rules. So the task is: given the left-hand side of a rule (and possible nested application conditions), find a or all possible matches of this pattern in a given host graph. In Henshin, this is implemented using constraint solving techniques and some heuristics for finding optimal search plans. Nevertheless, as a user you can still be confronted with cases where a transformation takes an extensive amount of time. In such situations, it is very important to find the bottlenecks in large and complex transformations.

In Henshin, you can use our basic profiling support to find out which part of your transformation is time-critical. Let's take a look at an example. The rules and units below are taken from an old version of the Grid & Comb Pattern example and are used to construct a (full) grid of a given width and height.

The main unit of this transformation is buildGrid. We can execute this unit using Henshin's interpreter API, e.g., like this:

Engine engine = new EngineImpl();
engine.getOptions().put(Engine.OPTION_SORT_VARIABLES, false);
UnitApplication application = 
   new UnitApplicationImpl(engine, graph, unit, null);
application.setParameterValue("width", 40);
application.setParameterValue("height", 40);
application.execute(null);

If we do it like this for the old version of this example, the execution takes about 1 minute, which is really slow. The generated grid has only 1.600 nodes and thus it should be possible to do it much faster. So, this is a good opportunity to try out Henshin's profiling support. The trick is to pass a ProfilingApplicationMonitor to the unit execution, like this:

ProfilingApplicationMonitor monitor =
   new ProfilingApplicationMonitor();
application.execute(monitor); 
monitor.printStats();

This automatically collects statistics about the execution times of all rules. In the last line, we just print the gathered data. We get this output on the console:

Stats for rule 'extendFirstColumn':
 - Number of Executions: 38
 - Total execution time: 35ms
 - Aver. execution time: 0ms

Stats for rule 'startNextColumn':
 - Number of Executions: 39
 - Total execution time: 414ms
 - Aver. execution time: 10ms

Stats for rule 'extendNextColumn':
 - Number of Executions: 1521
 - Total execution time: 60086ms
 - Aver. execution time: 39ms

We see for every rule the number of applications, the total execution time and the average execution time of the rule. Ok, now we see where the bottleneck is! It is the rule extendNextColumn which is applied 1.521 times and takes on average 39ms for one execution, summing up to about one minute. So, why is this rule so slow? The reason is that in the used version of the example, the nodes of the left-hand side of the rule are ordered in a way which is highly inefficient for the match finding. But wait, didn't I say before that Henshin uses heuristics to find optimal search plans? Yes, indeed. So why does it not work here? Well because above, I initialized the interpreter engine with this line:

engine.getOptions().put(Engine.OPTION_SORT_VARIABLES, false);

This turns of the automatic variable ordering, which is useful if you have optimized your rules yourself. By default, the option is enabled. If we use the automatic variable ordering for our example, we get these execution times:

Stats for rule 'extendFirstColumn':
 - Number of Executions: 38
 - Total execution time: 25ms
 - Aver. execution time: 0ms

Stats for rule 'startNextColumn':
 - Number of Executions: 39
 - Total execution time: 345ms
 - Aver. execution time: 8ms

Stats for rule 'extendNextColumn':
 - Number of Executions: 1521
 - Total execution time: 1662ms
 - Aver. execution time: 1ms

Et voila -- the whole transformation takes less than 2 seconds now! The main point that I wanted to show you here is that if you have a large transformation with many rule applications, it can be very useful to quickly use Henshin's ProfilingApplicationMonitor to find out where the performance could be improved. If you have an example where a particular rule takes in your eyes much too long, let us know on the mailing list and we will check whether the performance can be improved.

ECT 4

The Extensible Coordination Tools (ECT) are a set of plug-ins for the Eclipse IDE which are centered around the coordination language Reo. In the past, the ECT were hosted in a Subversion repository at the CWI Amsterdam. Since most of the ECT developers are no longer working at the CWI, we decided to manage the source code with a third-party provider for open source projects. ECT is now developed as a project at Google Code. We hope that this will open the project for new developers and make the tools more accessible to external users.

With the new home of ECT comes also a new build infrastructure and a new update / release strategy. We now deliver continuous updates so that we can more quickly react on problems or bugs. To reflect the new philosophy also in the version numbers, the new version of ECT is 4.0.0.X (where X is a date-based qualifier). Hence the name ECT 4.

To install ECT 4, please first make sure that you uninstall any old ECT versions. For this, click on Help - About Eclipse - Installation Details. Then uninstall all Reo features with versions below 4.0.0. To complete the uninstall process, restart Eclipse. Then you are ready to install ECT 4. Just point the Eclipse update manager to this URL: http://reo.project.cwi.nl/update. This is in fact the old ECT update site URL. Select the features you want to install and follow the installation instructions. Once you have upgraded to ECT 4, you can install updates as usual by clicking on Help - Check for Updates.

Note that the Distributed Engine feature is now part of the Reo Core Tools. Also, the conversion tools do no longer include the BPMN convertor because it required out-dated packages. We hope that we can migrate the BPMN converter soon to the new BPMN2 Modeler tools.

If you would like to get in touch with the development of ECT 4, you can check out the source code at our ECT project at Google Code. If you want to follow the news on ECT, you can subscribe to our mailing list. This is also the best place to ask questions or to get in touch with the developers.

Last but not least, here are some stats about ECT 4. I used the cloc script to count the lines of code.

--------------------------------------------------------
Language       files       blank     comment        code
--------------------------------------------------------
Java            1400       34962       83922      142259
Scala             63        1486        3063        6845
XML               45         316          40        3819
JSP               14         148          50         531
Bourne Shell       2         114          28         260
C                  4          59          14         250
CSS                2          18           0          79
C/C++ Header       3          21           8          78
make               1          15           8          62
Javascript         1          10           1          32
HTML               2           4           0          25
--------------------------------------------------------
SUM:            1537       37153       87134      154240
--------------------------------------------------------

A Probabilistic Merger for Reo

Reo is a coordination language or component-based systems which is based on the idea of plugging communication channels together using nodes. The channels in Reo are user-defined and can implement virtually any kind of communication or synchronization. What is typically fixed though in Reo is the notion of nodes. Nodes merge incoming data items and replicate them to all outgoing channel ends. The merging is technically more interesting and challenging, which is why in some papers, this behavior is modeled by a ternary component called a Merger, which is often visualized like this:

This component reads data items from a or b and writes them to c. If there is data available at both a and b, the choice for one of them is nondeterministic. If no additional fairness assumptions are made, the model really does not say anything about the policy for choosing between a and b.

The semantics of such a merger component can be formalized using Reo automata. In these automata, transitions are labeled by pairs of guards and dataflow actions, written as "g|f" where g is a guard and f is a dataflow action. The Reo automaton for the merger component is shown below on the left. It consists of only one state and two transitions. The label "ac|ac" is read as: if there are I/O requests on a and c, then there can be dataflow at a and c (analogously for "bc|bc").

The interesting thing about Reo automata is that they can also directly (without encodings) express context-dependent behavior. An example is the automaton for a PriorityMerger shown on the right. The "ac|ac"-transition is the same as in the nondeterministic merger but the transition for choosing b contains an additional constraint in the guard: a (that is the negation of a). This informally means that dataflow from b to c can occur only if there is no data item at a available. Thus, the choice between a and b is no longer nondetermistitic but prioritized to a. So far, nothing new. Ok, let's take a look at the following automaton.

This automaton is not a Reo automaton anymore, because its transitions form discrete probability distributions. This is very similar to probabilistic constraint automata. If you take a look at the two states on the right, they have essentially the behavior of an a-PriorityMerger and a b-PriorityMerger. So, depending on whether the autmaton is in the upper or the lower state, it favor either a or b. The interesting part is that whether it favors a or b is now random. From the initial state, there is one silent step where an initial random decision for either a or b is made (a is chosen with a probability p). Whenever data is available at both a and b, the automaton favors one of them as determined by its current state. Additionally, a coin is tossed to decide whether a or b should be favored the next time. Thus, we have modeled a merger where the choice for a or b is random. What is important here is that we still need context information, i.e. whether there are data items available or not. This is most likely also the reason why this notion of probabilistic mergers was not considered in probabilistic constraint automata (which cannot directly express context information).

The Achilles' Heel of Model Checkers

Implementing a model checker is a tricky business. There are a lot of pitfalls which can cause them to produce incorrect results or to become extremely inefficient. I recently stumbled on one particular performance problem in two very different state space generation and analysis tools: the PRISM model checker and the Henshin state space analysis tools. I am exaggerating of course by calling it an Achilles' heel, but the problem is severe as it caused both tools in some situations not to scale well for large models.

First a word on the two tools. PRISM is a really powerful model checker for quantitative (stochastic / probabilistic / timed) models. It has been applied to a lot of case studies and my personal experience is that it is very stable and, due to its symbolic engines, scales in general very well. For Henshin, I implemented the state space analysis tools myself, so obviously I think it is a great tool. ;)

Now to the problem: it occurred for certain kinds of models during the state space generation. The synopsis of the problem in both tools was that in the beginning the state space generation is really fast, but the larger the state space gets, the slower the generation was. To understand the source of the problem, let's take a look at this pseudo code for a state space generator (similarly implemented in PRISM and Henshin):

E = {}
X = [ init ]
while (!is_empty(X)) {
  x = pop(X)
  add(E,x)
  S = succ(x)
  for (s in S) {
    if (!contains(E,s)) {
      push(X,s)
    }
  }
}

E is a set of explored states (initially empty). X is a stack of unexplored states (contains the initial state in the beginning). Now the body of the while-loop is executed as long as there are unexplored states. In every iteration, the first unexplored state is popped from the list and added to the set of explored states. Then the set S of successor states of this states is computed. For every successor state, we check if it is explored already. If not, we add it to the list of unexplored states.

Now what is the problem in this piece of code? There is no problem specifically in this code. The issue lies in the implementations of the used collections. You should make sure you use a list implementation for X with constant complexity for pushing and popping elements (e.g. a linked list). But the real problem lies in the implementation of the set of states E, specifically in the used hash function (and in Henshin also the equality checker). In the state space generators, the hash function is used to assign a state to a memory slot. What is really important is that this hash function produces as few hash collisions as possible, because the state space sets tend to get very large and many collisions mean longer times for containment checks.

In the PTA state space generator of PRISM, states are pairs of a location and a zone (a symbolic representation of a time window). The implemented hash function computed the hash code only based on the location but not the zone. Now, if you have a system comprised of 1.000 locations and, say, 1.000.000 states, you have an average of 1.000 zones per state. If you use a simple hash function that uses only the location information, the hash code of every state collides with 1.000 other states. Thus, a simple containment check requires to iterate over all these states. And the larger the state space gets, the more collisions you get and the slower becomes the state space generation. By simply using a hash function that also takes into account the zones, the performance of the state space generator boosted from 438 to 12 seconds for one case of the CSMA example on my laptop.

In Henshin, I was facing the same problem, but here the solution was not so easy. In Henshin, states are essentially attributed, typed graphs (EMF models). Defining a good hash function for these models which can be efficiently computed is really not easy. Also, checking equality of states boils down to checking graph isomorphy -- a problem for which it is not even known whether it is in P. I think it took me 3 or 4 complete rewrites of the hash function implementation and the equality checker until it was running smoothly. If you are interested in the details, you can check out the source code of the hash function implementation. It is also the basis for the equality checker and, as I found out in a profiling session, it is the most often executed code during state space generation in Henshin. Maybe in one of my next posts I can explain some of its details.

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.

Ray Kurzweil's "How to Create a Mind"

We are not really up to date when it comes to communication technology. The mobile phone that my wife and I possess (yes, one for the two of us) resembles a pocket calculator from the 1980's. Two months ago I had to give a trial lecture for third semester students in computer science on the topic "Introduction to the Development of Mobile Applications". I talked about the new possibilities and challenges in the mobile sector and explained them how the lifecycle of an App in Android works. Overall I think I performed pretty well but I must say that I am very glad that none of the students asked for a demo on my mobile. Anyway, I decided that it is time to change something. I am still not convinced of smartphones, and so instead I got a Kindle Fire HD for my wife Carola for Christmas.

To be honest most of the time until now I was using the Kindle. The first e-book I read on the Kindle was "How to Create a Mind" by Ray Kurzweil. Ray Kurzweil is an icon in the Artificial Intelligence (AI) field and has worked for several decades on engineering intelligent systems. He worked a lot in the area of speech and text recognition. The research of his group led to a number of products that can be considered as the state of the art in intelligent systems. The most popular product is probably the Siri assistant that you may know from your iPhone.

In "How to Create a Mind", Kurzweil describes the state of the art in AI from a biological, a mathematical, and a philosophical perspective. One of the predominant messages of the book is that it is only a matter of a few decades until machines are more intelligent than humans. Kurzweil gives an overview of the structure of the human brain and describes the core concepts of thinking and learning in the neocortex. He describes thoughts as sequential and hierarchically structured patterns in the brain. An example of the hierarchy of patterns is (spoken) language: phonemes form words, words form sentences, sentences form stories. In a similar way, the brain organizes ideas and concepts into hierarchical structures with increasing levels of abstraction.

The sequential and hierarchical structure of patterns in the process of thinking and learning manifests also in the formalism of Hierarchical Hidden Markov Models (HHMMs) which Kurzweil uses and advocates in his book. In their core, HHMMs can be described as structured discrete-time Markov chains with observations. The process of learning involves to find (1) an optimal topology of the HHMM and (2) optimal transition probabilities, based on a training set that is given by sequences of observations. Problem (2) is the actual learning step and can be solved using variants of the Baum-Welch algorithm, whereas (1) can be solved using evolutionary algorithms.

One of the most often occurring criticisms of AI is that the used methods are just based on statistical models or manipulations of abstract symbols. In short: there is no real thinking going on, no awareness and no consciousness. Of course, Kurzweil defends AI, e.g., he argues that the whole decision making in the human brain is based on natural law and statistics. He describes an interesting situation where the AI system Watson was competing with the best two Jeopardy! players. Watson is based on statistical models and computes the probabilities of possible answers. For example, Watson's response to

“In Act 3 of an 1846 Verdi Opera, this ‘Scourge of God’ is stabbed to death by his lover Odabella” 

was “Who is Attila?”. The showmaster asked him (or it?) to specify the answer and Watson correctly responded with “Who is Attila the Hun?”. Kurzweil makes a point in saying that the understanding of the language used in the Jeopardy! questions (technically answers) is a real challenge and that Watson learned his knowledge by reading the whole Wikipedia and other human-written text resources, which marks a milestone in the engineering of artificial intelligence.

Kurzweil also gives some clues to the grand philosophical questions in AI which naturally arise when attempting to build machines that reach or exceed human intelligence. For a machine that acts like as if it were conscious and as if it had a free will, we should also assume that it is conscious and has a free will. Thus, Kurzweil believes that machines are conscious if they pass the Turing test. This topic is highly controversial as this excerpt from Wikipedia shows:

"Searle argues that the experience of consciousness can't be detected by examining the behavior of a machine, a human being or any other animal. Daniel Dennett points out that natural selection can not preserve a feature of an animal that has no effect on the behavior of the animal, and thus consciousness (...) can't be produced by natural selection. Therefor either natural selection did not produce consciousness, or (...) consciousness can be detected by suitably designed Turing test."

No matter whether you stand on the side of Kurzweil (as I on this question) or on Searle, I hope I was able to whet your appetite. If you are a computer scientist or generally interested in AI, I highly recommend to read "How to Create a Mind" (even if you don't own a Kindle).