quixotic project blog

Dieser Artikel soll eine kurze Einführung in die logische Programmierung mit Prolog geben.

Basics:

Prolog(Programming in Logic) gehört zu den sogenannten logischen Programmiersprachen. Diese unterscheiden sich erheblich von den sonst gebräuchlichen imperativen/prozeduralen Programmiersprachen in einigen Punkten.

Ein Programm in einer logischen Sprache ist eine Sammlung von logischen Formeln, deren Auswertungsstrategie nicht Bestandteil des Programmes ist. Das System prüft ob Aussagen wahr oder falsch sind bzw. gibt Variablenbelegungen an, die die Aussagen wahr machen. Die Programmierung befindet sich deshalb auf einer hohen Abstraktionsebene.

Speziell in Prolog sind Schleifenkonstrukte, wie sie aus imperativen Programmiersprachen bekannt sind, nur sehr eingeschränkt möglich. Auch

Variablenzuweisungen sind nur eingeschränkt möglich. Es gibt sogenannte freie und gebundene Variablen. Einer einmal gebundenen Variable kann kein anderer Wert mehr zugewiesen werden.

Wir beziehen uns im Folgenden nun auf SWI-Prolog, dass für Forschungs- und Schulungszwecke frei verfügbar ist.

Die Grundlage jeder logischen Programmiersprache ist die Aussagenlogik, die sich mit Elementaraussagen beschäftigt die entweder wahr oder falsch sein können. Die Aussagenlogik kennt logische Operationen wie zum Beispiel “und”, “oder” und “nicht” und in ihrem Zeichenvorrat sind ebendiese, Atome(welche im Folgenden immer mit Kleinbuchstaben beginnen) und Klammern.

Syntax und Operatoren:

Ein Prolog-Programm ist eine Folge von Regeln, die ihrerseits aus Termen bestehen. Ein Term kann eine Konstante, eine Variable oder eine Struktur sein.

Konstanten:

zusammenhängende Folge alphanumerischer Zeichen, beginnend mit einem Kleinbuchstaben:

hallo, sONNE, h1mm3l

oder beliebige Zeichenfolge in einfachen Anführungszeichen:

'Hallo', 'S@lz'

Variablen:
alphanumerische Zeichenfolge beginnend mit einem Grossbuchstaben oder Underscore:

X, Y, _hummel, Hoelle

Kommentare:

Kommentare über mehrere Zeilen werden wie in Java mit /*…*/ gebildet. % Kommentiert den Rest der Zeile.

Strukturen:

Strukturen sind zusammengesetzte Terme, die sich aufteilen lassen in Funktor und Komponenten. Die Anzahl der Komponenten gibt die Stelligkeit des Funktors an.

familienmitglied(peter, mueller).

familienmitglied ist der Funktor mit der Stelligkeit zwei, da er zwei Komponenten hat. Strukturen lassen sich auch schachteln:

pc(tastatur, ausgabe(monitor, drucker), maus).

Es ist möglich dass der selbe Funktor mehrmals mit unterschiedlichen Stelligkeiten existiert, ähnlich dem überladen in C++.

Operatoren in Prolog sind andere Schreibweisen für Funktoren. Zum Beispiel ist der Ausdruck “1+8″ keinesfalls identisch mit “9″, sondern eine kurze Schreibweise für den 2-stelligen Funktor +(1, 8).

Wenn man Prolog zum Rechnen animieren will, muss man das explizit tun, doch dazu später mehr. Weiterhin kann man Operatoren durch ihren Namen und ihre Position charakterisieren. Jeder Operator in Prolog besitzt eine Priorität die entscheidet welcher Operator in einer Folge von Anweisungen zuerst ausgewertet wird. Einige vordefinierte Operatoren und Prädikate:

term1 = term2 Unifikation von term1 und term2, gleich mehr dazu!

term1 \= term2 term1 und term2 stimmen nicht überein, Ungleichheit

term1 == term2 term1 und term2 referenzieren das gleiche Objekt

exp1 =:= exp2 der Wert von exp1 und exp2 ist gleich

exp1 =\= exp2 der Wert von exp1 und exp2 ist nicht gleich

+ – * / Addition, Subtraktion, Multiplikation, Division

X mod Y Modulo-Funktion

Unifikation:

Wann immer man das eingebaute Prädikat “=” benutzt, versucht Prolog die zwei Terme rechts und links davon zur Deckung zu bringen(d.h. zu unifizieren). Kann ein Ausdruck unifziert werden, wird er zu wahr evaluiert, ist es nicht möglich zu false. Hierbei gibt es verschiedene Möglichkeiten:

1. term1 und term2 sind Konstanten:

Konstanten und auch Integerwerte sind immer nur mit sich selbst unifizierbar:

sommer = sommer Bedingung erfüllt
sommer = winter Bedingung nicht erfüllt
42 = 42 Bedingung erfüllt

2. term1 ist ein beliebieger Term und term2 eine freie(ungebundene) Variable:

X = familienmitglied(peter, mueller).

Bedingungen dieser Art sind stets erfüllbar, die Variable wird in diesem Beispiel an die Struktur gebunden.

3. term1 und term2 sind freie Variablen:
Beide Variablen teilen sich das selbe Objekt, das im Moment noch nicht feststeht. Sobald eine Variable gebunden wird, ist die andere auch an dieses Objekt gebunden.

4. term 1 und term2 sind Strukturen:
term1 und term2 sind nur unifizierbar, falls sie den gleichen Funktor haben, die gleiche Anzahl von Argumenten(Komponenten) und alle entsprechenden Argumente unifizierbar sind. Beispiel:

a(X, z(T, k)) = a(x, z(t, K))

Dieses Beispiel ist unifizierbar, a hat beidesmal den gleichen Namen und die gleiche Stelligkeit. Die freie Variable X wird an x gebunden z hat wieder den gleichen Namen und Stelligkeit usw..

familienmitglied(peter, mueller) = familienmitglied(peter, X).

Auch dieses Beispiel ist unifizierbar, da der gleiche Funktor mit gleicher Stelligkeit benutzt wird, die Konstante ‘peter’ lässt sich mit sich selbst zur Deckung bringen und die freie Variable X wird an ‘mueller’ gebunden.

Klauseln und Faktenbasis:

Nun wollen wir aber endlich mal zur eigentlichen Programmierung mit Prolog kommen. Hierzu brauchen wir noch zwei Begriffe. Eine Klausel ist eine Regel nach der unser Programm arbeitet. Syntax:

klauselname(argument1, argument2) :- ... .

Die drei Punkte sollen verdeutlichen, dass hier beliebige Terme stehen können. Jede Klausel wird mit einem Punkt abgeschlossen. Eine Faktenbasis repräsentiert das “Wissen” über das unser Prologprogramm verfügt. Einträge in der Faktenbasis sind normalerweise Funktoren mit Konstanten als Argumente, denen keine weiteren Terme folgen. Als Grundlage für die nächsten Beispiele sei folgende Faktenbasis gegeben:

mann(adam).
mann(donald).
mann(peter).
mann(tick).
mann(trick).
frau(eva).
frau(daisy).
frau(steffi).
frau(marie).
elternteil(adam, daisy).
elternteil(eva, daisy).
elternteil(adam, peter).
elternteil(eva, peter).
elternteil(donald, tick).
elternteil(donald, trick).
elternteil(daisy, tick).
elternteil(daisy, trick).
elternteil(peter, marie).
elternteil(steffie, marie).

Was hat das zu bedeuten? Nun, mann() ist eine Klausel die überprüft ob ein gegebener Name ein Mann ist. Machen wir den Test. Wir wollen testen ob ‘donald’ ein Mann ist, also tippen wir in Prolog( ?- ist die Eingabeaufforderung bei SWI) folgende Zeile ein:

?- mann(donald).

Und promt wird uns Prolog mit yes antworten. Woher weiss Prolog das? Es geht alle bekannten Klauseln(Regeln) von mann durch und versucht ‘donald’ mit den bekannten Argumenten zu unifizieren. Dies gelingt, da mann(donald) in der Faktenbasis ist. Dagegen wird Prolog zu der Zeile

?- mann(dagobert).

mit no antworten, da es dagobert nicht unifzieren kann. Eingangs habe ich erwähnt, dass logische Programmiersprachen nicht nur Terme auf wahr/falsch überprüfen kännen, sondern auch herausfinden welche Variablenbelegung(en) einen Ausdruck wahr werden lassen. Probieren wir das aus. Diesesmal übergeben wir der Klausel mann() nicht eine Konstante, sondern eine freie Variable:

?- mann(X).

Prolog antwortet uns mit X = adam. Aber es gibt doch noch mehr Männer, und wir wollten doch alle Variablenbelegungen herausbekommen. Nun, noch müssen wir es Prolog explizit sagen, dass es nach einer weiteren Lösung suchen soll. Dies können wir tun, indem wir “;” drücken. Dadurch wird Prolog angewiesen in der Klausel rückwärts zu gehen, zum letzten sog. Choice Point, also einem Punkt an dem es die Wahl zwischen mehreren Alternativen hatte. Doch dazu sage ich zu einem späteren Zeitpunkt mehr. Eine andere Wahl für X ist donald, Prolog spuckt also X = donald aus. Dieses Spielchen können wir jetzt treiben, bis Prolog alle Möglichkeiten durch hat, dann wird es mit no antworten.
Die Klausel elternteil soll die Bedeutung haben, dass das erste Argument ein Elternteil vom zweiten Argument ist. Wenn wir also herausfinden wollen wer die Eltern von daisy sind müssen wir Prolog fragen:

?- elternteil(X, daisy).

Die Antwort:

X = adam ;
X = eva ;
No

Mit unserer Faktenbasis haben wir nun ein gewisses Grundwissen mit dem wir weiter arbeiten können. Wir können uns nun zum Beispiel eigene Regeln und Klauseln schreiben. Ein Beispiel wäre die Vater(V, K) Klausel. Zuerst müssen wir uns überlegen was einen Vater charakterisiert: Ein Vater muss auf alle Fälle ein Elternteil sein UND ein Vater muss ein Mann sein. Dies können wir leicht in Prolog ausdrücken:

vater(V, K) :- elternteil(V, K), mann(V).

Das Komma zwischen elternteil und mann repräsentiert hier das UND. Beispiele mit vater():

?- vater(X, daisy). %gibt uns alle Väter von Daisy aus
?- vater(adam, X). %gibt alle Personen aus, deren Vater adam ist

Zum Abschluss wollen wir uns noch eine Klausel geschwister(k1, k2) ausdenken. Wieder müssen wir uns fragen was denn Geschwister charakterisiert: Zumindest ein Elternteil müssen beide gemeinsam haben UND sie dürfen nicht die selbe Person sein. Formuliert als Prolog-Klausel:

geschwister(K1, K2) :- elternteil(E, K1), elternteil(E, K2), K1\=K2.

Wie habe ich jetzt erreicht, dass beide Kinder den gleichen Elternteil haben? Prolog wertet die Klausel von links nach rechts aus. Gehen wir von dem Fall aus, dass wir für K1 und K2 Konstanten eingesetzt haben, also wissen wollen, ob zwei Personen Geschwister sind. Jetzt versucht Prolog für E eine Variablenbelegung zu finden, so dass elternteil(E, K1) wahr wird. Hat es diese gefunden, kommt es zum zweitem Teil der Klausel und versucht auch hier zu unifizieren. E ist nun aber schon gebunden, das heisst Prolog schaut einfach in der Wissensbasis nach, ob es diesen Ausdruck mit wahr belegen kann. Zum Schluss vergleicht es noch, ob K1 und K2 nicht die selbe Person ist.

geschwister(tick, trick). %überprüft ob tick und trick Geschwister sind
geschwister(tick, X). %gibt alle Geschwister von tick aus
geschwister(X, Y). %gibt alle Paare von Personen aus, die Geschwister sind

Bei der letzten Anweisung gibt Prolog immer zwei Möglichkeiten pro Geschwisterpaar aus:

X = daisy

Y = peter ;

X = daisy

Y = peter ;

Dies liegt daran, dass es pro Geschwisterpaar zwei Elternteile gibt, den Weg über die Mutter und den Weg über den Vater.

Wie bei jeder Programmiersprache gilt auch insbesondere bei Prolog: üben, üben, üben… Es ist am Anfang schwer zu verstehen, besonders wenn man jahrelang nur imperativ programmiert hat.

Anmerkung zu SWI-Prolog: Am besten man schreibt die Klauseln und die Faktenbasis in eine Textdatei mit Endung .pl. Dann kann man im Programm ganz leicht mit File->Consult… darauf zugreifen.

Die verwendete Faktenbasis gibt es hier und die benutzten Klauseln hier