 \(\begingroup\)
Mit diesem recht kurzen Artikel möchte ich eine Einführung in die Programmierung mit der Programmiersprache Prolog geben.
Einleitung
Prolog steht für Programming in Logic. Entwickelt wurde diese Sprache von dem französischen Informatiker Alain Colmerauer zu Beginn der 1970er Jahre und sie gehört zu den sogenannten logischen Programmiersprachen. Dieser Typ von Programmiersprache unterscheidet sich von den sonst gebräuchlichen bzw. bekannten imperativen/prozeduralen Programmiersprachen, wie zum Beispiel Pascal, Java und Scheme.
Ein Programm, welches in einer logischen Programmiersprache geschrieben wurde, ist eine reine Sammlung von logischen Formeln, deren Auswertungsstrategie nicht Bestandteil des Programmes ist. Das System prüft lediglich, ob die Aussagen wahr oder falsch sind bzw. es gibt Variablenbelegungen an, die die Aussagen wahr machen können. Die Programmierung befindet sich deshalb auf einer hohen Abstraktionsebene.
Speziell sind in Prolog einfache Schleifenkonstrukte, welche man aus den imperativen Programmiersprachen kennt, nur sehr eingeschränkt bis gar nicht möglich.
Auch die Zuweisung von Variablen ist nur sehr eingeschränkt möglich. Es gibt sogenannte freie und gebundene Variablen. Einer einmal gebundenen Variable kann zur Laufzeit kein anderer Wert mehr zugewiesen werden. Die folgenden Beispiele sind mit dem SWI-Prolog erstellt und getestet worden, da diese Version für Forschungs- und Schulungszwecke kostenlos zur Verfügung gestellt wird.
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
Bei einer Konstanten handelt es sich um eine zusammenhängende Folge alphanumerischer Zeichen, beginnend mit einem Kleinbuchstaben. Wie zum Beispiel: hallo, sONNE, h1mm3l
Oder beliebige Zeichenfolge in einfachen Anführungszeichen. Wie zum Beispiel:
'Hallo', 'S@lz'
Variablen
Bei einer Variablen handelt es sich um eine alphanumerische Zeichenfolge beginnend mit einem Grossbuchstaben oder einem Unterstrich. Wie zum Beispiel: X, Y, _hummel, Hoelle
Kommentare
Kommentare über mehrere Zeilen werden wie in Java mit /* */ gebildet. Das Prozentzeichen % dient zum Kommentieren des Restes einer Zeile.
Strukturen
Strukturen sind zusammengesetzte Terme, die sich aufteilen lassen in Funktor und Komponenten. Die Anzahl der Komponenten gibt die Stelligkeit des Funktors an. Wie zum Beispiel: familienmitglied(peter, mueller).
familienmitglied ist der Funktor mit der Stelligkeit zwei, da er zwei Komponenten hat. Strukturen lassen sich auch schachteln. Wie zum Beispiel: 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 true 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 erfüllt die Bedingung, sommer = winter erfüllt die Bedingung nicht und 42 = 42 erfüllt die Bedingung.
2. term1 ist ein beliebiger 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. Wie zum 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. Die Syntax dazu lautet: 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:
\sourceonProlog
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).
\sourceoff
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 (bei ?- handelt es sich um die Eingabeaufforderung des SWI-Editors), folgende Zeile ein:
\sourceon Prolog
?- mann(donald).
\sourceoff
Und prompt wird uns Prolog mit yes antworten. Woher weiß 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 enthalten 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. Dieses Mal ü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 heißt 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 , no
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 der Endung .pl. Dann kann man im Programm ganz leicht mit File->Consult... darauf zugreifen.
\(\endgroup\)
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
