Pro Logik: Prolog für Einsteiger, Teil 3

Einer der großen Vorteile von Prolog gegenüber gewöhnlichen, imperativen Programmiersprachen ist die recht einfache Programmierung von Datenstrukturen. Vor allem Listen, Baumstrukturen und nichtzyklische Graphen können in Prolog sehr komfortabel und übersichtlich behandelt werden. Die Unifikation ist dabei der Schlüsselmechanismus zum Verarbeiten solcher Strukturen. Wie das genau vor sich geht, ist Inhalt dieser Folge.

In der letzten Folge haben wir die grundlegenden Mechanismen der Programmiersprache Prolog kennengelernt. Diese Mechanismen werden wir in dieser Folge zur Programmierung von Datenstrukturen einsetzen, die so allgemein gehalten sind, daß man sie zur Lösung vieler Programmieraufgaben einsetzen kann. Im Laufe dieser Folge werden wir uns viel mit Listen und Bäumen beschäftigen und sehen, daß sie sehr universelle Hilfsmittel beim Programmieren darstellen. Dabei werden wir auch einige Tricks kennenlernen, die bei der Verwendung solcher Datenstrukturen zu einer wesentlichen Effizienzsteigerung führen.

Eins nach dem anderen

Die in Prolog am häufigsten verwendete Datenstruktur ist die Liste. Deshalb besitzt sie, wie in der ersten Folge vorgestellt wurde, sogar eine eigene, spezielle Schreibweise. Dabei bieten Listen genaugenommen nur die Möglichkeit, beliebig viele Daten zu einer Einheit zusammenzufassen. Die einzige Struktur, die eine solche Ansammlung von Daten besitzt, ist die Reihenfolge, in der die einzelnen Elemente in der Liste stehen. Zum Beispiel könnte man auf die Idee kommen, eine Reihe von CD-Titeln in einer Liste zu speichern. Eine solche Liste könnte etwa wie folgt aussehen: [world_outside, eugine, seventeen_seconds]. Mit dem eingebauten Prädikat member|3 kann in einer Liste nach einem Element gesucht werden. Dies wird in der folgenden Anfrage gemacht.

?- member(eugine, [world_outside, eugine, seventeen_seconds]).

Die Anfrage wird von dem Prolog-System mit yes beantwortet. Die Definition des Prädikats member|3 ist recht einfach und lautet wie folgt:

member(X, [X|_]). member(X, [_|Xs]) :-member(X, Xs).

Die erste Klausel testet, ob das erste Element der Liste schon das gesuchte Element ist. Ist dies der Fall, bricht member|3 hier erfolgreich ab. Sonst wird die zweite Klausel benutzt, die das erste Listenelement ignoriert und stattdessen rekursiv auf dem Listenrest weiterarbeitet. Ist das gesuchte Element nicht in der Liste, langt member|3 irgendwann bei der leeren Liste an (pro Rekursionsschritt wird die Liste eins kürzer) und schlägt fehl. Somit realisiert memberß eine lineare Suche auf Listen.

Noch sinnvoller ist es, in unserem Beispiel nicht nur die Titel, sondern auch die Namen der Interpreten mit aufzuführen. Dies kann ganz einfach dadurch geschehen, daß in die Liste statt einzelner Atome wiederum Listen eingetragen werden. Jede dieser Listen enthält dann zwei Elemente, nämlich einen Interpreten und einen Titel. Die Beispielliste lautet dann [[the_psychedelic_furs, world_outside], [the_popguns, eugine], [the_cure, seventeen_seconds]]. Wie vorher können wir das Prädikat member|3 zur Suche innerhalb der Liste einsetzen. Doch bevor wir damit fortfahren, wollen wir uns etwas Tipparbeit sparen.

Die Liste, die sowohl Interpreten als auch Titel enthält, ist zum wiederholten Eintippen schon etwas lang, und sobald man die eigene CD-Sammlung derart bearbeiten will, wird sie bei den meisten wohl noch etwas länger. Es wäre also sehr schön, wenn man sie einmal eingeben und dann mit einem etwas kürzeren Namen referenzieren könnte. In Prolog läßt sich das einfach dadurch realisieren, daß wir die CD-Liste als Fakt in die Datenbank aufnehmen. Wir behandeln sie also sozusagen wie ein Programm, das nur aus einem einzelnen Fakt besteht, der wie folgt lautet:

cds([[the_psychedelic_furs, world_outside], [the_popguns, eugine], [the_cure, seventeen_seconds]]).

Wir können es wie gewohnt im Texteditor eingeben und dann mittels consult!1 laden. Anschließend können wir etwa die folgende Anfrage stellen.

?- cds(CDs).

Sie wird mit CDs = [[the_psychedelic_furs, world_outside], [the_popguns, eugine], [the cure, seventeen_seconds]] beantwortet.

Kommen wir zu unserem ursprünglichen Thema, der Listenverarbeitung, zurück. Wir können nun auch die etwas komplexe CD-Liste mit dem member|3-Prädikat durchsuchen. Eine beispielhafte Anfrage lautet etwa wie folgt.

?- cds(CDs), member([the_popguns, eugine], CDs).

Sie wird von Prolog, wie zu erwarten war, mit yes beantwortet. Doch es kommt noch besser. In einer CD-Liste möchte man eventuell nicht nur nachschauen, ob eine bestimmte CD von einem bestimmten Interpreten vorhanden ist. Stattdessen interessiert zum Beispiel, ob überhaupt eine CD eines Interpreten in der Liste ist, und wenn ja, welchen Titel diese CD besitzt. Diese Aufgabe ist für Prolog ein Kinderspiel, wie die folgende Anfrage zeigt.

?- cds(CDs), member([the_cure, Title],CDs).

Das Resultat der Anfrage lautet Title = seventeen_seconds. Sind in der Liste mehrere CDs vorhanden, die Cure als Interpreten besitzen, liefert Prolog an dieser Stelle natürlich auf die Anfrage alle möglichen Lösungen in der Reihenfolge, in der sie in der Liste stehen.

An diesem Beispiel wird der flexible Umgang von Prolog mit Datenstrukturen recht deutlich. Er ist im wesentlichen auf den Mechanismus der Unifikation zurückzuführen, der in der letzten Folge behandelt wurde. In dem Beispiel versucht das Prädikat member/2 die einzelnen Elemente der CD-Liste mit dem Term [the_cure, Title] zu unifizieren. Das Atom the_cure läßt sich dabei nur mit sich selber, d.h. einem Atom gleichen Namens, unifizieren. Im Gegensatz dazu kann Title mit jedem beliebigen Term unifiziert werden, da Title eine Variable ist. Zusammengenommen heißt das, daß der Term [the_cure, Title] mit dem ersten Listenelement, das als Interpreten the_cure enthält, erfolgreich unifiziert wird.

Um nun alle Titel eines bestimmten Interpreten in einer Liste aufzusammeln, können wir das Prädikat collectTitles|3 aus Listing 1 verwenden. Es durchsucht die übergebene CD-Liste, ähnlich wie member|2, rekursiv. Allerdings wird nicht abgebrochen, wenn ein Titel gefunden wurde (zweite Klausel), sondern dieser in die Ergebnisliste aufgenommen und weitergesucht. Bevor wir noch ein paar wichtige Techniken der Listenprogrammierung kennenlernen, wollen wir uns zunächst eine weitere oft verwendete Datenstruktur und deren Implementierung in Prolog ansehen.

Waldmeister

Im Gegensatz zu Listen besitzen Bäume eine stärker ausgeprägte Struktur. Diese wird oft benutzt, um zusätzliche Information zu speichern oder vorhandene für das Programm leichter verwertbar darzustellen. Ein Beispiel sind etwa Strukturbäume, die in Compilern verwendet werden, um die syntaktische Struktur eines Programms explizit darzustellen. Die Information ist schon in der sequentiellen Form des Programms (zum Beispiel als Liste aus Buchstaben) vorhanden, doch kann sie in dieser Form von einem Programm gar nicht oder nur sehr schwer genutzt werden (siehe zum Beispiel [2]). Außerdem können Bäume genauso zur schlichten Speicherung von Daten eingesetzt werden, wobei dann ein schnelleres Auffinden und Einfügen von Daten als bei Listen möglich ist.

Binärbaume, d.h. Bäume, in denen jeder einzelne Knoten genau zwei Nachfolger hat oder ein Blatt ist, wurden in der ersten Folge dieser Serie schon kurz vorgestellt. Dort wurden die Knoten eines Baumes durch Terme mit dem Funktor node|2 und Blätter mit leaf|1 dargestellt. Ein Beispiel eines solchen Baums ist node(node(leaf(5), leaf(2)), node(node(leaf(8), leaf(7)), leaf(1)))). Dieser Baum ist in Abb. 1 grafisch dargestellt.

Ein einfaches Prädikat, das Bäume dieser Art als Eingabe erwartet, ist sumTree|2. Es addiert die Werte in den einzelnen Blättern eines Baums und liefert die Summe im zweiten Argument als Ergebnis. Das Prädikat ist in Listing 2 abgebildet. Es besteht wie so oft aus zwei Klauseln. Die erste ist die Rekursionsabbruchbedingung und besagt, daß die Summe eines Blatts genau der Wert des Blatts ist. Die zweite Klausel beschreibt die Tatsache, daß die Summe eines Baums, der aus einem linken und einem rechten Teilbaum besteht, einfach die Summe des linken plus die Summe des rechten Teilbaums ist. Um uns ähnlich wie bei dem Beispiel mit den CDs etwas Tipparbeit bei der Anfrage zu sparen, ist der oben angegebene Baum in dem Fakt tree! 1 gespeichert. Eine Anfrage kann dann zum Beispiel wie folgt aussehen:

?- tree(Tree), sumTree(Tree, Sum).

Die Antwort lautet dann Sum = 23. Das Prädikat sumTree|2 unterscheidet sich bisher noch nicht wesentlich von den Prädikaten zur Listenverarbeitung, wie zum Beispiel die CD-Titelsuche. Ein bemerkenswerter Unterschied ist allerdings, daß sumTree|2 in der zweiten Klausel doppelt rekursiv ist, d.h. zweimal rekursiv aufgerufen wird. Dies war bei der CD-Titelsuche nicht der Fall. Aber genau diese doppelte Rekursion ist es, die uns im folgenden schwer zu schaffen machen wird.

Das Schöne an sumTree|2 ist, daß das Ergebnis eine einfache Zahl ist. Die Zwischenergebnisse, die in der zweiten Klausel beim rekursiven Aufruf für den linken und rechten Teilbaum entstehen, lassen sich dabei sehr einfach durch eine Addition zum Ergebnis für den kompletten Baum zusammenfassen. Anders wird das zum Beispiel, sobald man auf die Idee kommt, einen Baum in eine Liste umzuwandeln, d.h. es sollen die Werte aller Blätter eines Baums in eine Liste geschrieben werden.

In Listing 3 sind drei verschiedene Prädikate zu finden, die alle genau diese Aufgabe erfüllen. Uns soll zunächst nur das erste dieser Prädikate, also flattenTree|2, interessieren. Es führt diese Umwandlung mit Hilfe zweier Klauseln durch. Die erste behandelt die Blätter des Baums und wandelt ein Blatt einfach in eine einelementige Liste um, die lediglich den Wert des Blatts enthält. Die zweite Klausel behandelt hingegen die Knoten und wandelt (doppelt rekursiv) erst den linken und dann den rechten Teilbaum in eine Liste um. Die beiden Teillisten werden dann mit append|3 zur Gesamtliste kombiniert. In Abb. 2 ist der Vorgang grafisch dargestellt. In jedem Blatt wird eine Liste erzeugt, die als einziges Element den Wert des Blattes enthält. In den einzelnen Knoten des Baumes werden die Listen des linken und rechten Teilbaums zu einer Gesamtliste zusammengefaßt. Das Ergebnis ist dann die Liste, die in der Wurzel des Baumes entsteht. Soweit sieht das Ganze auch noch sehr schön aus. Unangenehm wird es allerdings, sobald man sich den Aufwand dieser naiven Version zur Linearisierung von Bäumen ansieht. Um besser sehen zu können, wo das Problem liegt, schauen wir uns noch einmal das Prädikat append!3 an.

append([], Xs, Xs). append([X|Xs], Ys, [X|Zs]):-append(Xs, Ys, Zs).

Wie man sieht, spaltet append|3 in jedem Rekursionsschritt der zweiten Klausel ein Element (das vorderste) von der Liste ab, die im ersten Argument steht. Dies geschieht mit dem Term [X/Xs]. Die Restliste, also Xs, wird an den rekursiven Aufruf weitergegeben, der dann das nächste Element abspaltet, usw. Dieser Vorgang endet, sobald die Liste im ersten Argument zur leeren Liste reduziert wurde. Kurz gesagt, append!3 mft sich genauso oft rekursiv auf, wie die Liste im ersten Argument lang ist. Genaugenommen wird sogar ein Aufruf mehr gemacht, da der letzte Aufruf die leere Liste übergeben bekommt Das bedeutet zum Beispiel, daß append([1, 2,3], [4,5], L) zu vier Rekursionen führt, eine für 1, eine für 2, eine für 3 und eine für die leere Liste. Man sagt auch, der Aufwand von append|3 ist linear proportional zur Länge der Liste, die im erstem Argument übergeben wird.

Nun wird append|3 in der naiven Version des Prädikats flattenTree|2 einmal pro Knoten des Baums aufgerufen, und zwar mit der linearisierten Form des linken Teilbaums als erstem Argument Besitzt der linke Teilbaum also ‘n’ Blätter, so benötigt append|3 ‘n+1’ Rekursionen. Da die linearisierte Form des Unken Teilbaums aber durch einen rekursiven Aufruf von flattenTree|2 berechnet wird, wird hier (falls der Baum nicht nur aus einem Blatt besteht) noch einmal append|3 aufgerufen. Die Anzahl der Rekursionen hängt auch hier wieder von der Anzahl der Blätter im linken Teilbaum dieser Rekursionsstufe ab. Wenn wir annehmen, daß die Blätter innerhalb des Baums immer gleichmäßig auf die rechten und linken Teilbäume verteilt sind, so sind es diesmal also ‘(n/2)+1’ Rekursionen. Der linke Teilbaum hat ‘n’ Blätter und teilt sich in einen linken und einen rechten Teilbaum mit je ‘n/2’ Blättern. Insgesamt sind es jetzt also schon ‘ (n+1 )+((n/2)+1) ’ Rekursionen. Da der linke Teilbaum des linken Teilbaums aber wieder rekursiv mittels flattenTree|2 berechnet wird, setzt sich das ganze immer weiter so fort.

Eine genaue Berechnung der Anzahl der benötigten Rekursionen wollen wir uns hier sparen. Nur soviel: Im schlechtesten Fall (ein zu einer Liste degenerierter links-rekursiver Baum) ist die Zahl der Rekursionen ungefähr ’1+2+3+...+n’, wenn der Baum n+1 Blätter besitzt. Dies ist aber genau die Gaußsche Reihe, die bekanntlich gleich ‘n*(n+1)/2’ ist. Die Anzahl der Rekursionen von append|3-Aufrufen hängt dann also ungefähr quadratisch von der Anzahl der Blätter im Baum ab. Und dabei haben wir die Anzahl der Rekursionen von flattenTree|2 noch komplett weggelassen. Dies erscheint angesichts der einfachen Aufgabe, die Blätter eines Baums in eine Liste einzutragen, wohl etwas übertrieben.

Wie wir im weiteren sehen werden, gibt es zwei andere Versionen, von flattenTree|2, die beide völlig ohne einen append|3-Aufruf auskommen und somit in der Anzahl ihrer Rekursionen linear proportional zur Anzahl der Knoten des Baums sind.

Da der hohe Aufwand von den append|3-Aufrufen herrührt, ist es sicherlich einen Versuch wert, sie durch einen anderen Mechanismus zu ersetzen. Dazu wollen wir uns noch einmal die Funktionsweise von flattenTree|2 vor Augen halten. Der Rekursionsschritt besteht darin, daß zuerst der linke und dann der rechte Teilbaum in eine Liste umgewandelt werden. Anschließend werden diese Listen zusammengehängt. Wenn es möglich wäre, die Elemente gleich in eine Liste zu schreiben, statt sie auf zwei Listen zu verteilen, würde auch das Zusammenhängen und damit der teure append|3-Aufruf entfallen.

Sammler

Das Prinzip, die Elemente von vornherein in eine einzige Liste zu schreiben, wird in dem Prädikat flattenTreeAccu|2 realisiert Die Idee dabei ist, rekursiv durch den Baum zu laufen und, wann immer man an einem Blatt vorbeikommt den zum Blatt gehörenden Wert in die Ergebnisliste aufzunehmen. Die Liste wird dabei sozusagen zum Aufsammeln der einzelnen Werte benutzt und deswegen Akkumulator genannt Das prinzipielle Vorgehen von flattenTreeAccu|2 wird in Abb. 3 grafisch dargestellt Der Algorithmus fängt in der Wurzel des Baumes mit einer leeren Liste an und arbeitet sich dann linksrekursiv durch den Baum hindurch. Dabei wird zuerst der Wert 5, dann 2 usw. aufgesammelt Die einzelnen Werte werden dabei immer vome in die Liste geschrieben.

Schaut man sich das Prädikat flattenTreeAccu|2 in Listing 3 an, so fällt auf, daß es zunächst ein Hilfsprädikat flattenTreeAccu|3 aufruft (die beiden Prädikate stören sich nicht, da sie verschiedene Stelligkeiten, d.h. Anzahl von Argumenten, haben). Dieses Hilfsprädikat bekommt im ersten Argument den Baum übergeben, der linearisiert werden soll. Das zweite Argument ist der Eingabeweit des Akkumulators, d.h. der Liste, die die Werte aufsammelt. Zu Beginn, also beim Aufruf im Rumpf von flattenTreeAccu|2, ist dies die leere Liste. Das dritte Argument ist im Gegensatz zu den anderen beiden ein Ausgabeargument, d.h. ein Argument, in dem ein Wert an den Aufrufer zurückgeliefert wird. Es liefert das Ergebnis, also die Liste, die die aufgesammelten Werte enthält.

Das Prädikat flattenTreeAccu|3 unterscheidet zwischen Blättern und Knoten des Baums. In der ersten Klausel, in der die Blätter behandelt werden, wird der Wert des Blattes einfach zu der Liste (dem Akkumulator), die im zweiten Argument übergeben wird, hinzugefügt. In der zweiten Klausel wird die Akkumulatorliste listln an den rekursiven Aufruf übergeben, der den linken Teilbaum behandelt. Das Ergebnis dieses Aufrufs ist ListTemp, das gegenüber ListIn um die Blätter des linken Teilbaums erweitert wurde. Dieses Zwischenergebnis wird nun als zweites Argument an den zweiten rekursiven Aufruf von flattenTreeAccu|3 übergeben, der den rechten Teilbaum behandelt Dieser zweite Aufruf erweitert die Liste nun noch um die Werte der Blätter des rechten Teilbaums und liefert das Ergebnis in der Variablen ListOut. Diese bildet gleichzeitig den Ergebniswert der zweiten Klausel des Prädikats flattenTreeAccu|3. Zusammenfassend kann man sagen: In der zweiten Klausel wird die Liste ListIn zuerst um die Werte der Blätter des linken Teilbaums erweitert wobei sie den Namen ListTemp erhält. Anschließend werden noch die Blätter des rechten Teilbaums zu ListTemp hinzugefügt wonach die Liste mit ListOut bezeichnet wird.

Offensichtlich wurde die Benutzung des Prädikats append|3 durch die Verwendung eines Akkumulators komplett überflüssig. Der Aufwand von flattenTreeAcuu|2 ist somit wie angekündigt linear proportional zur Anzahl der Knoten im Baum, da jeder Knoten (wobei Blätter auch als Knoten gelten) genau einmal besucht wird. Dies ist aber auch schon der minimale Aufwand, der für das Linearisieren eines Baums erzielt werden kann.

Die Verwendung von Akkumulatoren in der eben gezeigten Art hat allerdings einen Haken. Im Gegensatz zu flattenTree|2 liefert flattenTreeAccu|2 eine Liste, in der die Werte des Baums in umgekehrter Reihenfolge enthalten sind. Das sieht man an den folgenden beiden Anfragen:

?- tree(Tree), flattenTree(Tree, List).

Diese Anfrage liefert als Ergebnis List = [5, 2, 8, 7, 1 ]. Anders ist dies bei der nächsten Anfrage:

?- tree(Tree), fiattenTreeAccu(Tree, List).

Hier ist die Antwort des Prolog-Systems List = [1, 7, 8, 2, 5], d.h. die Elemente haben genau die umgekehrte Reihenfolge. Dies liegt daran, daß die einzelnen Werte immer an den Anfang der Akkumulatorliste geschrieben wurden. Oft ist dies keine wesentliche Einschränkung, da die Reihenfolge der Werte in der Liste nicht von Bedeutung ist, oder da nachfolgende Berechnungen die Reihenfolge ohne zusätzlichen Aufwand wieder umkehren können. In unserem Beispiel ist es auch nicht schwierig, die Reihenfolge zu ändern, in der flattenTreeAccu|2 die Ergebnisliste liefert. Dazu muß in der zweiten Klausel von flattenTreeAccu|3 nur die Reihenfolge der Rekursionen geändert werden, d.h. zuerst wird der rechte und dann der linke Teilbaum abgelaufen.

Allerdings gibt es auch manchmal Programme, in denen erstens die Reihenfolge der Elemente in der Liste von Bedeutung und zweitens eine Umkehrung der Rekursion nicht so ohne weiteres möglich ist. Möchte man zum Beispiel einen Compiler schreiben, in dem aus einem Strukturbaum eine Liste von Assembler-Befehlen erzeugt wird, ist es wohl kaum akzeptabel, wenn die Befehle in der falschen Reihenfolge erzeugt werden. Andererseits kann man die Reihenfolge, in der man die einzelnen Teilbäume eines Strukturbaums abläuft, meist nicht so einfach umkehren. Dies würde nämlich bedeuten, daß der Code von hinten her erzeugt wird. Da der Code, den man erzeugt, aber oft von vorhergehenden Instruktionen abhängt, ist dies nicht so einfach möglich. Eine letzte Möglichkeit ist nun, die Liste in umgekehrter Reihenfolge zu erzeugen und sie anschließend umzukehren. Zwei Prädikate, die die Reihenfolge der Elemente einer Liste umkehren, sind in Listing 4 abgebildet. Das Prädikat reverse|2 ist eine naive Version, die wieder mit Hilfe von append|3 arbeitet. Es hat leider mal wieder einen Aufwand, der quadratisch proportional zur Länge der übergebenen Liste ist, und ist daher für unseren Verwendungszweck denkbar ungeeignet. Anders sieht es mit dem Prädikat reverseAccu|2 aus. Es hat, durch die Verwendung eines Akkumulators, nur einen Aufwand, der linear proportional zur Länge der Liste ist. Der Trick von i ist ganz einfach, daß es die Elemente der Eingabeliste in einer Akkumulatorliste aufsammelt. Da ein Akkumulator die Elemente aber immer in umgekehrter Reihenfolge aufsammelt, sind die Elemente der Liste anschließend umgedreht.

Doch nun zu einem endgültigen Ausweg aus dem Dilemma. Das Problem bei der Benutzung einer Liste als Akkumulator rührt daher, daß man ein neues Element sehr einfach vorne an eine Liste hängen kann. Zum Beispiel ist [Elem|List] die Liste List vorne um das Element Eiern erweitert Viel aufwendiger ist es, ein Element hinten an eine Liste zu hängen, da man dazu wieder das recht aufwendige Prädikat append|3 verwenden muß. Möchte man zum Beispiel Elem hinten an List anhängen, kann man das mit append(List, [Elem], NewList). Da wir aber weiter oben gesehen haben, daß das Prädikat append|3 linear proportional zur Länge des ersten Arguments (hier also List) Rekursionen benötigt, ist es wohl recht ungeeignet, um einen effizienten Algorithmus zu erhalten.

Ein Loch in der Liste

Die Lösung des Problems bringen die sogenannten Differenzlisten. Der Name rührt von einer recht theoretischen Betrachtung des Problems her und soll uns hier nicht weiter interessieren. Die Differenzlisten werden manchmal auch als Listen mit Loch (engl.: hole) oder als offene Listen bezeichnet Sie ermöglichen es uns, ein Prädikat zur Linearisierung von Bäumen zu schreiben, das einen Aufwand besitzt der linear proportional zur Anzahl der Knoten im Baum ist, und dessen Ergebnisliste die Elemente in der richtigen Reihenfolge enthält. Der Preis, den wir dafür zahlen müssen, ist ein etwas schwerer verständlicher Algorithmus. Deshalb wollen wir uns zunächst einmal das Prinzip der Differenzlisten ansehen, bevor wir das Prädikat flattenTreeDiff|2 näher betrachten.

Bisher haben wir die Variablen in Prolog nur benutzt, um Argumente mit einem Namen versehen und sie so an andere Prädikate weitergeben zu können. Doch Prologvariablen stellen für sich schon Objekte dar, d.h. Variablen können, auch ohne für einen bestimmten Term zu stehen, von Bedeutung sein. Sehen wir uns einmal die folgende Anfrage an:

Als Antwort liefert uns das Prolog-System etwas wie A = [_237], Y = 257. Da ein Underscore (,,) als Großbuchstabe gewertet wird, ist _237 einfach ein anderer Name für die Variable, die wir bei der Eingabe mit Y bezeichnet haben. Genauso, wie wir in eine Liste Zahlen schreiben können, geht dies auch mit Variablen, die noch ungebunden sind, d.h. denen noch kein Term zugeordnet wurde. Als nächstes unifizieren wir eine solche Liste, die eine ungebundene Variable enthält, mit einer anderen Liste.

?- X = [Y], X = [1].

Die Antwort ist, wie zu erwarten war, X = [1],Y= /, d.h. bei der Unifikation von [YJ und [1 ] ist die / an F gebunden worden. Diese Bindung kann man aber auch direkt angegeben.

?- X = [Y], Y = 1.

Wieder ist die Antwort A = [1], Y = 1. Wir haben hier also zuerst eine Liste, die als einziges Element eine Variable, nämlich F, enthält, an X gebunden. Anschließend wurde an die Variable F die Zahl 1 gebunden. Damit wurde auch in der Liste F durch 1 ersetzt Genauso wie für die Elemente einer Liste, läßt sich dieser Mechanismus für den Listenrest einsetzen.

?- X = [1|Y], Y = [2].

Hier ist die Antwort A = [1,2],Y= [2], Es wurde also zuerst eine Liste, die als einziges Element die 1 besitzt und den Listenrest F hat, an A gebunden. Anschließend wurde der Listenrest durch die Liste [2] ersetzt. Dadurch ergibt sich natürlich die Gesamtliste [1,2]. Hiermit haben wir aber unser Ziel, an eine Liste hinten etwas anhängen zu können, ohne append|3 zu benutzen, erreicht Schließlich haben wir eine Liste, die vorher nur die 1 als Element enthalten hat, um ein weiteres Element, hier die 2, erweitert. Um mehr als einmal etwas hinten in eine Liste anhängen zu können, müssen die eingehängten Listen wieder eine Variable als Listenrest besitzen. Etwa wie im folgenden Beispiel.

?- X = [1|Y], Y = [2||Z], Z = [3|V].

Als Antwort erhalten wir hier X = [1,2,3|_237], Y = [2,3|_237], Z = [3|_237], V = _237 (wobei die Variable _237 einen beliebigen Namen haben kann). Die anfängliche Liste [1|Y], die an X gebunden ist, wurde also um zwei Elemente erweitert und dadurch, daß der Listenrest immer noch eine Variable (hier: 257) ist, kann sie auch noch weiter erweitert werden. Solche Listen, deren Listenrest eine Variable ist, werden als Differenzlisten, Listen mit Loch oder offene Listen bezeichnet dabei ist die Variable das Loch, das noch mit einem beliebigen Term ausgefüllt werden kann. Bei der Benutzung solcher Listen ist es wichtig, daß neben der Liste auch noch die Variable, die das Loch bildet, an Prädikate übergeben werden muß, die die Liste erweitern wollen. Denn schließlich muß das aufgerufene Prädikat wissen, welche Variable das Loch in der Liste bildet, in das weitere Elemente eingehängt werden können.

Nach dieser Vorbereitung schauen wir uns jetzt das Prädikat flattenTreeDiff|2 aus Listing 3 an. Es besteht wie flattenTreeAccu|2 aus dem Aufruf eines Hilfsprädikats, das drei Argumente besitzt Dieses Hilfsprädikat flattenTreeDiff|3 erhält im ersten Argument den Baum, der linearisiert werden soll. Im zweiten und dritten Argument bekommt es die Differenzliste übergeben, die zum Aufsammeln der Werte des Baums benutzt werden soll. Dabei wird im zweiten Argument die Liste und im dritten das Loch übergeben. Etwas verwirrend ist am Anfang der erste Aufruf flattenTreeDiff(Tree, List, []), da hier die leere Liste [] als Loch übergeben wird. Die Arbeitsweise dieses Aufrufs wird deutlicher, wenn man ihn als Konjunktion schreibt, die genau die gleiche Funktion erfüllt:

flattenTreeDiff(Tree, List, Hole), Hole = []. Er besagt dann einfach, daß das Loch, das sich zum Schluß in der Liste befindet, die bereits alle Elemente aufgesammelt hat, mit der leeren Liste abgeschlossen werden soll.

Das Prädikat flattenTreeDiff|3 unterscheidet in zwei Klauseln wieder zwischen den Knoten und den Blättern des Baums. Im Fall eines Blatts wird die bisher aufgebaute Differenzliste durch ein Element erweitert Dies geschieht durch das Anhängen einer Liste mit der Struktur [Wert|Hole], wobei Wert für den Wert des Blatts steht, das gerade abgearbeitet wird. Die Variable Hole wird zudem mit dem dritten Argument von flattenTreeDiff|3 unifiziert da sie das neue Loch der Differenzliste darstellt.

Die zweite Klausel behandelt wieder zuerst den linken und dann den rechten Teilbaum. Dabei wird das Loch der Liste des linken Teilbaums TempHole als zweites Argument an den rekursiven Aufruf für den rechten Teilbaum übergeben. Dies heißt daß die linearisierte Form des rechten Teilbaums in das Loch der linearisierten Form des linken Teilbaums eingehängt wird. Dadurch hängen dann die Werte des rechten Teilbaums hinter den Werten des linken Teilbaums, und die Reihenfolge der Elemente bleibt erhalten. Ein Beispielaufruf von flattenTreeDiff|2 ist etwa:

?- tree(Tree), flattenTreeDiff(Tree, List).

Die Antwort ist hierbei List = [5,2,8,7,1]. In Abbildung 4 wird die Funktionsweise von flattenTreeDiff|2 nochmal grafisch dargestellt Die Ursprungsliste List ist nur eine Variable, die dann in jedem Blatt des Baums um einen Term der Form [Wert|Hole] erweitert wird. Das letzte Loch (Hole_5) wird mit der leeren Liste gleichgesetzt und die Ergebnisliste dadurch abgeschlossen.

So long...

Obwohl wir uns in dieser Folge um ein paar sehr spezielle Probleme gekümmert haben (z.B.: das Linearisieren von Bäumen), sind die dabei vorgestellten Techniken sehr allgemein verwendbar. Gerade die Verwendung von Akkumulatoren und Differenzlisten sind zwei Techniken, die in ernsthaften Prolog-Anwendungen zu starken Effizienzsteigerungen führen können. Außerdem können sie ähnlich wie für Listen auch für andere Datenstrukturen verwendet werden. Zum Beispiel werden Terme, die ungebundene Variablen enthalten, allgemein als offene Terme oder offene Strukturen bezeichnet. Ein offener Baum ist zum Beispiel node(leaf(1),Hole). Durch Binden der Variable Hole kann dieser Baum noch erweitert werden. Deshalb ist es wichtig, trotz der teilweise recht speziellen Beispiele, das verwendete Prinzip zu erkennen und zu versuchen, es auf andere Probleme zu übertragen.

In der nächsten Folge wollen wir uns ein wenig um die sogenannten Metaprädikate kümmern. Das sind Prädikate, die es zum Beispiel erlauben, ein Prolog-Programm zur Laufzeit zu verändern (ist nicht so schlimm, wie es sich anhört) oder zu erzeugen.

Literatur:

[1] Clocksin/Mellish: „Programming in Prolog", Springer

[2] Chakravarty: „Compiler-Bau", Teil 3, ST-Computer 3/91

cds([[the_psychedelic_furs, world_outside], 
    [the_popguns, eugine],
    [the_cure, seventeen_seconds], 
    [the_psychedelic_furs, talk_talk_talk]])

collectTitles([], _, []) ;- !.
collectTitles([[Ip, Title] | CDs], Ip,
              [Title|Titles]) 
        collectTitles(CDs, Ip, Titles) 
collectTitles([[WrongIp, WrongTitle] | CDs], Ip, Titles) :-
        collectTitles(CDs, Ip, Titles)

Listing 1: Prädikat zum Auffinden von CD-Titeln in einer Liste

tree(node(node(leaf(5), leaf(2)), node(node(leaf(8), leaf(7)), leaf(1)))).

sumTree(leaf(X), X) :- !.

sumTree(node(LeftTree, RightTree), Sum) :-
        sumTree(LeftTree, LeftSum), 
        sumTree(RightTree, RightSum),
        Sum is LeftSum + RightSum.

Listing 2: Prädikat zum Addieren der Blätter eines Binärbaums aus Zahlen

% Naive Umwandlung eines Baums in eine Liste
%
flattenTree(leaf(X), [X]).
flattenTree(node(Lhs, Rhs), List) :-
        flattenTree(Lhs, LhsList), 
        flattenTree(Rhs, RhsList), 
        append(LhsList, RhsList, List).

% Umwandlung eines Baums in eine Liste mit Akkumulator
%
flattenTreeAccu(Tree. List) :- flattenTreeAccu(Tree, [], List)

flattenTreeAccu(leaf(X), ListIn, [X|ListIn])
flattenTreeAccu(node(LeftTree, RightTree), ListIn, ListOut) :-
        flattenTreeAccu(LeftTree, Listln, ListTemp), 
        flattenTreeAccu(RightTree, ListTemp, ListOut).

% Umwandlung eines Baums in eine Liste mit Differenzlisten
%

flattenTreeDiff(Tree, List)
        flattenTreeDiff(Tree, List, []).

flattenTreeDiff(leaf(X), [X]Hole], Hole).
flattenTreeDiff(node(LeftTree, RightTree), List, Hole) :-
        flattenTreeDiff(LeftTree, List, TempHole), 
        flattenTreeDiff(RightTree, TempHole, Hole).

Listing 3: Prädikate zum Linearisieren eines Baums

% Kehrt die Reihenfolge der Elemente in einer Liste um
%

reverse([], [])
reverse([X|Xs], Zs) :-
        reverse(Xs, Xs), 
        append(Ys, [X] , Zs)

% Kehrt die Reihenfolge der Elemente in einer Liste um.
% Besitzt durch die Verwendung eines Akkumulators nur
% einen Aufwand linear proportional zur Länge der Liste
%
reverseAccu(List, ReverseList) :-
        reverseAccu(List, [], ReverseList).

reverseAccu([], List, List)
reverseAccu([X|Xs], Ys, Zs)
        reverseAccu(Xs, [X|Ys], Zs).

Listing 4: Prädikate zum Umkehren der Elementreihenfolge einer Liste

Manuel Chakravarty

---

---