Dr. Steffen Mazanek

 

Forschung / Research

siehe meine private Webseite

siehe auch mein Blog über visuelle Sprachen (outdated)

Projekte während meiner Zeit an der UniBw München

Graph Parser Combinators

What are Graph Parser Combinators?

Graph parser combinators are an attempt to carry over the popular parser combinator approach to the domain of graphs. In analogy to string grammars there are also several different graph grammar formalisms. We have noted that most advantages of string parser combinators also apply to graphs, and, surprisingly, even further advantages have appeared. A parser constructed using graph parser combinators resembles the particular graph grammar very closely. It can be adapted to varying demands in a flexible way, and can be freely used in the host program -- it is a first-class citizen after all.

What is the current state of the implementation?

We have already written a powerful Haskell library on top of polyparse. However, we have noticed that a functional-logic approach is even more suited. Therefore, we have reimplemented the framework using the multi-paradigm declarative language Curry. The resulting library is simple and straightforward. We have already applied it successfully to several practical problems. However, since this is very much work in progress there is no downloadable release yet. We gladly send you a commented snapshot on request.

What can Graph Parser Combinators be used for?

As already mentioned the use of graph parser combinators has several merits. Most exciting is the fact that parsers can be applied backwards and, thus, used as generators or for the completion of graphs. We have connected our framework to the diagram editor generator framework DiaGen, where we use it to compute completions of a given diagram.

Graph Parser Combinators as a Benchmark

In the report "Graph Parser Combinators: A Challenge for Curry-Compilers" we have suggested to use this application as a benchmark for Curry compilers. Since only three compilers have been compared and we are no expert on these particular compilers we provide the benchmark suite here for download. That way you can reconstruct or even improve our results. You may also want to add data for your favourite compiler. Just send me an email and I gladly add your data here.

Download benchmark, see file README.txt for further information

Publications about Graph Parser Combinators

We can send you these documents in PDF on request.

  • S. Mazanek, M. Minas. Constructing a Bidirectional Transformation between BPMN and BPEL with Functional-logic Graph Parser Combinators. Accepted solution for the GraBaTs 2009 synthesis case study. At the contest this solution was awarded with the third place out of the 10 submitted solutions.
  • S. Mazanek, M. Minas. Graph Parser Combinators: A Challenge for Curry-Compilers. 25. Workshop der GI-Fachgruppe Programmiersprachen und Rechenkonzepte, 2008. Technical Report of Christian-Albrechts-Universität Kiel, no. 0811, pages 55-66.
  • 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, M. Minas. Functional-logic graph parser combinators. Proc. of the 19th International Conference on Rewriting Techniques and Applications (RTA 2008), 2008. LNCS, Volume 5117/2008, pages 261-275.
  • S. Mazanek, M. Minas. Parsing of hyperedge replacement grammars with graph parser combinators. Proc. 7th International Workshop on Graph Transformation and Visual Modeling Techniques (GT-VMT 2008), 2008. Electronic Communications of the EASST, Volume 10.
  • S. Mazanek, M. Minas. Graph parser combinators. Proc. of the 19th International Symposium on Implementation and Application of Functional Languages (IFL 2007), 2008. LNCS, Volume 5083/2008, pages 1-18.

Contact

Please send any questions, requests and suggestions to Steffen Mazanek.

Projekte während des Studiums

  • Diplomarbeit: Higher-Kinded Types in the Context of Subtyping, UniBwM-ID 29/2003

    Zusammenfassung:

    Typsysteme moderner funktionaler Programmiersprachen unterstützen den Software- Entwicklungsprozess maßgeblich. So verwundert es nicht, dass viel Arbeit in ihre Weiterentwicklung und Verbesserung investiert wird. Im Bereich der objektorientierten Programmierung hat es sich gezeigt, dass Erweiterung und Spezialisierung durch Bildung von Subtypen und Vererbung eine enorme Produktivitätssteigerung ermöglichen. Dies legt die Überlegung nahe, bestimmte Konzepte davon in die funktionale Welt zu übertragen.

    Bisher fehlen diese Möglichkeiten etwa in der Programmiersprache Haskell, so dass wir, ausgehend von O'Haskell, dem Ansatz Nordlanders, ausarbeiten, welche Bedeutung Subtyp-Beziehungen in Haskell haben könnten und wie sie sich realisieren lassen. Dabei stellen wir eine neue Anwendungsmöglichkeit des Haskell kind-Systems vor und erweitern mit dessen Hilfe den Ansatz Nordlanders auf sogenannte higher-kinded types. Varianzen berücksichtigen wir durch spezielle Funktions-kinds und kind-Variablen. Unser Konzept sorgt dafür, dass auch zwischen sehr komplexen, currysierten Typen Subtyp-Beziehungen aufgestellt werden können.

    Desweiteren motiviert unser kind-System eine bestimmte Form des subkinding. Erfahrungen aus Typsystemen folgend soll diese subkind-Beziehung Abschwächungen spezifischerer kinds erlauben. Daraus resultieren weitere bemerkenswerte Analogien zwischen Typen und kinds. Beispielsweise verhält sich auch der Konstruktor für Funktions-kinds kontravariant im ersten Argument, so dass bekannte Effekte auftreten.

    Unsere Ziele sind Übersichtlichkeit, Kompatibilität zu Haskell98 und eine akzeptable Komplexität. Wir werden unseren Ansatz mit anderen Ideen und bewährten Ergänzungen des Haskell Typsystems vergleichen und deren Verträglichkeit untersuchen. Letztlich stellen wir mit dieser Arbeit eine Implementierung der vorgestellten Algorithmen zur Verfügung.

  • Studienarbeit: Implementierung eines Interpreters für RATH, UniBwM-IS 04/2002

    Zusammenfassung:

    RATH ist ein Paket von Haskell-Modulen, die die Analyse von (endlichen) Relationenalgebren und bestimmten schwächeren Strukturen wie Kategorien, Allegorien und Dedekind-Kategorien unterstützen.

    In dieser Arbeit ging es nun darum, eine Art Taschenrechner für Relationenalgebren zu implementieren. Entstanden ist eine eigene kleine Programmiersprache, in der Relationen "Bürger erster Klasse" sind und sehr komfortabel manipuliert werden können.