Erweiterungen für Toy Prolog
Durch den Public-Domain-Service erhält jeder Atari-ST-Besitzer die Möglichkeit, die Programmiersprache Prolog zu nutzen. Auf der Diskette PD 11 ist die Implementation TOY PROLOG ST zu haben. Nun sind verschiedene Interpreter anderer Rechner mit einer größeren Zahl vordefinierter Prädikate ausgestattet. Dadurch wird die Portabilität von Prolog-Programmen eingeschränkt. Ein großer Teil des TOY-Prolog ist aber bereits in Prolog selbst geschrieben. Wir können daher genauso einige weitere Prädikate in Prolog schreiben und dem Interpreter hinzufügen. Die Programmierung solcher Prädikate soll in diesem Artikel besprochen werden. Programmiersprachen wie Pascal, BASIC oder Fortran bestehen aus einer Folge von Anweisungen, die der Computer erfüllen solI. Da heißt es z.B.' Drucke "Hallo" oder 'Gehe nach 200'. Prolog hingegen baut auf dem Begriff des Prädikats auf. Ein solches kann man sich am ehesten als Frage vorstellen. Nehmen wir zur Veranschaulichung das Prädikat sum. Rufen wir es auf als ,sum(2,3,5)', stellen wir die Frage:' Ist 2+3=5?' Da das richtig ist, erhalten wir die Antwort' yes'. Ganz analog wird dagegen die Frage ,sum( 1,3,5)' mit 'no' beantwortet.
Wollen wir sum zur Berechnung einer Summe heranziehen, müssen wir eine Variable benutzen, sum( 1 ,3,X)'. Damit fragen wir: ,Für welches X gilt l+3=X?' Der Interpreter sucht dann eine Lösung und findet X=4. Genauso können wir fragen: ,Für welches X gilt 2+X=7?' Dazu müssen wir ,sum(2,X,7)' eingeben und bekommen die Antwort ,X=5.'
Variablen beginnen übrigens mit einem großen Buchstaben, Prädikate mit einem kleinen. Zur Syntax ist weiter noch zu sagen, daß jede Anfrage mit einem Punkt abgeschlossen wird. Ist eine Lösung für eine Frage gefunden worden, wird diese ausgegeben. und der Interpreter wartet, was er nun tun soll. Soll er eine weitere Lösung des Problems suchen, dann muß ein : eingegeben werden, ansonsten ein beliebiges anderes Zeichen, beispielsweise ein Punkt.
Sehen wir uns nun einen konkreten Anwendungsfall an. Hierzu nehmen wir an, daß eine Anzahl von Prädikaten zum Thema Fußball in der Datensammlung vorhanden ist. Wir wollen nun wissen, welche deutsche Fußballmannschaft nach 1945 viermal Pokalsieger und einmal deutscher Meister war. Dazu stellen wir die Anfrage ,pokalsieger (X,4), meister (X,1)'. Diese wird beantwortet mit ,X=eintracht_frankfurt'.
Die Vorgehensweise eines Prolog-Interpreters bei der Abarbeitung einer solchen Programmzeile ist relativ schnell erklärt: Zunächst wird versucht, die erste Frage zu beantworten, also hier: Welche Mannschaft wurde viermal Pokalsieger? Da kann es durchaus mehrere Lösungen geben, z.B. werde als erste ,X=fc_köln' gefunden. (Pokalsieger 1968, 1977, 1987, 1983.) Damit wird diese Lösung an die Variable X gebunden und dann versucht, das nächste Prädikat mit dieser Lösung zu erfüllen. Es wird also die Anfrage ,meister(fc_köln)' gestellt. War der FC Köln (genau) einmal deutscher Meister? Antwort: Nein, er war dreimal Meister (1962, 1964, 1978).
Die Anfrage kann also nicht erfüllt werden. Somit geht der Interpreter zurück zur vorherigen Anfrage und sucht eine neue Lösung für diese. (Dies nennt man Backtracking.) Als nächstes findet er X=eintracht_frankfurt' (Pokalsieger 1974, 1975, 1981, 1988). Damit kann er wieder nach rechts gehen und die Anfrage meister(eintracht_frankfurt, 1)' Diesmal wird ein 'yes' die Antwort sein, Eintracht Frankfurt war nur 1959 deutscher Meister. Weil kein weiteres Prädikat zu erfüllen ist, kann die Lösung ausgegeben werden. Soll noch eine Lösung gesucht werden, geht der wieder zum vorherigen Prädikat zurück. Dort findet er aber keine mehr, daher wird 'no geantwortet.
Obwohl sich das alles recht plausibel anhört, erfordert eigenes Programmieren in Prolog doch ein totales Umdenken und vor allem viel Übung. Oft hat es sich gezeigt, daß Beispiele sehr hilfreich beim Erlernen einer Programmiersprache sind. Wer Prolog allerdings von Grund auf lernen will, der sollte sich ein Lehrbuch zulegen, Literaturhinweise finden sich am Ende des Artikels. Denn dies soll kein Einführungsartikel in Prolog sein. Wer Prolog schon sicher beherrscht, kann hier neue Anregungen finden. Wer noch nicht so sicher im Umgang mit der Sprache ist, kann etwas dazulernen. Und wer schließlich Prolog noch gar nicht kennt, wird immerhin sehen, was man mit diesem System alles machen kann.
Wie bereits erwähnt, beziehen wir uns hier vollkommen auf TOY PROLOG ST. Wir werden dem Interpreter einige Prädikate hinzufügen, die TOY-Prolog an andere Implementationen annähern sowie einige, die das Arbeiten mit Toy-Prolog erleichtern.
Neue Listenprädikate Eine wichtige Datenstruktur in Prolog ist die Liste, die man sich am einfachsten als Aufzählung von Daten vorstellen kann. Zur Darstellung einer Liste gibt es verschiedene Notationen. Am bequemsten benutzt man die eckigen Klammern, z.B. [a,s,d]. Einige Prädikate für Listen sind in Listing 1 angegeben. first(L,X) ist wahr, falls X das erste Element der Liste L ist. Was wir hierbei vor uns haben, ist eine Regel. Der Operator :-ist zu interpretieren als "falls". Die gesamte Regel würde so lauten: first(L,X) ist wahr, falls L=[X|R] wahr ist. Was bedeutet [X|R]? Durch die eckigen Klammem wird wieder eine Liste gekennzeichnet. "1" ist der Kopf-Rest-Separator, d.h. die Variable X links davon kennzeichnet das erste Element, die Variable R rechts die Restliste. Würden wir z.B. die Anfrage [a,s,d,f]=[K|R] stellen, würde sie mit K=a, R=[s,d,f] beantwortet. Der Wert, den R durch die Anfrage erhält, ist für uns unwichtig. Deshalb taucht er auch nur auf der rechten Seite der Regel auf append(L,M,N) ist ein Prädikat, das bei den meisten Interpretern bereits vorhanden ist. Hier wird getestet, ob N die Liste ist, die durch Aneinanderhängen der Listen L und M entsteht. Natürlich können an jeder Stelle Variablen stehen.
append wird durch zwei Regeln rekursiv realisiert. Die erste Regel besagt, daß die leere Liste [] verkettet mit einer beliebigen Liste L wieder L ergibt. Bei der Lösungssuche wird zuerst versucht, diese Regel zu erfüllen. Dies wird im allgemeinen nicht gelingen. da der Benutzer meistens nichtleere Listen angeben wird. Da aber durch die Rekursion irgendwann dieser Fall doch auftritt, benötigen wir diese Regel als Randbedingung. Das Ausrufezeichen heißt in Prolog "Cut". Es bewirkt hier, daß nur eine Lösung gefunden werden soll. Es wären durchaus mehrere möglich, wenn append mit Variablen in den ersten beiden Argumenten aufgerufen wird. Aber durch den Cut wird das Auffinden weiterer Lösungen unterbunden.
Die zweite Regel lautet nun: append([K|R1],L,[K|R2]) ist wahr, falls append(R1,L,R2) wahr ist. D.h. die Anfrage wird auf den einfacheren Fall zurückgeführt, bei dem die ersten Elemente der jeweiligen Listen abgetrennt sind, was wieder mit dem Kopf-Rest-Separator gemacht wird. Dies geht jedoch nur dann gut, wenn beide Kopf-Elemente tatsächlich identisch sind, denn sie werden durch dieselbe Variable K repräsentiert. Andernfalls schlägt die Anfrage fehl.
Beim Prädikat last(L,X), das uns das letzte Element einer Liste liefert, verwenden wir append: last(L,X) ist wahr, falls L durch Aneinanderhängen einer beliebigen Liste und [Xl entsteht. Auf ähnliche Art hätten wir auch first definieren können. Aber die Verwendung von append hätte Geschwindigkeit bei der Ausführung gekostet. Bei last hingegen kommen wir an einer Rekursion nicht vorbei, da eine Liste intern baumartig dargestellt ist und das letzte Element das am weitesten von der Wurzel stehende Element des Baums ist.
Das I-te Element X der Liste L erhalten wir durch item(I,L,X). Die Randbedingung sagt diesmal aus, daß X das erste Element der Liste ist, falls X der Kopf der Liste ist, so formuliert eine triviale Aussage. Der Cut sorgt wieder dafür, daß nur eine Lösung gesucht wird. Der Rest geschieht wie bei append rekursiv. Um die Listenelemente zu zählen, verwenden wir hier eine Hilfsvariable J. Diese wird um 1 kleiner als I. Anstelle von = müssen wir hier den Operator is verwenden, da is arithmetische Ausdrücke auswertet, = aber nicht. Die Rekursion reduziert die Anfrage jeweils auf den einfacheren Fall einer um 1 kürzeren Liste. Dies geht so lange, bis X als erstes Element einer Liste dasteht oder die Liste durch die Rekursion leer geworden ist. Listing 2 zeigt, auf welche verschiedenen Arten die neu definierten Prädikate aufgerufen werden können. Die Zeichen ?-werden vom Interpreter vorgegeben und erinnern den Benutzer daran, daß er nun eine Anfrage stellen kann. Das letzte Beispiel zeigt den Aufruf der neu definierten Prädikate für Ein/Ausgabe, die nun besprochen werden sollen.
Prädikate für Ein/Ausgabe
Die genauen Dehnitionen sind in Listing 3 angegeben. In Anlehnung an Pascal definieren wir zunächst das Prädikat writeln(X), welches nach Ausgabe von X einen Zeilenvorschub durchführt. In Toy-Prolog wird ein Zeilenvorschub durch nl gekennzeichnet. Das Prädikat tab(X) gibt X Leerzeichen aus. Die Definition erfolgt wieder rekursiv. Als Randbedingung geben wir tab(O) an. Die dritte, rekursive Regel gibt jeweils ein Leerzeichen mittels weh aus und bezieht sich dann auf den nächst niedrigeren Fall. Dies geht so lan-ge, bis tab(O) aufgerufen wird. Bei Aufruf mit einem negativen Wen würde die Rekursion so bis ins Unendliche gehen. Deshalb müssen wir da einen Riegel vor-schieben und diesen Fall ausschließen. In der zweiten Regel wird zunächst gete-stet, ob X
Listing von Prädikaten
In Prolog ist es möglich, mit dem Prädikat Listing den Text sämtlicher Prädikate aufzulisten. Ein unglücklicher Umstand bei Toy-Prolog ist es, daß hierdurch auch die Systemprädikate betroffen sind, die ja auch in Prolog geschrieben sind. Anstelle eines kurzen Listings der wenigen selbstdefinierten Prädikate, an denen man gerade arbeitet, erhält man so fast den gesamten Inhalt der Systemdatei ausgegeben. Was wir nun selbst programmieren wollen, ist ein Prädikat, das nur die von uns definierten Prädikate listet. Dazu müssen wir einen kleinen Eingriff in das System vornehmen. Wir nehmen einmal an, wir lesen alle unsere Prädikate jeweils mit consult ein. Dann definieren wir einfach ein neues Prädikat bad, welches genau dasselbe wie consult erledigt, aber zusätzlich jedes eingelesene Prädikat markiert. Das Prädikat list wird dann nur diejenigen Prädikate auflisten, die mittels bad markiert wurden.
Glücklicherweise müssen wir uns die Programmierung von bad nicht von Grund auf neu überlegen, denn mit Listing können wir ja den Text von consult erhalten. In Listing 4 sehen wir das Ergebnis. Die Prädikate see, seeing und seen öffnen und schließen Dateien, echo und noecho sorgen für die Wiedergabe auf dem Bildschirm. Von Interesse ist für uns nur get-prog. Er stellt die Schleife dar, in der die Prädikate eingelesen und definiert werden.
Wie wir das nun verwenden müssen, können wir in Listing 5 sehen. bad schreiben wir wie consult, ersetzen aber read-prag durch readprogram. Dieses wird wie readprog definiert, jedoch getprog wird nun getprogram genannt. getprogram schließlich wird wie getprog definiert, nur schieben wir make_listable(X) ein. Dies sorgt dafür, daß das Prädikat P, das durch die Regel X definiert ist, markiert wird. Die Markierung geschieht durch Hinzufügen der Klausel listable(P) zur Datenbank. (Eine Klausel ist eine Regel ohne Bedingung.) Weil jede Datei durch end abgeschlossen werden muß, wird somit auch jedesmal ein listable(end) der Datenbank hinzugefügt. Dies ist aber nicht erwünscht, durch retract (listable(end)) wird es wieder entfernt.
make_listable(X) holt sich den Namen P des Prädikats, das durch X definiert wird, und prüft, ob listable(P) bereits vorhanden ist. Wenn nein, wird es hinzugefügt.
Auf das Prädikat pred(X,K) soll nicht so ausführlich eingegangen werden. Es prüft, ob K der Name des Prädikats ist, das durch die Regel X definiert wird. Eine Fallunterscheidung muß vorgenommen werden. Denn einmal kann X eine Regel mit dem Operator :- sein, zum anderen eine grammatische Regel mit dem Operator->. Außerdem ist es möglich, daß X eine Klausel ist. Das Prädikat list holt sich mit listable(X) jeweils ein markiertes Prädikat und gibt mittels listing(X) dessen Programmtext aus. Das fail am Ende sorgt dafür, daß die Anfrage fehlschlägt und durch Backtracking nacheinander alle Lösungen von listable(X) gefunden werden.
Fassen wir also zusammen: Laden wir eine Datei mit load, werden alle Prädikate daraus markiert. list gibt eine Auflistung nur der markierten Prädikate. Wollen wir Eingaben im Direktmodus machen, so können wir eine Markierung auch erreichen. Wir müssen nur load(user) eingeben. Außerdem kann ein Prädikat nachträglich markiert werden. Nötig ist ein Hinzufügen von listable(P) zur Datenbank.
Aus Gründen der Einheitlichkeit definieren wir zusätzlich list(P), welches nur den Text des Prädikats P listet. listable gibt eine Liste aller markierten Prädikate. Da die Lösungen von listable(X), das als erstes aufgerufen wird, explizit in der Datenbank stehen, werden sie vom Interpreter leicht gefunden.
oblist gibt die Namen aller in Prolog definierten Prädikate aus, also auch die aus der Systemdatei. Erzeugt werden sie als Lösungen der Anfrage proc(X), die restlichen Prädikate aus dieser Regel dienen nur der optischen Autbereitung, so etwa Abtrennen der Argumente etc. oblist arbeitet ebenso wie listable mit der Schleifenbildung durch fail.
Impiementierung des Break Die Anweisung break unterbricht den Programmlauf und führt den Benutzer wieder auf die oberste Interpreterebene. Zur Kennzeichnung wird eckigen Klammern das Break-Level angezeigt, denn Verschachtelungen sind möglich. Nun können beliebige Anfragen gestellt werden. Durch Eingabe von cont gelangt man wieder ein Level tiefer. Das dort begonnene Programm wird nun fortgeführt.
Um dies nachträglich in Prolog zu programmieren, müssen wir uns dieses Mal die Interpreterschleife ansehen. Der Dokumentation zu Toy-Prolog entnehmen wir, daß der sogenannte äußere Interpreter durch das Prädikat ear gestartet wird. Mit listing verschaffen wir uns wieder den Programmtext (siehe Listing 6).
Ear ruft loop auf. In der Schleife loop wird die Benutzereingabe gelesen und ausgeführt. Ein paar Worte müssen zu dem Aufruf von loop gemacht werden. loop ist eine Endlosschleife. Dafür sorgt die repeat/fail-Konstruktion. Riefe man dieses Prädikat einfach durch Angabe des Namens auf, würde es nie zum Ende kommen. Das ist aber nicht erwünscht. Durch den Aufruf tag(loop) erhalten wir die Möglichkeit, später von außen auf die Erfüllung des Prädikats loop Einfluß zu nehmen. Denn ein Aufruf von tagfail(loop) bewirkt, daß loop sofort fehlschlägt, was damit auch für ear gilt. Der Interpreter versucht dann, ear mittels der zweiten Regel zu erfüllen. Dort wird durch halt der Interpreter abgebrochen.
Die Idee zur Programmierung des Break ist nun die folgende: Das Prädikat break wird analog zu ear programmiert. Die ausgegebenen Meldungen werden jedoch anders aussehen. ear ruft statt loop das Prädikat breakjoop auf. Dieses sieht fast genauso wie loop aus, nur wird das Break- Level in eckigen Klammem mit ausgegeben. cont entspricht stop.
Die Realisierung finden wir in Listing 7. Zur Kennzeichnung des Break-Levels existiert jeweils ein Prädikat breakJevel(X). Durch Aufruf von die-sem wird X auf den entsprechenden Wert gesetzt. Geht man in ein anderes Break-Level, muß dieses Prädikat gelöscht und durch das mit dem neuen Wen ersetzt werden. So ist zu Beginn das Prädikat break_level(0) vorhanden. Bei Aufruf von break wird es gelöscht und durch break_level(1) ersetzt. Eingabe von cont macht dies wieder rückgängig.
Listing 8 zeigt uns die Wirkungsweise von break. Nachdem das Atom 'eins' ausgegeben wurde, gelangen wir auf Break-Level 1. Dort können wir uns 'zwei' ausgeben lassen. Nach Eingabe von cont gelangen wir zurück. Dort muß die angefangene Programmzeile noch beendet werden, d.h. 'drei' wird ausgegeben.
Einen echten Anwendungsfall sehen wir in Listing 9. Angenommen, wir haben das Prädikat tier für eine Anzahl von Daten in der Datenbank. tier(elefant) beispielsweise soll heißen: Der Elefant ist ein Tier. Die Aufgabe soll darin bestehen, für jedes Tier, das vorhanden ist, ein Prädikat ordnung einzugeben, das die biologische Ordnung des jeweiligen Tieres angibt. Dazu können wir den Break benutzen.
Zur Illustration geben wir zunächst mit assert drei Daten ein. Bei der folgenden Anfrage findet tier(X) jeweils eins dieser Tiere, write(X) gibt es aus. Der dann folgende Break bringt uns auf die Interpreterebene, in der wir Eingaben machen können. Wir fügen dann das entsprechende Prädikat ein. Zuerst wird fledermaus gefunden. Wir wissen, die Fledermaus gehört zur Ordnung der Flattertiere und geben dies ein. Nach cont wird die Anfrage fortgesetzt, wir erhalten das nächste Tier. Das fail bildet wieder eine Schleife.
Einbau der neuen Prädikate
Das Toy-Prolog-System erlaubt es nun, die neu definierten Prädikate der Systemdatei hinzuzufügen, so daß sie nach Starten des Systems direkt zur stehen. Wie das gemacht wird, jetzt noch besprechen. Zunächst schreiben wir mit einem Editor alle Prädikate, die wir in unserem System neu haben wollen, in eine einzige Datei. Wir nennen sie jetzt einmal ERWEIT. Die letzte Zeile bildet die Anweisung end., der Punkt darf nicht fehlen. Jetzt starten wir den Prolog-Interpreter und rufen das Prädikat translate auf. Hiermit übersetzen wir den von uns geschriebenen Code in die Syntax des inneren Interpreters. Der Aufruf lautet translate(erweit, erw). Der gebildete Code wird in der Datei ERW abgelegt.
Mit stop beenden wir Prolog und starten wieder den Editor. Hier laden wir zunächst die Datei ERW und löschen deren letzte drei Zeilen. Diese bestehen aus einem Doppelpunkt, dem Wort seen und der Zeichenkombination []#. Nun laden wir die Datei SYSFILE.TOY und gehen mit dem Cursor an das Ende des Textes. Dort finden wir nach einem Doppelpunkt einige Anweisungen, die direkt ausgeführt werden sowie die Definition des letzten Prädikats, unprotect. Dieses endet mit []. Zwischen [] und den Doppelpunkt wird die geänderte Datei ERW nun geladen.
Das war fast schon alles. Wie wir aber sehen, werden durch protect alle geladenen Prädikate geschützt. Das Prädikat break_level wird jedoch bei Aufruf von break verändert, was bei einem geschützten Prädikat nicht möglich ist. Deshalb müssen wir nur hierfür den Schutz rückgängig machen. Wie die letzten Zeilen von SYSFILE.TOY aussehen sollten, zeigt Listing 10.
1: tab(0).. 2: tab(X) :- x<0, !, fail. 3: tab(X) :- Y is X - 1, wch(' '), tab(Y). 4: 5: writeln(X) :- write(X), nl.
Eckart Winkler