Pro Logik: Prolog für Einsteiger Teil 4

Neben den eleganten Möglichkeiten zur Verarbeitung von Datenstrukturen sind es vor allem die sogenannten Metaprädikate, die die Ausdrucksstarke der Programmiersprache Prolog bestimmen. Die von ihnen zur Verfügung gestellten Operationen, wie zum Beispiel das Verändern des aktuellen Prolog-Programms, das Interpretieren von Termen als Anfragen und die Operatorgrammatik, werden auf den ersten Blick meistens unterschätzt. Trotzdem sind sie oft der Schlüssel zu eleganten Problemlösungen.

Die Metaprädikate haben ihren Namen aus dem Bereich, aus dem Prolog stammt, also aus der Logik. Als Metasprache wird dort die Sprache bezeichnet, die man benutzt, um Aussagen überden verwendeten Formalismus zu machen. Benutzt man etwa die natürliche Sprache (zum Beispiel Deutsch), um über die Aussagenlogik zu reden, so ist die natürliche Sprache die verwendete Metasprache, und die Aussagenlogik ist die Objektsprache.

Die Metaprädikate sind Prädikate, die es ermöglichen, über Prolog zu sprechen. Genauer: Die Metaprädikate erlauben es, Prolog-Programme oder Programmteile zu erzeugen und zu verändern. Das hört sich aufs erste unsauberer an, als es in Wirklichkeit ist, aber das werden wir im Laufe dieser Folge noch sehen. Nötig ist das ganze, da es in reinem Prolog, ohne die Metaprädikate, nicht oder zumindest nicht allgemein möglich ist, Aussagen über Prolog zu machen. Das liegt daran, daß Prolog, wie in der zweiten Folge dieser Serie bereits erwähnt wurde, seinen Ursprung in einer eingeschränkten Form der Prädikatenlogik erster Ordnung hat. Und genau der Zusatz „erster Ordnung“ besagt, daß diese Logik nicht in der Lage ist, Aussagen über sich selbst zu treffen. Diese Einschränkung ist nötig, um Prolog effizient implementieren zu können. Da sie für die Praxis aber zu hart ist, wird die Möglichkeit, Programme höherer Ordnung zu schreiben, durch ein Hintertürchen, nämlich die Metaprädikate, wiedereingeführt.

Datenreigen

Offen bleibt, wozu man eine scheinbar so unsaubere Sache wie die Modifizierung eines Programms eigentlich braucht. Zuerst einmal: Unsauber ist ein relativer Begriff. Sicherlich kann man mit den Metaprädikaten einige Sachen machen, die jenseits dessen liegen, über das sich ein Programmierer, der etwas auf sich hält, auch nur Gedanken macht. Zum Beispiel könnte man ein Prädikat schreiben, das sich selber verändert, während es sich rekursiv aufruft. Solch ein Prädikat würde die Lesbarkeit eines Programms sicherlich nicht erhöhen.

Doch wenn man sich mal überlegt, was ein Interpreter oder ein Compiler eigentlich macht, so sieht man sehr schnell eine wertvolle Anwendung der Metaprädikate. Ein Interpreter muß ein vorgegebenes Programm analysieren und dabei gleichzeitig die darin enthaltenen Aktionen ausführen. Da in Prolog zur Analyse von Programmteilen teilweise dieselben (Meta-)Prädika-te verwendet werden wie zur Synthese, kann man also auch neue Programme erzeugen. Analysiert man einen Programmteil und erzeugt dann einen etwas anderen, hat man ein Programm auch schon modifiziert. Somit sind die Mittel zum Schreiben eines Interpreters und der etwas bösartigen, sich selbst modifizierenden Prozedur die gleichen. Extremer wird es noch bei einem Compiler. Dieser muß ein Programm ja nicht nur analysieren, sondern auch ein neues erzeugen. Stellt man sich zum Beispiel ein System vor, in dem eine Programmiersprache von einem Compiler nach Prolog übersetzt wird und der erzeugte Prolog-Code dann sofort ausgeführt werden kann, so stellt das die Modifikation eines laufenden Programms dar. Der Compiler befindet sich ja als Prolog-Programm im Speicher und erzeugt gleichzeitig neue Klauseln, die Teil des übersetzten Programms sind. Trotzdem kann man diesen Vorgang wohl kaum als unsaubere Programmierung ansehen. Es muß lediglich dafür gesorgt werden, daß die Namen, die der Compiler für die neuen Klauseln verwendet, noch nicht im System Vorkommen. Daß solch eine Anwendung gar nicht so fern liegt, wie man auf den ersten Blick annimmt, werden wir in dieser und der nächsten Folge noch sehen.

Nach dieser Rechtfertigung nun zu den Fakten der Prolog-Programmierung. Alle Klauseln, die man zum Beispiel mittels consult/1 in das Prolog-System einliest, werden in einer Datenbank gespeichert. Der aktuelle Zustand der Datenbank bestimmt die Reaktion des Systems auf Anfragen. Anders formuliert, alle Regeln und Fakten, die gerade in der Datenbank gespeichert sind, bilden das aktuelle Programm. Wendet man zum Beispiel zweimal hintereinander consult/1 auf verschiedene Dateien an, befinden sich die Klauseln beider Dateien anschließend gleichzeitig im Speicher, d.h. in der Datenbank. Möchte man eine neue Version einer Datei einlesen, die schon mal mittels consult/1 in die Datenbank aufgenommen wurde, verwendet man besser reconsult/1. Dies löscht nämlich die alten Prädikate. Es werden allerdings nur Prädikate gelöscht, die in der neuen Version, d.h. in der neu eingelesenen Datei, auch Vorkommen. Alle anderen Prädikate bleiben intakt.

Eine sehr viel direktere Methode, um Klauseln in die Datenbank einzufügen, bieten die Prädikate asserta/1 und assertz/1. Die ihnen als Argument übergebenen Klauseln werden sofort in die Datenbank aufgenommen. Dies stellt genaugenommen eine Modifizierung des aktuellen Programms dar. Denn, wie schon gesagt wurde, der momentane Inhalt der Datenbank bestimmt das aktuelle Programm, d.h. die Klauseln, die zur Beantwortung einer Anfrage verwendet werden. Wir probieren dies mit den folgenden beiden Anfragen aus.

?- assertz(test(1)).
?- test(A).

Die zweite Anfrage wird vom System mit „A = 7“ beantwortet, d.h. das Fakt test(1), das in der ersten Anfrage als Argument an assertz/1 übergeben wurde, ist zur Verarbeitung der zweiten Anfrage herangezogen worden. Für den hypothetischen Compiler, der irgendeine Sprache nach Prolog übersetzt und den erzeugten Code direkt in die Datenbank einfügt, wäre ein Prädikat wie assertz/1 offensichtlich von großem Nutzen. Wie wir in Kürze sehen werden, ist das Prädikat auch noch für völlig andere Programme sehr nützlich.

Neben dem Prädikat assertz/1 gibt es auch noch asserta/1. Der einzige Unterschied zwischen den beiden tritt zutage, wenn schon eine Klausel zum Prädikat, das mit asserta/1 bzw. assertz/1 modifiziert wird, existiert. Unter diesen Umständen fügt asserta/1 die neue Klausel nämlich vor allen bereits vorhandenen und assertz/1 dahinter ein. Als Gegensatz zum Einfügen von Klauseln gibt es natürlich auch ein Prädikat, das Klauseln wieder aus der Datenbank löscht. Es heißt retract/1. Die Klausel, die bei einem Aufruf von retract/1 als Argument angegeben wird, wird aus der Datenbank entfernt. Wird eine Klausel nicht vollständig angegeben, d.h. es werden an manchen Stellen Variablen eingesetzt, so wird die erste Klausel, die auf das angegebene Muster paßt, entfernt. Wird versucht, die Anfrage, die das Prädikat retract/1 enthält, wieder zu erfüllen, wird auch die nächste passende Klausel entfernt.

Sobald man Regeln und nicht nur Fakten mittels asserta/1 bzw. assertz/1 verarbeiten will, muß man beachten, daß alle Terme, die ':-', ',' (Komma) oder ';' (Semikolon) als Operatoren enthalten, immer geklammert werden müssen (auch wenn es Parameter sind). Die folgende Anfrage gibt ein kleines Beispiel.

?- assertz((inc(X, Y) :- Y is X + 1)).

Wie man leicht sieht, ist der Term zusätzlich geklammert worden. Anders wird die Eingabe vom Prolog-System nicht akzeptiert (das gilt nicht für Toy-Prolog).

So ein Zufall

Ein kleines Beispiel, das die Prädikate asserta/1 und retract/1 nutzt und überhaupt nichts mit Compilern zu tun hat, ist in Listing 1 abgebildet. Das Prädikat rand/2 liefert Pseudozufallszahlen. Im ersten Argument kann man den Wert angeben, den die Zufallszahl maximal haben darf (ihr kleinster Wert ist eins). Die Zahl selber wird dann im zweiten Argument geliefert. Nachdem das Prädikat in das Prolog-System eingelesen wurde, können mehrere Anfragen der folgenden Bauart benutzt werden, um es auszutesten.

?- rand(20, R).

Als Antworten für „R“ werden nacheinander die Zahlen 12, 17, 6, 3, 16, l usw. geliefert. Der Pseudozufallszahlengenerator beruht darauf, daß eine Basiszahl in Schritten, die relativ zu der Maximalgröße der Zufallszahlen recht groß sind, verändert wird. Die Basiszahl wird dabei konstant erhöht, ohne daß sie einen bestimmten Wert überschreiten kann. Letzteres wird durch die Modulo-Operation („... mod 4096“) bewirkt (für die Mathematiker: Das ganze ist ein Restklassenring). Der Rest, der übrigbleibt, wenn man die Basiszahl durch den Maximalwert der Zufallszahlen teilt („Seed mod Max“), ergibt plus eins die Zufallszahl. Dies verändert sich dadurch auch sehr sprunghaft.

Ein Problem bei dem zugehörigen Prolog-Programm ist, daß man sich den Wert der Basiszahl von einem zum nächsten Aufruf des Prädikats rand/2 merken muß. Man braucht also eine Art globale Variable. Dies kann man sehr einfach durch die Verwendung der Datenbank lösen. Die Zahl wird einfach in dem einzigen Argument des Fakts r_seed/1 gespeichert. Der Initial-Wert (hier: elf) wird direkt im Programm angegeben. Um den Wert zu lesen, genügt die Anfrage r_seed(Seed). Um ihn zu ändern, wird das alte Fakt erst mit retract/1 entfernt und danach das neue mittels asserta/1 in die Datenbank eingetragen.

Außer dem Einträgen und Löschen von Information in bzw. aus der Datenbank, stellt sich für Programme, die Prolog-Klauseln erzeugen oder manipulieren sollen, noch ein weiteres Problem. Wie in der zweiten Folge schon erwähnt wurde, sind auch Prolog-Programme lediglich eine Ansammlung von Termen, die, durch die Benutzung von Operatordeklarationen, auch Prefix-, Infix- und Postfixoperatoren enthalten können. Was uns bisher noch fehlt, ist eine allgemeine Methode, die Terme zu zerlegen und zu konstruieren. Bisher wurde die Termzerlegung bzw. -konstruktion durch die Unifikation erledigt. Dies hat aber den Nachteil, daß der Funktor des Terms, der zerlegt wird, bekannt sein muß. Das soll durch ein einfaches Beispiel veranschaulicht werden.

?- node(A, B) = node(leaf(1), leaf(2)).

Diese Anfrage liefert als Ergebnis ,A = leaf(1), B = leaf(2)“. Der Term rechts des Gleichheitszeichens wurde also derart zerlegt, daß seine Argumente an die Variablen „4“ und gebunden wurden. Wie man leicht sieht, mußte dazu aber der Funktor (hier: node/2) des Terms angegeben werden, denn er taucht auch auf der linken Seite des Terms auf. Möchte man also ein Prädikat schreiben, das einen beliebigen Baum in den äußersten Funktor und eine Liste seiner Elemente zerlegt, so sieht dies wie folgt aus.

destructTree(node(T1, T2), node, [T1, T2]). 
destructTree(leaf(Value), leaf, [Value]).

Die Argumente werden dabei als Liste geliefert, da es unterschiedlich viele sein können. Ein beispielhafter Aufruf ist

?- destructTree(node(leaf(1), leaf(2)), Functor, Args).

Das Ergebnis lautet dann: Functor = node, Args = [leaf(1), leaf(2)]. Auch hier ist leicht zu erkennen, daß alle Funktoren, die Vorkommen können, bekannt sein müssen, denn destructTree/3 besitzt für jeden der möglichen Funktoren (hier: node/2 und leaf/1) eine Klausel. Für ein Programm, wie zum Beispiel einen Compiler, ist dies kein sehr befriedigender Zustand. In einem zu compilierenden Programm können beliebig viele neue Funktoren Vorkommen, die beim Schreiben des Compilers kaum alle berücksichtigt werden können. Es ist also eine Operation nötig, die einen beliebigen Term in seinen Funktor und seine Argumente zerlegen kann, ohne daß man schon wissen muß, welche Funktoren in Frage kommen. In Prolog gibt es ein Metaprädikat, das genau diese Funktion bietet. Es wird durch den sogenannten Univ-Operator bezeichnet. Links von diesem Operator steht der Term, der zerlegt werden soll, und rechts eine Liste, die als erstes Element den Funktor und als weitere Elemente die Argumente des Terms enthält.

?- node(leaf(1), leaf(2)) =.. L.

Auf diese Anfrage erhält man die Antwort L = [node, leaf(1), leaf(2)]. Auch der umgekehrte Weg ist möglich, d.h. aus einer Liste, die einen Funktor mit Argumenten enthält, kann man einen Tenn konstruieren.

?- Term =.. [node, leaf(1), leaf(2)].

Hier lautet die Antwort Term = node (leaf(1), leaf(2)). Ein etwas komplexeres Beispiel, in dem der Univ-Operator verwendet wird, ist in Listing 2 abgebildet. Das Prädikat patmat/2 implementiert einen Pattern-Matching-Algorithmus. Pattern-Matching (dt.: Mustererkennung) funktioniert ähnlich wie die in der zweiten Folge vorgestellte Unifikation, die einen der Grundmechanismen von Prolog darstellt. Um genau zu sein, Pattern-Matching ist eine eingeschränkte Form der Unifikation. Bei der Unifikation können die zwei zu unifizierenden Terme freie Variablen enthalten. Zum Beispiel ist eine Unifikation wie „c(1, A) = c(B, 2)“ kein Problem. Die Lösung wäre dabei „A=2,B=1“. In beiden Termen wurden also Variablen an einen Wert gebunden. Beim Pattern-Matching ist so etwas nicht erlaubt. Hier darf nur das Muster Variablen enthalten (in unserem Prädikat ist das immer das erste Argument). Eine Variable in dem anderen (zu zerlegenden) Term führt zu einer Fehlermeldung, sobald die Variable in einer Position ist, in der sie gebunden werden würde.

?- patmat(c(A, B), c(1,2)).

Diese Anfrage liefert die Antwort „A = 1, B = 2“. Anders verhält es sich mit der folgenden Anfrage, die, wie schon erläutert wurde, beim Pattern-Matching nicht zulässig ist.

?- patmat(c(1, A), c(B, 2)).

Hier terminiert das Prädikat mit einer Fehlermeldung. Diese Fehlermeldung wird von der ersten Klausel des Prädikats patmat/2 ausgelöst, sobald diese eine freie Variable im zu zerlegenden Term mit Hilfe des eingebauten Prädikats var/1 entdeckt. In der zweiten Klausel werden dagegen Variablen, die im Muster Vorkommen, erkannt. Sie sind erlaubt und führen dazu, daß der zu zerlegende Term an die freie Variable gebunden wird. Die dritte Klausel fängt Zahlen und Atome mit dem eingebauten Prädikat atomic/1 ab. Mittels Unifikationsoperator („=“) wird dann geprüft, ob das Atom oder die Zahl mit dem zu zerlegenden Term übereinstimmen. Die vierte und letzte Klausel ist für uns die interessanteste. Sie benutzt den Univ-Operator, um das Muster und den Term in ihren Funktor und die jeweilige Argumentliste zu zerlegen. Durch die Verwendung derselben Variable Functor als erstes Element der Liste des zerlegten Musters und des zerlegten Terms wird sichergestellt, daß beide Terme denselben Funktor besitzen. Auf die Argumentlisten PatArgs und TermArgs wird das Prädikat patmat-List/2 angewandt, was den Pattern-Matching-Algorithmus patmat/2 rekursiv für die einzelnen Elemente der Argumentliste aufruft.

Die Unterscheidung mittels atomic/1 muß durchgeführt werden, da der Univ-Operator nicht auf ein einzelnes Atom angewendet werden kann. Anders ausgedrückt: Prolog betrachtet ein einzelnes Atom nicht als Term mit dem Atom als Funktor und einer leeren Argumentliste. Eine Anfrage wie zum Beispiel „?- hallo =.. L“ schlägt also fehl.

Im Übrigen sind die eingebauten Prädikate var/1, atomic/1 usw. (siehe Folge 2) auch Metaprädikate. Ihre Funktion könnte nicht durch ein anderes Prädikat simuliert werden, falls sie allesamt nicht vorhanden wären.

Ein weiteres sehr wichtiges Metaprädikat ist call/1. Es ruft den Prolog-Interpreter für das übergebene Argument auf, d.h. das Argument wird selber als Prolog-Anfrage behandelt. Dieses Prädikat kann man zum Beispiel verwenden, um neue Kontrollstrukturen in Prolog einzuführen. Eine Kontrollstruktur, die dem if-then-else imperativer Sprachen entspricht, ist Bestandteil der meisten Prolog-Systeme, obwohl sie ursprünglich nicht in Prolog vorgesehen war. Eine Anfrage der Form < Cond > -> < ThenGoal > wird ausgewertet, indem zuerst die Anfrage < Cond > ausgewertet wird. Gelingt sie nicht, schlägt das ganze Konstrukt fehl. Gelingt sie aber, wird die Anfrage < ThenGoal > ausgewertet. Der einzige Unterschied zu < Cond >, <Then-Goal> ist, daß < Cond > nicht ein zweites Mal probiert wird, falls < SubGoal > fehlschlägt. Ähnlich funktioniert < Cond > -> < ThenGoal >; < ElseGoal >. Allerdings wird hier versucht, < ElseGoal > auszuwerten, falls < Cond > mißlingt. Erst wenn auch dies mißlingt, mißlingt das gesamte Konstrukt. Diese Form von if-then-else kann mit Hilfe von call/1 sehr einfach selber implementiert werden. Wie, ist in Listing 3 abgebildet. Die erste Zeile enthält noch die zusätzlich notwendige Operator-Deklaration. In der ersten Klausel werden die Konstrukte behandelt, die einen Else-Fall besitzen. Dort wird zuerst die Bedingung Cond mit dem Prädikat call/1 ausgewertet. Je nachdem, ob dies gelingt oder nicht, werden anschließende Then oder Else (abgetrennt durch ein Semikolon, als alternative Anfrage - siehe auch Folge 1) ausgewertet. Der Cut („!“) erfüllt zwei Aufgaben. Erstens kann der Else-Fall nicht mehr ausgewertet werden, sobald Cond gelungen ist, auch wenn Then fehlschlägt. Zweitens kann nicht probiert werden, Cond wiederzuerfüllen, falls Then fehlschlägt. Die zweite Klausel wird benutzt, falls kein Else-Fall angegeben wurde, und funktioniert entsprechend.

Diese Form von if-then-else ist in MA-XON-Prolog schon von vorne herein vorhanden. In Toy-Prolog muß sie allerdings erst noch in Form des Programms aus Listing 3 nachgeladen werden. Dies sollte man insbesondere im folgenden Beispiel beachten, das von dieser Kontrollstruktur Gebrauch macht und somit ohne Listing 3 nicht auf dem Toy-Prolog lauffähig ist.

Eine Anwendung

Nachdem sooft davon geredet wurde, daß man die Metaprädikate braucht, sobald man einen Compiler in Prolog implementieren will, der als Zielcode Prolog erzeugt, soll nun auch ein Beispiel dazu folgen. Das Programm ist in Listing 4 abgebildet. Bevor wir uns näher mit seinem Aufbau und seiner Funktionsweise beschäftigen, wollen wir zuerst einmal sehen, welche Eingaben übersetzt werden, und wie der erzeugte Code aussieht.

Der Compiler übersetzt eine sehr einfache Form von Funktionen in Prolog-Prädikate. Jede Funktion setzt sich dabei aus ein oder mehreren Regeln zusammen. Um die Übersetzung zu starten, wird das Prädikat compile/1 aufgerufen. Es bekommt als einziges Argument pro Aufruf eine Regel übergeben. Die Regel wird daraufhin übersetzt und in die Datenbank eingetragen, sofern beim Übersetzen kein Fehler auf-tritt. Jede legale Regel besteht aus einem Kopf und einem Rumpf, die durch einen Doppelpfeil („=>“) getrennt sind. Der Funktor des Kopfes bestimmt den Namen der Funktion, zu der die Regel gehört. Die Argumente können einfach nur Variablen, aber auch komplexere Terme sein. Beim Aufruf der Funktion werden diese dann mit den übergebenen Parametern unifiziert. Der Rumpf einer Regel ist ein beliebiger arithmetischer Ausdruck, der die üblichen Grundrechenarten, Funktionsaufrufe und eine besondere Form von if-then-else enthalten kann. Funktionsaufrufe haben die normale Form, wobei natürlich auch Regeln für die aufgerufenen Funktionen mittels compile/1 übersetzt werden sollten. Ein bedingter Ausdruck hat die Form if < Condition > then < ThenExpr > else < ElseExpr >, wobei < Condition > eine beliebige Prolog-Anfrage sein kann, insbesondere auch Anfragen wie „N == 0“ oder „N>1“ Die beiden Ausdrücke < Then Expr > und < ElseExpr > sind dann wieder arithmetische Ausdrücke wie die Rümpfe der Regeln, wobei weitere if-then-else darin geklammert werden müssen. Um die Fakultätsfunktion zu compilieren, genügt die folgende Anfrage (die Formatierung spielt dabei keine Rolle):

?- compile(fac(N) => if N == 0
                then 1
                else fac (N-1)*N).

Eine Anfrage, die das Prädikat eval/1 enthält, kann nun benutzt werden, um die Funktion auszuwerten.

?- eval(fac(7)).

Diese Anfrage hat die Ausgabe Resultat: 520 zur Folge. Alternativ zu der eben verwendeten Regel kann man die Fakultätsfunktion auch durch zwei etwas kürzere Regeln definieren. Vorher muß die alte Regel allerdings gelöscht werden. Dies geschieht mit dem Prädikat killFunfl in der folgenden Anfrage:

?- killFun(fac(_).

Danach können wir die neue Definition der Fakultätsfunktion compilieren.

?-compile(fac(0) => 1).
?-compile(fac(N) => fac(N -1) * N).

Offensichtlich wurde hier das if-then-else durch zwei alternative Regeln ersetzt. Wie in Prolog üblich, wird zuerst die erste Regel ausprobiert. Paßt diese nicht, da das Argument ungleich Null ist, wird die zweite Regel benutzt, die immer paßt.

Nach diesem Beispiel wollen wir uns ansehen, wie dieser kleine Compiler funktioniert. Wie schon gesagt, bildet das Prädikat compile/1 den Ausgangspunkt des Übersetzungsvorgangs. Es besteht aus zwei Klauseln. Die zweite Klausel dient nur dazu, eine Fehlermeldung auszulösen, falls die erste mißlingt. Dies kann entweder passieren, weil das Argument der zu übersetzenden Regel nicht die Form < Head > => < Body > hat, oder weil einer der untergeordneten Übersetzungsschritte fehlgeschlagen ist. Den Rumpf der ersten Klausel können wir grob in vier Schritte einteilen. Der erste besteht aus den beiden Aufrufen von splitHead/3 und dem Aufruf von append/3. Er dient der Übersetzung des Funktionskopfs (links vom „=>“). Der zweite Teil ist compileExpr/3 und übersetzt den Rumpf (rechts vom „=>“). Der dritte Teil besteht nur aus stripTrue/2 und entfernt überflüssige Aufrufe des Prädikats true/0 aus dem übersetzten Rumpf. Der letzte Teil beinhaltet nur das assertz/1 und erweitert die Datenbank durch ein neues Prädikat um die übersetzte Regel.

Um verstehen zu können, wie der Übersetzungsvorgang abläuft, müssen wir uns zuerst einmal mit dem Ziel der Übersetzung vertraut machen, d.h. mit dem Code, der für eine Regel generiert werden soll. Eine Funktion (und die wollen wir ja übersetzen) hat einen Funktionswert, der an den Aufrufer zurückgegeben werden muß. Da es solch einen Mechanismus nicht für Prolog-Prädikate gibt, muß die für eine Funktionsregel erzeugte Klausel ein Argument mehr besitzen als die Funktionsregel. Wollen wir zum Beispiel die 0-stellige (also konstante) Funktion eins => 1 übersetzen, muß das erzeugte Prädikat etwa wie folgt aussehen: eins(Result) :- Result = 7. Ähnlich würde die Inkrementfunktion inc(X) => X + 1 etwa in inc(X, Result):-Result is X + 1 übersetzt. Dieses Erweitern der Argumentliste des Funktionskopfs wird von dem erwähnten ersten Teil der ersten Klausel von compile/1 durchgeführt. Dazu wird das Prädikat splitHead/1 aufgerufen. Es leistet im Prinzip genau die Arbeit des Univ-Operators (wozu dieser auch benutzt wird), allerdings wird der Sonderfall eines nullstelligen Funktionskopfs (also eines einzelnen Atoms) richtig behandelt. Der Funktionskopf wird also zuerst zerlegt, dann wird die Argumentliste mittels append/3 um eine Variable, nämlich ResultVar, erweitert. Zum Schluß werden der Funktor und die erweiterte Argumentliste mit splitHead/3 wieder zu einem Term (dem Kopf des zu erzeugenden Prädikats) zusammengebaut. Das Prädikat splitHead/3 wird also in Prolog-Manier sowohl zum Zerteilen als auch zum Zusammenbauen verwendet.

Auf welche Art compileExpr/3 den Funktionsrumpf übersetzt, werden wir gleich noch sehen. Wichtig ist vorerst nur, daß das vom Rumpf berechnete Ergebnis auf jeden Fall an die Variable ResultVar gebunden wird. Sie wird zu diesem Zweck auch an compileExpr/3 übergeben. Ansonsten wird der Funktionsrumpf in eine Prolog-Anfrage umgeformt, die genau die im Rumpf beschriebenen Berechnungen durchführt. Um compileExpr/3 und die davon aufgerufenen Prädikate möglichst einfach und uniform zu halten, werden in diese Anfrage recht viele nutzlose true/0 eingefügt. Diese werden im dritten Schritt von stripTrue/2 wieder entfernt. Das Prädikat stripTrue/2 macht dabei nichts anderes, als die erzeugte Anfrage rekursiv abzulaufen und zu kopieren. Dabei wird in allen Teilstücken, die die Form true, Goal oder Goal, true haben, das überflüssige true in der Kopie weggelassen. Der vierte und letzte Schritt fügt das erzeugte Prädikat, das aus dem erweiterten Funktionskopf und der von überflüssigen true/0 befreiten Anfrage besteht, in die Datenbank ein. Dies geschieht mit assertz/1, damit die Regeln in der Datenbank dieselbe Reihenfolge haben, in der sie eingefügt wurden. Wichtig ist dabei noch, daß die Anfrage vorne um einen Cut („!“) erweitert wird, denn schließlich soll in einer Funktion kein Backtracking stattfinden. Das scheinbar überflüssige true/0 am Ende der Anfrage ist im MAXON-Prolog nötig.

In die Tiefe

Nachdem wir nun die grundlegenden vier Schritte der Übersetzung kennengelernt haben, wollen wir uns näher mit den Details der Übersetzung eines einzelnen Ausdrucks beschäftigen. Diese Aufgabe wird von dem Prädikat compileExpr/3 übernommen. Es erwartet im ersten Argument den zu übersetzenden Ausdruck und im zweiten eine Variable. Sobald der übersetzte Ausdruck ausgewertet wird, wird das Ergebnis dieser Auswertung an die übergebene Variable gebunden. Die Prolog-Anfrage, die den Ausdruck auswertet und gleichzeitig die eben genannte Variablenbindung durchführt, wird im dritten Argument als Ergebnis geliefert. Dies ist sozusagen der erzeugte Code.

Die fünf Klauseln von compileExpr/3 werden im folgenden anhand der Fälle, die sie abdecken, besprochen. Die ersten zwei Klauseln behandeln freie Variablen und Zahlen, die durch var/1 bzw. integer/1 erkannt werden. Diese werden nicht weiter übersetzt, sondern im erzeugten Code direkt an die Ergebnisvariable ResultVar gebunden. Vor allem der Fall der freien Variablen muß unbedingt am Anfang, d.h. vor den anderen Fällen, geprüft werden. Denn schließlich kann solch eine Variable mit jedem anderen Term unifiziert werden, also auch mit jedem der anderen Fälle, die anhand von irgendwelchen Mustern unterschieden werden.

Die dritte Klausel übersetzt Ausdrücke der Form if < Cond > then <Then> else < Else >. Dies geschieht ganz einfach dadurch, daß die beiden Ausdrücke < Then > und < Else > übersetzt und zu der Anfrage < Cond > -> <ThenCode>; < ElseCode > zusammengebaut werden. Man beachte, daß < Cond > nicht verändert wird, da die Bedingung sowieso schon eine Anfrage ist.

Die vierte Klausel übersetzt die Grundrechenarten, dabei bestimmen isUnary Op/1 und isBinaryOp/1, welche einstelligen bzw. zweistelligen Operatoren zugelassen sind. Aus einem Teilausdruck, der Grundrechenarten enthält, wird im Code eine Anfrage mit dem Prädikat is/2 (dies Prädikat wurde in Folge 2 besprochen). Allerdings kann man einen solchen Ausdruck nicht direkt als Argument für is/2 verwenden, da er unter Umständen noch Funktionsaufrufe oder if-then-else enthält. Diese zwei Konstrukte aus dem Ausdruck herauszuziehen, ist Aufgabe von compileArith/3. Dies übersetzt einen Ausdruck in einen neuen Ausdruck, der weder Funktionsaufrufe noch if-then-else enthält und im zweiten Argument zurückgeliefert wird. Außerdem liefert es im dritten Argument eine Anfrage, die die Behandlung der herausgezogenen Konstrukte übernimmt. Näheres dazu später.

Die fünfte Klausel dient der Übersetzung von Funktionsaufrufen. Da diese auch die Form von Funktionsköpfen haben, werden sie auch mittels splitHead/3 zerlegt, die Argumentliste hinten um eine Ergebnisvariable ResultVar erweitert und anschließend wieder mit splitHead/3 neu zusammengesetzt. Allerdings wird hier zum Erweitern der Argumentliste nicht append/3, sondern ein eigenes Prädikat compileArgs/4 verwendet. Dies ist nötig, da die Argumente des Funktionsaufrufs ja wiederum beliebige Ausdrücke sind, die Funktionsaufrufe, if-then-else usw., enthalten können. Das Vorgehen von compileArgs/4 ist allerdings recht einfach. Es wird die gesamte Argumentliste rekursiv abgelaufen. Argumente, die nur aus einer Variablen bestehen, werden nicht verändert. Kompliziertere Argumente werden durch eine neue Variable ersetzt, und es wird ein Aufruf an compileExpr/3 gemacht, der das Argument derart übersetzt, daß das Ergebnis seiner Auswertung an die neue Variable gebunden wird. Ans Ende der Liste wird dann natürlich noch die im zweiten Argument übergebene Ergebnisvariable des Funktionsaufrufs angehängt (erste Klausel). Wichtig ist dabei natürlich, daß der Code, der die Argumente berechnet, in der endgültigen Anfrage vor dem Aufruf der Funktion zu liegen kommt.

Nun fehlt noch das Prädikat compile Arith/3. Es fängt wie schon compile Expr/3 zuerst die freien Variablen und die Zahlen ab, die natürlich auch als Argumente von Grundrechenarten auftreten können. Sonst wird zwischen einstelligen und zweistelligen Operatoren unterschieden. Die Terme werden dabei immer in ihren Funktor (Operator) und die Argumente zerlegt. Die Argumente werden dann rekursiv mit compile Arith/3 übersetzt. Anschließend werden die Terme wieder zusammengebaut, wobei die übersetzten Argumente anstatt der Originale eingesetzt werden. Sobald ein Ausdruck keine der Grundrechenarten als äußersten Funktor (also einen Funktionsaufruf oderein if-then-else) enthält, ruft die fünfte und letzte Klausel compileExpr/3 auf, um diesen Ausdruck zu behandeln. Dazu wird eine neue Variable ResultVar in den Ausdruck anstelle des Konstrukts eingefügt, das von compileExpr/3 derart übersetzt wird, daß sein Ergebnis bei der Auswertung an eben diese neue Variable gebunden wird.

Damit ist der Übersetzungsvorgang komplett. Sobald man einen Ausdruck mit eval1 ausgewertet haben möchte, wird dieser Ausdruck ganz normal mit compileExpr/3 übersetzt. Anschließend wird die neu erzeugte Anfrage mittels call/1 auf gerufen und danach das Ergebnis ausgedruckt. Letzteres befindet sich in der Variablen, die dem Aufruf von compileExpr/3 als zweites Argument mitgegeben wurde.

Und jetzt?

Nachdem wir alle wesentlichen Aspekte der Programmiersprache Prolog kennengelernt haben, werden wir uns in der nächsten Folge hauptsächlich mit einem großen Beispielprogramm befassen. Außerdem werden wir rückblickend noch einmal den Unterschied zwischen Prolog und den imperativen Programmiersprachen betrachten. Das Beispielprogramm wird noch einmal ein Compiler sein. Doch diesmal wird eine Sprache compiliert, deren Umfang und Fähigkeiten weit über die diesmal vorgestellte hinausgehen. Sie ist mächtig genug, um als eine Erweiterung von Prolog tatsächlich zum Programmieren eingesetzt zu werden. Doch wie wir sehen werden, kann auch deren Übersetzung in Prolog recht einfach und kurz formuliert werden.

Manuel Chakravarty

Literatur:

[I] Clocksin/Mellish, Programming in Prolog, Springer-Verlag

r_seed(11). % Pseudozufallszahlenbasis

% rand(Max, Num) — Liefert eine Pseudozufalls- % zahl zwischen 1 und 'Max' in Num’ zurück. % % Für Toy-Prolog müssen andere Konstanten % verwendet werden (kleinerer Zahlenbereich): % 23 statt 125 und 1002 statt 4096 % Ergibt dann natürlich auch andere Zufallszahlen. % rand(Max, Num) :- r_seed(Seed), Num is (Seed mod Max) + 1, retract(r_seed(Seed)), NewSeed is (125 * Seed + 1) mod 4096, asserta(r_seed(NewSeed)), !.

Listing 1: Ein Zufallszahlengenerator

% patmat(Pattern, Term) -- Zerlegt den Term % "Term" anhand des Musters "Pattern". % patmat(_, Var) :- var(Var), !, display('ERROR: Free variable!'), nl. patmat(Var, Term) :- var(Var), !, Var = Term, patmat(Atom, Term) :- atomic(Atom), !, Atom = Term, patmat(Pattern, Term) :- Pattern =.. [Functor|PatArgs], Term =.. [Functor|TermArgs], patmatList(PatArgs, TermArgs).

patmatList([], []) :- !. patmatList([Pat|Pats], [Term|Terms]) patmat(Pat, Term), patmatList(Pats, Terms).

Listing 2: Ein Pattern-Matching-Algorithmus

:-op(1150, xfy, '->').

'->'(Cond, (Then; Else)) :- call(Cond), !, call(Then) ; call(Else). '->'(Cond, Then) :- call(Cond), !, call(Then).

Listing 3: if-then-else in Prolog

% Operatordeklarationen % :- op(870, xfx, '=>'). :- op(850, fx, 'if'). :- op(840, xfx, 'then'). :- op(830, xfx, 'else').

% compile(Rule) — Übersetzt eine einzelne % Regel und fügt sie in die Datenbank ein. %

compile(Head => Body) :- !, splitHead(Head, Func, Args), append(Args, [ResultVar], NewArgs), splitHead(NewHead, Func, NewArgs), compileExpr(Body, ResultVar, BodyGoal), stripTrue(BodyGoal, StrippedGoal), assertz((NewHead :- !, (StrippedGoal), true)), display('compiled'), nl. compile(IllegalRule) :- display (' >>> Error in " '), write(IllegalRule), display('"'), nl.

% compileExpr(Expr, ResultVar, Code) — % Übersetzt einen beliebigen Ausdruck. % compileExpr(Var, ResultVar, ResultVar = Var) :- var(Var), !. compileExpr(Num, ResultVar, ResultVar = Num) :- integer(Num), !. compileExpr(if Cond then Then else Else, ResultVar, (Cond -> ThenCode; ElseCode)) :- !, compileExpr(Then, ResultVar, ThenCode), compileExpr(Else, ResultVar, ElseCode). compileExpr(ArithExpr, ResultVar, (ArithCode, ResultVar is NewExpr)) :- ArithExpr =.. [Op|Args], (isUnaryOp(Op); isBinaryOp(Op)), !, compileArith(ArithExpr, NewExpr, ArithCode). compileExpr(FunCall, ResultVar, (ArgCodes, NewCall)) :- splitHead(FunCall, Func, Args), !, compileArgs(Args, ResultVar, NewArgs, ArgCodes), splitHead(NewCall, Func, NewArgs).

% compileArith(Expr, ResultVar, Code) -- % Übersetzt einen arithmetischen Ausdruck. % compileArith(Var, Var, true) :- var(Var), !. compileArith(Num, Num, true) :- integer(Num), !. compileArith(UnaryExpr, NewUnary, ArgCode) :- UnaryExpr =.. [UnaryOp, Arg], isUnaryOp(UnaryOp), !, compileArith(Arg, NewArg, ArgCode), NewUnary =.. [UnaryOp, NewArg]. compileArith(BinaryExpr, NewExpr, (LeftCode, RightCode)) BinaryExpr =.. [BinaryOp, Left, Right], isBinaryOp(BinaryOp), !, compileArith(Left, NewLeft, LeftCode), compileArith(Right, NewRight, RightCode), NewExpr =.. [BinaryOp, NewLeft, NewRight]. compileArith(Expr, ResultVar, ExprCode) compileExpr(Expr, ResultVar, ExprCode).

% compileArgs(Args, ResultVar, NewArgs, Code) — % Übersetzt eine Argumentliste "Args" für % einen Funktionsaufruf. % compileArgs([], ResultVar, [ResultVar], true) :- !. compileArgs([Arg|Args], ResultVar, [Arg|NewArgs], Codes) :- var(Arg), !, compileArgs(Args, ResultVar, NewArgs, Codes). compileArgs([Arg|Args], ResultVar, [ArgVar|NewArgs], (Code, Codes)) :- compileExpr(Arg, ArgVar, Code), compileArgs(Args, ResultVar, NewArgs, Codes).

% splitHead(Head, Fun, Args) — Zerteilt den % Term "Head" in einen Funktor "Fun" und % eine Liste aus Argumenten "Args". % splitHead(Head, Func, Args) Head =.. [Func|Args], !. splitHead(Func, Func, []).

% Die erlaubten einstelligen Operatoren % isUnaryOp('-'). isUnaryOp('+').

% Die erlaubten zweistelligen Operatoren % isBinaryOp('+'). isBinaryOp('-'). isBinaryOp('*'). isBinaryOp('/'). isBinaryOp('mod').

% stripTrue(Goal, StrippedGoal) — % Entfernt überflüssige "true/0" % Prädikate. % stripTrue(true, true) :- !. stripTrue((true, Goal), StrippedGoal) :- !, stripTrue(Goal, StrippedGoal). stripTrue((Goal, true), StrippedGoal) :- !, stripTrue(Goal, StrippedGoal). stripTrue((Goal1, Goal2), (StrippedGoal1, StrippedGoal2)) :- !, stripTrue(Goal1, StrippedGoal1), stripTrue(Goal2, StrippedGoal2). stripTrue((Cond -> Then; Else), (StrippedCond -> StrippedThen; StrippedElse)) :- !, stripTrue(Cond, StrippedCond), stripTrue(Then, StrippedThen), stripTrue(Else, StrippedElse). stripTrue(Goal, Goal).

% eval(Expr) — Berechnet den Ausdruck "Expr” % und gibt das Ergebnis aus. % eval(Expr) :- compileExpr(Expr, ResultVar, Goal), call(Goal), display(' Result: '), display(ResultVar), nl. eval(IllegalExpr) :- display (' >>> Error in " '), write(IllegalExpr), display('"'), nl.

% killFun(Head) — Löscht alle Regeln der % angegebenen Funktion. %

killFun(Head) :- splitHead(Head, Func, Args), append(Args, [_], NewArgs), splitHead(NewHead, Func, NewArgs), retract((NewHead :- )), fail. killFun().

Listing 4: Ein kleiner Ausdruckscompiler

---

---