GP (Graph Programs)

From The Programming Languages and Systems Research Group
Revision as of 19:34, 2 March 2010 by Cposkitt (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 Poskitt and Detlef Plump are currently investigating the formal verification of Graph Programs.

GP Literature


  • Detlef Plump. The Graph Programming Language GP (.pdf). In Proc. Algebraic Informatics, Third International Conference (CAI 2009), 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. To appear.

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 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.

CheckForest: example graph program for testing whether a graph is a forest.