(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:
- Durch eine neuartige abstrakte Maschine (VAM-Vienna Abstract Machine [Kral88])
können Programme in Zwischencodedarstellung besonders effizient interpretiert
werden. Nichtdeterministische Programme werden insbesondere bei shallow
backtracking schneller exektuiert als durch ein auf dem üblichen
Implementierungsmodell (WAM-Warren Abstract Machine [War77,83]) basierendes
System, auch wenn die WAM-Instruktionen inline übersetzt werden; die
Prologprogramme also direkt in Maschinensprache übersetzt werden. Eine genaue
Analyse der WAM bezüglich ihres Speicherverhaltens findet sich in [Tick88]. Die
typischen Anwendungen von Prolog, Expertensysteme, natürlichsprachige
Schnittstellen, verwenden derartig große Programme, daß inline expansion den
Platzbedarf und das paging im virtuellen Speicher zu stark erhöhen würde. In
[Dem89] wurde dies vor kurzem diskutiert.
- Die Unifkation ist in VIP für einen gesonderten Datentyp -der Metastruktur
[Neum88]- von Prolog aus programmierbar. Gleichungsorientierte Sprachen nach
dem CLP (constraint logic programming)-Schema können so vom Prologprogrammierer
realisiert werden, ohne den eigentlichen Interpreter zu verändern. Herkömmliche
Prologprogramme können dennoch mit der bisherigen Effizienz interpretiert
werden.
- Um von Prolog aus Datenbanken ab dem Gigabytebereich effizient verwenden zu
können, wurde eine nichtdeterministische Schnittstelle implementiert, durch die
Iteratoren dargestellt werden können, die unabhängig von der Implementierung der
Zugriffe die Lösungsmengen entweder über die Wiedererfüllung eines
Datenbankprädikats oder über Vorwärtsrekursion als ein Objekt (z.B. Liste), das
aber erst durch Unifizieren bekannt wird, dem Prologsystem übergeben. Durch die
Verwendung von mittels Metastrukturen realisierter constraints können
Filestrukturen, die Abfragen in Bereichen (range queries) oder Hierarchien
unterstützen, transparent verwendet werden.
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.