|
IPD Goos - GrGen.NET
参考：http://www.info.uni-karlsruhe.de/software/grgen/
|
GrGen.NET: transformation of structures made easy. |
|
The Graph Rewrite Generator offers declarative languages for graph modeling, pattern matching, and rewriting, as well as rule control; brought to life by a compiler emitting highly efficient assemblies and a rapid prototyping environment offering graphical and step-wise debugging. |
|
Contents:
» Description » Look'n'Feel » Download » Documentation » Benchmark » Papers » Known uses » History » Contact
Description
GrGen.NET is a programming tool for graph transformation, which eases the transformation of complex graph structured data as e.g. required in model transformation, computer linguistics, or modern compiler construction, comparable to other programming tools like parser generators which ease the task of formal language recognition, or relational databases which ease the task of persistent data storage and querying. Graph rewriting is the high-level way of processing pointer structures. GrGen.NET allows you to work at the abstraction level of graphs, with declarative pattern matching and rewriting, on a visualization of your mesh/network of objects, instead of low level pointer structure fiddling, chasing objects by following references in the debugger.
GrGen.NET (Graph Rewrite Generator, see Wikipedia for an explanation of graph rewriting, deutsch: Graphersetzung) features an intuitive and expressive domain specific specification language for graph rewriting and implements a modification of the theoretically well-founded SPO approach to graph rewriting (DPO available as well). The program code generated by GrGen executes very fast and is easy to invoke through a comfortable API. According to a benchmark introduced by Varró the performance of rewriting, especially of the potentially costly pattern matching, is at least one order of magnitude faster than of any other known system. In most cases GrGen.NET outperformes the other systems even by some complexity classes. We achieve this by using specially tailored data structures and by a dynamically optimizing approach to subgraph matching, which means that the pattern matchers can be recompiled at runtime to maximally exploit the structure of the actual present host graph. In this context we use the concept of search plans to represent different matching strategies. By stating a cost model we understand the generation of good search plans as an optimization problem, which we solve heuristically. In contrast to systems like Fujaba our pattern matching algorithm is fully automatic and does not need be tuned or partly be implemented by hand. Due to its textual specification languages, you can easily generate GrGen-specifications on your own, or diff specification changes.
A while ago we re-implemented the original GrGen system (written in Java/C, yielding a C based virtual machine interpreting the matcher). The result of this effort is the new GrGen.NET system for graph rewriting (written in Java/C#, yielding C# code implementing the matcher). Its core is the Graph Rewrite Generator, which turns declarative rewrite specifications into .NET assemblies performing the rewrites. The GrGen.NET system consists of the generator written in Java and C#, a graph backend written in C# and the .NET assemblies generated by the generator. The system - available under Windows and Linux - is open source licensed under LGPL v3, you find the code in the download section (public mercurial repository).
 Structure of the GrGen.NET system The process of graph rewriting can be divided into four steps: Representing a graph according to a model (creating an instance graph), searching a pattern aka finding a match, performing changes to the matched spot in the host graph, and, finally, selecting which rule(s) to apply where next. We have organized the presentation of the features of GrGen.NET according to this breakdown of graph rewriting.
- The graph model (meta-model) supports:
- Typed nodes and edges, with multiple inheritance on types
- Directed multigraphs (including multiple edges of the same type)
- Undirected and arbitrarily directed edges
- Node and edge types can be equipped with typed attributes (like structs) including generic set, map and array types
- Connection assertions to restrict the "shape" of graphs
- Turing complete language for checking complex conditions
- The pattern language supports:
- Plain isomorphic subgraph matching (injective mapping)
- Homomorphic matching for a selectable set of pattern elements, so that they may match (non-injectively) the same graph element
- Besides SPO, three additional modes for the semantics of a rule application can be choosen: matching of exact patterns only, matching of induced subgraphs only, and DPO semantics
- Attribute conditions (e.g. arithmetic-,boolean-,string- or set-expressions on the attributes)
- Type conditions (including powerful instanceof-like type expressions)
- Nested patterns, specifying negative and positive application conditions as well as iterated, optional, or alternative structures
- Subpatterns for pattern reuse, allowing via recursion to match substructures of arbitrary depth (e.g. iterated paths) and breadth (e.g multinodes)
- Parameter passing to rules and subpatterns
- The rewrite language supports:
- Keeping, adding and deleting graph elements according to the SPO approach
- Choosing out of three additional rule application semantics: DPO or exact patterns only or induced subgraphs only
- Attribute re-/calculation (assigning the result of e.g. arithmetic expressions to the attributes)
- Retyping of nodes/edges (a more general version of casts known from common programming languages)
- Creation of new nodes/edges of only dynamically known types or as exact copies of other nodes/edges
- Two modes of specification: A rule can either express changes to be made to the match or replace the whole match
- A rewrite part for the nested patterns and subpatterns, so that complex structures can not only get matched (parsing), but also get rewritten (transduction)
- Embedded graph rewrite sequences capable of calling other rules (with access to the nodes/edges of the rule)
- Emitting user-defined text to stdout or files during the rewrite steps
- Visited flags and storages to communicate between rule applications using state
- Parameter passing out of rules and subpatterns
- The rule application control language (xgrs: extended graph rewrite sequences) supports:
- Rule execution
- Logical and sequential connectives
- Loops
- Variable handling
- Basic graph querying and manipulation
- Visited flags and storages management
- Extended control (e.g decisions, transactions, backtracking, indeterministic choice)
- Sequence definitions (procedural abstraction)
- These constructs combined allow to program a state space enumeration
- The rapid prototyping environment
These were the features of the core of the GrGen.NET-System, the generator grgen.exe and its languages plus its runtime environment libGr. In addition, the GrGen.NET system offers a shell application, the GrShell, which features commands for:
- graph management,
- graph validation,
- graph input and output,
- graph change recording and replaying,
- graph manipulation,
- graph and model queries,
- graph visualisation (including nested graphs keeping large graphs understandable),
- action execution,
- debugging,
- backend selection and usage.
The debugging and graph visualisation commands are implemented in cooperation with the graph viewer yComp; combined with the expressive rules they allowed us to win both of the GraBaTs live contests held (GraBaTs 2008, GraBaTs 2009), which were measuring the expressiveness and rapid prototyping abilities of the competing graph based tools.
Alternatively to GrShell, you can include the graph model and rewrite rules directly into your code and/or access them through LibGr. This way you can build your own applications with a graph rewriting core in a .NET language of your choice.
Look'n'Feel
Koch snowflake generation debugging in GrGen.NET (GrShell, yComp); rule, match highlighted |
Koch snowflake generation debugging in GrGen.NET (GrShell, yComp); rule, rewrite highlighted |
 An excerpt from the model file of the GrGen.NET specification solving the Antworld-challenge posed at Grabats 08
 An excerpt from the rule file of the GrGen.NET specification solving the Antworld-challenge posed at Grabats 08
Download
You can download a binary package of GrGen.NET and the outdated GrGen C:
Documentation
Benchmark
This benchmark was introduced by Gergely Varró. The benchmark itself is described in a tech report. A more high-level description as well as runtimes for several graph rewrite systems are given in a paper by Gergely Varró, Andy Schürr, and Daniel Varró. Extensive benchmark results can be found on a website maintained by Gergely Varró. The original measurements carryied out by Varró contained some flaws, being described in our paper On Improvements of the Varro Benchmark for Graph Transformation Tools. The figures below reflect the improvements suggested by this paper. To get a better insight at the performace of the faster tools we performed measurements far beyond the size suggested by Varró.
 Note the logarithmic scaling of the time axis.
 Note the logarithmic scaling of the time and the size axis.
 Note the logarithmic scaling of the time and the size axis. The benchmark was conducted using the LGSP backend of GrGen.NET on an AMD Athlon(tm) XP 3000+ running SuSE Linux 9.3 with 1 GiB main memory.
The runtime displayed includes the whole rule applications i.e.: matching, rewriting, cleanup, and the overhead executing the rewrite sequences.
Papers
This is a small selection of papers on GrGen and GrGen.NET, a full list is available here:
- Geiß, Batz, Grund, Hack, Szalkowski, GrGen: A Fast SPO-Based Graph Rewriting Tool
- Kroll, Geiß: Developing Graph Transformations with GrGen.NET
- Batz, Kroll, Geiß: A First Experimental Evaluation of Search Plan Driven Graph Pattern Matching
- Hoffmann, Jakumeit, Geiß: Graph Rewrite Rules with Structural Recursion
- Geiß: Graphersetzung mit Anwendungen im Übersetzerbau (Diss., dt.)
- Jakumeit, Buchwald, Kroll: GrGen.NET
Known Uses
This is a list of some projects using GrGen.NET or papers describing GrGen employments:
- The AutoModel and SaleMX projects - Natural Language to UML
- The booggie project - Graph grammars for the domain of mechanical engineering
- Skalch - Sketching for scala, a compiler for programs with holes
- The GMoC tool and the locutor project - Are concerned with the management of change on collections of documents
- GRAPE - Implements SHAPE and Palladian grammars from the domain of architecture
- Schösser, Geiß: Graph Rewriting for Hardware Dependent Program Optimizations
- Gelhausen, Derre, Geiß: Customizing GrGen.NET for Model Transformation
- Schimmel, Gelhausen, Schaefer: Gene Expression with General Purpose Graph Rewriting Systems
- Bedaride, Gardent: Semantic Normalisation: a Framework and an Experiment
- Van Gorp, Eshuis: Transforming Process Models: executable rewrite rules versus a formalized Java program
- BPMN operational semantics in GrGen, a series of screencasts by Pieter van Gorp
- Buchwald, Zwinkau: Instruction Selection by Graph Transformation
History
This is a link to the homepage of the previous release of GrGen. It is outdated and will not be maintained or updated, but may be of historical interest.
- 2012-07-29
- Release of GrGen.NET V3.5
- 2011-07-29
- Release of GrGen.NET V3.0
- 2010-09-05
- Release of GrGen.NET V2.6
- 2009-06-28
- Release of GrGen.NET V2.5
- 2008-12-19
- Release of GrGen.NET V2.1
- 2008-07-29
- Release of GrGen.NET V2.0
- 2008-03-20
- Release of GrGen.NET V1.4
- 2008-03-06
- Release of the MOF Suite for GrGen.NET V1.0
- 2007-11-06
- Release of GrGen.NET V1.3
- 2007-07-19
- Release of GrGen.NET V1.2
- 2007-04-19
- First public beta of GrGen.NET
- 2007-04-14
- GrGen has its own domain www.grgen.net
- 2006-10-04
- Last release of C based GrGen
- 2006-09-17
- ICGT 2006: An article stating that GrGen is the world's fastest automatic graph transformation system
- 2003-12-20
- First release of C based GrGen
- 2003-02-01
- Sebastian Hack and Rubino Geiss initiate the development of GrGen
Questions, suggestions, bugs? Feel free to contact the GrGen.NET developers at
|
程序开发
