MPS released

JetBrains just released version 1.0 of its Meta Programming System.

The screencasts provided by Markus Völter are very nice. They show how the Java base language can be extended by a lock abstraction, which is translated to some best practice lock code by the generator component afterwards. This seems to be a good example of growing a language as motivated by Guy L. Steele Jr.

I wonder whether multiparadigm programming could be supported that way more straightforwardly. So, one could not only generate imperative code from imperative abstractions, but one also could generate imperative code from an embedded functional program, right? Also it seems to be promising to integrate visual languages. That way, one could specify a method's body not only by Java code, but alternatively with, say, activity diagrams. However, currently only the creation of editors for textual and tabular representations seems to be supported.

All in all, MPS is a promising system, but regarding performance there seems to be plenty of potential for improvements (it took really long to load the simplest possible language for the first time, which raises the question how long it would take to load something real - on the other hand the system seems to be bootstrapped, which usually is an indicator of maturity). The language oriented programming approach as a whole of course is also heavily disputed, cf. this discussion.

Alligator Eggs (for the last time)

Now I have also constructed an editor for alligator eggs. This editor is different from Torsten's editor with the nice animation discussed some days ago. My editor provides syntax-based user assistance instead, i.e. the user gets help in creating syntactically correct alligator eggs expressions. Whereas Torsten's editor has been created with DiaMeta (syntax defined by a class diagram), my approach relies on the DiaGen framework (syntax defined by a graph grammar).

Here is a screencast:


And here is the executable jar.

The underlying hyperedge replacement grammar is very straightforward and close to the textual lambda grammar:

Alligator Eggs revisited (again)

The video about the animated editor for Alligator Eggs has raised some questions on where the editor is available for download. Therefore, Torsten has provided an executable jar. Feel free to try it out yourself!

Actually, the success of this video on youtube (more than 3.000 views already) really motivates me to implement syntax-based assistance for the language of alligator eggs. The language is tree-based, i.e., context-free, so that the developed approach is applicable. I hope to find some time in the near future to this end.

Business Process Models

In the last weeks I have developed an editor for business process models with syntax-based user assistance as described in previous blog posts. A screencast of this editor is shown below:



The editor is provided for download as an executable jar.

Concepts and realization are described in S. Mazanek, M. Minas. Business Process Models as a Showcase for Syntax-based Assistance in Diagram Editors. Appears in Proc. of the ACM/IEEE 12th International Conference on Model Driven Engineering Languages and Systems (MODELS 2009), 2009. The original publication will be available at www.springerlink.com.

Alligator Eggs revisited

At the moment I spend a lot of time on polishing my PhD thesis. Therefore, not so many new posts appear on this blog in these days. However, today I would like to follow up on my last post, which was about the visual language of alligator eggs. A colleague of mine, Torsten Strobl, has created a very nice editor for alligator eggs expressions. It even animates the evaluation of such expressions, i.e. alligators eat other alligators (but don't worry, there is no blood).

Here is the video:

Alligator Eggs!

Some time ago I had already written about a nice visualization of lambda calculus called VEX (visual expressions). In VEX the variable bindings are made explicit by using connecting lines. In contrast, in conventional lambda calculus bindings are implicitly given by the names of the variables. From my experience this is difficult to understand for students, in particular if alpha conversion comes into play. Today I have seen an even nicer visualization for the representation and execution of lambda expressions called Alligator Eggs!.

For motivation, here is an example expression from the Alligator Eggs! website:



Very briefly: A hungry alligator is an abstraction, an old (=uncolored and non-hungry) alligator can be used for bracketing, and eggs represent variables. There is an eating rule, which corresponds to beta-reduction, and a color rule for over-cautious alpha-conversion. Finally, for clean-up, there is an old age rule, which says that if a pair of parentheses contains a single term, the parentheses can be removed.

I really look forward to empirical results whether this approach helps in teaching lambda calculus.

Graph Transformation Day Bremen

Directly after the World Usability Day in Dresden I attended the Graph Transformation Day in Bremen. Here, I gave a talk about the generation of correctness-preserving editing operations for diagram editors. More on this later...

The other talks have been given by my supervisor Prof. Mark Minas (about using triple graph grammars for analysis in diagram editors), Dr. Rubino Geiß, the architect of the GrGen graph transformation engine (and indeed his talk was about the implementation and application of GrGen), and finally Edgar Jakumeit, who described the realization of recursive matching rules for GrGen. I have found these recursive "star" rules particularly interesting, because they actually allow to write parsers with GrGen in a declarative style. In a sense, this is quite similar to my approach to graph parsing via combinators.

It was a nice workshop. I learned a lot about the GrGen system. In particular I now have an idea how they managed to build the fastest (at least in quite some cases) graph transformation tool in the wild. Thank you Berthold for organizing this...

World Usability Day Dresden

Last Thursday I gave a talk at the World Usability Day Dresden with the title "Nutzerunterstützung in Diagramm-Editoren zum Erlernen visueller Sprachen" (in English: User assistance for diagram editors supports the learning of visual languages). I provide an abstract of my talk (in German) on my website. I got quite encouraging feedback and some nice tips on how to actually conduct a user study.

All in all, I really liked this workshop. It was well organized by Jan-Henning Raff from the media center of TU Dresden. There have been round about 50 participants listening to the ten talks. Although I am not a usability expert (I just start exploring this domain), I learned a lot from most of the talks. In particular I enjoyed the talks about tools:

• Jürgen Steimle introduced the CoScribe-System, an impressive pen-and-paper-interface for collaboration based on the Anoto approach.


• Stefan Meißner from seto company talked about Enterprise 2.0 and introduced a nice WYSIWYG editor for websites.


• Severin Taranko from queo media demonstrated a WordPress plugin that gives visitors of your blog an overview over the most relevant and popular articles of your blog (using some reasonable criteria).


• Robert Jung motivated the use of sketch tools for CAD. In particular he showed a nice video of a tool developed at the university of Toronto: ILoveSketch. There is a nice video on the tool's website.


• Prof. Gerhard Weber and one of his students talked about accessibility in (web) applications. They have improved the accessibility of the Moodle learning platform for blind people. Furthermore, they have studied how blind and non-blind people collaborate in the creation of UML class diagrams.

The day was completed by a "Usa-beer" evening in a nice bar of Dresden.

Roughly sketch your diagrams

In recent posts I have already demonstrated the power of diagram completion.

In the paper I have presented at this year's LED workshop, I have shown how diagram completion can be used in order to facilitate a completely novel(?) approach to diagram editing. It is enough to just roughly sketch your diagram. You do not need to hit the mark quite precisely anymore as required in traditional diagram editors. Rather the completion engine computes all ways, how the diagram can be put together. Thereafter, the completion causing minimal change to the layout of existing diagram components is selected automatically! I am quite sure that this feature can boost the accessibility of diagram editors.

Example:

This figure shows how tedious the manual correction of a roughly sketched diagram can be. At least three complex mouse dragging operations are necessary here. The completion engine would yield two results for this example, the diagrams A and B given in the upper row. However, it is quite clear which diagram the editor user would prefer: the one with minimal changes to his components, namely A. A shortcut that automatically applies completion A could greatly improve editing performance.

However: This approach is only possible as long as there are not too many possible compositions of the fragements. For instance, n disconnected NSD statements can be put together in n! ways. As a consequence, the user would have to invoke the completion engine every few steps. Even so, this kind of assistance is still useful.

• S. Mazanek, S. Maier, M. Minas. Exploiting the Layout Engine to Assess Diagram Completions. Proc. of the 2nd International Workshop on Layout of (Software) Engineering Diagrams (LED 2008), 2008. Electronic Communications of the EASST.

Visual Week up and running

The Visual Week in Herrsching, Germany is already up and running. Yesterday the Workshops Layout of (Software) Engineering Diagrams and Sketch tools for diagramming took place. I attended LED where I gave a talk with the title "Exploiting the Layout Engine to Assess Diagram Completions" (paper and slides). But I also really enjoyed the other talks that covered a wide range of topics from industry projects to sophisticated graph layout approaches. A highlight was the 3D UML Heuristic Challenge. We have been divided in several groups and had to solve given tasks. My group had to think about the differences in 2D and 3D usability heuristics and, subsequently, evaluate a given tool using the heuristics we just developed.

Today the ACM SoftVis conference has started and a graduate consortium took place (many exciting new ideas!).

Usability

In this post I briefly discuss usability. First of all, I have to say that there is so much research that it is nearly impossible to write a short blog post about this topic. For instance, Jakob Nielsen, a popular usability expert, writes about usability for years. So I will just give you a quick impression by introducing the GOMS approach, which I found very straightforward and easy to apply. I especially use it to evaluate the task performance of my approach to diagram completion.

GOMS is an acronym for Goals, Operators, Methods, and Selection rules. The approach, however, is much easier than these terms suggest. The key idea is, that you write down all operations that have to be performed in order to achieve a given goal. Depending on its kind a predetermined execution time is attached to each of these operations. For instance, a keystroke takes 0.28 seconds for an average user, pointing with the mouse to an object on the screen lasts round about 1.1 seconds. There are several more kinds of actions and appropriate average times (determined on an empirical base). Summing up the times for all necessary operations finally yields the task execution time. Once you have this time you can compare different user interfaces, you can evaluate changes to the user interface and so on. It's that easy.

Note that in the context of the Visual Week (15.-21.09.08 in Herrsching am Ammersee, Germany) there will be a tutorial on another popular usability approach called Cognitive Dimensions. Here, usability is evaluated on a much higher level. To quote from the tutorial website (accessed 19 July 2008):
The Cognitive Dimensions of Notations (CDs) framework is the world's leading approach to understanding the usability of programming tools. It provides an analytic framework and design vocabulary that can be used to evaluate and improve, not only programming languages, but a wide variety of environments and notations for design, problem-solving, and creative work.

Currently I apply usability evaluation methods to my approach on diagram completion. In my talk "Exploiting the Layout Engine to Assess Diagram Completions" to be held at the layout workshop LED 2008 (satellite event of VL/HCC 2008) I will present a first improvement: in certain situations a special shortcut can more than double the task performance (to speak in terms of GOMS). Stay tuned!

Further reading:

• Stuart Card, Thomas P. Moran and Allen Newell: The Psychology of Human Computer Interaction. 1983.


• GOMS Model Work, comprehensive website about GOMS maintained by David E. Kieras.

RTA 2008

I am just back from the RTA 2008 (Rewriting Techniques and Applications) conference in Linz. My talk has been on Wednesday and was about Functional-logic Graph Parser Combinators. I already have written on this blog about graph parser combinators, but this purely functional approach had several problems we solved using functional-logic programming techniques. In particular, the new framework can be used as a back-end for my approach to diagram completion.

Hagenberg, the conference location, is a nice little village 20km away from Linz. It has a romantic, medieval castle in which the conference took place. Furthermore, an important branch of the FH Oberösterreich is located here.

From the talks I attended I especially liked the invited one by Thomas Hillenbrand about the theorem prover Waldmeister which is known to be very fast and powerful. Recently, the popular computer algebra system Mathematica even incorporated the Waldmeister approach to equational theorem proving into its tool suite.

Although I do not know much about automatic theorem proving there have been some impressive facts I remember from the talk. First of all, it is still very important to think about the most efficient data structures for a particular application. In theorem proving execution time and memory usage are really a big issue, so every little improvement of the data structures might make a decisive difference. And second, there is no all-in-one algorithm suitable for every application domain. Thus, it is important to provide a flexible framework that can be parameterized by the users. In Waldmeister one has to choose among several weighting functions from which each one is superior for some special domains. Finally, automatic theorem proving has advanced a lot in the last years. Even for some "real proofs" there is a good chance that they can be found without much manual investigation.

Logic gates

In previous posts I already have discussed several visual languages like VEX, Trees or ER diagrams. These languages have in common that all of them are used by computer scientists. Of course, visual languages also exist in other domains (in fact, visual notations are much older than computers).

In this post I show an editor for a language mainly used by electrical engineers: Logic gates. This is a visual notation for logic expressions that can be used in the domain of circuit design. Expression languages normally are context-free (although often some kind of sharing is used that cannot be described in a context-free way).

Again my approach to diagram completion is applicable, so we get a powerful editor for logical expressions. Here is a screencast demonstrating its use:



I also provide this screencast at an extra site, if this one is two small. You can also download this logic editor as an executable jar (however, keep in mind that this is still a research prototype).

Finally, let me admit that in the last time the most posts have been related to my own approach. I hope you forgive me this way too restricted focus. I will soon attend ICGT and VL/HCC conferences and the LED workshop, where I surely get inspiration for other interesting topics. You might also consider suggesting topics you are interested in for discussion. Of course, if you want to write something about a fancy tool, I gladly publish your description here as a guest contribution.

Course on Visual Languages

I already have written several posts about our previous course on graph and model transformation conducted in autumn last year and the practical afterwards. Next autumn we will hold another course, this time directly on visual languages. We will discuss approaches to language definition like extended positional grammars, constraint multiset grammars, hyperedge replacement grammars, and, of course, metamodels. I look forward to report on these approaches here soon.

Similar courses and practicals have been conducted at several universities in the past (e.g. at Universität Bremen (Berthold Hoffmann), CAU Kiel (Hauke Fuhrmann), RWTH Aachen (Manfred Nagl), Philipps-Universität Marburg (Gabriele Taentzer)). I would appreciate very much any comments on the lessons learned while conducting these courses.

Trees

Trees are a central data structure in computer science. A lot of visual languages have a tree-like structure, for instance class hierarchies with single inheritance, family trees or organizational charts. In contrast to the language of all graphs the sublanguage of trees can be described in a context-free way with a hyperedge replacement grammar:



However, this straightforward definition is problematic: A given tree might have a lot of derivations, i.e., the grammar is highly ambiguous. It is simply not clear in which order sibling nodes have to be derived. Therefore, it might be a better idea to encode this order in the grammar explicitly:



An example tree then is represented as follows:



Since my approach to diagram completion is applicable to all visual languages that can be defined with hyperedge replacement grammars, a powerful tree editor with completion can be realized easily. Here is a screencast demonstrating its use:



I also provide this screencast at an extra site, if this one is two small. You can also download this tree editor as an executable jar (however, keep in mind that this is still a research prototype).

Constraint Logic Programming and Diagram Completion

I got stimulating feedback after my last post on diagram completion. For instance, I was not aware of the SmartEMF project of Anders Hessellund et al. They aim at extending EMF with an inference engine to facilitate reasoning about models. Interestingly, they also get some guidance that way. A similar approach has been realized in the AToM3 tool by Sagar Sen et al. They also employ constraint logic programming to infer model completions.

The diagram completion presented in my last post has been incorporated into the DiaGen tool which is based on hyperedge replacement grammars. However, metamodels are more popular nowadays for language specification. I already introduced the DiaMeta tool on this blog. It is based on DiaGen, but allows the generation of free-hand editors out of a metamodel-based specification. Syntax analysis then can be mapped to the solution of a constraint satisfaction problem. It would be interesting to see if the approaches of Hessellund and Sen could be used to get similar diagram completion for DiaMeta.

Dear readers, please continue to comment on my posts or give feedback by mail. I appreciate this very much. If your own project is related somehow to visual languages, do not hesitate and send me a short summary. I gladly post and/or discuss it here on this blog.


Further reading:

• Anders Hessellund, Krzysztof Czarnecki, Andrzej Wasowski: Guided Development with Multiple Domain-Specific Languages. In Proc. of MODELS'07, 2007


• Sagar Sen, Benoit Baudry, and Hans Vangheluwe: Domain-specific model editors with model completion. In Multi-paradigm Modelling Workshop at MoDELS'07, 2007.


• Mark Minas: Syntax analysis for diagram editors: A constraint satisfaction problem. In Proc. of the Working Conference on Advanced Visual Interfaces (AVI'2006), 2006.

Diagram Completion

Recently I have been working on an approach to diagram completion. This kind of assistance helps users in correcting and extending diagrams. That way they can learn new languages much more easily. Furthermore, the construction of complex diagrams is also greatly simplified.

Following my approach, completions are computed on the abstract syntax level with respect to a hyperedge replacement grammar. Thereafter, they are embedded into the diagram by the layout engine. The details are provided in the papers given below.

For motivation I provide a screencast that shows how diagram completion actually has been realized in the DiaGen system. I also provide this screencast at an extra site, if this one is two small:



I also provide this editor for Nassi-Shneiderman diagrams as an executable jar.

If you are interested you might want to attend VL/HCC 2008 where I will give a talk about the overall approach. (If you are not interested in this you should join the conference anyhow. Early registration is still possible :-))

Further reading:

• S. Mazanek, S. Maier, M. Minas. Auto-completion for Diagram Editors based on Graph Grammars. Appears in Proc. of the 2008 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2008), 2008. IEEE Computer Society Press.


• S. Mazanek, S. Maier, M. Minas. An Algorithm for Hypergraph Completion according to Hyperedge Replacement Grammars. Appears in Proc. of the 4th International Conference on Graph Transformation (ICGT 2008), 2008. LNCS.

Sierpinski Triangles

I have already introduced my approach to graph parsing via Graph Parser Combinators on this blog recently. This time I provide a nice sample parser; at RTA I will present the concepts and how the used framework can actually be realized in the functional-logic programming language Curry.



The example I am going to discuss are Sierpinski triangles. This graph language is particularly interesting for several reasons. First of all, Sierpinski triangles are beautiful thanks to their self-similarity. Second, they can be described by a hyperedge replacement grammar as shown in the image below. And finally, depending on the generation, Sierpinski triangles grow exponentially in size making them an ideal candidate for tool benchmarks (see Taentzer et al. '08).



Note that the given grammar does not ensure that only regular Sierpinski triangles are generated. For instance, the graph shown below is also a member of its language. Regularity can be enforced by using a parallel replacement mechanism or control structures, though (see Habel, Kreowski '87).



Let's see how we can map this grammar to a parser using our framework:

s (Succ depth) (n1,n2,n3) = s depth (n1,n4,n5) *> 
                            s depth (n4,n2,n6) *>
                            s depth (n5,n6,n3)
                            where n4,n5,n6 free
s One (n1,n2,n3) = edge ("line",[n1,n2]) *> 
                   edge ("line",[n2,n3]) *>
                   edge ("line",[n3,n1]) 

sierpinski = s depth (n1,n2,n3) 
             where depth,n1,n2,n3 free

The actual mapping is described in the RTA paper, but you will probably have no difficulties figuring out how it works. Note that inner nodes of a production are guessed using free variables. The regularity is ensured by a parameter depth. As a parser these functions are not very interesting, since parsing can't be done efficiently. However, due to the logic nature of the framework, it can be directly used for the generation of Sierpinski triangles. Compared to other tools (see Taentzer et al. '08) this generation even is reasonably efficient. For instance, we have generated a Sierpinski triangle of generation 11 with nearly 200.000 edges in about a minute.

Further reading:

• Sierpinski Triangle for the AGTIVE 2007 Tool Contest


• G. Taentzer et al., Generation of Sierpinski triangles: A case study for graph transformation tools. In: Applications of Graph Transformations with Industrial Relevance AGTIVE ’07 (eds.: A. Schürr, M. Nagl, A. Zündorf), International Workshop Kassel, Oct. 10-12, 2007, LNCS, Springer, 2008


• A. Habel, H.-J. Kreowski, Pretty Patterns Produced by Hyperedge Replacement, Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, Springer, 1987


• S. Mazanek, M. Minas, Functional-logic Graph Parser Combinators. To appear in Proceedings of 19th International Conference on Rewriting Techniques and Applications (RTA 2008), LNCS, Springer, 2008

Fujaba and Story Driven Modeling

Let's continue talk about our practical on graph and model transformation. In fact, it is already finished, but unfortunately I did not managed to write about the other stages in time. Remember, that in the first stage a UML class diagram editor had to be developed by the student teams using different meta-CASE-tools. The second stage, in contrast, was focused on transformations. The students had to deal with the simulation of finite state machines and pushdown automata using different research tools, namely AToM3, Tiger and Fujaba. At the end, all teams presented quite appealing solutions.

Fortunately, a student of the Fujaba-group, Thore Backen, has been willing to provide us a summary of his insights about the practical work with Fujaba:

In the second stage of our practical on graph and model transformation our group of three students had the objective to produce the simulation of deterministic as well as nondeterministic finite automata using Fujaba.

At first we needed quite some time (approx. 15 h) of practice to get used to Fujaba. To be honest we had some trouble deciding which version to use for our task. In the end we chose the Fujaba Tool Suite Version 4.3.2. The main reason why we chose this version over the more up-to-date version 5.0.4 was the easy-to-use already integrated Dynamic Object Browsing System (DOBS) in the older version. Since we wanted to use DOBS to simulate our finite automata, the outsourced eDOBS (in Fujaba 5) needing Eclipse did not offer any obvious advantages.

As usual, our first step has been the development of a model, i.e., a class diagram of our application domain (click image to enlarge):



The dynamic behavior of a system then can be specified via so-called story patterns. For instance, the story diagram for the firing of a deterministic finite state machine is shown in the screenshot below:



After getting used to modeling with story patterns, which by the way presented itself to be quite intuitional, we learned that simple, figurative designs produced powerful code. After all, we did not write one line of code ourselves throughout the whole phase of the practical. Having needed adequate time to adjust to a new way of thinking, i.e. modeling, Fujaba enabled us for the rapid production of a stable solution to our problem.

Although allowing us to solve our task conveniently, there were some drawbacks working with Fujaba as well. The integrated diagram editor was sometimes hard to use, e.g., the handles on associations were too small to move them comfortably and the automatic layout often scrambled diagrams even more rather than clarifying them. Manual adaption of the generated code, although not needed in the end, was not even possible. Furthermore, the integrated versioning support CoObRA did not work at all on our systems. Due to the fact that diagrams grow rather quickly utilizing story driven modeling we believe that the use of Fujaba is limited to small or medium-sized projects.

In summary, Fujaba offered us a quick, well visualized way to implement the simulation of finite automata. The simulation of these automata using the integrated DOBS is more practical than beautiful, but proved to be sufficient for our purposes.

GT-VMT, MetaEdit+

I am back from Budapest where I have attended the GTVMT workshop and ETAPS. The feedback to my talk about graph parser combinators was positive and I even have been pointed to very useful and interesting references later. I will provide a more detailed post about my stay in Budapest soon.

Let me just point you to an up to date news from the DSL tool market. I have already written about the MetaEdit+ tool. You might be interested in the news that this week MetaCase rolled out a new version of their tool as announced by the company's sales manager James Hammond. I have not tried the new version yet, so if somebody has tried it already: please leave a comment on your impression.

By the way, the CEO of MetaCase, Dr. Tolvanen, gave an interesting talk (slides) about the state of the art in the domain of DSL tools and the great speed ups that are possible with proper tool support. A main practical issue I have not been aware of before was the problem of a changing metamodel. According to Tolvanen MetaEdit+ is quite good at dealing with this issue due to its repository approach. I wonder how other tools deal with this issue. Any comments on this?