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!

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.

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.

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.

Practical - end of first stage

The first stage of our practical on graph and model transformation is already finished. The students have produced nice class diagram editors with all three meta-CASE-tools. As expected, all tools have particular strengths and weaknesses.

GMF:

• Strong points: open source, integration with popular eclipse platform and EMF, wizards, tutorials


• Weak points: difficult to realize nested packages, internal metamodels not documented very well (students sometimes had to consult the generated code to understand the differences of particular options), graphics cannot be defined in a visual way

DSL Tools:

• Strong points: predefined skeletons, good documentation (in particular the book "Domain-Specific Development with Visual Studio DSL Tools"), good error messages, visual mapping between abstract and concrete syntax


• Weak points: generated editors need Visual Studio, arrangement of the metamodel as a tree is rather confusing, nested packages difficult to realize

MetaEdit+:

• Strong points: good documentation, many examples, changes to graphics and metamodel on the fly, integrated code generator, nested packages possible


• Weak points: generated editors need MetaEdit+, project portability, too many open dialogs in particular situations

The students have learned that domain specific languages can be realized with modern tools very conveniently.

VEX

VEX (visual expressions) is a VL for the representation of lambda expressions.


The picture provides two exemplary VEX expressions. The upper one represents the lambda term λy.(x y), i.e. a function that applies the free variable x to its argument. The other one represents the term λx.λy.(x y). Here variable x also is bound by an abstraction.

VEX is a very simple visual language in the sense that there are only three different visual components: the circle, the line and the arrow. The whole meaning of an arrangement of these components is determined by their spatial relations.


A lambda term is inductively defined. It is either a variable, an application of one lambda term to another one or an abstraction that consists of the variable to be bound and its body, i.e. the scope of the particular variable. For these three cases visual representations are defined.

In VEX a single variable is represented by a circle. It does not need to have a name as in the textual form. An abstraction is represented by a circle with a smaller circle internally tangent to it. Elements contained in the bigger circle are part of the abstractions body whereas the smaller circle represents the parameter. The application of an expression e1 to an expression e2 is represented by an arrow that points from e1 to e2. Further the outermost circles of e1 and e2 have to touch each other.

Variables can be bound via lines to parameters of abstractions. If they are free they need to be bound to a free variable circle that must not be inside another circle. The meaning for this is that it has to be possible to identify occurrences of the same free variable.

The main purpose of VEX is to simplify the teaching of lambda calculus. For this sake it is very benefitial that variable bindings are made explicit by lines and not implicitly hidden behind equal names. In particular one does not have to deal with the difficulties resulting from overlapping scopes and thus the need for alpha conversion.



Syntax analysis for VEX diagrams is quite difficult. There are ambiguities (i.e. to circles connected by a line, which one is the variable and which one the free variable circle?) and a lot of combinations of particular patterns and their spatial arrangement. However, there is a quite flexible DiaGen editor for VEX where the language is defined via a hyperedge replacement grammar. However, as you see in the picture "two different kinds of circles" need to be defined restricting the freedom of the user somewhat.

Practical on Graph and Model transformation

I have already written several posts regarding our seminar on graph and model transformation. The next three months we conduct a practical on graph and model transformation on top of this seminar.

The first task is the implementation of an editor for UML class diagrams (restricted to classes, attributes, generalizations and a limited notion of associations). However, the editor should, of course, not be implemented from scratch. Rather it should be generated using a meta-CASE-tool. We have divided the students in three small groups. Each group has to use a different meta-CASE-tool. The tools to use are:

• MetaEdit+ by MetaCase, I already have written about MetaEdit+


• GMF, an eclipse project


• DSL Tools by Microsoft, a framework based on MS Visual Studio

Whereas MetaEdit+ and DSL Tools are commercial products, GMF is open source. All three tools have in common that they are of sufficient quality and well-documented, making them suited for our practical.

Course on Graph and Model transformation

My name is Steffen Mazanek and I am a scientific assistant at the department of computer science of the Universität der Bundeswehr, Munich. Here I work on my PhD thesis in the field of visual languages. My supervisor is Prof. Mark Minas.

I am also involved in teaching. For instance, this semester we conduct a course on graph and model transformation. I think this is a good starting point for this new blog on visual languages. So my first posts will be about the topics of the students presentations. In the next semester we plan to conduct a practical to give the students hands-on knowledge about common tools in this domain. This is also going to be interesting.

Further on I will present and discuss interesting research papers from this domain here in brief. So, stay tuned.