(Bilder, die momentan hier noch nicht vorhanden sind, scheinen als auf.)

DIPLOMARBEIT

Speicherbereinigung für Prologsysteme

ausgeführt am Institut für Praktische Informatik der Technischen Universität Wien
unter Anleitung von
o. Prof. Dipl. Ing. Dr. techn. M. Brockhaus
und
Univ.-Ass. Dipl.-Ing. Dr. techn. A. Krall
als verantwortlich mitwirkendem Universitätsassistenten

durch

Ulrich Neumerkel
Theresianumgasse 3/33
A-1040 Wien

1. Auflage: Wien, 16. Mai 1989: 6 Exemplare Format A4, McWrite
2. verbesserte Auflage: Wien, 9. Feber 1990: 5 Exemplare Format A5, McWrite
3. verbesserte Auflage: Wien, 11. Feber 1991: Umstellung auf Latin-1-Text
4. Auflage: Wien, 7. Feber 1995: Als html-Dokument

Kurzfassung

In dieser Diplomarbeit werden die bekannten Verfahren zur Speicherbereinigung (garbage collection) auf ihre Verwendbarkeit für Prolog im allgemeinen und VIP (Vienna Integrated Prolog) im besonderen überprüft. Es wurde ein neues inkrementelles Verfahren entwickelt, das nicht nur den Platzbedarf stärker reduziert als bisherige aus der Literatur bekannte Verfahren, sondern dadurch auch die Ausführungsgeschwindigkeit des Prologinterpreters erhöht. Zur Kompaktierung von Speicherzellen wird ein auf Morris I [Mor78] basierender neuer Algorithmus vorgestellt, der auf die Besonderheiten der Prolog-Datenstrukturen eingeht.

Inhaltsverzeichnis

Kurzfassung 1
Inhaltsverzeichnis 2
1 Einleitung 5
2 Prologsysteme 7
3 Verfahren zur Speicherbereinigung 21
4 Implementierung für VIP 45
5 Zusammenfassung 72
Literatur 73
Kurzfassung 1
Inhaltsverzeichnis 2
1 Einleitung 5
2 Prologsysteme 7
2.1 Entwicklung von Prolog 7
2.1.1 Système-Q 7
2.1.2 Prolog 0 8
2.1.3 Prolog und Logik 10
2.2 Vergleich der Spracheigenschaften 10
2.2.1 Referenzielle Transparenz 10
2.2.2 Metasprachlichkeit 11
2.2.2.1 Prolog 12
2.2.2.2 Funktionale Sprachen 12
2.2.2.3 Imperative Sprachen 12
2.2.2.4 Maschinensprachen 12
2.3 Prologs Implementierungsmodell 13
2.3.1 Deterministisches Prolog 13
2.3.2 Nichtdeterministisches Prolog 13
2.4 Anforderungen an die Speicherverwaltung 13
2.4.1 Zeitliches Speichermodell 14
2.4.2 Flüchtige Datenstrukturen 14
2.4.2.1 Implementierungskosten 14
2.4.2.2 Beispiele 16
2.4.2.2.2 Metainterpreter 16
2.4.2.2.2 Matrizenmultiplikation 18
2.4.2.2.3 Sortieren 18
2.4.2.3 Unterstützung des Programmierstils 19
2.4.3 Permanente Datenstrukturen 19
2.4.4 Redundante Darstellung 20
3 Verfahren zur Speicherbereinigung 21
3.1 Problemstellung 21
3.2 Verteilte Speicherbereinigung 22
3.3 Feststellung der Referenzierbarkeit 22
3.3.1 Durchwandern mittels Tiefensuche 22
3.3.2 Deutsch-Schorr-Waite 24
3.3.2.1 Herleitung nach Derschowitz 24
3.3.2.1.1 Elimination der Parameter und lokalen Variablen 24
3.3.2.1.2 Elimination der Rekursion 25
3.3.2.2 Herleitung nach Broy und Pepper 25
3.3.2.2.1 Lastcall- Optimierung 26
3.3.2.3 Vermeidung des Zählers 26
3.3.3 Durchwandern mittels Breitensuche 26
3.3.4 Referenzzähler -- ein verzögertes Markieren 26
3.3.4.1 Ein-Bit 27
3.3.4.2 Gewichtete Referenzzähler 27
3.3.4.3 Verallgemeinerte Referenzzähler 28
3.3.4.4 Deutsch-Bobrow 28
3.4 Verfahren zur Speicherrückgabe 29
3.4.1 Mark and sweep 29
3.4.1.1 Dijkstras On-the-Fly 30
3.4.1.2 Abraham und Patel 31
3.4.2 Kompaktierende Algorithmen 31
3.4.3 Knuths LISP 2 31
3.4.4 Table Compactors, Haddon & Waite, Wegbreit 31
3.4.5 Edwards Kompaktierer 32
3.4.6 Kopieralgorithmen 33
3.4.6.1 Minsky 33
3.4.6.2 Fenichel-Jochelson - Twospace Kompaktierung 33
3.4.6.3 Scavenging Algorithms 34
3.4.6.3.1 Bakers Kopieralgorithmus 34
3.4.6.3.2 Ringkompaktierung 34
3.4.6.3.3 Liebermann und Hewitt 35
3.4.6.3.4 Ungar generation scavenging 35
3.4.6.4 Anwendungen 36
3.4.7 Zeigerumkehrtechniken 36
3.4.7.1 Auffädelung 36
3.4.7.2 Morris I 38
3.4.7.3 Jonkers 41
3.4.7.4 Dewar-McCann 41
3.4.7.5 Thorelli 41
3.4.7.6 Morris II 42
3.4.7.7 Vergleich 43
3.4.8 Aufwand 44
4 Implementierung für VIP 45
4.1 Voraussetzungen für eine Speicherbereinigung in VIP 45
4.1.1 VAM vs. WAM 45
4.1.2 Zwischencode und Stackframes 49
4.1.2.1 Erweiterung der Stackframes 49
4.1.2.2 Erweiterung des Zwischencodes 50
4.1.3 Dynamische Datenbankprädikate 50
4.1.4 Metastrukturen 51
4.1.5 Aufbau der Datenstrukturen 55
4.1.6 Speicherung der Datenstrukturen 56
4.1.7 Eigenschaften der Datenstrukturen 57
4.1.8 Zeigerrichtung 58
4.2 Markierung 59
4.2.1 Kompaktierung des Trail 59
4.2.2 Umformung von Variablenreferenzen 60
4.2.3 Markierung des Environments 61
4.2.4 Kompaktierungsalgorithmen 61
4.2.4.1 Adaptiver Algorithmus mittels Morris I, Morris I+II 61
4.2.4.2 Vergleich Morris I+II vs. Lisp 2 62
4.2.4.3 Wegbreit 63
4.3 Inkrementelle Speicherbereinigung 64
4.3.1 Inkrementelle Erkennung 64
4.3.2 Generationen durch Wahlpunkte 64
4.3.3 Künstliche Wahlpunkte 65
4.4 Faltung von Datenstrukturen 65
4.4.1 Problemstellung 65
4.4.2 Sprache der sichtbaren Terme 66
4.4.3 Repräsentation der Terme als DFA 67
4.4.4 Minimierung der Zustände 67
4.4.5 Vorteile der referenziellen Transparenz 69
4.4.6 Unendliche Datenstrukturen 69
4.5 Inkrementelle Faltung 69
4.6 Lokalität der Terme 70
4.7 Vergleich mit existierenden Implementierungen 70
4.7.1 Bruynooghe 70
4.7.2 Garbage Cut 71
4.7.3 Appleby et al. 71
4.7.4 Das MALI-System 71
5 Zusammenfassung 72
Literatur 73

1 Einleitung

Das am Institut für Praktische Informatik entwickelte Prologsystem VIP zeichnet sich durch folgende Eigenschaften aus: Während der Bearbeitung komplexer dynamischer Datenstrukturen ist es meist nicht möglich, die Zeitdauer, wie lange man diese Strukturen zur Berechnung benötigt, zum Zeitpunkt der Entwicklung oder Übersetzung des Programms zu bestimmen. Zudem ist das ausdrückliche Überschreiben von Datenstrukturen eine mögliche Fehlerquelle in imperativen Programmiersprachen. Die Verwaltung derartiger Datenstrukturen wird daher häufig vom Betriebssystem bzw. Laufzeitsystem durchgeführt. So ist es bei der Verwendung von files nicht erforderlich, den durch sie benötigten Platz zu verwalten. In Programmiersprachen wie Smalltalk, Lisp, Snobol oder Prolog wird die Verwaltung der dynamischen Datenstrukturen durch das Laufzeitsystem verwirklicht. Es ist dem Programmierer hier möglich, neue Datenstrukturen (bzw. Terme, Ausdrücke, Objekte, Symbole) zu erzeugen, aber unmöglich, sie explizit freizugeben. Die Speicherbereinigung ermöglicht es, den Platz für die nicht mehr benötigten Strukturen für das Anlegen neuer Strukturen zu verwenden.

In Kapitel 2 wird die Programmiersprache Prolog aus ihrer geschichtlichen Entwicklung heraus vorgestellt und auf einige wichtige Spracheigenschaften, der referentiellen Transparenz von Termen und der Unterstützung von metasprachlichen Abstraktionen, eingegangen. Durch das Implementierungsmodell von Prolog und durch typische Programme wird gezeigt, welche Aufgaben eine Speicherbereinigung in Prolog zu erfüllen hat. Das aus [Un87] bekannte zeitliche Speichermodell wird verwendet, um die Anforderungen genauer zu präzisieren: Eine Speicherbereinigung muß vor allem flüchtige (kurzlebige) Datenstrukturen effizient verwalten können.

Kapitel 3 führt die bisher entwickelten Verfahren zur Speicherbereinigung im allgemeinen an. Kapitel 4 geht auf VIP genauer ein, um die wichtigsten Eigenschaften des Systems bezüglich einer Speicherverwaltung herauszustellen. Es wird ein neues Markierungverfahren vorgestellt, das im Gegensatz zu den aus der Literatur bekannten Verfahren [Bru84,Pit87,Appleby88] von den ältesten Wahlpunkten aus mittels virtual backtracking die benötigten Datenstrukturen nicht nur markiert, sondern auch vereinfacht. Dadurch kann die Menge der verbleibenden Datenstrukturen besser reduziert werden, da Ketten, die durch shared variables entstehen, vollständig aufgelöst werden können. Auch die Ausführungsgeschwindigkeit des Interpreters wird nach einer Speicherbereinigung erhöht werden, da diese Ketten nicht mehr durchlaufen werden müssen. Dieses Problem wurde im Zusammenhang mit Prolog in der Literatur noch nicht erkannt. Ein ähnlicher Ansatz, die erreichbaren Datenstrukturen nicht einfach zu markieren, sondern auch zu vereinfachen, konnte nur im Bereich der Implementierung von Funktionalen Sprachen gefunden werden [Wad87]. Alle aus der Literatur bekannten Algorithmen zur Speicherbereinigung für Prologsysteme werden bei dem hier aufgezeigten Fall keine Speicherzellen freigeben können.

Um permanente Datenstrukturen nicht bei jeder Speicherbereinigung markieren zu müssen, wird eine inkrementelle Variante vorgestellt, die ähnlich [Pit87] auf dem Verfahren von Liebermann und Hewitt [Lieb83] beruht und wie [Pit87] die Laufzeit des Interpreters nicht beeinträchtigt. Da nur die Variablen von Prologtermen verändert werden können, muß man in Prolog gleiche Terme nur genau einmal repräsentieren. Ein Algorithmus, der im Wesentlichen auf der Minimierung der Zustände eines endlichen Automaten beruht, sowie eine inkrementelle Variante wurden entwickelt. Man kann so zusichern, daß identische Terme nur genau einmal im Speicher repräsentiert werden. In der Literatur finden sich im Zusammenhang mit Algorithmen zur Speicherbereinigung keinerlei Hinweise auf diese Problemstellung. Im besten Fall ist es so möglich, den benötigten Speicherplatz von n Zellen auf ld(nP1) zu reduzieren. Dadurch wird die Lokalität des Interpreters verbessert und bei virtuellem oder mit cache erweitertem Speicher die Ausführungsgeschwindigkeit erhöht.