Document [original]

Generierung von Animation und

Simulation für graphische

Struktureditoren

Dissertation

Schriftliche Arbeit zur Erlangung des akademischen Grades

„Doktor der Naturwissenschaften“

an der Fakultät für Elektrotechnik, Informatik und Mathematik

der Universität Paderborn

vorgelegt von

Bastian Cramer

Paderborn, September 2010

Datum der mündlichen Prüfung:

6. Dezember 2010

Gutachter:

Prof. Dr. Uwe Kastens, Universität Paderborn

Prof. Dr.-Ing. Mark Minas, Universität der Bundeswehr München

Inhaltsverzeichnis

1 Einleitung 1

2 Grundlagen 7

2.1 VisuelleSprachen............................... 8

2.2 Eigenschaften visueller Sprachen und ihre Historie . . . . . . . . . . . 10

2.3 Programm- u. Softwarevisualisierung und visuelle Programmierung . 14

2.4 Animation................................... 17

2.5 Simulation................................... 22

2.5.1 SIMAN................................. 27

2.5.2 GPSS.................................. 28

2.5.3 SIMSCRIPTIII ............................ 29

2.5.4 Simula................................. 30

2.5.5 Bibliotheken zur Simulationsunterstützung . . . . . . . . . . . . 31

2.6 Programmvisualisierungssysteme . . . . . . . . . . . . . . . . . . . . . 31

2.6.1 Sorting out Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.6.2 BALSA................................. 32

2.6.3 TANGO ................................ 32

2.6.4 POLKA-RC .............................. 34

2.6.5 Lens .................................. 35

2.6.6 Forms/3................................ 37

2.6.7 PictorialJanus............................. 37

2.6.8 Alma.................................. 39

2.7 Generatorsysteme............................... 41

2.7.1 MetaEdit+............................... 41

2.7.2 GenGed/Tiger ............................ 43

2.7.3 DiaGen/DiaMeta........................... 44

2.7.4 MosesToolsuite............................ 47

2.7.5 AToM3................................. 48

2.8 Relevanz im Kontext dieser Arbeit . . . . . . . . . . . . . . . . . . . . . 51

2.9 DasDEViL-System .............................. 54

2.9.1 Spezifikation der abstrakten Struktur . . . . . . . . . . . . . . . 55

2.9.2 Spezifikation der graphischen Darstellung . . . . . . . . . . . . 59

2.9.3 Zusammenhang zur Repräsentationsgraphik . . . . . . . . . . . 62

2.9.4 Das Klassenmodell und Pfadausdrücke in DEViL . . . . . . . . 64

2.9.5 Eigenschaften generierter Umgebungen . . . . . . . . . . . . . . 65

III

Inhaltsverzeichnis

3 Simulier- und Animierbarkeit visueller Sprachen 69

3.1 StrukturundDaten.............................. 70

3.2 Zustand und Zustandsübergänge . . . . . . . . . . . . . . . . . . . . . . 73

3.3 Repräsentation................................. 76

3.4 Klassifikation visueller Sprachen . . . . . . . . . . . . . . . . . . . . . . 77

4 Simulationskonzept 87

4.1 DerSimulator ................................. 88

4.1.1 Der erweiterte Spezifikationsprozess . . . . . . . . . . . . . . . . 88

4.1.2 Anforderungen an den generierten Simulator . . . . . . . . . . 90

4.1.3 Einbettung des Simulators in die Werkzeugkette . . . . . . . . . 92

4.1.4 Zeitliches Verhalten des Simulators . . . . . . . . . . . . . . . . 93

4.2 Entwurf der Simulationssprache . . . . . . . . . . . . . . . . . . . . . . 96

4.2.1 Imperativ vs. regelbasiert . . . . . . . . . . . . . . . . . . . . . . 99

4.3 Die Simulationsspezifikationssprache DSIM . . . . . . . . . . . . . . . . 99

4.3.1 Spezifikation der Simulationsstruktur . . . . . . . . . . . . . . . 100

4.3.2 Spezifikation des Simulationsverhaltens . . . . . . . . . . . . . . 102

4.3.3 Spezifikation von Ereignissen . . . . . . . . . . . . . . . . . . . . 104

4.3.4 Spezielle Funktionalitäten . . . . . . . . . . . . . . . . . . . . . . 106

4.3.5 Textuell vs. visuell . . . . . . . . . . . . . . . . . . . . . . . . . . 110

4.4 VerwandteArbeiten ............................. 111

5 Animationskonzept 113

5.1 Das Animationsframework . . . . . . . . . . . . . . . . . . . . . . . . . 114

5.1.1 Einordnung der Animationskomponente . . . . . . . . . . . . . 114

5.1.2 Der “interesting-events”-Ansatz................... 116

5.1.3 Animation durch lineare graphische Interpolation . . . . . . . . 117

5.1.4 Der deklarative Animationsansatz . . . . . . . . . . . . . . . . . 122

5.1.5 Berechnung der Animation . . . . . . . . . . . . . . . . . . . . . 126

5.1.6 Dynamische Animationsobjekte . . . . . . . . . . . . . . . . . . 127

5.1.7 Statische Animationsobjekte . . . . . . . . . . . . . . . . . . . . 128

5.1.8 Graphische Anknüpfungspunkte . . . . . . . . . . . . . . . . . . 130

5.1.9 Informationsverlust zwischen Simulation und Animation . . . 131

5.2 Eigenschaften generierter Umgebungen . . . . . . . . . . . . . . . . . . 135

5.3 Diskussion................................... 138

5.4 VerwandteArbeiten ............................. 139

6 Analyse 141

6.1 Analyse der Simulationsspezifikation . . . . . . . . . . . . . . . . . . . 142

6.2 Analyse des visuellen Programms . . . . . . . . . . . . . . . . . . . . . 145

6.3 Aspektorientierte Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . 146

7 Evaluation 149

7.1 Grundlagen der Usability . . . . . . . . . . . . . . . . . . . . . . . . . . 151

Inhaltsverzeichnis

7.2 Usability-Maße ................................ 152

7.3 Allgemeine Methoden zur Usability Untersuchung . . . . . . . . . . . 153

7.4 Usability des Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

7.4.1 Implementierung von Beispielsprachen . . . . . . . . . . . . . . 155

7.4.2 Feld-Beobachtung . . . . . . . . . . . . . . . . . . . . . . . . . . 166

7.4.3 Expertenbewertung . . . . . . . . . . . . . . . . . . . . . . . . . 170

7.4.4 Kontrolliertes Experiment . . . . . . . . . . . . . . . . . . . . . . 173

7.5 Geschwindigkeit ............................... 177

8 Resümee und Ausblick 183

1 Einleitung

Anwendungsspezifische Sprachen werden zur Zeit in der Forschung diskutiert

[28, 29]. Sie sollen das momentan vorherrschende objekt-orientierte Paradigma

erweitern und so Lösungen zu spezialisierten Teilproblemen bereitstellen. Es sollen

Spezialsprachen entwickelt werden, die ineinander greifen und auch in allgemeine

Programmiersprachen eingebettet werden können. Durch diesen Ansatz können

Probleme auf einem viel höheren Abstraktionsniveau und mit Metaphern der

Domäne gelöst werden. Dies führt zu einer Entkopplung der Spezifikation von der

Implementierung.

Zur schnellen Entwicklung solcher Spezialsprachen stehen diverse Generator-

systeme zur Verfügung (vgl. Abschnitt 2.7). Allen ist gemein, dass sie auf Basis einer

abstrakten Beschreibung einer Sprache vollständige graphische1Entwicklungs-

umgebungen generieren. Graphisch bedeutet dabei, dass wesentliche Anteile der

dargestellten Sprache durch Konstrukte wie Farbe, Form, Verbindung, Enthalten-

sein etc. dargestellt werden. Diese Umgebungen enthalten zudem alle wichtigen

Werkzeuge um Sprachinstanzen komfortabel zu manipulieren und Zielcode zu

erzeugen. Generatoren für Entwicklungsumgebungen für visuelle Sprachen kapseln

Expertenwissen und stellen es zur Wiederverwendung zur Verfügung. Sie machen

damit Gebrauch eines der mächtigsten Programmierparadigmen der Informatik [62].

Aktuelle Generatoren für visuelle Entwicklungsumgebungen generieren in der

Regel nur graphische Umgebungen, die statischer Natur sind. Visuelle Sprachin-

stanzen können zwar vom Benutzer sehr einfach manipuliert und erstellt werden,

trotzdem besteht immer noch eine große kognitive Distanz zwischen der visuellen

Beschreibung und dem, was aus der Beschreibung generiert wird: nämlich ein

auführbares Programm. Dieses Problem ist auch als “gulf of execution” bekannt [78],

weshalb das Programmieren mental sehr aufwändig ist.

Gerade bei der Spezifikation von nebenläufigen Prozessen, aber auch bei der

Erstellung von komplexen Algorithmen im imperativen Paradigma ist der An-

wender oft bereits sehr früh überfordert. Eine dynamische Repräsentation der

Zustandsübergänge mittels einer Animation kann hier beim Verifikations- bzw. Ver-

ständnisprozess helfen. Auch in anderen Bereichen, z. B. der Lehre, kann Simulation

und Animation zu erhöhtem Systemverständnis führen.

1Ich werde in dieser Arbeit graphisch und visuell als Synonym verwenden.

KAPITEL 1. EINLEITUNG

Den Nutzen von Animation hat bereits Knuth 1973 in The Art of Computer Program-

ming [59] beschrieben:

“Es sollte sofort erwähnt werden, dass der Leser nicht erwarten sollte, einen

Algorithmus wie ein Buch zu lesen; solch ein Versuch würde es sehr schwierig

machen, zu verstehen, was dieser leistet. Ein Algorithmus muss gesehen um ver-

standen zu werden und der beste Weg einen Algorithmus zu lernen ist es ihn

auszuprobieren. Der Leser sollte immer Stift und Papier bereithalten...“

Dass die dynamische Zeichengebung, wie Schiffer sie bezeichnet [100], bisher vernach-

lässigt wurde, hat mehrere Gründe. Zum einen gibt es bisher nur wenig Unterstüt-

zung auf Seiten der Generatorsysteme. Oft existiert hier nur eine Beschreibung der

Zustandsübergänge (meist durch Graphtransformation), jedoch nur wenig Hilfe bei

der Entwicklung einer sanften Animation der Übergänge. Diese ist jedoch für ein Sys-

temverständnis unerlässlich. Insbesondere die syntax-gerichteten Editoren verhalten

sich bei der Animation nicht so wie gewünscht (vgl. Kapitel 5.1).

Zum anderen ist die dynamische Repräsentation - auf Systemebene betrachtet -

sicherlich nicht einfach zu implementieren. Expertenwissen auf mehreren Gebieten

ist notwendig. Oft gibt es in bestehenden Systemen (vgl. [17]) schlicht nur unzurei-

chende Erweiterungsmöglichkeiten.

Der wichtigste Aspekt ist jedoch sicherlich, dass es keinen Konsens über eine

Spezifikationsmethode gibt. Es existiert zwar eine Menge von Spezifikationsmetho-

diken (AsmL [66], Graphtransformation [31]), jedoch keine allgemein anerkannte

Vorgehensweise. Dies liegt wahrscheinlich am formalen Charakter der bisherigen

Ansätze.

Ein letzter Aspekt ist, dass die Möglichkeit der Analyse einer dynamischen Reprä-

sentation bisher unterschätzt wurde. Durch die dynamische Repräsentation ist es

möglich, Fehler im Modell viel früher zu finden. Ein zeitaufwändiger Umweg über

das generierte Produkt ist nicht mehr nötig, wie es ein bekanntes Generatorsystem

versucht.

In dieser Arbeit soll das Generatorsystem DEViL (Development Environment

for Visual Languages) zur Erzeugung von Struktureditoren für visuelle Sprachen

so erweitert werden, dass die Spezifikation der Simulation und Animation einer

visuellen Sprache ermöglicht wird. Dabei sind zwei Aspekte wichtig: Erstens soll

das Spektrum der Sprachen, die mit Simulations- und Animationsunterstützung

ausgestattet werden sollen, möglichst groß sein. Existierende Systeme beschränken

häufig die Art der visuellen Sprache, z. B. auf graphartige Strukturen [33]. Dies

wirkt sich direkt auf den zweiten Aspekt aus: die Spezifikationsmethodik. Sie soll

besonders einfach sein. Dies ist wichtig, da Generatoren für visuelle Sprachen

(VLs) besonders im Rapid Prototyping eingesetzt werden und die Einfachheit der

Spezifikation die Akzeptanz und die Einsetzbarkeit des Systems erhöhen. Damit die

Spezifikationsmethode für den Sprachentwickler einfach ist, sollen bereits bewährte

Konzepte des DEViL Systems übernommen und adaptiert werden. Dies wird sich

im Laufe der Arbeit in mehreren Teilbereichen zeigen: die entwickelte Simulati-

onssprache wird Strukturspezifikationskonzepte wieder aufgreifen, die Animation

wird erreicht, indem der bereits bestehende deklarative Ansatz der so genannten

visuellen Muster erweitert wird.

Methodischer Beitrag dieser Arbeit Diese Arbeit soll einen methodischen Beitrag

zur Simulation und Animation im Rahmen der visuellen Sprachen darstellen.

Existierende visuelle Sprachen, ebenso wie Simulationssprachen und existierende

Generatorsysteme werden systematisch untersucht. Dabei zeigt diese Arbeit eine

Kategorisierung von visuellen Sprachen in Bezug auf ihre Simulier- und Animier-

barkeit auf. Die Sprachen werden hinsichtlich ihrer Struktur, Ausführungssemantik

sowie ihrer Simulations- und Animationsstruktur untersucht. Somit kann abgeleitet

werden, wann und wie eine Sprache simulier- und animierbar ist. Aus dieser

Untersuchung ergibt sich eine methodische Vorgehensweise für die Spezifikation

visueller Sprachen mit dynamischer Repräsentation. Diese zeichnet sich dadurch

aus, dass vorhandene Konzepte wiederverwendet werden und so die Simulation

als einfache Erweiterung einer bestehenden Sprachspezifikation gesehen werden

kann. Wohlbekannte Konzepte und Methoden der Simulationsforschung werden

übernommen und integriert. Wiederverwendung zeigt sich bei der Spezifikation der

Simulationstruktur, die den bisherigen klassenbasierten Entwurf von semantischen

Strukturen für VLs benutzt und diesen durch Attribute und Pfadausdrücke erwei-

tert. Somit wird eine passende Simulationsstruktur erreicht.

Der entwickelte Ansatz zeigt, dass ein großes Spektrum visueller Sprachen si-

muliert werden kann. Trotzdem ist die Simulationssprache dabei einfach gehalten,

da sie eine standardisierte und enge Schnittstelle zur Manipulation von Simulations-

strukturinstanzen bereitstellt, an die auch gleichzeitig die Animation anknüpfen

kann.

Bereits hier sei gesagt, dass die entworfene Simulation in keiner Konkurrenz

zu spezialisierten Simulatoren aus dem wissenschaftlichen Bereich stehen soll. Sie ist

lediglich Mittel zum Zweck der Animation einer visuellen Sprache. Das heißt jedoch

nicht, dass die Simulation in ihrem Anspruch weniger von Bedeutung ist.

Aus einer Simulation kann mit dem hier gezeigten Ansatz automatisch eine

Animation abgeleitet werden. Es wird sich zeigen, dass diese generierte Animation

als Standardfall häufig schon die Bedürfnisse einer animierten visuellen Sprache

abdeckt. Nur in Ausnahmefällen muss durch den Sprachdesigner eine Anpassung

vorgenommen werden. Dies geschieht deklarativ durch eine Bibliothek von para-

metrisierten Animationsmustern. Die Animation kann flexibel angepasst werden.

Durch die nahezu beliebige Kombination von Bibliotheksbausteinen kann eine an-

spruchsvolle Animation erstellt werden. Auch hier werden bekannte und bewährte

KAPITEL 1. EINLEITUNG

Spezifikationsmethoden wiederverwendet. Somit ist der Spezifikationsaufwand im

Verhältnis zum erzielten Ergebnis gering. Ein Sprachdesigner, der die Entscheidung

fällt eine Sprache zu simulieren, bekommt eine automatisch generierte Animation

nebenbei.

Zudem wird in dieser Arbeit gezeigt, dass die Animation eine formal korrekte

Abbildung ihrer Simulation ist. Dies wird durch standardisierte Änderungsop-

erationen in der Simulation erreicht, an die die Animation anknüpft. Durch die

einfache und kleine Schnittstelle werden Animationen automatisch berechnet. So

kann eine erstellte Simulation direkt durch ihre Animation getestet werden.

Des Weiteren soll diese Arbeit einen Beitrag zur Analyse visueller Sprachen

aufzeigen. Neben der Animation als Analysemittel für den Sprachanwender gibt es

noch weitere Methoden, die es erlauben ein genaues Bild des Ausführungszustandes

der Sprachinstanz zu erlangen. Dies sind u.a.:

•Logging Mechanismen zur späteren statistischen Auswertung.

•automatisch generierte Auslastungsgraphen.

•ein integrierter Debugger für die Simulationssprache. Somit können auch Al-

gorithmenanimationssysteme nachgebildet werden.

•Ereignisgraphen.

•Modellinspektion; zur schrittweisen Analyse der Simulationsstruktur.

Die Generierung von Struktureditoren für anwendungsspezifische Sprachen ist

mit dem bereits entwickelten Generator DEViL unproblematisch. Struktureditoren

lassen sich in kurzer Zeit spezifizieren. Entworfen wird zunächst die abstrakte

Struktur, also das Modell der Sprache. Dieses wird dann mit so genannten visuellen

Mustern dekoriert, sodass eine graphische Repräsentation entsteht. Die Spezifi-

kation findet dabei auf einem sehr hohen Abstraktionsniveau statt, das es dem

Sprachentwickler erlaubt, von Implementierungsdetails zu abstrahieren und das im

Generator gekapselte Expertenwissen zu nutzen. Das DEViL System generiert aus

den Spezifikationen Struktureditoren, die Eigenschaften moderner Systeme wie eine

Multi-Fensterumgebung, Interaktionsmechanismen und Konsistenzüberprüfungs-

funktionen enthalten.

Um visuelle Sprachen mit dynamischer Repräsentation generieren zu können,

werde ich im nächsten Kapitel den Bereich der Programmvisualisierung vorstel-

len. Hier werden sich bereits Anforderungen sowohl an die Ausführung eines

Programms als auch an dessen Darstellung ergeben. Ein Blick auf verschiedene

Algorithmenanimationssysteme wird zeigen, welche Stilmittel eingesetzt werden

um eine anspruchsvolle Animation zu erreichen. Im Anschluss werden diverse

Simulationssprachen und Bibliotheken betrachtet. Diese geben Aufschluss über die

Beschreibung und Implementierung von Simulationsspezifikationen. Insbesondere

wird der Begriff Simulationsmodell eingeführt und beschrieben. Die vorgestellten

Simulationssprachen betrachte ich unter besonderer Berücksichtigung des hier

eingesetzten Kontextes: der Simulation und Animation visueller Sprachen. Danach

betrachte ich existierende Generatorsysteme für visuelle Sprachimplementierungen.

Besonders im Bereich der Graphtransformation exstieren bereits Systeme, die

Sprachinstanzen simulieren können. Ich werde die Systeme später nochmals in der

Evaluation aufgreifen um einen Vergleich mit der hier vorgestellten Implementie-

rung zu ziehen. Eine Vorstellung des Spezifikationskonzepts von DEViL schließt das

Grundlagenkapitel ab.

Des Weiteren muss geklärt werden, wann und unter welchen Umständen ei-

ne visuelle Sprache simuliert und animiert werden kann. Ich werde zu diesem

Zweck in Kapitel drei diverse Sprachen untersuchen und am Ende des Kapitels

ein Klassifizierung dieser Sprachen vorstellen. Diese dient als Grundlage für das

Simulationskonzept in Kapitel vier und die Animationskomponente, die in Kapitel

fünf vorgestellt wird. Das Simulationskonzept wird mit dem Simulator in das

allgemeine Spezifikationskonzept eingebettet. Die Animationskomponente wird

die Besonderheit des vorgestellten Ansatzes zeigen: die graphische Interpolation.

Kapitel sechs geht auf den Aspekt der Analyse von visuellen Sprachen ein. Ich

werde zeigen, dass es diverse Analysekomponenten auf Spezifikationsebene gibt,

die dem Sprachspezifizierer helfen, eine korrekte Simulation bzw. Animation für

eine Sprachimplementierung zu entwerfen. Auch auf Anwendungsseite wird es

Methoden geben, eine Animation auszuwerten. Kapitel sieben stellt eine Evaluation

des entworfenen Konzepts dar. In Kapitel acht resümiere ich das Konzept und stelle

weitere zukünftige interessante Forschungsaspekte vor.

2 Grundlagen

Inhalt

2.1 VisuelleSprachen............................. 8

2.2 Eigenschaften visueller Sprachen und ihre Historie . . . . . . . . 10

2.3 Programm- u. Softwarevisualisierung und visuelle Programmie-

rung .................................... 14

2.4 Animation ................................. 17

2.5 Simulation ................................. 22

2.5.1 SIMAN................................. 27

2.5.2 GPSS.................................. 28

2.5.3 SIMSCRIPTIII ............................ 29

2.5.4 Simula................................. 30

2.5.5 Bibliotheken zur Simulationsunterstützung . . . . . . . . . . . . 31

2.6 Programmvisualisierungssysteme . . . . . . . . . . . . . . . . . . . 31

2.6.1 Sorting out Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.6.2 BALSA................................. 32

2.6.3 TANGO ................................ 32

2.6.4 POLKA-RC .............................. 34

2.6.5 Lens .................................. 35

2.6.6 Forms/3................................ 37

2.6.7 PictorialJanus............................. 37

2.6.8 Alma.................................. 39

2.7 Generatorsysteme ............................ 41

2.7.1 MetaEdit+............................... 41

2.7.2 GenGed/Tiger ............................ 43

2.7.3 DiaGen/DiaMeta........................... 44

2.7.4 MosesToolsuite............................ 47

2.7.5 AToM3................................. 48

2.8 Relevanz im Kontext dieser Arbeit . . . . . . . . . . . . . . . . . . . 51

2.9 DasDEViL-System ............................ 54

2.9.1 Spezifikation der abstrakten Struktur . . . . . . . . . . . . . . . 55

2.9.2 Spezifikation der graphischen Darstellung . . . . . . . . . . . . 59

2.9.3 Zusammenhang zur Repräsentationsgraphik . . . . . . . . . . . 62

2.9.4 Das Klassenmodell und Pfadausdrücke in DEViL . . . . . . . . 64

2.9.5 Eigenschaften generierter Umgebungen . . . . . . . . . . . . . . 65

KAPITEL 2. GRUNDLAGEN

Im folgenden Kapitel soll die Basis zum Verständnis dieser Arbeit geschaffen wer-

den. Visuelle Sprachen werden vorgestellt und ihre Eigenschaften untersucht. Da-

nach werden Programmvisualisierung, Programmanimation sowie Algorithmenani-

mationssysteme betrachtet, da sie sowohl eine Simulations- als auch eine Animati-

onskomponente enthalten. Auch andere Generatorsysteme im Umfeld der visuellen

Sprachen werden anschließend untersucht. Zum Schluss des Kapitels wird auf die

Architektur sowie das Spezifikationskonzept von DEViL eingegangen. Dies ist not-

wendig, da die Ergebnisse dieser Arbeit, Spezifikationsaspekte des Generators wie-

der aufgreifen.

2.1 Visuelle Sprachen

Graphische Darstellungen haben in der Softwareentwicklung eine lange Historie. So

konnte Haibt in den 1950er Jahren aus Flußdiagrammen Assembler- und Fortran-Code

generieren [1]. Diese Diagramme können bereits als “visuelle Sprache“ zur Darstel-

lung von Software bezeichnet werden. Um jedoch den Begriff “visuelle Sprache“

zu definieren, ist es zunächst wichtig zu definieren, was “visuell“ eigentlich bedeutet.

Der Begriff “visuell“ haftet heute aus marketingtechnischen Gründen auch Systemen

an, die im hier später definierten Sinn nicht wirklich visuelle Sprachelemente benut-

zen. VisualBasic und Visual C++ sind so zum Beispiel Programmierumgebungen,

die einen im Wesentlichen textuellen Editor erweitern und Methoden integrieren,

die das Programmieren erleichtern. Zu nennen sind hier das automatische Ergänzen

von Methodennamen, umfangreiche Refactoringfunktionalitäten oder eine direkte

Hilfe zu API-Funktionen. Das eigentliche Erstellen der Software erfolgt allerdings

häufig noch mit einer herkömmlichen textuellen Sprache. Visuelle Sprachen (VL) wie

z. B. UML setzen dabei auf vorwiegend graphische Notationselemente wie Farbe,

Form, Layout etc., sie schränken jedoch meist auch die Anwendungsdomäne stärker

ein. Sie werden also domänen- oder auch anwendungsspezifischer. Dabei gilt in der

Regel, dass Ausdrucksstärke ×Domänengröße konstant ist [79]. Schiffers [100]

Definition von visuell:

“Visuell ist die Bezeichnung für jene Eigenschaft eines Objekts, durch die min-

destens eine Information über das Objekt, die für das Erreichen eines Handlungs-

ziels unverzichtbar ist, nur durch das visuelle Wahrnehmungssystem des Men-

schen gewonnen werden kann.“

Schiffer meint damit, dass das visuelle Wahrnehmungssystem des Menschen als “un-

verzichtbares“ Instrumentarium notwendig ist. Textuelle Spezifikationen schließt er

nicht aus, verweist jedoch darauf, dass diese primär das verbale Verarbeitungssystem

des Menschen ansprechen. Price et al. gehen in [10] bei der Definition von “visuell“

noch einen Schritt weiter und verweisen auf eine Definition von “visuell“ im Oxford

Dictionary, wobei visuell sich nicht auf die Wahrnehmung mit dem Auge beschränkt,

2.1. VISUELLE SPRACHEN

sondern eher ein mentales Bild im Geiste formen soll. Diese Definition des Begriffs

“visuell“ ist die Umfassendste, denn sie schließt auch andere Sinne mit ein. So gibt

es auch Versuche den Gehörsinn in der Softwareentwicklung zu berücksichtigen [11].

Myers [71] definiert eine visuelle Sprache als ein System, das Graphik einsetzt.

Diese Definition ist sehr schwammig und bezieht sogar Systeme wie VisualBasic ein,

die eine ikonische Oberfläche anbieten, deren inhärente Programmierstruktur jedoch

rein textuell ist.

Schiffers Definition ist auch hier genauer:

“Eine visuelle Sprache ist eine formale Sprache mit visueller Syntax oder visu-

eller Semantik und dynamischer oder statischer Zeichengebung.“

Schiffers Definition geht insbesondere auf die visuelle Syntax ein und meint damit

eine graphische Notation der Grundsymbole. Mit visueller Semantik ist der Laufzeit-

zustand der visuellen Objekte gemeint, der ebenfalls visuell sein kann. Dynamische

Zeichengebung bedeutet dabei die Darstellung von flüchtigen Vorgängen, z. B. das

Aufblinken eines Objekts, das sich verändert.

Schmidt hat in [101] den Begriff der visuellen Sprache noch verfeinert. Er un-

terscheidet zwischen echt visuellen Sprachen, deren “wesentliche Teile“ eine

graphische Notation haben und textuellen Sprachen. Insbesondere definiert Schmidt

visuelle Sprachen als eine Obermenge der textuellen Sprachen. Er nennt Python [47]

als Beispiel, das - neben einer rein textuellen Syntax - Einrückung als semantisches

Äquivalent zu Blöcken betrachtet. Ich werde seine Definition beibehalten und mit

visuellen Sprachen echt visuelle Sprachen bezeichnen. Textuelle Sprachen verstehe

ich als Sprachen mit hauptsächlich “verbaler“ Syntax, wie Schiffer es auch definiert.

Die von Schiffer angesprochene dynamische Zeichengebung, also die Darstel-

lung flüchtiger Vorgänge werde ich im Folgenden als Animation bezeichnen. Eine

Animation ist somit die Visualisierung eines Zustandes oder einer Zustands-

änderung einer Programminstanz einer visuellen Sprache durch eine geeignete

graphische Darstellung. Ihr Zweck ist die Darstellung diskreter Zustandsübergänge,

die ansonsten nicht erfasst werden könnten oder das Hinweisen auf interessante

Stellen in einer Programmausführung. Am häufigsten eingesetzt wird die Animation

um eine Bewegung einer Struktur darzustellen. Dabei visualisiert die Animation

kontinuierliche Transformationen der Programminstanz.

Die Transformation eines visuellen Programms bedeutete bisher im statischen

Sinne, dass eine Manipulation durch einen Benutzer stattfindet. Der Benutzer

editiert die Struktur durch vordefinierte Funktionen. In Struktureditoren, wie sie

in dieser Arbeit betrachtet werden, sind dies: das Einfügen, Löschen, Klonen und

das Bewegen von Objekten bzw. das Ändern von Attributen eines Objekts. Diese

Manipulation wird innerhalb einer Simulation nun durch einen Zustandübergangs-

automaten ausgelöst. Dieser Automat wird später als Simulator bezeichnet. Die

KAPITEL 2. GRUNDLAGEN

Simulation ist dann der Vorgang der durch den Simulator ausgelöst wird. Die konti-

nuierliche Interpolation zwischen diskreten Simulationsschritten ist die Animation.

Die Simulation visueller Sprachen und insbesondere die Animation der Simu-

lationsschritte wird heute noch nicht häufig eingesetzt [89]. Dies erscheint aufgrund

der oben genannten Vorteile von Animation, und der Tatsache dass dies bereits

sehr früh erkannt wurde, als unverständlich. Es ist aber erklärlich aufgrund des

mehrdimensionalen Schwierigkeitsgrades. Es müssen Techniken aus der Simulation

und aus der Visualisierung zusammengeführt und angewendet werden.

In den nächsten Abschnitten sollen visuelle Sprachen und ihre Eigenschaften

in Bezug zu herkömmlichen allgemeinen Sprachen gesetzt werden. Insbesondere

gehe ich auf den Nutzen von Animation ein.

2.2 Eigenschaften visueller Sprachen und ihre

Historie

Schiffer nennt eine ganze Reihe von Vorteilen visueller Sprachen gegenüber rein

textuellen. So werden vom Menschen Bilder viel schneller als Texte verstanden.

Laut Kognitionspsychologie werden verbale Informationen sequentiell verarbeitet,

wohingegen visuelle parallel verarbeitet werden können. Das führt dazu, dass mit

einer visuellen Notation mehr Informationen gleichzeitig wahrgenommen werden

können.

Die Einführung von piktogrammorientierten Systemen mit natürlichen Meta-

phern zur Steuerung des Rechners (mit Desktop-Metapher) hat die Bedienung

des Computers wesentlich vereinfacht; sie sind heute nicht mehr aus dem Alltag

wegzudenken. Gerade bekannte visuelle Metaphern führen dazu, dass sich ein

künstliches System besser verstehen lässt. Für abstrakte Konzepte gibt es häufig

jedoch keine Bilder oder die Benutzung von Bildern kann zu Missverständnissen

führen. In Abbildung 2.1 sind Harels Higraphen [45] als ein Beispiel zu sehen,

wie Missverständnisse bei der visuellen Notation von Mengen entstehen können.

Laut Harel ist die ursprüngliche Mengennotation mehrdeutig. Woraus besteht die

Menge A? Sich überlagernde Mengen in der Abbildung links können nicht eindeutig

definiert werden. Harel schlägt eine alternative Darstellung vor (Abbildung 2.1

rechts). Dieses kleine Beispiel verdeutlicht bereits die Interpretationsproblematik bei

visuellen Darstellungen, obwohl nur wenige graphische Konstrukte benutzt werden.

Shu [108] bezeichnet Bilder als mächtige Kommunikationsmittel, da es keine Sprach-

barrieren gibt. Allerdings gibt es trotzdem Probleme bei der Interpretation, die sich

hauptsächlich aus der Erfahrung eines Betrachters ergeben. So ist der Verständnis-

prozess eines visuellen Ausdrucks bei einem geübten Menschen wesentlich schneller

2.2. EIGENSCHAFTEN VISUELLER SPRACHEN UND IHRE HISTORIE

Abbildung 2.1: Mißverständnisse bei visueller Notation: Woraus besteht die

Menge A?

als bei einem ungeübten. Außerdem benötigen visuelle Ausdrücke nicht unbedingt

ein tiefes Verständnis von zu Grunde liegenden computerspezifischen Methoden.

Die hohe Dichte an Informationen in einem Bild und die direkte Manipulation von

Objekten können die Arbeit mit visuellen Ausdrücken wesentlich vereinfachen.

Trotzdem ist die geometrische Darstellung von Software problematisch, weil sie

keine Struktur im Raum hat. In visuellen Darstellungen ist aber gerade die räumliche

Anordnung häufig wichtig. Konzepte wie räumliche Positionierung, ”Enthaltensein“

oder ”Überlappung“ tragen hier in der Regel eine Semantik. Diese kann jedoch bei

der Darstellung als Graphik zu Platzproblemen führen, was die Informationsdichte

wiederum verringert. Auch können komplexe Abläufe ebensolche Darstellungen

zur Folge haben.

Der oft zitierte Satz “Ein Bild sagt mehr als 1000 Worte“ scheint bei der visuel-

len Programmierung nicht immer zu stimmen, denn unterschiedliche Betrachter

interpretieren Bilder anders. Häufig hängt die Interpretation einer visuellen Notati-

on auch vom Kontext ab. Eine einheitliche Übereinkunft, um visuelle Programme

eindeutig zu machen, besteht nicht [86].

Diagramme können oft nicht sofort erfasst werden, da die visuelle Notation

erst erlernt werden muss. Es gibt keine Regeln, wie Diagramme zu lesen sind. Falls

mehrere Diagramme zu einer visuellen Sprache gehören, ist auch nicht unmittelbar

klar, wo der Einstiegspunkt ist. In textuellen Sprachen ist dies jedoch recht klar

bestimmt (durch die Leserichtung) und auch Mehrdeutigkeiten können anhand des

Kontextes erkannt werden.

Visuelle Sprachen sind somit besonders von Vorteil wenn Metaphern einer be-

KAPITEL 2. GRUNDLAGEN

stimmten Domäne benutzt werden oder wenn graphische Objekte strengen

allgemein gültigen Konventionen unterliegen (z. B. das “Heimat”-Piktogramm

in graphischen Bedienoberflächen, das immer den Heimatordner des jeweiligen

Benutzers referenziert). Eine gute Gestaltung, der Einsatz von sekundärer Notation

und Mechanismen, um relevante Daten zu zeigen, machen also eine gute visuelle

Sprache aus.

Schmidt geht sogar noch weiter: Wenn visuelle Sprachen eine Obermenge der

textuellen Sprachen sind, dann gibt es für jedes Problem eine visuelle Sprache,

die mindestens genauso gut ist wie jede textuelle Sprache, die das Problem

beschreibt. Insbesondere verweist Schmidt auf die Layoutfreiheiten visueller Spra-

chen, die bestimmte Strukturen besser abbilden und auf zusätzliche informelle

Zusatzinformationen, die eingebettet werden können. Zusätzlich können Interak-

tionsmechanismen durch geeignete Symbolik direkt in visuelle Repräsentanten

eingebaut werden. Beispiele sind “Griffe“ zum Anfassen visueller Objekte oder ein

“+“-Symbol zum Ausklappen bestimmter Bereiche.

Inkrementelle Entwicklung ist ein weiterer Vorteil von visuellen Sprachen. Ob-

jekte können leicht nachträglich manipuliert oder modifiziert werden. So kann in

einem UML-Klassendiagramm sehr einfach eine neue Klasse eingefügt werden,

indem andere Objekte entsprechend verschoben werden. In einer rein textuellen

Darstellung ist dies nicht so einfach möglich. Oft müssen mehrere Dateien geöffnet

werden und Fragmente von verschiedenen Positionen kopiert werden. Dann muss

Platz geschaffen werden, was in der Regel mehr Aufwand erzeugt. Die Haupt-

nachteile einer visuellen Sprache werden im Allgemeinen im Platzbedarf und beim

Aufwand der Konstruktion gesehen. So benötigt ein visuelles Programm - bedingt

durch Verschnitt - wesentlich mehr Platz auf dem Bildschirm. Dies führt dazu, dass

in der Regel weniger Informationen gleichzeitig dargestellt werden können als bei

einer textuellen Sprache. Die Konstruktion eines Programms mittels einer visuellen

Sprache ist - bedingt durch die großen Mauswege - recht aufwändig. Gute Tastatur-

interaktionsmechanismen für den versierten Benutzer sind somit unumgänglich.

Ein wesentlicher, wenn nicht gar der wichtigste Vorteil von visuellen Sprachen

ist hingegen, dass auf einem extrem hohen Abstraktionsniveau gearbeitet werden

kann. Syntaktische Elemente einer textuellen Sprache werden durch graphische

Objekte mit Attributen repräsentiert. Das hohe Abstraktionsniveau erlaubt eine

Entkopplung von der Zielsprache, die ggf. sogar austauschbar ist. Spezielle Editoren

können dem Anwender bei der Konstruktion eines visuellen Programms helfen.

Gerade in speziellen Domänen ist ein Einsatz sinnvoll, wenn die Anzahl der

der Sprachkonstrukte eng gefasst ist oder der Anwenderkreis auf Nicht-Experten

eingeschränkt ist.

2.2. EIGENSCHAFTEN VISUELLER SPRACHEN UND IHRE HISTORIE

Historie Bereits in den 50er Jahren wurden graphische Systeme zur automatischen

Generierung von Flußdiagrammen aus Assembler- und Fortran-Code erstellt. Der

Nutzen solcher Flußdiagramme wurde bereits 1947 durch von Neumann und

Goldstein gezeigt. 1966 wurde das wohl erste graphische Programmiersystem von

Sutherland entwickelt. Der “Graphical Program Editor“ erlaubte die Spezifikation

von Programmen ähnlich der von Hardwareplänen. Die Programme konnten dann

interpretiert werden. Die Entwicklung von Pygmalion 1975 [109] durch David C.

Smith war ein weiterer Meilenstein. Die Idee war, Programme durch Vorzeigen

geeigneter Beispiele zu entwerfen, anstatt konkret den Programmablauf zu model-

lieren.

Ende der 70er, Anfang der 80er Jahre wurden Tabellenkalkulationssprachen

entwickelt, die weite Verbreitung fanden. VisiCalc war das erste Tabellenkalku-

lationsprogramm, das auf einer 2-D-Darstellung basierte. Dieses System war so

erfolgreich, dass sich in den nächsten Jahren etliche Arbeiten mit tabellen- und

formularbasierten Ansätzen beschäftigten. Für komplexere objektorientierte oder

komponentenbasierte Ansätze sind diese jedoch untauglich.

In den 80er Jahren wurde bereits viel im Bereich der visuellen Programmie-

rung geforscht. Visuelle Programmierung sollte auch den Endanwender in die Lage

versetzen Programme zu erstellen, so die Hoffnung.

Seit den 90er Jahren werden vermehrt kommerzielle Werkzeuge zur visuellen

Programmierung angeboten, was an der höheren Leistungsfähigkeit von Computer-

systemen und deren graphischen Bedienoberflächen liegt. So erfreut sich LabVIEW

[124] im Bereich der Hardware-Spezifikation großer Beliebtheit.

Heute ist ein neuer Trend absehbar: Die Einbettung spezialisierter domänen-

spezifischer Sprachen in allgemeine Hochsprachen [28, 29] sowie der Einsatz

visueller Sprachen im Rapid Prototyping.

Visuelle Sprachen mit dynamischer Repräsentation gehen noch einen Schritt

weiter. Sie unterstützen den Benutzer dabei, nicht nur ein syntaktisch oder se-

mantisch korrektes Programm zu erstellen, sondern zusätzlich noch die in der

Programmbeschreibung inhärenten Zustandsübergänge zu visualisieren. Die

Programminstanz ist nun nicht mehr nur statisch, sondern kann direkt ausge-

führt werden. Die Kluft zwischen Programminstanz und Programmausführung, die

jeder Anwender einer visuellen Sprache mental überbrücken muss, wird kleiner [78].

Die direkte Ausführbarkeit einer visuellen Sprache hilft auch im Rapid Proto-

typing. Hier kann von Systemeigenschaften abstrahiert und auf einem hohen

Niveau spezifiziert werden. Die Simulation auf derselben Ebene führt zu einem

direkterem Systemverständnis. Auftretende Fehler können direkt exploriert und

entfernt werden. Somit muss nicht erst das spezifizierte System generiert, übersetzt

KAPITEL 2. GRUNDLAGEN

und getestet werden, was eine erhebliche Zeitersparnis bedeutet.

In [82] werden noch einige weitere Vorteile von dynamischen Darstellungen

genannt. Diese sind:

1. die Demonstration sequentieller Aktionen in prozeduralen Aufgaben.

2. die Simulation von Modellen mit komplexem Verhalten.

3. die explizite Darstellung von eigentlich unsichtbarem Verhalten.

4. die Illustration von Verhalten, das verbal schlecht zu beschreiben ist.

5. die Bereitstellung einer visuellen Analogie für ein abstraktes Konzept.

6. die Ausrichtung der Aufmerksamkeit des Anwenders auf einen spezifischen

Aspekt.

7. die Validierung eines spezifizierten Verhaltens.

Park und Hopkins [82] zeigen Forschungsergebnisse zum Einsatz von dynamischen

Darstellungen in unterschiedlichen Medien. Die oben genannten Punkte zeigen

sowohl Einsatzzwecke von Animation auf, z. B. in der Simulation (2) und auch in

der Lehre (4, 5). Dazu werden in den folgenden Kapiteln dieser Arbeit Simulations-

werkzeuge untersucht, aber auch Werkzeuge zur Vermittlung des Verständnisses

von Algorithmen beschrieben.

Des Weiteren zeigen die Punkte bereits Eigenschaften, die ein gutes Animati-

onssystem bereitstellen sollte: Nämlich die Fähigkeit einer Animation Abläufe (seien

sie in Wirklichkeit sogar unsichtbar (3)) in geeigneter Weise darstellen zu können

(5) und dem Betrachter im richtigen Moment wichtige Teilaspekte der Simulation

vermitteln zu können (6).

2.3 Programm- u. Softwarevisualisierung und visuelle

Programmierung

Schon früh hat man sich im Rahmen der Softwarevisualisierung mit Algorith-

menanimation beschäftigt. Erste Systeme wurden bereits Anfang der 1980er Jahre

entwickelt. Die folgende Einordnung der Softwarevisualisierung orientiert sich stark

an der Klassifikation von Price et al. [1], da diese sehr ausführlich ist und sie noch

weiter geht als die von Myers [71], der Programmvisualisierung nur anhand von

zwei Achsen unterscheidet. Zum einen, ob Code oder Daten visualisiert werden

und zum anderen, ob die Visualisierung dynamisch oder statisch ist. Die folgende

Klassifikation von Price beruht auf der Untersuchung einer Reihe von Algorith-

menanimationssystemen bzw. visuellen Programmierwerkzeugen, berücksichtigt

jedoch keine domänenspezifischen Sprachen (DSLs). Die Klassifikation ist jedoch so

allgemein, dass sie auch für DSLs benutzt und ggf. erweitert werden kann.

2.3. PROGRAMM- U. SOFTWAREVISUALISIERUNG UND VISUELLE

PROGRAMMIERUNG

Nach Price et al. wird Softwarevisualisierung in der Literatur häufig missver-

standen und mit den Begriffen “visuelle Programmierung“,“Programmvisualisierung“,

“Algorithmenanimation“ und “Programming-by-example“ in Zusammenhang gebracht,

wobei alle Begriffe austauschbar untereinander verwendet werden. Dies ist jedoch

falsch und eine genauere Betrachtung der Begriffe ist nötig.

Softwarevisualisierung ist demnach “das Handwerk Typographie, Graphikde-

sign, Animation und Kinematographie mit moderner Mensch-Maschine-Interaktion

und Computer-Graphik Technologie einzusetzen um beides, das menschliche

Verständnis und die effektive Benutzung von Computer-Software voranzutreiben“.

Programmvisualisierung hingegen ist die Visualisierung des aktuellen Programm-

codes oder dessen Datenstruktur in entweder statischer oder dynamischer Form.

Der Begriff Programmvisualisierung wurde früher auch für Softwarevisualisierung

benutzt.

Der wesentliche Unterschied zwischen visueller Programmierung und Programm-

visualisierung ist, dass visuelle Programmierung es erlauben soll, Programme

einfacher zu spezifizieren. Softwarevisualisierung soll Programme und visuelle

Spezifikationen leichter verständlich machen.

Programmvisualisierung ist jedoch mit dem Programmcode, also einem niedri-

gen Abstraktionslevel konnotiert, wohingegen Softwarevisualisierung eher mit dem

Algorithmenlevel verbunden ist. Myers Klassifikation unterscheidet zwischen Code

und Datenvisualisierung und zwischen statischer und dynamischer Animation.

Eine statische Code-Visualisierung ist somit z. B. ein Prettyprinter wie Baeckers SEE

Program Visualizer [5], der Quellcode für das menschliche Auge aufbereitet und

Gebrauch von Einrückungen und Kommentaren als sekundäre Notation macht.

Ein Beispiel für eine statische Datenvisualisierung wäre die Darstellung einer

verknüpften Liste mit ihren aktuellen Werten. Eine animierte Code-Visualisierung

wäre die Darstellung eines Debuggers, der anzeigt, welche Programmzeile gerade

ausgeführt wird. Eine dynamische Datenvisualisierung wäre somit eine statische

Datenvisualisierung mit veränderlichen Inhalten, also z. B. eine Algorithmenvisuali-

sierung wie das Vertauschen von Elementen bei einem Sortieralgorithmus.

Shu unterteilt visuelle Sprachen in der Klassifikation aus [108] in drei Ausprä-

gungen: Ihrem Anwendungsgebiet, dem Ausmaß an rein visuellen Konstrukten,

die die Sprache benutzt und wie groß die Entfernung zwischen Problem und

Problemlösung durch das Programm ist.

Die Abbildung zwischen Problem und Problemlösung betrachten auch Cox et

al. in [22]. Dort wird nicht nur die Entfernung betrachtet, sondern die Art, wie

KAPITEL 2. GRUNDLAGEN

Abbildung 2.2: Framework zur Klassifizierung von Softwarevisualisierung

Programminformationen dargestellt werden. Dies rückt die zu untersuchende

Problematik in den Vordergrund. Bereits hier sei gesagt, dass diese Arbeit und das

erweiterte DEViL Framework alle Klassifikationen nach Cox abdecken kann. Cox

unterscheidet folgende Abbildungen:

•Direct: ist die unmittelbare Abbildung eines Aspekts des Programms auf ein

Bild. Es wird keine weitere Abstraktion hinzugefügt, z. B.: beim Sortieren von

Listenelementen wird die Größe eines Elements auf ein Rechteck entsprechen-

der Größe abgebildet.

•Structural: in der Simulation versteckte oder zusätzliche Daten werden darge-

stellt, z. B. das Pivotelement im Quicksort-Algorithmus.

•Synthesized: hierbei werden Daten gezeigt, die nicht unmittelbar aus der Simu-

lation abgeleitet werden können, aber aus zusätzlichen Berechnungen ermittelt

werden können, z. B. die akkumulierte Ausführungshistorie des Sortierens.

•Analytical: hierbei wird von der Repräsentation differenziert und abstrakte Ei-

genschaften der Struktur oder des Verhaltens des Programms dargestellt, z. B.

Aussagen wie “alle Elemente kleiner als Index isind korrekt sortiert”.

•Explanatory: hierbei wird versucht das Verständnis des Beobachters zu erwei-

tern indem zusätzliche visuelle Hinweise in das Programm eingearbeitet wer-

den, z. B. die weiche Animation oder zusätzliche textuelle Hinweise, die die

Aktion erläutern.

In [97] heben Cox et al. noch hervor, dass besonders Abbildungen der letzten Katego-

rie ein hohes Maß an Flexibilität erfordern. Programmzustand, Zustandsübergänge

und deren Animation liegen weit voneinander entfernt.

Price et al. schlagen ein Framework zur Klassifizierung von Softwarevisualisierungs-

systemen vor (Abb. 2.2). Aus diesem Framework lassen sich direkt Anforderungen

für simulierbare DSLs ableiten. So sollte eine gute Software-Visualisierung in allen

von Price et al. genannten Teilbereichen hohe Werte erzielen. Prices Framework ist

jedoch so umfangreich, dass eine detailierte Darstellung an dieser Stelle den Rahmen

2.4. ANIMATION

der Arbeit sprengen würde.

Stasko et al. nennen im Rahmen ihres Algorithmenanimationssystems DANCE

[112] weitere Anforderungen, die nicht nur für Algorithmenanimation gelten

können:

•Ease of Design: Animationsdesigner können von der Simulation abstrahieren

und beliebige Animationen erstellen. Low-Level-Details sind dabei für den An-

wender transparent.

•Program development support: Es existieren diverse Mechanismen um Program-

mierfehler zu vermeiden und zusätzliche Hilfen um Simulationen zu entwi-

ckeln bzw. Fehler zu verstehen.

•Rapid-Prototyping: Die Animation (in DANCE) wird visuell spezifiziert, somit

ist sehr schnelles Feedback möglich.

•Ability to fine-tune: Überschreiben von Code um Animationen zu erreichen, die

“genauso und nicht anders aussehen” müssen.

Dass graphische Modelle und deren Animation das Verständnis einer Simulation un-

terstützen ist bereits seit langem bekannt [99]. Trotzdem ist die Simulation im Bereich

der DSLs noch nicht weit verbreitet [89]. Vielleicht auch, weil es durchaus schwierig

ist, den Ablauf von DSLs einfach zu spezifizieren und für einen ggf. anderen Nut-

zerkreis verständlich und übersichtlich aufzubereiten. Die Animationskomponente

wurde hier häufig vernachlässigt.

2.4 Animation

In der Programmvisualisierung wird der Begriff der Animation häufig nur implizit

eingesetzt, in dieser Arbeit ist er jedoch sehr wichtig. Es muss genau betrachtet

werden, ob es sich lohnt eine Animation zu erstellen. Diese ist nicht immer nötig und

kann oft auch sehr teuer sein [85]. Mit automatisch generierten Animationen ist diese

Designentscheidung jedoch nicht mehr so wichtig. Der Mehrwert einer Animation

muss genau abgewogen werden und liegt in der zusätzlichen Erfahrung, die aus

einer Animation gewonnen werden kann [95]. Für Lehr- und Lernzwecke kann

eine visuelle Simulation eine gute Basis sein. Auch in Systemen in denen Aktionen

gleichzeitig ausgeführt werden, z. B. in Petri-Netzen oder in der nebenläufigen

Programmierung ist eine Animation besonders geeignet.

Programmvisualisierung bzw. Animation ist jedoch kein Allheilmittel [7] für

das Verständnis von Software. Eine Programmvisualisierung ist nicht unmittelbar

verständlich und muss ebenfalls gelernt werden, da auch hier sehr stark vom

eigentlichen Problem abstrahiert werden kann und sich die Darstellung vom zu

Grunde liegende Problem stark unterscheiden kann. Eine Animation ist nicht zwin-

gend für jedes Problem geeignet, sie stellt auch die Problematik nicht unmittelbar

KAPITEL 2. GRUNDLAGEN

einleuchtend dar. Sie muss der Zielgruppe angepasst werden und so ist es oft von

Vorteil, wenn die Animation von Experten des Problembereichs entworfen wird.

Einfache Spezifikationstechniken werden somit unumgänglich.

Der Einsatzzweck einer Animation muss genau überlegt werden. Simulationen sind

oft sehr groß. Der animierte Teil, der von Interesse ist, kann jedoch sehr klein sein.

Hier kann Animation als Validierungsmittel für die Simulation eingesetzt werden.

Manchmal ist auch der Modellierer der Simulation der Entscheidungsträger und eine

Animation erübrigt sich. Andere Simulationssysteme sind evtl. stochastischer Natur,

bei der Zwischenstände nicht von Belang sind. Hier sind mehrere Simulationsläufe,

die Log-Ausgaben erzeugen relevanter als eine Animation. Oft wird eine Animation

auch erstellt um einen anderen Nutzerkreis, z. B. Entscheidungsträger anzusprechen.

Animation ist also dann von Vorteil, wenn aus ihr ein echter Mehrwert gewon-

nen werden kann. Dies kann zu Ausbildungszwecken, zur Validierung oder auch für

Präsentationen der Fall sein. So wird beispielsweise in [76] eine primitive Animation

eingesetzt um eine natürliche Sprache zu lehren.

Die Animationskomponente (als Teil einer Programmvisualisierung oder einer

Simulation) sorgt für die graphische Animation von Objekten in all ihren Facetten:

Von einfachen Farbänderungen bis zu komplexen animierten Pfaden in unterschied-

lichen Geschwindigkeiten. Die Simulation sorgt für die zeitliche Abstimmung und

die Triggerung der Animation. Sie teilt der Animation mit, was wann animiert

werden soll. Die Animationskomponente kann man sich dabei als eine Sammlung

abstrakter Funktionen vorstellen, die auf graphischen Objekten operieren. Die

Sammlung an sich besteht aus einer Menge von Animationstypen, die vordefiniert

sind. Die Simulation füllt diese abstrakten Funktionen mit konkreten Werten. Sie

bildet ihren Zustand auf die Animation ab.

Nach Baecker [4] sollte Animation dabei unterstützen komplexe Strukturen

und Funktionen darzustellen und zu untersuchen. Animation hat dabei unter-

schiedliche Ausprägungen in Form und Funktion. Prinzipiell soll sie eine kausale

Verbindung zwischen einem alten und einem neuen diskreten Zustand schaffen,

der ohne Animation nicht unmitelbar klar ist [18]. Durch diesen hinweisenden

Effekt muss der Anwender nicht darüber nachdenken was sich wo geändert hat

und kann sich der eigentlichen Aufgabe widmen. Bei der visuellen Programmierung

kommt hinzu, dass der Programmierer bereits mit visuellen Konstrukten arbeitet,

diese Konstrukte jedoch nur statisch sind. Das Programm, das er spezifiziert, ist

jedoch in der Regel dynamisch. D. h. er muss trotzdem ein mentales Bild des

dynamischen Ausführungsverhaltens seines Programms vor Augen haben. Warum

sollte eine Animation ihm also nicht dabei helfen, die Kluft zwischen Programm und

Programmausführung zu verringern?

In [73] wird zunächst zwischen Basic Animation,Motion Animation und Cartoon

2.4. ANIMATION

Abbildung 2.3: Sogenannte “Effect Lines” (Schattenrisse) um Geschwindigkeit

zu verdeutlichen, aus [55]

Animation unterschieden. Mit Basic Animation sind einfache Animationen wie Blin-

ken oder das Wechseln von Farbe bzw. Bitmap Graphiken gemeint. Diese Art der

Animation hat in der Regel nur einen hinweisenden Effekt und soll häufig nur das

Auge des Betrachters auf eine Stelle lenken in der etwas geschieht. Das Ändern von

Bitmap Graphiken zeigt häufig den Zustand des Objekts an.

Motion Animation stellt die Bewegung von Objekten dar. Häufig wird ein Pfad

zwischen zwei so genannten Schlüsselbildern interpoliert. Die Bewegung kann aller-

dings auch dem “Path-Transition“ Paradigma folgen und eine beliebige Punkteliste

darstellen, über die sich ein Objekt bewegt. Minas stellt in [69] eine so genannte

“parametrisierbare Bewegung“ vor, in der die Bewegung von (x0, y0)nach (x1, y1)

nicht durch zwei Schlüsselbilder, sondern durch Gleichungssysteme der Form

x= (x1−x0)λ+x0

y= (y1−y0)λ+y0λ∈[0,1]

beschrieben wird. “Programmierbare Bewegungen“ erweitern dieses Konzept noch

durch algorithmische Spezifikationen.

Cartoon Animation übernimmt klassische Effekte der Trickfilmanimation, die die

Animation somit einfacher verständlich und flüssiger erscheinen lässt. Physikalische

Effekte der echten Welt werden in das System übernommen. So stoppen Objekte

nicht abrupt in einer Bewegung, sondern pendeln sanft aus. Weitere Effekte sind

z. B. ein Vibrieren von Objekten, die im Begriff sind sich zu bewegen. Auch “Antici-

pation”, d. h. Objekte bewegen sich zunächst in die entgegengesetzte Richtung bzw.

“Exaggeration”, also die Übertreibung sind beliebte Stilmittel um anspruchsvolle

Animationen zu erreichen. In [55] werden zusätzliche Linien und Schattenrisse

hinter sich schnell bewegenden Objekten gezeichnet (Abb. 2.3). Das Morphen von

Farben zur Darstellung des Alters von Objekten geht in eine ähnliche Richtung wie

die Effect-Lines. Hier tragen graphische Konstrukte semantische Informationen.

Die Bedeutung von Farben in der Animation heben Nardi et al. in [77] hervor. Die

KAPITEL 2. GRUNDLAGEN

Effect-Lines führen später zum Konzept der statischen Animationsobjekte (vgl.

Abschnitt 5.1.7). All diese Varianten der Animation dienen dazu, die dynamische

Zeichengebung leicht verständlich zu machen und die Simulation in geeigneter

Weise darzustellen.

Lasseter et al. zeigen in [63] einen guten Überblick zur Animation anhand der

Illustration von Filmen. Sie identifizieren im Wesentlichen folgende Animationsar-

ten:

•Squash and Stretch definiert die Masse oder Festigkeit eines Objekts. Objekte

bleiben während einer Bewegung in der Regel nicht starr. Sie werden gedehnt

und gestaucht. Dadurch erreicht man, dass Geschwindigkeit besser wahrge-

nommen wird. Betrachter können den Objekten besser folgen.

•Timing also die Geschwindigkeit einer Aktion ordnet ihr Bedeutung zu. Je nach-

dem wie schnell eine Aktion ausgeführt wird, kann sie eine unterschiedliche

Semantik tragen. So kann gleichartigen Objekten durch ein unterschiedliches

Timing ein unterschiedliches Gewicht zugeordnet werden. Das schwerere Ob-

jekt wird nur langsam beschleunigt, während das leichte Objekt sehr schnell

seine Endgeschwindigkeit erreicht.

•Anticipation beschreibt die Vorbereitung auf eine Aktion. Sie wird benutzt um

den Anwender auf einen Ort hinzuweisen, an dem in Kürze etwas passieren

wird. Diese Art der Animation führt später in der Arbeit zum Konzept des Trig-

gerns von Animationsobjekten.

•Staging bedeutet eine Aktion so zu präsentieren, dass sie unmittelbar einleuch-

tend erscheint. Dies wird häufig dadurch erreicht, dass zu einer wichtigen Stel-

le hingezoomt wird oder die Beleuchtung entsprechend angepasst wird, sodass

das Objekt quasi im Rampenlicht steht.

•Follow Through and Overlapping Action wird dazu verwendet, eine Aktion zu be-

enden und zu einer anderen überzuleiten. Dass eine Aktion abrupt zur nächs-

ten Aktion führt ist in der Realität eher selten zu sehen, ein Überlappen von

Aktionen führt zu einer harmonischeren Animation.

•Straight ahead action and pose-to-pose action sind zwei gegensätzliche Ansätze zur

Entwicklung von Animationen. Eine Variante basiert auf einem ad-hoc Ent-

wicklungsansatz, wodurch Spontanität entsteht, während die andere Variante

planvoller ist.

•Slow In and Out bezieht sich auf die zeitliche Abstimmung in Bewegungen. Ob-

jekte bewegen sich nicht konstant sondern werden langsam beschleunigt und

abgebremst.

•Arcs sind geschwungene Bewegungspfade für Animationsobjekte. Bewegun-

gen erscheinen so natürlicher.

•Exaggeration also die Übertreibung ist gerade in Cartoon Animation ein belieb-

tes Stilmittel.

2.4. ANIMATION

Automation level Technique

1 frame-wise

2 keyframe

3 algorithmic / task-level Animation

4 actor-based Animation

Abbildung 2.4: Technische Klassifikation von Animation

•Secondary Action sind Aktionen, die als Resultat von anderen Aktionen entste-

hen. Sie werden eingesetzt um ein Interesse zu erhöhen und der Animation eine

realistische Komplexität zu geben. Die Bewegung einer Figur als Kernidee wird

beispielsweise durch eine zweitrangige Aktion, wie die Mimik unterstützt.

Als letzten Aspekt nennen Lasseter et al. Appeal also den Anreiz. Eine Animation

wird erst dann gut, wenn ihre Visualisierung sorgsam ist und die Idee, die sie

vermitteln soll, dem Publikum klar wird.

Paelke beschreibt in [81] noch einige weitere Techniken um gute Animationen

zu erstellen. Sie basieren darauf, geeignete Kameraperspektiven oder auch mehrere

unterschiedliche Sichten auf denselben Sachverhalt zu wählen. Außerdem kann eine

Szenerie geeignet beleuchtet werden um eine Idee zu transportieren. Diese eher

auf die Animation von dreidimensionalen Szenen ausgelegten Animationsarten

werde ich hier nicht genauer beschreiben, da sich diese Arbeit im Rahmen der

zweidimensionalen visuellen Sprachen bewegt.

Nach Bertin [8] sind so genannte “Marks” die Grundelemente auf denen Vi-

sualisierungen aufbauen. Sie sind durch ihre Position und sechs weitere Attribute

(Größe, Orientierung, Grauwert, Farbe, Text sowie Form) charakterisiert. Die

Definition der “Marks” charakterisiert auch die Repräsentation von DEViLs Struk-

turobjekten sehr gut. Auch diese werden durch einfache Primitive zu komplexen

graphischen Darstellungen zusammengestellt. In [73] ist eine knappe Übersicht

gegeben, wie Animation technisch klassifiziert wird:

Bei der frame-wise-Animation (Level 1) werden die einzelnen Bilder der Animation

in einem gesonderten Editor von Hand produziert. Ein Player akzeptiert diese Bilder

und spielt sie dann ab. Bei der keyframe-Animation (Level 2) werden Schlüsselbilder

vorgegeben. Die Animation wird dann durch Interpolation generiert. Die Bewegung

kann dabei einem bestimmten Pfad folgen. Keyframe-Animation kann auch durch

Attribute der Objekte parametrisiert werden. Bei der algorithmischen oder task-level-

Animation (Level 3) wird definiert, was animiert werden soll und nicht wie dies

geschehen soll. Die algorithmische Animation wird dabei durch eine Sequenz von

parametrisierten Transformationen bestimmt. Bei der task-level Animation wird die

Bewegung in abstrakten Aufgaben beschrieben wie “bewege Objekt von A nach B“.

Die actor-based-Animation folgt dem objektorientierten Ansatz. Die Aktoren führen

dabei die Animation selbständig aus. Vorher werden Regeln definiert, die aussagen,

KAPITEL 2. GRUNDLAGEN

in welcher Weise Zustandsübergänge erfolgen sollen.

Ein weiterer Aspekt ist die Nachbildung realer physischer Abläufe. Hierzu ist

es notwendig, dass physikalische Gegebenheiten, wie zum Beispiel Schwerkraft,

Wind oder Federkräfte geeignet und einfach in die Animation mit eingebunden

werden. Die physikalische Animation wird allerdings nur sehr selten von Anima-

tionsentwicklern eingesetzt [25] und wird in dieser Arbeit zunächst keine Rolle

spielen. Außerdem wird sie häufig nur in sehr speziellen Anwendungsszenarien

eingesetzt, die in der Regel anspruchsvolle Simulationen sind und nur am Rande

etwas mit visuellen Sprachen zu tun haben.

Animationen können schnell sehr komplex und groß werden. Hier kann es

notwendig sein weitere Techniken einzusetzen. Zum Beispiel Kamerafahrten zu

Punkten in der Animation an denen gerade Aktionen stattfinden [81] (falls im

aktuellen Fenster der entsprechende Teil nicht sichtbar ist). Weitere alternative

Kameraperspektiven, semantisches Zoomen, transparente Objekte, Ebenen oder

ganz andere visuelle Darstellungen (Fisheye, 3D,...) können verwendet werden [87].

Insgesamt lassen sich die in Abbildung 2.5 beschriebenen Grundtypen der Anima-

tionsarten definieren, die einen Ausschnitt aus dem Spektrum der Möglichkeiten

sind. Prinzipiell sind hier dem phantasievollen Animator keine Grenzen gesetzt.

2.5 Simulation

Bisher wurde die Animation, also die dynamische Zeichengebung betrachtet. Ihr zu

Grunde liegt ein Algorithmus, der die Animationen ausführt. Systematisch betrach-

tet wird eine Eingabe (das Programm) durch eine vorgegebene Semantik ausgeführt.

Ausführung bedeutet, dass eine Struktur oder ein Modell existiert, in dem Zustände

gespeichert und modifiziert werden können. Diese Zustandsübergänge triggern

dann Animationen. Im Folgenden sollen Simulation und Simulationsstrukturen

genauer betrachtet werden. Begriffe wie Simulationsmodell und ereignisbasierte

Simulation werden eingeführt. Danach folgt ein Überblick auf existierende Simu-

lationswerkzeuge und ihre Bedeutung im Kontext dieser Arbeit. Dazu gehören

Simulationssprachen, allgemeine Hochsprachen mit Simulationsunterstützung

sowie Bibliotheken zur Simulation.

Simulation ist die Disziplin ein Modell eines realen oder eines nur theoretisch

existierenden Systems zu entwerfen, dieses Modell auszuführen und es zu analysie-

ren [36]. Im Gegensatz zu mathematischen Modellen, die Endzustände berechnen,

bilden Simulationen Dynamik ab. Simulation wird interdisziplinär angewendet.

Wetter- und n-Körper-Simulationen sowie Anwendungen in der künstlichen

Intelligenz und Virtual Reality zeigen die vielfältigen Facetten der Simulation. Simu-

2.5. SIMULATION

Operation Beschreibung

Objekte

create Objekt wird neu erstellt, es wird dabei ausge-

hend von einem Punkt bis zur endgültigen Grö-

ße vergrößert.

delete Objekt wird bis zur Unkenntlichkeit verkleinert

und dann entfernt (fade-out)

toFront Objekt wird auf die oberste Ebene verlagert.

Ggf. Durchdringung anderer Objekte via Trans-

parenz.

toBack Objekt wird auf die unterste Ebene verlagert.

Ggf. Durchdringung anderer Objekte via Trans-

parenz.

blink Objekt blinkt

colorChange(Color) Objekt verändert Farbe (abrupt oder kontinuier-

lich)

rotate(degree) Objekt wird rotiert

scale(delta) Objekt wird skaliert

substitute(X,Y) Objekt X wird durch Objekt Y ersetzt.

shake Objekt vibriert

Bewegung

move(a, b) direkte Bewegung eines Objekts von a nach b

moveSlowInAndOut(a, b) Bewegung von a nach b, am Anfang/Ende lang-

samer

moveArcs(a,b) Objekt wird in einer Kurvenform von a nach b

bewegt.

parametricMove(f) Objekt wird durch Funktion f bewegt.

programmedMove(alg) Objekt wird durch Algorithmus bewegt.

Komposition

AnimxAnimation x Mal wiederholen

AnimX •AnimY Animation X vor Animation Y ausführen

AnimX ΘAnimY Animation X und Y gleichzeitig ausführen

Abbildung 2.5: Animationsarten

KAPITEL 2. GRUNDLAGEN

lationen die auf besonders großen Datenmengen arbeiten, z. B. Klimasimulationen,

erforden häufig den Einsatz von Großrechnern.

Eine Simulation führt häufig zu einem erhöhten Systemverständnis, auch kann

ein komplexes reales System oft nicht analytisch erfasst werden bzw. das reale

System ist nicht einfach zu manipulieren. Häufig existiert das reale System noch

gar nicht. Dies ist beispielsweise bei der Simulation von Fabrikanlagen der Fall,

bei der die Fertigungsstraßen schon vor dem eigentlichen Baubeginn auf Engpässe

hin untersucht werden können. Simulationen werden auch angewendet, um eine

bereits analytisch vorliegende Lösung zu verifizieren oder um Vorhersagen über ein

zukünftiges Verhalten zu machen.

Das Simulationsmodell ist die abstrakte logische und mathematische Repräsen-

tation eines Systems, das die Bezüge zwischen Objekten beschreibt. Durch das

wiederholte Ausführen von Operationen auf dem Simulationsmodell mit unter-

schiedlichen Parametern können Erfahrungen mit dem System gesammelt werden.

Das Simulationsmodell stellt dabei die Abbildung eines Modells in einer Struktur

dar, die es erlaubt, bestimmte Aspekte detailliert zu untersuchen, d. h. es abstrahiert

von nicht relevanten oder unnötigen Details. Diese Vereinfachung birgt jedoch

Risiken, denn ein vereinfachtes Simulationsmodell A0über ein System Aist nur gut,

wenn die Antworten, die A0über Agibt, dieselben sind, die Ageben würde.

Die Korrektheit des Simulationsmodells ist demnach für eine aussagekräftige

Simulation besonders wichtig. Ein zu niedriges Detaillevel im Modell kann zu

wertlosen Simulationsergebnissen führen. Auf der anderen Seite führt ein großer

Detaillierungsgrad zu einem undurchschaubaren Modell, sowie zu langen Simulati-

onslaufzeiten.

Simulationen benötigen den Zufall um realistische Modelle abbilden zu kön-

nen. Dazu können Zufallsvariablen bestimmter Verteilungen eingesetzt werden. Bei

einem stochastischen Simulationsmodell ist eine sorgfältige Analyse des Modells

besonders wichtig. Hier können verlässliche Aussagen oft nur getroffen werden,

wenn die Simulation häufig wiederholt wird, sodass eine Sättigung der Parameter

eintritt.

Kontinuierliche Modelle beschreiben Zustandsänderungen über die Zeit. Ihr

Zustandsübergangsmodell wird häufig durch Gleichungssysteme beschrieben.

Diskrete Simulationsmodelle hingegen unterteilen die Zeit in gleich große Ab-

schnitte. Das Zustandsübergangsmodell ist hier häufig durch einen Automaten

beschrieben. Die Zeitunterteilung der diskreten Variante kann dazu führen, dass

über einen langen Zeitraum keine Zustandsänderung eintritt. Dies wird durch

die ereignisorientierte Simulation umgangen. Hier werden Zustandsänderungen

durch Ereignisse, die in einer sortierten Liste gespeichert werden, realisiert. Die

Zeit wird dabei immer zum nächsten Ereignis fortgeschaltet. Ereignisse können

2.5. SIMULATION

dabei wieder Ereignisse auslösen, die dann auch ggf. weiter in der Zukunft in die

Ereigniswarteschlange eingeordnet werden. Durch dieses Prinzip lassen sich auch

elegant Benutzerinteraktionen oder Ausnahmebehandlungen als spezielle Ereignisse

in das Simulationsmodell integrieren.

In [36] werden mehrere Simulationsmodelle diskutiert. Interessant sind das dekla-

rative, das funktionale sowie das räumliche Simulationsmodell. Beim deklarativen

Simulationsmodell wird das Modell anhand von Ereignissen und deren Modifika-

tionen am Zustandsmodell beschrieben. Diese Zustandsänderungen werden durch

DFAs oder Markovmodelle bzw. Ereignisgraphen beschrieben. Der deklarative

Ansatz hat jedoch den Nachteil, dass sehr häufig sehr viele Zustände beschrieben

werden müssen.

Beim funktionalen Modell wird die Simulation durch das Verknüpfen von Funktio-

nen beschrieben. Eine Funktion hat dabei einen oder mehrere Eingabe-Parameter

und einen Ausgang. Die Darstellung kann hier graphisch durch Blöcke erfolgen,

die die Funktionen repräsentieren. Wird der Fokus auf eine ereignisorientierte

Simulation gelegt, so führt dies zu einer funktionalen Sichtweise.

Das räumliche Simulationsmodell fügt der Anordnung von Objekten Semantik

hinzu. Objekte können andere Objekte in der Nähe beeinflussen. Das räumliche

Simulationsmodell wird häufig durch Regeln ausgedrückt. Regeln haben jedoch den

Nachteil, dass sie sehr schnell unübersichtlich werden. Das wiederum führt zu einer

schlechten Wartbarkeit [111]. Insbesondere können komplexe Beziehungen zwischen

Objekten, die unter Umständen weit entfernt liegen nicht modelliert werden.

Des Weiteren wird häufig zwischen prozessorientierten Simulationen und er-

eignisorientierten Simulationen unterschieden. Bei ereignisorientierten Simulationen

(Abb. 2.6) ist der Modellierungsansatz auf den Fluss von Simulationsobjekten ausge-

legt. An interessanten Zeitpunkten werden Ereignisse ausgelöst. Die Eigenschaften

von Objekten werden als Attribute gespeichert. Abbildung 2.6 zeigt dabei die Simu-

lation einer einfachen Fertigungsstraße. Fertigungsteile durchlaufen dabei mehrere

Stationen an denen sie verzögert werden. Während sich ein Fertigungsteil in einer

Station befindet, können andere Teile auf diese Station nicht zugreifen. Sie werden

in eine Warteschlange eingefügt. Nachdem die Station durchlaufen ist, verlässt

das Fertigungsteil die Abteilung und ein weiteres Teil wird aus der Warteschlange

genommen. Jeder Block kann hier als Funktion angesehen werden, der Ereignisse

auslöst.

Bei ereignisorientierten Simulationen werden Simulationsentitäten häufig durch

Klassen gekapselt, die durch Nachrichten miteinander kommunizieren (Abb. 2.7).

Die Abbildung zeigt denselben Fertigungsprozess. Hier sind die einzelnen Statio-

nen jedoch durch Nachrichten dargestellt. Die prozessorientierte Simulation mag

einfacher erscheinen, erlaubt aber weniger Programmkontrolle. Für jedes Simu-

KAPITEL 2. GRUNDLAGEN

Abbildung 2.6: Ereignisorientierte Simulation (aus [96])

Abbildung 2.7: Prozessorientierte Simulation (aus [96])

lationsobjekt im System muss ein eigener Prozess mit eigener interner Ablaufzeit

erstellt werden.

Beim diskreten Simulationsansatz wird die Zeit in kleinste Einheiten unterteilt und

diskret weitergeschaltet. In Kombination mit Ereignissen spricht man häufig vom

“next-event to time advance” Ansatz. In der Simulation werden dabei an bestimmten

Zeitpunkten Ereignisse ausgelöst, die Simulationsobjekte modifizieren können.

Diese Ereignisse werden in eine prioritätsbasierte Warteschlange eingeordnet und

die Zeit bis zum nächsten Ereignis weitergeschaltet.

Es sollen im Folgenden einige Simulationsumgebungen auf ihre Konzepte und

ihre Relevanz in Bezug auf die Simulation visueller Sprachen hin untersucht werden.

Dabei ist zwischen Simulationsbibliotheken und Simulationssprachen zu unterschei-

den. Simulationsbibliotheken sind in einer herkömmlichen Programmiersprache

geschrieben und sollen den Benutzer dabei unterstützen, das eigene Programm um

Simulationskonstrukte zu erweitern. Im Rahmen dieser Arbeit betrachte ich nur

objektorientierte Simulationsbibliotheken.

Die hier betrachteten Simulationssprachen sind speziell auf die diskrete Simu-

lation ausgelegt, sie sind quasi domänenspezifisch. Sie enthalten Spezialkonstrukte,

die es dem Benutzer besonders einfach machen sollen, eine Simulation zu entwerfen.

Die aus den Simulationssprachen generierten Programme können entweder direkt

oder mit einem Interpreter ausgeführt werden. Einige Simulationssprachen, wie

zum Beispiel Simula, sind jedoch ebenso mächtig, wie eine herkömmliche Program-

miersprache.

2.5. SIMULATION

Simulationssprachen werden häufig bei transportorientierten Systemen, wie

Fertigungsstraßen, eingesetzt. Simulationsumgebungen basieren auf Simula-

tionssprachen, haben jedoch meist eine visuelle Spezifikation und bieten eine

Analyseumgebung.

2.5.1 SIMAN

SIMAN [83] ist eine Simulationssprache zur Modellierung von diskreten, kontinu-

ierlichen oder hybriden Modellen. Diskrete Systeme können in SIMAN entweder

prozess- oder ereignisorientiert entworfen werden. Ein kontinuierliches Simu-

lationsmodell wird definiert, indem Zustandsvariablen Differentialgleichungen

zugeordnet werden. In kleinen Zeitintervallen werden die Zustandsvariablen ak-

tualisiert. SIMAN ist spezialisiert auf die Untersuchung von Fertigungsstraßen und

Arbeitsabläufen. Es bietet ein Framework das zwischen der Modellkomponente und

dem Experimentrahmen unterscheidet. Das Modell beschreibt die physikalisch vor-

handenen Elemente, wie Maschinen, Arbeiter, Transporter etc. und deren logische

Verknüpfung. Der Experimentrahmen definiert die Bedingungen unter denen das

Modell ausgeführt wird.

Für die Beschreibung des Modells steht neben einer textuellen Sprache eine vi-

suelle Blockdiagrammsprache zur Verfügung. In den Blockdiagrammen werden

einzelne Stationen modelliert. Jede Station wird graphisch durch ein benanntes

Rechteck dargestellt. Unterhalb der Blockdefinition stehen die Parameter der Block-

funktion. Die Simulationsobjekte “durchlaufen” dann das Blockdiagram von oben

nach unten und werden durch Prozessfunktionen oder das Warten in einer Schlange

verzögert. Pfeilverbindungen zeigen den Fluss der Simulationsobjekte durch das

Diagramm an. Simulationsobjekte können mittels spezieller Konstrukte zwischen

verschiedenen Blockdiagrammen wechseln und simulieren so zum Beispiel den

Transport von Waren.

In SIMAN können Ressourcen beliebiger Größe modelliert werden. In der Re-

gel werden Ressourcen mit einer vorangehehenden Warteschlange modelliert,

sodass Simulationsobjekte warten müssen, wenn die Ressource belegt ist. Für die

Modellierung von Schlangen stehen Konzepte wie LIFO, FIFO etc. bereit. Des

Weiteren ist es in SIMAN möglich, Simulationsobjekte anhand probabilistischer

Funktionen zu erstellen bzw. zu löschen. Auch Verzweigungen zwischen einzelnen

Stationen sind anhand von Wahrscheinlichkeitsfunktionen möglich. Durch so ge-

nannte “Macro Submodels” können generische Stationen definiert werden, die mit

konkreten Parametern quasi instanziiert werden können.

Im Rahmen der Arena Simulationsumgebung erlaubt es SIMAN eine einfache

Animation zu definieren. Abbildung 2.8 zeigt ein Blockmodell für die Simulation

KAPITEL 2. GRUNDLAGEN

Abbildung 2.8: Blockmodell in SIMAN (aus [84])

eines Restaurants. Kunden kommen dabei entsprechend einer Exponentialvertei-

lung im Restaurant an. Kunden, die vor neun Uhr (TNOW <= 240) ankommen,

werden wieder weggeschickt. Die restlichen Kunden werden in einem DELAY-Block

verzögert - sie essen - die Zeit ist normalverteilt mit 24 Minuten und einer Standard-

abweichung von fünf Minuten. Nach dem Essen gehen Kunden zum Kassierer. Der

Kassiervorgang ist normalverteilt mit 1,5 Minuten und einer Standardabweichung

von einer halben Minute.

2.5.2 GPSS

GPSS [106] wird seit den frühen 1960er Jahren entwickelt und ist heute mit den

Nachfolgern GPSS/H und GPSS World für Windows [90] eine der am weitest ver-

breiteten Simulationssprachen. GPSS erlaubt die diskrete Simulation von Systemen

auf Warteschlangenbasis und ähnelt sehr stark der Simulationssprache SIMAN.

Jedoch gibt es in GPSS keine visuelle Modellierung von Stationen mittels Blockdia-

grammen. Interessant an GPSS ist die flexible Modellierung von Warteschlangen,

die schrittweise Simulation und die Definition von Haltepunkten (ähnlich zu denen

in Debuggern). Außerdem erlaubt es GPSS Störungsszenarien zu spezifizieren,

wie sie in Fertigungsanlagen entstehen können. Bei GPSS durchlaufen Transaktio-

nen ebenfalls wie in SIMAN den Modellraum. Zusätzlich können Transaktionen

geklont werden, z. B. wenn ein Auftrag mehrere Unteraufträge nach sich zieht.

Die geklonten Transaktionen werden dann wieder zusammengeführt und warten

gegenseitig aufeinander. Dies kommt zum Beispiel in Werkstätten vor, wenn ein

Inspektionsauftrag weitere gleichzeitige Untersuchungen in verschiedenen Teilbe-

reichen des Werkstücks nach sich zieht. GPSS erlaubt es, so genannte Matrizen zur

Ressourcenbelegung zu definieren. So können räumliche Bezüge zwischen einzelnen

Ressourcen modelliert werden. Dies tritt zum Beispiel bei Parkplätzen auf, wobei ein

2.5. SIMULATION

¨ ¥

GENERATE 7,6 ;nächster Kunde kommt

TRANSFER BOTH,Serv_Bob,Serv_Alice

Serv_Bob SEIZE Bob ;warten...

ADVANCE 8,4 ;Haare schneiden...

RELEASE Bob ;Haarschnitt fertig

TRANSFER ,finito

Serv_Alice SEIZE Alice ;warten

ADVANCE 15,10 ;Haare schneiden...

RELEASE Alice ;Haarschnitt fertig

finito TERMINATE 1 ;der Kunde geht

Listing 2.1: Spezifikation mit GPSS aus [90]

LKW mehrere PKW Plätze beansprucht und eine Fragmentierung die Folge ist.

Das GPSS Skript in Listing 2.1 modelliert ein Frisörgeschäft mit zwei Frisören

(Bob und Alice), die gleichzeitig Kunden bedienen. Ein Kundenobjekt wird dabei

durchschnittlich alle sieben Minuten (mit einer Standardabweichung von sechs

Minuten) generiert und an einen der Frisöre weitergeleitet. Dort wird dann gewartet

bis der Kunde an der Reihe ist und die Haare geschnitten werden können. Im

Anschluss verlassen die Kunden das Geschäft. Eine Anweisung in GPSS besteht

dabei immer aus vier Teilen: dem Label, der Operation, den Parametern und einem

optionalen Kommentar.

2.5.3 SIMSCRIPT III

SIMSCRIPT [94] ist eine objekt-orientierte Simulationssprache und eignet sich eben-

falls sowohl für diskrete als auch kontinuierliche Simulation. Gleichzeitig ist SIM-

SCRIPT auch als allgemeine Sprache zu benutzen. Die Syntax ist selbstdokumen-

tierend. SIMSCRIPT erlaubt die Definition von Klassen mit Objektattributen und

-methoden und Vererbung. Es können Warteschlangen mit unterschiedlichen Be-

dienungsvarianten definiert werden. Simulationsobjekte können gleichzeitig belie-

big vielen Mengen angehören. Methoden können als so genannte Prozessmethoden

deklariert werden, diese werden dann, mittels eines “schedule” Aufrufs, beliebig

weit in der Zukunft ausgeführt. Des Weiteren können Prozessmethoden unterbro-

chen und wieder neu gestartet werden. Zu statistischen Zwecken gibt es spezielle

Ausdrücke, die zum Beispiel die Auslastung eines Variablenwerts über die Simula-

tionszeit bestimmen. Listing 2.2 zeigt die Definition einer Klasse Vehicle mit einer

Prozessmethode Trip. Es wird ein Objekt Car vom Typ Vehicle angelegt und die

Methode Trip nach zwei Tagen ausgeführt. In der Prozessmethode wird zunächst

gewartet und anschließend die Wartezeit ausgegeben.

KAPITEL 2. GRUNDLAGEN

¨ ¥

begin class Vehicle

every Vehicle

has a Trip process method

define Trip as a process method

given ’’miles to travel and

’’average speed in miles per hour

2 double arguments

yielding ’’duration of trip in hours

1 double argument

end

schedule a Trip(Car) given 200, 50 in 2 days

methods for the Vehicle class

process method Trip

given Distance, Avg_Speed

yielding Actual_Duration

define Duration, Start_Time

as double variables

Duration = Distance /

uniform.f(Avg_Speed-5, Avg_Speed+5, 1)

Start_Time = time.v

wait Duration hours

Actual_Duration = (time.v -Start_Time) *hours.v

end

Listing 2.2: Spezifikation mit SIMSCRIPT III

2.5.4 Simula

Simula [24] wurde in den sechziger Jahren am Norwegian Computing Center ent-

wickelt. Mit Simula sollten zeitdiskrete Systeme simuliert und entwickelt werden.

Der Focus liegt dabei nicht nur auf Fertigungsstraßen wie bei SIMAN oder GPSS

sondern ist breiter gefächert, da Simula auch als General Purpose Sprache entwor-

fen ist. Simula, das auf Algol 60 basiert, entwickelte sich zur ersten objektorien-

tierten Programmiersprache. Dynamisch instanziierbare Koroutinen, auch Prozes-

se genannt, enthalten lokale Prozeduren und Daten. Koroutinen laufen quasi paral-

lel ab, jedoch zu jedem Zeitpunkt ist nur genau eine Koroutine aktiv. Sie können

auf die Daten anderer Koroutinen zugreifen und in beliebig vielen Mengen ent-

halten sein. Die enthaltenen Klassen SIMSET und SIMULATION bieten Unterstüt-

zung für die diskrete ereignisorientierte Simulation. Mit der “activate process

[at|before|after|delay]”-Klausel können Prozesse zu beliebigen Zeitpunk-

ten oder verzahnt mit anderen Prozessen gestartet werden.

2.6. PROGRAMMVISUALISIERUNGSSYSTEME

2.5.5 Bibliotheken zur Simulationsunterstützung

Anders als die bisher angesprochenen Simulationssprachen, die eine eigene, ggf.

spezialisierte Syntax (GPSS, SIMAN) haben, sind Simulationsbibliotheken in her-

kömmliche Programmiersprachen wie Java oder C/C++ geschrieben. Sie bieten

somit eine hohe Flexibilität, jedoch mit dem Nachteil, dass sie nicht so spezialisierte

Konstrukte enthalten und ein zusätzlicher herkömmlicher Programmrahmen ge-

schrieben werden muss.

SimJava [61] ist eine Java Bibliothek zur diskreten ereignisbasierten Simulati-

on. Es können statische Netzwerke mit aktiven Elementen, wie sie beispielsweise

bei Schaltungen zu finden sind, modelliert werden. Simulationsobjekte, die in

einem Java Thread laufen, werden durch so genannte Ports miteinander verknüpft.

Über die Ports können die Simulationsobjekte dann miteinander kommunizieren,

indem sie Nachrichten bidirektional verschicken. Das Verhalten der einzelnen

Simulationsobjekte wird durch das Überschreiben einer geerbten Methode erreicht.

Zusätzlich gibt es eine Reihe vordefinierter Methoden um Nachrichten zu verschi-

cken, Log-Ausgaben zu erzeugen oder den aktiven Thread zu wechseln. Konstrukte

für Warteschlangen, Ressourcenbelegung oder Zufallsvariablen existieren nicht.

Silk [46] ist eine weitere auf Java basierende objektorientierte Simulationsspra-

che, die prozessorientierte Modellierungskonzepte bereitstellt. Silk enthält eine

Reihe von Funktionen für Warteschlangen, die auch von SIMAN bekannt sind. Jedes

Simulationsobjekt läuft hier in einem eigenem Java Thread ab und erbt von einer

speziellen Klasse “Entity”, die spezielle Methoden für Simulationsobjekte bereithält.

Die kommerzielle C/C++ Simulationsbibliothek CSIM [107] enthält weitaus

mächtigere Konstrukte als SimJava. CSIM erlaubt die Modellierung von diskreten

Systemen in einer prozessorientierten Sichtweise. Dabei hat CSIM ein ausgefeiltes

Ressourcen Konzept: Ressourcen können so zum Beispiel auch nur teilweise von

Prozessen belegt werden. Neben der Definition von Ereignissen, auf die Prozesse

hören, können auch Mailboxen modelliert werden, in die Prozesse Nachrichten

legen. Neben der Erzeugung von Zufallszahlenströmen hat CSIM umfangreiche

Funktionen zur Reportgenerierung.

2.6 Programmvisualisierungssysteme

Werkzeuge zur Programmvisualisierung und besonders diejenigen, die graphische

Darstellungen dynamischer Natur erzeugen, sind besonders interessant, da sie so-

wohl eine Simulations- als auch eine Animationskomponente enthalten. Ich möchte

hier zunächst auf Systeme für die Algorithmenanimation eingehen. In diesen Syste-

men wird besonderer Wert auf die Animation gelegt, da das Ziel war, Verständnis für

KAPITEL 2. GRUNDLAGEN

einen bestimmten Algorithmus beim Anwender zu erreichen. Auf Seiten der Spezi-

fikation herrscht hier besonders das Prinzip vor, den Code zu annotieren. Da bereits

Anfang der 1980er Jahre mit diesem Forschungszweig begonnen wurde, existiert eine

große Menge (ca. 100) an Systemen. Im folgenden Abschnitt sollen einige interessante

Systeme vorgestellt werden.

2.6.1 Sorting out Sorting

Die erste Arbeit im Bereich der Softwarevisualisierung war der 1980 entstandene

Film “Sorting out Sorting“ von Baecker [3], der verschiedene Sortieralgorithmen

zeigt, die animiert miteinander verglichen werden. SOS diente hauptsächlich Lehr-

zwecken und war Vorbild für die Animation in vielen weiteren Algorithmenanima-

tionssystemen.

2.6.2 BALSA

BALSA, der “Brown University Algorithm Simulator and Animator“ [12] war 1984

das erste interaktive System zur Algorithmenanimation, das die damaligen fenster-

basierten Systeme ausnutzte. Balsa war in C geschrieben und konnte Pascal Code

animieren. Es unterstützt mehrere Sichten, in denen auch unterschiedliche Algorith-

men gleichzeitig betrachtet werden konnten. Die aktuelle Codezeile wurde graphisch

hervorgehoben. BALSA beruht auf dem Prinzip der “Interesting Events“, wobei der

Benutzer bestimmte Stellen im Algorithmus identifiziert, die er für die Visualisie-

rung wichtig hält. Diese Stellen werden dann dem Animationswerkzeug übergeben

und entsprechend graphisch dargestellt. Das System der “Interesting Events“ hat den

Nachteil, dass der Animator den Algorithmus kennen muss. BALSA I lief auf Apollo

Rechnern mit schwarz-weiß Displays, BALSA II auf Apple Rechnern mit Farbdis-

plays und Soundausgabe zu Ereignissen.

2.6.3 TANGO

TANGO [114] wurde 1989 von Stasko ebenfalls wie BALSA an der Brown Universität

entwickelt. Es führt das so genannte “Path-Transition“-Paradigma ein, das für eine

gleichmäßige und kontinuierliche Animation sorgt. Das Path-Transition-Paradigma

wird in vielen anderen Animationssystemen eingesetzt und erlaubt eine einfache

Spezifikation, ohne viel Code zu schreiben. In TANGO werden zunächst fundamen-

tale Operationen des Algorithmus identifiziert, dann Animationen angefertigt und

schließlich die Algorithmenoperationen auf ihre graphische Repräsentation abgebil-

det. Das Ziel von TANGO ist dabei, eine mächtige Graphikbibliothek bereitzustel-

len, die einfach zu verstehen ist und auch von Nicht-Experten angewendet werden

kann. Die Animationskomponente von TANGO animiert im Wesentlichen Bilder, die

2.6. PROGRAMMVISUALISIERUNGSSYSTEME

Image Location Path Transition

Create Create Create Rotate Create

Locate X Load Scale Concatenate

Y Store Example Iterate

Modify Length Motion Compose

Equal Dx Distance Perform

Dy Concatenate

MakeType Iterate

Null Compose

Copy AddHead

Color AddTail

Extend DeleteHead

Interpolate DeleteTail

Abbildung 2.9: Operationen auf TANGO Datentypen

hinsichtlich ihrer Größe, Position und Farbe verändert werden. Dazu stehen vier ab-

strakte Datentypen zur Verfügung: “Images“ - Graphiken, die dargestellt werden,

“Locations“ - Positionen, die von Bildern eingenommen werden und “Paths“ - Pfa-

de, die die Bild-Positionen modifizieren. Animation wird dadurch erreicht, dass be-

stimmten Bildern während einer Transition ein Start- und ein Endpunkt zugewiesen

wird. Anhand des entstehenden Pfades wird das Bild bewegt. Dies ist das “Path-

Transition“-Paradigma. TANGO unterstützt neben der Bewegung von Graphikob-

jekten noch eine ganze Reihe anderer Transitionen: So gibt es neben Graphik Primi-

tiven wie Linien, Rechtecken, Kreisen und Text noch zusammengesetzte Bildobjekte,

die es erlauben, mehrere andere Primitive zu kombinieren.

TANGO Datentypen und Operationen können der Tabelle aus Abbildung 2.3 ent-

nommen werden.

Das Pfad Argument wird dabei je nach Transitionstyp interpretiert. Handelt es sich

z. B. um eine “alter visibility“ Transition, so wird für jedes Koordinatenpaar die Sicht-

barkeit einmal an- und ausgeschaltet. Transitionen können auch vom Typ “Iteration“,

“Concatenation“ und “Composition“ sein.

Ein Beispiel zur konkreten Spezifikationssprache von TANGO ist in Listing 2.3 zu

sehen. Das Beispiel erzeugt ein Rechteck und einen Kreis. Das Rechteck wird an eine

neue Position bewegt, während der Kreisradius vergrößert wird. Problematisch am

TANGO/XTANGO-Ansatz ist, dass Transitionen zwar hintereinander und nebenläu-

fig modelliert werden können, aber nicht beliebig verschränkt nebenläufig. Dies ist

besonders in Programmen mit mehreren Threads problematisch, die zu beliebigen

Zeitpunkten gestartet werden können. POLKA-RC soll dies umgehen.

KAPITEL 2. GRUNDLAGEN

¨ ¥

TANGO_IMAGE rect, circ;

TAGO_LOC center, to Loc;

TANGO_PATH path1, path2;

TANGO_TRANS trans1, trans2, doBoth;

double delta[5] = {0.1, 0.1, 0.1, 0.1, 0.1};

rect = TANGOimage_create(TANGO_IMAGE_TYPE_RECTANGLE,

0.2, 0.2, 1, TANGO_COLOR_RED, 0.1, 0.3, 0.5);

circ = TANGOimage_create(TANGO_IMAGE_TYPE_CIRCLE, 0.6,

0.8, 1, TANGO_COLOR_BLUE, 0.05, 0.0);

center = TANGO_image_loc(rect, TANGO_PART_TYPE_C);

toLoc = TANGOloc_create(0.2, 0.7);

path1 = TANGOpath_motion(center, toLoc,

TANGO_PATH_TYPE_STRAIGHT);

path2 = TANGpath_create(5, delta, delta);

trans1 = TANGO_trans_create(TANGO_TRANS_TYPE_MOVE,

rect, path1);

trans2 = TANGOtrans_create(TANGO_TRANS_TYPE_RESIZE,

circ, path2);

doBoth = TANGO_trans_compose(2, trans1, trans2);

TANGOtrans_perform(doBoth);

Listing 2.3: Spezifikation in TANGO.

2.6.4 POLKA-RC

POLKAs [114] Unterschied zu TANGO ist der Animationszähler (frame-counter). Die

Transitionen von TANGO werden durch Actions ersetzt, die eine ähnliche Semantik

haben und zusätzlich eine globale Zeitvariable einführen.

time = Animate(time, 20)

erzeugt somit 20 neue Animationsframes, die zur Zeit time eingeplant werden.

Der POLKA Code zum TANGO Beispiel oben ist in Listing 2.4 zu sehen. Zusätzlich

bietet POLKA noch einige zusätzliche Eigenschaften gegenüber TANGO, wie

Callback-Funktionen, dynamische Typänderung von Objekten und kontinuierliche

Actions, die quasi dauerhaft laufen, sowie Anfügestellen für Objekte, an denen

andere Objekte angeheftet werden könnnen. Bewegt sich ein Objekt, so wird das

angeheftete Objekt mitbewegt.

Ein Nachteil von POLKA ist, dass die Animation nicht zeitgesteuert ist. Dies

hat zur Folge, dass die Animation auf schnellen Rechnern evtl. zu schnell abläuft

und auf langsamen Maschinen ruckelt. POLKA-RC (real clock) [113] umgeht dieses

Problem, indem Animationen auf Basis einer Echtzeit-Uhr berechnet werden. Die

wesentlichen Konzepte von POLKA wurden dabei übernommen. Neu hinzugekom-

men sind die so genannten “Trajectories“, die Flugbahnen von Objekten darstellen.

Sie bekommen drei Parameter: 1. den Offset vom Start bis zum Ende der Flugbahn,

2. den Bewegungstyp, z. B. direkt oder im Uhrzeigersinn und 3. eine Funktion, die

die Geschwindigkeit beschreibt. Actions haben nun zusätzliche Zeitparameter mit

2.6. PROGRAMMVISUALISIERUNGSSYSTEME

¨ ¥

Rectangle *rect;

Circle *cir;

Loc *center; *toLoc;

Action *action1, *action2;

double delta[5] = {0.1, 0.1, 0.1, 0.1, 0.1};

int len1, len2;

rect = new Rectangle(view, 1, 0.2, 0.2, 0.1, 0.3,

"red", 0.5);

circ = new Circle(view, 1, 0.6, 0.8, 0.05, "blue", 0.0);

center = rect->Where(PART_C);

toLoc = new Loc(0.2, 0.7);

action1 = new Action("MOVE", center, toLoc, STRAIGHT);

action2 = new Action("RESIZE", 5, delta, delta);

len1 = rect->Program(acion1, time);

len2 = circ->Program(action2, time);

time = Animate(time, MAX(len1, len2));

Listing 2.4: Spezifikation in POLKA.

Werten in Sekunden, Millisekunden oder Spezialwerten wie “NOW“, “ASAP“ oder

“START_AFTER_START_OF“.

Abbildung 2.10 zeigt einen Screenshot des Polka Systems. Mittlerweile ist von

POLKA-RC auch eine 3-D-Variante verfügbar.

2.6.5 Lens

Das Lens System [70] verfolgt einen anderen Ansatz als die bisher genannten Algo-

rithmenanimationssysteme. Lens soll die Lücke zwischen Programmvisualisierung

und Algorithmenanimation füllen. Es soll beliebige Programme mit Sichten der Algo-

rithmenanimation darstellen können. Die Autoren möchten dabei die einfache Dar-

stellung eines visuellen Debuggers, der das Programm automatisch als Blockstruktur

(Objekte oder Felder) darstellt, erweitern. Die Darstellung soll dem Abstraktionsle-

vel einer Algorithmenanimation ähneln und einfach hergeleitet werden können, oh-

ne dass es nötig ist, Programmierung auf Grafikebene zu kennen. Stasko et al. haben

dazu zunächst Algorithmenanimationssysteme untersucht und eine Menge von gra-

phischen Grundprimitiven identifiziert. Diese sind “Linien, Rechtecke, Kreise, Text”

sowie “Objekt Arrays”. Alle graphischen Primitive haben Kontrollattribute wie Po-

sition, Ausdehnung oder Radius. Des Weiteren wurde eine Menge von Grundopera-

tionen auf graphischen Primitiven identifiziert. Diese sind:

•ein Objekt zu einer bestimmten absoluten/relativen Position oder zu einer Po-

sition relativ zu einem anderen Objekt bewegen.

•Änderung der (Füll-) Farbe eines Objekts.

•Aufblinken eines Objekts.

•Positionswechsel zweier Objekte.

KAPITEL 2. GRUNDLAGEN

Abbildung 2.10: Polka

•Löschen eines Objekts.

Um im Lens System eine Animation zu entwickeln, wird der Programmcode dazu

in den Lens Editor geladen. Dort kann in einer Zeichenfläche ein graphisches Objekt

erstellt werden und das Erstellen des Objekts einer bestimmten Zeile im Code zuge-

ordnet werden. Die Kontrollattribute des graphischen Objekts können mit Variablen

des Programms assoziiert werden. Lens speichert dies in einer internen Datenbank.

Das Lens System verallgemeinert das Konzept der Algorithmenanimation. Es wird

von zu Grunde liegenden Grafikbibliotheken abstrahiert und es kann eine sehr allge-

meine Abbildung von Programmelementen auf graphische Primitive geschaffen wer-

den. Der Code wird nicht, wie beim Ansatz der “interesting events”, direkt annotiert,

sondern instrumentiert. Bis zu einem gewissen Level ist der Ansatz auch deklarativ,

2.6. PROGRAMMVISUALISIERUNGSSYSTEME

da ausgesagt wird, was animiert wird und nicht wie. Allerdings kann es in manchen

Animationen auch notwendig sein, an dieser Stelle einzugreifen und z. B. durch ei-

ne Boole’sche Formel oder eine textuelle Zusatzspezifikation anzugeben, wann eine

Animation stattfindet. Problematisch sind auch graphische Abbildungen von primi-

tiven Arrays. Hier ist eine Abbildung durch direkte Manipulation nur sehr einge-

schränkt möglich.

2.6.6 Forms/3

Forms/3 [16] basiert auf dem Tabellenkalkulationsparadigma. Der Programmierer

manipuliert Zellen in Formularen und definiert Berechnungsvorschriften für jede

Zelle. Jede Berechnungsvorschrift darf Konstanten, Referenzen zu anderen Zellen

oder Selbstreferenzen beinhalten. Dieser Ansatz ist deklarativ - die Beziehungen zwi-

schen Ein- und Ausgabe werden definiert.

Effekte, wie Änderungen von Daten, wirken sich unmittelbar aus und sind sofort

sichtbar. Burnett nennt dies “declarativeness and responsiveness“. Der Benutzer

muss sich nur um die gewünschte Ausgabe kümmern.

Die Animation folgt Staskos “Path-Transition“ Paradigma. Die Animationsarten äh-

neln denen in Staskos POLKA. So gibt es z. B. Transitionen für Bewegung, Sichtbar-

keit, oder Farbe. Transitionen können ebenfalls zusammengesetzt werden. Im Ge-

gensatz zu POLKAs expliziten Aufrufen werden in Forms/3 die Transitionen prin-

zipiell kontinuierlich ausgewertet und brauchen deshalb nicht explizit ausgewertet

werden. Deshalb wird POLKAs “perform“ Kommando durch die zwei Komman-

dos “resetEvent“ und “continueEvent“ ersetzt. Das Prinzip der “interesting

events“ wird in Forms/3 deklarativen Ansatz durch Bedingungen im Programm er-

weitert. Ein Algorithmus muss nun nicht mehr eine bestimmte Stelle im Code er-

reichen, sondern eine beliebige Bedingung kann eine Algorithmensequenz auslösen.

Ein Suchen im Code nach möglichen Stellen, in denen eine bestimmte Bedingung

erfüllt sein kann, ist nun nicht mehr nötig. Da Forms/3 sofort auf Änderungen rea-

giert, kann der Benutzer auch während der Ausführung Animation oder Algorith-

mus ändern. Ein weiterer interessanter Aspekt von Forms/3 ist, dass mittels einer

Zeitschiene die Ausführungsrichtung beliebig geändert werden kann.

2.6.7 Pictorial Janus

Pictorial Janus [52] wurde 1989 von Kahn und Saraswat entworfen und basiert

auf der textuellen Sprache Janus. Janus wiederum basiert auf ähnlichen Konzep-

ten wie Prolog. Ein Janus Programm ist dabei eine Menge von Klauseln. Jede Klau-

sel hat einen Head, einen Guard und einen Body. Der Guard ist eine Vorbedingung,

die erfüllt sein muss, um den Body anzuwenden. Body und Guard sind durch

einen “Commit Operator“ (“|“) getrennt. Janus Programme definieren nebenläufige

KAPITEL 2. GRUNDLAGEN

Abbildung 2.11: Pictorial Janus Syntax

Abbildung 2.12: Pictorial Janus Beispiel: Verknüpfung zweier Listen

Agenten, die durch gerichtete Kanäle kommunizieren. Die Ausführung wird durch

Pattern-Matching bestimmt. Falls mehrere Guards gleichzeitig erfüllt sind, so wird

ein Guard nicht-deterministisch ausgewählt.

append (x, y, z) :- x = [], z = !z1 | z1 = y.

append (x, y, z) :- x = [x1|x2], z = !z1 |

z1 = [x3|x4], x3 = x1, z.

Das Janus Programmlisting definiert das Aneinanderfügen zweier Listen. Pictorial

Janus ist die visuelle Janus Variante und basiert auf den Prinzipien

•Bilder sind Programme.

•Bilder sind Schnappschüsse der Berechnung.

•die Berechnung ist die visuelle Manipulation von Bildern.

Pictorial Janus Programme sind topologisch vollständig, d. h. sie sind gegenüber Ro-

tation oder einer beliebigen Ausdehnung wie Streckung, Schrumpfung oder Form-

veränderung invariant. Graphische Primitive werden durch geschlossene Konturen

dargestellt und sind unabhängig von ihrer graphischen Erscheinung.

Abbildung 2.11 zeigt Primitive von Pictorial Janus.

2.6. PROGRAMMVISUALISIERUNGSSYSTEME

Abbildung 2.12 zeigt eine Pictorial Janus Version des obigen Janus Beispiels. Wird

das Programm ausgeführt, so wird je nach Pattern Matching eine Regel innerhalb des

Agenten aktiviert und ausgeführt. Diese Regel wird dann bis zum ursprünglichen

Agenten graphisch ausgedehnt und so zum neuen Agenten. Innerhalb einer Regel

ist die Subkonfiguration des Agenten wiederum rekursiv vorhanden. Prinzipiell

entsteht so eine Struktur unendlicher Tiefe, die jedoch nur endlich tief visualisiert

wird. Wenn eine Regel aufgebläht wird, so wird die Subkonfiguration ebenfalls

langsam sichtbar. Dies entspricht in gewisser Weise einem semantischen Zoom.

Interessant an Pictorial Janus ist, dass eine weiche (“smooth”) Animation er-

reicht wird, die scheinbar nahtlos zwischen den Systemzuständen interpoliert.

Die zugrundeliegende Sprache Janus könnte hinsichtlich der Simulationskompo-

nente Aufschluss über regelbasierte Konzepte geben, die in das zu entwickelnde

Spezifikationskonzept einfließen könnten.

2.6.8 Alma

Alma [122] ist ein System zur Programmvisualisierung und Algorithmenanimation.

Es versucht aus einem abstrakten Strukturbaum den Programmablauf zu visualisie-

ren. Der Strukturbaum ist mit Attributen, die Zeichenfunktionen darstellen, deko-

riert. Aus einem Programmtext baut es mit Hilfe des zu Grunde liegenden LISA Com-

piler Generators einen abstrakten Strukturbaum auf. An diesen können so genannte

Visualisierungsregeln dekoriert werden. Die Regeln beschreiben ein Baummuster, das

zutreffen muss und eine Reihe von Bedingungen, die für den Teilbaum gelten müs-

sen. Sind Baummuster und Bedingungen erfüllt, so werden primitive Zeichenfunk-

tionen aufgerufen. Um Animationen herleiten zu können, werden so genannte Erset-

zungsregeln benötigt. Diese modifizieren Instanzen von Bäumen, indem zunächst ein

Baummuster und konkrete Bedingungen gematched werden. Anschließend wird der

Baum anhand der Ersetzungsregel modifiziert. Dies entspricht sehr dem Prinzip der

Graphtransformation [38].

Listing 2.5 zeigt die Spezifikation von Visualisierungsregeln in Alma anhand der ab-

strakten Syntax zur Definition einer Variablenzuweisung (Produktionen p13-p16).

Wird ein Baummuster erkannt, das einer Zuweisung entspricht, bei der der Wert

des linken sowie des rechten Operanden undefiniert ist, wird eine graphische

Darstellung wie in Abbildung 2.13 oben erzeugt. Sind beide Operanden definiert, so

wird eine graphische Darstellung wie in Abbildung 2.13 unten erzeugt.

Um Animationen zu erhalten, werden noch Ersetzungsregeln benötigt. Listing

2.6 zeigt zwei Ersetzungsregeln für eine abstrakte Syntax, die einen bedingten

Ausdruck modelliert (Produktionen p8 und p9). Die erste Regel trifft zu, falls ein

bedingter Ausdruck gematched wird, dessen Bedingung wahr ist. Ist dies der Fall,

so wird die Regel durch Regel p9 ersetzt, wobei der THEN-Teil ausgeführt wird.

Andernfalls wird der ELSE-Teil ausgeführt.

KAPITEL 2. GRUNDLAGEN

¨ ¥

p13: rel_oper : exp exp

p14: exp : CONST

p15: exp : VAR

p16: exp : oper

vis_rule(p13) = <oper,a,c>(

(a.value=NULL) AND (c.value=NULL)

AND (a.type=VAR) AND (c.type=CONST)),

{drawRect(a.name), drawRect(), put(opr.name),

put(’?’)}

vis_rule(p13) = <oper,a,c>(

(a.value!=NULL) AND (c.value!=NULL)

AND (a.type=VAR) AND (c.type=CONST)),

{drawRect(a.name, a.value), drawRect(c.value),

put(opr.name), put(’?’)}

Listing 2.5: Spezifikation von Visualisierungsregeln in Alma.

Abbildung 2.13: Visualisierung in Alma

¨ ¥

p8: IF : cond actions actions

p9: | cond actions

rule(p8) = <if,op,a,b>,

(op.value=true),

<p9:if,op,a>,

{}

rule(p8) = <if,op,a,b>

(op.value=false),

<p9:if,op,b>,

{}

Listing 2.6: Spezifikation von Ersetzungsregeln in Alma.

2.7. GENERATORSYSTEME

Das Alma System erlaubt eine Programmvisualisierung für Sprachen, die über

eine abstrakte Syntax verfügen und in LISA implementiert sind. Es ist keine

Code-Annotation notwendig. Allerdings müssen zur Visualisierung bestimmte

Grafikroutinen bekannt sein. Außerdem kann es schwierig sein aus einer abstrakten

Syntax eine Animation herzuleiten, da diese, wie z. B. in Ausdrucksgrammatiken,

oft sehr stark von der konkreten Syntax abweicht. Hier ist es wohl notwendig, dass

Sprach- und Animationsentwerfer dasselbe Wissen über die Sprache haben.

2.7 Generatorsysteme

In den folgenden Abschnitten werde ich verwandte Generatorsysteme für Entwick-

lungsumgebungen für visuelle Sprachen vorstellen. Ich werde dabei insbesondere

auf den Aspekt der Simulation und Animation eingehen. Die Entwicklung der ei-

gentlichen visuellen Sprache steht dabei eher im Hintergrund. In [104] werden einige

der Systeme jedoch genauer beschrieben.

2.7.1 MetaEdit+

MetaEdit+ [21] ist ein kommerzielles System der Firma MetaCase und gehört

zur Klasse der CASE-Werkzeuge1. Im Gegensatz zu den weiter unten beschriebe-

nen Systemen basiert es nicht darauf Bäume als Grundlage zur Berechnung der

graphischen Repräsentation zu nutzen. Stattdessen wird das so genannte GOPRR-

Modell verwendet, was für Graph-Object-Property-Relationship-Role steht. Die

einzelnen Begriffe bezeichnen Methoden zur Berechnung einzelner Aspekte einer

Sprache. So werden durch das Object-Kalkül Konstrukte modelliert, die mit anderen

Konstrukten Beziehungen eingehen können. Das Relationship-Kalkül modelliert

Beziehungen zwischen Objekten. Durch das Property-Kalkül können Eigenschaften

von Konstrukten modelliert werden.

Der GOPRR Ansatz ist stark auf graphartige Darstellungen spezialisiert, wie

sie in CASE-Werkzeugen häufig vorkommen. Für andere und komplexere visuelle

Darstellungen ist er nicht gut geeignet. Allerdings wurde beim Entwurf des Systems

ein besonderes Augenmerk auf einfache Benutzbarkeit gelegt, deshalb existieren für

alle Modellierungsaspekte graphische Werkzeuge. Außerdem unterstützt MetaEdit+

die Teamentwicklung, da alle Sprachkonstrukte in einem globalen Repository

abgelegt werden können.

MetaEdit+ erlaubt ebenfalls die Simulation von Programmen. Diese jedoch nur

1CASE steht für Computer Aided Software Engineering

KAPITEL 2. GRUNDLAGEN

Abbildung 2.14: MetaEdit+

über den Umweg der Source-to-Source-Übersetzung. Dazu spezifiziert der Sprach-

designer für seine visuelle Sprache eine Zielcodetransformation. MetaEdit+ kann

durch vorgefertigte Module Callback-Funktionen implementieren, die, während

das Programm ausgeführt wird, wiederum auf die MetaEdit+ Umgebung zugreifen

können. In der MetaEdit+ Umgebung wird dann das entsprechende Sprachkon-

strukt, das aktiv ist oder eine Zustandsänderung auslöst, graphisch hervorgehoben.

Die Callback-Funktionen sind über eine SOAP Schnittstelle realisiert. MetaEdit+

erreicht so relativ schnell eine einfache Simulation, jedoch mit der Einschränkung,

dass erst Code generiert und dieser annotiert werden muss. Die in dieser Arbeit

vorgeschlagene Simulationslösung ist eine Ebene direkter. Der Umweg über die

Codegenerierung fällt weg.

Abbildung 2.14 zeigt die Ausführung einer Spezifikation, die eine Stoppuhr reali-

siert. In der rechten Bildhälfte im kleinen Fenster ist das ausgeführte Programm zu

sehen. Die Stoppuhr ist im Zustand Stopped. Dieser Zustand ist auch in der MetaEdit+

Umgebung selektiert, dargestellt durch einen roten Rand.

2.7. GENERATORSYSTEME

2.7.2 GenGed/Tiger

Das Spezifikationskonzept von GenGed [6] beruht auf Graphgrammatiken. Der

abstrakte Syntaxgraph (ASG) repräsentiert die logische Struktur des Programms.

Der konkrete Syntaxgraph ordnet Konstrukten des ASG eine konkrete Repräsenta-

tion zu, siehe Abbildung 2.15a. Die graphische Darstellung wird dann durch einen

Constraintsolver - im Falle von GenGed wird Parcon eingesetzt - durchgeführt.

Dabei wird die graphische Darstellung als eine Menge von Bedingungen aufgefasst,

die durch Gleichungen repräsentiert wird. Diese Gleichungen müssen dann vom

Constraintsolver gelöst werden. Nachteilig ist hierbei, dass die Gleichungssysteme

schnell sehr groß werden können und somit nicht mehr schnell genug vom Con-

straintsolver gelöst werden können. Dies führt häufig dazu, dass constraintbasierte

Generatoren für graphische Struktureditoren nicht so ausdrucksstark sind.

Korrekte Instanzen eines graphischen Programms werden durch visuelle Syntaxre-

geln ausgedrückt, vgl. Abbildung 2.15b. GenGed generiert somit auch Umgebungen

für strukturiertes Editieren.

Die Simulations- und Animationsdefinition in GenGed [32] basiert hauptsäch-

lich auf der Basis von Graphtransformation. Die Basis hierfür bildet AGG [119].

AGG ist eine Entwicklungsumgebung für algebraische Graph-Transformation.

Die Transformation basiert dabei auf einem Parsing Prozess des Graphen mittels

Backtracking, der exponentielle Zeitkomplexität hat. Um dies zu verbessern wird

Critical Pair Analysis eingesetzt.

In GenGed können im Layout der Sprache Verhaltensregeln angegeben werden

um Simulation zu spezifizieren. Die Regeln bestehen aus einer Vorbedingung, die

im Syntaxgraph gematched werden muss und einer Ersetzung des entsprechenden

Konstrukts. Um automatisch Regeln anzuwenden, können so genannte Transfor-

mationseinheiten definiert werden. Diese erlauben die Spezifikation von beliebig

vielen Regelanwendungen in einer bestimmten Sequenz. Um eine allgemeine

Simulation in ein domänenspezifisches Layout zu transformieren, existieren Sicht-

transformationsregeln. Teile des Syntaxgraphen werden durch ein konkretes Layout

ersetzt. Abbildung 2.15d zeigt sechs der Regeln, um ein allgemeines Petri-Netz

in ein konkretes Layout “Mutter kocht für ihr Kind” zu transformieren. Falls die

Transformation erfolgreich ist, wird die entsprechende Animationsfunktion, z. B.

“genProd1” aufgerufen.

Der Nachfolger von GenGed namens Tiger basiert auf dem Eclipse-Framework

[13] und der Erweiterung dem Graphical Editing Framework (GEF)2. Die konkrete

Repräsentation (in Tiger VL-Alphabet genannt) wird dabei erstellt, indem dem

Modellelementen GEF-Graphikprimitiven zugeordnet werden. Die Syntax der

2Ein Vergleich des Spezifikationsansatzes von Eclipse mit DEViL ist in [17] zu finden.

KAPITEL 2. GRUNDLAGEN

Sprache wird durch Graphgrammatikregeln, definiert in AGG, festgelegt. Diese

schränken die Standardeditieroperationen von GEF ein. Die Simulation der Sprache

wird dabei ebenfalls durch Regeln definiert. Die Animation in Tiger wird durch

parametrisierbare Zeichnungen erreicht: in [9] wird dazu das Spiel Rubicks Clock

animiert. Die Zeiger der Uhren sind durch ihre Position parametrisiert. Das zeitliche

Weiterschalten der Uhren kann so flüssig animiert werden.3

GenGed setzt auf die konsequente Anwendung von Graphtransformation und den

daraus resultierende formalen Ansatz. Aus Simulationsregeln können so systema-

tisch Animationen abgeleitet werden. Die Spezifikation erfolgt dabei immer visuell

und im Layout der entsprechenden Domäne. Problematisch ist die Beschränkung

auf Constraint-basiertes Layout, was zu einer Einschränkung hinsichtlich der gra-

phischen Ausdruckskraft führt. Die Simulationsspezifikationen bilden nur konkrete

Muster im Syntaxgraph ab - eine Modellierung von Zufall oder eine Gruppierung

von Simulationsobjekten ist nicht möglich. Ebenso wenig existieren Mechanismen

für eine weiche Animation oder eine Animation von Objekten, die nur indirekt von

Modifikationen betroffen sind.

2.7.3 DiaGen/DiaMeta

DiaGen [67] ist ein Generatorsystem, das basierend auf einer internen Hypergraph-

darstellung wahlweise freie, syntax-gesteuerte oder hybride Editoren generiert. Freie

Editoren sind bei der Konstruktion von visuellen Programmen nicht so restriktiv

wie syntax-gesteuerte Editoren. Sie erlauben auch zeitweilige Syntaxfehler in der

Darstellung und schränken den Benutzer beim Entwurf eines Programms nicht ein.

Dies ist besonders vorteilhaft bei großen Programminstanzen. Andererseits helfen

syntax-gerichtete Editoren dem Anwender indem sie die Auswahl an Sprachkon-

strukten bei jedem Editiervorgang vorgeben.

DiaGen benutzt eine Hypergraphgrammatik um die Syntax der Sprache zu spezi-

fizieren. Hypergraphgrammatiken werden ähnlich wie Grammatiken für textuelle

Sprachen definiert. Sie bestehen aus sogenannten terminalen oder nichtterminalen

Hyperkanten. Eine Hyperkannte hat einen Typ und kann beliebig viele Knoten

verbinden. Zusätzlich zur Hypergraphgrammatik werden Constraints angegeben,

die das Layout für die Knoten angeben.

Da Hypergraph Repräsentationen bereits für kleine Programme sehr groß werden,

wird dieser Graph zunächst durch einen so genannten Reducer in ein reduziertes

Hypergraph Modell transformiert. Dies ist vergleichbar mit einer abstrakten Syntax,

die aus einer konkreten Syntax abgeleitet wird. Im Anschluss wird durch den

Parser die maximale korrekte Teilmenge des Programms bestimmt. Unkorrekte Teile

3Die Animationskomponente in DEViL wird dies automatisch durch das Morphen von Sprachkon-

strukten leisten.

2.7. GENERATORSYSTEME

a) Definition des Alphabets b) Definition der Syntax

c) Verhaltensgrammatik

d) Sichttransformationsregeln

Abbildung 2.15: Spezifikation in GenGed

KAPITEL 2. GRUNDLAGEN

werden entsprechend visuell markiert.

Durch einen Attributauswerter werden die korrekten Teile des Diagramms in

eine semantische Repräsentation des Programms überführt. Durch einen optionalen

Layouter wird das Diagramm mittels Constraints in eine optimale Darstellung

hinsichtlich Platzbedarf und Optik überführt. Um auch strukturiertes Editieren zu

erlauben, können Hypergraph-Transformationsregeln hinzugefügt werden, die den

Hypergraph entsprechend modifizieren und auch auf das reduzierte Hypergraph-

modell sowie die Ableitungsstruktur zugreifen können.

Die neuere Variante von DiaGen - DiaMeta [68] - basiert auf dem Eclipse Fra-

mework. DiaMeta setzt zur Spezifikation des Sprachmodells nicht mehr, wie

DiaGen, auf Grammatiken, sondern auf Meta-Modelle.

Es ist damit das erste System, das freie Editoren auf Basis von Meta-Modellen

erzeugt. Die Spezifikation von Simulation wird in DiaMeta durch Graphersetzungs-

regeln auf Basis der abstrakten Syntax erreicht [116, 117]. Dies geschieht (noch) in

einer textuellen Sprache. Das Graphmodell wird dabei durch Animationskanten,4

sowie ein Attribut, das die Animationszeit darstellt, erweitert. So repräsentiert der

Graph die sich aktuell verändernde Modellinstanz. Ausgewählt werden die Regeln

durch einen Zustandsübergangsautomaten.

Abbildung 2.16 zeigt die Spezifikation von Simulation und Animation auf Ba-

sis des Hypergraphen an einem Ausschnitt, der das Spiel Avalanche spezifiziert.

Die Darstellung ist hier graphisch, die Spezifikation erfolgt jedoch eigentlich in

textueller Form. Die Kanten switching_to bzw. blocked definieren die dis-

kreten Zustandsübergänge. Das Attribut tc repräsentiert die Animationszeit. Die

Position von Sprachkonstrukten während der Animation kann durch Formeln

angegeben werden (Time-Abschnitt im Bild unten). Die Animationskanten geben

an, zu welchem Zeitpunkt die Animation gestartet wurde. So kann aufgrund der

aktuellen Systemzeit und der aktuellen Graphinstanz eine konkrete Animation auf

das Graphmodell zurückgeführt werden.

Animationszustände werden also als Zustände des Graphtransformationssys-

tems angesehen, d. h. jeder Animationszustand lässt sich auf das zu Grunde

liegende Graphmodell abbilden. Dies hat den Vorteil, dass auch während der

Animation Ereignisse durch den Benutzer ausgelöst werden können, allerdings nur

gültige im Sinne der Simulationsspezifikation. DiaMeta berechnet dazu alle gültigen

internen Ereignisse, die Zustandsübergänge auslösen können, als auch alle momen-

tan gültigen externen Ereignisse, die der Benutzer während der Animation auslösen

kann. Dieser Mechanismus erinnert an das DEVS Verfahren von Vangheluwe und

4Die Kanten heißen in der Tat Animationskanten, obwohl sie in der Sprache zur Beschreibung von

Zustandsübergängen auftauchen.

2.7. GENERATORSYSTEME

Abbildung 2.16: Spezifikation von Simulation und Animation in DiaMeta (aus

[116])

Syriani [118], das auch im AToM3-System (vgl. Abschnitt 2.7.5) zum Einsatz kommt.

Des Weiteren lassen sich so recht einfach kontinuierliche Simulationen entwerfen.

Sowohl Simulation und Animation werden in DiaMeta auf Basis des Graph-

modells spezifiziert, das durch dedizierte Attribute bzw. Kanten erweitert werden

muss. Komplexere Animationen bzw. Animationen auf Objekten, die durch Seiten-

effekte betroffen sind, können durch den Layouter ebenfalls berechnet werden.

Mit DiaMeta wurden bereits einige Editoren mit Animationsunterstützung im-

plementiert. Darunter Alligator Eggs, eine Variante des Lambda Kalküls [115] sowie

die Implementierung des Spiels Avalanche [116] und eine Verkehrssimulation.

2.7.4 Moses Toolsuite

Die Moses Toolsuite [33] generiert aus Spezifikationen frei editierbare Editoren.

Die Definition einer visuellen Sprache ist sehr einfach. Es müssen lediglich Struk-

turobjekte sowie deren Attribute definiert werden (Abb. 2.17). Durch so genannte

Prädikate werden Einschränkungen für gültige Sätze der visuellen Sprache definiert.

Das konkrete Aussehen der Knoten wird durch die Zuordnung von einfachen

Formen aus einer Bibliothek erreicht. Benutzerdefinierte Formen können selbst aus-

programmiert werden. Ein Pendant zu DEViLs Editor für generische Zeichnungen

ist nicht vorhanden. Formen sind jedoch stark parametrisierbar.

KAPITEL 2. GRUNDLAGEN

Abbildung 2.17: Definition einer VL in Moses

Aus den Spezifikationen wird intern dann ein attributierter Graph generiert.

Besonderes Augenmerk legen die Autoren von Moses auf die Komposition von

Strukturen. So können Formen aus Unterstrukturen bestehen, die beliebig ein-

oder ausgeblendet werden können. Dies entspricht einer Verflachung von 2,5

dimensionalen Editoren. Von Moses generierte Editoren sind stark auf grapharti-

ge Strukturen festgelegt. Muster wie Matrizen, Tabellen oder Bäume existieren nicht.

Die Moses Toolsuite erlaubt die Spezifikation von Simulationen mittels einer

Variante der Abstract State Machines [43] (ASM). ASMs sind eine recht einfa-

che Art operationale Semantik auszudrücken. Transformationen werden durch

Regeln ausgedrückt, Sprachkonstrukte können über einfache Bedingungen einge-

schränkt werden. Abbildung 2.18 zeigt eine ASM Definition für das Ausführen

von Petri-Netzen. In der Definition für die visuelle Sprache kann über das Attribut

“AnimationDecorator” eine Klasse zur Animation angegeben werden. Diese Klasse

muss jedoch von Hand ausprogrammiert werden. Sprachkonstrukte werden dann

über einen Listener über Änderungen benachrichtigt. In der Decorator-Klasse kann

dann entsprechend reagiert werden. Moses verfügt mit ASMs über eine mächtige

Simulationssprache, die jedoch auch sehr formal ist. Für die Animation hingegen

gibt es keine direkte Werkzeugunterstützung, Animationen müssen ausprogram-

miert werden. Ebenso schränkt Moses die generierten Sprachen auf Sprachen mit

inhärentem Zustand und Zustandsübergängen ein [50].

2.7.5 AToM3

AToM3[27] ist ein visuelles Meta-Modellierungs Werkzeug, das ER-Diagramme mit

OCL [125] zur Spezifikation von Meta-Modellen einsetzt. Das Besondere an AToM3

ist, dass mehrere Sichten auf ein Modell spezifiziert werden können. Dies ist bei

2.7. GENERATORSYSTEME

Abbildung 2.18: Definition eines Petri-Netz Interpreters in Moses

KAPITEL 2. GRUNDLAGEN

GenGed und DiaGen nicht der Fall. Die Spezifikation weiterer Sichten wird durch

Graphersetzungsregeln auf dem Ausgangsmodell erreicht. Dieser Mechanismus ist

vergleichbar mit dem Konzept der gekoppelten Sichten in DEViL.

Neben der Modellierung von Modellen in ER-Notation können Elementen pri-

mitive, bereits voreingebaute typisierte Attribute, wie Integer oder String,

mitgegeben werden oder zusammengesetzte Attribute, die wiederum als Sub-

Modelle aufzufassen sind.

Simulation ist in AToM3ebenfalls durch Graphersetzungsregeln möglich, die

die Autoren als einen “natürlichen, deklarativen und allgemeinen” Ansatz sehen.

Dazu wird in AToM3das DEVS-Modell [118] verwendet. Ein atomares DEVS-Modell

wird dabei zusammengesetzt aus hS,X,Y, δint, δext, λ, τi.Sist eine Menge sequen-

tieller Zustände, Xist eine Menge erlaubter Eingabeereignisse, Yeine Menge

erlaubter Ausgabeereignisse. δint bzw. δext ist die interne bzw. externe Transitions-

funktion. τist die Zeitfortschaltungsfunktion, λist die Ausgabefunktion.

Das Modell startet in einem Initialzustand. Es bleibt in einem beliebigen Zustand,

solange es die Zeitfortschaltungsfunktion vorschreibt und kein Eingabeereignis

stattfindet. Falls kein Eingabeereignis stattfindet, wird ein Ausgabeereignis erzeugt,

sobald die Zeitfortschaltungsfunktion für den momentanen Zustand abgelaufen ist.

Danach wird in den neuen Zustand gesprungen. Findet ein Eingabeereignis statt,

dann wird die externe Transitionsfunktion angewendet.

Mit sogenannten gekoppelten DEVS-Modellen lässt sich ein DEVS-Modell noch

weiter hierarchisch strukturieren. Dabei beschreiben Transfer-Funktionen die

Ausgabe-zu-Eingabe Beziehungen zwischen Komponenten. Abbildung 2.19a zeigt

ein gekoppeltes DEVS-Modell in AToM3zur Simulation von Modellen. Der Con-

troller wählt die im Block GGRule definierten Regeln aus und wendet sie an. Die

Regeln selbst sind ein hierarchischer DEVS-Block, der in Abbildung 2.19b dargestellt

ist. Regeln sind priorisiert und in Layern angeordnet. Ein Synchronisationsblock

entscheidet über die Anwendung von Regeln, falls mehrere in demselbem Priori-

tätslayer matchen. Die Linien zwischen den Blöcken stellen den Datenfluss dar. Die

Daten an sich sind in AToM3Graphen.

Ein Vorgehen zur Herleitung einer Animation ist nicht bekannt.

Konsequent wird in AToM3der Modellbegriff eingesetzt - die Transformation

zwischen Modellen wird als ein Hauptziel angesehen. AToM3ist damit im Gebiet

der Multi-Paradigmen Modellierung [121] anzusiedeln. Der Vorteil, des DEVS-Ansatzes

in AToM3liegt in der Modularität. DEVS-Blöcke können als Black-boxes angesehen

werden, die leicht zu erweitern sind. Kontinuierliche Simulation, genauso wie

Benutzerinteraktion sind ebenso leicht modellierbar, indem z.B. der GGRule-Block

2.8. RELEVANZ IM KONTEXT DIESER ARBEIT

Abbildung 2.19: Gekoppeltes DEVS-Modell in AToM3

in Abbildung 2.19b nochmals unterteilt wird um autonome und benutzerdefinierte

Regeln zu unterstützen.

2.8 Relevanz im Kontext dieser Arbeit

Die bisherigen Betrachtungen beinhalten bereits einige Anforderungen an das zu

entwerfene Gesamtkonzept. Die Klassifizierung der Programmvisualisierung von

Price et al. sowie die Darstellung von Cox zeigen bereits einige generelle Aspekte

für eine Simulation und Animation einer visuellen Sprache. Die Animation sollte

eine nahezu beliebige Abbildung von der zu Grunde liegenden Simulation zulassen.

Große Visualisierungen sollten geeignet aufbereitet werden, um ein hohes Maß

an Verständnis zu erreichen. Hier ist es wichtig Maßnahmen zu treffen um eine

Animation hinsichtlich zeitlichem Ablauf, Strukturierung und Art der Visualisierung

anzupassen. Auch ist es wichtig das Sprachspektrum nicht einzuschränken. Alle

Editortypen, die sich mit DEViL generieren lassen, sollen auch mit einer Simulations-

und Animationskomponente ausgestattet werden können, falls dies gewünscht ist.

Die Animation soll nicht nur direkt auf der Simulation aufbauen, sondern da-

zu benutzt werden um das Verständnis der Simulation zu fördern. Im weiteren

Verlauf der Arbeit wird sich zeigen, dass dazu auch unkonventionelle Mittel wie

z. B. “Exaggeration” und “Anticipation” aus der Comicanimation eingesetzt werden

können. Der Einsatz von mehreren gleichzeitig arbeitenden animierten Sichten

KAPITEL 2. GRUNDLAGEN

erhöht nicht nur die Skalierbarkeit der Sprache. Es können auch verschiedene

Varianten der simulierten Sprachinstanz gleichzeitig betrachtet werden. Hier erlaubt

das Sichten- und das Strukturkopplungskonzept von DEViL bereits ausgefeilte

Darstellungs- und Strukturierungsvarianten.

Die betrachteten Algorithmenanimationssysteme sind besonders interessant im

Hinblick auf die Animationskomponente. Sie stellen Basisanimationstypen bereit,

wie beispielsweise das Bewegen von graphischen Objekten. TANGOs Path-

Transition Paradigma erlaubt es einfach Animationspfade zu spezifizieren. Auch

dies wird sich in dieser Arbeit wiederfinden, wenn es darum geht, Objekte im Struk-

turmodell entlang beliebiger Positionen zu bewegen. Pictorial Janus’ kontinuierliche

Animation zeigt, dass es für eine gute Animation wichtig ist, Zustandsübergänge als

eine weiche Animation darzustellen.

Häufig ist die Darstellung der simulierten visuellen Sprache von der ihr zu-

grundeliegenden DSL weit entfernt. Zum Beispiel werden Roboter im Fahrzeugbau

mit einer Spezialsprache programmiert. Zum Testen dieses Programms möchte

man sich jedoch der visuellen Domäne der Roboter bedienen, anstatt eine Art De-

bugging im Robotercode durchzuführen. Dieser strukturelle Unterschied zwischen

Simulations- und Animationsstruktur sollte ebenfalls einfach spezifizierbar sein.

Auf Seiten der Simulation zeigen die Simulationssprachen und -umgebungen

zum einen den Umgang mit der Simulationsszeit und zum anderen den Umgang mit

Simulationsobjekten. Die Simulationszeit sollte sich möglichst feingranular einstellen

lassen und ein “Springen“ in der Simulationszeit sollte ebenso ermöglicht werden.

Nicht nur Komprimierung von Zeit, sondern auch das beliebige Zurückspringen

und das Einplanen von Aktionen in der Zukunft sind wichtig. Hierbei ist eine ereig-

nisbasierte Simulation mit einer prioritätenbasierten Warteschlange am flexibelsten.

Es wird sich in den nächsten Kapiteln zeigen, dass nur eine Ereignis-Warteschlange

nicht immer ausreichend ist. Insbesondere wenn Daten des Simulationsmodells

gleichzeitig geschrieben und gelesen werden. Dies führt zu “Race-Conditions”, die

ebenfalls geeignet behandelt werden müssen. Lang laufende Simulationen sollten

interessante Zwischenergebnisse speichern bzw. an vom Benutzer festgelegten

Haltepunkten, die vielleicht eine konkrete Ausprägung der Simulation darstellen,

stoppen.

Alle Simulationssprachen und -umgebungen haben gemein, dass Simulations-

objekte erstellt werden und durch das Simulationsmodell wandern, wobei sie

manipuliert werden. Die Simulationsobjekte sind sich ihrer Umgebung “bewusst”,

d. h. je nachdem in welchem Kontext sie sich befinden, werden entsprechende

Aktionen ausgeführt, z. B. die Verzögerung beim Verladen in einer Transportsimu-

lation. Diese Erkenntnis führt zu kontext-sensitiven Simulationsfunktionen (vgl.

Abschnitt 4.3.1 auf Seite 100). Des Weiteren sollte eine Simulationssprache das

einfache Erstellen bzw. Gruppieren von Simulationsobjekten erlauben. Der Zugriff

2.8. RELEVANZ IM KONTEXT DIESER ARBEIT

auf Simulationsobjekte einer bestimmten Art oder mit bestimmten Eigenschaften ist

insbesondere bei visuellen Sprachen wichtig (z. B. “alle Stellen eines Petri Netzes, die

Vorbedingung einer bestimmten Transition sind”). Die Simulationsobjekte kapseln

dabei Eigenschaften, sind also im Sinne der objektorientierten Programmierung In-

stanzen von Klassen. Diese Art der Gruppierung und Neuanordnung von Objekten

führt zum Begriff des Simulationsmodells.

Um aussagekräftige Simulationen zu erreichen, ist ein Simulationsmodell, das

Zufallsvariablen diverser Verteilung bietet von Bedeutung. Alle Simulationsspra-

chen bieten hierfür spezialisierte Konstrukte. Auch ist das Protokollieren von

Variablen über die Zeit (so genannte Tracevariablen) wichtig, um Aussagen zum

Simulationsmodell zu treffen. Hier zeigt sich, dass die Simulationsumgebungen aus-

gefeilte Mechanismen zur Analyse mitbringen. Dies können Report Mechanismen

oder die Überprüfung von Eigenschaften des Simulationsmodells sein. In der vor-

liegenden Arbeit wird dieser Aspekt besonders berücksichtigt. Der hier entworfene

Simulator wird Mechanismen zur Analyse bereitstellen, die über die reine Animation

hinausgehen. Es werden dem Sprachanwender und auch dem Sprachspezifizierer

weitere Werkzeuge zur Überprüfung der Sprachinstanz mitgegeben.

Viele Simulationsumgebungen sind auf die Simulation von Fertigungsstraßen

spezialisiert. Hier gibt es diverse Sprachkonstrukte um den Fluss von Werkstücken

zu spezifizieren. Die Simulationsobjekte sind sich ihrer Umgebung “bewusst”, d. h.

je nachdem in welchem Kontext sie sich befinden, werden entsprechende Aktionen

ausgeführt, z. B. die Verzögerung beim Verladen in einer Transportsimulation. Diese

Erkenntnis führt zu kontext-sensitiven Simulationsfunktionen (vgl. Abschnitt 4.3.1

auf Seite 100).

Des Weiteren ist, wenn die Spezifikation von Simulation betrachtet wird, ein

Nachteil in den Algorithmenanimationssystemen erkennbar: Beim Konzept der

“interesting Events” muss der Animator den Algorithmus kennen um animieren

zu können. Der Simulationsalgorithmus wird durch Animationsaufrufe erweitert.

Simulation und Animation sind somit nicht mehr voneinander entkoppelt, was

dazu führen kann, dass interessante Ereignisse verpasst werden bzw. eigentlich gar

nicht wirklich von Belang sind. Letztlich muss der Animator genauso viel über den

Simulationsalgorithmus kennen, wie der Simulationsentwerfer.

Wenn die generierten Simulationsumgebungen betrachtet werden, fällt auf, dass es

sehr nützlich sein kann, wenn der Benutzer direkt in die Animation eingreifen und

diese unmittelbar verändern kann. Dies hat dann direkte Auswirkungen auf die

Simulation. Der Forms/3 Ansatz zeigt das deutlich.

Die vorgestellten Generatorsysteme zur Spezifikation von Struktureditoren ha-

ben zum Teil schon Mechanismen eingebaut, um Simulationen und Animationen

herzustellen. Zum einen sind Systeme auf Basis von Graphtransformation zu

KAPITEL 2. GRUNDLAGEN

nennen, die Simulation über Ersetzungregeln definieren. Der Ansatz ist sehr formal

jedoch deswegen auch problematisch. Der Spezifizierer muss sich zunächst mit

einem formalen Kalkül auseinandersetzen. Insbesondere beim GenGed System

ist dies schwierig, da recht viele neue Ebenen für die Simulation und Animation

eingeführt werden. Von Vorteil ist, dass Graphersetzungssysteme wie GenGed

Simulation auf der konkreten Syntax definieren können. Einschränkend ist zu sagen,

dass Graphersetzungregeln Zusammenhänge zwischen entfernten Objekten sowie

Objekten, die irgendwo im Modell zu finden sind nur schlecht beschreiben können

[58]. Zudem ist es schwierig, immer alle möglichen Fälle abzudecken. Dies führt

häufig zu einer Explosion der Regelmenge und auch zu Problemen, falls mehrere

Regeln zutreffen. Meist wird dann eine Regel nicht-deterministisch ausgewählt.

Eine weitere Schwierigkeit ist das Speichern von Zuständen, damit Regelse-

quenzen ausgeführt werden können. Hier müssen Regeln künstlich um Attribute,

die den Zustand speichern, erweitert werden.

2.9 Das DEViL-System

Das Generatorsystem DEViL (Development Environment for Visual Languages) ist

eine Entwicklungsumgebung für visuelle Struktureditoren. Es basiert auf dem Vor-

gängersystem VL-Eli von Jung [54] und wurde von Schmidt weiterentwickelt [101].

Aus Spezifikationen eines hohen Abstraktionsniveaus erzeugt DEViL vollständige

graphische Editoren mit Codegenerierung. Die Spezifikationen beschreiben dabei

das Modell der Sprache, sowie Repräsentation und Transformation der visuellen

Sprache. Von DEViL generierte Editoren basieren auf dem Model-View-Controller

Paradigma, wobei die so genannte abstrakte Struktur das Modell der Sprache ist und

verschiedene graphische Repräsentationen, so genannte Sichten, daran gekoppelt

sind. Das Spezifikationskonzept ist in Abbildung 2.20 dargestellt. Es besteht im

Wesentlichen aus der Spezifikation der abstrakten Struktur mittels DSSL (DEViL

Structure Specification Language) und der Dekoration dieser abstrakten Struktur

mit visuellen Mustern (VP).

Die visuellen Muster beschreiben deklarativ, wie Teilbäume der Struktur graphisch

repräsentiert werden sollen. Dazu steht eine breite Bibliothek an vorgefertigten Mus-

tern zur Verfügung. So kann beispielsweise ausgedrückt werden, dass Teilbäume

als Listen, Mengen oder Matrizen dargestellt werden sollen. Zusätzlich kann ein

Codegenerator spezifiziert werden, um aus Instanzen der visuellen Sprache Zielcode

zu generieren. Dazu stehen alle Werkzeuge des Eli-Systems [41], auf dem DEViL

basiert, zur Verfügung. DEViL benutzt Generatoren zur Sprachimplementierung

des Eli Systems sowie Wodan, ein eigenes Herstellungsprozesssystem. Mit Dot zum

Layout von Graphen und AspectC++ zur Implementierung von aspekt-orientiertem

Code kann der Generator Struktureditoren generieren, die eine eigene Multi-

2.9. DAS DEVIL-SYSTEM

1Spezifikation der

abstrakten Struktur

2b Spezifikation der

Codegenerierung

3Generierte

Umgebung

DEViL

Spezifikation

visueller Sichten

Abbildung 2.20: Das Spezifikationskonzept von DEViL

Fenster-Umgebung mit selbstdefinierten Datentypen unterstützen. Zur visuellen

Spezifikation graphischer Struktureditoren kann der DEViL-Designer [23] benutzt

werden, der Eingaben für alle unterliegenden Werkzeuge generiert.

Alle von DEViL generierten Editoren basieren auf einem Grundmodell: der Trennung

von editierbarer und semantischer Struktur (Abb. 2.21). Die abstrakte Struktur einer

visuellen Sprache ist mit der abstrakten Syntax einer kontextfreien Sprache in Üb-

sersetzern vergleichbar. Sie bildet das Fundament für semantische und editierbare

Struktur. Die semantische Struktur enthält die für das Programm semantisch wich-

tigen Konstrukte und ist frei von Attributen, die nur der konkreten Repräsentation

dienen. Die editierbare Struktur ist Grundlage für die konkrete graphische Repräsen-

tation der Darstellung. Sie enthält vor allem zusätzliche Layout-Informationen.

2.9.1 Spezifikation der abstrakten Struktur

Zur Spezifikation der abstrakten Struktur wird in DEViL DSSL benutzt. DSSL basiert

auf objektorientierten Modellierungskonzepten wie Klassen, Attributen und Verer-

bung. Jede Instanz einer nicht-abstrakten Klasse repräsentiert ein graphisches Objekt

in der Darstellung. Innerhalb von Klassen existieren drei Knotentypen:

KAPITEL 2. GRUNDLAGEN

Kopplung

Editierbare Struktur

●Passt zur visuellen

Repräsentation

●Enthält Layout-Informationen

Semantische Struktur

●Redundanzfrei

●abstrahiert von allen

Repräsentationsaspekten

ändern generieren

Visuelle

Repräsentation

Generierter Code,

Analyse-Ergebnisse, ...

visualisieren

01 11 00 01 01

11 10 01 01 00

10 11 00 01 01

01 11 00 01 01

11 10 01 01 00

01 11 00 01 11

11 10 01 11 00

10 11 00 01 01

Abbildung 2.21: Die Trennung von editierbarer und semantischer Struktur in

DEViL (aus [101])

•Knoten vom Typ VAL. Sie speichern primitive Attribute und können diverse

Datentypen annehmen, z. B. VLInt zum Speichern von Integer-Werten oder

VLString zum Speichern von Zeichenketten. Durch ein Fragezeichen hinter

dem Knoten kann spezifiziert werden, ob ein VAL-Attribut zwischenzeitlich

auch leer sein darf.

•Knoten vom Typ REF. Sie speichern Referenzen zu anderen Objekten im Struk-

turbaum. Sie modellieren also die Querbeziehungen im Baum.

•Knoten vom Typ SUB. Sie speichern Unterstrukturen vom angegebenen Typ.

Sie modellieren also die Baumkanten der abstrakten Struktur. SUB-Knoten dür-

fen nur Objekte von Untertypen der angegebenen Klasse enthalten. Hinter der

Typangabe darf eine Kardinalität angegeben werden. So können auch Knoten

modelliert werden, die nur genau einen Unterbaum speichern.

In der Arbeit werden Knoten vom Typ VAL bzw. REF auch Attributknoten genannt.

Knoten vom Typ SUB werden Aggregationsknoten genannt. Wenn alle Knoten ange-

sprochen werden sollen, wird in dieser Arbeit die Bezeichnung Sprachkonstruktknoten

verwendet.

Abbildung 2.22a zeigt einen kleinen Ausschnitt aus einer Spezifikation für

Statecharts. Dabei erben die Klassen SimpleState und XORState von der abstrak-

ten Klasse State. In XORState können im Attribut subStates weitere Unterobjek-

te des State Knotens enthalten sein. Die Klasse Transition enthält neben einem

Attribut für den Namen, zwei Referenzen auf State Knoten.

2.9. DAS DEVIL-SYSTEM

Stärken und Schwächen DSSL besticht durch die Einfachheit der Beschreibung

von strukturellen Eigenschaften. Es kommt mit wenigen orthogonalen Sprachkon-

strukten aus, die eine Beschreibung von Struktur und persistenten Daten ausdrücken

können. Somit ist die Sprache sehr übersichtlich und schlicht gehalten, aber trotz-

dem mächtig genug um beliebige Baumstrukturen beschreiben zu können. Aus einer

Spezifikation der abstrakten Syntax kann breits ein baumbasierter und voll funkti-

onsfähiger Struktureditor generiert werden. Allerdings können in DSSL keine Trans-

formationen auf Basis eines Automaten ausgedrückt werden. Es gibt keine direkte

Unterstützung zur Gruppierung von Sprachkonstruktinstanzen.

KAPITEL 2. GRUNDLAGEN

ABSTRACT CLASS State {

}

CLASS SimpleState INHERITS State

{}

CLASS XORState INHERITS State {

subStates: SUB State*;

}

CLASS Transition {

label: VAL VLString;

from: REF State;

to: REF State;

}

a) b)

SYMBOL StatechartDiagram INHERITS VPRootElement,VPForm, VPConnectionArea

COMPUTE

SYNT.drawing = ADDROF(StatechartDiagramDrawing);

END;

SYMBOL StatechartDiagram_transitions INHERITS VPConnectionList END;

SYMBOL StatechartDiagram_name INHERITS VPFormElement, VPIdTextPrimitive

COMPUTE

SYNT.formElementName = "name";

END;

SYMBOL StatechartDiagram_states INHERITS VPFormElement, VPSet

COMPUTE

SYNT.formElementName = "body";

END;

SYMBOL State INHERITS VPSetElement, VPConnectionEndpoint

COMPUTE

END;

SYMBOL XORState INHERITS VPForm

COMPUTE

SYNT.drawing = ADDROF(XORStateDrawing)

END;

Abbildung 2.22: Spezifikation von Struktur und Repräsentation: a) semantische

Struktur, b) eine generische Zeichnung, die einem Sprachkon-

strukt seine konkrete graphische Darstellung verleiht und c) Be-

schreibung der graphischen Repräsenation durch Anwendung

visueller Muster.

2.9. DAS DEVIL-SYSTEM

2.9.2 Spezifikation der graphischen Darstellung

Die Sprachkonstruktknoten der abstrakten Struktur werden, um eine konkrete

graphische Repräsentation zu erreichen, mit visuellen Mustern attributiert (Abb.

2.22c). Wie zu sehen ist, erben die Sprachkonstruktknoten dabei bestimmte Rollen

der visuellen Muster, z. B. VPSet zur Darstellung einer Menge. DEViL stellt eine

große Bibliothek an vorgefertigten Mustern bereit. Dies sind beispielsweise Muster

zur Darstellung von Listen, Mengen, Matrizen, Tabellen und vieles mehr. Die

visuellen Muster können durch Kontrollattribute geeignet parametrisiert werden

um das Layout und die graphische Darstellung individuell anzupassen. In [103] und

[104] werden die visuellen Muster genauer beschrieben.

Das visuelle Muster VPForm hat eine herausragende Rolle: Es hat die Eigen-

schaft, Sprachkonstrukten ein spezifisches Aussehen zu verleihen. So kann diesem

Muster durch ein Kontrollattribut SYNT.drawing eine so genannte generische

Zeichnung zugeordnet werden. Abbildung 2.22b zeigt eine solche Zeichnung für

das visuelle Element XORState der Statecharts. Generische Zeichnungen ordnen

Sprachkonstrukten ihr konkretes Aussehen zu. Sie sind als abstraktes Konzept zu

verstehen und kapseln neben graphischen Primitiven, wie Linien, Rechtecken oder

Kreisen auch Ausdehnungseigenschaften. Innerhalb von generischen Zeichnungen

können so genannte Container benutzt werden. Container können Unterbäume

aufnehmen und dehnen die generische Zeichnung entsprechend der Größe der

aggregierten Elemente aus. In Abb. 2.22b sind die beiden Container subStates

und name enthalten. Container können innerhalb der Sichtdefinition mit dem

Kontrollattribut formElementName angesprochen werden (vgl. Abb. 2.22c). Das

Besondere an generischen Zeichnungen ist, dass sie automatisch den Platzbedarf für

aggregierte Objekte berechnen und sich die Zeichnung beliebig ausdehnen kann.

Ist so beispielsweise der horizontale Platzbedarf nicht ausreichend, so wird die

Zeichnung gedehnt, indem quasi an den Enden “gezogen” wird. Diese Ausdehnung

kann mit Eigenschaften der Container angepasst werden, d. h. sie ist insbesondere

nicht linear!5

Die Musteranwendung erfolgt in der funktionalen Sprache LIDO [53]. In der

Regel müssen nur wenige Kontrollattribute überschrieben werden. Falls dies nicht

ausreicht, stehen jedoch alle Mechanismen des zu Grunde liegenden Eli Systems zur

Verfügung. Auch benutzerdefinerter Code in Form von C- oder Tcl-Funktionen kann

zur Berechnung benutzt werden.

Stärken und Schwächen Der Ansatz zur Spezifikation einer graphischen Dar-

stellung ist vollständig deklarativ. Durch die große visuelle Musterbibliothek und

die Kombinierbarkeit der Muster kann nahezu jede graphische Darstellung erreicht

werden. Die Modellierung des Zusammenhangs zwischen Struktur und Darstellung

5Dies führt später in der Arbeit zum Konzept des Morphens von generischen Zeichnungen.

KAPITEL 2. GRUNDLAGEN

ist klar: Ein Sprachkonstrukt wird in einer Sicht durch eine Musterberechnung

dargestellt6.

Für eine Animation kann dieser direkte Bezug auch ein Nachteil sein. Objekte,

die keinen Repräsentanten im Modell haben, z. B. flüchtige Objekte, können zu-

nächst nicht definiert werden. Die Spezifikation der Repräsentation ist vollständig

von der Strukturdefinition entkoppelt, was zu einer Erleichterung bei der Ent-

wicklung in Teamarbeit führt. Das Konzept der Spezifikation der graphischen

Darstellung mittels generischer Zeichnungen überzeugt durch den visuellen Ansatz.

Nachteilig im Hinblick auf die hier entworfene Animationserweiterung wirkt sich

aus, dass zwar Strukturobjekten eindeutig graphische Primitive zugeordnet werden,

dies aber nicht konsequent bei Attributen gemacht wird. D. h. Attribute haben in

der graphischen Darstellung keine Identität mehr. Dies ist problematisch, wenn auf

einem Attribut eine Änderung in der Simulation ausgelöst wird, dieses Attribut

aber in der graphischen Repräsentation nicht mehr “gefunden” werden kann.

Hier zeigt sich ein generelles Problem der Implementierung von DEViL: Der Weg

von der Struktur zur graphischen Repräsentation ist durch Abbildungen recht ein-

fach, diese sind jedoch nicht bijektiv, sodass der Rückweg entsprechend schwierig ist.

Der Algorithmus zur Berechnung der graphischen Darstellung mittels generi-

scher Zeichnungen ist sehr komplex und wirkt sich zum Teil unvorhersehbar auf

die graphische Darstellung aus. Dies führt später in der Arbeit dazu, dass die

Repräsentation von zwei aufeinanderfolgenden Simulationszuständen nur durch

einen “Trockenlauf” der Attributauswerter und dem Zwischenspeichern aller(!)

graphischer Objekte erreicht werden kann.

Grammatikabbildung

Um attributierte Grammatiken als Kalkül zur Berechnung der Darstellung verwen-

den zu können, muss die semantische Struktur, spezifiziert durch DSSL, auf eine

kontextfreie Grammatik abgebildet werden. Dieses Verfahren beruht darauf, dass

die Abbildung eine neue Struktur schafft, die für LIGA [53] geeignet ist. Allgemein

wird dabei jede nicht-abstrakte DSSL Klasse auf eine Grammatikregel abgebildet.

Auf der linken Seite steht ein Nichtterminal, das sich aus dem Namen der Klasse

ableitet. Auf der rechten Seite steht die Attributhülle der Klasse. Diese besteht aus

der Menge der direkt definierten Attribute, vereinigt mit den direkt oder indirekt

geerbten Attributen.

Die Abbildung der DSSL Sprachkonstrukte auf die kontextfreie Grammatik ge-

schieht automatisch, der Anwender braucht hier in der Regel nicht einzugreifen.

6Dies ist auch ein Nachteil, da innerhalb einer Sicht ein Sprachkonstrukt an allen Stellen dieselbe

Musteranwendung bekommt. Dies resultiert aus der Spezifikationssprache LIDO, die keine mehr-

fachen Aufkommen von gleichbenannten Symbolberechnungen erlaubt.

2.9. DAS DEVIL-SYSTEM

function dvariable

lowerBound

upperBound

operandssymbol middle

Integral

symbol operands

upperBounds middle lowerBounds

function d variable

CLASS Integral {

function: SUB Expression!;

variable: SUB Variable!;

lowerBound: SUB Expression!;

upperBound: SUB Expression!;

}

Integral(

symbol(),

operands(

upperBounds,

middle(function, d(), variable),

lowerBounds

)

a) Editor-Syntax

c) Konkrete Repräsentation

b) Spezifikation der Repräsentationsstruktur

d) Illustration der Repräsentationsstruktur

Abbildung 2.23: Das Konzept der Grammatikabbildung (aus [101])

Allerdings gibt es Fälle, in denen es sinnvoll ist, die automatische Grammatikabbil-

dung zu überschreiben. Meistens kommt dies vor, wenn editierbare und semantische

Struktur sich leicht unterscheiden und wenn eine abweichende Strukturierung

sinnvoller erscheint. Abbildung 2.23a zeigt die Modellierung eines Integrals in DSSL

und die graphische Repräsentation 2.23c dieser Klasse. Wie zu erkennen ist, besteht

die graphische Darstellung aus einer Reihe von geschachtelten Rechtecken, in denen

die Bestandteile des Integrals eingefügt werden sollen. Die Standardabbildung von

DSSL auf die Grammatik würde hier zu einer Baumstruktur führen, bei der die

Attribute der Klasse Integral aus Abbildung 2.23a alle auf einer Ebene dargestellt

werden. Die nochmalige Schachtelung, um eine Darstellung wie in Abbildung 2.23c

zu erreichen, wäre nicht möglich. Um diese Strukturierung dennoch zu erhalten,

kann eine textuelle Spezifikation wie in Abbildung 2.23b benutzt werden. Es ent-

steht dann ein Strukturbaum wie in 2.23d. Die Wurzel Integral ist der einzige

Sprachkonstruktknoten der Spezifikation. Die grau hinterlegten Knoten stellen neue

Zwischenknoten dar. Sie können beliebig benannt werden und beschreiben neu

eingefügte Zwischenproduktionen der Grammatik, die dann auch benutzt werden

können um Rollen visueller Muster anzuwenden.

KAPITEL 2. GRUNDLAGEN

In der textuellen Spezifikation in Abb. 2.23b werden Unterknoten in Klammern

hinter ihrem Vaterknoten notiert. Zwischenknoten lassen sich von Attributknoten

daran unterscheiden, dass hinter Zwischenknoten noch ein evtl. leeres Klammern-

paar folgt.

2.9.3 Zusammenhang zur Repräsentationsgraphik

Editierbare und semantische Struktur sind in der Regel nahezu identisch. In ei-

nigen Spezialfällen können sich beide Strukturen allerdings unterscheiden. Dies

ist beispielsweise der Fall, wenn es von einem semantischen Sprachkonstrukt

in unterschiedlichen Sichten mehrere Repräsentanten gibt. Dies kommt in UML

Diagrammen vor. Hier kann eine Klasse in mehreren Diagrammen enthalten sein.

Die editierbare Struktur würde im zugehörigen Editor also noch einen zusätzlichen

Repräsentanten der Klasse bereitstellen. Häufig möchte man auch Sprachen spezi-

fizieren, die einen bestimmten Teil der semantischen Struktur mehrfach, jedoch in

unterschiedlichen Layoutvarianten, darstellt. Weitere Anforderungen für die Tren-

nung von semantischer und editierbarer Struktur nennt Schmidt in [101] (Seite 106 ff).

Um auch Sprachen mit unterschiedlichem Niveau von semantischer und edi-

tierbarer Struktur spezifizieren zu können, steht in DEViL ein so genannter

asymmetrischer Kopplungsmechanismus zur Verfügung. Er erlaubt es, beide

Strukturen aneinander anzupassen. Dazu stehen diverse Anpassungsschemata

bereit, die flexibel bestimmte Sprachkonstruktknoten aneinander binden können.

Asymmetrisch ist die Kopplung, da es möglich ist, beide Richtungen der Kopp-

lung unterschiedlich zu behandeln. So kann beispielsweise spezifiziert werden,

dass sich das Löschen eines Repräsentanten in der editierbaren Struktur nicht auf

sein Pendant in der semantischen Struktur auswirkt. Schmidt beschreibt in [101]

sieben Anpassungsschemata um die Kopplung zu definieren. In [127] wurde eine re-

gelbasierte Spezifikationssprache zur Kopplung von Strukturen in DEViL entworfen.

Listing 2.7 zeigt einen Ausschnitt der Basisstruktur für einen Petri-Netz Editor,

der das Dining-Philosophers Problem modelliert. Die Basisstruktur modelliert einfa-

che Petri-Netze. Die abgeleitete Struktur aus Listing 2.8 koppelt an jede PetriNet

Instanz eine diningPhilosophers::PetriNet-Instanz. Sie enthält genau die

Attribute aus Listing 2.8 und überschreibt somit die entsprechende Klasse aus der

Basisstruktur. Durch das Anpassungsschema syncVal wird sichergestellt, dass

2.9. DAS DEVIL-SYSTEM

das Größenattribut setSize in der abgeleiteten Struktur nicht gekoppelt wird.7

¨ ¥

CLASS Root {

petriNets: SUB PetriNet%;

diningPhilosophers: SUB

diningPhilosophers::PetriNet*;

}

CLASS PetriNet {

nodes: SUB Node*;

connections: SUB Connection*;

setSize: VAL VLPoint?EDITWITH "None";

}

ABSTRACT CLASS Node {

position: VAL VLPoint?EDITWITH "None";

}

...

Listing 2.7: Ausschnitt aus der

Basisstruktur

¨ ¥

DERIVED diningPhilosophers ROOT PetriNet {

CLASS PetriNet {

philosoph1: SUB Philosoph?;

philosoph2: SUB Philosoph?;

philosoph3: SUB Philosoph?;

philosoph4: SUB Philosoph?;

philosoph5: SUB Philosoph?;

setSize: VAL VLPoint?INIT "500 500"

EDITWITH "None";

}

CLASS Philosoph {

dishRef: REF Dish EDITWITH "None";

}

...

PetriNet.setSize.syncVal = 0;

}

Listing 2.8: Eine abgeleitete

Struktur

Abbildung 2.24 zeigt, wie in DEViL sukzessive die graphische Darstellung aus der

editierbaren Struktur berechnet wird. Auf der linken Seite sind dazu die notwendi-

gen Transformationsschritte dargestellt. Dies führt letztendlich zur Rastergraphik,

also der Darstellung, die durch den Anwender manipuliert werden kann. Rechts ist

dargestellt, wie intern graphische Primitive in der Zeichenfläche auf Strukturobjekte

abgebildet werden.

Die editierbare Struktur wird zunächst auf die Repräsentationsstruktur abgebildet.

Diese enthält zusätzlich Methoden und Daten für die weiteren Transformationen.

In DEViL sind dies die visuellen Muster. Die abstrakte Repräsentation beschreibt

die wesentlichen Darstellungseigenschaften in einem konzeptionell sprachunabhän-

gigen Kalkül. In der Layoutphase werden den Layoutattributen der graphischen

Objekte ihre konkreten Werte zugewiesen. In der Regel sind dies Angaben über

Positionen und Farben. Durch das Rendering wird durch das Betriebssystem die

Darstellung auf dem Monitor erzeugt.

Wie auf der rechten Seite zu sehen ist, werden den Strukturobjekten des se-

mantischen Modells eindeutige Kennungen zugeordnet, sodass Benutzerinterkation

(z. B. das Löschen eines Objekts) in der Rastergraphik auf das korrekte Strukturobjekt

zurückgeführt werden kann. Dabei kann ein Strukturobjekt aus vielen graphischen

Primitiven, z. B. mehreren Linien (spezifiziert im Editor für generische Zeichnungen)

zusammengesetzt werden. Die Primitive haben dann keine eindeutige Kennung

mehr, sie erben die Kennung des zugeordneten Strukturobjekts. Auch Attributkno-

7Die Simulation des Dining-Philosophers Problems ist in Abschnitt 7.4.1 auf Seite 156 zu finden.

KAPITEL 2. GRUNDLAGEN

Editierbare Struktur

(Editor-Syntax)

Repräsentations-

struktur

Mapping

Transformation

Abstrakte

Repräsentation

Layout

Vektorgrafik

Rendering

Rastergrafik

Semantische

Struktur

obj-1

obj-2

Abbildung 2.24: Abbildung auf die Repräsentationsstruktur

ten erben ihre Kennung von dem Knoten in dem sie definiert wurden. Prinzipiell

ist es in von DEViL generierten Struktureditoren schwierig die Rückrichtung zu

berechnen, da die Transformationen nicht bijektiv sind. Dies ist von Nachteil bei

der Berechnung einer Animation, die alle Primitive eindeutig zuordnen muss, um

Änderungen zu erkennen. In dieser Arbeit musste deswegen ein Mechanismus

geschaffen werden um trotzdem Primitive eindeutig identifizieren zu können.

2.9.4 Das Klassenmodell und Pfadausdrücke in DEViL

Häufig ist es nötig, dass im Strukturbaum eines generierten Editors bestimmte Attri-

bute aufgesammelt werden müssen, z. B. um eine Analyse zu bewerkstelligen.

Um im Strukturbaum der visuellen Sprache zu navigieren und Objekte aufzusam-

meln bzw. Attributeigenschaften zu lesen, stehen die so genannten Pfadausdrücke zur

2.9. DAS DEVIL-SYSTEM

Transition

Transition.from

Transition.to

XORState

XORState.subStatesXORState.name

SimpleState XORState

„State 1“

.from .VALUE

THIS

.name

.VALUE

Abbildung 2.25: Pfadausdruck für THIS.from.VALUE.name.VALUE

Verfügung. Sie beschreiben in einer Spezialsprache, die sich an XPath orientiert, Be-

wegungen im Strukturbaum. Somit kann durch den Baum gewandert und Attribute

bzw. Substrukturen abgefragt werden. In Abbildung 2.25 ist eine mögliche Instanz

eines Strukturbaums der Spezifikation aus Abb. 2.22 zu sehen. Hier wird, ausgehend

von einem Transition-Knoten auf den Namen des zugeordneten XOR-Knotens

zugegriffen. Die Pfadausdruck Syntax besteht aus Konstrukten um Werte zu lesen

und um auf Mengen von Objekten zuzugreifen. Eine genauere Beschreibung ist [101]

zu entnehmen.

2.9.5 Eigenschaften generierter Umgebungen

Mit dem DEViL Generator lassen sich eine Vielzahl an unterschiedlichen Arten

von Struktureditoren für visuellen Sprachen generieren. Struktureditoren mit

2,5-dimensionalen Darstellungen [40], die es erlauben z. B. Detailsichten zu einem

Sprachobjekt zu öffnen und untereinander verbundene Diagramme zu spezifizieren,

sind in DEViL eingeschränkt generierbar. Editoren mit dreidimensionalen Darstel-

lungen lassen sich hingegen nicht spezifizieren.

Interaktionsbasierte Repräsentationen, deren wichtiges Layoutmittel die Explo-

ration des Programms durch den Benutzer ist, können ebenfalls generiert werden.

Dazu gehören Baumdarstellungen, deren Knoten durch den Anwender auf- bzw.

zugeklappt werden können oder beispielsweise Sprechblasen, die sich öffnen, wenn

der Benutzer mit der Maus über ein Sprachkonstrukt fährt.

Von DEViL generierte Editoren bieten dem Benutzer sowohl diskrete als auch

kontinuierliche Layoutfreiheiten. Diskrete Layoutfreiheiten sind z. B. der Zeilenum-

bruch in einem textuellen Editor, der vom Benutzer bestimmt werden kann. Eine

KAPITEL 2. GRUNDLAGEN

kontinuierliche Layoutfreiheit ist die Anordnung von Mengenelementen, um für

den Benutzer eine zusätzliche Semantik durch sekundäre Notation zu erreichen.

Die Interaktion zwischen Benutzer und DEViL-Editoren basiert darauf, dass

Sprachobjekte in DEViL immer nur abhängig vom Kontext eingefügt werden kön-

nen. DEViL bietet also je nach Editiersituation nur Sprachkonstrukte an, die auch laut

Syntax der Sprache eingefügt werden dürfen. Dies hat den Vorteil, dass syntaktisch

inkonsistente Strukturen nicht entstehen können. Daraus ergibt sich jedoch auch der

Nachteil, dass temporär inkonsistente Strukturen nicht entworfen werden können,

was zu einem erhöhten Aufwand bei der Erstellung einer Sprachinstanz durch einen

Anwender führt. Editoren mit Parsing Techniken umgehen dieses Problem. Zusätz-

lich können Sprachkonstrukte mit der Maus “angefasst“ und direkt manipuliert

werden (direct-manipulation). Über Tastaturkürzel und Eigenschaften, die auch von

Texteditoren bekannt sind, wie “Kopieren, Einfügen” oder “Ausschneiden” kann

der versierte Benutzer die Editoren zügig benutzen.

Semantische und editierbare Struktur der Editoren haben in DEViL das gleiche

Niveau. Unterschiede können durch Anpassung des Kopplungsmechanismus

zwischen den beiden Strukturen ausgeglichen werden. Dadurch ist es möglich, ein

Sprachkonstrukt in mehreren Sichten modifiziert darzustellen. In UML Diagrammen

kann somit beispielsweise eine Klasse in mehreren Diagrammen (Sichten) dargestellt

werden. Es existieren also mehrere Sichtrepräsentanten in der editierbaren Struktur

für ein semantisches Objekt.

Die Schärfe der Editorsyntax beschreibt den Abstand zwischen syntaktisch und

semantisch korrekten Programmen. In Struktureditoren können per Definition nur

syntaktisch korrekte Programme erstellt werden. Eine allzu scharfe Syntax würde zu

einem benutzerunfreundlichen Editor führen. Die Schärfe der Syntax in von DEViL

generierten Editoren ist durch DSSL in etwa mit denen von UML Diagrammen ver-

gleichbar. So können durch Baumstrukturen, Querbeziehungen und Kardinalitäten

strukturelle Constraints definiert werden.

Die von DEViL generierten Editoren sind, bedingt durch den nicht-parsing ba-

sierten Ansatz, sehr ausdrucksstark. Eine vollständige Evaluation der Produktebene

hinsichtlich der Bedienbarkeit findet sich in [101] und in [102].

Relevanz im Kontext dieser Arbeit DEViL erlaubt es mit klar getrennten Kon-

zepten Struktur, graphische Repräsentation und Analyse zu beschreiben. DSSL zur

Strukturspezifikation bietet sich in ähnlichen Konzepten auch zur Definition eines

Simulationsmodells an. Es können Aggregation, Vererbung und Attributierung wie-

derverwendet werden. Die Pfadausdrücke, mit denen Strukturobjekte bestimmter Ei-

genschaften “gesammelt” werden können, bieten sich ebenfalls an um Simulations-

2.9. DAS DEVIL-SYSTEM

objekte mit gleichen Eigenschaften zu kapseln. Auf struktureller Seite fehlen DSSL

Eigenschaften wie Funktionen und ein zufallsbasierter Baumaufbau.

Zur Spezifikation der graphischen Darstellung bietet DEViL eine mächtige parame-

trisierbare Musterbibliothek. Diese kann einfach (durch Kontrollattribute) aber auch

beliebig angepasst werden. Das deklarative Konzept ist bewährt [102]. Die direkte 1:1

Beziehung zwischen Struktur und Repräsentation sowie die komplexen Algorithmen

zur Darstellung stellen jedoch hohe Anforderungen im Hinblick auf die Implemen-

tierung einer Animationskomponente.

3 Simulier- und Animierbarkeit

visueller Sprachen

Inhalt

3.1 StrukturundDaten............................ 70

3.2 Zustand und Zustandsübergänge . . . . . . . . . . . . . . . . . . . 73

3.3 Repräsentation .............................. 76

3.4 Klassifikation visueller Sprachen . . . . . . . . . . . . . . . . . . . 77

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

Voraussetzung für eine Simulation oder eine Animation ist zunächst, dass sie für

eine gegebene Sprache auch sinnvoll ist und einen echten Mehrwert an Erfahrung

bringt. Dies hängt stark von der Sprache, dem Entwickler- und Anwenderkreis

sowie dem Teilgebiet ab, dem die Sprache zuzuordnen ist (vgl. auch Abschnitt 2.4).

Ist dieser Aspekt geklärt, kann untersucht werden, ob und wie die Sprache mit

Simulations- bzw. Animationsunterstützung ausgestattet werden kann.

In diesem Kapitel werden visuelle Sprachen untersucht, und es soll geklärt werden,

welche Bedingungen für eine Sprache gelten, die simulier- bzw. animierbar ist. Dabei

werden die Sprachen insbesondere auf ihre interne Struktur hin untersucht, d. h. es

wird betrachtet, wie sich das Modell der Sprache von der Zustandsrepräsentation

unterscheidet oder inwieweit beides miteinander verwoben ist. Es soll dabei im

Folgenden herausgefunden werden, wie eine visuelle Sprache mit Simulations-

und Animationsunterstützung beschaffen ist und unter welchen Bedingungen

eine Instanz einer visuellen Sprache simuliert werden kann. Dazu werde ich den

Begriff “Programm” genauer charakterisieren und ausweiten. Außerdem wird auf

Besonderheiten einer Animation hingewiesen: z. B. können dies zusätzliche Effekte

oder spezielle Animationsrepräsentationen sein.

3.1 Struktur und Daten

Im herkömmlichen Sinne der Programmiersprachen ist ein Programm “die Formu-

lierung eines Algorithmus und der zugehörigen Datenbereiche sowie Darstellung

von Prozessen und Objekten in einer Programmiersprache“ [64]. Diese Definition

sagt noch nichts über die Simulierbarkeit eines visuellen Programms aus. Insbeson-

dere kann ein Programm im herkömmlichen Sinne noch nicht unmittelbar simuliert

werden, da noch nichts über den Zustand und die Zustandsübergänge bekannt ist.

Ein Programm ist lediglich eine konkrete Ausprägung der Syntax einer Sprache.

In einer visuellen Sprache wird ein Programm durch eine Menge von visuellen

Konstrukten beschrieben, die durch eine gegebene Syntax entsprechend angeordnet

werden. Visuelle Konstrukte sind dabei vergleichbar mit Konstrukten aus textuellen

Sprachen, wie z. B. bedingte Ausdrücke, Befehle etc.. Auch sie werden entsprechend

einer gegebenen Syntax und Semantik angeordnet. Die Ausführungssemantik

könnte z. B. durch eine denotationale Semantik formal definiert werden. Eine deno-

tationale Semantik ordnet den Konstukten der Sprache eine Wirkung zu. Auch in

der Simulation einer visuellen Sprachinstanz wird den einzelnen Sprachkonstrukten

durch eine Verhaltensbeschreibung eine Wirkung zugeordnet.

Der Fokus der Simulation, also die Frage, was simuliert und animiert werden

soll, wirkt sich auf das strukturelle Level der Sprache aus. Ein Beispiel ist die Simula-

tion eines Bubblesort-Sortieralgorithmus: Sollen die elementaren Tauschoperationen

innerhalb eines Arrays flüssig animiert werden oder stellt man den Kontrollfluss

3.1. STRUKTUR UND DATEN

mitsamt der aktuellen Variablenbelegung im Quellcode des Algorithmus dar?

Ersteres würde bedeuten: Man benötigt eine Struktur, die verschieden große

Datenelemente enthält, die wiederum visualisierbar sein müssen, z. B. als ver-

schieden große Rechtecke. Die Animation zeigt dann den Tauschvorgang zweier

benachbarter Elemente als weiche Animation. Die Programmbeschreibung hierfür

- der Quellcode - ist in diesem Fall nicht von Interesse. Einzige Bedingung ist, dass

auch wirklich Bubblesort implementiert wird.

Eine andere Sichtweise auf die Bubblesort-Simulation wäre die Code-orientierte:

Der Fokus liegt dabei auf der Hervorhebung einer entsprechenden Zeile des Pro-

grammcodes, der Bubblesort mit einer beliebigen Eingabe simuliert. Dies ähnelt der

Sichtweise eines Debuggers in einer imperativen Programmiersprache. In diesem

Fall würde die Struktur des Programms aus Sprachkonstrukten bestehen, die Pseu-

docodeelemente darstellen. Die einzelnen Pseudocode-Sprachkonstrukte könnten

entsprechend zu einem Programmtext zusammengestellt werden, der Bubblesort

beschreibt. Wenn den einzelnen Programmkonstrukten eine Ausführungssemantik

zugeordnet wird, könnte jedoch auch jedes andere beliebige Programm im Rahmen

der Pseudocodesprache konstruiert werden. Als Eingabe würde der Algorithmus

beispielsweise eine Reihe von Zahlen “konsumieren”. Abbildung 3.1 verdeutlicht

die Struktur- und Darstellungsunterschiede beider Varianten. Das Beispiel zeigt,

dass Struktur und Daten, je nach Anwendungsfall, sehr unterschiedlich sein können.

Liegt der Fokus auf den Tauschoperationen, die weich animiert werden sollen, so

kann die zu Grunde liegende Sprachstruktur sehr flach sein. Lediglich die Eingabe-

daten (die zu tauschenden Elemente) werden modelliert.

Bei der Algorithmenvisualisierung ist die Struktur größer und wesentlich tiefer.

Sprachkonstrukte haben eine eigene Ausführungssemantik, die vom Simulationss-

pezifizierer festgelegt wird. Der Benutzer kann diese selbst kombinieren und auf

eine Eingabe anwenden lassen. Die Eingabe wird zur Laufzeit, z. B. durch einen

modalen Dialog in die Simulationsstruktur geladen.

Die Simulation wird komplexer, wenn der Benutzer beliebige Sprachkonstrukte

(mit Ausführungssemantik) in einem visuellen Programm kombinieren kann und

diese dann auf einen anderen dedizierten Teilbaum angewendet werden, der als

Eingabe dient und den Programmzustand speichert. Als Beispiel ist hier eine

Verkehrssimulation zu nennen, bei der der Benutzer selbst innerhalb des Editors

Verkehrsregeln, wie “rechts vor links” definieren kann, die dann auf das Verkehrs-

geschehen angewendet werden. Das Verkehrsgeschehen stellt dann den aktuellen

Systemzustand dar. Hier müssen Strukturen und Daten in einem Teilbaum des

Programms erkannt werden. Dies entspricht in gewisser Weise einer recht auf-

wändigen Mustererkennung und wird in Programming-by-Demonstration-Systemen

wie Agentsheets [92] angewendet. In Agentsheets kann die Programmierung visuell

durch Vorher-/Nachher-Regeln erfolgen. Im Hintergrund arbeitet dann ein System

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

Abbildung 3.1: Ein Struktureditor zur Simulation des Quicksort-Algorithmus.

Links die datenorientierte Sicht. Eine Animation zeigt Vertau-

schungsoperationen zwischen Elementen. Rechts die codeorien-

tierte Variante, die den Fokus auf den Algorithmus legt. Beide

Ansichten sind in von DEViL generierten Editoren möglich.

zur Auswertung dieser Regeln. Der Simulator muss also nicht mehr von Hand

entworfen werden, da er auf das regelbasierte Kachelparadigma spezialisiert ist.

Wie weit Simulation und Animation strukturell voneinander entfernt sind, wirkt sich

ebenfalls auf das Spezifikationskalkül aus. In einigen Sprachen fallen Simulations-

und Animationsstruktur zusammen. Zustandsübergänge sind in der Sprache

definiert. Hier sind wieder Petri-Netze zu nennen, wobei das Programm aus den

Daten, repräsentiert durch Marken, zusammen mit der Struktur, d. h. den Stellen,

Transitionen und Verbindungen, modelliert wird. Eine Animation ist dann die

kontinuierliche Bewegung der Marken.

Betrachtet man nun eine Sprache, die Verkehrsampeln einer Kreuzung durch

ein gegebenes Petri-Netz simuliert, so möchte man evtl. in einem ersten Schritt

die Stellen des Petri-Netzes in den unterschiedlichen Farben der Verkehrsampel

färben. Dies ist eine rudimentäre Darstellung, die jedoch noch kein domänenspe-

zifisches Layout beinhaltet. Ein domänenspezifisches Layout wäre die Darstellung

der Kreuzung mit den Ampeln. Durch das bereits vorgestellte Kopplungskonzept

von DEViL (Seite 62) kann eine Struktur, die eine Verkehrsampel darstellt, an Teile

des Petri-Netzes gekoppelt werden. Markenbewegungen des Petri-Netzes führen

dann gleichzeitig zu einer Änderung der Ampel-Darstellung. Somit kann für die

Struktur einer visuellen Sprache mit Simulations- und Animationskomponente

gesagt werden:

3.2. ZUSTAND UND ZUSTANDSÜBERGÄNGE

Simulation und Animation fallen im einfachen Fall zusammen, in komplexen Fällen

können gekoppelte Strukturen eingesetzt werden.

Petri-Netze haben eine Modellierungseigenschaft, d. h. mit ihnen können an-

dere Systeme formal spezifiziert werden. Vorteilhaft ist hier, dass die Domäne sehr

eingeschränkt ist, da nur vier unterschiedliche Sprachkonstrukte benutzt werden

können. Problematisch wird es, wenn diese Einschränkung nicht mehr gilt, d. h.

wenn Sprachen mit allgemeinen Modellierungseigenschaften betrachtet werden, z. B.

Java. Allgemein bedeutet, dass jede beliebige Anwendung durch ein Programm

dieser Sprache ausgedrückt werden kann. Ein beliebiges Java-Programm (oder eine

andere GPL) und dessen Ausführung sind somit das andere Ende des Unterschiedes

zwischen Simulations- und Animationsstruktur. Die Darstellung, also der Java-

Quelltext, unterscheidet sich erheblich von dem ausgeführten Programm. Allerdings

ist Java auch keine domänenspezifische Sprache mehr und fällt somit auch nicht in

die Kategorie der Sprachen, die hier simuliert und animiert werden sollen.

Wie eine visuelle Sprache strukturell implementiert wird, liegt häufig auch an

den Vorlieben des Designers. Ein Unterschied liegt in der Regel darin, ob eher flache

oder tiefe Baumstrukturen bevorzugt werden. So kann etwa die Markenbelegung

eines Petri-Netzes als Attribut der Stelle modelliert werden oder als eigener Struk-

turknoten, der in der Stelle aggregiert enthalten ist. Die Simulation würde bei der

ersten Variante das Attribut der Stelle entsprechend in- oder dekrementieren. Bei der

zweiten Variante müsste das Sprachkonstrukt strukturell bewegt werden. Dies hat

direkte Konsequenzen für die Animation: Im ersten Fall muss ein Animationsobjekt

in Form einer Marke erstellt und bewegt werden, das keinem Sprachkonstrukt der

Simulationsstruktur zugeordnet ist. Im letzteren Fall stellt die Animation direkt die

Bewegung der Marke dar. Um dem Entwickler freie Wahl bei der Implementierung

zu lassen, sollten beide Fälle spezifizierbar sein und eine Animation sollte auch in

beiden Fällen gleich aussehen. Den ersten Fall, bei dem keine Sprachkonstrukte

bewegt werden, nenne ich im Folgenden attributorientiert, die Simulation für tiefe

Strukturen nenne ich strukturorientiert. Struktur- und attributorientierte Simulation

sind natürlich auch kombinierbar.

3.2 Zustand und Zustandsübergänge

Um ein Programm einer visuellen Sprache zu animieren, benötigt man einen Zu-

standsübergangsautomaten, der Zustände des Programms erkennt und Zustands-

übergänge auslöst. Dies ist nur möglich, wenn die Sprache eine wohldefinierte

Ausführungssemantik hat. Sie beschreibt, wie ein gegebener Programmzustand

in einen anderen überführt werden soll. Diese Transformation ist bei den meisten

Sprachen diskret, d. h. es gibt für einen Zustandsübergang nur zwei adjazente

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

Zustände, zwischen denen das Programm in einem diskreten Schritt überführt

wird. Die Animation zeigt dann eine Interpolation zwischen den beiden Zuständen

an. Während dieser Interpolation ist das Programm quasi in einem ungültigen

Zwischenzustand. In manchen Editoren (vgl. DiaMeta, Abschnitt 2.7.3 auf Seite

44) korrespondiert dieser Zustand jedoch auch mit dem Zustand des zu Grunde

liegenden Graphtransformationssystem. Ein Animationszustand ist dann auf eine

Graphinstanz abbildbar. Diese Systeme eignen sich dann nicht nur für diskrte

Simulationen, sondern auch für kontinuierlicher Modelle. In visuellen Sprachen

kommen solche kontinuierlichen Darstellungen vor allem bei der Positionierung

von Mengenelementen vor. So kann durch räumliche Nähe Beziehungen zwischen

verwandten Elementen ausgedrückt werden (sekundäre Notation).

Die obige Betrachtung zur Struktur visueller Sprachen zeigt, dass Zustände in-

nerhalb einer Sprache ganz unterschiedlich definiert sein können. Sie können Teil

der visuellen Sprache sein, in einem separaten Teilbaum gespeichert werden und

auch strukturell unterschiedlich komplexe Ausprägungen haben.

Sprachen, die dynamische Systeme modellieren, definieren den Zustand häufig

schon innerhalb des Programms selbst. Petri-Netze repräsentieren den Zustand

durch Marken. Pictorial Janus (vgl. Abschnitt 2.6.7 auf Seite 37) repräsentiert den

Zustand durch Listenelemente unterschiedlicher Länge und ein Aufblähen der

aktuellen Vorbedingung. Eine Spielesprache wie Pac-man1beschreibt den aktuellen

Spielzustand über die Position und Darstellung der einzelnen Spielfiguren. Zustände

sind hier häufig relativ einfache Sprachkonstrukte. Diese lassen sich gut darstellen

und haben eine eingeschränkte Bedeutung.

Eine Sprache wie UML-Statecharts modelliert ebenfalls dynamische Systeme,

sie definiert jedoch nur ihre Zustandsübergänge durch benannte Kanten. Der aktu-

elle Zustand kann einer Programminstanz nicht angesehen werden. Die so genannte

Zustandsnotation kann hier jedoch leicht nachgerüstet werden, indem jedem Knoten

des Statecharts ein Attribut zugeordnet wird, das angibt, ob der Knoten aktiv oder

inaktiv ist. Zustandsübergänge werden hier durch externe (Tastatur-)Ereignisse

geschaltet. Aus einer Programminstanz lässt sich also nicht unmittelbar der Folgezu-

stand wie bei Petri-Netzen oder Pictorial-Janus-Programmen berechnen. Hier kann

zunächst nur eine mögliche Menge von Folgezuständen angegeben werden. Der

Benutzer des Programms wählt aus dieser Menge dann direkt einen Folgezustand

aus. Eine andere Variante wäre, Zustandsübergänge nicht durch den Benutzer schal-

ten zu lassen, sondern durch eine nicht-deterministische Auswahl eines möglichen

Folgeereignisses.

Die Simulation einer visuellen Sprache kann entweder universell für alle Pro-

gramminstanzen oder modellspezifisch sein, d. h. nur eine Teilmenge aller möglichen

1Pac-man ist eingetragenes Warenzeichen der Firma Namco.

3.2. ZUSTAND UND ZUSTANDSÜBERGÄNGE

Programme der Sprache kann simuliert werden. Für den Zustandsübergangsauto-

maten bedeutet dies, dass im letzteren Fall nur Übergänge ausgelöst werden, wenn

eine ganz bestimmte Programminstanz erkannt wird. Eine Sprache mit universeller

dynamischer Semantik hingegen kann für jede Programminstanz den Folgezustand

bestimmen. In der Literatur wird dies auch als Interpreter Semantik beschrieben

(vgl. [31]). Sprachen mit nicht-universeller Semantik werden auch als Sprachen mit

Übersetzer Semantik bezeichnet. Auch hybride Sprachen sind durchaus anzutreffen.

Beispiele sind Ampelsteuerungen oder das “Dining-Philosophers”-Problem, welche

beide durch Petri-Netze modelliert werden können. Dazu kann ein Zustands-

übergangsautomat für universelle Petri-Netze benutzt werden, der durch einen

(Kopplungs-)Mechanismus Änderungen an der anwendungsspezifischen Sicht

beschreibt.

Die Komplexität von Zustandsübergängen kann sehr unterschiedlich sein. Im

einfachsten Fall sind Zustände im Programm repräsentiert und Zustandsübergänge

universell definiert. Dies reicht bei komplexen Simulationen nicht aus und Berech-

nungen müssen zwischengespeichert werden. Auch hier kann im einfachen Fall die

Simulationsstruktur durch das Einführen neuer persistenter Attribute angepasst

werden. Dies ist manchmal auch nötig um den globalen Programmzustand zu

speichern und Unterprogramme aufzurufen. In Graphtransformationssytemen

muss hier die Graphgrammatik künstlich erweitert werden um kaskadierende

Ersetzungsregeln aufzurufen.

Bei der Frage wer Zustandsübergänge beschreibt, handelt es sich also um den

Anwender oder den Entwerfer der Sprache, gibt es mehrere Varianten. Neben

universellen Zustandsübergängen können Zustandsübergangsdefinitionen sich

auch in die Progamminstanz selbst verlagern. Der Benutzer programmiert in diesem

Fall selbst Zustandsübergänge. Dazu benutzt er Konstrukte der Sprache, die eine be-

stimmte dynamische Semantik haben und setzt sie zu einem Programm zusammen.

Diese “höhere” Semantik ist wiederum durch den Sprachspezifizierer festgelegt

worden. Logo ist so eine Sprache, bei der imperative Anweisungssequenzen auf

ein spezielles Sprachkonstrukt (eine Schildkröte) angewendet werden. Dieses

Sprachkonstrukt stellt den Zustand durch Position und Rotationswinkel dar. Es

befindet sich in einem anderen Teilbaum des Programms der visuellen Sprache als

die Anweisungssequenzen.

Die Simulation wird umso komplexer, je aufwändiger die Semantik der Regeln ist.

Sind diese tief strukturiert und müssen sie auf eine Reihe anderer Sprachkonstrukte

angewendet werden, so steigen die Anforderungen an die Simulationssprache.

Wie Zustandsübergänge ausgelöst werden, ist ein weiteres Unterscheidungsmerk-

mal. Für Sprachen mit universeller Ausführungssemantik kann der Folgezustand in

der Regel ohne weiteres ermittelt werden. Nicht-Determinismus kann hier allerdings

auch entstehen. Eine Methode diesen aufzulösen besteht darin, den Anwender zu

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

fragen. Bei Petri-Netzen kann dies passieren, wenn zwei Transitionen gleichzeitig

schalten können. Dem Anwender wird dann ein modaler Auswahldialog angezeigt.

Modal bedeutet hier, dass der Zustandsübergangsautomat zwingend eine Eingabe

benötigt um weiter arbeiten zu können.

In anderen Fällen lösen Tastaturereignisse einen Zustandsübergang aus, z. B.

durch die Betätigung einer Taste um in einem Statechart den nächsten Zustand zu

aktivieren. Nicht modale Ereignisse werden somit auch nicht zwingend für eine

laufende Simulation benötigt. Die Steuerung des Pac-man durch den Anwender ist

z. B. so ein nicht-modales Ereignis. Ohne dieses läuft die Simulation trotzdem ab, die

anderen Spielfiguren werden durch den Computer bewegt.

Ein Benutzerereignis kann andere Ereignisse verdrängen, evtl. weil eine Be-

rechnung nicht mehr gültig ist oder aufgrund anderer Effekte nicht mehr ausgeführt

werden kann. Anzumerken ist, dass Zustände als Daten in der Sprache oder als

Eingabedaten durch den Benutzer definiert werden können.

3.3 Repräsentation

Die graphische Notation des Zustands ist neben wohldefinierten Zustandsübergän-

gen nötig, um eine geeignete Animation zu finden. Die graphische Notation drückt

den aktuellen Systemzustand visuell in der Sprache aus. Sprachen mit universell

definierten Zustandsübergängen haben diesen meist bereits integriert. Aber auch

bei Sprachen, die den Zustand nicht von Haus aus graphisch ausdrücken können,

kann dies nachgerüstet werden. Dies liegt dabei häufig in der Kreativität des Ani-

mationsentwerfers. Aktive Zustände in Statecharts können so beispielsweise durch

ein grüne Hintergrundfarbe dargestellt werden. Aber auch andere Repräsentationen

sind hier denkbar, z. B. durch Pfeile, die auf den aktiven Zustand hindeuten.

Simulation und zugehörige Animation einer visuellen Sprache können auch

eine völlig andere Darstellung haben. In Petri-Netzen kann dies die bekannte

Markensimulation sein, aber auch ein domänenspezifische Layout ist denkbar. Dies

könnte wie beim Produzent/Konsument Beispiel eine Mutter (Produzent) sein, die

für ihr Kind (Konsument) einen Kuchen (Marke) backt.

In Generatorsystemen wie AToM3(vgl. Abschnitt 2.7.5 auf Seite 48) werden

beide Layoutvarianten in einem Objekt-Repository zu einer verallgemeinerten

Sprache vereint und darauf simuliert. In GenGed (vgl. Abschnitt 2.7.2 auf Seite

43) wird eine zusätzliche Transformationsgrammatik angegeben, die aus einer

Instanz des Petri-Netzes ein konkretes DSL-Layout erstellt. Auf diesem können

dann Simulationsregeln definiert werden. In DEViL leistet dies auch wieder das

Kopplungskonzept. Diese Distanz zwischen visueller Sprache und Simulation

3.4. KLASSIFIKATION VISUELLER SPRACHEN

bzw. Animation kann jedoch noch größer sein. Beispiele hierfür sind strukturierter

Programmtext, der in ein beliebiges ausführbares Programm übersetzt wird oder

auch eine regelbasierte Spielesprache, die als visuelles Konstrukt nur eine Reihe von

Vorher-/Nachher-Regeln kennt und diese dann auf die Zustandsrepräsentation, ein

konkretes Spielfeld mitsamt Spielfiguren, anwendet.

Um die Distanz zwischen Programm und Programmausführung zu verringern

setzen manche Animationsdesigner auch hinweisende Animationen ein, die sich

nicht direkt auf die aktuelle Simulationssituation zurückführen lassen aber aus ihr

abgeleitet werden können. Einfache Varianten davon sind schlichte Hinweistexte,

die in einem Nachrichtenfenster erscheinen oder auch direkt in die Zeichenfläche

der Animation eingebunden werden können. Anspruchsvoller sind kleine Sub-

Animationen, wie sie in einem Editor vorstellbar wären, der den Datenpfad einer

CPU simuliert: Hier werden Datenimpulse durch einen kleinen Ball dargestellt, der

entlang einer Verbindung läuft. Das Besondere ist, dass diese Animation keinen

Repräsentanten in der Struktur hat, d. h. alle Animationen wurden bisher durch

das Verändern von Strukturobjekten, z. B. einer Bewegung, ausgelöst. Diese Verbin-

dung ist bei solchen hinweisenden oder analytisch aus der Simulation berechneten

Animation nicht mehr der Fall. Ein anderes Anwendungsszenario sind die bereits

vorgestellten Effect-Lines, die Geschwindigkeit für sich bewegende Objekte verdeut-

lichen. Auch hier haben die einzelnen Linien keinen Strukturrepräsentanten.

Häufig basiert die Repräsentation einer Animation auch auf dem Kontext, in

dem ihr zugehöriges Sprachkonstrukt eingebettet ist. Je nachdem wo sich ein Struk-

turobjekt innerhalb des Modells befindet, wird eine unterschiedliche Animation

ausgelöst. Hier muss die Animation auf Daten des Modells zurückgreifen.

3.4 Klassifikation visueller Sprachen

Aus den obigen Überlegungen lassen sich Typen von visuellen Sprachen ableiten

und eine Aussage darüber treffen, ob und wie sie simulier- bzw. animierbar sind.

Im Folgenden werde ich eine Klassifizierung vorstellen und diese anhand konkre-

ter Sprachen verdeutlichen. Durch diese Einordnung kann für andere Sprachen

abgeschätzt werden, wie hoch der Aufwand einer zusätzlichen Simulation und

Animation ist.

Generell kann gesagt werden, dass Sprachen, die simuliert und animiert wer-

den sollen, Folgendes benötigen: eine Notation des Zustands, die zum einen nötig

ist um den Zustand graphisch zu repräsentieren und zum anderen um den Folge-

zustand zu beschreiben. Entweder ist diese Zustandsnotation bereits vorhanden,

wie bei Petri-Netzen durch die Markenbelegung oder die Zustandsnotation ist

integrierbar durch zusätzliche graphische Elemente, wie bei Statecharts (Aktivität

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

eines Zustands wird repräsentiert durch die Hintergrundfarbe) bzw. durch neue

Strukturen, wie beim Logo Interpreter (durch Hinzufügen einer Cursor-Struktur).

Des Weiteren werden wohldefinierte Regeln für Zustandsübergänge gebraucht.

Diese sind entweder universell wie bei Petri-Netzen und Statecharts oder sie können

durch den Benutzer durch die Definition von Regeln in der Sprache festgelegt

werden (z. B. Logo-Anweisungssequenzen).

Insgesamt lassen sich durch die vorangegangenen Betrachtungen eine Klassifi-

kation von Sprachen hinsichtlich ihrer Simulier- und Animierbarkeit erstellen. Die

Einordnung sagt aus, wie weit sich Animation von der Simulation unterscheiden

und welche Methodik angewendet werden muss, um eine anspruchsvolle Animation

zu erstellen. Man kann folgende Kategorien unterscheiden:

1. Sprachen, die den Programmzustand inhärent definieren und beispielsweise

universelle Zustandsübergänge haben, sowie zusätzlich bereits eine graphische

Notation ihres Zustands mitbringen. Hier ist keine Erweiterung von Sprach-

oder Simulationsstruktur notwendig.

2. Sprachen bei denen die Simulationsstruktur erweitert werden muss um Daten

zwischenzuspeichern oder den Programmzustand zu merken sowie Sprachen,

die eine Erweiterung der editierbaren Struktur benötigen um die graphische

Notation des Zustands darzustellen.

3. Sprachen, bei denen eine erhebliche Distanz zwischen Simulations- und Ani-

mationsstruktur vorhanden ist. Die Animationsstruktur ist dabei mittels Struk-

turkopplung an die semantische Struktur gebunden sein. Die Animation kann

hier in der Regel fast automatisch mit dem Strukturkopplungsprinzip hergelei-

tet werden.

4. Sprachen, deren Ausführungssemantik innerhalb der Sprache selbst definiert

ist. Der Sprachanwender kann hier selbst ein Programm aus Konstrukten zu-

sammenstellen, die Semantik tragen, häufig sind dies visuelle Regeln. Diese

können entweder mit der Animationsstruktur zusammenfallen oder in einem

anderen Teilbaum beheimatet sein.

5. Sprachen, die sich nicht simulieren bzw. animieren lassen, da Programm-

und Programmausführung dieselbe Darstellung haben. Die Sprache definiert

hier keine Zustandsübergänge. Außerdem gehören hierzu Sprachen bei denen

Programm- und Programmausführung eine erhebliche Distanz haben, die nicht

oder nur mit erheblichen Aufwand überbrückt werden kann.

Die erste Kategorie sind Sprachen mit universellen Zustandsübergängen, die gra-

phische Notation ist ebenfalls integriert. Die Simulationsstruktur fällt hier mit der

semantischen Struktur zusammen. Charakteristisch ist, dass Strukturobjekte durch

die Simulationsstruktur “wandern”. Mit Hilfe von Zufallsvariablen lassen sich so

auch Warteschlangensimulationen einfach entwickeln. Für die visuelle Sprache ist

eine Animation unmittelbar ersichtlich, so definieren Petri-Netze den Markenflug.

3.4. KLASSIFIKATION VISUELLER SPRACHEN

Die Simulation elektronischer Schaltkreise benutzt “fliegende Einsen” als Metapher

um Stromfluss zu verdeutlichen. Die Animation kann selbstverständlich noch

erweitert werden. So blinken die schaltenden Transitionen im hier entwickelten

Editor für Petri-Netze. Für die Analyse ist die Animation in solchen Sprachen

das primäre Mittel. Trotzdem sind auch Untersuchungen denkbar, die sich nicht

direkt aus der Sprache ergeben und erst durch eine mehrmalige und zufallsbasierte

Ausführung der Simulation ergeben. In der Waschstraßensimulation ist dies ein

Auslastungsgraph der Warteschlange bzw. die durchschnittliche Wartezeit eines

Autos wiedergibt. Mit der später vorgestellten Analysekomponente lässt sich dies

leicht und fast automatisch realisieren. Abbildung 3.2 zeigt drei generierte Struktur-

editoren dieser Kategorie.

a) b)

Abbildung 3.2: Beispiele visueller Sprachen der ersten Kategorie. Eine zufallsba-

sierte Waschstraße (a), Petri-Netze (b) und ein Editor zum Mo-

dellieren elektronischer Schaltkreise (c)

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

In der zweiten Kategorie können Zustandsübergänge nicht allein aus dem semanti-

schen Sprachmodell berechnet werden. Es werden zusätzliche Attribute benötigt,

die den Programmzustand zwischenspeichern. In der Quicksort-Implementierung

sind dies die Zeiger auf die linke bzw. rechte Grenze sowie ein Zeiger auf das

Pivotelement. Werden erweiterte Attribute nicht nur für die Simulation benötigt,

sondern auch um die graphische Zustandsdarstellung zu berechnen, so können

diese Attribute in die editierbare Struktur gezogen werden. Dies ist der Fall bei der

Simulation des Statecharts. Die Aktivität/Inaktivität eines Zustands wird durch

ein Boole’sches Attribut in der Simulationsstruktur ausgedrückt. Da aus diesem

Attribut jedoch noch die Hintergrundfarbe berechnet wird, kann es in die editierbare

Struktur gezogen werden.

In dieser Kategorie liegen Sprachen, die zur Simulation zusätzlich Benutzer-

interaktion verwenden. Entweder modal oder kontinuierlich. Im generierten

Pac-man Editor wird eine kontinuierliche Interaktion genutzt um den Pac-man

zu steuern. Der Computer bewegt die restlichen Spielfiguren. Ähnlich verhält es

sich bei der Implementierung des “Mensch-ärgere-Dich-nicht”-Editors, der halbau-

tomatisch abläuft. Der Computer steuert drei Spielfiguren, die vierte wird durch

den Anwender bewegt. Dieser wählt, falls mehrere Figuren ziehen können, eine

mögliche Spielfigur aus. Der Statechart-Editor erwartet explizit Tastatureingaben

um Zustandsübergänge zu triggern. Somit muss die Eingabe als Teil der Daten einer

Simulation betrachtet werden. Gegebenenfalls müssen Eingabedaten entsprechend

transformiert werden, bevor sie verarbeitet werden können.

Da in diese Kategorie Sprachen mit komplexerer Simulation fallen, ist auch die

Animation anspruchsvoller. Die Animation des Pac-man kann verbessert werden,

indem er sich bei einer Richtungsänderung vor der Bewegung entsprechend dreht.

Für Statecharts sind hier die Farbübergänge zu nennen, eine Startfarbe wird lang-

sam in eine Zielfarbe überführt (siehe auch Abb. 3.3 rechts). Dies hat den Sinn,

auf einen sich sonst sehr schnell auswirkenden Zustandsübergang hinzudeuten.

Ebenfalls hinweisend wirken sich zusätzliche Animationen aus. In der Quicksort-

Implementierung deuten Pfeile auf Pivotelement und Grenzen hin. In der Pac-man

Animation wird ein sich bewegender Totenkopf angezeigt, wenn der Pac-man

gefangen wird. Diese Animationstypen haben keinen Repräsentanten in editierbarer

oder Simulationsstruktur, lassen sich aber ähnlich wie die anderen Animationen

spezifizieren und nutzen.

Die dritte Kategorie der Klassifizierung bilden Sprachen mit erheblicher Struk-

turdifferenz zwischen Simulation und Animation. In dieser Kategorie liegen

Sprachen, die eine Modellierungseigenschaft besitzen: d. h. mit ihnen lässt sich die

Semantik anderer komplexer Systeme beschreiben. Es ist also schon implizit klar,

dass auch ein anwendungsspezifisches Layout möglich ist. Beispiel ist auch hier

wieder das Petri-Netz, mit dem sich Ampelsteuerungen oder das bekannte “Dining-

Philosophers”-Problem modellieren lassen (Abb. 3.5). Interessant ist hier, dass die

3.4. KLASSIFIKATION VISUELLER SPRACHEN

Abbildung 3.3: Beispiele visueller Sprachen der zweiten Kategorie. Links im Bild

ein Pac-man Editor. Der Pac-man wurde gerade von einem ro-

ten Geist gefangen. Als dynamisches Animationsobjekt wird ein

sich bewegender Totenkopf angezeigt. Das rechte Bild zeigt die

Simulation eines Statecharts. Das Diagramm befindet sich gera-

de im Zustandsübergang von anach c. Die Hintergrundfarbe

von Zustand awird langsam wieder weiß (inaktiv), Zustand c

wird langsam grün (aktiv)

Sprache universelle Zustandsübergänge definiert. An ein konkretes Programm lässt

sich dann eine anwendungsspezifische Sicht koppeln. Zustandsübergänge in der

Basisstruktur triggern dann Änderungen in der gekoppelten Struktur. Diese lassen

sich wiederum durch Animationen geeignet visualisieren. Die Animation kann mit

DEViLs Strukturkopplungsprinzip automatisch hergeleitet werden.

Die vierte Kategorie bilden Sprachen, die es erlauben die dynamische Semantik

als Teil des Programms zu definieren. Der Benutzer kann Sprachelemente mit

Ausführungssemantik auswählen und zusammenstellen um selbst ablaufende

Programme definieren. Ein schönes Beispiel ist die Lernsprache Logo [65] mit der

durch imperative Anweisungen ein graphischer Cursor (meist in der Form einer

Schildkröte) bewegt werden kann. Die Anweisungen in Form von Kommandos

wie VORWÄRTS 100, RECHTS 90, ... ändern die Position und den Rotationszu-

stand des Cursors. In der Sprache lassen sich keine Zuweisungen oder Variablen

definieren. Die Anweisungen selbst sind Sprachkonstrukte, die in der Simulations-

spezifikation eine hinterlegte dynamische Semantik haben.

Simulations- und Animationsstruktur können in zwei verschiedenen Teilbäu-

men beheimatet sein. Die Semantik der Sprachkonstrukte wird gewissermaßen

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

interpretiert und auf ein dediziertes Sprachkonstrukt angewendet. Einen Sonderfall

in dieser Kategorie bildet Pictorial Janus: Animations- und Simulationsstruktur

fallen zusammen. Regeln, mit denen PJ-Programme erstellt werden können, werden

quasi auf sich selbst angewendet. Erschwerend kommt in Pictorial Janus noch die

Selbstähnlichkeit hinzu. Subkonfigurationen sind innerhalb einer Regel prinzipiell

beliebig tief enthalten, werden jedoch nur bis zu einer gewissen Tiefe visualisiert.

Interessant in dieser Kategorie ist der CPU-Datenpfad Editor (inspiriert durch

[34]). Hier wandern Instruktionen durch das Simulationsmodell und je nach Position

werden unterschiedliche Ereignisse ausgelöst. So bewirkt eine Additionsinstruktion

im Decoder etwas anderes als in der arithmetischen Einheit. Dies führt später zum

Konzept der kontext-sensitiven Funktionen.

Komplizierter zu behandeln sind Sprachen, bei denen die für die Simulation

wichtigen und Semantik tragenden Sprachkonstrukte nicht nur auf ein einzelnes

dediziertes Sprachelement angewandt werden und dessen Zustand verändern,

sondern wenn beliebig viele dieser Elemente existieren. Dann müssen in einem

Teilmodell Sprachkonstrukte, die bestimmte Eigenschaften aufweisen, z. B. sich in

einer ganz speziellen Umgebung befinden, identifiziert werden. Diese Mustererken-

nung ist aufwändig und nicht leicht abzubilden. Systeme wie Agentsheets, die sich

auf diese Domäne spezialisiert haben, sind hier klar im Vorteil. Sie haben jedoch den

Nachteil, keine anderen Systeme außer kachelbasierten simulieren zu können.

Für die Simulationssprache ergibt sich hieraus die Konsequenz, Mechanismen

einzubauen um Sprachkonstrukte mit spezifischen Eigenschaften, wie Attributbe-

legungen oder Kontext, zu identifizieren. Die in DEViL integrierten Pfadausdrücke

arbeiten hier eher strukturell. Deswegen wurde zusätzlich ein XPath-Auswerter

[129] integriert um auch komplexere Muster und konkrete Wertbelegungen zu

erkennen.

Für die Animation lassen sich in dieser Kategorie einige interessante Beobach-

tungen machen. In der Logo-Animation fallen die Spurlinien auf, die die Schildkröte

während der Bewegung hinterlässt. Diese sind nicht flüchtig, sondern überdauern

die Simulationsschritte. Vergleichbar ist dies mit den bereits erwähnten Effect-Lines

zur Darstellung von Geschwindigkeit in Comic-Animationen. Sie werden nicht,

wie der Ball, der Datenimpulse in der CPU-Simulation repräsentiert, bewegt oder

rotiert, sondern statisch auf die Zeichenfläche gelegt. In dieselbe Kategorie fallen

hinweisende Texte, die die aktuell ausgeführte Instruktion textuell anzeigen, jedoch

nur ein oder zwei Simulationsschritte überdauern.

In der Animation des Datenpfad-Editors sind Bewegungen entlang von Weg-

punkten wichtig, in diesem Fall Linien, die Verbindungen repräsentieren. Auch in

der Verkehrssimulation wird erst durch eine korrekte Bewegung der Autos eine

anspruchsvolle Animation erreicht. Dies wird erschwert, da die Bewegung eines

3.4. KLASSIFIKATION VISUELLER SPRACHEN

Abbildung 3.4: Beispiele visueller Sprachen der dritten Kategorie, die Gebrauch

von Strukturkopplung machen. Die anwendungsspezifischen

Sichten (Ampel- bzw. Dining-Philosophers-View) sind an das

Petri-Netz gekoppelt. Änderungen in der Basisstruktur leiten

Animationen in der gekoppelten Struktur ein.

Autos in jedem Simulationsschritt in so genannte Mikroschritte unterteilt wird.

Dies ist notwendig um ein realistisches Verhalten der Autos zu simulieren, das dem

Nagel-Schreckenberg Modell [20] nachempfunden ist. Innerhalb eines Mikroschrittes

kann ein Auto nacheinander auf mehrere Straßenkacheln bewegt werden. Dies hat

zur Folge, dass vor und nach einem Simulationsschritt nur Start- und Endposition

eines Autos bekannt sind. Wurde das Auto während eines Simulationsschrittes über

eine Kurve bewegt, so soll nicht der direkte Weg in der Animation benutzt werden,

sondern das Auto soll sich realistisch am Straßenverlauf orientieren und sich auch

entsprechend in Kurven zur Fahrtrichtung drehen. Hier zeigt sich, dass zwischen

Simulation und Animation eine Informationslücke klafft. Besonders deutlich wird

dies bei Petri-Netzen, wobei eine Marke in der Nachbedingung erstellt wird, aber

zwei unterschiedliche Transitionen hätten schalten können. In der Simulation kann

dies nicht ohne Änderungen (dem Zwischenspeichern der schaltenden Transition)

ausgedrückt werden. Somit fehlen der Animation Informationen. Der Animations-

komponente müssen also Mechanismen bereitgestellt werden um auch diese Fälle

abzudecken, ohne dabei die Simulationsspezifikation ändern zu müssen.

In der Datenpfad-Animation fällt außerdem auf, dass der Ball, der die Daten-

impulse repräsentiert, an unterschiedlichen Stellen eines Sprachkonstrukts andockt.

Dadurch, dass DEViL syntax-basierte Struktureditoren generiert, ist die Ausdehnung

eines Sprachkonstrukts nur zur Laufzeit zu ermitteln. Um trotzdem komfortabel

Positionen innerhalb eines Sprachkonstrukts angeben zu können (z. B. der out1-

Ausgang des RAM), wurde das Konzept der graphischen Anknüpfungspunkte mittels

so genannter Crosslines entwickelt. In Abbildung 3.5 sind im Datenpfad-Editor

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

Statische Animationsobjekte Dynamisches Animationsobjekt Verschiedene graph. Anknüpfungs-

punkte

Abbildung 3.5: Beispiele visueller Sprachen der vierten Kategorie. Links im Bild

der Logo-Editor, rechts der Datenpfad-Editor. Zu sehen ist der

Unterschied zwischen statischen und dynamischen Animations-

objekten. Statische überdauern Simulationsschritte und werden

nicht bewegt. Dynamische Animationsobjekte werden nur in-

nerhalb einer Animationssequenz benutzt.

zwei solcher Anknüpfungspunkte zu sehen. Im Editor für generische Zeichnungen

können bestimmte benannte Stellen eines Sprachkonstrukts markiert werden, die

dann zur Laufzeit in absolute Positionen umgerechnet werden und referenziert

werden können.

In die fünfte Kategorie fallen Sprachen, wie z. B. der DEViL-Menü-Designer. Mit

ihm lassen sich visuell Menüstrukturen entwerfen, wie sie sich auch später in von

DEViL generierten Editoren finden. Programm- und Programmausführung haben

dieselbe Darstellung. Das andere Ende des Spektrums von Sprachen dieser Kategorie

bilden VLs wie PaderWAVE [105]. Mit PaderWAVE lassen sich dynamische Websei-

ten visuell modellieren. Dabei werden neben den Verlinkungen und der visuellen

Definition statischer Webseiten auch Skripte und Datenbankabfragen modelliert.

Aus einer visuellen Spezifikation werden PHP-Skripte und HTML-Code generiert,

die zusammen auf einem Webserver ausgeführt werden können. PaderWAVE

als VL definiert selbst keine Ausführungssemantik innerhalb der Sprache. Der

generierte Code, der auf dem Webserver ausgeführt wird, erhält seine Daten durch

den Benutzer, der Aktionen auf der Webseite ausführt. Die Ausführung ist durch

quasi beliebige PHP-Skripte sehr komplex und auch nicht in der Sprache definiert.

Eine simulierte Variante von PaderWAVE könnte also höchstens darin bestehen,

Callback-Methoden in den generierten PHP-Code zu integrieren, die ausgeführt

werden, wenn die Webseite besucht wird und bestimmte Animationsaktionen im

3.4. KLASSIFIKATION VISUELLER SPRACHEN

Abbildung 3.6: Klassifikation visueller Sprachen und Einordnung der Beispiel-

implementierungen.

generierten Editor triggern. Diesen indirekten Ansatz verfolgt MetaEdit+ (vgl.

Abschnitt 2.7.1 auf Seite 41). Er soll hier aber nicht Teil der Betrachtung sein. Eine

simulierte PaderWAVE-Variante erscheint im Übrigen aber auch nicht besonders

sinnvoll.

Abbildung 3.6 zeigt einen Überblick auf die Sprachklassen und eine Einordnung

der Beispielimplementierungen. Die X-Achse repräsentiert das Simulationsniveau.

Es unterscheidet sich von Stufe zu Stufe vom semantischen Modell der Sprache.

Ab Stufe drei ist die Simulationssemantik Teil der visuellen Sprache. Hier ist ein

deutlicher Komplexitätssprung in der Realisierung zu verzeichnen. Sprachen mit

externem Zustandsautomaten oder Sprachen ohne dynamische Semantik (links der

Y-Achse) sind nicht simulierbar.

Auf der Y-Achse ist das Animationsniveau abgebildet. Es gibt an, wie weit

sich Animations- von Simulationsstruktur unterscheiden. Hier ist anzumerken, dass

ein höheres Animationsniveau nicht zwingend mit einer schwierigeren Spezifikation

einhergeht. Sprachen auf der höchsten Ebene zeichnen sich hier durch Strukturkopp-

lung aus. Hieraus lassen sich wiederum automatisch Animationen ableiten. Dies

ist recht einfach in DEViL zu realisieren. Innerhalb einer Sprachklasse gibt es keine

Rangordnung zwischen den einzelnen Sprachen. Der Schwierigkeitsgrad ist hier

nur schwer abzuschätzen. Ich habe dennoch versucht dem Spezifikationsaufwand

der einzelnen Sprachen gerecht zu werden. So ergibt sich beispielsweise für die

KAPITEL 3. SIMULIER- UND ANIMIERBARKEIT VISUELLER SPRACHEN

Pac-man-Implementierung ein erhöhter Spezifikationsaufwand für die Animation

als für die der Statecharts, da noch dynamische Animationsobjekte eingesetzt

werden. Trotzdem lässt sich auch dies recht einfach realisieren, wie die Evaluation

zeigen wird.

4 Simulationskonzept

Inhalt

4.1 DerSimulator ............................... 88

4.1.1 Der erweiterte Spezifikationsprozess . . . . . . . . . . . . . . . . 88

4.1.2 Anforderungen an den generierten Simulator . . . . . . . . . . 90

4.1.3 Einbettung des Simulators in die Werkzeugkette . . . . . . . . . 92

4.1.4 Zeitliches Verhalten des Simulators . . . . . . . . . . . . . . . . 93

4.2 Entwurf der Simulationssprache . . . . . . . . . . . . . . . . . . . . 96

4.2.1 Imperativ vs. regelbasiert . . . . . . . . . . . . . . . . . . . . . . 99

4.3 Die Simulationsspezifikationssprache DSIM . . . . . . . . . . . . . 99

4.3.1 Spezifikation der Simulationsstruktur . . . . . . . . . . . . . . . 100

4.3.2 Spezifikation des Simulationsverhaltens . . . . . . . . . . . . . . 102

4.3.3 Spezifikation von Ereignissen . . . . . . . . . . . . . . . . . . . . 104

4.3.4 Spezielle Funktionalitäten . . . . . . . . . . . . . . . . . . . . . . 106

4.3.5 Textuell vs. visuell . . . . . . . . . . . . . . . . . . . . . . . . . . 110

4.4 VerwandteArbeiten............................ 111

KAPITEL 4. SIMULATIONSKONZEPT

In diesem Kapitel soll das hier entworfene Simulationskonzept vorgestellt werden.

Es bildet die Grundlage für die Animation. Dazu beschreibe ich zunächst den aus

einer Spezifikation generierten Simulator; die Anforderungen, die an den Simulator

gestellt werden und dessen Einbettung in das Gesamtsystem. Im Anschluss werden

Anforderungen zur entworfenen Simulationsspezifikationssprache DSIM diskutiert

und diese dann an ausgewählten Beispielen vorgestellt.

4.1 Der Simulator

Im Rahmen dieser Arbeit wird die Simulation als Hilfsmittel zur Animation visueller

Sprachen betrachtet. Die Begriffe Simulator bzw. Simulation habe ich gewählt, da

die Ausführung visueller Sprachen analysiert werden soll. Durch das gewählte

ereignisbasierte Simulationskonzept lassen sich sehr einfach Sprachen entwerfen und

untersuchen, die auf stochastischen Modellen basieren. Das Konzept der Ereignisse

und der Ereigniswarteschlage wird in der Literatur immer in Zusammenhang mit

Simulatoren gebracht (vgl. Abschnitt 2.5). Generatorsysteme, wie GenGed oder

DiaMeta, führen ebenfalls den Begriff der Simulation in Zusammenhang mit der

Ausführung von VLs ein. Den Simulator betrachte ich in meiner Arbeit als einen

Automat, der den Simulationsablauf koordiniert. Er arbeitet dabei nicht auf einer

Zwischensprache, wie z.B. eine virtuelle Maschine, sondern modifiziert direkt eine

Instanz der Simulationsstruktur.

Der entworfene Simulator soll nicht als Simulator im herkömmlichen Sinne be-

trachtet werden, der in der Regel für Fertigungssysteme oder rechenintensive

Simulationen gedacht ist. Deshalb soll er auch nicht mit einem existierenden Simu-

lator direkt verglichen werden, da die Ansätze verschieden sind.

Es sollen die in Kapitel 3 untersuchten Sprachen der Kategorien eins bis vier der

Klassifikation simuliert werden. Neben der reinen Simulation wird der Simulator

eine Analysekomponente enthalten, sodass eine Auswertung auch von komplexen

Simulationen unterstützt wird. Weitere Eigenschaften werden in den folgenden

Abschnitten diskutiert.

Zunächst soll auf den nun erweiterten allgemeinen Spezifikationsprozess für

Struktureditoren in DEViL eingegangen werden.

4.1.1 Der erweiterte Spezifikationsprozess

Die Simulations- und Animationsspezifikation erweitert das allgemeine DEViL Spe-

zifikationskonzept um einen weiteren Zweig, wie in Abbildung 4.1 zu sehen ist. Die

Simulationskomponente wird dabei nur optional in die generierten Umgebungen in-

tegriert - und auch nur, falls eine Simulationsspezifikation vorhanden ist. Somit kann

4.1. DER SIMULATOR

1Spezifikation der

abstrakten Struktur

2b Spezifikation der

Codegenerierung

3Generierte

Umgebung

DEViL

Spezifikation

visueller Sichten

move

grow

shrink

2c Spezifikation der

Simulationsstruktur

2d Spezifikation der

Animationsmuster

Abbildung 4.1: Erweiterung des DEViL Spezifikationsprozesses

erreicht werden, dass bereits vorhandene Spezifikationen ohne Simulationsunterstüt-

zung nicht durch Seiteneffekte beschädigt werden. Ebenso ist zu sehen, dass eine Si-

mulationsspezifikation nicht auf vorhandenen Spezifikationen aufbaut. So ist es auch

denkbar, ausschließlich einen Struktureditor mit Simulationsunterstützung zu gene-

rieren und erst später die graphische Repräsentation hinzuzufügen. Somit können

Simulationsspezifikationen auf DSSL aufbauen, müssen dies aber nicht. Wie später

noch zu sehen ist, wird aus einer Simulationsspezifikation automatisch eine Anima-

tionsstruktur generiert, die standardisierte Animationen aus Grundoperationen der

Simulation generiert. Diese Animationen können vom Spezifizierer noch flexibel an-

gepasst werden (Schritt 2d).

In der generierten Umgebung wird durch eine Simulationsspezifikation ein ereignis-

basierter Simulator integriert, der auf einer eigenen Simulationsstruktur arbeitet. Die

Wahl des ereignisbasierten Konzeptes ist aufgrund der Verbreitung bei den Simula-

KAPITEL 4. SIMULATIONSKONZEPT

tionssprachen und der Flexibilität der ereignisorientierten Simulation gefallen, wie

sich bei der Untersuchung anderer Werkzeuge herausgestellt hat (vgl. Abschnitt 2.5).

4.1.2 Anforderungen an den generierten Simulator

Bevor die Spezifikationsmethoden der Simulation für visuelle Sprachen erläutert

werden, wird an dieser Stelle zunächst der Fokus auf den aus der Spezifikation

generierten Simulator gelegt.

Vorweg sei erwähnt, dass der hier generierte Simulator auf die Anforderungen

visueller Sprachen maßgeschneidert ist. Er soll nicht in Konkurrenz zu Simulatoren

stehen, die komplexe wissenschaftliche Aufgaben lösen, wie z. B. die Simulation

des Klimas und dazu Aufgaben auf einen Rechnercluster verteilen. Vielmehr soll

der generierte Simulator sich nahtlos in das DEViL-System einpassen. Trotzdem soll

er korrekte Ergebnisse liefern und Mechanismen anbieten, die auch in etablierten

Simulatoren bereitgestellt werden. Dazu gehört unter anderem die Generierung von

Zufallszahlen bestimmter Wahrscheinlichkeitsverteilungen.1

Die konkreten Anforderungen an den Simulator sind:

1. Arbeit auf einer eigenen maßgeschneiderten Simulationsstruktur.

2. Entkopplung vom semantischen Modell der visuellen Sprache.

3. Abbildung des vollständigen semantischen Modells auf eine geeignete Simula-

tionsstruktur.

4. Realisierung von langlaufenden Simulationen.

5. Spezielle Anforderungen: Zufallszahlen, Pfadausdrücke, Mustererkennung

und kontext-sensitive Funktionen.

6. Anpassung an den LIGA Attributauswertergenerator.

7. Analysefähigkeiten.

8. Erweiterbarkeit.

9. Schmale Schnittstelle zur Animation durch standardisierte Änderungsoper-

ationen.

10. Flexibilität bei der Bedienung.

Die Arbeit auf einer eigenen Simulationsstruktur verdeutlicht eines der wichtigsten

Ziele bei der Gestaltung von Modellen für die Simulation. Die Simulationsstruktur

muss in ihrer Komplexität möglichst minimal sein, um keine unnötigen oder

langwierigen Berechnungen zu provozieren, die nicht der Problemlösung dienen.

Trotzdem müssen geeignete Schnittstellen enthalten sein, die es erlauben, die Simu-

lationsstruktur zu attributieren um neue Eigenschaften hinzufügen zu können. Des

1Intern werden die Zufallszahlengeneratoren der etablierten Boost C++ Bibliothek verwendet [26].

4.1. DER SIMULATOR

Weiteren muss es die Simulationsstruktur ermöglichen, einfach auf Strukturobjekte

mit bestimmten Eigenschaften zugreifen zu können. Außerdem muss es möglich

sein, Strukturobjekte im Baum zu verschieben. Dies geschieht im Hinblick auf trans-

portorientierte Simulationen, bei denen Simulationsobjekte im Modell “wandern”.

Die vollständige Entkopplung des Simulators und der Simulationsstruktur vom

semantischen Modell der Sprache bedeutet, dass bestehende Spezifikationen nicht

beeinflusst werden. Dies stellt die besondere Bedeutung eines Simulators im Kontext

eines Generatorframeworks für VLs heraus. Dies ist wichtig, da mit DEViL bereits

viele DSLs spezifiziert wurden. Des Weiteren erlaubt es die Entkopplung, den

Simulator leichter wart- und erweiterbar zu machen. So ist eine spätere Erweiterung

denkbar, um Rechenlast auf mehrere Rechner zu verteilen. Dazu müssten lediglich

im Simulator entsprechende Erweiterungsschnittstellen geschaffen werden. Ein

weiterer Aspekt der Entkopplung wird sich in der Sprache zeigen: die Verwen-

dung von Zugriffsfunktionen auf Typen von Objekten. Dadurch lässt sich später

sehr einfach die visuelle Darstellung anpassen ohne die Simulationsspezifikation

modifizieren zu müssen. Des Weiteren erlaubt die Separierung von semantischer

Struktur und Simulationsstruktur, beide Modelle auch in so genannten Erstellungs-

und Initialisierungsfunktionen zu unterscheiden. Dies sind Funktionen, die auto-

matisch aufgerufen werden, wenn ein neues Sprachkonstrukt erstellt wird oder an

einen anderen Ort verschoben wird. Beide Strukturen können somit unabhängig

voneinander modifiziert werden.

Die Abbildbarkeit von semantischer und Simulationsstruktur besagt, dass alle

Konstrukte der semantischen Struktur der VL auch im Simulator abgebildet und

manipuliert werden können.

Zufallsbasierte Simulationen liefern häufig erst sehr spät in der Simulatoin

Ergebnisse oder es sind, um ein korrektes Resultat zu erzielen, mehrere Simula-

tionsläufe nötig. Ein Mechanismus muss vorhanden sein, um die Animation von

Simulationsschritten zu unterbinden. Auch können die Editoren so durch ein Skript

automatisiert gestartet werden.

Besondere Konstrukte wie Pfadausdrücke, Mustererkennung oder Zufallszah-

len sollen ebenfalls spezifiziert werden können. Diese Anforderung wurde direkt

aus den untersuchten Simulationssprachen abgeleitet.

Die Anpassung an LIGA ist wichtig zur späteren Berechnung der dynamischen

graphischen Darstellung durch den Simulator. DEViL benutzt zur Berechnung

der Animation den Attributauswertergenerator LIGA [53] des Eli-Systems. Die

Simulationsstruktur wird dabei so transformiert, dass sie von LIGA durchlaufen

werden kann. Dies ist jedoch transparent für den Benutzer und schränkt ihn in keiner

Weise bei der Spezifikation ein. Hier zeigt sich der Nutzen der Designentscheidung,

Vorhandenes und bereits Bewährtes aus dem DEViL-System zu adaptieren und

KAPITEL 4. SIMULATIONSKONZEPT

wiederzuverwenden.

Neben der Animation als Analysewerkzeug kann es auch noch andere Mecha-

nismen geben, um visuelle Programme zu analysieren. Dies kann die schrittweise

Ausführung von Simulationen, das Loggen von Ereignissen oder auch die Verifika-

tion von Eigenschaften der Struktur sein (vgl. Kapitel 6).

Erweiterbarkeit ist insbesondere wichtig für die Analyse. Sprachentwickler sol-

len den Simulator durch eigene oder fremde Bibliotheken erweitern können. Dies

geschieht bereits durch den Einsatz der C++ Boost-Bibliotheken um Zufallszahlen

zu erzeugen. Aber auch eigene Funktionen, die nicht so allgemein sind, dass sie in

das Generatorframework einfließen können, sollen sich einbinden lassen.

Die schmale Schnittstelle verweist bereits auf die Animation. Durch einige we-

nige standardisierte Operationen, die die Simulationsstruktur ändern, kann eine

Animation abgeleitet werden. Somit kann die Animation als formale Abbildung der

Simulation betrachtet werden.

Der letzte Punkt zielt auf die Bedienbarkeit und die Flexibilität des Simulators

ab. Es soll möglich sein Simulationsschritte einzeln ablaufen zu lassen, die Simula-

tion zu stoppen und mit veränderten Eingaben wieder zu starten. In der Literatur

wird dies oft auch als Reaktivität bezeichnet. Auch eine Rückwärtssimulation mit

Animation im Sinne des Forms/3 Systems [16] sollte möglich sein.

4.1.3 Einbettung des Simulators in die Werkzeugkette

Der Simulator kann als eine Umgebung verstanden werden, die aus einer Reihe

von Werkzeugen besteht (siehe Abb. 4.2). Es wird ein zeitdiskreter ereignisbasierter

Simulator generiert, der dem “next-event to time advance”-Ansatz folgt. Das Zeit-

modell unterteilt die Simulation in ihre kleinsten Einheiten und kann vom Benutzer

des Simulators flexibel angewendet werden. Neben einer Warteschlange, in die

Ereignisse eingeordnet werden können, gibt es noch die Option Ereignisse direkt

auszuführen. Dies vermeidet race-conditions, da sich Änderungen in der Struktur

direkt auswirken.

Der Simulator ist das Kernstück der generierten Simulationsumgebung. Er simuliert

auf der Simulationsstrukturinstanz. Diese wird aus dem semantischen Modell der

Sprache hergeleitet. D. h. es können alle Konstrukte des semantischen Modells in

die Simulationsstruktur übernommen werden. Man kann jedoch auch Teilbäume,

die nicht für die Simulation von Belang sind, weggelassen. Dies kann für Teilbäume

gelten, die nur der Darstellung dienen. Die so entstandene Simulationsstruktur kann

dann noch um weitere optionale persistente Attribute, Zufallszahlen, Pfadausdrücke

oder kontext-sensitive Funktionen erweitert werden. Pfadausdrücke können so zur

4.1. DER SIMULATOR

Laufzeit Gruppen von Objekten aufsammeln, die bestimmte Eigenschaften erfüllen,

z. B. die Vorbedingung einer Transition in einer Petri-Netz-Simulation.

Der Simulator überprüft während der Simulation in einer Endlosschleife die

Simulationsstruktur und plant Ereignisse ein, die die Simulationsstrukturinstanz

ändern (explizite Darstellung ist in der Abbildung 4.2 weggelassen). Änderungen

an der Simulationsstruktur, die sich auf die semantische Struktur der VL zurück-

führen lassen, werden ebenfalls vom Simulator geschrieben. Außerdem schreibt der

Simulator in die Analysekomponente und protokolliert die Veränderungen in ei-

ner Historie. Simulationsschritte können so vollständig rückgängig gemacht werden.

Eine weitere Eigenschaft des Simulators ist, dass die Instanz einer Simulations-

struktur während einer schrittweisen Simulation durch den Anwender modifiziert

werden kann. Hier ist jedoch Vorsicht geboten, da auch das Löschen von Programm-

konstrukten erlaubt ist und so auch ungültige Simulationszustände produziert

werden können. Trotzdem wird hier eine optimistische Variante benutzt, die den

Eingriff des Anwenders in die Simulationsstrukturinstanz jederzeit erlaubt. So wird

eine besonders hohe Flexibilität erreicht. Eine Filterung von potentiell gefährlichen

Modifikationen könnte eine sinnvolle Erweiterung sein. In der Literatur wird diese

Eigenschaft als eine “in-place”-Änderung bezeichnet [88].

Der so genannte Change-Propagation-Handler registriert Änderungen an der Simula-

tionsstruktur und stößt ggf. Sicht-Updates an. Dies kann bei jedem Simulationsschritt

passieren, was eine Animation auslösen würde oder, wenn im Simulation-only Modus

gearbeitet wird, auch erst nach beispielsweise 1000 Simulationsschritten. Weiterhin

wichtig für Sprachen, bei denen sich Simulations- und Animationsstruktur stark

unterscheiden und eine Spezifikation durch Kopplung realisiert ist, ist der Zusam-

menhang zwischen editierbarer Struktur und Simulator, verdeutlicht durch den

gestrichelten Pfeil. Änderungen an der semantischen Struktur können nämlich Än-

derungen in gekoppelten editierbaren Strukturen auslösen. Der Simulator erkennt

dies und schreibt für die gekoppelten Strukturen ebenfalls Modifikationsoperationen

in die Schnittstelle zur Animation. Somit kann auch hier einfach eine Animation

hergeleitet werden.

4.1.4 Zeitliches Verhalten des Simulators

Das Zeitmodell kann durch den Spezifizierer einer Simulation flexibel angepasst

werden. Da ich den ereignisbasierten Ansatz zur Simulation gewählt habe, existiert

eine Ereigniswarteschlange, in die Ereignisse zu beliebigen Zeitpunkten eingeordnet

werden können. Zu einem Simulationszeitpunkt können beliebig viele Ereignisse

ausgeführt werden, die wiederum aus beliebig vielen Änderungsoperationen beste-

hen. Eine Ordnung über Ereignisse, die zum selben Zeitpunkt ausgeführt werden,

existiert nicht. Eine Notwendigkeit für solche Ordnungen hat sich bei den bisher

KAPITEL 4. SIMULATIONSKONZEPT

Abbildung 4.2: Einbettung des Simulators in das Simulationsframework

implementierten Sprachen noch nicht gezeigt. Dies könnte jedoch leicht nachgerüstet

werden. Zeitpunkte zu denen kein Ereignis eingeplant ist, werden übersprungen.

Dies ist der “next-event to time advance”-Ansatz. Um anzudeuten, dass zu einem

Zeitpunkt kein Ereignis getriggert wurde, kann im generierten Editor eine Stoppuhr

angezeigt werden. Besonders in Warteschlangensimulationen kann der Anwender

Inaktivität so sehr leicht erkennen.

Neben der Warteschlange für Ereignisse existiert noch die weitere Möglichkeit

Ereignisse direkt auszuführen: Die Ereigniswarteschlange wird dabei umgangen.

Mit diesem Mechanismus können race-conditions verhindert werden. Diese können

in ereignisbasierten Systemen eintreten, wenn mehrere Ereignisse zu unterschied-

lichen Zeitpunkten auf dieselben Daten zugreifen. Dies kommt beispielsweise in

Petri-Netzen vor, wenn zwei Transitionen dieselbe Stelle als Vorbedingung haben.

Ist dort eine Marke vorhanden, so stellt der Simulator in der Simulationsschleife

fest, dass beide Transitionen schalten können, obwohl dies laut Petri-Netz Semantik

nur für eine Transition geschehen darf. Wird die Marke direkt durch ein Ereignis

entfernt, so erkennt der Simulator dies und plant kein weiteres Ereignis mehr ein.

Abbildung 4.3 zeigt exemplarisch das zeitliche Verhalten des Simulators. Prin-

zipiell lässt sich ein Simulationsschritt dabei in zwei Phasen unterteilen. In der ersten

Phase (lila farbene Blöcke auf der X-Achse) arbeitet der Simulator die Simulatorschlei-

fe ab. In ereignisbasierten Simulatoren wird dabei das Simulationsmodell überprüft

und Ereignisse werden in die Warteschlange eingeordnet. In einer zweiten Phase

4.1. DER SIMULATOR

Abbildung 4.3: Zeitliches Verhalten des Simulators

KAPITEL 4. SIMULATIONSKONZEPT

werden die Ereignisse zum selben Simulationszeitpunkt abgearbeitet.

Abb. 4.3a zeigt, dass im ersten Schleifendurchlauf ein Ereignis xzum Zeitpunkt 1in

die Warteschlange eingeordnet wird (grünes Kästchen).

Abb. 4.3b zeigt die Warteschlange zum Zeitpunkt 1. Das Ereignis x(graues

Kästchen) ist abgearbeitet, hat jedoch ein weiteres Ereignis yin die Warteschlange

eingeordnet. In der Simulatorschleife zum Zeitpunkt 1wurden die Ereignisse zund

aeingefügt. Die Zeitpunkte der Ausführung sind 2bzw. 5.

Abb. 4.3c zeigt die Warteschlange nach Abarbeiten der Ereignisse zum Zeit-

punkt 2. Das Ereignis zwurde bearbeitet und hat ein weiteres Ereignis dausgelöst,

das jedoch nicht in die Warteschlange eingeordnet, sondern direkt bearbeitet wurde.

Das momentan einzig unbearbeitete Ereignis ist a. Zwischen Zeitpunkt 2und 5

passiert weiter nichts; die Simulation würde hier zur Verdeutlichung die Stoppuhr

anzeigen. Zum Zeitpunkt 5wird aausgeführt. Da Ereignis akeine weiteren Ereig-

nisse feuert und die Warteschlange leer ist, stoppt die Simulation.

Abb. 4.3e zeigt, dass jedes Ereignis beliebig viele Simulationsmodifikations-

operationen auslösen kann, deren Animationen jeweils nach Abarbeiten einer

Simulationsschleife erfolgt.

4.2 Entwurf der Simulationssprache

Der Entwurf einer Simulation auf Basis einer visuellen Sprache zeigt, dass die

semantische Struktur der visuellen Sprache nicht unbedingt optimal zur Simula-

tionsstruktur passt. Das ist der Fall, wenn sie Klassen, Attribute oder Referenzen

enthält, die als Zugeständnis an die editierbare Struktur, also der visuellen Dar-

stellung der visuellen Sprache hinzugefügt wurden. Es werden aber bestimmte

Objekte der visuellen Sprache in der Simulationsstruktur benötigt. Häufig muss die

Simulationsstruktur auch neue Funktionalitäten wie das Gruppieren von Objekten

oder das Ausführen von Funktionen bereitstellen.

Die Simulationsstruktur einer visuellen Sprache kann also Gebrauch vom se-

mantischen Modell der visuellen Sprache machen, d. h. in der Simulationsstruktur

kann auf Objekte des semantischen Modells zugegriffen werden. Diese Simulations-

objekte haben gegenüber Objekten des semantischen Modells der visuellen Sprache

einige zusätzliche Eigenschaften. Bei der Initialisierung sind sie genaue Kopien ihrer

Pendants der visuellen Sprache, werden in der Simulationsstruktur jedoch erweitert

oder beschnitten.

Der erwähnte Zugriff auf Objekte der visuellen Sprache erfolgt durch die bereits

4.2. ENTWURF DER SIMULATIONSSPRACHE

eingeführten Pfadausdrücke. Diese erlauben es, einfach durch den Strukturbaum zu

wandern und Objekte, die bestimmte Eigenschaften erfüllen, aufzusammeln (z. B.

die Vorbedingung einer Transition eines Petri-Netzes).

Folgende Eigenschaften von Strukturspezifikation und Simulationsstruktur sind zu

nennen:

1. Ähnlichkeit der Spezifikationssprache zu DSSL und anderen Spezifikationsme-

thoden in DEViL.

2. Erweiterung der Struktur durch weitere (so genannte erweiterte) Attribute.

3. Erweiterung der Struktur durch kontext-sensitive Funktionen.

4. Spezialkonstrukte wie Zufallszahlen.

5. Zugriff auf Mengen von Objekten.

Die Ähnlichkeit zu vorhandenen Spezifikationsmethoden ist eine der wichtigsten

Beiträge dieser Arbeit. Die Ähnlichkeit zu existierenden und bewährten Methoden

ermöglicht es, Simulation und Animation von visuellen Sprachen als einfache Erwei-

terung des bestehenden Konzepts aufzufassen. Simulationsspezifikationen können

leicht gelesen und verstanden werden. Durch die Wiederverwendung müssen nicht

neue Spezifikationstechniken erlernt werden.

Die Strukturerweiterung ist wichtig, wenn Simulationen spezifiziert werden sollen,

die strukturelle Eigenschaften besitzen, die im semantischen Modell der Sprache

nicht vorhanden sind. Außerdem erleichtert dies die Teamarbeit und die Trennung

von Simulation und Strukturdefinition in DSSL. Ein Simulationsspezifizierer kann

eine Simulation entwerfen, ohne Rücksicht auf die zu Grunde liegende semantische

Modellstruktur zu nehmen. Bestehende Klassen des semantischen Modells können

erweitert werden, z. B. auch durch neue Teilbäume. Dies ist nützlich, wenn die

Simulation einige zusätzliche Attribute benötigt um Simulationseigenschaften

graphisch zu repräsentieren. In der Statechartssimulation ist dies beispielsweise das

Attribut, das die Aktivität eines Zustands angibt. Aber auch neue Unterstrukturen

sind denkbar, um beispielsweise Strategien für Routen von Autos in einer Verkehrs-

simulation zu beschreiben und zu speichern.

In objektorientierten Simulationen kommt es häufig vor, dass Simulationsob-

jekte durch die Simulationsstruktur “wandern” und an bestimmten Stationen

modifiziert, z. B. verzögert werden. Das Simulationsobjekt weiß selbst, was an jeder

Station passiert. Es kennt also seinen Kontext und führt entsprechende Funktionen

aus. Die Erweiterung durch neue Objekte oder auch Spezialisierung ist deshalb sehr

einfach.

Die Generierung und Benutzung von Zufallszahlen ist ein wichtiger Aspekt in

Simulationen. Nur so lassen sich aussagekräftige Ergebnisse erzielen. Mit Hilfe

der Zufallszahlen, erweiterter Attribute und der Auslastungsanalyse können sehr

KAPITEL 4. SIMULATIONSKONZEPT

einfach Warteschlangensyteme spezifiziert werden.

Der letzte Punkt besagt, dass der Zugriff auf bestimmte Mengen von Objekten

ermöglicht werden soll. Dies wird, wie ich später aufzeigen werde, durch Quanto-

ren, die auf Objekte eines Typs zugreifen, realisiert. Somit ist es leicht möglich, die

Struktur der Sprache später anzupassen, z. B. um sie zu verschieben oder tiefer zu

schachteln, ohne die Simulationsspezifikation zu ändern.

Insgesamt ergibt sich nun für die Simulationsstruktur das Tripel S= (Csim,Asim,M),

wobei Csim die Menge der Klassen des visuellen semantischen Sprachmodells ist

und Asim =Asemantic ∪ Aextended die Menge der Attribute des semantischen Modells

vereinigt mit der Menge der erweiterten Attribute der Simulationsstruktur ist.

M:Csim × Asim ist eine Abbildung von Attributen auf Klassen.

Die Anforderungen an die Spezifikationssprache für die Simulation sind viel-

fältig: sie soll möglichst einfach sein, jedoch eine große Menge an Simulationen

visueller Sprachen durch einfache Sprachkonstrukte abdecken. Der Sprachumfang

der Spezifikation leitet sich dabei direkt aus den Sprachen ab, die simulierbar sind.

Diese decken das Spektrum zufallsbasierter, transportorientierter und Simulationen

mit in der Sprache verankerter Simulationssemantik ab. Ist die Ausdrucksfähigkeit

der Simulationssprache an einer Stelle nicht ausreichend, so soll es möglich sein, die

Simulationssprache durch vom Sprachanwender definierte Funktionen zu erweitern.

Die Schnittstelle zur Animation sollte eng und standardisiert werden. Nur so

ist es möglich, die Animation als formale Abbildung der Simulation anzusehen und

Standardanimationen aus einer Simulationsspezifikation zu generieren.

Ein weiterer wichtiger Aspekt beim Entwurf der Sprache war, dass die Fähig-

keit zur Teamarbeit in DEViL erhalten bleibt. Die einzelnen Spezifikationsaspekte

beim Entwurf einer Sprache sollten weiterhin getrennt bleiben, d. h. Simulation, Ani-

mation, Sprachmodell und Repräsentation müssen weiterhin separat spezifizierbar

bleiben.

Auch der Zugriff auf Sprachkonstruktinstanzen ist einfach. Er kann auf Typ-

ebene erfolgen. Visuelle Darstellungen können so einfach geändert werden ohne die

Simulationsspezifikation zu beeinträchtigen.

Wiederverwendung ist ein weiteres Merkmal, durch das sich die Spezifika-

tionssprache auszeichnet. Vorhandene Konzepte zur Strukturdefinition werden im

Simulationsmodell wieder aufgegriffen und erweitert.

4.3. DIE SIMULATIONSSPEZIFIKATIONSSPRACHE DSIM

 Transition

tt.incomingPlaces marks > 0 ? FIRE

Transition t

Abbildung 4.4: DSIM - funktional betrachtet

4.2.1 Imperativ vs. regelbasiert

Die Simulationsspezifikation folgt dem imperativen Programmierparadigma. Eine

alternative Variante wäre das regelbasierte Programmierparadigma. Dagegen spricht

jedoch, dass schon einfache Simulationen viele Regeln haben können. So werden in

GenGed für die Simulation einer konkreten Ausprägung eines Petri-Netzes bereits

vier Regeln zur Simulation und nochmal sechs Regeln für das Animationsmapping

benötigt [32]. Regeln werden aufgrund von Seiteneffekten schnell unwartbar und

unübersichtlich [111]. Fishwick beschreibt in [36], dass deklarative Modelle bei

kontinuierlichen Systemen sowie bei Systemen, die aus einer Menge von Objekten

bestehen (wie in unserem Fall), nicht gut geeignet sind. Außerdem können in

regelbasierten Szenarien Abhängigkeiten zwischen entfernten Objekten nur schwer

modelliert werden. Trotzdem ist es denkbar, die Sprache um regelbasierte Konstrukte

zu erweitern, um eine vereinfachte Spezifikation für gewisse Anwendungsszwecke

zu erreichen.

Des Weiteren orientiert sich die Sprache DSIM am prozessorientierten Simula-

tionsparadigma, wobei Simulationsobjekte bestimmten Typs aufgesammelt werden

(durch Pfadausdrücke) und dann durch das Simulationsmodell wandern. Kontext-

sensitive Funktionen unterstützen dieses Paradigma. Währenddessen werden

Eigenschaften der Objekte durch Modifikation ihrer Attribute geändert. Diese Mo-

difikationen können auch funktional als Hintereinanderschaltung von Funktionen

betrachtet werden, die bestimmte Mengen von Objekten einschränken. Abbildung

4.4 zeigt diese funktionale Betrachtungsweise am Beispiel von Petri-Netzen. Die

Menge aller Transitionen wird benutzt um die Menge aller eingehenden Stellen zu

berechnen. Die berechneten Stellen werden dann wiederum gefiltert (marks > 0).

4.3 Die Simulationsspezifikationssprache DSIM

In den folgenden Abschnitten soll die Simulationsspezifikationssprache DSIM vorge-

stellt werden. Anhand einiger Ausschnitte aus Spezifikationen für bereits implemen-

KAPITEL 4. SIMULATIONSKONZEPT

tierte Editoren werde ich die einzelnen Teile des Spezifikationsprozesses in DSIM

verdeutlichen.

4.3.1 Spezifikation der Simulationsstruktur

Die Spezifikation von Simulation in DSIM unterteilt sich in mindestens drei Ab-

schnitte (ein vierter ist zur Konfiguration von globalen Einstellungen optional).

Zunächst wird die Simulationsstruktur beschrieben. Hier können Klassen des

semantischen Sprachmodells mit zusätzlichen persistenten Attributen, Pfadaus-

drücken oder kontext-sensitiven Funktionen ausgestattet werden. Im einfachsten

Fall fällt die Simulationsstruktur mit dem semantischen Modell der Sprache zusam-

men. In diesem Fall wäre die Spezifikation hier leer, wie das beim Editor für das

bekannte Game-of-Life-Szenario ist.

¨ ¥

1MODEL {

2CLASS Transition {

3SET incomingPlaces OF Place: "THIS.IVALUE[Connection.to].PARENT.from.VALUE[Place]";

4SET outgoingPlaces OF Place: "THIS.IVALUE[Connection.from].PARENT.to.VALUE[Place]";

Listing 4.1: Spezifikation der Simulationsstruktur für Petri-Netze in DSIM

Listing 4.1 zeigt die Spezifikation der Simulationsstruktur für einfache Petri-

Netze in DSIM. Der Ausschnitt zeigt, wie die Klasse Transition des semantischen

Sprachmodells um zwei Pfadausdrücke erweitert wird. Die Pfadausdrücke berech-

nen zur Laufzeit die Vor- bzw. Nachbedingung einer Transition. Das Schlüsselwort

THIS innerhalb des Pfadausdrucks wird dabei zur Laufzeit durch das aktuelle

Objekt ersetzt, in diesem Fall ein Transition-Objekt.

Listing 4.2 zeigt einen weiteren Ausschnitt aus einer Simulationsstrukturspezi-

fikation. Der Ausschnitt ist der Verhaltensspezifikation des “Mensch-ärgere-Dich-

nicht’’-Editors entnommen. Das Besondere ist, dass hier Klassen nicht nur um

Pfadausdrücke erweitert werden, sondern auch durch persistente Attribute (Zeile

5 u. 6). Es können die gleichen Attributtypen wie in DSSL verwendet werden. So

können unter Verwendung von SUB-Knoten aggregierte Unterbäume spezifiziert

werden, die nur in der Simulation existieren. Interessant ist dies, wenn beispielswei-

se komplexe Strategien in Spielen modelliert werden sollen. Eine Spielfigur könnte

so eine komplexe Strategie aggregiert enthalten. Das Weglassen von Teilbäumen, die

für die Simulation irrelevant sind, kann ebenfalls spezifiziert werden. Im Beispiel

wird der Teilbaum ruleDescription, der eine textuelle Beschreibung für Regeln

des Spiels enthält, weggelassen (Zeile 37).

100

4.3. DIE SIMULATIONSSPEZIFIKATIONSSPRACHE DSIM

¨ ¥

1...

3CLASS PlayerFigure {

4OBJECT getNode OF GameNode: "THIS.PARENT.PARENT";

5isOnTurn: VAL VLBoolean INIT "0";

6error: VAL VLBoolean INIT "0";

8FUNCTION moveToNextNode(PlayerTable player) {

9ON SimpleNode CONTEXT {

10 PlayerFigure figure = THIS;

11 GameNode node = figure.getNode;

12 GameNode nextNode = node.next;

13 GoalNode goalNode = node.goalNode;

14 IF(NOTNULL(goalNode)) {

15 IF(goalNode.color == figure.color) {

16 nextNode = goalNode;

17 }

18 }

19 FIRE moveFigureTo(figure,nextNode) @ TIME_DIRECT;

20 }

22 ON StartNode CONTEXT {

23 PlayerFigure figure = THIS;

24 GameNode node = figure.getNode;

25 GameNode nextNode = node.next;

26 GoalNode goalNode = node.goalNode;

27 IF(NOTNULL(goalNode)) {

28 IF(goalNode.color == figure.color) {

29 nextNode = goalNode;

30 }

31 }

32 FIRE moveFigureTo(figure,nextNode) @ TIME_DIRECT;

33 }

34 }

36 CLASS Root {

37 IGNORE SUBTREE (ruleDescription);

38 }

39 ...

Listing 4.2: Ausschnitt der Spezifikation der Simulationsstruktur für Ludo in

DSIM

Eine weitere Besonderheit ist die Definition von kontext-sensitiven Funktionen

(Zeile 8 - 34). Eine solche Funktion kann als Objektmethode einer Klasse angesehen

werden, die aus der Verhaltensspezifikation (siehe nächster Abschnitt) aufgerufen

werden kann. Innerhalb dieser Funktion können Blöcke definiert werden, die den

strukturellen Modellkontext einer Klasseninstanz referenzieren. Im Beispiel sind

mit StartNode und SimpleNode zwei Strukturknoten benannt, d. h. der Rumpf

des Blocks wird nur ausgeführt, wenn sich das aktuelle Objekt direkt unterhalb

eines SimpleNode bzw. eines StartNode befindet. So kann das Verhalten von

Objekten in bestimmten Kontexten sehr einfach spezifiziert werden. Dies ist bei

transportorientierten Simulationen häufig der Fall. Je nach Station (Kontext) werden

unterschiedliche Aktionen ausgeführt. Der Kontext kann auch noch genauer ange-

geben werden, indem nicht nur ein Strukturobjekt, sondern zusätzlich noch ein Ag-

101

KAPITEL 4. SIMULATIONSKONZEPT

gregationsknotenkontext in der Form Strukturknoten.Aggregationsknoten

angegeben werden kann.

Des Weiteren sind innerhalb der kontext-sensitiven Funktion bereits Teile der

Verhaltensspezifikation zu sehen. Es können Variablen und Strukturobjekte zuge-

wiesen werden (Zeilen 10-13 u. 23-26), außerdem werden mit dem Schlüsselwort

FIRE bereits Ereignisse gefeuert. TIME_DIRECT ist dabei die Variante, die die Ereig-

niswarteschlange umgeht und Ereignisse direkt abarbeitet. Ein Ereignis entspricht

dann einer Methode ohne Ergebnis.

4.3.2 Spezifikation des Simulationsverhaltens

Die Spezifikation des Simulationsverhaltens findet in der Regel im LOOP-Abschnitt

der DSIM Spezifikation statt. Wie oben gesehen, können aber auch innerhalb von

kontext-sensitiven Funktionen Verhaltenssbeschreibungen stehen.

Der LOOP-Abschnitt der Spezifikation wird direkt in den Simulator generiert.

Was hier spezifiziert wird, wird vom Simulator in einer Endlosschleife durchlaufen.2

Dies ist eine direkte Konsequenz aus der Wahl eines ereignisbasierten Simulatorsys-

tems.

Innerhalb einer DSIM-Spezifikation kann es mehrere benannte LOOP-Blöcke ge-

ben um unterschiedliche Varianten implementieren zu können. In der Simulation

von Sortieralgorithmen gibt es so einen Quicksort- und einen Bubblesort-Block. Zu

Beginn der Simulation fragt der Simulator interaktiv den Benutzer, welcher Block

ausgeführt werden soll.

Zweck des LOOP-Abschnittes ist das Einplanen von Ereignissen in die Warteschlange

mittels des FIRE-Konstrukts. Dazu kann die Simulationsstruktur durchlaufen und

überprüft werden. Dies geschieht mit Zugriffen auf Sprachkonstruktknoten und

deren Attribute.

Listing 4.3 zeigt mehrere Prinzipien in der Verhaltensspezifikation von DSIM.

Der Zugriff auf Gruppen von Objekten soll so einfach wie möglich sein. Dazu gibt es

eine Reihe von Quantoren. In der ersten Zeile ist das FOREACH-Konstrukt zu sehen.

Es ermöglicht den Zugriff auf alle Objekte eines bestimmten Typs, in diesem Fall alle

Transition-Objekte. Mit dem Schlüsselwort RANDOM in der Spezifikation werden

die Objekte in zufälliger Reihenfolge zurückgegeben. Auch auf Unterklasseninstan-

zen von abstrakten Klassen kann zugegriffen werden. Ein Vorteil des typ-basierten

2Unterbrochen werden kann die Schleife nur, falls der Simulator feststellt, dass sich in der Simu-

lationsstruktur nichts geändert hat und keine Ereignisse mehr abgearbeitet werden müssen oder

falls der Benutzer selbst die Simulation unterbricht.

102

4.3. DIE SIMULATIONSSPEZIFIKATIONSSPRACHE DSIM

¨ ¥

1FOREACH tIN [Transition] RANDOM{

2IF(t.canFire) {

3IFEVERY t.incomingPlaces->tokenCount > 0 {

4FIRE preTransitionFire(t2) @ TIME_DIRECT;

5FIRE postTransitionFire(t2) @ TIME_NOW + 1;

Listing 4.3: Ausschnitt der Spezifikation des LOOP-Blocks für Petri-Netze in

DSIM

Zugriffs ist, dass Teilbäume auch nach einer Simulationsspezifikation noch verscho-

ben werden können. Dies ist häufig der Fall, wenn die Spezifikation für eine visuelle

Sprache refaktorisiert wird. Möchte der Sprachspezifizierer beispielsweise nicht nur

ein Petri-Netz darstellen, sondern eine Menge von Petri-Netzen, so fügt er üblicher-

weise noch eine Sicht ein, die die einzelnen Netze mit Namen darstellt. Die Netze

selbst wandern im Strukturbaum eine Ebene tiefer. Die Verhaltensspezifikation der

Simulation bleibt unberührt.

Das Listing zeigt mit dem IFEVERY-Konstrukt einen weiteren Quantor. Dabei

wird überprüft, ob die Markenanzahl größer als null ist. Mit dem Punkt-Operator

wird dabei auf Attribute der Simulationsstruktur zugegriffen. Dies können erwei-

terte Attribute oder auch Attribute des semantischen Modell sein. In diesem Fall

ist incomingPlaces ein Pfadausdruck (vgl. Listing 4.1), der die Vorbedingung

der Transition berechnet. Der Pfadausdruck liefert eine Menge von Objekten, das

IFEVERY-Konstrukt wertet das Attribut tokenCount dieser Menge aus.

Listing 4.3 zeigt, wie Ereignisse gefeuert werden. Das erste Ereignis wird mit-

tels FIRE-Konstrukt direkt ausgeführt (TIME_DIRECT). Ereignisse diesen Typs

wirken sich unmittelbar auf die Simulationsstruktur aus, d. h. Veränderungen an

der Struktur sind bereits in der Zeile nach dem FIRE-Konstrukt wirksam. Dies

verhindert, dass zwei Transitionen gleichzeitig feuern, die dieselbe Vorbedingung

haben, jedoch zu wenig Marken auf der Vorbedingung. Es würde sich hier also

um eine race-condition handeln. Die zweite Variante zeigt das Einordnen in die

Ereigniswarteschlange - ebenfalls mit dem FIRE-Konstrukt. Als Zeitangabe steht

hier TIME_NOW, was für den nächsten Simulationsszeitpunkt steht - plus einem

nicht-negativen Ausdruck. So können Ereignisse beliebig weit in der Zukunft

eingeplant werden.

Listing 4.4 zeigt mit REPEAT und WHILE zwei weitere Schleifenkonstrukte zur Iterati-

on. Besonderheit an diesem Ausschnitt ist der direkte Zugriff im gesamten Struktur-

baum auf Sprachkonstruktinstanzen mit dem Offset-Operator #[i]. Besonders ein-

fach gestalten sich damit Zugriffe auf Objekte, wenn bereits bekannt ist, wie viele

103

KAPITEL 4. SIMULATIONSKONZEPT

¨ ¥

1...

3WHILE ((#[i]ListElement.size <= pivot.size) AND (i < right)) {

4i=i+1;

7REPEAT SIZE(#[0]Root.elements) {

8...

Listing 4.4: Ausschnitt einer Spezifikation eines LOOP-Blocks mit

Schleifenvarianten und Ausdrücken

Objekte zur Laufzeit existieren. Es darf nur ein Root-Objekt im Programm existie-

ren, somit kann mit #[0]Root auf das einzige Wurzelobjekt zugegriffen werden.

4.3.3 Spezifikation von Ereignissen

Im Ereignisabschnitt der Simulationsspezifikation wird definiert, wie die Simula-

tionsstruktur verändert werden soll. Ereignisse werden benannt und haben eine

beliebig lange formale Parameterliste. Als Parameter sind Sprachkonstruktknoten

oder Attributwerte spezifizierbar. Innerhalb von Ereignissen können beliebig viele

Simulationsmodifikationsoperationen definiert werden. Diese modifizieren, wenn das

Ereignis ausgeführt wird, die Simulationsstruktur. Simulationsmodifikationsope-

rationen dürfen nur innerhalb von Ereignissen und kontext-sensitiven Funktionen

¨ ¥

1EVENTS {

2preTransitionFire(Transition transition) {

3FOREACH place IN transition.incomingPlaces {

4Token token = REMOVE(place.tokens, FIRST);

8postTransitionFire(Transition transition) {

9FOREACH place IN transition.outgoingPlaces {

10 Token token = INSERT(place.tokens, INSTANCEOF [Token], FIRST);

11 }

12 }

13 }

Listing 4.5: Spezifikation von Ereignissen für einen Petri-Netz-Editor

benutzt werden. Um kontextabhängige Animationen definieren zu können, kann ab-

gefragt werden, welches Ereignis Auslöser für eine Änderungsoperation war. Somit

können für die Animation notwendige Kontextinformationen aus der Simulation

einfach gelesen werden (vgl. Abschnitt 5.11).

Ereignisse können auch selbst wieder Ereignisse einplanen. Listing 4.5 zeigt

104

4.3. DIE SIMULATIONSSPEZIFIKATIONSSPRACHE DSIM

die Spezifikation von zwei Ereignissen für eine Petri-Netz-Simulation. Beide

Ereignisse werden ausgelöst, wenn eine Transition schalten kann. Das Ereignis

preTransitionFire sorgt dafür, dass auf allen Stellen der Vorbedingung der

Transition (berechnet durch den Pfadausdruck transition.incomingPlaces

aus Listing 4.1) jeweils die erste Marke (FIRST-Schlüsselwort) entfernt wird. Dazu

wird die Simulationänderungsoperation REMOVE benutzt, die als Parameter einen

Aggregationsknoten und eine symbolische Position erhält. Als Rückgabe liefert sie

eine Referenz auf das entfernte Objekt.3

Das Ereignis postTransitionFire generiert auf allen Stellen der Nachbedingung

der Transition ein neues Token-Objekt. Es bekommt ebenfalls als Parameter einen

Aggregationsknoten, eine symbolische Position und liefert eine Referenz auf das

neu erstellt Objekt als Rückgabe. Insgesamt lassen sich in Ereignissen bzw. kontext-

sensitiven Funktionen die folgenden vier Simulationsmodifikationsoperationen

benutzen:

•REMOVE zum Löschen von Objekten, z. B.

REMOVE(StrukturObjekt.Aggregationsknoten, LAST);

•INSERT zum Einfügen von Objekten, z. B.

INSERT(StrukturObjekt.Aggregationsknoten, FIRST); Wird ein

vorher gelöschtes Objekt eingefügt, wird eine MOVE-Änderungsoperation

erkannt. Wird ein neues Objekt eingefügt, wird eine CREATE-

Änderungsoperation erkannt.

•COPY zum Klonen von Objekten (kopieren im Struktureditor-Sinn), z. B.

StrukturObj x = COPY(StrukturObjekt.Aggregationsknoten,

LAST);

xkann danach mittels INSERT eingefügt werden.

•CHANGE_VAL implizite Änderungsoperation, die beim Ändern primitiver At-

tribute ausgelöst wird, z. B.

StrukturObjekt.value = VLInt(5);

Die Modifikationen reichen aus, um beliebige Strukturbäume zu modifizieren, wie

sie in von DEViL generierten Editoren existieren.

Listing 4.6 zeigt ein etwas komplexeres Ereignis aus dem Pac-man-Editor. Es

spezifiziert das Verhalten des Pac-man, der einen Geist ”fressen“ darf. Zunächst

wird dabei ein weiteres Ereignis direkt ausgeführt, das den Spielstand setzt (Zeile

2). Das Attribut numberOfEatenGhosts wird inkrementiert (eine CHANGE_VAL

Operation wird ausgelöst). Das Ereignis computeRotation wird gefeuert. Zum

Schluss werden die Spielfiguren entsprechend bewegt, d. h. die Geist-Figur wird

3Die Zuweisung auf der linken Seite in Zeile 4 kann auch weggelassen werden, da die Referenz

nicht mehr gebraucht wird. Sie dient lediglich der Darstellung der Funktionalität des REMOVE-

Konstrukts.

105

KAPITEL 4. SIMULATIONSKONZEPT

¨ ¥

1eatGhost(Tile from, Tile to, Pacman p, VLInt d){

2FIRE incrementScore(#[0]Score, 1000) @ TIME_DIRECT;

3#[0]Root.numberOfEatenGhosts = #[0]Root.numberOfEatenGhosts + VLInt(1);

5FIRE computeRotation(p,d) @ TIME_DIRECT;

7REMOVE(to.item, FIRST);

8Item i = REMOVE(from.item, FIRST);

9INSERT(to.item, i, FIRST);

10 }

Listing 4.6: Spezifikation eines Ereignisses für den Pac-man-Editor

gelöscht (Zeile 7) und Pac-man auf die Position des Geistes gesetzt (REMOVE und

INSERT werden zu MOVE).

4.3.4 Spezielle Funktionalitäten

DSIM bietet noch einige weitere Eigenschaften, wie z. B. Logging-Mechanismen, Ka-

chelzugriffsfunktionen, Interaktion sowie Pattern-Matching.

¨ ¥

1...

2Tile to = NEIGHBOUR_TILE(default, NEUMANN, ghost.tile, Pacman);

3IF(NOTNULL(to) AND (ghost.eatable == VLBoolean(0))){

4FIRE eatPacman(ghost.tile, to) @ TIME_DIRECT;

5}ELSE{

6to = NEIGHBOUR_EMPTY_TILE_RANDOM(default, NEUMANN, ghost.tile);

7IF(NOTNULL(to)){

8FIRE goGhost(ghost.tile, to) @ TIME_DIRECT;

10 }

11 ...

Listing 4.7: Spezifikation von Kachelzugriffsfunktionen im Pac-man Editor

Kachelzugriffsfunktionen Listing 4.7 zeigt zwei Kachelzugriffsfunktionen des

Pac-man-Editors. Von DEViL generierte Editoren, die Gebrauch vom visuellen

Matrix-Muster machen, also kachelbasierte Darstellungen nutzen, setzen eine

ganz bestimmte semantische Struktur voraus um das Matrix-Muster anwenden

zu können. Kachelzugriffsfunktionen nutzen diese immer gleiche Struktur aus

um einfach auf die Umgebung einer bestimmten Kachel zugreifen zu können.

Die Funktion NEIGHBOUR_TILE erwartet dabei eine Referenzkachel, sowie eine

Nachbarschaftsdefinition (von NEUMANN im Beispiel, also Kacheln links, rechts,

oben sowie unten von der Referenzkachel). Sie liefert als Ergebnis die Kachel,

auf der ein Strukturobjekt eines bestimmten Typs (hier Pacman) beheimatet ist.

Die Kachelfunktion NEIGHBOUR_EMPTY_TILE_RANDOM liefert zufällig eine leere

106

4.3. DIE SIMULATIONSSPEZIFIKATIONSSPRACHE DSIM

Kachel in der Umgebung zurück. Die Spezifikation in Listing 4.7 berechnet die

Bewegung eines Geistes im Pac-man-Editor. Ist auf einer der Nachbarkacheln ein

Pac-man-Objekt vorhanden, so wird der Pac-man gefressen, andernfalls wird der

Geist zufällig bewegt.

Kachelzugriffsfunktionen sind ein Resultat aus der Implementierung des Pac-

man Editors. In [128] konnte gezeigt werden, dass bereits eine kleine Anzahl

verallgemeinerter Zugriffsfunktionen den Spezifikationsaufwand erheblich redu-

zieren kann. Neben den beiden vorgestellten Funktionen gibt es noch eine Reihe

anderer Funktionen, die z. B. den Zugriff über eine Richtung oder die Kachelnummer

liefern.

Log-Ausgaben Logging-Mechanismen sind bei der Analyse von Simulationen

wichtig. DSIM bietet ein Log-Konstrukt an, das ähnlich wie die C printf Funk-

tion arbeitet; also eine variable Parameterliste handhaben kann und verschiedene

Logging-Stufen bietet. Da Logging sehr rechenintensiv sein kann, lässt es sich in

DSIM jederzeit ausschalten.

¨ ¥

1...

2IF(#[0]Root.logging == VLBoolean(0))

3LOGLEVEL =NONE;

4...

5IF(fired > 1) {

6LOG(WARNING, "Statechart ist nicht-deterministisch bei Übergang %s!",

7transition.name);

9...

Listing 4.8: Log-Ausgaben

Listing 4.8 zeigt eine einfache Anwendung des Logging-Mechanismus. In Ab-

hängigkeit eines Attributs in der Simulationsstruktur wird ggf. das Logging

abgeschaltet (Zeile 3). In Zeile 6 wird eine Log-Ausgabe mit einem Parameter und

Log-Level WARNING definiert. Generell werden während der Simulation geschaltete

Ereignisse und angewendete Animationsmuster gelogged. Dies lässt sich jedoch

jederzeit beliebig anpassen.

Interaktion DSIM erlaubt das Einbinden von Benutzerinteraktion innerhalb der

Simulationsspezfikation. Prinzipiell gibt es zwei Arten von Interaktion: modale

und kontinuierliche Interaktion. Die erste Variante hält die Simulation an und

zwingt den Anwender eine Eingabe zu machen. Die kontinuierliche Interaktion

ist nicht zwingend für das Fortschreiten einer Simulation notwendig. Sie kann zu

jedem beliebigen Zeitpunkt geschehen. In der Simulation kann auf diese Interak-

tion eingegangen werden, muss es jedoch nicht. Der Spezifikation ist dies nicht

107

KAPITEL 4. SIMULATIONSKONZEPT

unbedingt anzusehen, wie Listing 4.9 zeigt. Dort werden zwei Benutzerereignisse

spezifiziert - der Einfachheit halber zwei Implementierungen in einem Beispiel.

Dies geschieht im optionalen CONFIGURATION-Block von DSIM. Das erste Ereignis

registriert die Pfeil-nach-oben Taste unter dem Namen keyUp. Das zweite registriert

eine beliebige Taste (<Key-Press>) unter dem Namen input und konvertiert das

Ergebnis in den VLString-Typ, wobei der Wert des VLString die Taste selbst ist

(%A. Tcl-Notation). In der Simulation kann eine solche Benutzerinteraktion über das

¨ ¥

1CONFIGURATION {

2// Pac-man

3REGISTER "<Up>" AS keyUp CONVERT "1" VLInt;

5// Statecharts

6REGISTER "<KeyPress>" AS input CONVERT "%A" VLString;

9LOOP {

10 // Statecharts

11 IF(ACTION_EVENT(input) AND

12 ACTION_EVENT_VALUE(input) == outgoingTransition.label) {

13 ...

14 }

16 // Pac-man

17 IF(ACTION_EVENT(keyUp)){

18 FIRE movePacman(1) @ TIME_DIRECT;

19 }

20 }

Listing 4.9: Benutzerinteraktion

ACTION_EVENT(eventName) Schlüsselwort abgefragt werden. Ist es aufgetreten,

kann man den Wert mittels ACTION_EVENT_VALUE(eventName) abfragen (Zeile

12). So können sowohl modale als auch kontinuierliche Interaktion realisiert werden.

Mit Spezifikationen der Form

Transition toFire =

SELECT(list, "Select transition to fire.", NOTNULL);

können Dialoge geöffnet werden, in denen dem Benutzer eine Auswahl an möglichen

Sprachkonstrukten gegeben wird. Die Liste der Sprachkonstrukte wird dem Anwen-

der dabei in der graphischen Oberfläche präsentiert. Sollten nicht alle Objekte eine

graphische Repräsentation haben, so wird eine textuelle Auswahlliste präsentiert. In

Abbildung 4.5 ist das Resultat eines solchen Konstrukts zu sehen. Die Transitionen,

die feuern können, werden rot hinterlegt dargestellt. DEViL stellt sicher, dass die

Auswahl des Benutzers korrekt ist, d. h. es muss eines der möglichen Objekte ausge-

wählt werden und die Auswahl darf nicht leer sein. In ähnlicher Form können auch

Fragedialoge erstellt werden, die primitive Werte als Eingabe erwarten.

108

4.3. DIE SIMULATIONSSPEZIFIKATIONSSPRACHE DSIM

Abbildung 4.5: Interaktionsdialog

Konfiguration der Simulation Der oben erwähnte optionale CONFIGURATION-

Block dient neben der Definition von Benutzerinteraktion dazu, auch benutzerdefi-

nierte Funktionen, z. B. externe C-Header einzubinden (genauso wie in C mit dem

#include-Makro). Außerdem können hier einige globale simulationsspezifische

Einstellungen vorgenommen werden. Die Wichtigste davon ist die Simulationsstruk-

turwurzel. Mit der Spezifikation

SIMULATION_ROOT PetriNet

kann die Wurzel der Simulationsstruktur angegeben werden. Existieren in einer

Petri-Netz-Spezifikation mehrere Objektinstanzen vom Typ PetriNet, so wird der

Benutzer durch Hinzufügen einer solchen Zeile vor der Simulation gefragt, auf wel-

cher Petri-Netz-Instanz simuliert werden soll. So können mehrere Petri-Netze kom-

fortabel nebeneinander existieren, wobei immer nur genau ein Netz simuliert wird.

Mustererkennung In Sprachen der vierten Kategorie der Klassifikation müssen

in der Regel Sprachkonstrukte gefunden werden, die bestimmte Eigenschaften

109

KAPITEL 4. SIMULATIONSKONZEPT

erfüllen. Meist werden diese Eigenschaften in der Sprache selbst durch (visuelle)

Regeln beschrieben. Die Regeln definieren dabei eine räumliche Semantik zwischen

Sprachkonstrukten. In einer Verkehrssimulation kann z. B. die Rechts-vor-links-

Regel visuell durch ein Kachelmuster ausgedrückt werden. Häufig sind dies nicht

nur strukturelle Eigenschaften, sondern konkrete Wertbelegungen von Attributen.

DEViLs Pfadausdrücke können dies nicht vollständig leisten. Aus diesem Grund

wurde ein XPath Auswerter [2] integriert. So kann die gesamte Simulationsstruktur

mit XPath-Ausdrücken ausgewertet werden.

¨ ¥

1...

2VLList[Streetsection] listOfProducer = MATCH("//Streetsection[@prodConsNorth=1] |

3//StreetsectionNE[@prodConsSouth=1] |

4//StreetsectionWE[@prodConsWest=1], OF [

Streetsection]);

5FOREACH producer IN listOfProducer {

6FIRE produceCar(producer);

8...

Listing 4.10: Mustererkennung mit XPath

Listing 4.10 zeigt einen Ausschnitt aus einer Verkehrssimulation. Dem Match-

Konstrukt wird ein XPath Ausdruck übergeben, der alle Straßenabschnitte der

Simulationsstruktur aufsammelt, die als Produzenten definiert sind (prodCons*

Attribut auf 1).

4.3.5 Textuell vs. visuell

In den eingangs erwähnten verwandten Generatorsystemen wird die Simulations-

spezifikation häufig visuell erstellt. Dies ist insbesondere bei Systemen auf Basis

von Graphtransformation der Fall. Dies ist zunächst ein Vorteil gegenüber DSIM,

allerdings muss erwähnt werden, dass DSIM darauf ausgelegt ist, sehr kompakt

auch komplexes Verhalten zu spezifizieren. In den genannten Generatorsystemen

müssen dagegen bereits bei sehr einfachen Problemen viele Regeln erstellt werden,

oft sogar in unterschiedlichen Kalkülen wie bei GenGed (vgl. Abschnitt 2.7.2). Um

auch kaskadierende Regelanwendungen auszudrücken muss der Graph in der Regel

künstlich erweitert werden. Im schlimmsten Fall werden sogar Simulation und

Animation innerhalb der Graphstruktur vermischt.

Unter anderem operiert DSIM auf der Simulationsstruktur bzw. dem seman-

tischen Modell der Sprache. Eine graphische Repräsentation muss noch nicht

zwingend vorliegen. Eine Spezifikation auf Basis einer graphischen Notation hätte

den Nachteil, dass Änderungen in der graphischen Darstellung auch Änderungen

in der Simulationsspezifikation nach sich ziehen würden. Dies widerspricht der

110

4.4. VERWANDTE ARBEITEN

Trennung von Layout und Logik. Trotzdem ist es vorstellbar, dass für DSIM eine

visuelle Sprache “on-top” definiert wird. Diese wäre wahrscheinlich aufgrund der

Verwendung von Pfadausdrücken wiederum sehr textlastig. Ein weiterer Nachteil

ist, dass die Manipulation von strukturell weit entfernten Objekten nur schlecht

visuell ausgedrückt werden kann.

4.4 Verwandte Arbeiten

Ein Ansatz zur Spezifikation von simulierbaren visuellen Sprachen ist der der Ab-

stract State Machines [44] (ASM) und der dazu gehörigen von Microsoft entwickelten

domänenspezifischen Sprache AsmL [66]. In [19] wird AsmL benutzt um das Verhal-

ten von DSLs zu spezifizieren. AsmL-Spezifikationen sehen wie Pseudo-Code auf

abstrakten Datenstrukturen aus und beinhalten regel-basierte Konstrukte. Des Wei-

teren erlauben sie auch die Verwendung von Iteratoren über Datenstrukturen. In [15]

werden ASMs für eine Fallstudie zur Spezifikation einer Lichtkontrollanlage benutzt.

In [31] und [117] werden Graphersetzungsregeln zur Simulation visueller Spra-

chen benutzt. Hier muss ein Vorher-/Nachher-Zustand in Form von Regeln

spezifiziert werden, der dann über ein Transformationswerkzeug, z.B. AGG, eine

Simulation in Gang setzt.

DSIM ist nicht als eine GPL auf Datenstrukturen so wie AsmL zu verstehen,

sondern speziell auf die Eigenschaften visueller Sprachen zugeschnitten. Der

Sprachumfang ist nicht so mächtig wie bei AsmL, jedoch ausreichend und es werden

viele Konzepte bereitgestellt, um einfach auf Sprachkonstruktinstanzen zuzugreifen

(Iteratoren, Quantoren, Pfadausdrücke). Außerdem integriert DSIM Konzepte von

Simulationssprachen, die bisher noch nirgends auf dem Gebiet der VL-Simulation

zu finden sind. Diese sind:

•Eigenständige Simulationsstruktur.

•Gruppieren von Simulationsobjekten.

•Kontext-sensitive Funktionen.

•Verschiedene Interaktionsmechanismen.

Gegenüber der Spezifikation durch Graphtransformation ist die einfache Lesbarkeit

auch bei komplexen Simulationen als Vorteil zu nennen. Der ereignisbasierte Ansatz

erlaubt eine sehr flexible Handhabung der Simulationszeit. Dieser hat sich bereits in

der Literatur beim DEVS-System [118] bewährt und kommt auch im DiaMeta-System

zum Einsatz. Die Erweiterung bzw. Einschränkung der semantischen Struktur zur Si-

mulationsstruktur erlaubt es, auch komplexe Simulationen abzubilden und das Sys-

tem zu modularisieren.

111

5 Animationskonzept

Inhalt

5.1 Das Animationsframework . . . . . . . . . . . . . . . . . . . . . . . 114