Graph based programming language 

for PROgrammed GRaph REwriting Systems

Andy Scheurr and Albert Zuendorf, RWTH, Aachen, 1991

Very high-level language based on graph grammars. Supports multiple inheritance and type of types, declarative specification of graphical attributes, visual specification of graph rewrite rules.

"PROGRES supports structurally object-oriented specification of attributed graph structures with multiple inheritance hierarchies and types of types (for parametric polymorphism). It also supports declarative/relational specification of derived attributes, node sets, binary relationships (directed edges) and Boolean constraints, rule-oriented/visual specification of parameterised graph rewrite rules with complex application conditions, nondeterministic and imperative programming of composite graph transformations (with built-in backtracking and cancelling arbitrary sequences of failing graph modifications)."

It is used for implementing abstract data types with graph-like internal structure, as a visual language for the graph-oriented database GRAS, and as a rule-oriented language for prototyping nondeterministically specified data/rule base transformations.

Related languages
PROGRES => Grace   Influence

  • Andy Schuerr. "PROGRES: A VHL-language based on graph grammars" H. Ehrig, H.-J. Kreowski, G. Rozenberg, eds., Graph Grammars and Their Application to Computer Science, LNCS 532, pp641- 659, 1991. view details
  • Scheurr, A. "Introduction to PROGRES, an Attribute Graph Grammar Based Specification Language", in Proc WG89 Workshop on Graph-theoretic Concepts in Computer Science", LNCS 411, Springer 1991 view details
  • Schuerr, Andy "Programmed graph transformations and graph transformation in GRACE" Presented at the 5th Workshop on Graph Grammars and Their Application to Computer Science (Williamsburg, USA), 1994. view details
  • Andy Schürr "Rapid Programming with Graph Rewrite Rules" Proc. USENIX Symp. on Very High Level Languages (VHLL), Santa Fee, Oct. 1994, USENIX Association, pp. 83-100 view details Abstract: Graphs play an important role within many areas of computer science and rule-based languagesare more and more used to describe complex transformation or inference processes. Nevertheless, their combination in the form of graph rewriting systems were more or less unknown among computer scientists for along time. Nowadays, the situation is gradually improving with the appearance of a number of graph rewritingsystem implementations. Currently, the multi-paradigm language PROGRES is the most expressive imple-mented graph rewriting language. It has the flavor of a visual database definition and programming languageand combines the advantages of attributed (graph) grammars with rule-oriented as well as imperative pro-gramming. An integrated set of tools supports editing, analyzing, and debugging of applications as well astranslation into procedural programming languages (C, Modula-2) Extract: Introduction
    Graphs play an important role within many areas of computer science and there exists an abundance of visuallanguages and environments which have graphs as their underlying data model. Furthermore, rule-based rewriting languages are well-suited for the description of complex transformation or inference process-es on complex data structures. Although graphs and rule-base rewriting systems are quite popular amongcomputer scientists, their combination in the form of graph rewriting systems were more or less unknown for a long time. Nowadays the situation is gradually improving with the appearance of graph rewriting systemimplementations like AGG, GraphED, PAGG, or GOOD. Unfortunately, all these systemshave their main focus on the definition of graph rewrite rules only, and they either have no proper means tomodel integrity constraints and derived properties of data structures or they do not offer any constructs tocombine basic rewrite rules to more complex transformation processes.The language PROGRES is the first attempt to overcome these deficiencies of graph rewriting systems.It is a strongly typed multi-paradigm language with well-defined syntax, static and dynamic semantics. Itsname is an acronym for PROgrammed Graph REwriting Systems which are the language?s underlying for-malism and are in turn defined by means of nonmonotonic logic and fixpoint theory [26, 27]. Being a mixedtextual and diagrammatic language, it permits quite different styles of programming and supports
    graphical as well as textual definition of graph database schemas,
    declaration of derived graph properties,
    rule-oriented and diagrammatic specification of atomic graph rewriting steps by means of parametrizedgraph rewrite rules (productions) with complex preconditions, and
    imperative programming of composite graph transformation processes by means of deterministic andnondeterministic control structures.

    In some respect, PROGRES is rather similar to so-called ?visual database languages? as for instance GraphLog or QBD*. But note that these languages are more or less ?pure? query languages which donot support the definition of complex transformation processes. In contrast, PROGRES and its programming-environment support definition and manipulation of data. They are already in use for specifying tools and data structures of software engineering environments, describing tools for process modeling and configuration management in CIM environments, and defining the semantics of a visual database query language.
    Extract: The Language PROGRES
    The Language PROGRES

    The language PROGRES was mainly designed as a specification language for syntax-directed tools of software engineering environments. But gradually it became obvious that it is also a kind of visual database programming language, and that it might even be used as a very high level language for implementing graph-like abstract data types. The running example, red/black trees, has been selected in order to demonstrate the advantages of programming with graph rewrite rules in contrast to the usage of conventional programming languages. It has rather complex tree restructuring operations, but its data model is just a binary tree with colored nodes. Therefore, we have to emphasize that PROGRES allows for the definition of arbitrary directed (attributed) graphs, and is not restricted to the case of attributed trees or directed acyclic graphs(as for instance). Directed, attributed graphs consist of typed nodes with attributes and directed typed edges between pairsof nodes. Each edge may be traversed in both directions (from source to target and vice-versa), i.e. is equivalent to a pair of pointers of Pascal-like programming languages. Furthermore, referential integrity is guaranteed, i.e. when a node is deleted, all adjacent edges are deleted, as well. Node attributes and binary relationsare either extensionally defined and manipulated by graph rewrite rules (as intrinsic attributes and edges) orthey are intensionally defined and maintained by the PROGRES runtime system (as derived attributes andmaterialized path expressions). A lazy and incrementally working evaluation process keeps derived data in aconsistent state. It is a refined version of the algorithm in the graph-oriented database system Cactis andpart of our own database system GRAS. As a consequence, PROGRES programmers do not have to worry about inconsistent pairs of pointers, dangling references, and inconsistent intensionally definable data.
  • Heimann, Peter ; Gregor Joeris, Carl-Arndt Krapp and Bernhard Westfechtel, A programmed graph rewriting system for software process management, Electronic Notes in Theoretical Computer Science, Vol. 2 (2000) view details
    • FTP at Aachen