PROGRES(ID:2271/pro028)Graph based programming languagefor 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. Structures: Related languages
References: 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. Resources
|