2 Prologsysteme

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

2 Prologsysteme

2.1 Entwicklung von Prolog

2.1.1 Système-Q

Erst nach dieser Entwicklung (1970) erfuhr Colmerauer in Marseille von den Arbeiten Robinsons. Mit Phillipe Roussel entwickelte er den Begriff der formellen Gleichheit für die Unifikation. Dadurch galt für Terme nicht mehr das Assoziativgesetz, dafür ließ sich die Unifkation aber wesentlich effizienter realisieren. Kowalski hatte sich, als reiner Logiker, die Einbindung des Axioms der Assoziativität in die Horn-Klauseln noch vorgestellt. In [Kowa88] beschreibt Kowalski die Entwicklungen jener Zeit. Auch wenn diese Eigenschaft gerade für Zeichenfolgen elementar ist, wurde erst in den letzten Jahren diese Idee wieder aufgegriffen [ComLe88 und Referenzen]. Colmerauer überarbeitete sein Système Q vollständig, um es in Einklang mit den Formalismen der Logik zu bringen. Anstatt der Produktionen ähnlich den Typ 0 Grammatiken in Système Q wurden Horn-Klauseln verwendet. Eine Horn-Klausel ist entweder eine Klausel eines definiten Programms oder ein definites Ziel [Llo87]. Horn Klauseln besitzen maximal ein positives Literal. Vom Standpunkt der Grammatiken aus betrachtet wurden dadurch die Produktionen kontextfrei, während in Typ 0 Grammatiken auch kontextabhängige Produktionen verwendet werden können. Die Ausführung eines Programms entspricht nun dem Beweisen eines definiten Ziels unter Verwendung der SLD-Resolution (Linear resoultion with Selection function of Definite clauses). Colmerauer entschied sich für eine Selektionsfunktion mit Tiefensuche und die der Auswahl der Literale nach ihrer Ordnung in einer Klausel von links nach rechts. Dadurch war es möglich, eine sehr effiziente Implementierung, die den Prozeduraufrufen in herkömmlichen Sprachen ähnelt, zu realisieren.

Hornklauseln:
A :-
	B1,...,Bn        Klausel eines definiten Programms,
:- B1,...,Bn             Definites Ziel
keine Hornklausel:
:- A1,A2 ,  B1,...,Bn

2.1.2 Prolog 0

+VATER(PETER,PAUL) ;;
+MUTTER(MARIA,JAKOB) ;;
+GATTE(PETER,MARIA) ;;
+BRUDER(*Z,*Y) -VATER(*X,*Y ) -VATER(*X,*Z) -DIF(*Y,*Z) ;;
+VATER(*X,*Z) -GATTE(*X,*Y) -MUTTER(*Y,*Z) ;;
Anfrage: -BRUDER(PAUL,*X) / +ANTWORT(*X) ..
Antwort: +ANTWORT(JAKOB) ;.

	Prolog 0- Programm

Beim Beweis eines Programms wurden ausgehend von der Anfrage stets ein negatives Literal (das Ziel) mit einem positiven Literal (Kopf einer Klausel) unifiziert, und durch die negativen Literale dieser Klausel (Rumpf) ersetzt. Ziele, die nicht direkt bewiesen werden konnten -etwa -DIF(*Y,*Z)- wurden in der Liste der negativen Literale (Zielliste) belassen. Dadurch konnte auf einfache aber nicht sehr effiziente Weise das Aufschieben von Zielen und damit eine sichere Implementierung des dif/2 realisiert werden. Insofern war dieser Interpreter schon wesentlich fortgeschrittener als die meisten heutigen Systeme. Die Arbeitsweise eines Prologinterpreters läßt sich also wie folgt schematisch darstellen:

In der weiteren Folge wurde Prolog vor allem durch eine große Menge von vordefinierten Prädikaten erweitert. Der eigentliche Mechanismus wurde nicht mehr verändert. Durch die Übersetzungstechnik von D.H.D. Warren [Warr77,Warr83] konnte Prolog mit ähnlicher Effizienz wie andere symbolische Sprachen implementiert werden. Dadurch waren die Voraussetzungen für einen breiteren Einsatz von Prolog gegeben. Auf der anderen Seite entdeckten immer mehr Forscher, die zuvor an dem bis heute noch immer nicht erreichten Ziel der automatischen Verfikation imperativer Programme gearbeitet hatten, die Schönheit von Prolog, das bis zu einem gewissen Grad nur mehr die Zusicherungen (assertions) aber nicht mehr die dazwischenstehenden obskuren imperativen Programmteile, darstellt. Prolog wurde so bei einer immer größer werdenden Gruppe von Theoretikern populär, die erkannten, daß sie nur in diesem Rahmen, dem Bereich der Logik-Programmierung, theoretische Erkenntnisse rasch in die Praxis umsetzen konnten, ohne dabei allzu lange mit den Implementierungsdetails ihrer Ideen aufgehalten zu werden. Der Begriff der Unifikation etwa, der sich in Prolog nur auf einfache Terme bezieht, ist eine Hintertür, um in Prolog noch weitere interessante Gleichungssysteme zu verwenden. So wurde in Marseilles mittlerweile Prolog III entwickelt, das auch Gleichungen über rationale Zahlen lösen kann. Allgemein gehören diese Erweiterungen zum sog. CLP-Schema (Constraint Logic Programming) [JaLa87]. Prolog stieß in viele Bereiche der theoretischen Informatik, etwa der algebraischen Spezifikation [GoMe87] oder der Programmtransformation [Hog81] vor, in denen praktische Implementierungen rasch verwirklicht werden können.

Trotz des theoretischen Umfelds, das Prolog umgibt; der Logik-Programmierung, konnte Prolog auch in anderen Bereichen der Informatik, etwa beim VLSI-Entwurf seine Verwendbarkeit beweisen. Anwendungen, die aus dem Bereich der künstlichen Intelligenz -dem ursprünglichen Anwendungsgebiet von Prolog- stammen, vor allem Expertensysteme und die Verarbeitung natürlicher Sprache dürfen natürlich nicht unerwähnt bleiben. Die Verwendung von Prolog hat sich, ausgehend von einigen Universitäten und vielen Pionieren, in den letzten fünf Jahren auf den industriellen Bereich ausgedehnt, sodaß seit Frühjahr 1988 an einer internationalen Prolog-Standardisierung innerhalb der ISO SC22 WG17 [Der89] gearbeitet wird.

2.1.3 Prolog und Logik

Prolog hat also mit Prädikatenlogik nur sehr wenig zu tun. Aber vielleicht hat sich Philippe Roussel nur verhört, als seine Frau in einem Zug zwischen Paris und Marseille den Namen Prolog erfand und Prolog steht in Wirklichkeit für programmation la logique.

2.2 Vergleich der Spracheigenschaften

2.2.1 Referenzielle Transparenz

• Objekte können noch "unvollständig" sein, d.h. Variablen enthalten. Im Gegensatz zu imperativen Sprachen gibt es durch das Konzept der Unifikation für Prologs Variablen eine klare Semantik. Prolog wird deshalb auch single assignment Sprache genannt. Dadurch wird ein Großteil der destruktiven Operationen, wie sie etwa in Lisp vorhanden sind (REPLACA u.ä.) hinfällig. D.H.D Warren und Fernando und Luis Pereiras haben als erste diesen Vorteil deutlich herausgestrichen [WarP77]. Tatsächlich gibt es kein einziges kommerzielles Prologsystem, das zu REPLACA analoge Operationen erlaubt. Auch der ISO-Vorschlag für einen Prologstandard blieb bisher [Der89] von derartigen Unterwanderungen der referentiellen Transparenz verschont. Offensichtlich kann also das Konzept der logischen Variablen von Prolog die destruktiven Operationen (Zuweisungen) effizient genug ersetzen.
• Prolog-Programme können während der Ausführung des Programms verändert werden. Es ist dadurch zwar möglich, Zuweisungen imperativer Programmiersprachen zu simulieren, insofern wäre Prolog ebenso referentiell opak wie herkömmliche Programmiersprachen; durch die sog. logical update view [LiKe87] kann allerdings ein Großteil der unvorhersehbaren Seiteneffekte vermieden werden. Ganz abgesehen davon existieren die Programme zudem völlig unabhängig von den dynamischen Daten. Durch assert/2 kann ausschließlich die Datenbank manipuliert werden. Insofern entspricht assert/2 eher dem DEFUN oder SETQ von LISP. Der Vergleich dieser Elemente mit imperativen Programmiersprachen ist zudem nicht gerechfertigt, da jene ja keinen Übersetzer für die Sprache selbst als Sprachmittel besitzen und dennoch referentiell opak sind. Bei einem System, das sehr lange Zeit existiert, müssen Fähigkeiten zur Selbstverwaltung, ähnlich wie in Betriebssystemen, vorhanden sein.

2.2.2 Metasprachlichkeit

2.2.2.1 Prolog

2.2.2.2 Funktionale Sprachen

2.2.2.3 Imperative Sprachen

2.2.2.4 Maschinensprachen

2.3 Prologs Implementierungsmodell

2.3.1 Deterministisches Prolog

2.3.2 Nichtdeterministisches Prolog

2.4 Anforderungen an die Speicherverwaltung

2.4.1 Zeitliches Speichermodell

In einer konkreten Realisierung wird zu den beiden Zeitpunkte GC1 und GC2 eine Speicherbereinigung die nicht mehr benötigten Objekte entfernen. Eine charakteristische Eigenschaft der Verfahren ist ihre Abhängigkeit von diesen vier Klassen. Es stellt sich bei den meisten Systemen heraus, daß man vor allem mit einer großen Menge von flüchtigen (transient) und permanenten Datenstrukturen zu rechnen hat. Je älter ein Objekt ist, umso eher wird es auch weiterexistieren. Je nach Wahl der Größe des Intervalls kann man die neu hinzukommenden Objekte (arrival objects) und die nicht mehr referenzierten Objekte zu einer dieser Klassen zuordnen.

2.4.2 Flüchtige Datenstrukturen

2.4.2.1 Implementierungskosten

Die Kosten pro Zelle g daher:

Zum Anlegen einer Zelle benötigen beide Implementierungen eines Stacks gleich viel Zeit. Die Freigabe eines Elements auf einem traditionell implementierten Stack benötigt die Zeit f. Bei einer Speicherverwaltung mit Speicherbereinigung ist keinerlei Mehraufwand erforderlich. Die beiden Versionen werden also unter folgenden Bedingungen den gleichen Aufwand pro angelegter Zelle benötigen:

Falls also M/sA größer als (c + ds)/f +1 gemacht werden kann, wird eine Speicherbereinigung effizienter als eine Stackverwaltung sein. Bei den Annahmen von [Appel 87] muß der Speicher 8 mal größer als die Anzahl der verwendeten Elemente sein. Bei einer Verdopplung der momentanen Speichergröße, werden sich die Kosten bei M >> A also halbieren!

G	.............	Anzahl der Zellen, die zwischen zwei GC angelegt werden.
A	.............	Anzahl der erreichbaren Zellen
M	.............	Größe des vorhandenen Speichers
c	.............	Aufwand pro Zelle
d	.............	Aufwand pro Zeiger
s	.............	Zellgröße
g	.............	Kosten pro Zelle
f	.............	Kosten für eine pop-Operation

Andrew Appel [Appel 87] begründet so, daß es zur Unterstützung von applikativen Sprachen wesentlich interessanter ist, mehr Speicher zur Verfügung zu haben, als durch spezielle Hardware oder aufwendige Analysen des Compilers den Prozessor beim Anlegen von Speicherelementen zu unterstützen. Die einzige Voraussetzung ist, daß die Speicherbereinigung unabhängig von der Anzahl der flüchtigen Datenstrukturen ist. Natürlich können durch eine derartige Speicherverwaltung möglicherweise sehr lange Pausen entstehen. Adaptive Verfahren, bei denen ähnlich Annahmen für ihren Aufwand gelten, werden in Kapitel 3.3.6.3 vorgestellt. Der Vergleich ist natürlich nur dann zulässig, wenn pro pop-Operation tatsächlich zumindest eine Zeit von f > 0 benötigt wird.

Bei der Speicherverwaltung von Prolog ist es allerdings noch immer interessant, das in Kapitel 2.3 vorgestellte Implementierungsmodell zu verwenden. Durch die zeitliche Abhängigkeit der Datenstrukturen in Prolog kann man bei backtracking größere Teile des Stacks sofort freigeben. Man kann also pro pop-Operation mit einem wesentlich geringeren Aufwand rechnen, der nicht mehr proportional zur Anzahl der freigegebenen Elemente ist. Deswegen kann daher durch einen größeren Speicher wohl nie diese Effizienz erreicht werden. Dennoch experimentiert man auch in Prolog mit derartigen Konfigurationen [Bek84, Bek86]. Für die Verwaltung der Speicherzellen am Copystack gilt allerdings allgemein, daß ihre Kosten durch eine Vergrößerung des Speichers reduziert werden können.

Flüchtige Datenstrukturen werden gerade auf neueren Systemen, die mit Daten-caches ausgestattet sind, sehr effizient unterstützt: Bei ihrer Erzeugung werden sie, da dadurch auf Speicherzellen geschrieben, aber nicht gelesen wird, im cache angelegt. Es erfolgt keinerlei Zugriff auf den eigentlichen Hauptspeicher. Während der kurz auf ihre Erzeugung folgenden Verwendung werden sie sich noch immer im cache befinden. Es ist daher nicht erforderlich, sie aus dem Hauptspeicher einzulesen. Erst lange nach ihrer Verwendung werden die flüchtigen Datenstrukturen in den Hauptspeicher hinausgeschrieben werden, da der Prozessor nunmehr auf anderen Speicherzellen arbeitet (cache flush). Bei größerem cache (ab ca. 64K) kann man sogar erwarten, daß die Speicherbereinigung, falls sie sich nur auf einen kleineren Bereich des Arbeitsspeichers bezieht, die "toten" Strukturen noch immer im cache antrifft. Der eigentliche Mehraufwand liegt so nur mehr in der Speicherbereinigung, die dafür verantwortlich ist, daß sich die Maschine bezüglich des paging des virtuellen Speichers noch immer lokal verhält.

2.4.2.2 Beispiele

2.4.2.2.1 Metainterpreter

solve(true).
solve((X,Y)) :-
	solve(X),
	solve(Y).
solve(X) :-
	clause(X,Y),
	solve(Y).

clause(H,B) :-
	H \= clause(_,_),
	real_clause(H,B).
clause(clause(H,B),B) :-
	real_clause(H,B).

p(X,X).
p(X,Z) :-
	q(X,Y),
	p(Y,Z).
q(a,b).

Beweis mittels Prolog-Resolution und die durch den Metainterpreter angelegten Strukturen zum Zeitpunkt der zweiten gefundenen Lösung

Der Metainterpreter wird nun bei :- solve(p(X,b)). all jene Ziele als Datenstrukturen durch clause/2 erzeugen, die von der Anfrage aus zu dem aktuellen Knoten führen. Dabei werden nur bei Regeln Strukturen erzeugt. Eine direkte Ausführung des Programms hätte nur einen einzigen Wahlpunkt mit den dazugehörigen Variablen erzeugt. Die neu angelegten Strukturen ,/2 und q/2 werden für die nachfolgenden Berechnungen nicht mehr benötigt. Verglichen mit der direkten Ausführung wird sich daher der Platzbedarf bei folgenden Elementen unterscheiden:

Die Kontrollstruktur ,/2 wird im Prologinterpreter durch structure sharing der Darstellung der Klauseln realisiert, d.h. daß die gleichbleibenden Teile einer Klausel nur einmal in der Datenbasis dargestellt werden. Die sich ändernden Teile, also die Variablen werden gesondert abgespeichert. Der Metainterpreter muß diese Struktur aber bei jedem neuen Ziel erzeugen. Die aktuellen Ziele werden durch den Prologinterpreter mit Hilfe des Environmentstacks realisiert. Der Metainterpreter muß auch hier jedes einzelne anfallende Ziel als Term im Copystack besitzen. Das Stackframe einer deterministischen Klausel kann bei Aufruf des letzten Ziels durch lastcall-Optimierung entfernt werden. Der Metainterpreter hat hier direkt keine Entsprechung. Allerdings können sämtliche angefallenen Kontrollstrukturen, insofern sie nicht mehr wegen eines Wahlpunktes benötigt werden, durch die Speicherbereinigung entfernt werden. Dabei kann der Metainterpreter sogar mehr Elemente entfernen als dies bei einem Prologinterpreter der Fall ist: Der Prologinterpreter muß jedes Environment als eine Einheit behandeln. Wenn also bereits gewisse Variablen darin nicht mehr benötigt werden, könnte der Prologinterpreter sie höchstens freigeben, falls diese am "Rand" des Environments vorkommen. Bei der WAM (siehe unten) wird dieser Vorgang stack trimming genannt. Im Gegensatz dazu muß der Metainterpreter nur die einzelnen Ziele als Strukturen verwalten; die Variablen werden dadurch implizit mitverwaltet. Der Metainterpreter könnte im besten Fall in Bezug auf die Größe des Environmentstacks um einen von der Größe des Programms abhängigen Faktor weniger Platz als das direkt exekutierte Programm verbrauchen.

In diesem Beispiel wurde gezeigt, wie die Speicherbereinigung für einen Metainterpreter den Großteil der typischen Prolog-Optimierungen nachvollzieht.

2.4.2.2.2 Matrizenmultiplikation

Der übliche Ansatz, Programme zu entwickeln, zerlegt ein Problem in Teilprobleme, die sich zum Teil rekursiv formulieren lassen. Im Unterschied zu Prozeduralen Sprachen kann aber in applikativen Sprachen das Teilproblem vollkommen unabhängig von der eigentlichen Aufgabe verstanden werden. Zwischenergebnisse oder Parameter können, falls sie bereits bekannt sind, nicht mehr verändert werden. Falls Zwischenergebnisse noch nicht Teil des Endergebnisses sind, werden sie nach erfolgter Berechnung nicht mehr benötigt. Hier fallen dann flüchtige Datenstrukturen, die durch eine Speicherbereinigung erkannt werden müssen, an.

Es soll etwa die Multiplikation von zweidimensionalen Matrizen implementiert werden. Matrizen seien durch Listen von Listen dargestellt, die zeilenweise die Matrix darstellen. Die Anfrage :- matrix_multiply([[3,5],[2,9]],[[6,2],[7,1]],M). sollte M = [[53,11],[75,13]] liefern. Die Zeilen der ersten Matrix sollen mit den Spalten der zweiten für alle Kombinationen errechnet werden. Da es aber nicht direkt möglich ist, die zweite Matrix spaltenweise zu bearbeiten, müßte man ein komplexeres Verfahren entwickeln. Innerhalb der Implementierung einer Bibliothek von Vektor- und Matritzenoperationen seien nun bereits mehrere Prädikate implementiert worden, etwa transpose/2 zur Transponierung einer Matrix...

transpose(M,[]) :-
	nullrows(M).
transpose(M1,[Row|M2]) :-
	makerow(M1,Row,M3),
	transpose(M3,M2).

makerow([],[],[]).
makerow([[X|R1]|M1],[X|Row],[R1|M2]) :-
	makerow(M1,Row,M2).

nullrows([]).
nullrows([[]|M]) :-
	nullrows(M).

:- transpose(L,[[6,2],[7,1]]).
    L = [[6,7],[2,1]].

... sowie das Skalarprodukt zweier Vektoren:

dot_prod([],[],0).
dot_prod([X|Xs],[Y|Ys],S) :-
	dot_prod(Xs,Ys,T),
	S is T + (X * Y).

matrix_multiply(MA,MB,MR) :-
	transpose(MB,TB),
	mul_rows_cols(MA,TB,MR).

mul_rows_cols([],_,[]).
mul_rows_cols([X|M1],T,[Y|M2]) :-
	mul_onerow_cols(T,X,Y),
	mul_rows_cols(M1,T,M2).

mul_onerow_cols([],_,[]).
mul_onerow_cols([Col|Cols],Row,[El|Els]) :-
	dot_product(Col,Row,El),
	mul_onerow_cols(Cols,Row,Els).

2.4.2.2.3 Sortieren

quicksort([],L,L).
quicksort([Key|List],Tail,Sort) :-
	partition(Key,List,L1,L2),
	quicksort(L2,Tail,Between),
	quicksort(L1,[Key|Between],Sort).

partition(Key,[],[],[]).
partition(Key,[E|L],[E|L1],L2):-
	E =< Key,
	!,
	partition(Key,L,L1,L2).
partition(Key,[E|L],L1,[E|L2]) :-
	partition(Key,L,L1,L2).

slowsort(L,K) :-
	permutation(L,K),
	ordered(K).

Hier ist es wohl offensichtlich, daß flüchtige Datenstrukturen als Zwischenergebnisse, die schlimmstenfalls einen Mehraufwand von n2 für die nachfolgende Speicherbereinigung bedeuten, sehr gerne in Kauf genommen werden.

2.4.2.3 Unterstützung des Programmierstils

Durch die verbesserten Möglichkeiten neuerer imperativer Programmiersprachen bei der Unterstützung von Datenabstraktion können etwa Iterationen auch dort einfacher realisiert werden. Grenzen werden aber durch die strenge zeitliche Folge der Instruktionen gesetzt. CLU stellt hier die konsequenteste Realisierung dar, aber auch in ADA können derartige Iterationen klar dargestellt werden.

2.4.3 Permanente Datenstrukturen

2.4.4 Redundante Darstellung