4 Implementierung für VIP

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

4 Implementierung für VIP

Das Projekt VIP wurde anfangs [Oppi85] mit der Zielsetzung in Angriff genommen, ein Prologsystem zu entwickeln, das über eine vollständige integrierte Umgebung, die den eigentlichen Kern, die Programmiersprache mit einer großen Menge von nützlichen Werkzeugen umgibt, verfügen sollte. Es waren etwa ein syntaxgesteuerten Editor, ein integrierten Debugger, ein Parser Generator und eine natürlichsprachigen Schnittstelle zur eigentlichen Sprache geplant, die aber nur zum Teil tatsächlich realisiert wurden—jedenfalls nicht lange weiter verfolgt wurden. Zum Teil sind auch viele dieser ursprünglichen Ziele, etwa das Windowsystem, das unter GEM realisiert wurde, auf neueren Systemen direkt vom Betriebssystem verwirklicht.

VIP als integriertes System

Bei den Entwicklungen beschränkte man sich daher auf die für Prolog spezifischen Teile des Projektes; der Entwicklung einer neuartigen Interpretertechnik [Kral87], der Realisierung einer effizienten Symbol- und Regelverwaltung [Punt89], der Unterstützung von gleichungsorientierten Erweiterungen für Prolog [Neum88], sowie der Unterstützung von Datenbanken [Küh89], insbesondere für Expertensysteme.

4.1 Voraussetzungen für eine Speicherbereinigung in VIP

In Kapitel 4.1 werden jene Eigenschaften des Systems beschrieben, die für eine Speicherbereinigung von Bedeutung sind, um dann in den weiteren Kapiteln die verschiedenen Algorithmen zu beschreiben.

4.1.1 VAM vs. WAM

Sieht man von VIP ab, basieren alle existierenden effizienten Implementierungen von Prologsystemen auf der von David H.D. Warren entworfenen abstrakten Maschine [Warr83]. Es gibt zwar auch einige andere, doch unterscheiden sich diese Modelle nur marginal von der WAM. Die WAM wird gerne als die Standardimplementierungstechnik für Prolog bezeichnet. Die Inferenz innerhalb der WAM ist einem Prozeduraufruf vergleichbar. Nicht ohne Grund weist [Co83b] darauf hin, daß man das Beweisen eines Ziels auch als Folge von Prozeduraufrufen der Unterziele im Rumpf der entsprechenden Klausel verstehen kann. Cohen [Co83b] stellt Prolog-Programme auch direkt Pascal-Programmen gegenüber. Wie die prozeduralen Sprachen, muß auch die WAM die einzelnen Argumente auf einen Stack legen, bzw. den Registern zuweisen, damit sie von der "aufgerufenen Prozedur", dem entsprechenden Prädikat verarbeitet werden können. Die in den Argumenten dargestellten Datenstrukturen können selbst wieder Datenstrukturen enthalten (z.B. Listen). Dadurch ist es erforderlich derartige Datenstrukturen auf einen eigenen Stack zu legen. Die darzustellenden Terme können nun Konstanten oder Variablen sein, sie werden dann in der Speicherzelle selbst dargestellt, oder aber Strukturen, dann enthält die entsprechende Speicherzelle eine Referenz auf die eigentliche Struktur. Die wesentlichste Eigenschaft ist die klare Trennung zwischen der Parameterübergabe vom Aufrufer, dem aktuellen Ziel (put-Instruktionen), und der Übernahme vom Aufgerufenen (get-Instruktionen), dem Kopf einer Klausel des entsprechenden Prädikats. Sehr gut lassen sich die meisten Vorteile der WAM an append/3 zeigen, daß im bekanntesten Prolog-Benchmark, dem naive reverse Verwendung findet. Der Vermutung, die WAM wäre genau für diesen Benchmark konzipiert, kann ja kaum widersprochen werden. Die WAM arbeitet mit festgelegten Registern, die bei entsprechenden Wahlpunkten oder Prozeduraufrufen, die nicht an letzter Stelle stehen, in einer Klausel am Copystack gesichert werden müssen (put_unsave). 
append([],     get	 Y0, const([])
Xs,	       %get	 Y1, var(Y1) % erstes Vorkommnis
Xs).	       get	 Y2, val(Y1) % unifiziere Y1 mit Y2
	       proceed		     % es gibt noch eine Alternative
append([X|Xs], get_list Y0, var(Y3), var(Y0)
Ys,	       %get	 Y1, var(Y1)
[X|Zs]) :-     get_list Y2, val(Y3), var(Y2)
append(			
Xs,	       %put	 Y0, val(Y0)
Ys,	       %put	 Y1, val(Y1)
Zs).	       %put	 Y2, val(Y2)
				execute append/3
	WAM-Code für append/3

Der große Vorteil der WAM liegt also in der Entfernung redundanter Operationen bei simplen Programmen.

Die VAM faßt zwar die einzelnen Ziele auch als Prozeduraufrufe auf, unterläßt allerdings die Übergabe der Parameter, diese werden einzeln mit den Argumenten des Aufrufers unifiziert. Ein Argument wird also erst dann sichtbar, wenn das vorhergehende Argument unifiziert worden ist. Damit wird die Übergabe der Argumente und die Unifizierung derselben verzahnt ausgeführt. Dies hat den großen Vorteil, daß ... 1. ... die Dekodierung während der Parameterübergabe und der Unifikation genau einmal erfolgt, durch die Technik des direct threaded code wird die VAM als Interpreter genauso schnell wie die WAM als Compiler. 2. ... mehr Information über diese Schnittstelle hinweg übergeben wird, insbesondere kann eine wesentlich differenzierte Behandlung von Variablenbindungen erfolgen, was die zu registrierenden Bindungen drastisch reduziert, sowie die Anzahl der auf dem Copystack angelegten Datenstrukturen vermindert. Im obigen Beispiel wird z.B. bei der 2. Anfrage kein einziges Element auf einen Stack gelegt. 3. ... keine Argumentregister benötigt werden und dadurch das aufwendige Sichern beim Anlegen von Wahlpunkten wegfällt. In [Tick88] findet sich eine Analyse der WAM mit dem Schluß, daß das Anlegen von kurzlebigen Wahlpunkten—shallow backtracking—das Verhalten des Kontrollfluß wesentlich beeinträchtigt. Etwa 46% der dynamischen Speicherreferenzen gingen zu Lasten der call/fail-Operationen. 

append([],	const empty
Xs,		firsttemp0
Xs).		temp0
		nocall

append([X|	listfirsttemp0
Xs],		firstvar 1
Ys,		firstvar 2
[X|		listtemp0
Zs]) :- 	firstvar 3
append(		goal append/3
Xs,		var 1
Ys,		var 2
Zs).		var 3
		lastcall
VAM-Code für append/3
In der VAM können die entsprechenden Instruktionen ad hoc nicht gefaltet werden. Da es allerdings häufig der Fall ist, daß ein deterministischer rekursiver Aufruf derselben Klausel auftritt, werden in einer erweiterten Version auch derartige Fälle unterstützt werden.

Die für die Speicherbereinigung relevanten Unterschiede betreffen vor allem die Menge der am Copystack anzulegenden Datenstrukturen. Während die VAM zur gleichen Zeit die Argumente des Aufrufers sowie des Aufgerufenen "sieht", muß die WAM stets durch die Register die Argumente "durchschleußen"; Dies kann solange sehr effizient realisiert werden, solange Parameter, die bereits auf existierende Terme am Copystack verweisen, übergeben werden. Beim allgemeinen Fall der Unifikation stellt sich diese Eigenschaft jedoch als Flaschenhals heraus. Der Aufgerufene kann nicht mehr feststellen woher und in welcher Form die Parameter übergeben wurden. Dadurch, daß bei einem Prozeduraufruf eine einheitliche Schnittstelle existiert, erfolgen in den folgenden beiden Beispielen dieselben Operationen innerhalb von q/1. 

q(s(a)).
:- X = s(a), q(X).
:- q(s(a)).

Die WAM muß bei beiden Anfragen die Struktur s(a) anlegen, bevor q/1 aufgerufen wird. Zudem müssen noch benötigt Argumentregister am Copystack gesichert werden.

Inferenz in der WAM: Vor Aufruf eines Ziels müssen u.U. Argumentregister gesichert werdeN

Die VAM wird im Gegensatz dazu die erste Anfrage, wie auch die WAM durch Unifikation der am Copystack angelegten Struktur realisieren, während in der zweiten Anfrage der Interpreter sofort erkennen kann, daß Ziel und Faktum miteinander übereinstimmen, ohne auch nur eine einzige Zelle am Copystack anzulegen.

Inferenz in der VAM

Die Nachteile der VAM betrafen bisher die recht langsame Implementierung der tail-end recursion-Optimierung, die im naive-reverse Benchmark und anderen rein deterministischen Programmen voll zum Tragen kommt. In der verbesserten Version der VAM wurden eigens Faltungen für Direktrekursion implementiert, sodaß diese Fälle noch effizienter als in der WAM realisiert werden. Ein weiterer Nachteil ist die Tatsache, daß die VAM kaum Terme in Hardwareregistern halten kann, die WAM dagegen übergibt einige Argumente in Hardwareregistern, andere WAM-Register über fixe Adressen. Dies beschleunigt abgesehen vom Wegfallen einiger Instruktionen zwar gewisse Operationen, nichtdeterministische Programme werden dadurch aber besonders langsam, da ja die Register gerettet werden müssen. Auch in der bisherigen Implementierung war daher die VAM in extrem nichtdeterministischen, aber rekursiven Benchmarks (z.B. 8-queens) doppelt so schnell, wie die entsprechenden compilierten WAM-Programme. Betrachtet man die Entwicklung auf dem Mikroprozessormarkt, so sind Zweifel angebracht, ob derartige Register-Optimierungen auf neueren Maschinen überhaupt noch von Softwareherstellern berücksichtigt werden sollen. Durch caching kann dies von der Hardware meist besser realisiert werden. Da ja auch Variablen, die in Registern gehalten werden, aufeinander zeigen könnten, muß die WAM im Falle eines Prozeduraufrufes innerhalb des Rumpfs diese Variablen auf referenzierbaren Speicher auslagern (put_unsave). Dies ist bei der VAM nicht erforderlich. Zusammenfassend kann man also sagen, daß die VAM mit wesentlich weniger Speicherzellen am Copystack und Trail auskommt als die WAM. Insbesondere wird

Die VAM benötigt immer weniger Speicherplatz auf Copystack und Trail als die WAM, auf dem Environmentstack (zur Verwaltung der lokalen Variablen und der Backtrackpunkte) könnten dieselben Optimierungen angewendet werden, wie sie auch bei einigen wenigen Implementierungen der WAM Gebrauch finden. In dieser Arbeit beschäftigen wir uns aber ausschließlich mit erstgenannten Stacks, da sie für die meisten Anwendungen besonders kritisch sind. Die wesentlichste Optimierung für den Environmentstack (tail-end) wurde bereits implementiert, weitere Optimierungen (stack trimming) würden eine Verminderung des Speicherverbrauchs am Environementstack im Prozentbereich ergeben.

4.1.2 Zwischencode und Stackframes

Ein weiterer für die Speicherbereinigung wichtiger Aspekt ist die Beschaffenheit des Zwischencodes und der Stackframes. Die meisten WAM-Implementierungen sichern zu, daß sämtliche in einer Klausel verwendeten Variablen bereits nach sämtlichen get-Instruktionen vollständig initialisiert sind. In der VAM kann dies nicht zugesichert werden, dadurch kann die VAM zwar viele unnötige Trail-Operationen vermeiden, bei einer Speicherbereinigung ist es aber erforderlich, den Zwischencode von der aktuellen Stelle aus bis an das Ende der Klausel zu lesen. Aus diesem Grund wurden Überlegungen angestellt den Zwischencode oder die Stackframes derart zu erweitern, daß zum Zeitpunkt der Speicherbereinigung der Zustand des Stackframes sofort erkannt werden kann.

4.1.2.1 Erweiterung der Stackframes

Jede Variable in einem Stackframe könnte dynamisch auch den Wert "undefiniert" besitzen, der beim Anlegen des Stackframes initialisiert werden würde. Durch ein Bitfeld im Stackframe wäre dies ebenfalls sehr einfach zu realisieren. Bei jedem first- Vorkommnis einer Variable im Rumpf einer Klausel würde das entsprechende Bit gesetzt werden. Der Nachteil dieser Variante liegt vor allem darin, daß bei erfolgtem Backtracking auch dieser Wert zurückgesetzt werden müßte. Diese Erweiterungen würde also die first- Instruktionen im Rumpf wesentlich aufwendiger machen, zudem müßte jedes Vorkommnis am Trail durch einen von den gewöhnlichen Bindungen unterschiedlich angemeldet werden, sodaß dadurch auch mehr Platz am Trail und somit am Copystack verloren geht und auch das in der VAM sehr schnelle Backtracking verlangsamt wird.

4.1.2.2 Erweiterung des Zwischencodes

Naheliegend wäre die gerade aktiven Zellen bei jedem Unterziel einer Klausel zu bezeichnen. Dies kann ja bereits statisch festgestellt werden. Für die meisten Klauseln würde etwa ein Bitfeld in einem Wort dafür völlig ausreichen. Dieses Wort würde man nach dem Ende eines jeden Ziels in den Zwischencode einfügen. Die Größe der Darstellung einer Klausel würde dadurch um weniger als 10% anwachsen, der Interpreter müßte allerdings nach jedem bewiesenen Ziel dieses Wort überspringen.

Zusammenfassend läßt sich sagen, daß die Darstellung des Zwischencodes in der VAM für die Speicherbereinigung auf alle Fälle von Nachteil ist. Jede der in Betracht gezogenen Erweiterungen würde einen vermehrten Platzverbrauch, aber auch einen größeren Interpretationsaufwand mit sich führen. Da die Speicherbereinigung gerade in Prolog nur die dynamischen Datenstrukturen erfaßt, die Datenbasis kann ja völlig unabhängig realisiert werden, und die VAM ohnehin weniger flüchtige Zellen produziert als die WAM, wurde von einer derartigen Erweiterung vorerst abgesehen. Die meisten Programme bestätigen die Annahme, daß die Fortsetzung nach einem Unterziel im Rumpf—wenn überhaupt—aus zwei bis drei weiteren Zielen besteht. Anstatt dessen wird in Kapitel 4.2 und 4.3.2 ein Markierungsverfahren und eine inkrementelle Variante vorgestellt, durch die sich dieser Aufwand wesentlich besser reduzieren läßt. So ergeben sich für Programmteile, die keinerlei Speicherbereinigung in Anspruch nehmen, keine Nachteile.

4.1.3 Dynamische Datenbankprädikate

In der ursprünglichen VIP-Version wurde eine eingeschränkte immediate update view implementiert [Kral88]. Durch eine eigene Deklaration konnte man auch zusichern, daß für ein bestimmtes Prädikat die vollständige immediate update view zugesichert werden kann, folgendes Ziel also erfüllt werden kann. 
a :-
	assert(a),
	fail.
:- a.

Durch die Arbeiten der ISO WG17 und vor allem durch den Artikel von Richard O'Keefe [LiKe87] wird nun für sämtliche Prädikate die logical update view unterstützt. Dadurch kann jedes Ziel im Moment seiner Ausführung bereits vollständig verstanden werden. Jedes Prolog-Unterziel im Rumpf einer Klausel könnte, abgesehen von den durch !/0 möglichen Seiteneffekten, durch das Durchsuchen sämtlicher im Moment sichtbarer Alternativen unter Annahme der immediate update view ersetzt werden. 

			... ,
			findall(pair(X,B),clause(p(X),B),L),
... , p(X), ... <==>	member(pair(X,B),L),
			B, ...
Simulation der logical update view mittels der immediate update vieW

Dadurch ergeben sich nicht nur für die Optimierungstechniken des Interpreters einfachere und klarer definierbare Rahmenbedingungen, sondern auch bessere Voraussetzungen für die Implementierung der Speicherbereinigung.

Bei Prozeduren, die vom Prologprogrammierer aus gesehen deterministisch sind, die aber nicht durch clause indexing deterministisch gemacht werden können, entstehen unerkannte Wahlpunkte. Dadurch können Programme, die sonst mit lastcall-Optimierung arbeiten könnten, den gesamten Environmentstack aufbrauchen, und dadurch auch eine Speicherbereinigung am Copystack verhindern. Eine entsprechende Speicherbereinigung am Environmentstack kann diese Wahlpunkte erst durch die Semantik der logical update view ausschließen, und dadurch auch Speicherzellen am Copystack freigeben.

4.1.4 Metastrukturen

Um durch VIP auch den gerade in der Forschung momentan aktuellen Erweiterungen von Prolog in Richtung einer gleichungsorientierten Sprache gerecht zu werden, wurde in [Neum88] eine Erweiterung entwickelt, die es ermöglicht, mit demselben erweiterten Interpreter alle Sprachen aus der Klasse der CLP-Sprachen (constraint logic programming) [JaLa87], in Prolog zu realisieren. Die Erweiterung selbst sieht einen neuen Datentyp -die Metastruktur- vor, die sich während der Unifikation unterschiedlich von gewöhnlichen Termen verhält. Dadurch wird die Unifikation in Prolog gleichsam "programmierbar". Eine Metastruktur sieht aus wie ein gewöhnlicher Funktor: meta(Value,Property1, ..., Propertyn)

Dabei hat das erste Argument eine besondere Bedeutung: Falls es bereits instanziert ist, ersetzt dieser Wert die gesamte Metastruktur. Die folgenden Terme sind also bezüglich der erweiterten Unifikation stets äquivalent:

meta(a,p(X)) = a

Metastrukturen müssen zumindest dieses eine Argument besitzen. Die darauffolgenden Argumente sind vom Programmierer der Metastrukturen, wie auch bei einem gewöhnlichen Prädikat, frei wählbar; ebenso der Name der Metastruktur. Der Einfachheit halber wird hier nur der Funktor meta verwendet. Die Metastrukturen können so eine beschränkte Form der Evaluierung, wie sie ja beim Lösen von Gleichungssystemen vorkommt, unterstützen. Verglichen mit dem Verhalten von gewöhnlichen Prologtermen müssen einige neue Fälle in Unifizierer des Systems eingebracht werden:

Unifikation, um Metastrukturen erweitert; die mit $ gekennzeichneten Fälle wären beim herkömmlichen Implementierungsansatz etwa [Chane86] ebenfalls betroffeN

Die neue Unifikation unterscheidet sich also in nur wenigen Punkten von der herkömmlichen Prolog-Unifikation: Metastrukturen verhalten sich genauso wie gewöhnliche Strukturen bei der Unifikation mit einer Variable. Nur wenn eine Metastruktur mit einer gewöhnlichen Struktur unifiziert wird, oder zwei Metastrukturen miteinander unifiziert werden, werden die vom Benutzer definierten Prädikate betrachtet. Der Interpreter kann daher die besonders zeitkritischen Operationen genauso effizient wie in einem gewöhnlichen Prologsystem realisieren. Das "Übergeben" eines instanzierten Terms an eine Variable etwa, das bei jedem Prozeduraufruf durchgeführt wird, wird durch diese Erweiterung nicht beeinträchtigt. Metastrukturen, die nicht mehr aktiv sind, können unabhängig von den gegebenen Definitionen des Benutzers vom Interpreter erkannt werden. Dadurch kann das "Ergebnis" einer über constraints erfolgten Berechnung wie ein gewöhnlicher Prologterm weiterverwendet werden, ohne von den Definitionen der constraints nach der Instanzierung abzuhängen. Diese Ergebnisse können dann vergleichbar schnell, nach einer Speicherbereinigung genauso schnell interpretiert werden, wie gewöhnliche Terme.

Der aus [StSh86] bekannte Metainterpretationsmechanismus wird durch um ein neudefiniertes Unifikationsprädikat erweitert. Das Prädikat meta_unify/2 erfüllt diesen Zweck. Um Metastrukturen in einem Standard-Prologsystem darzustellen, werden die Funktoren mit dem Namen meta als Metastrukturen angenommen. 

ismeta(X) :-
	nonvar(X),
	functor(X,meta,_).

Die Prädikate term_meta_unify/2 und meta_meta_unify/2 sind vom Benutzer programmierbar und beschreiben die Unifikationsmethode für zwei Metastrukturen, bzw. für eine Metastruktur mit normalen Prologtermen. 

meta_unify(V,W) :-
	( var(V); var(W) ),
	!,
	V = W.
meta_unify(V,W) :-
	unused_meta(V,VNew),
	!,
	meta_unify(VNew,W).
meta_unify(V,W) :-
	unused_meta(W,WNew),
	!,
	meta_unify(V,WNew).
meta_unify(V,W) :-
	active_meta(V,VN),
	active_meta(W,WN),
	!,
	(	V == W,
		!
	; 	VN = W,
		meta_meta_unify(WN,V,W)
	).
meta_unify(V,W) :-
	active_meta(V,VN),
	!,
	VN=W,
	term_meta_unify(W,V).
meta_unify(V,W) :-
	active_meta(W,WN),
	!, WN=V,
	term_meta_unify(V,W).
meta_unify(V,W) :-
	V =.. [F|VL],
	W =.. [F|WL],
	meta_unify_list(VL,WL).

meta_unify_list([],[]).
meta_unify_list([V|VR],[W|WR]) :-
	meta_unify(V,W),
	meta_unify_list(VR,WR).

unused_meta(V,VN) :-
	nonvar(V),
	functor(V,MetaName,_),
	ismetaname(MetaName),
	arg(1,V,VN),
	nonvar(VN). % Variable instanziert
active_meta(V,VN) :-
	nonvar(V),
	functor(V,MetaName,_),
	ismetaname(MetaName),
	arg(1,V,VN),
	var(VN).                % Variable nicht instanzierT

Es wird eine Implementierung des Prädikates freeze/2 (geler/2) angegeben, das dieselbe Semantik wie in Prolog-II [Chane86] haben soll: freeze(Variable, Goal).

Die Ausführung des Ziels Goal wird bis nach dem Zeitpunkt verschoben, da Variable instanziert ist. Vergleichbare Ideen finden sich in delay/2 [Carl87], den wait Deklarationen des Mu-Prolog [Nais86] und der erweiterten Variante: Nu-Prolog [ThZo87]. Man bindet Goal an die Variable. Falls diese mit einem nicht variablen Term unifiziert werden solltem, wird das Ziel Goal ausgeführt. Man bindet daher die Variable an eine Metastruktur, die als zweites Argument das eigentliche Ziel enthält: 

freeze(V,G) :-
	V = meta(_,G).
Bei Unifikation der Metastruktur mit einem Term wird das Ziel ausgeführt: 
term_meta_unify(M,T) :-
	M = meta(X,G),
	G.

Falls zwei Metastrukturen miteinander unifiziert werden, wird eine neue Metastruktur gebildet, die die Konjunktion der beiden darstellt. Es wird also ein neues Ziel erzeugt, das aus den Teilzielen der beiden Metastrukturen gebildet wird: 

meta_meta_unify(V,M1,M2) :-
	M1 = meta(X1,G1),
	M2 = meta(X2,G2),
	V = meta(_,(G1,G2)).

Die durch den Metainterpreter definierte operationale Semantik würde erfordern, daß während der Unifikation ein aufgeschobenes Ziel ausgeführt werden könnte. Bei einer direkten Implementierung im Interpreter möchte man aber vermeiden, daß die Unifikation des Ziels und des Kopfes eines Klausel unterbrochen wird, weil sonst temporäre Variablen gerettet werden müßten. Existierende Systeme, wie etwa Prolog II, das die Prädikate freeze/2 und dif/2 anbietet, schieben die Ausführung von durch freeze/2 verursachte Ziele auf den Zeitpunkt nach der Unifikation auf, während durch dif/2 eingeschränkte Variablen auf ihre Unifizierbarkeit bereits während der Unifikation überprüft werden. Unterschiedliche Interpretationen könnten sich dadurch ergeben, daß in den neu erzeugten Zielen Variablen vorkommen können, die auch im Kopf der gerade unifizierten Klausel vorkommen, sowie bei Prädikaten mit Seiteneffekten. 

p(a,b).

q(X) :-
	var(X)
	writeln('Ausführung während der Unifikation').
q(X) :-
	nonvar(X),
	writeln('Ausführung nach der Unifikation').

:- freeze(X,q(Y)), p(X,Y).
Beim folgenden Programm werden Metastrukturen mit einem zusätzlichen Ziel aufgebaut. Da zwischen der "Deklaration" der Bedingung und ihrer Ausführung kein Wahlpunkt mehr vorhanden ist, könnten die beiden Strukturen bereits entfernt werden, und die verbleibende Struktur richtiggesetzt werden. Das Prädikat islist/1 sichert zu, daß das Argument eine Liste ist: 
islist(X) :-
	var(X),
	!,
	freeze(X,islist(X)).
islist([]).
istlist([E|L]) :-
	islist(L).
Nach Erfüllung der Anfrage :- islist(L), range(1,2,L). Befinden sich am Copystack die folgenden Strukturen,...

... obwohl nur mehr die erzeugte Liste benötigt wird.

nach der Entfernung der Metastrukturen und der Property-Terme

Gerade beim Lösen von Gleichungen wird der property-Teil der Metastruktur wesentlich größer als die Metastruktur selbst sein. Da dieser Teil aber ein gewöhnlicher Term sein kann, würde eine getrennte Verwaltung der Metastrukturen in einem gesonderten Bereich den Aufwand für die Speicherbereinigung kaum vermindern. Allein wegen der dadurch komplexer werdenden Bindungsoperationen wurde von einer derartigen Variante Abstand genommen. Boizumault schlägt eine derartige Implementierung in [Boi86,Boi86] vor.

Durch Metastrukturen kann also in einem sehr beschränkten Ausmaß eine "destruktive" Zuweisung an eine Variable erfolgen. Häufig kommt es in Anwendungen mit Metastrukturen vor, daß man Variablen schrittweise immer genauer spezifiziert, bis letztendlich ein konkreter Wert für die Variable gefunden werden kann. Dadurch entstehen Ketten von Metastrukturen, die die "Geschichte" der Variable beschreiben: 

meta(
	meta(
		meta(
			meta(Aktuelle_Variable,Zustand4),
		Zustand3),
	Zustand2),
Zustand1).
Diese Zustände können aber nicht vom Benutzer der Metastrukturen gesehen werden. Es ist stets nur der letzte Zustand gültig. Alle vorhergehenden Zustände können daher von der Speicherbereinigung erfaßt werden. In einigen Anwendungen, vor allem bei der Implementierung von Programmiersprachen, die temporales Wissen darstellen, kann man dennoch zeitliche Zustände oder andere Eigenschaften verwalten. Man wird hier eine ähnliche Definition, wie freeze/2 verwenden, die aber bei der Unifkation zweier Metastrukturen überprüft, ob die Eigenschaften der Variablen miteinander vereinbar sind.

Die Metastrukturen stellen eine effizientere Implementierung als [Chan86],[Boi88] dar, obwohl sie wesentlich allgemeiner anwendbar sind. Der Grund liegt in der Darstellung der ausgezeichneten Variablen durch besondere Strukturen. Die hier vorgestellte Erweiterung kann in ein Prologsystem eingebunden werden, ohne daß der Interpretationsmechanismus bei gewöhnlichen Programmen dadurch verlangsamt wird. Im Gegensatz zu [Carl87] kann man das Verhalten der Metastrukturen in Prolog selbst programmieren. Die Speicherbereinigung hat die Möglichkeit nicht mehr aktive Terme zu entfernen.

4.1.5 Aufbau der Datenstrukturen

Die VIP-Implementierung ist darauf ausgelegt, den gesamten 32 Bit Adressierungsraum aktueller Maschinen auszunutzen. Damit wurde ein Format festgelegt, das auch für zukünftige Prozessoren noch lange ausreichen wird. Die Objekte wurden mit einer variablen Tagfieldlänge von 1 bis 3 Bit implementiert. Die Tagfields befinden sich im Vorzeichenbereich. Dadurch kann durch einfache und schnelle Vorzeichenabfragen und Shiftoperationen der Typ eines Objektes analysiert werden. 
31 30 29 28  27 - 24  23 - 16     15 - 0
 0  p  p  p     pppp pppppppp pppppppppppppppp t_ref
 0  0  0  0     0000 00000000 0000000000000000 t_undef
 1  0  0  s     ssss ssssssss ssssssssssssssss t_list
 1  1  0  s     ssss ssssssss ssssssssssssssss t_struct
 1  0  1  l     llll llllllll llllllllllllllll t_short
 1  1  1  0     00aa aaaaaaaa iiiiiiiiiiiiiiii t_atom
 1  1  1  1     1111 11111111 1111111111111111 t_empty

 0  c  c  c     ccaa aaaaaaaa iiiiiiiiiiiiiiii b_funct
 1  1  c  c     ccaa aaaaaaaa iiiiiiiiiiiiiiii b_meta
 1  0  1  1     11aa aaaaaaaa iiiiiiiiiiiiiiii b_lfunct
 1  0  1  1     10-- -------- ffffffffffffffff b_float
 1  0  1  1     01-- -------- llllllllllllllll b_long
t_ref
Referenz; das Value Field enthält einen 31 Bit großen Zeiger auf ein weiteres Wort
t_undef
freie Variable; das gesamte Wort ist 0
t_list
Liste; das Value Field enthält einen 29 Bit großen Zeiger, der um 2 Bit nach links verschoben eine 31 Bit große Adresse ergibt, die auf einen Block von 2 Worten zeigt, der den Kopf und den Rest der Liste enthält
t_struct
Struktur; das Value Field enthält einen 29 Bit großen Zeiger, der um 2 Bit nach links verschoben eine 31 Bit große Adresse ergibt, die auf einen Strukturblock zeigt; der Strukturblock enthält als erstes Wort ein b_functor (Funktor) und cccccc + 1 weitere Worte mit den Argumenten der Struktur
t_short
ganze Zahl; das Value Field enthält eine 29 Bit große Integer Zahl in 2'er Komplementdarstellung
t_atom
Atom; aaaaaaaaaaiiiiiiiiiiiiiiii stellt den 26 bit großen Atomindex dar [Punt89].
t_empty
Leere Liste; das ganze Wort ist 1 (arithmetisch -1)
b_funct
Funktor; ccccc ist die Anzahl der Argumente - 1 als positive 5 Bit Integerzahl dargestellt (1 bis 32 Argumente); Rest siehe atom
b_meta
Metastruktur; cccc ist die Anzahl der Argumente (1 bis 16), danach wie bei b_functor der Atom-Index
b_lfunct
Funktor für große Argumentanzahl; die Anzahl der Argumente steht im folgenden 32 Bit Wort als positive 32 Bit ganze Zahl gespeichert
b_float
Gleitkommazahl; die folgenden zwei Worte enthalten eine 80 Bit Gleitkommazahl in IEEE Format
b_long
große ganze Zahl; die folgenden llllllllllllllll Worte enthalten eine beliebig große ganze Zahl in 2'er Komplementdarstellung

4.1.6 Speicherung der Datenstrukturen

Ähnlich den WAM-basierten Implementierungen gibt es auch im VIP im wesentlichen drei dynamische Stacks. Auf den Environment Stack werden die Stackframes mit Kontrollinformationen und den lokalen Variablen gespeichert. Die von der Speicherbereinigung betroffenen Datenstrukturen befinden sich am Copystack, dort werden ebenso auch die Metastrukturen angelegt. Die Variablenbindungen werden auf dem Trail markiert. Weiters wird noch Speicherplatz für temporäre Variable und den auf Zwischencode übersetzten Prologklausen (heap; Man beachte, daß heap zuweilen auch den Copystack bezeichnet) benötigt. Um die Zeigerrichtung einfach feststellen zu können, sind die verschiedenen Stacks in folgender Reihenfolge angeordnet.

Anordnung der Speicherbereiche in VIP Auf dem Environment Stack ist der Activation Record gespeichert. Es wird zwischen deterministischen und indeterministischen Activation Records (Wahlpunkt) unterschieden. Bei einem deterministischen Activation Record werden die lokalen Variablen, der Zeiger auf den Vorgängerrecord und der Zeiger auf den Fortsetzungszwischencode abgespeichert. Die Zeiger sind nicht nur auf den direkten Vater gerichtet, sie können auch auf einen indirekten Vater zeigen. Bei einem Wahlpunkt werden zusätzlich der Zeiger auf den aufrufenden Activation Record, ein Zeiger auf den Zwischencode des aufrufenden Zieles, ein Zeiger auf die noch existierenden Alternativen, der Zeiger auf den letzten Wahlpunkt, die Spitze des Copystacks und die Spitze des Trails abgespeichert.

Aufbau eines Stackframes und eines Wahlpunktes

4.1.7 Eigenschaften der Datenstrukturen

Vergleicht man die in VIP existierenden Datenstrukturen mit den Zellstrukturen aus Kapitel 3 so können folgende Eigenschaften festgehalten werden:

4.1.8 Zeigerrichtung

Eine wesentliche Eigenschaft betrifft die Zeigerrichtung; ob eher Zeiger von älteren Zellen auf neuere zeigen oder umgekehrt. Dabei hat sich herausgestellt, daß die Richtung der aufgebauten Zeiger vor allem von den verwendeten Programmiertechniken abhängt. Die folgendenden Beurteilungskriterien wurden dabei verwendet:
a) assert/retract-Stil: alt → neu
Viele Prologprogrammierer rechtfertigen die übermäßige Verwendung von assert/2 und retract/2 für einen Großteil der eigentlichen Berechnungen durch die Tatsache, daß einige Systeme noch in unzureichender Weise Speicherbereinigungen effizient zur Verfügung stellen. Für die Zeigerrichtung ist hier nur von Belang, wie die Strukturen aus der Datenbank in den dynamischen Teil des Interpreters kopiert werden. Dabei wird in VIP wie bei der Unifikation mittels Tiefensuche gearbeitet. Bei dem Faktum f([a,b,c]). würde also bei :-retract(f(X),true), die Listenelemente in der Reihenfolge [a|_], [b|_], [c|[]] kopiert werden. Es bestehen hier also immer Zeiger von älteren Zellen auf jüngere.
b) clause-Stil: meist alt → neu
Eine von der Art der erzeugten Zeigerrichtungen sehr verwandte Programmiertechnik, die aber sonsts nicht mit a) zu schaffen hat, arbeitet mit Metainterpretern, hier werden entweder über clause/2 oder aber über ausdrückliche Fakten Programmdaten einem Programm, dem Metainterpreter, übergeben. Solange es sich um variablenfreie Klauseln handelt, werden auch hier nur alt → neu Zeiger zu finden sein. Falls jedoch Variablen in den Fakten/Regeln vorkommen, kann keine eindeutige Entscheidung mehr getroffen werden. In diesem Fall hängt die Zeigerrichtung vom nach c), d) und f) klassifizierten Programmierstil ab.
c) Direktes vorwärtsrekursives Programmieren: alt → neu für besuchte Struktur (z.B. append/3).
Über Vorwärtsrekursion wird elementweise eine Liste "von links nach rechts" konstruiert. Es zeigen daher stets die älteren Zellen auf die jüngeren. Den einzigen umgekehrten Zeiger gibt es, wenn das 3. Argument frei ist, die konstruierte Liste zeigt dann auf das zweite Argument. In allen anderen Fließmustern von append/3 werden aber auf der Ebene der Zeiger ausschließlich Zeiger auf neuere Zellen konstruiert. Man beachte jedoch, daß meistens auch die Listenelemente schon bekannt sind. Falls es sich bei ihnen um komplexe Terme handelt, so wird zusätzlich für jedes Element eine neu → alt Referenz erzeugt. Das Verhältnis wäre dann ausgeglichen.
d) Vorwärtsrekursives Programmieren mit Differenzlisten: neu → alt
(z.B. reverse/2) über Vorwärtsrekursion wird elementweise eine Liste "von rechts nach links" konstruiert. Die neugebildeten Zeiger verweisen daher stets auf ältere Zellen. Die Elemente der Strukturen, in diesem Beispiel die Elemente der Listen, werden zumeist auch schon bekannt sein, sodaß also sämtliche Zeiger auf älterer Zellen zeigen. 
reverse([],Xs-Xs).
reverse([E|Xs],Ys-Zs) :-
	reverse(Xs,Ys-[E|Zs]).
f) Programmieren mit Metastrukturen: eher neu → alt
Beim Anlegen von Metastrukturen wird sich das Verhältnis der Zeigerrichtungen eher in Richtung neu → alt- Referenzen verändern. Einerseits wird eine neue Struktur erzeugt, und daher eine alt → neu Referenz geschaffen, falls die Metastruktur nicht nur auf Zielebene auftritt und daher in einer anderen Struktur steht; auch werden durch die zu verwaltenden Variablen, die ja einmal gebunden werden sollen, alt → neu Referenzen geschaffen. Durch die bisherige Erfahrungen mit Metastrukturen kann man allerdings sagen, daß Metastrukturen nicht gleich mit einem nichtvariablen Term gebunden werden, sondern sich über verschiedene Zwischenzustände ihrer eigentlichen Darstellung nähern. Beim Lösen eines Gleichungssystems werden etwa schrittweise immer mehr zusätzliche Gleichungen über das Programm den Metastrukturen mitgeteilt. Es müssen immer wieder neue Metastrukturen, die die älteren ersetzten, erzeugt werden. Ein Großteil der Information jener Strukturen kann aber übernommen werden, sodaß in diesem Fall, der allgemein narrowing genannt wird, größtenteils neu → alt Zeiger erzeugt werden. Als einfachstes Beispiel, das allerdings nicht narrowing realisiert, kann etwa das freeze/2 genannt werden. Hier werden die Metastrukturen durch meta_meta_unify/2 (siehe 4.1.4) vereint und aus ihnen eine neue Struktur, die die Ziele der beiden in einer Konjunktion darstellt, konstruiert.
Das Verhältnis der Zeigerrichtungen läßt sich also nicht genau vorhersagen, es ist aber anzunehmen, daß in den meisten Programmen die Zeiger auf ältere Zellen überwiegen werden.

Der einfacheren Darstellung wegen werden nun der neue Markierungalgorithmus, der sich in jedem Prologsystem, das die Speicherbereiche ähnlich wie [Bru82] aufbaut, verwendet werden, und der neue Kompaktierungsalgorithmus getrennt vorgestellt.

4.2 Markierung

Man kann die in der Einleitung von Kapitel 3 erwähnte Formulierung auch hier abgewandelt anwenden: Es werden all jene Terme am Copystack benötigt, auf die noch entweder über Ziele in der Vorwärtsrekursion, oder über ein erneut erfüllbares Ziel, also über einen Wahlpunkt, zugegriffen werden kann. Durch die Einbindung von Metastrukturen gilt dann zusätzlich für Metastrukturen, daß jene nur genau dann nicht überschrieben werden dürfen, wenn es einen Wahlpunkt gibt, über den sie in einen aktiven Zustand erreicht werden können. In sehr wenigen Systemen gibt es Speicherbereinigungen, die über die Referenzierbarkeit von Zellen hinausgehen, z.B. [Wad87] für Funktionale Sprachen.

4.2.1 Kompaktierung des Trail

Durch die Verwendung von !/0 werden Wahlpunkte gelöscht. Alle Strukturen die nach diesem Wahlpunkt angelegt worden sind, können daher nur mehr über Vorwärtsrekursion referenziert werden. Bei einem Scheitern (fail) wird der letzte noch aktive Wahlpunkt aufgesucht. Bindungen, die am Trail markiert sind, und Strukturen betreffen, die nach den weggeschnittenen Wahlpunkten erst angelegt worden sind, können daher vom Trail entfernt werden, dadurch kann vor allem der Platzbedarf für die nächsten Markierungsschritte reduziert werden.

4.2.2 Umformung von Variablenreferenzen

Da auf dem Copystack durch shared variables unter Umständen ein Argument einer Struktur zwar noch referenziert wird, die Struktur aber nicht mehr benötigt wird, muß man den Wert des Arguments von der Position in der Struktur weg in die noch aktive Struktur verlegen. Die folgenden Beispiele zeigen, wie unbeabsichtigt sehr lange Ketten von Referenzen entstehen können, ohne daß einer der in der Literatur erwähnten Algorithmen diese Ketten auflösen kann. 
/* erzeugt sinnlose Referenzkette in X */
mkvrs(N,X) :-
	mkvrs(N,_,_,_,X).
/* erzeugt sofort nicht mehr referenzierte Strukturen,
die Referenzkette erzwingen */
mkvrs(1, f(X,X), f(X,X),X,X).
mkvrs(N,f(X,X,F,G),f(Y,Y,F,G),X,Y) :-
	N > 1,
	!,
	M is N - 1,
	mkvrs(M,F,G,X,Y).

dom(0,M,Y) .
dom(N,M,Y) :-
	N > 0,
	O is N - 1,
	mkvrs(M,Y),
	dom(O,M,Y).
dom(_,_,_) :-
	fail.
Programm zur Erzeugung von Elementen, die durch eine einfache Markierung nicht mehr zurückgewonnen werden können. Durch Anlegung von Wahlpunkten in dom/3 können die Referenzketten bei Markierungsalgorithmen, die vom jüngsten Wahlpunkt ausgehen, nie erkannt werden. Man wähle N << M.

Aus diesem Grund sollte man bei der Markierung mit dem ältesten Wahlpunkt beginnen. Dieses Problem dürfte in der Literatur noch nicht erkannt worden sein. [Appleby 88] geben sogar genau eine redundante Referenzkette, die aus ehemaligen Strukturen besteht, zur Veranschaulichung ihres Markierungsalgorithmus an! Bruynooghe beginnt ebenfalls die Markierung beim neuesten Wahlpunkt. Auch für die Metastrukturen hat diese Vorgangsweise ihre Vorteile: Bei einem Durchwandern des Copystacks kann man so eine noch nicht markierte Metastruktur, die kein freies erstes Argument besitzt, direkt überlesen, ohne Gefahr zu laufen, daß bei der Fortsetzung des Programms die Metastruktur noch aktiv werden kann. Man sieht, daß für Variablenreferenzen und inaktive Metastrukturen dasselbe Problem auftritt: Obwohl sie logisch nur mehr einen Wert, bei Variablenreferenzen u.U. nur mehr eine Variable bezeichnen, können sie zu ihrer Realisierung beliebig viel Platz benötigen. Bei der Markierung innerhalb eines Wahlpunktes wird bei inaktiven Metastrukturketten und Referenzketten, die bereits an eine Konstante gebunden sind, der Wert kopiert. Die Kette selbst bleibt unmarkiert. Da es ja keine Zyklen geben kann, wird der Markierungsalgorithmus terminieren. Bei Referenzketten, die auf eine Variable zeigen, setzt man in die Variable eine Referenz auf die neue (und markierte) Position in der Struktur, von der man ausgegangen ist, und setzt dort eine Variable ein. Dies ist ja möglich, da ältere Wahlpunkte bereits die Kette markiert haben müßten, wenn sie benötigt worden wären. Bei Variablenreferenzen, die direkt vom Environmentstack auf eine Variable am Copystack verweisen, wird genauso verfahren. Dadurch ist es zwar aufwendiger Referenzketten zu durchwandern, dafür können aber auch sämtliche unbenötigte Speicherzellen freigegeben werden.

4.2.3 Markierung des Environments

Nach Markierung eines Wahlpunktes wird zum nächsten Wahlpunkt gegangen. Es werden die entsprechenden Bindungen, die auf markierte Variablen zeigen, wieder auf den Trail geschrieben und die entsprechenden Werte in die Variablen gesetzt. Falls man statt einer Variable eine Referenz findet, so wurde in einer der vorherigen Wahlpunkte eine Referenzkette zerlegt. Man sucht daher die neue Position der Variable und legt diese Adresse auf den Trail. Ausgehend von den neuen Bindungen werden die Strukturen markiert. Danach müssen über den Wahlpunkt alle von diesen Wahlpunkt aus erreichbaren Stackframes markiert werden. In den meisten Fällen werden die Variablen in den Stackframes selbst aber schon markiert worden sein, sodaß das Lesen des Zwischencodes, wie in Kapitel 4.1.2 beschrieben, entfallen kann.

4.2.4 Kompaktierungsalgorithmen

Da die zeitliche Reihenfolge auf den Stacks erhalten bleiben muß, muß ein ordnungserhaltender kompaktierender Algorithmus angewendet werden. Die Kopieralgorithmen können im Gegensatz zu Funktionalen und Imperativen Programmiersprachen nicht verwendet werden. Die Familie der Algorithmen um Dewar-McCann und Torelli kann auch nicht direkt verwendet werden, da nicht unbedingt jede Zelle einen Header besitzt, und auch die Argumente einer Struktur selbst referenziert werden können. Es können nur Lisp 2, der Table-Compactor und Morris I verwendet werden. Bei Lisp 2 wird während der Kompaktierung der gesamte Speicher und die Zeiger zu den neuen Zellen referenziert, also doppelt soviel wie bei der Abarbeitung des Programms. Der zusätzliche Speicher wird während der gewöhnlichen Ausführung vom Hauptspeicher ausgelagert sein, während der Kompaktierung muß dieser Bereich zusätzlich geladen werden. Lisp 2 kam wegen der sehr großen benötigen Speichermenge nicht in Betracht; man beachte, daß ja auch für die prologspezifischen Operationen, etwa der Verwaltung des Trails noch eine beträchtliche Menge an Speicher benötigt wird. Der Table-Compactor geht von der Voraussetzung aus, daß die kleinste nichtreferenzierte Zelle noch groß genug ist, einen Zeiger und einen Zähler zu beinhalten, also zumindest immer zwei aufeinanderfolgende VIP-Wörter frei sind. Wenn sämtliche Referenzketten, wie in Kapitel 4.2.2 beschrieben, aufgelöst werden, könnte der Table-Compactor eine mögliche Alternative sein. Die Analysen von Cohen[Co83] haben gezeigt, daß Morris I immer schlechter als andere Verfahren abschneidet. Diese Behauptung wurde zwar in dieser Arbeit nicht direkt überprüft, durch einfache Erweiterungen kann der Aufwand für Morris I, aber auch für Jonkers noch beträchtlich reduziert werden. Ein weiterer Grund für die nähere Auswahl von Morris I als Grundlage der VIP-Implementierung war der besonders einfache Algorithmus, und die Möglichkeit, ihn durch einfache Änderungen der Repräsentation noch wesentlich zu beschleunigen. Als Alternative für weitere Untersuchungen wurde der Table-Compactor und Lisp 2 für kleine zu kompaktierende Bereiche in Erwägung gezogen.

4.2.4.1 Adaptiver Algorithmus mittels Morris I, Morris I+II

Die meisten existierenden Prologsysteme verwenden Morris I [Mor78]. Ein Großteil der in Phase II notwendigen Entscheidungen kann bereits in der Markierungsphase abgehandelt werden. Die Aufwärtszeiger in VIP entsprechen den neu → alt Zeigern der in Kapitel 4.1.8 besprochenen Analyse. Bei der Implementierung von Prologsystemen ist es ad hoc nicht möglich, den von Morris verbesserten Algorithmus Morris II zu verwenden, da es auch Referenzen in eine Zelle geben kann. Betrachtet man allerdings die typische Belegung von Prologtermen (Kapitel 4.1.7)so fällt auf, daß fast immer die für Morris II erforderliche Situation gegeben ist. Nur in sehr wenigen Fällen gibt es Referenzen in einen Prologterm. Morris II geht von der Tatsache aus, daß die Terme gegen die Kompaktierungsrichtung lesbar sind. Durch die Anordnung der Strukturen auf dem Copystack ersieht man jedoch, daß in VIP die Strukturen in entgegengesetzter Richtung liegen, da der Interpreter auf diese Weise die Terme schneller verarbeiten kann. Wegen der Möglichkeit von—wenn auch wenigen—Referenzen in Strukturen oder Listen muß man auf alle Fälle die Phase II von Morris I beibehalten. Ein Großteil dieser Phase kann, aufgrund der üblichen Eigenschaften von Termen bereits in die Markierungsphase übernommen werden, sodaß Phase II zum größten Teil nur aus einem Überlesen der Speicherzellen besteht. Algorithmus Morris I+II
Phase I: Markierung und Umkehrung von sicheren Aufwärtszeigern
Ein sicherer Aufwärtszeiger muß in einer Zelle stehen, die selbst von keiner anderen Zelle mittels eines Aufwärtszeigers referenziert werden kann. Wenn ein derartiger Zeiger auf eine VIP-Struktur verweist, kann er schon während der Markierungsphase umgekehrt werden. Bei Listen ist dies im allgemeinen nicht möglich, da ja der Zeiger auf eine Liste direkt auf den Kopf der Liste verweist. Wenn bereits, wie in den meisten Fällen, eine Konstante im Kopf der Liste vorhanden ist, oder aber ein Abwärtszeiger, kann ebenso der Zeiger auf diese Liste umgekehrt werden. Erst während der Markierungsphase kann man feststellen, ob eine Zelle einen sicheren Aufwärtzeiger besitzt. Falls man also während der Markierungsphase über einen Aufwärtszeiger, der eine Variablenreferenz darstellt, auf einen bereits umgekehrten Zeiger stößt, muß dieser Aufwärtszeiger gesondert gekennzeichnet werden, damit er während der nächsten Phase gesondert behandelt werden kann.
Phase II: Umkehrung der verbleibenden Aufwärtsreferenzen, Behandlung unsicherer Aufwärtszeigern
Falls der Kompaktierer in dieser Phase auf unsichere Aufwärtszeiger trifft, wird die Zelle mit dem in der Markierungsphase umgekehrten Zeiger als Wert genommen. Die Zeiger werden nun genauso wie gewöhnliche Zeiger umgekehrt. Es ist also nur eine Sonderbehandlung erforderlich, wenn man auf derartige unsichere Aufwärtszeiger trifft, alle anderen Zeiger und Zeigerketten insbesondere des Umkehren der unsicheren Zeiger erfolgt wie bisher.
Phase III: wie Morris I

4.2.4.2 Vergleich Morris I+II vs. Lisp 2

Die Überlegungen von Morris in [Mor82] zeigen, daß Morris II sicher wesentlich schneller als Jonkers sein wird. Der hier entwickelte Algorithmus unterscheidet sich in den meisten Fällen gar nicht von Morris II: die zweite Phase wird aus einem Durchsuchen der Bitfelder bestehen. Da pro Zelle ein Bit anzeigt, ob diese Zelle in der 2. Phase betrachtet werden muß, und bereits fast alle Aufwärtsreferenzen in der Markierungsphase umgehängt wurden, wird Phase II in vernachlässigbarer Zeit den zu bereinigenden Speicher durchsucht haben und die Aufwärtszeiger an ihre zukünftige Postion gerichtet haben.. Man kann also annehmen, daß sich dieser neue Algorithmus kaum von Morris II unterscheiden wird, und daher sicher schneller als Jonkers sein wird. Insbesondere wird die Lokalität der dynamischen Referenzierungen erhöht, da fast jede Zelle nur zweimal besucht werden muß; Jonkers Algorithmus muß inklusive Markierungsphase dreimal eine jede Zelle besuchen. Die Anzahl der Referenzierungen der Argumente einer Struktur bzw. einer Zelle ist in beiden Verfahren gleich 2. Damit ist es durchaus denkbar, daß unser neuer Algorithmus in die Nähe der Geschwindigkeit von Lisp 2 bei Bewahrung der Lokalität der Referenzierungen kommt, schließlich unterscheidet sich ja bereits Jonkers kaum von Lisp 2 [Co83]. Der neue Algorithmus wird sich daher bei Speichergrößen ab der Größe des vorhandenen Hauptspeichers wegen seiner Lokalität auf alle Fälle besser als Lisp 2 verhalten. Die zusätzlichen Operationen während der Markierungsphase bewirken keine neuen Referenzierungen, es können daher auch relativ kleine Daten-caches ausgenützt werden. In Phase 3 kann zwar unser Algorithmus nicht so schnell wie Lisp 2 die Zellen an ihre neue Position bewegen, dafür entfallen aber fast alle Referenzen von Phase 2. Lisp 2 muß hier ja für jede referenzierte Zelle, die einen Zeiger enthält, ihre neue Adresse schreiben. Unter den momentanen Voraussetzungen der Speichertechnologie, die die Lokalität von Referenzierungen unterstützt, kann man also annehmen, daß unser Algorithmus sich besser als Lisp 2 verhalten wird. Vergleicht man unseren Algorithmus mit dem Aufwand der Kopieralgorithmen, so sieht man, daß der größte Mehraufwand durch Phase III verursacht wird. Die Markierungsphase wird zwar schneller als das Kopieren der Terme sein, dafür benötigt man noch ein weiteres Besuchen aller Terme. Falls ein Kopieralgorithmus inkrementell verwendet wird, müssen Referenzierungen des Interpreters zusätzlich überprüft werden. Inkrementelle Kopieralgorithmen erhöhen die Laufzeit des Interpreters auf konventionellen Systemen [Lieb83]. Im folgenden Abschnitt wird untersucht, wie ein Kompaktierungsalgorithmus für Prolog auf eine inkrementelle Variante erweitert werden kann. Dabei wird sich herausstellen, daß eine mit [Lieb83] vergleichbare inkrementelle Speicherbereinigung möglich ist, die keinerlei Mehraufwand für den Interpreter impliziert.

4.2.4.3 Wegbreit

Der Algorithmus von Wegbreit wurde als mögliche Alternative für große Speicherbereiche untersucht. Da auch Zeiger in VIP Typinformation enthalten, ist der Dekodierungsaufwand für die Umkehrung von Zeigern sehr groß. Eine Speicherzelle kann auch von zwei Zeigern mit unterschiedlicher Typinformation referenziert werden: Der Kopf einer Listenzelle kann zugleich durch eine Variablenreferenz und eine Listenreferenz bezeichnet werden. Lisp 2 und Wegbreit hingegen müssen nur ein einziges Mal die Zeiger dekodieren und die neue Adresse in den Zeiger kodieren. Da Lisp 2 eine große Menge von zusätzlichen Speicherzellen benötigt, wurde der Algorithmus von Wegbreit in Betracht gezogen. Dieser ist ja mit n log n im worst case von der Anzahl der aktiven Zellen abhängig. Bei einer großen Anzahl zusammenhängender Blöcke, kann dieser Aufwand stark reduziert werden. Da meistens (z.B. bei Listen) komplexe terme auf einmal erzeugt werden, ist es zudem sehr wahrscheinlich, daß ein Großteil der Zeiger eines Blockes in denselben Block zeigen. Anstatt daher ein Suchverfahren mittels einer Hashtabelle und binären Unterbäumen zu verwenden, kann man annehmen, daß ein Zeiger den letzten gefundenen Block benötigen wird. Dadurch wird der Suchaufwand vergleichbar mit der direkten Referenzierung in Lisp 2 werden. Welches Verfahren angewendet werden soll, kann in die Markierungsphase entschieden werden: Beim Markieren einer Struktur werden zusätzlich die markierten Nachbarzellen betrachtet. Mittels zwei Zählern kann die Anzahl der zusammenhängenden Blöcke bestimmt werden. Es kann beim Markieren einer Zelle die folgenden Fälle geben: Durch das Verhältnis der insgesamt markierten Zellen zu den Blöcken kann man entscheiden, ob Morris I oder Wegbreit zu verwenden ist. Morris I+II kann dann natürlich nicht mehr verwendet werden.

4.3 Inkrementelle Speicherbereinigung

Um den Copystack von Anfang an kompakt zu halten, wird in regelmäßigen Abständen vom Interpreter überprüft, ob ein genügend großer Bereich, der eventuell schon nichtreferenzierte Strukturen enthalten könnte, am Copystack angelegt wurde. Zudem sollen Bereiche des Copystacks, die bereits kompaktiert wurden, erst wieder einer neuen Kompaktierung unterzogen werden, wenn es möglich ist, daß Zellen in diesem Bereich nicht mehr benötigt werden.

4.3.1 Inkrementelle Erkennung

Der Interpreter muß die Überprüfung ausführen, ob der Copystack bereits größer geworden ist. Es ist zwar naheliegend diese Überprüfung beim Allokieren einer Zelle auszuführen, aufgrund der Verwendung der Register für die Stackzeiger kann allerdings nur eine Überprüfung des Copystacks gegen den Trail erfolgen. Andere Vergleiche würden im Verhältnis zu den notwendigen Operationen beim Anlegen zu stark ins Gewicht fallen und die Laufzeit des Interpreters erhöhen. Ähnliche Überprüfungen sind auch in jenen vordefinierten Prädikaten erforderlich, die neue Terme erzeugen. Im Falle eines Überlaufens des Copystack müssen einigen Sonderbehandlungen, für die gerade zu allokierenden Elemente durchgeführt werden, da für sie ja kein Platz mehr vorhanden ist. Die in vielen Systemen praktizierte Technik[Chan86], die Größe des Copystacks um einen kleinen Bereich zu vermindern und so kritische Operationen auslaufen zu lassen, ist in VIP aufgrund der Stackaufteilungen nicht möglich. Dafür wird versucht, den Kompaktierer in regelmäßigen Abständen aufzurufen, um diesen Sonderfall fast gänzlich ausschließen zu können. Es muß daher eine Stelle im Interpreter ausgewählt werden, die einerseits nicht zu häufig auftritt und bei der andererseits bereits nichtreferenzierte Zellen vorhanden sein können. Die Wahl fiel auf eine in der VAM ohnehin komplexe Instruktion, der last-call-Optimierung. Dieser Fall tritt bei jedem Ende einer Regel auf. An dieser Stelle wird jedes n-te mal überprüft, ob der Copystack seit der letzten Kompaktierung um einen fixen Betrag angewachsen ist. Falls dies der Fall ist, wird aufgrund der seit der letzten Kompakierung angefallenen Wahlpunkte entschieden, ob eine neuerliche Kompaktierung durchgeführt werden soll. Je geringer die Anzahl der seitdem verstrichenen Wahlpunkte ist, je mehr Elemente am Copystack zwischen zwei Wahlpunkten liegen, umso eher wird eine neuerliche Kompaktierung vorgenommen. Durch diese Verbesserung kann zwar der insgesamt benötigte Platz stark reduziert werden, und daher Auslagerungen auf die Platte größtenteils vermieden werden, der Aufwand für die Kompaktierung wird jedoch stets von der Anzahl aller aktiven Zellen abhängen. Aus diesen Grund versucht man auch in Prolog gewisse "Generationen", ähnlich den Generationen der scavenging Kopieralgorithmen, von Zellen zu finden. Eine einfache, wenn auch nicht immer völlig zufriedenstellende Variante nimmt die Wahlpunkte als Grenzen an.

4.3.2 Generationen durch Wahlpunkte

Falls ein neuer Wahlpunkt angelegt wird, wird der Zustand des Interpreters an dieser Stelle eingefroren, bei einer etwaigen Rückkehr zu diesem Punkt, werden die währenddessen erfolgten Berechnungen wieder zurückgenommen. Alle dazwischenliegenden Operationen müssen also, falls sie Elemente, die vor dem Wahlpunkt angelegt worden sind, verändern, ohnehin getrennt am Trail markiert werden. Nach einer erfolgten Speicherbereinigung wird am Trail zum Zeitpunkt des letzten Wahlpunktes eine Marke gesetzt. Bei der Auflösung von Bindungen wird diese Marke verwendet, um die Höhe des Stacks zurückzusetzen, bis zu der eine Speicherbereinigung bereits erfolgt ist. Eine andere Möglichkeit wäre, den letzten Zeitpunkt der Speicherbereinigung in einem jeden Wahlpunkt zu vermerken. In [Appleby88] wird diese Variante erwähnt. Da jedoch dadurch ein jeder Wahlpunkt vergrößert werden würde, und auch das Anlegen eines Wahlpunktes aufwendiger werden würde, wurde von dieser Variante abgesehen. Man beachte, daß durch eine derartige Implementierung zwar eine Variante von [Lieb83] implementiert wird, der Interpreter aber—abgesehen von der Auflösung von Bindungen—keinerlei Änderungen bedarf.

4.3.3 Künstliche Wahlpunkte

Häufig sind große Teile von Berechnungen bis auf shallow backtracking vollkommen deterministisch. In diesen Fällen kann also keine sinnvolle Einteilung des Copystacks in Generationen erfolgen. Durch zusätzliches Anlegen von Wahlpunkten, die bei einer Wiedererfüllung sofort scheitern, kann man auch diese Teile in Generationen einteilen. Man nimmt dadurch aber einen höheren Aufwand bei der Bindung von Termen in Kauf. Zudem können dadurch auch nicht mehr referenzierte Terme am Stack erhalten bleiben. Durch geeignete Heuristiken muß man diese Wahlpunkte daher wieder auflösen.

4.4 Faltung von Datenstrukturen

Sprachen mit referentieller Transparenz (2.2.1) abstrahieren ja auch die Identität eines Objektes. Falls z.B. in Prolog zwei Terme bezüglich ==/2 identisch sind, und es auch keinen Wahlpunkt gibt, sodaß sie unterschieden werden können, ist es möglich, diese Terme durch dieselbe Repräsentation darzustellen. Dadurch können also Terme zusammengelegt, gefaltet werden, ohne daß sich das Verhalten des Interpreters ändert. Man komprimiert so gewissermaßen redundante Darstellungen am Copystack.

4.4.1 Problemstellung

Das folgende der Lisp-Terminologie nachempfundene Beispiel zeigt den worst case für dieses Phänomen; der Redundanz der Darstellung, die nicht durch simple Markierungsalgorithmen erkannt werden kann. Die sogenannten BLAM-Listen [Ed64] werden bei der Entwicklung von Lisp-Systeme gerne zum Debuggen der Listenverwaltung eingesetzt. Es handelt sich hier um eine Liste, deren Kopf und Rumpf wieder auf dasselbe Element verweisen. Durch eine derartige Liste ist es möglich mittels N Listenelementen 2N-1 Listenelemente darzustellen. Bei der weiteren Berarbeitung dieser Struktur, kann es nun vorkommen, daß eine derartige Liste auf ihre "volle" Darstellung expandiert wird. 
blam(0,[]).
blam(N,[X|X]) :-
	N > 0,
	M is N - 1,
	blam(M,X).

same([],[]).
same([X|Xs],[Y|Ys]) :-
	same(X,Y),
	same(Xs,Ys).
Das erwähnte Beispiel stellt kaum einen realistischen Teil einer Prologanwendung dar. Typische Prädikate, die in ähnlicher Weise dieses Phänomen zeigen, ändern Teile von komplexeren Termen. Dabei können redundante Operationen kaum - wenn überhaupt - in Prolog erkannt werden. Eines der einfachsten Beispiele stellt etwa das Löschen der Vorkommnisse eines Elements aus einer Liste dar. Die Liste, die nach dem letzten passenden Element noch angelegt wird, stellt bereits eine redundante Kopie dar. Falls beide Listen in der nachfolgenden Berechnung noch benötigt werden, könnten sie wieder zu einem Vorkommnis vereint werden. In diesem Fall wäre es sogar möglich gewesen, ein "testendes" Prädikat mit dem eigentlichen berechnenden zu kombinieren; dadurch hätte aber die Klarheit des Programms sowie auch seine Ausführungsgeschwindigkeit gelitten. 
delete_all(X,[],[]).
delete_all(X,[X|Xs],Ys) :-
	delete_all(X,Xs,Ys).
delete_all(X,[Y|Xs],[Y|Ys]) :-
	X \= Y,
	delete_all(X,Xs,Ys).
Noch wesentlich häufiger kommt das Kopieren von redundanten Termen bei Datenbanken, die nicht der 1. Normalform entsprechen, vor. Tupel von variablenfreien Werten dargestellt durch Strukturen werden bei jeder Anfrage in den Copystack kopiert.

4.4.2 Sprache der sichtbaren Terme

Die dem Interpreter sichtbaren Daten am Copystack können allgemein durch eine Sprache dargestellt werden. Die Sprache der aktiven Prologterme sind alle von der Wurzel aus möglichen Wege durch die Terme. Man möchte eine Realisierung dieser Terme, sodaß möglichst wenige Speicherelemente verwendet werden und dennoch sämtliche mögliche Wege darstellt werden. Zur Veranschaulichung der Problemstellung sei die Gesamtheit der zu kompaktierenden Elemente durch einen Prologterm gegeben. Die Menge der entsprechenden Pfade, die durch den Interpreter durchlaufen werden können, wird durch die Lösungsmenge des folgenden Prädikat beschrieben; dabei wird der Einfachheit halber nur ein variablenfreier Term verwendet. Die noch "offenen" Variablen stelle man sich durch unterscheidbare Atome ersetzt vor. 
pfad(Term,[]).
pfad(Term,[Funktor-atom]) :- 			% Konstante gefunden
	functor(Term,Funktor,0).
pfad(Term,[Funktor/Arität+Argument|Rest]) :-
	functor(Term,Funktor,Arität),
	Arität > 0,				% Term mit Arität > 0
	zwischen(1,Arität,Argument),
	arg(Argument,Term,TermArgument),
	pfad(TermArgument,Rest).
Die möglichen Lösungen für Pfad in :- pfad(Term,Pfad) stellen die Sprache L dar. Falls rekursive Datenstrukturen vorhanden sind, wird diese Sprache abzählbar unendlich viele Elemente besitzen. Die aktiven Terme können allgemein durch eine Sprache dargestellt werden, die durch einen endlichen Automaten erzeugt werden können. Die so erzeugte Sprache wird vom Prologinterpreter während der Berarbeitung der Terme "gesehen", die Realisierung der Terme in der aktuellen Implementierung entspricht direkt dem endlichen Automaten.

4.4.3 Repräsentation der Terme als DFA

Tatsächlich entspricht die physische Repräsentation der Terme einem DFA. Es gelten die folgenden Entsprechungen:

Zustände ... Adressen der Funktoren
Übergänge ... Zeiger auf Unterstrukturen
Endzustände... Jeder Zustand

Die aufgezeigte Analogie schließt allerdings Variablenreferenzen aus. Diese konnten allerdings bereits in den vorhergehenden Schritten vollständig bis auf einfache direkte Referenzen reduziert werden. Bei der Zusammenlegung von Termen spielen sie daher keine Rolle mehr. Der Automat kann allerdings nicht jede beliebige Form annehmen, die folgenden Einschränkungen sind noch zu beachten:

Falls AB ∈ L so ist A ∈ L.
Falls AB ∈ L, B ≠ ε und not∃ C ≠ ε sodaß ABC ∈ L so ist B = Name-atom.
Falls AB ∈ L, B = NameB/AritätB+ArgB
so not∃ AC∈ L, C = NameC/AritätC+ArgC
mit NameB/AritätB ≠ NameC/AritätC
oder mit ArgC < 0 bzw. ArgC > AritätB
Es wurde zwar bereits in Arbeiten über rekursive Datenstrukturen in Prolog die Analogie zwischen endlichen Automaten und Prologtermen hingewiesen [Colm82], eine Verwendung dieser Tatsache zur Transformation der Terme konnte aber in der Literatur nicht gefunden werden.

4.4.4 Minimierung der Zustände

Da also Prologterme eine Untermenge der DFA darstellen, kann man den Algorithmus zur Minimierung des DFA von Hopcroft [Ho71] verwenden, der sich mit O(nlogn) noch im vertretbaren Bereich befindet. Es wird nun eine für Prolog adaptierte Variante vorgestellt, die auf die Charakteristik von Prologtermen bereits eingeht. Das Verfahren wird natürlich nicht bei jeder Speicherbereinigung angewendet werden, da meist nur flüchtige Datenstrukturen vorkommen. Gerade aber bei dictionaries oder anderen permanenten Daten kann eine derartige Komprimierung nicht nur den Speicherbedarf reduzieren, sondern vor allem das Arbeiten auf diesen Termen beschleunigen: Man wird hier auf bereits gelesene Terme treffen, die sich möglicherweise noch im Daten-cache befinden. Im wesentlichen kann man den Algorithmus von Hopcroft direkt verwenden. Um Mengen von Termen möglichst effizient darzustellen, wird der Fall, daß eine Menge genau aus einem Element besteht gesondert behandelt. Zur Feststellung der Identität zweier Terme genügt es nicht nur, die momentanen Werte zu betrachten, man muß zusätzlich auch die Geschichte der beiden Terme untersuchen. Dies erfolgt durch das Durchsuchen der Traileinträge. Falls man so einen Zustand finden kann, sodaß die Terme bei einem Wahlpunkt voneinander verschieden sind, dürfen diese Terme nicht gefalten werden. Minimierung des Copystacks nach [Ho71]. Benötigte Markierungsbits:
marked
wenn false: an der Stelle der Zelle befindet sich ein Vorwärtszeiger zur neuen Repräsentation der Zelle
single
die Zelle konnte im letzten Durchlauf der Schleife keine entsprechende Zelle finden. Alle auf sie direkt zeigenden Zellen können daher auch als single markiert werden.
/* Dieser Algorithmus sollte direkt nach einer Speicherbereinigung erfolgen. Dadurch kann die Typinformation der Speicherzellen wiederverwendet werden. Es können sich ja nach einer Speicherbereinigung nur ganze Listen oder Strukturen im Speicher befinden. Die Einträge am Trail sind minimal und werden zum Testen auf Identität verwendet. */ 
marked(alle) = true;
single(alle) = false;

`partition = {M| für alle a,b ∈ M: a == b oder nur gleich auf 1. Ebene}

do {


	für alle M ∈ partition, mit C(M) = 1, a ∈ M: single(a) = true;
	lösche M aus partition;

	lösche jede Zelle a, die nur auf Zellen b mit
	single(b) == true zeigt aus einer Menge, setze single(a) = true

	teile jede Menge in partition so in Untermengen,
	daß zwei Zellen genau dann in dieselbe Untermenge kommen,
	wenn sie in jedem Argument auf Zellen zeigen,
	die sich in derselben Menge befinden;

	Spezialfall:


		Zellen a,b identisch (==/2) und not∃ Wahlpunkt, sodaß \==/2:
		Vorwärtszeiger von jüngerer Zelle a auf b,
 		marked(a) = false;
		lösche a aus Menge; nach diesem Durchlauf auch single(b) = true


} while (partition ändert sich);
Wähle für alle M ∈ partition einen Repräsentanten, falls not∃ Wahlpunkt, sodaß \==/2. single bezeichnet also den (sehr häufig auftretenden) Fall, daß eine Zelle am gesamten Copystack einmalig ist. Anstatt diese Menge ausdrücklich darzustellen, wurde diese Information direkt in das Markierungsbit verschoben. Falls keine zyklischen oder redundanten Strukturen auftreten, wird sich dieser Algorithmus im worst case sehr schlecht verhalten: So muß z.B. bei einer Struktur s(s( ... s(0) ... )) der Größe n die dazugehörige Menge n mal durchlaufen werden, falls sich die Zeiger stets genau in zur Leserichtung entgegengesetzter Richtung befinden. Der Algorithmus kann also zu O(n2) ausarten. Nachdem alle Zellen komprimiert wurden, werden noch die auf unmarkierte Zellen gerichteten Zeiger durch die Vorwärtszeiger umgestellt. Es könnte nun eine erneute Speicherbereinigung stattfinden, diese sollte aber auf den nächsten Durchgang aufgeschoben werden, um den Interpreter nicht zu lange zu unterbrechen. Der Aufwand für die Faltung der Terme am Copystack hängt in Anlehnung an [But87] ab,...

4.4.5 Vorteile der referentiellen Transparenz

Das vorgestellte Verfahren läßt sich nur in Sprachen anwenden, die konsequent referentielle Transparenz unterstützen. Es wäre zum Beispiel unmöglich, dieses Verfahren in Lisp einzubinden. Hingegen könnten in wirklich Funktionalen Sprachen oder für CLUs unveränderbare Datentypen ähnliche Verfahren verwendet werden. Durch die referentielle Transparenz—also der Unabhängigkeit der Eigenschaften eines Objekts von seinem Kontext—konnte die Repräsentation der Terme beliebig verändert werden. Durch referentielle Transparenz kann man also die Repräsentation der Daten von sämtlicher Redundanz, die durch die Repräsentation identischer Strukturen bewirkt wird, befreien.

4.4.6 Unendliche Datenstrukturen

Die Unifikation von unendlichen Datenstrukturen stellt in den meisten Systemen einen Schwachpunkt dar: Meist wird sie nur für jene Fälle korrekt ausführbar sein, bei denen dieselbe Zelle mit sich selbst unifiziert wird. Durch die Komprimierung von Termen werden u.U. einige unendliche Datenstrukturen zusammengefaltet, sodaß der Interpreter auch in diesen Fällen nach einer erfolgten Komprimierung die Unifikation erfolgreich durchführen kann, obwohl ohne Komprimierung ein undefinierter Zustand eingetreten wäre. Programme, die also gelegentlich auf einem Interpreter laufen, könnten das nächste Mal in einem undefinierten Zustand enden. Als konsequente Lösung kann man hier nur die korrekte Implementierung der Unifikation unendlicher Datenstrukturen vorschlagen. Diese werden aber wahrscheinlich nicht in den ISO-Standard aufgenommen.

4.5 Inkrementelle Faltung

Da der Aufwand zur Faltung der Datenstrukturen eher in Richtung n2 als n log n gehen wird, weil sehr häufig längere Listen vorkommen werden, ist es auch hier naheliegend, eine inkrementelle Faltung vorzunehmen. In diesem Fall muß man also die neu hinzugekommenen Terme betrachten und versuchen, diese in die bereits komprimierten einzubinden. Man müßte bei einer inkrementellen Faltung zumindest die Typinformation des alten Bereichs über die Laufzeit des Interpreters hinweg bewahren. Zur Faltung mit älteren Termen wird man nur Terme heranziehen, die entweder variablenfrei oder Variablen besitzen, die bereits zum Zeitpunkt der älteren Terme existierten. Um das "Einsortieren" der neuen Terme möglichst zu beschleunigen, sollten alle Terme zwischen zwei Wahlpunkten vorsortiert sein. Bei der Komprimierung von Termen muß man ohnehin die Menge aller Terme vorsortiert haben. Da Variablen dieser Terme erst später gebunden werden können, muß man beim Suchen nach identischen Termen auch nach f(X,Y) suchen. Zum Zeitpunkt des Sortierens der Terme können Teile noch nicht instanziert sein; durch späteres Instanzieren ist es daher möglich, daß die Reihenfolge in den Termen zu einem späteren Zeitpunkt nicht mehr gilt. Variablen werden daher zum Zeitpunkt des Sortierens gesondert markiert, um auch im Nachhinein einen Teil der Ordnung auszunutzen. Um ein binäres Suchen zu realisieren, müssen die folgenden Tags für die bereits komprimierten Speicherzellen realisiert werden: 
tag_old = {
    list,struct,/* Beginn einer Liste bzw. Struktur */
    var,	/* ist zum Zeitpunkt der Gültigkeit des
		   Wahlpunkt eine Variable; er kann im
		   Moment des Suchens bereits instanziert
		   worden sein */
    other		
}
Bei der binären Suche nach einen passenden Term, wird man nach jeder Berechnung eines Teilungspunktes nach einer list bzw struct-Markierung gesucht, und dort die Suche fortgesetzt. Insgesamt muß man nach dem konkreten Term suchen, sowie nach allen Termen, die zu diesem Term instanziert worden sein könnten.

4.6 Lokalität der Terme

Die bisher vorgestellten Verfahren zur Verkleinerung des Copystacks sind von der Annahme ausgegangen, daß alle aktiven Strukturen unter einer virtuellen Speicherverwaltung im Hauptspeicher gehalten werden können. Bei einem größeren Umfang der Prologstacks kann aber die Faltung von Termen die Lokalität einer Berechnung sogar vermindern. In diesem Fall kan man für ein einzelnes Ziel alle Referenzen auf den Copystack erneut (an die Spitze des Stacks) kopieren.

4.7 Vergleich mit existierenden Implementierungen

Die meisten Prologimplementierungen verwenden einen stop and collect Algorithmus. Da alle existierenden kommerziellen Systeme auf der WAM basieren, werden am Copystack nicht nur Terme allokiert, und damit größere Elemente, sondern auch einzelne Speicherzellen, die eine Variable sichern müssen. Bei den meisten Klauseln, die mehr als ein Unterziel im Rumpf besitzen, muß daher ein WAM-Interpreter eine derartige Zelle anlegen. Dies ist auch der Grund dafür, warum keine der existierenden Implementierungen den Algorithmus von Wegbreit verwendet: Dieser Algorithmus baut auf der Annahme auf, daß die kleinste freiwerdende Zelle die Größe eines Eintrags zum Verschieben eines Zellblockes aufnehmen kann. Auch bei deterministischen Programmen, die an sich keine unnötigen Terme erzeugen, werden in der WAM Zellen zum Sichern von Argumentregistern verwendet. Dadurch wird es sehr unwahrscheinlich sein, daß größere zusammenhängende Blöcke am Copystack überhaupt entstehen können. Für WAM-basierte Implementierungen kommen daher ausschließlich Lisp 2 oder Morris I in Frage. Diese Verfahren arbeiten ja unabhängig von der Verteilung der Blöcke im Hauptspeicher. Nach den exisiterenden Veröffentlichungen und Aussagen über konkrete Systeme werden für Prologsysteme, die das Speichermodell aus Kapitel 2.3 verwenden, ausschließlich Varianten von Morris I verwendet.

4.7.1 Bruynooghe

Maurice Bruynooghe dürfte sich schon am längsten mit der Speicherverwaltung von Prolog im allgemeinen [Bru82] und mit der Speicherbereinigung im besonderen [Bru84,Pit87] auseinandersetzen. Er veröffentlichte als erster ein Verfahren zur Speicherbereinigung, das auf den Nichtdeterminismus von Prolog eingeht [Bru84]. In [Bru84] wird virtual backtracking zum ersten Mal erwähnt: Es handelt sich hier um ein Markierungsverfahren, das ausgehend vom aktuellen Environment schrittweise die Wahlpunkte durchwandert, so als ob man eine Wiedererfüllung der Wahlpunkte anstrebt. Dabei werden die Bindungen des Trails zurückgenommen. Bruynooghe braucht daher genausoviel zusätzlichen Speicherplatz für die Sicherung der durch das virtuelle Wiedererfüllen zurückgesetzen Bindungen, wie der in dieser Arbeit vorgestellte Algorithmus. Allerdings nimmt Bruynooghe die Bindungen schrittweise ausgehend von dem letzten Wahlpunkt zurück. Dadurch ist es unmöglich, sinnlose Referenzketten aufzulösen. Gerade aber bei Metainterpretern kommt es sehr häufig vor, daß shared variables auf Strukturebene entstehen, die dadurch nicht mehr aufgelöst werden können. Die Speicherbereinigung wird daher die immer länger werdenden Ketten von Referenzen, die ja logisch nichts anderes als genau eine Variable darstellen, als noch benötigte Datenstrukturen ansehen. In [Pit87] wird eine inkrementelle Variante des virtual backtracking vorgestellt. Bruynooghe und Pittomsvill sehen diese Implementierung als eine einfach zu realisierende Adaptierung von Liebermanns und Hewitts Verfahren. Auf den Unterschied wurde in 4.3.2 bereits hingewiesen: Liebermanns Algorithmus ist völlig unabhängig von der eigentlichen Semantik der Sprache, der vorgestellte Algorithmus kann allerdings ausschließlich vorwärtsrekursive Berechnungen nicht in inkrementelle Zwischenziele zerlegen. Die Kompaktierung erfolgt mittels Morris I.

4.7.2 Garbage Cut

Eine sehr pragmatische Erweiterung sehen Barklund und Millroth [Bar86] vor: Da bei einem !/0 meist auch Terme am Copystack freiwerden, wird zu diesem Zeitpunkt die Speicherbereinigung aufgerufen. Gerade bei iterativen großen Prologprogrammen können dadurch sehr früh Speicherzellen freigegeben werden. Es soll eine Verdopplung der Ausführungsgeschwindigkeit dadurch erreicht werden können. Da diese Implementierung auf der WAM beruht, ist die vor allem durch die gesicherten Variablen am Copystack zu erklären. Durch die inkrementelle Erkennung kann bereits früh genug erkannt werden, ob eine Speicherbereinigung am Copystack erforderlich ist. Eine Einbindung dieser Überprüfung in ein gesondertes !/0 wäre möglich.

4.7.3 Appleby et al.

Appleby et al. stellen in [Appleby88] eine vollständige Implementierung einer Speicherbereinigung für Prolog vor. Abgesehen von der Tatsache, daß es sich hier um eine Implementierung für die WAM handelt, können folgende Unterschiede festgestellt werden. Für die Markierungsphase wird ein dem Deutsch-Schorr-Waite Algorithmus—der aber leider nicht zitiert wird—nicht unähnliches Verfahren vorgestellt, das mittels eines zusätzlichen Bits auch Strukturen mit beliebiger Länge verarbeiten kann. Die Kompaktierungsphase erfolgt mittels Morris I. Für eine inkrementelle Variante wird vorgeschlagen, daß in jedem Wahlpunkt ein Zeiger auf den letzten von einer Speicherbereinigung betroffenen Wahlpunkt zeigt.

4.7.4 Das MALI-System

Das in Kapitel 2.3 vorgestellte Implementierungsmodell bezieht sich auf die meisten existierenden Systeme im kommerziellen und wissenschaftlichen Bereich. Insbesonders gilt bei fast allen Systemen, daß Backtracking über Stacks dargestellt wird; die Zwischenergebnisse können so sofort freigegeben werden. MALI (Mémoire Adaptée aux Langages Indéterministes) [Bek84,86] stellt eine der wenigen echten Alternativen zu der üblichen Speicherverwaltung dar. Hier werden auf einem gleichförmigen Heap stets neue Elemente angefordert. Bei Wiedererfüllung eines Ziels wird auf ein altes Environment zurückgegriffen. Die Strukturen am Heap bleiben allerdings erhalten. Die innere Ordnung der Terme ist hier also nicht mehr von Belang. Der Vorteil liegt in der einfacheren Implementierung der Kompaktierungsphase, die eine hardwaremäßige Unterstützung bzw. eine Realisierung durch Mikroprogrammierung nahelegt. In Kapitel 3.4.6.3.2 wurde bereits der verwendete Algorithmus, ein Ringkopierer, der eigens für diese Maschine entwickelt wurde, vorgestellt. Ridoux hat das Verhalten einer parallelen Implementierung von MALI in [Rid87] stochastisch modelliert. Der Prologinterpreter wird vollständig von der eigentlichen Speicherverwaltung getrennt. Es existieren zwei unabhängige Systeme—der Prologinterpreter und MALIQdie nur über eigene Befehle, die Nachrichten entsprechen, miteinander kommunizieren. Der Prologinterpreter ist für die Verwaltung der Datenbasis sowie die Ausführung der Programme verantwortlich, während MALI die Verwaltung der dynamischen Datenstrukturen übernimmt. Die Objekt- bzw. Termverwaltung von MALI ist auf die UND-ODER Kontrolle von Prolog abgestimmt. Entsprechend können Terme ... Um die komplexen Sonderbehandlungen für temporäre Referenzen des Prologinterpreters zu umgehen, werden alle Strukturen, die seit der letzten GC angelegt worden sind, beibehalten.