Ich bringe mir Prolog (PROgramming in LOGic) wieder bei, indem ich ein Text-Adventure-Beispiel-Tutorial durchgehe. Ich lasse dich teilhaben, vielleicht findest du das ja auch interessant.
In Prolog erklärt man dem Computer nicht (wie sonst üblich), wie er ein Problem lösen soll, sondern definiert Fakten und Regeln und vertraut darauf, dass der eingebaute universelle "Problemlöser" die gewünschte(n) Antwort(en) ableiten kann. SQL funktioniert ähnlich.
Prolog arbeitet mit Relationen. Eine Relation hat einen Namen und Argumente (die wieder Relationen sein können). Eine Zahl oder ein Name (oder ein String in '...') heißt Atom. Atome stehen für sich selbst. Sie haben keine Bedeutung für Prolog. Ein Atom kann man als 0-stellige Relation (also nur der Name ohne Argumente) auffassen.
Aussagen werden mit einem Punkt beendet.
room(kitchen).
room(office).
door(kitchen, office).
Diese Relationen bedeuten für uns, dass Küche und Büro zwei Räume sind und das es eine Tür vom Büro zur Küche gibt. kitchen und office sind Atome, room und door sind die Namen von Relationen. Alle Namen müssen klein geschrieben werden. Nur Variablen fangen mit einem Großbuchstaben (oder _) an.
Ich kann Prolog fragen (das ?- ist der Prompt, der Rest die Ausgabe), welche Räume es gibt:
?- room(X).
X = kitchen
X = office
Dazu benutze ich eine Variable und gebe ein Muster an, wo Prolog dann alle möglichen Werte für die Variable X in dem Muster aufzählt. Dazu werden alle Fakten konsultiert (d.h. durchprobiert).
Alternativ kann ich z.B. fragen, ob attic auch ein Raum ist:
?- room(attic).
no
Enthält ein Muster keine Variablen, antwortet Prolog nur mit yes oder no.
Wir wollen ein paar weitere Räume definieren:
room(hall).
room(dining_room).
room(cellar).
Nun wollen wir die Räume über Türen verbinden:
door(office, hall).
door(kitchen, office).
door(hall, dining_room).
door(dining_room, kitchen).
door(cellar, kitchen).
Und ein paar Gegenstände verteilen:
located_in(desk, office).
located_in(apple, kitchen).
located_in(flashlight, desk).
located_in(washing_machine, cellar).
located_in(nani, washing_machine).
located_in(broccoli, kitchen).
located_in(crackers, hall).
located_in(computer, office).
Einige Dinge sind essbar:
edible(apple).
edible(broccoli).
edible(crackers).
Die Taschenlampe kann man später anschalten:
turned_off(flashlight).
Und wir befinden uns in der Küche:
here(kitchen).
Wir können jetzt nach dem Apfel suchen:
?- located_in(apple, X).
X = kitchen
Wir können fragen, was alles in der Küche liegt:
?- located_in(X, kitchen)
X = apple
X = broccoli
Wir können auch fragen, ob der Apfel im selben Raum wie wir sind:
?- located_in(apple, X), here(X).
yes
Verschiedene (und-verknüpfte) Bedingungen werden mit , aufgereiht. Prolog sucht nach einer Lösung, wo ein X beide Bedingungen gleichzeitig erfüllt. Alternativ kann ich fragen, welche Gegenstände sich in dem Raum, in dem ich mich befinde, befinden:
?- located_in(X, Y), here(Y)
X = apple
X = broccoli
Hier bindet here(Y) die Variable Y an kitchen, da dies der einzige mögliche Wert für dieses Muster ist und beschränkt so das located_in-Muster. Dies ist die einzige Form in Prolog, wie man Variablen Werte zuweisen kann (etwas wie X = 1 funktioniert nicht).
Neben Fakten kann ich Regeln definieren. Türen sollen in beide Richtungen funktionieren:
connect(X, Y) :- door(X, Y); door(Y, X).
Vor dem :- steht, was definiert werden soll und danach, wann es gilt. Das ; steht für "oder", es reicht also, wenn eine der beiden Aussagen erfüllt werden kann. Die Regel sagt also, dass das es eine Verbindung von X nach Y gibt, wenn es eine Tür von X nach Y oder von Y nach X gibt.
Wie kann ich die Taschenlampe finden? Sie ist nicht direkt in einem Raum, sondern in einem Gegenstand, der in einem Raum ist. Ich glaube, es geht so (das ; ist ein ODER - das , steht für UND und bindet stärker):
is_located_in(X, Y) :-
located_in(X, Y), room(Y);
located_in(X, Z), is_located_in(Z, Y).
?- is_located_in(flashlight, X).
X = office
Bislang waren alle Befehle interaktiv. Schreiben wir unsere erste Funktion mit I/O. writeln/1 kann ein Atom ausgeben (dem ein Zeilenumbruch folgt, write wäre ohne Zeilenumbruch). tab/0 rückt den folgenden Text ein. Das /n gibt die Stelligkeit der Relation an. tab/1 wäre eine andere Relation.
list_items(R) :-
located_in(I, R),
tab, writeln(I),
fail.
Das fail sorgt dafür, dass wenn Prolog ein I gefunden hat, das located_in(I, R) erfüllt und auch writeln(I) erfüllt (was immer klappt, da hier nur der Seiteneffekt, dass etwas ausgegeben wird, wichtig ist), schlägt die letzte Bedingung fehlt, was dazu führt, das I verworfen wird und nach dem nächsten passenden Namen gesucht wird. Sprich, das ist eine Schleife, die über alle möglichen Werte iteriert und sie ausgibt.
Ich kann eben so alle Verbindungen von einem Raum ausgeben:
list_connections(R1) :-
connect(R1, R2),
tab, writeln(R2),
fail.
Spielen wir das einmal durch. Wenn ich list_connections(hall) aufrufe, setzt Prolog R1=hall und versucht dann connect(hall, R2) zu erfüllen. Es gibt die Regel connect(X, Y), d.h. X=hall und Y=R2, d.h. es muss nach door(hall, Y) bzw. door(Y, hall) gesucht werden. Das passt einmal für Y=office und einmal für Y=dining_room. Damit ist auch R2 definiert. Diese Namen werden ausgegeben, doch durch das fail wird list_connections keine Antwort liefern.
Hier ist unser erster Befehl für ein Text-Adventure:
look :-
here(R),
write('You are in the '), writeln(R),
writeln('You can see:'), list_items(R),
writeln('You can go to:'), list_connections(R).
?- look.
You are in the kitchen
You can see:
apple
broccoli
You can go to:
office
cellar
dining room
Man darf nicht vergessen, das Prolog keine Funktionen kennt, die etwas zurückgeben können. Das here(R) bindet R an einen Wert - nämlich den aktuellen Raum - und ist das Äquivalent zu einem Funktionsaufruf. Der Rest der Regel sind nur Seiteneffekte.
Bislang war unsere Datenbasis statisch. Wenn ich jedoch zu einem anderen Raum gehen will, muss ich here(kitchen) löschen und ein neues Fakt hinzufügen können. Das geht so:
can_go(R) :-
here(R1), connect(R1, R);
writeln("You can't go there."), fail.
move(R) :-
retract(here(_)),
assertz(here(R)).
go(R) :- can_go(R), move(R), look.
Kannst du nachvollziehen, wie das funktioniert? can_go/1 prüft, ob man von der aktuellen Position den angegebenen Raum erreichen kann. Falls nein, wird eine Fehlermeldung ausgegeben und fail/0 lässt dann auch go/1 fehlschlagen. Mit retract/1 kann ich Relationen aus der Datenbasis entfernen. Das _ ist die unbestimmte Variable. Der konkrete Wert ist mir egal, ich entferne alle here/1-Relationen, denn das ist ja nur eine. Mit assertz/1 füge ich dann eine neue Relation hinzu. move/1 schlägt nie fehl, daher folgt danach dann ein look/0.
Jetzt will ich etwas nehmen können:
can_take(I) :-
here(R), located_in(I, R);
write('There is no '), write(I), writeln(' here.'), fail.
take(I) :-
can_take(I),
retract(located_in(I, _)), assertz(have(I)),
writeln('Taken.').
Könntest du jetzt drop/1 schreiben?
can_drop(I) :-
have(I);
write('You don't have '), write(I), writeln('.'), fail.
drop(I) :-
can_drop(I),
here(R),
retract(have(I)), assertz(located_in(I, R)),
writeln('Dropped.').
Die Taschenlampe mittels turn_on/1 einzuschalten funktioniert analog:
turn_on(I) :-
can_turn_on(I),
retract(turned_off(I)), assertz(turned_on(I)),
write('You turned the '), write(I), writeln('on.')
can_turn_on(I) :- turned_off(I); writeln('You can't turn this on'), fail.
Nun will ich erreichen, dass ich nur dann den Keller betreten kann, wenn ich eine eingeschaltete Taschenlampe dabei habe. Dazu definiere ich ein puzzle:
puzzle(go(cellar)) :-
have(flashlight), turned_on(flashlight), !;
writeln('It's darf and you are afraid of the dark.'), !, fail.
puzzle(_).
Der ! (eine 0-stellige Relation mit einem Namen, der aus Sonderzeichen besteht) hat eine besondere Bedeutung: Er bricht die Suche nach weiteren Lösungen ab. Ich habe ehrlich gesagt nicht genau verstanden, warum das notwendig ist. Es ist eine Performance-Optimierung aber in diesem Fall wohl nicht zwingend notwendig. Die letzte Regel sorgt dafür, dass wir noch weitere Rätsel einbauen können. Der Standard ist, dass es einfach funktioniert.
So kann das Puzzle eingebaut werden:
go(R) :- puzzle(go(R)), ...
Noch besser ist es aber, an der Stelle, wo wir aus der Eingabe einen Befehl erzeugen und ausführen wollen, zunächst diesen mit puzzle/1 zu prüfen. Die Relation call/1 dient dazu, das Argument wie eine Anfrage auszuführen.
game :- read(Str), command(Str, Cmd), puzzle(Cmd), call(Cmd).
Die Relation command/2 kann eine durch read/1 gelesene Eingabe (in Form einer Liste aus Atomen) verarbeiten und z.B.aus go kitchen oder turn flashlight on ein go(kitchen) oder turn_on(flashlight) machen. Wie das geht, sehen wir nach einem kleinen Exkurs.
Prolog eignet sich auch zum Erkennen (nicht unbedingt verstehen) von Sätzen in mehr oder weniger natürlich-sprachlicher Form. Dazu müssen wir die folgende Relation verstehen:
noun([dog|X]-X).
Die [|]-Notation ist eine Liste in typischer Paar-Darstellung. Eine Liste ist rekursiv definiert als ein Paar bestehend aus einem Element und einer Liste. Diese Liste kann auch die leere Liste, traditionell als nil bezeichnet, sein. Die eckigen Klammern sind einfach Syntax und es könnte auch so aussehen:
noun(pair(dog, X)-X).
Das - ist ebenfalls Syntax. Die üblichen mathematischen Operationen können auch bei Prolog in Infix-Notation dargestellt werden. Zu beachten ist nur, dass X = 3-1 nicht etwa X auf 2 setzt, sondern vergleicht, ob X wohl die Relation -(3, 1) ist. Es braucht einen speziellen Operator (is), der eine Relation als mathematische Formel auffasst und auswerten kann. Doch das ist ein anderes Thema. Das - ist jedenfalls einfach nur eine Abkürzung für:
noun(-(pair(dog, X), X)).
Nachdem wir das mit der Syntax geklärt haben, was soll das bedeuten? Wird noun mit einer Liste aufgerufen, deren erstes Element dog ist, wird X an den Rest der Liste gebunden. Denke daran, dass [dog, ate, bone] eine Kurzform für [dog | [ate | [bone | nil]]] ist, was eine Kurzform für pair(dog, pair(ate, pair(bone, nil))) ist:
?- noun([dog, ate, bone]-X)
X = [ate, bone]
?- noun([cat, ate, mouse]-X)
no
Wenn das erste Wort der angegebenen Liste dog (also ein Nomen) ist, wird X an den Rest der Liste gebunden. Ist das erste Wort unbekannt, wird no zurückgegeben. Damit kann ich alle entsprechen definierten Wärter erkennen. Damit haben wir einen - zugegeben primitiven - Parser.
Nun kann ich Nomen und Verben definieren:
noun([dog|X]-X).
noun([cat|X]-X).
noun([mouse|X]-X).
verb([ate|X]-X).
verb([chases|X]-X).
Außerdem ein paar Adjektive und Artikel:
adjective([big|X]-X).
adjective([brown|X]-X).
adjective([lazy|X]-X).
determiner([the|X]-X).
determiner([a|X]-X).
Nun kann ich sagen, dass Satz aus einer Nominalphrase und einer Verbphrase besteht und diese aus einem Artikel und Nomen bzw. Adjektiv und Verb und Objekt besteht:
sentence(S) :- nounphrase(S-S1), verbphrase(S1-nil).
nounphrase(NP-X) :-
determiner(NP-S1), nounexpression(S1-X);
nounexpression(NP-X).
nounexpression(NE-X) :-
noun(NE-X);
adjective(NE-S1), nounexpression(S1-X).
verbphrase(VP-X) :- verb(VP-S1), nounphrase(S1-X).
?- sentence([the, dog, chases, a, brown, cat]).
yes
Da [Y|X]-X (eine sogenannte "Difference List") häufig vorkommt, gibt es eine einfachere Syntax:
sentence --> nounphrase, verbphrase.
nounphrase --> determiner, nounexpression; nounexpression.
nounexpression --> noun; adjective, nounexpression.
verbphrase --> verb, nounphrase.
noun --> [dog].
noun --> [cat].
noun --> [mouse].
verb --> [ate].
verb --> [chases].
adjective --> [big].
adjective --> [brown].
adjective --> [lazy].
determiner --> [a].
determiner --> [the].
Die selbe Technik kann man nun benutzen, um die Befehle für das Text-Adventure zu definieren:
command([V, O]) --> verb(OT, V), object(OT, O).
verb(room, go) --> [go, to].
verb(item, take) --> [take].
object(T, N) --> det, noun(T, N); noun(T, N).
det --> [the].
det --> [a].
noun(room, X) --> [X], {room(X)}
noun(room, dining_room) --> [dining, room].
noun(item, X) --> [X], {located_in(X, _)}
Der Teil in {...} wird nicht von dem -->-Makro umgewandelt, sondern bleibt als Prolog-Code bestehen. Ein Befehl besteht aus einem Verb V und einem Objekt O, diese beiden will ich ermitteln. Das OT (für "object type") sorgt dafür, dass Verben, die für Räume gedacht sind, auch nur mit Raum-Dingen zusammenpassen und Verben, die für Gegenstände sind, nur mit Gegenständen. Ein Verb für Räume ist go, eines für Gegenstände ist take. Wenn ich "go to the kitchen" eingebe, finde ich das go-Verb. Ein Objekt hat optional einen Artikel und ansonsten sind all die Dinge Räume, für die es eine room(X)-Relation gibt. Ausnahme ist das Esszimmer, weil das mit zwei Worten geschrieben werden muss. Einen Gegenstand erkenne ich dadurch, dass er irgendwo liegt.
Mir fehlt das Stück, das aus dem oben gezeigten command/1, das ein Array mit Verb und Objekt erzeugt, ein command/2 macht, wie ich es bräuchte, um aus einer eingelesenen Liste den Befehl in der Form verb(objekt) macht. Geh einfach davon aus, dass es das gibt. Dann haben wir vom Prinzip her ein komplettes Textadventure in Prolog entworfen.
Stefan