The Joys of Graph Transformation
Arend Rensink · 2005
We believe that the technique of graph transformation offers a very natural way to specify semantics for languages that have dynamic allocation and linking structure; for instance, object-oriented programming languages, but also languages for mobility. In this note we expose, on a rather informal level, the reasons for this belief. Our hope in doing this is to raise interest in this technique and so generate more interest in the fascinating possibilities and open questions of this area. 1 Graph Transformation Is Easy Transformation means changing (literally: shaping) one thing into another. In the case of graph transformation, obviously, the things being changed are graphs. A fundamental assumption in studying such changes is that they are not arbitrary but controlled by some guiding principles, and that these principles can be captured in rules. A graph transformation rule (often called a production rule) describes a kind of change that will transform certain graphs — those to which the rule is applicable — into others, in a specific way encoded in the rule. A set of production rules is usually called a production system; graphs