Prolog oder die unendlichen Weiten der Logik
Seite 2: Alles ist logisch, nicht prozedural
Die oben verwendete Punktedistanz soll nun berechnet werden. Berechnung ist doch etwas Prozedurales, oder nicht? Denn die Punkte aller Karten eines Spielers sind zu summieren und danach der Abstand zu 21 zu bestimmen. Also:
% Teste ob 21 überschritten ist
% Distance ist im folgenden ein Abstand eines Punktwertes zu 21
% cardsTest(+Kartenliste, -Abstand zu 21 (ggf negativ))
cardsTest(Cards, Distance) :-
sumCards(Cards, Sum),
Distance is 21 - Sum.
cardsTest ist wahr, wenn sumCards(...) und die letzte Zeile wahr sind. Distance is 21 - sum ist aber keine prozedurale Anweisung! Eben sowenig ist cardsTest(...) eine Funktion. Und wo ist überhaupt der Rückgabewert?
Betrachten wir den Aufruf der Regel cardsTest näher. Angenommen, Cards sei mit einer Liste von card(...) Strukturen instanziert. Distance wäre unbelegt. Zunächst wird die Regel sumCards(..) im Regelrumpf auf wahr geprüft. Wenn ja, wird die Variable Sum mit eben dieser Punktesumme instanziert, zum Beispiel "10". Die folgende Klausel kann nur wahr werden, wenn Distance zu 11 instanziert wird. Alle Klauseln des Regelrumpfes sind wahr, und so ist der Kopf cardsTest() es auch. Was also prozedural aussieht, ist logische Struktur pur!
Da war noch die Frage nach einem Rückgabewert. Jede freie Variable eines Regelkopfes versucht Prolog zu instanzieren, damit die Regel wahr wird beziehungsweise einem bekannten Fakt entspricht. In unserem Beispiel würde Distance instanziert werden und so eine Art Rückgabewert bilden. Es ist gute Praxis, die Intention der Variablen in den Kommentaren anzuzeigen, wie im nachfolgenden Beispiel.
Etwas ungenau könnte man sagen: In Prolog beschreibt man logische Strukturen. Dort, wo Informationen fehlen (egal wo), versucht Prolog, eine Instanzierung zu finden. Was auf den ersten Blick verwirren mag, ist Prologs Potenzial für Prototyping. Es erlaubt, ein Problem Top-Down zu beschreiben. Beispiel: Eine weitere Gewinnregel soll festlegen, Spieler 1 habe gewonnen, wenn Spieler 2 über 21 kommt. In Prolog:
% Kommentar zu den Argumenten wie SWI Prolog
% + bedeutet "input", soll instanziert sein
% - bedeutet "output", wird instanziert durch die vorliegende Regel
% +Distance1, +Distance2, -Spielernummer
winner(Distance1, Distance2, 1) :-
cardsOk(Distance1, ok),
cardsOk(Distance2, loser).
Die Prüfung der Überschreitung steckt in der Klausel cardsOK(...). Diese kann später durch Einführung einer entsprechenden Regel detailliert werden. Prolog braucht Details erst, wenn der Wahrheitswert von cardsOK() bestimmt werden soll.
Datenstrukturen! und Algorithmen?
Rekursion, Listen und Bäume sind aus der prozeduralen Welt gut bekannt. In Prolog sind sie ein wichtiges und effizientes Gestaltungsmittel. Für die Berechnung der Punktesumme aller Karten könnte man schreiben:
% sumCards(+Liste von Karten als Kartenstrukturen, +Punkte vorher, -Punkte summiert)
sumCards([C|Cards], Sum, Sum3) :-
sumPoints(C, Sum, Sum2),
sumCards(Cards, Sum2, Sum3).
Der Term [C|Cards] gibt ein Muster vor. Es steht für eine Liste [..], die ein erstes Element C enthält, und die restliche Liste Cards. Die Punkte der Karte C werden auf die Summe Sum aufsummiert. Nun folgt die Rekursion: Für die restliche Liste Cards wird wieder dieselbe Regel sumCards(...) angewendet. Prolog verfügt über Mechanismen, soll eine rekursive Struktur intern als leichtgewichtige lineare Aufrufsequenz umzusetzen.
Damit das Ganze stoppt, muss noch eine Bedingung formuliert werden, wenn es keine Restliste mehr gibt:
sumCards([], Sum, Sum).
Wird also die Regel sumCards(..,..,..) mit leerer Liste aufgerufen, so ändert sich an der Summe nichts.
Um Listen und Bäume tummeln sich viele Algorithmen. In Prolog lassen sich die Algorithmen als logische Struktur beschreiben. Nehmen wir das Prädikat append(...), das zwei Listen aneinander fügt. Die Implementation dieses Prädikats verdeutlicht das wunderbar:
append([], List, List).
append([Element|Restliste], AlteListe, [Element | Neueliste]) :-
append(Restliste, AlteListe, NeueListe).
Die wichtigste Datenstruktur ist natürlich die Faktenbasis selbst. Ein Prolog-Programm kann sie direkt manipulieren. Das Prädikat asserta(Term) fügt einen Term an den Anfang der Wissensbasis ein. retract(Term) entfernt den Term wieder.
drawCard(Farbe, Name, Card) :-
Card = card(Farbe, Name, _),
retract(Card).
Dieser Code bildet das Ziehen einer Karte aus dem Deck nach, indem es diese aus der Wissensbasis löscht. Hier noch ein wichtiger Hinweis: das _ steht für eine unbenannte Variable. Auf sie kann nicht zugegriffen werden. Sie zeigt hier nur an, dass der Funktor card drei Argumente hat. Es ist die logische Variante von "don't care".
Nicht zu vergessen ist auch: Jedes Prädikat hat eine Datenstruktur. Weil Argumente von Funktoren geschachtelt werden können, sind beliebige hierarchische Strukturen denkbar. Das Fakt
newPlayer(Num, player(Num, [])).
beschreibt eine Player-Struktur, die selbst wieder eine Liste in sich trägt. Mit ?- newPlayer(1, Player). wird Player zu player(1, []) instanziert. Übrigens ist das ein Prolog-typisches Generator Pattern.
Die prozedurale Falle
Prozedurales Denken kann in Prolog hinderlich sein. Folgende Regel schreibt vor, eine Karte aus der Wissensbasis zu ermitteln und der Kartenliste Field anzuhängen.
% addCard(+Spielfeld als Kartenliste, +Kartenfarbe, +Name, -Spielfeld mit neuer Karte
addCard(Field, Farbe, Name, Field2) :-
A = card(Farbe, Name, _),
append(Field, [A], Field2).
Prolog sagt dazu:
Überraschung! Field2 sollte die neue Karte enthalten. Statt dessen lautet der Eintrag card(herz, bube, _3498). Der Punktwert fehlt. Das Missverständnis liegt in dem Ausdruck A = card(...). Dies ist keine Zuweisung wie bei prozeduralen Sprachen. A = card(...) ist wahr (und nur darum geht es!), wenn A mit card(herz, bube, _) instanziert werden kann. Und es kann, denn ein card(herz, bube, "und irgend etwas") ist Teil der Wissensbasis. "_" bedeutet nur, da muss etwas sein. Aber der Inhalt spielt keine Rolle und muss somit auch nicht instanziert werden. Aus diesem Grund wird auch nur card(herz, bube, _) der Liste hinzugefügt.
Ein Fehler ist das aber nicht. Eine Liste [Kopf|_] darf unvollständig sein und kann weiterverarbeitet werden. Unvollständige Datenstrukturen sind jedoch ein elegantes Mittel von Prolog, weil sie ein Problem in seiner Struktur allgemein beschreiben lassen.
