PROGRES
PROGRES (für PROgrammierte GRaph ErsetzungsSysteme bzw. PROgrammed Graph REwriting Systems) ist eine Programmiersprache und eine integrierte Entwicklungsumgebung für selbige. Es wird seit 1989 am Lehrstuhl 3 für Informatik an der RWTH Aachen entwickelt.
Es eignet sich besonders für die Entwicklung von CASE-Werkzeugen. So sind beispielsweise Werkzeuge
- für die Unterstützung von Autoren (CHASID),
- für die Analyse von Kommunikationssystemen (E-CARES),
- für den konzeptionellen Gebäudeentwurf (ConDes) und
- für das Management von komplexen Prozessen (AHEAD) mittels PROGRES realisiert worden.
PROGRES basiert dabei auf gerichteten, attributierten und getypten Graphen. Mit Hilfe von Graphen können umfangreiche und komplizierte Sachverhalte übersichtlich und strukturiert dargestellt werden (siehe auch abstrakte Syntaxbäume und Petri-Netze). PROGRES besteht zum einen aus einer Spezifikationssprache und zum anderen aus einer komplexen, integrierten Umgebung.
Die Sprache
Um ein Werkzeug mit PROGRES zu entwickeln, wird zunächst ein geeignetes Graphschema mit der Spezifikationssprache festgelegt, da in PROGRES die Knoten und Kanten der Graphen getypt sind. Es handelt sich hierbei um ein zweistufiges Typsystem, d. h., es gibt Knotenklassen und Typen, wobei nur Typen instanziiert werden dürfen. Zum Beispiel könnte man sich eine Knotenklasse „Animal“ definieren und von dieser Klasse einen Typ „Wolf“ ableiten. Von diesem Typ kann man sich wiederum ein entsprechendes Objekt in einem Arbeitsgraphen, dem sogenannten Wirtsgraphen, erzeugen. Da PROGRES die Objektorientierung unterstützt, kann man zu allen Knotenklassen und Typen Attribute und Methoden definieren. Im Gegensatz zu den Knoten sind die Kanten in PROGRES nur getypt und nicht attributiert.
Neben dem Graphschema können Graphtransformationen grafisch und textuell spezifiziert werden. Diese können an eine Klasse und einen Typ des Schemas gebunden sein oder für sich allein stehen. Eine einfache Graphtransformation besteht aus einer linken und rechten Regelseite, wobei in der linken Seite ein Graphmuster angegeben wird, dass durch die rechte Seite ersetzt wird. Wenn eine Graphtransformation angewendet werden soll, wird der aktuelle Wirtsgraph solange durchsucht, bis das entsprechende Muster der linken Seite gefunden wird. Diese Anwendungsstelle wird anschließend durch die rechte Seite ersetzt. Falls es in dem Wirtsgraphen mehrere verschiedene Anwendungsstellen gibt, wird eine dieser Stellen nichtdeterministisch ausgewählt.
Beispiel
Als Beispiel kann man das bekannte FerryMan-Problem betrachten, in dem es einen Fluss mit zwei Uferseiten und ein Boot gibt. Mit Hilfe des Bootes sollen drei Frachten (ein Kohlkopf, eine Ziege und ein Wolf) auf die andere Uferseite des Flusses gefahren werden, wobei das Boot immer nur eine Fracht laden kann. Das Problem liegt darin, dass der Wolf und die Ziege nicht ohne den Bootsführer auf einer Uferseite sein dürfen, da ansonsten der Wolf die Ziege frisst. Analoges gilt für die Ziege und den Kohlkopf. Dieses Beispiel kann mit einer GuidedTour, die im PROGRES-Release enthalten ist, spezifiziert werden. Zusätzlich können zu jeder Graphtransformation Vor- und Nachbedingungen, Attributzuweisungen, Eingabe- und Ausgabeparameter usw. angegeben werden. Neben einfachen Transformationen können auch komplexe Transformationen modelliert werden. Diese können z. B. aus mehreren einfachen Transformationen zusammengesetzt sein und verschiedene Kontrollstrukturen wie Schleifen und Bedingungen enthalten. Durch die unterliegende Datenbank erfüllt jede Transformation die ACID-Eigenschaften. Neben den Transformationen können auch Graphtests und Pfade definiert werden.
Die Entwicklungsumgebung
Die PROGRES-Umgebung besteht aus drei integrierten Tools:
- einem syntaxkontrollierten Editor mit einem Analysator, der alle Verstöße gegen die statische Semantik der Sprache prüft,
- einem Interpreter mit einem entsprechenden Graph-Browser, der den Spezifizierer bei der Fehlersuche durch inkrementelles Ausführen der Spezifikation unterstützt sowie
- einem Compiler, der die Spezifikation automatisch in C- oder Java-Quelltext übersetzt.
Überdies wurde das UPGRADE-Rahmenwerk für PROGRES entwickelt. Mit Hilfe dieses Rahmenwerks lässt sich aus dem generierten Code ein grafisches Tool erzeugen, das dem Benutzer eine grafische Oberfläche zur Verfügung stellt und gemäß den Ansprüchen der Benutzer angepasst werden kann.