GP (Graph Programs)

From The Programming Languages and Systems Research Group
Revision as of 09:47, 7 May 2013 by Chrisbak (talk | contribs)

Jump to: navigation, search
GP (for Graph Programs) is a rule-based, nondeterministic programming language for solving graph problems at a high level of abstraction, freeing programmers from handling low-level data structures. The core of GP consists of four constructs: single-step application of a set of conditional graph-transformation rules, sequential composition, branching and iteration. The language has a structural operational semantics, as well as a prototype implementation.

Sandra Steinert, Greg Manning, and Detlef Plump worked on the design and implementation of GP; Chris Bak and Detlef Plump are currently working on the design and implementation of GP2. Chris Poskitt and Detlef Plump are currently investigating the verification of Graph Programs.

GP Literature


  • Detlef Plump. The Design of GP2 (.pdf). In Proc. Algebraic Informatics, Third International Conference (CAI 2009), volume 82 of Electronic Proceedings in Theoretical Computer Science, pages 1-16, 2012.
Description of GP2, the newest version of GP. The publications below describe the previous version of GP, now known as GP1.
  • Detlef Plump. The Graph Programming Language GP (.pdf). In Proc. International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2011), volume 5725 of Lecture Notes in Computer Science, pages 99-122. Springer-Verlag, 2009.


  • Detlef Plump and Sandra Steinert. The Semantics of Graph Programs (.pdf). In Proc. Rule-Based Programming (RULE 2009), Electronic Proceedings in Theoretical Computer Science, 2009.


  • Christopher M. Poskitt and Detlef Plump. A Hoare Calculus for Graph Programs (.pdf). In Proc. International Conference on Graph Transformation (ICGT 2010), volume 6372 of Lecture Notes in Computer Science, pages 139-154. Springer-Verlag, 2010.

Case Studies

Prototype Implementation

  • Greg Manning and Detlef Plump. The GP Programming System (.pdf). In Proc. Graph Transformation and Visual Modelling Techniques (GT-VMT 2008), volume 10 of Electronic Communications of the EASST, 2008.
  • Greg Manning and Detlef Plump. The York Abstract Machine (.pdf). In Proc. Graph Transformation and Visual Modelling Techniques (GT-VMT 2006), volume 211 of Electronic Notes in Theoretical Computer Science, pages 231-240. Elsevier, 2008.

Possible GP Research Projects

Please contact Detlef Plump for more information about the following possible Ph.D. projects.

  • Speeding up GP. This project will attempt to speed up GP's current implementation, which is based on a compiler and the York abstract machine, to rival with the fastest graph transformation tools currently available. Activities to make GP faster include the introduction of a powerful type system for graphs to support the analysis of graphs at run time, the implementation of dynamic search plans for graph pattern matching, and the use of so-called rooted graph transformation rules which can be matched in constant time.
  • Static analysis of graph programs. This project will develop an automatic program analysis for detecting confluence and termination in graph programs. A nondeterministic program is confluent (or 'don't care' nondeterministic) if all its executions on a given input will produce the same result. Confluence is essential for run time efficiency because GP's backtracking mechanism can be turned off for confluent subprograms without compromising the semantics. Sufficient conditions for confluence will be developed by generalizing so-called critical pair techniques from sets of graph transformation rules to programs. A simple static analysis of termination will complement the analysis of confluence.

More information about these possible projects (and others) are available on our prospective research students page.

Simple_Dijkstra: a graph program implementation of Dijkstra's single-source shortest-path algorithm.
CheckForest: a graph program for testing whether a provided input graph is a forest or not.