Prof. Dr. Reinhard Wilhelm Dipl.-Inform. Andreas Kerren                                                                     Fachbereich Informatik                                                                   Universität des Saarlandes                                                                      Tel.: (0681) 302-3235

    FoPra im Wintersemester 00/01

Visualisierung abstrakter Maschinen

Abb.: GANIMAM    

Inhalt:

GANIMAM ist ein webbasierter Generator für interaktive Animationen abstrakter Maschinen. Häufig werden abstrakte Maschinen als plattformunabhängige Zwischenarchitekturen bei der Übersetzung höherer Programmiersprachen verwendet. Die Anweisungen einer abstrakten Maschine sind für die Übersetzung einer bestimmten Quellsprache oder für Quellsprachen desselben Sprachenparadigmas (imperativ, funktional, logisch, objektorientiert) maßgeschneidert. Im Folgenden beschreiben wir, wie GANIMAM verwendet werden kann und was das System generiert. Abschließend diskutieren wir dann die Vorteile von GANIMAM und der erzeugten interaktiven Animationen sowohl als Entwicklungswerkzeug, als auch als Teil einer Lernsoftware.

Technischer Überblick

GANIMAM kann über die Webseite des GANIMAL-Projekts aufgerufen werden. Der Benutzer (Lehrer oder Lerner) gibt die Spezifikation einer abstrakten Maschine ein, die dann zum Server geschickt wird. Ein CGI-Skript auf dem Server erzeugt Java-Quellcode, der durch einen Java-Compiler in Klassendateien übersetzt wird. In Kombination mit den Klassen des Basispakets von GANIMAM ergeben die Klassendateien ein interaktives Java-Applet. Das Applet kann über das Internet geladen werden und der Benutzer kann dann Maschinenprogramme eingeben, das Layout der verschiedenen Teile der visualisierten abstrakten Maschine ändern und die animierte Ausführung seines Maschinenprogramms steuern. Abstrakte Maschinen können eine unterschiedliche Anzahl von Registern, Kellern, Halden haben, daher wird für jede generierte Maschine ein automatisches Layout benötigt. Das automatische Layout gruppiert die verschiedenen Speicherarten um den Akkumulator, eine konzeptionelle Recheneinheit, herum. Programmcode und Keller werden links, die Halde rechts, lokale Variablen über und Register unter dem Akkumulator plaziert. Mit dem Akkumulator ist ein Akkumulatorfenster verbunden, das den Ausdruck anzeigt der gerade im Akkumulator berechnet wird, sowie die Definition der Instruktion bzw. Funktion, die gerade ausgeführt wird. Durch einen zweifachen Mausklick mit der rechten Maustaste auf eine Instruktion im Programmcode wird die Definition der Instruktion in das Akkumulatorfenster geladen. Ein zweifacher Mausklick mit der linken Maustaste auf eine Instruktion im Programmcode setzt den Wert des Programmzählers auf die Adresse der Instruktion, d.h. die Ausführung des Programms wird an dieser Stelle fortgesetzt. Ein Klick auf eine Zelle des Kellers, der Halde oder auf ein Register öffnet ein Fenster. In diesem Fenster kann der Benutzer den Wert und den Typ, bei Registern nur den Wert ändern.

Vorteile interaktiver Animationen

GANIMAM bietet verschiedene Arten der Interaktion. Erstens kann der Benutzer Spezifikationen einer abstrakten Maschine eingeben oder ändern. Beim Visualisieren einer abstrakten Maschine ist es wichtig, daß man nicht nur Daten und Vorgänge auf dem geringen Abstraktionsniveau und der Granularität der Spezifikationssprache darstellt, sondern auch Abstraktionen auf höherem Abstraktionsniveau. Um dies zu ermöglichen, wurden Visualisierungsannotationen zur Spezifikationssprache hinzugefügt. Diese Annotationen ähneln den 'interesting events' einschlägiger Algorithmenanimationssysteme. Nach der Erzeugung der Implementierung der abstrakten Maschine kann der Benutzer Programme in der Sprache der abstrakten Maschine eingeben, diese Schritt für Schritt ausführen und den Inhalt jedes Registers und jeder Speicherzelle inspizieren. Während der Ausführung einer Instruktion zeigt eine Animation den Fluß der Information von Registern oder Speicherzellen in den Akkumulator und vom Akkumulator zurück zu Register oder Speicherzellen. Die Berechnung, die im Akkumulator durchgeführt wird, wird in einem separaten Fenster angezeigt. Annotationen helfen nur solche Prinzipien sichtbar zu machen, die wir schon vorher kennen. GANIMAM kann auch dazu verwendet werden, neue Prinzipien durch Experimentieren mit Maschinenprogrammen oder Spezifikationen von abstrakten Maschinen zu entdecken. Dieses experimentelle Vorgehen kann u.a. für folgende Zwecke eingesetzt werden:
• Als Teil einer explorativen Lernsoftware ermöglicht es Schülern und Studenten, neue Hypothesen zu formulieren und diese durch Änderung der Spezifikation oder des Maschinenprogramms zu überprüfen. Zusätzliche Hinweise in textueller Form sollte dabei sicherstellen, daß der Lerner auch die wesentlichen Punkte untersucht. Solche könnten z.B. der Vergleich zwischen caller-save-registers und callee-save-registers oder zwischen lazy und eager Auswertung sein oder das Finden des Kellerrahmens des statischen Vorgängers. Andererseits können Lehrer GANIMAM derart instanziieren, daß sie etwa eine abstrakte Maschine für eine imperative und eine logische Prgrammiersprache generieren und dann von den Schülern/Studenten vergleichen lassen.
• Als Entwicklungswerkzeug kann es helfen, Fehler oder Optimierungsmöglichkeiten zu entdecken. Eine solche Optimierung könnte z.B. die Endrekursion betreffen: Durch das Verfolgen der Ausführung von Beispielprogrammen könnte der Benutzer feststellen, daß bestimmte Informationen in einem Kellerrahmen nach rekursiven Aufrufen nicht mehr benötigt werden.

GANIMAM kann auch von Forschern eingesetzt werden, um ihre neusten Implementierungstechniken vorzuführen oder einfach für Rapid Prototyping.

Aufgaben

• Entwicklung neuer Frontends für 3 Sprachen unterschiedlicher Paradigmen, d.h. imperativ (C oder Pascal), funktional (SML) und logisch (Prolog). Implementierungssprache ist SML.
• Entwicklung von Codegeneratoren für diese 3 Frontends, ebenfalls in SML, die abstrakte Maschinenprogramme erzeugen.
• Spezifikation einer abstrakten Maschine für den jeweiligen Output der Codegeneratoren in der GANIMAM-Maschinenspezifikationssprache.
• Neuentwicklung bzw. Modifikation der o.g. CGI-Scripten in Perl, PHP, o.ä..
• Erweiterung des GANIMAM Systems dahingehend, daß bisher Datenstrukturen im Heap in einer keller- oder listenartigen Visualisierung dargestellt wurden. Eine in Java neu zu entwickelnde Extension soll nun komplexe Heapstrukturen angemessen visualisieren. Dazu stehen Klassenbibliotheken (Graphlayouter, etc.) aus dem Ganimal-Projekt zur Verfügung.




Liste der Teilnehmer:

Teilnehmer	Aufgabe	Betreuer	Status
Claudia Bieg	Implementierung eines Codegenerators für C in SML	A. Kerren	ok

Literatur:

Ausgewählte Kapitel aus
 
• Diehl, Kunze. Visualizing principles of abstract machines by generating interactive animations. In FGCS - Future Generation Computer Systems, Vol. 16, pp. 831-839, 2000.
• Wilhelm, Maurer. Übersetzerbau - Theorie, Konstruktion, Generierung. 2. Auflage, Springer-Verlag, 1997
• Aho, Sethi, Ullmann. Compilerbau. Vol.1 + 2, Addison-Wesley, 1990

 

Betreuer:	Andreas Kerren
Ort:	Geb. 45, Raum 431
Besprechungstermin:	Alle zwei Wochen, jeweils Donnerstags, 14.00 c.t., ab dem 09.11.2000
Angebotsturnus:	einmalig
Leistungspunkte:	18
Umfang:	F6
Voraussetzungen für  die Scheinvergabe:	Regelmäßige Teilnahme an allen Besprechungsterminen, Bearbeitung/Implementierung der gestellten Aufgabe und eine schriftliche Ausarbeitung (Dokumentation). Die schriftliche Ausarbeitung ist in Papierform und elektronisch (PDF, PS, LaTex) abzugeben.
Allgemein:	Keine Angaben.

 
 
 

AK, 27.09.00