Prolog Florian Kleene

Westfälische Wilhelms-Universität Münster
Ausarbeitung
Prolog
im Rahmen des Seminars Programmiersprachen
Florian Kleene
Themensteller: Prof. Dr. Herbert Kuchen
Betreuer: Dipl.-Medienwiss. Susanne Gruttmann
Institut für Wirtschaftsinformatik
Praktische Informatik in der Wirtschaft
Inhaltsverzeichnis
1 Einführung in Prolog
1
1.1
Entstehung und Geschichte . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Prolog-Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Anwendungsgebiete . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2 Aufbau von Prolog-Programmen
3
2.1
Grundsätzliche Struktur . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2
Fakten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.3
Regeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.4
Anfragen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.5
Code-Beispiel: Stammbaum . . . . . . . . . . . . . . . . . . . . . . .
6
3 Funktionsweise des Interpreters
3.1
Grundlagen der Logik
8
. . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1.1
Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.1.2
Prädikatenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2
Unifikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3
Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4
Backtracking und der Cut . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Prolog in der Praxis
17
4.1
Expertensysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2
Code-Beispiel: Send + More = Money . . . . . . . . . . . . . . . . . 19
5 Zusammenfassung und Fazit
20
A Anhang
22
A.1 Code-Beispiel Stammbaum . . . . . . . . . . . . . . . . . . . . . . . . 22
A.2 Wahrheitstabelle zur Resolutionsprüfung . . . . . . . . . . . . . . . . 23
A.3 Abarbeitungsreihenfolge von Anfragen an den Prolog-Interpreter (trace) 24
Literaturverzeichnis
25
i
Kapitel 1: Einführung in Prolog
1
1.1
Einführung in Prolog
Entstehung und Geschichte
Prolog ist die wohl bekannteste logische Programmiersprache. Entwickelt wurde sie
Anfang der 1970er Jahre vom französischen Forscher Alain Colmerauer und seinen
Mitarbeitern am Groupe d’Intelligence Artificielle in Marseille. Der Name Prolog
entstand aus dem französischen PROgrammation en LOGigue“, was mit Program”
”
mieren in Logik“ ins Deutsche übersetzt werden muss. Aufbauend auf den Ideen des
Forschers Edgar F. Codd zu relationalen Datenbankmodellen [Bo87, S. 8], J.A. Robinsons Arbeit zum Resolventenprinzip und dem Unifikationsverfahren von Jacques
Herbrand [CL90, S. 2] entwickelte Colmerauer zunächst System-Q. System-Q war
ein Frage-Antwort-System, welches auf Hornklauseln aufbaute und die oben genannten Prinzipien der Resolution und Unifikation zur Beweisführung ausnutzte [CL90,
S. 2]. Ausgehend von diesem System entstand mit Unterstützung von P. Roussel
und R. Pasero die Sprache Prolog.
Der erste Interpreter für Prolog wurde 1973 in Fortran geschrieben und um 1975
stand der erste Compiler zur Verfügung. Zu dieser Zeit wurde Prolog nur von einem
engen Personenkreis der Artificial-Intelligence-Forscher genutzt und geschätzt. Erst
als die japanische Regierung 1981 Prolog zur Basissprache ihrer Rechnersysteme
”
der 5. Generation“ – eine Rechnerarchitektur, die viele parallel arbeitende Prozessoren vorsieht – ernannte, erlangte Prolog einen größeren Bekanntheitsgrad. Zwar ist
die Bedeutung der Programmiersprache Prolog in der Folgezeit in den Hintergrund
gerückt und sicher keiner breiten Masse mehr bekannt, doch werden auch heute noch
praktische Anwendung in Prolog programmiert. Als Beispiele lassen sich Programme zur Fahrplangestaltung bei Zugverspätungen, zur Minimierung von Materialverbrauch oder zur Aufstellung von Schicht- und Stundenplänen anführen [IF08].
Im Gegensatz zu prozeduralen Programmiersprachen ist der Programmierer in Prolog lediglich aufgefordert das Problem zu beschreiben. Er muss jedoch keinen Lösungsalgorithmus spezifizieren. Insofern ist Prolog deklarativ wie beispielsweise die
bekannte Structured Query Language (SQL) für Datenbanken und es steht die Frage nach dem Was gelöst werden soll“ im Gegensatz zur Frage nach dem Wie es
”
”
gelöst werden soll“ bei imperativen oder objektorientierten Programmiersprachen
im Vordergrund. Dennoch bedient auch Prolog sich bei der Lösungssuche einiger
prozeduraler Elemente [KS88, S. 13], die im Kapitel 3 aufgezeigt werden.
1
Kapitel 1: Einführung in Prolog
1.2
Prolog-Systeme
Als die Programmiersprache Prolog nach der ersten Entwicklung durch A. Colmeraurer größere Bekanntheit erlangte, entwickelte sich eine Vielzahl von verschiedenen
Prolog-Systemen. Bekannte Namen sind in diesem Zusammenhang Arity-Prolog,
Micro-Prolog, Prolog II und III, Turbo-Prolog, SWI-Prolog, IF/Prolog und eine
Vielzahl anderer [Be88, S. 275]. Die Systeme unterschieden sich im Hinblick auf die
Anzahl der Schnittstellen zu anderen Programmiersprachen oder die dem Anwender
zur Verfügung gestellten Utilities (Interpreter, Compiler, Editor, Bugtracker, usw.).
Außerdem gibt es in den Systemen eine unterschiedliche Syntax und verschiedene
Bezeichnungen und Anzahlen für die sog. Built-In-Prädikate – einer Art Grundwortschatz bzw. Schlüsselwörter.
Im Laufe der Zeit bildeten sich zwei Standards für die Syntax heraus. Zum einen
war dies die Marseille-Syntax, wie sie ursprünglich von Alain Colmerauer aufgestellt
wurde, und zum anderen die Edinburgh-Syntax [Be88, S. 275 ff.]. Erst im Jahr 1995
wurde bei der ISO der Standard ISO/IEC 13211-1:1995 [ISO95] und im Jahr 2000
der zweite Teil ISO/IEC 13211-2:2000 [ISO00] aufbauend auf der Edinburgh-Syntax
festgelegt. Zumindest den ersten Teil des ISO-Standards aus dem Jahr 1995 implementieren heute die Systeme IF/Prolog und SWI-Prolog, die in größeren Kreisen
Verbreitung gefunden haben. SWI-Prolog wird in der Version 5.6.64 im Rahmen
dieser Arbeit verwendet.
1.3
Anwendungsgebiete
Zunächst ist zu sagen, dass es sich bei Prolog um eine universelle Programmiersprache handelt [CL90, S. 3], die also prinzipiell für diverse Gebiete in der Informatik
einsetzbar ist. Ursprünglich entwickelt wurde sie jedoch für die algorithmische Verarbeitung natürlicher Sprachen [KS89, S. 9] – also den Bereich der Computerlinguistik.
Aus diesem Ursprung heraus ergibt sich, dass Prolog insbesondere für die verschiedenen Teilgebiete der künstlichen Intelligenz, wie Spracherkennung und Bildverarbeitung und weniger für arithmetische Operationen geeignet ist. Neben dem Gebiet
der Computerlinguistik findet Prolog seine Anwendung in Expertensystemen, die im
Kapitel 4.1 dieser Arbeit näher erläutert werden, und in der Lehre und Forschung
[CL90, S. 3, 4].
2
Kapitel 2: Aufbau von Prolog-Programmen
2
Aufbau von Prolog-Programmen
2.1
Grundsätzliche Struktur
Ein Prolog-Programm besteht aus einer sog. Wissensbasis, die einen Ausschnitt aus
der Realwelt darstellt. In der Wissensbasis werden Fakten und Regeln, die die Eigenschaften der Objekte aus der Realwelt und deren Beziehungen widerspiegeln,
gespeichert. Fakten und Regeln werden durch den Programmierer mit Hilfe eines
Editors in einer Datei gespeichert, von manchen Systemen kompiliert (z. B. Arity Prolog [Be88, S. 277]) und anschließend vom Interpreter, der die Aufgabe eines
Theorembeweisers bzw. einer Inferenzmaschine übernimmt, geladen. Um Erkenntnisse aus der Wissensbasis zu erlangen, ist der Nutzer aufgefordert Anfragen an den
Interpreter abzugeben, die dieser versucht durch die Wissensbasis zu beweisen oder
zu widerlegen.
Auch in diesem Aspekt wird ein wesentlicher Unterschied zu den heute mehr gebräuchlichen Programmiersprachen deutlich und man erkennt die Ursprünge des
Frage-Antwort-Systems wieder. Der schematische Aufbau eines Prolog-Programms,
der an die Darstellung aus [KS89, S. 15] angelehnt ist, ist in der nachfolgenden
Grafik noch einmal zu erkennen.
Editor
Benutzerschnittstelle
(Anfragen)
Interpreter
(Inferenzmaschine)
Wissensbasis
(Fakten und Regeln)
Abbildung 1: Bestandteile der Programmiersprache Prolog
2.2
Fakten
Fakten in Prolog bezeichnen Aussagen über Objekte oder die Beziehung zwischen
Objekten, die immer als eindeutig wahr angesehen werden [KS88, S. 16]. Die generelle Struktur eines Fakts lässt in Anlehnung an die Backus-Naur-Form beschreiben
durch:
f akt ::= f unktor. | f unktor({argument, }∗0 argument).
3
Kapitel 2: Aufbau von Prolog-Programmen
Fakten bestehen also entweder aus einem Funktor oder aus einem Funktor auf den
in runden Klammern beliebig viele durch Kommata getrennte Argumente folgen
[KS88, S. 76]. Für alle nachfolgenden Quellcodebeispiele sei darauf hingewiesen,
dass Zeilenkommentare in Prolog durch %“ eingeleitet und Blockkomentare durch
”
/* ... */“ eingeschlossen werden. Fakten und Regeln werden am Ende der Zeile
”
durch einen Punkt abgeschlossen.
true . % Nullstelliger Fakt .
student ( philipp ). % Philipp ist ein Student .
vater ( reinhold , florian ). % Reinhold ist Florians Vater .
Zu beachten ist, dass Prolog kein tieferes Verständnis von Fakten gewinnt, sondern
lediglich Zeichenfolgen verarbeitet. Die Aussage Reinhold ist Florians Vater“ aus
”
dem dritten Fakt entsteht aus der Interpretation des Programmieres heraus und
könnte auch durch Florian ist Reinholds Vater“ festgelegt werden. Die Art und
”
Weise die Reihenfolge der Argumente zu lesen sollte daher einmalig vom Programmierer festgelegt werden [CM03, S. 4].
Für die Programmierung von Fakten gilt folgende Syntax [KS88, S. 18]:
1. Der Bezeichner – auch Funktor genannt – eines Fakts beginnt mit einem Kleinbuchstaben. Dadurch wird er vom Prolog-Interpreter als Konstante aufgefasst.
2. Auf den Funktor folgen direkt in Klammern die Argumente. Mehrere Argumente werden durch Kommata voneinander abgetrennt.
3. Die Argumente eines Fakts können selbst auch wieder Fakten sein. Fakten
oder verschachtelte Fakten werden als Struktur bezeichnet.
4. Die Anzahl der Argumente, die beliebig groß aber auch Null sein kann, wird
als Stelligkeit bezeichnet. Fakten mit gleichem Funktor und gleicher Stelligkeit
werden unter dem Begriff Prädikat zusammengefasst.
5. Alle Fakten werden mit einem Punkt abgeschlossen.
2.3
Regeln
Regeln ermöglichen es dem Prolog-Interpreter Wissen abzuleiten und vereinfachen
es dem Programmierer eine Vielzahl gleich gearteter Fakten in der Wissensbasis
darzustellen [KS88, S. 28]. Die allgemeine Struktur einer Regel ist gegeben durch:
regel ::= f akt : − {struktur, }∗1 struktur.
4
Kapitel 2: Aufbau von Prolog-Programmen
Angenommen jeder Student interessiere sich für Informatik. Dies ist mit unserer
bisherigen Kenntnis nur möglich, indem jeweils zwei Fakten pro Person in die Wissensbasis aufgenommen werden:
student ( florian ). % Florian ist Student .
% Florian interessiert sich für Informatik .
interesse ( florian , informatik ).
student ( philipp ). % Philipp ist Student .
% Philipp interessiert sich für Informatik .
interesse ( philipp , informatik ).
Effizienter ist dies durch eine einzige Regel in Prolog ausdrückbar: Jemand in”
teressiert sich für Informatik, falls er Student ist.“ Mit Hilfe von Regeln wird die
Wissensbasis übersichtlicher und bei vielen gleichartigen Fakten verkürzt sie sich
enorm.
student ( florian ). % Florian ist Student .
student ( philipp ). % Philipp ist Student .
% eine einzige Regel
interesse (X , informatik ) : - student ( X ).
Den linken Teil der Regel vor dem :-“ bezeichnet man als Kopf, den Teil auf der
”
rechten Seite als Rumpf der Regel. Regeln sind so zu lesen, dass der Kopf der Regel
als wahr angesehen werden kann, sofern alle Voraussetzungen im Rumpf erfüllt, d.h.
wahr sind. Das :-“ muss somit als umgedrehter Implikationspfeil gelesen werden.
”
Prinzipiell können auch Fakten in Form von Regeln dargestellt werden. Der Kopf
der Regel besteht dann aus dem Fakt selbst und der Rumpf aus dem null-stelligen
Prädikat true. Der Fakt mensch(florian). würde also zu der Regel mensch(florian
):- true. umgeformt.
Für die Programmierung von Regeln gilt folgende Syntax [KS88, S. 28]:
1. Der Kopf der Regel besteht aus genau einem Fakt, der als Argumente sowohl
Konstanten als auch Variablen, die in Prolog mit einem Großbuchstaben oder
einem Unterstrich begonnen werden, aufweisen kann.
2. Der Rumpf der Regel besteht aus einer oder mehreren Strukturen, die durch
Kommata oder Semikola voneinander abgetrennt werden. Das Komma in Prolog bezeichnet dabei das logische Und, während das Semikolon für das logische
Oder verwendet wird.
5
Kapitel 2: Aufbau von Prolog-Programmen
3. Der Geltungsbereich einer Variablen ist auf exakt eine Regel beschränkt, d.h.
Variablen mit derselben Bezeichnung in verschiedenen Regeln sind voneinander
unabhängig.
4. Jede Regel wird durch einen Punkt abgeschlossen.
Fakten und Regeln, die nach der obigen Syntax aufgebaut sind, werden in Prolog
als Klauseln – genauer als Programmklauseln – bezeichnet.
2.4
Anfragen
Die Benutzung von Prolog-Programmen geschieht dadurch, dass der Nutzer am
Prolog-Prompt, der durch ?-“ symbolisiert wird, Anfragen abgibt. Anfragen müssen
”
aus einer oder mehreren durch Kommata oder Semikola getrennten Strukturen, die
auch Variablen beinhalten können, bestehen. Der Geltungsbereich einer Variablen
ist in diesem Fall auf den Bereich einer einzelnen Anfrage beschränkt. Der Interpreter
versucht die Anfrage aus der Wissensbasis abzuleiten und antwortet mit true, false
oder, falls die Anfrage Variablen beinhaltete, mit einer Variablenbelegung, die bei
entsprechender Anfrage true liefern würde.
2.5
Code-Beispiel: Stammbaum
Im Folgenden soll der Umgang mit Fakten, Regeln und insbesondere Anfragen anhand eines Beispielprogramms gezeigt werden. Das Äquivalent zum Hello-World”
Programm“ in imperativen Programmiersprachen ist die Implementierung eines
Stammbaumes in logischer Programmierung. Der als Beispiel gewählte Stammbaum
ist in der folgenden Grafik zu sehen, wobei die ausgegrauten Personen nur zur optischen Vervollständigung des Stammbaumes eingezeichnet sind. Die zugehörige Wissensbasis, die nach oben beschriebener Syntax aufgebaut ist, befindet sich im Anhang
auf Seite 22 und soll als Code-Grundlage für die gesamte Seminararbeit dienen. Sie
enthält neben den offensichtlichen Fakten einige Regeln, die die Verwandtschaftsverhältnisse beschreiben.
6
Kapitel 2: Aufbau von Prolog-Programmen
Adam + Eva
Hermann + Katharina
Tina + Wilhelm
Reinhold + Doris
Florian
Thomas
Steffen
Abbildung 2: Darstellung des Staummbaumes
Zunächst werden einige Anfragen gestellt, die sich direkt auf Fakten in der Wissensbasis beziehen, also durch einfaches Vergleichen bewiesen oder widerlegt werden
können.
?-
mutter ( doris , thomas ).
true .
?-
vater ( hermann , thomas ).
false .
?-
mensch ( tobias ).
false .
Wie die letzte Anfrage zeigt, können Anfragen, die sich auf Aussagen beziehen, die
nicht in der Wissensbasis abgebildet sind, nicht bewiesen werden. Die Wissensbasis
repräsentiert eine abgeschlossene Welt in der alles, was nicht explizit bewiesen werden kann, als falsch angesehen wird. Die Anfrage wird daher vom Interpreter mit
false beantwortet. Für die nachfolgenden Anfragen ist jeweils die Auswertung einer
oder mehrerer Regeln nötig. Die Funktionsweise des Interpreters für die Schlussfolgerungen wird in den kommenden Kapitel ausführlich vorgestellt.
?-
elternteil ( doris , florian ) . % Beispiel 1
true .
?-
vorfahre (X , reinhold ) . % Beispiel 2
X = hermann ;
X = katharina ;
false .
?-
vorfahre ( doris , Y ) . % Beispiel 3
Y = florian ;
Y = thomas ;
false .
7
Kapitel 3: Funktionsweise des Interpreters
Neben Anfragen, die true oder false als Ergebnis zurück liefern (Beispiel 1: ?elternteil(doris,florian).), können auch Anfragen abgeben werden, die Varia-
blen beinhalten (Beispiele 2 und 3). Derart gestaltete Anfragen beantwortet der
Interpreter mit Variablenbelegungen, die zum Ergebnis true führen würden. Gibt es
mehrere Lösungen, so ist der Nutzer aufgefordert durch Eingabe eines Semikolons
eine weitere Lösung zu verlangen. Der Interpreter gibt solange Lösungen zurück, bis
es keine weiteren mehr gibt und endet dann mit false.
Das dritte Beispiel soll nochmals verdeutlichen, dass der Prolog-Interpreter sowohl
die Anfragen als auch die Wissensbasis lediglich als Zeichenfolgen verarbeitet. Das
Prädikat vorfahre( , ) ist daher auch dazu geeignet Nachfahren zu bestimmen.
3
3.1
3.1.1
Funktionsweise des Interpreters
Grundlagen der Logik
Aussagenlogik
Um die Funktionsweise des Prolog-Interpreters verstehen zu können, erscheint es
zunächst sinnvoll, die Grundlagen der Logik, die das Fundament der Programmiersprache bilden, darzustellen. Die Syntax von Prolog ist nämlich nicht willkürlich
gewählt, sondern lehnt sich stark der Prädikatenlogik erster Ordnung an. Zunächst
sei jedoch die Aussagenlogik als Ausgangspunkt für die Prädikatenlogik vorgestellt.
Einfache aussagenlogische Formeln bestehen aus durch Und (∧) oder Oder (∨) verknüpften Aussagen (negierte (¬) oder nicht-negierte Literale), wobei ein Wahrheitswert für eine Formel aus den Wahrheitswerten der Literale resultiert [Sch00, S. 15].
Die Formel a ∧ (¬b ∨ c) ∧ b ist beispielsweise für die Belegung a = 1, b = 1, c = 1
erfüllt, d. h. =1. Die Formel (a ∧ b) ∧ (¬a ∧ b) ist hingegen für keine Belegung erfüllt.
Man nennt eine solche Formel Kontradiktion, während Formeln, die für alle Belegungen erfüllt sind, Tautologien genannt werden.
Prolog arbeitet nicht mit aller Art aussagenlogischer Formeln, die erzeugbar sind. Es
hat sich herausgestellt, dass sich Hornformeln – benannt nach dem amerikanischen
Logiker Alfred Horn – in Kombination mit der SLD-Resolutionsregel (Linear resolution with S elected function for Definite clauses) gut maschinell verarbeiten lassen
und gleichzeitig auch viele Praxisprobleme in dieser Form abbildbar sind [KS88,
S. 36]. Die sog. Hornformeln, deren Aufbau im Folgenden gezeigt werden soll, stellen eine Teilmenge aller aussagenlogischen Formeln dar:
8
Kapitel 3: Funktionsweise des Interpreters
• Hornklausel: Eine Hornklausel ist eine Disjunktion (Oder-Verkünpfung) von
Literalen, wobei maximal ein Literal in nicht-negierter Form aufritt.
Beispiele: a; (¬a); (¬a ∨ b); (¬a ∨ ¬b ∨ c); (¬a ∨ ¬b ∨ ¬c);
• Hornformel: Eine Hornformel ist eine Konjunktion (Und-Verknüpfung) von
Hornklauseln.
Beispiele: a; (¬a) ∧ (¬a ∨ b); a ∧ (¬a ∨ ¬b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c);
Eine Hornformel ist also eine Formel in konjunktiver Normalform, d. h. eine Konjunktion von Disjunktionstermen, bei der jeder Disjunktionsterm höchstens ein nichtnegiertes Literal aufweist [Sch00, S. 26, 31].
Den Fakten, Regeln und Anfragen in Prolog-Programmen lassen sich charakteristisch drei verschiedene Arten der Hornformeln zuordnen:
Ein Fakt ist eine Hornformel, die aus exakt einem nicht-negierten Literal besteht.
Eine Regel enthält ein oder mehrere negierte Literale und exakt ein positives Literal und eine Anfrage besteht nur aus negierten Literalen. Um dies ersichtlich zu
machen muss zunächst die Auflösung des umgedrehten Implikationspfeils innerhalb
der Anfragen und Regeln vorgenommen werden. Es gilt (a ← b) = (a ∨ ¬b) und
allgemeiner unter Ausnutzung der De Morgan’schen Regel a ← (b1 ∧ ... ∧ bn ) =
a ∨ ¬(b1 ∧ ... ∧ bn ) = a ∨ ¬b1 ∨ ... ∨ ¬bn [Sch00, S. 14, 24]. Wendet man diese Regeln
entsprechend an, so lässt sich folgende Tabelle zusammenstellen:
Darstellung in Prolog
Codierung durch
Auflösung des
Symbole
Implikationspfeils
Fakt
student(florian).
a
a
Regel
interesse(florian,informatik)
c ← a, b, ...
c ∨ ¬(a ∧ b ∧ ...)
= c ∨ ¬a ∨ ¬b ∨ ¬...
:- student(florian), ...
Anfrage
?- interesse(florian,informatik).
←b
¬b
Tabelle 1: Charakteristika von Fakten, Regeln und Anfragen in Hornklauseln
Fakten und Regeln bezeichnet man, da sie jeweils ein nicht-negiertes Literal enthalten, als Programmklauseln. Anfragen hingegen werden als Zielklauseln bezeichnet.
Um eine Zielklausel beweisen zu können, muss diese unter Ausnutzung der Programmklauseln soweit äquivalent transformiert werden, dass der Beweis aus der Wissensbasis ersichtlich wird. Dabei kommt dem Schlussfolgern aus der Logik die entscheidende Bedeutung zu. Eine Formel lässt sich aus den Ausgangsformeln schlussfolgern, wenn die neue Formel für alle Belegungen, für die die Ausgangsformeln wahr
liefern, ebenfalls wahr liefert [KS88, S. 39].
9
Kapitel 3: Funktionsweise des Interpreters
Beispiel: Aus (a ∨ b) ∧ (¬b ∨ c) lässt sich die Formel (a ∨ c) folgern, da
nicht gleichzeitig b und ¬b wahr sein können. Das b kann also eliminiert
werden. Nachvollziehbar wird die Eliminierung sofort, nachdem man die
Ausgangsformel zu (¬a → b) ∧ (b → c) und das Ergebnis zu (¬a → c)
umgeformt hat.
Wendet man diese Regel der Eliminierung auf eine Kontradiktion wie z. B.
(¬a∧b)∧(a∧¬b) an, so bleiben keine Literale übrig und es entsteht die leere Klausel
(t). Diese Erkenntnis und das Wissen darüber, dass eine Formel genau dann unerfüllbar (widerspruchsvoll) ist, wenn ihre Negation eine Tautologie ist, führt zum
Unerfüllbarkeitstest. Fügt man das negierte Literal aus der Anfrage dem Programm
hinzu und gelingt es, die leere Klausel herzuleiten, so gibt es einen Widerspruch
[Sch00, S. 37 ff.]. Dies ist äquivalent dazu, dass die unnegierte Anfrage sich aus dem
Programm ableiten lässt, also beweisbar ist.
Beispielsweise existiere eine Wissensbasis {e, c, (d ← e), (b ← c, d), (a ← b)} und
es werde die Anfrage nach ← a gestellt, so muss für den Beweis der Zielklausel in
Kombination mit dem Programm die leere Klausel erzeugt werden können. Gelingt
dies, so ist a beweisbar. In der nachfolgenden Darstellung ist in jeder Zeile ein Eliminierungsschritt (Resolution) ausgeführt worden. Ziel- und Programmklausel sind
innerhalb einer Zeile durch Komma voneinander abgetrennt und passen“ deswegen
”
zu einander, weil die Zielklausel nur negierte Literale und Fakten und Köpfe von
Regeln stets positive Literale sind (vgl. auch obige Tabelle):
(← a), (a ← b)
(← b), (b ← c, d)
(← c, d), c
(← d), (d ← e)
(← e), e
t
Die Anfrage ← a ist also aus dem Programm beweisbar. Die zugehörige, vollständige
Wahrheitstabelle findet der interessierte Leser im Anhang auf Seite 23.
3.1.2
Prädikatenlogik
Für die vollständige Betrachtung von Prolog-Programmen genügt die Aussagenlogik
alleine jedoch noch nicht, da keine Funktoren und keine Variablen, wie sie in PrologProgrammen enthalten sind, nachgebildet werden können. Die Prädikatenlogik erweitert die Aussagenlogik um Quantoren, Funktions- und Prädikatssymbole [Sch00,
S. 50]. Insbesondere die Quantoren ∃ (es existiert ein) und ∀ (für alle) sind in diesem
10
Kapitel 3: Funktionsweise des Interpreters
Zusammenhang unabdingbar, da z. B. der Aussage vater(X, f lorian) kein Wahrheitswert zugeordnet werden kann, solange die Variable X nicht durch einen Quantor
festgelegt ist. Ist X durch einen Quantor festgelegt, d. h. gebunden, so lässt sich ein
Wahrheitswert für ∃X : vater(X, f lorian) oder ∀Y : mutter(Y, f lorian) in Bezug
auf die Wissensbasis bestimmen.
In Prolog sind Variablen in Programmklauseln implizit allquantifiziert, da sie für
einen Beweis nur einmalig festgelegt werden können. Anfragen hingegen sind implizit existenzquantifiziert, weil es genügt eine Variablenbelegung aufzufinden, die die
Anfrage beweist.
Um die Beweisbarkeit einer Anfrage überprüfen zu können, muss diese daher zunächst
durch Transformationen in eine Form überführt werden, die keine Existenzquantoren mehr enthält. Durch den Vorgang der Skolemisierung, benannt nach dem norwegischen Mathematiker Thoralf Skolem, kann dies bewerkstelligt werden [Sch00,
S. 63 f.]. Grundlage dieses Verfahrens ist, dass existenzquantifizierte Variablen durch
eine Skolemkonstante bzw. bei voranstehendem Allquantor durch eine Skolemfunktion ersetzt werden können ohne dass sich der Wahrheitswert ändert [Sch00, S. 64, 65].
∀Y : ∃X : mann(Y ) → lieben(Y, X) ⇔ ∀Y : mann(Y ) → lieben(Y, fs (Y ))
Die Aussage Für alle Männer Y existiert eine Frau X, so dass Y X liebt“ wird
”
durch den Vorgang der Skolemisierung ersetzt durch Für alle Männer Y gibt es eine
”
vom konkreten Mann Y abhängige Frau X, die Y liebt“. Die existenzquantifizierte
Variable X wird also durch die Skolemfunktion fs (Y ) substituiert.
Nachdem alle existenzquantifizierenden Variablen ersetzt worden sind, können die
Allquantoren ohne weitere Beachtung weggelassen werden, da Variablen in Aussagen
– wie bereits oben erwähnt – implizit allquantifizierend sind [KS88, S. 65]. Die
Beweisbarkeit kann jetzt mit Hilfe des gewöhnlichen Unerfüllbarkeitstests, der aus
dem vorigen Kapitel bekannt ist, hergeleitet werden.
Im folgenden Kapitel wird die Instanziierung von Variablen und der Beweisprozess in
Prolog vorgestellt. Das Themengebiet der reinen Logik wird verlassen und der Focus
auf das Verständnis der konkreten Arbeitsweise des Prolog-Interpreters gelegt.
3.2
Unifikation
Die Wortbedeutung Unifikation leitet sich aus den lateinischen Wörtern unus (eins)
und facere (machen) ab, so dass sich als Gesamtbedeutung zu eins machen“ oder
”
vereinigen“ ergibt [KS89, S. 29]. Ziel ist es mit Hilfe der Unifikation die an den
”
Interpreter gestellten Anfragen aus der Wissensbasis abzuleiten. Um eine Anfrage
11
Kapitel 3: Funktionsweise des Interpreters
beantworten zu können, durchsucht der Interpreter die Wissensbasis nach einem
Prädikat mit gleichem Funktor und gleicher Stelligkeit. Dieses Prädikat kann sowohl
der Kopf einer Regel als auch ein Fakt sein. Damit die Anfrage bewiesen werden
kann, müssen neben Prädikat und Stelligkeit zusätzlich auch die Argumente des
Prädikats unifizieren [KS88, S. 103]. Für die weitere Betrachtung wird aus Gründen
der Übersichtlichkeit zwischen den verschiedenen Arten der Argumente unterschieden. Unifizierbarkeit lässt sich mit Hilfe des internen, zweistelligen Prolog-Prädikats
=( , )“ am Prompt überprüfen.
”
1. Zwei Konstanten sind unifizierbar, falls ihre Zeichenketten übereinstimmen:
Die Anfrage ?- =(florian,florian). würde also unifizieren, d. h. mit true
beantwortet.
2. Eine (ungebundene) Variable und eine Konstante sind stets dadurch unifizierbar, dass die Konstante an die Variable gebunden wird. Man nennt diesen
Vorgang Instanziierung der Variablen:
Die Anfrage ?- =(X,florian). würde also dadurch unifizieren, dass an die
Variable X die Konstante florian gebunden würde.
3. Eine (ungebundene) Variable und eine Struktur sind stets dadurch unifizierbar,
dass die Struktur an die Variable gebunden wird:
Die Anfrage ?- =(mensch(florian),X). würde also dadurch unifizieren, dass
an die Variable X die Struktur mensch(florian) gebunden würde.
4. Zwei (ungebundene) Variablen sind stets dadurch unifizierbar, dass sie im Anschluss für den gleichen Wert stehen.
5. Zwei Strukturen sind dann unfizierbar, wenn sie den gleichen Funktor, die
gleiche Stelligkeit haben und jedes Argument auch nach den hier vorgestellten
Regeln unfizierbar ist:
?- =(kind(eltern(X,doris),florian),kind(eltern(reinhold,doris),florian
)). als Anfrage würde also dadurch unifizieren, dass an die Variable X die
Konstante reinhold gebunden würde, da der Funktor kind übereinstimmt, die
Stelligkeit jeweils zwei ist und auch die Argumente nach den Regeln 5, 2 und
1 unifizierbar sind.
Bei der Unifikation wird von den meisten Prolog-Interpretern – so auch von SWIProlog – auf den sog. Occurcheck aus Gründen der Effizienz verzichtet [KS89, S. 176].
Der Occurcheck stellt einen Kontrollmechanismus bereit, der überprüft, ob eine Variable in beiden zu unifizierenden Argumenten auftritt. Das einfachste Beispiel hierzu ist die Anfrage ?- =(X,f(X))., die prinzipiell vom Interpreter abgefangen werden
12
Kapitel 3: Funktionsweise des Interpreters
müsste, um eine unendliche Schleife zu verhindern.
Durch die Unifikation lässt sich die Arbeitsweise des Interpreters für die Anfrage
nach Fakten in der Wissensbasis erklären. Falls jedoch die Auswertung von Regeln
für die Beantwortung einer Anfrage hinzugezogen werden muss, so ist ein weiteres
Konzept – nämlich das der Resolution – nötig.
3.3
Resolution
Die Resolution bezeichnet einen Schlussfolgerungsmechanismus [CM03, S. 248], der
bereits im Kapitel zur Aussagenlogik kurz behandelt wurde und dazu verwendet
wird, logische Formeln auf Gültigkeit zu prüfen. Ergebnis der Resolution zweier
Klauseln ist eine neue dritte Klausel, die sich als Konsequenz aus den beiden gegebenen Klauseln mit Hilfe der Unifikation ergibt. Die Anfrage am Prompt stellt
die zu beweisende Klausel dar. In Kombination mit einer Regel (Resolution) ändert
sich die zu beweisende Klausel, so dass ein äquivalentes Problem entsteht, welches
im nächsten Schritt zu beweisen ist.
Nachfolgend ist der für die Anfrage ?- vorfahre(reinhold,thomas). relevante Ausschnitt aus dem Code-Beispiel Stammbaum wiedergegeben:
vater ( reinhold , thomas ) .
elternteil (X , Y ) : - vater (X , Y ) .
vorfahre (X , Y ) : - elternteil (X , Y ) .
Der Prolog-Interpreter ist aufgefordert die Anfrage ?- vorfahre(reinhold,thomas).
zu beweisen. Er durchsucht die Wissensbasis nach einem Prädikat mit dem Funktor
vorfahre und Stelligkeit 2. In der dritten Zeile des Code-Ausschnitts wird er fündig.
Die Unifikation bewirkt die Instanziierung der Variablen X=reinhold und Y=thomas.
Durch die Resolution verlagert sich das zu beweisende Problem von ?- vorfahre(
reinhold,thomas). zu ?- elternteil(reinhold,thomas)., wobei die instanziierten
Variablen bereits eingesetzt wurden.
In einem nächsten Schritt unifiziert ?- elternteil(reinhold,thomas). mit elternteil
(X,Y):- vater(X,Y).. Wieder werden X und Y instanziiert und als Ergebnis der
Resolution ergibt sich das neu zu beweisende Ziel ?- vater(reinhold,thomas)..
Die Anfrage ?- vater(reinhold,thomas). unifiziert mit dem Fakt vater(reinhold
,thomas). in der Wissensbasis. Die Anfrage ist folglich bewiesen, also wahr. Weil
durch die Unifikation und Resolution nur erfüllbarkeitsäquivalente Umformungen
ausgeführt wurden, ist daher auch die Anfrage ?- vorfahre(reinhold,thomas). mit
wahr zu beantworten. Dieses Ergebnis ergibt sich auch aus dem Schaubild des
13
Kapitel 3: Funktionsweise des Interpreters
Stammbaums.
Zum Abschluss dieses Kapitels soll noch auf die prozedurale Arbeitsweise des PrologInterpreters, die Prolog als Programmiersprache von der reinen Logik differenziert
[Be86, S. 101], eingegangen werden. Das prozedurale Vorgehen bei der Beweissuche
sollte dem Programmierer bei der Zusammenstellung der Wissensbasis immer bewusst sein, da es sonst leicht zu ungewollten Fehlern und Problemen kommen kann.
Prolog durchsucht bei Anfragen die Wissensbasis nach passenden, d. h. unifizierbaren Prädikaten, von oben nach unten. Besteht die Anfrage aus mehreren verknüpften
Strukturen, so wird versucht, diese in der Reihenfolge von links nach rechts zu beweisen. Ein einfaches Beispiel, das die Wichtigkeit der Reihenfolge in der Wissensbasis
untermauern soll, ist nachfolgend wiedergegeben (vgl. [KS88, S. 71]:
beweisbar ( X ) : - zirkel ( X ) .
zirkel ( Y ) : - beweisbar ( Y ) .
beweisbar ( egal ) .
Stellt man die Anfrage ?- beweisbar(egal)., so liefert obiges Programm niemals
das Ergebnis true, sondern der Interpreter gerät in eine unendliche Schleife, obwohl
die Anfrage als Fakt in der Wissensbasis vorliegt. Die Begründung liegt in der oben
genannten Suchreihenfolge des Interpreters und dem ungünstigen Aufbau der Wissensbasis, so dass der Interpreter nie die dritte Zeile des Codes erreicht. Aus der
formalen Logik heraus ist ein solches Verhalten natürlich nicht erwünscht. Die Reihenfolge der Fakten und Regeln sollte keine Rolle spielen [Be86, S. 101].
Insbesondere für rekursiv definierte Prädikate, die im Übrigen die einzige Möglichkeit
darstellen in Prolog iterative Schleifen wie z. B. die for-Schleife nachzubilden, ist es
notwendig die Abbruchbedingung der Rekursion stets vor dem rekursiv definierten Prädikat selbst in die Wissensbasis aufzunehmen. Als Beispiel hierfür sei das
Prädikat vorfahre(_,_). aus dem Code-Beispiel genannt:
/* Abbruchbedingung */
vorfahre (X , Y ) : - elternteil (X , Y ) .
/* rekursive F un k t io n s de f i ni t i on von vofahre (_ , _ ) .
Nur so sind beliebig weit entfernte Vorfahren
ermittelbar */
vorfahre (X , Y ) : - elternteil (Z , Y ) , vorfahre (X , Z ) .
Steht das rekursiv definierte Prädikat in der Wissensbasis vor der zugehörigen Abbruchbedingung, so ist das Prädikat wertlos, da es den Interpreter in eine Schleife
ohne Abbruch zwingt (vgl. oben).
14
Kapitel 3: Funktionsweise des Interpreters
3.4
Backtracking und der Cut
Die bisherigen Ausführungen erklären bereits einen großen Teil der Vorgehensweise
des Prolog-Interpreters. Jedoch ist bislang nicht geklärt worden, wie vorgegangen
wird, wenn der Prolog-Interpreter durch die Resolution in eine Sackgasse“ gerät.
”
Als Beispiel soll die Anfrage ?- elternteil(doris,florian). dienen. Der relevante
Code-Ausschnitt ist nachfolgend wiedergegeben:
mutter ( doris , florian ) .
elternteil (X , Y ) : - vater (X , Y ) .
elternteil (X , Y ) : - mutter (X , Y ) .
Wie im Kapitel zur Resolution beschrieben durchsucht der Prolog-Interpreter die
Wissensbasis von oben nach unten nach unifizierbaren Prädikaten. In diesem Fall
würde die Anfrage also mit der in Zeile 2 gezeigten Regel unifizieren. Nach Instanziierung der Variablen und Resolution verbleibt als neues Ziel der Beweis von
?- vater(doris,florian).. Diese Klausel kann in der Wissensbasis nicht aufgefun-
den werden, so dass man nach bisheriger Kenntnis davon auszugehen hat, dass der
Prolog-Interpreter mit false antworten würde.
Dies ist jedoch nicht der Fall. Der Prolog-Interpreter erkennt, dass er in eine Sack”
gasse“ geraten ist und geht einen Schritt in seiner Auswertungsreihenfolge zurück
(Backtracking) [KS88, S. 104]. Er überspringt also die Regel in Zeile 2 und wendet
stattdessen die Regel in Zeile 3 an, die sich ebenfalls mit der Anfrage unifizieren
lässt. Als neues Ziel verbleibt zu zeigen, dass ?- mutter(doris,florian). gilt. Da
dies ein Fakt der Wissensbasis ist, gibt der Prolog-Interpreter demzufolge true aus.
Die Reihenfolge der Abarbeitungen lässt sich in Prolog durch das nullstellige BuiltIn-Prädikat trace nachvollziehen. Zum besseren Verständnis der Abarbeitungsreihenfolge kann der trace in einem Und-/Oder-Suchbaum dargestellt werden [Be86,
S. 112]. Die Wurzel dieses Baumes bildet die Anfrage an den Interpreter. Ausgehend
von dieser Wurzel bestimmen sich die Nachfolger dann jeweils als alle möglichen Fakten oder Rümpfe von Regeln, die mit der Wurzel unifizieren. Die einzelnen Verzweigungen werden, da verschiedene Fakten und Regeln als voneinander unabhängiges
Wissen gesehen werden müssen, mit oder verknüpft werden. Hat eine Regel mehr
als eine Voraussetzung im Rumpf, so werden diese im Baum mit und verknüpft. Die
Blätter des Baumes stellen Fakten aus der Wissensbasis dar.
Die Beweissuche einer Anfrage geschieht durch Traversierung des Baumes. Um eine
Anfrage zu beweisen, müssen dann alle Nachfolger eines Und-Knotens und einer der
15
Kapitel 3: Funktionsweise des Interpreters
Nachfolger eines Oder-Knotens erfolgreich abgearbeitet werden. Scheitert der Beweis eines Teilziels, so wird zum letzten Oder-Knoten (Choicepoint), der noch nicht
bearbeitete Nachfolger aufweist, zurückgegangen (Backtracking) [Be86, S. 115]. Bei
einem Backtracking-Schritt werden Variableninstanziierungen, die bis zum Choicepoint vorgenommen wurden, rückgängig gemacht.
Der zur Anfrage ?- vorfahre(hermann,florian). gehörende Suchbaum ergibt sich
aus dem trace (vgl. Anhang, Seite 24). In den Knoten des Baumes lassen sich die
jeweils noch zu beweisenden Anfragen erkennen, angewandte Regeln sind durch die
Ziffern an den Kanten dargestellt und die gestrichelte Linie zeigt die Abarbeitungsreihenfolge.
vorfahre(hermann,florian)
X=hermann
Y=florian
X=hermann
Y=florian
ODER
4
3
elternteil(hermann,florian)
UND
ODER
1
vater(hermann,florian)
Z=reinhold
2
mutter(hermann,florian)
elternteil(Z,florian)
ODER
Z=reinhold
Legende zu den Regelnummern:
1: elternteil(X,Y) :- vater(X,Y).
2: elternteil(X,Y) :- mutter(X,Y).
3: vorfahre(X,Y) :- elternteil(X,Y).
4: vorfahre(X,Y) :- elternteil(Z,Y),vorfahre(X,Z).
Legende zu den Symbolen:
fail: Backtracking Schritt
exit: Teilziel erreicht
2
1
vater(reinhold,florian)
vorfahre(hermann,reinhold)
Z=doris
mutter(doris,florian)
3
elternteil(hermann,reinhold)
ODER
1
vater(reinhold,florian)
2
mutter(doris,florian)
Abbildung 3: Abarbeitung einer Anfrage dargestellt in einem Suchbaum
Der Suchbaum zeigt, dass die Abarbeitungsreihenfolge der Regeln von oben nach
unten und von links nach rechts einer Tiefensuche entspricht. Diese wird in Prolog in
Kombination mit Backtracking verwendet. Die Anfrage ist beweisbar, da im rechten
Teilbaum beide durch Und-verknüpfte Teilziele parallel erreicht werden können.
Der sogenannte Cut – ein nullstelliges Built-In-Prädikat mit dem Funktor ! – stellt
dem Programmierer ein Werkzeug zur Seite, das es ihm ermöglicht die Abarbeitungsreihenfolge des Interpreters dadurch zu steuern, dass Backtracking gezielt verhindert
wird [KS88, S. 120].
Der Programmierer beschränkt den Suchraum des Interpreters durch gezieltes Ab”
schneiden“ irrelevanter Teilbäume und kann somit die Effizienz von Programmen
steigern [Sch00, S. 152]. Eine andere Einsatzform von Cut erlaubt es dem Programmierer, nur exakt eine Lösung zu einem Problem ausgeben zu lassen und danach die
16
Kapitel 4: Prolog in der Praxis
Suche abzubrechen. Letztendlich kann mit Hilfe des Cut sogar das aus prozeduralen
Programmiersprachen bekannte if-then-else nachgebildet werden [Sch00, S. 152].
Aufgrund der Eigenschaften des Cut, dass er die Lösungssuche beeinflusst, wird er
in der Literatur kontrovers diskutiert. Auf der einen Seite ist es mit seiner Hilfe
möglich, die Effizienz der Auswertung zu steigern [Sch00, S. 152]. Auf der anderen
Seite wird er als Alptraum jedes Logikers“ [KS89, S. 142] bezeichnet, da er den
”
Prinzipien der logischen Programmierung Was statt Wie“ genau entgegenwirkt.
”
An dieser Stelle wird auf die genauere Darstellung der verschiedenen Möglichkeiten
des Cut verzichtet, da es sich nicht um eine für Prolog wesentliche Komponente
handelt. Es sei hierzu jedoch auf [Be86, S. 103ff.] und [KS88, S. 120 ff.] verwiesen.
4
4.1
Prolog in der Praxis
Expertensysteme
Nachdem die wesentlichen Aspekte der Programmiersprache Prolog vorgestellt wurden, kann jetzt auf die praktische Anwendung in Expertensystemen eingegangen
werden. Expertensysteme, die auch als wissensbasierte Systeme bezeichnet werden
[KS88, S. 240], sollen in einem gewissen Rahmen den menschlichen Experten ersetzen können. Dies ist immer dann nötig, wenn es nur eine sehr geringe Anzahl an
Experten in dem entsprechenden Fachgebiet gibt, die Komplexität der zu beachtenden Vorschriften besonders hoch ist (Beispiel: Behörden) oder das Spezialwissen
nur sehr selten benötigt wird (Behandlung von Ausfallsituationen) [Sa89, S. 24 f.].
Aus diesen Umständen ergibt sich, dass ein Expertensystem ähnliche Fähigkeiten
aufweisen muss, die auch ein menschlicher Experte besitzt. Es ist also zunächst eine genauere Analyse des menschlichen Experten von Nöten, bevor anschließend die
einzelnen Fähigkeiten in Bezug zu Prolog gesetzt werden können:
Als Experte wird i. A. eine Person bezeichnet, die umfangreiches Wissen
in einem bestimmten Fachgebiet besitzt und dieses Wissen kompetent
anwenden und auch erläutern kann. Das Wissen wurde durch Talent,
Übung und/oder langjährige Erfahrung gesammelt, wobei sich der Experte auch schnell neues Wissen aus externen Quellen aneignen kann. In
Problemsituationen steht der Experte in direkter Interaktion mit anderen Menschen. Er erfragt dabei problemrelevante Aspekte, um schließlich
das Problem lösen zu können (vgl. [KS88, S. 240], [Sa89]).
17
Kapitel 4: Prolog in der Praxis
Fasst man diese Fähigkeiten in einer schematischen Darstellung (vgl. [Be86, S. 26])zusammen, so ergeben sich verschiedene Komponenten, die ein Expertensystem aufweisen muss, um den Anforderungen nach obiger Definition zu genügen:
Benutzer
Expertensystem
Dialogkomponente
(Benutzerschnittstelle)
Wissensveränderungskomponente
Erklärungskomponente
Problemlösung
(Inferenzmechanismus)
Wissensbasis
(internes, externes, erfragtes Wissen)
Abbildung 4: Allgemeine Struktur eines Expertensystems
In Prolog kann durch das Konzept der Fakten und Regeln ein regelbasiertes Expertensystem aufgebaut werden. Die wichtigste Komponente dieses Systems stellt der
Inferenzmechanismus dar, da er die verschiedenen anderen Komponenten integrieren
und steuern muss. In Prolog wird diese Aufgabe durch den Interpreter übernommen,
so dass sich die Arbeitsweise als Tiefensuche in Kombination mit Backtracking charakterisieren lässt [CL90, S. 170].
Eng verknüpft mit dem Inferenzmechanismus ist die Repräsentation der verschiedenen Arten des Wissens – in Prolog Fakten und Regeln. Wichtig ist es, das erfragte
Wissen, welches erst im Rahmen der Interaktion mit dem Benutzer erlangt wird und
sich somit fall-spezifisch unterscheidet, von den zwei anderen Wissensarten zu abzugrenzen. Um erfragtes Wissen speichern zu können, unterstützt Prolog in diesem
Zusammenhang das dynamische Hinzufügen und Löschen von Fakten und Regeln
in die Wissensbasis zur Laufzeit. Dies wird durch die Built-In-Prädikate asserta( ).
und retract( ). und einige Abwandlungen von diesen realisiert [KS88, S. 179]. Externes Wissen erlangt der Prolog-Interpreter aus anderen Programmen, die über
Schnittstellen angebunden sind. Die Schnittstellen sind, wie in der Einleitung dargelegt, jedoch zwischen den verschiedenen Prolog-Systemen sehr inhomogen und
lassen sich nur für den Einzelfall detaillierter beschreiben.
Die Benutzerschnittstelle sollte nach Auffassung von Kleine Büning und Schmittgen
nicht in Prolog selbst realisiert werden [KS88, S. 245]. Dies erscheint auch logisch,
da Prolog sich nur sehr bedingt dazu eignet grafische Elemente einzubinden, sodass
lediglich eine Interaktion mit dem Benutzer am Prompt verbliebe. Der heutige Nutzer ist hingegen grafische Oberflächen gewöhnt und würde eine solche Interaktion
ablehnen. Die Erklärungskomponente muss dem Benutzer über die Benutzerschnitt18
Kapitel 4: Prolog in der Praxis
stelle auf verständliche Art und Weise den Problemlösungsprozess deutlich machen
können, da das Expertensystem ansonsten nur geringe Akzeptanz finden würde.
Aus der allgemein gehaltenen Beschreibung der verschiedenen Komponenten und
der Realisierung geht hervor, dass Benutzerschnittstelle, Inferenzmechanismus und
die Repräsentation des Wissens unabhängig von der konkreten Problemstellung implementiert werden können. Die Architektur sieht eine strikte Trennung von Wissen
und Wissensverarbeitung vor. Da die problemspezifische Wissensbasis in solch ein
System eingepflegt werden muss, spricht man daher auch von leeren Schalen oder
Shells [KS88, S. 243].
Das Produkt TWAICE der Firma Nixdorf ist eine solche Expertensystem-Shell,
die auf Prolog aufsetzt. Der interessierte Leser findet eine genauere Beschreibung
in [Sa89, S. 135-159]. In [KS88, S. 245-274] findet sich die ausführlich erläuterte,
vollständige Implementierung eines Expertensystems anhand eines Autokauf-Beispiels.
4.2
Code-Beispiel: Send + More = Money
Nachfolgend ist ein Beispielprogramm zur Lösung der Gleichung SEND + MORE =
MONEY wiedergegeben, um einen Vergleich von Prolog mit anderen Programmier-
sprachen zu ermöglichen. Jeder Buchstabe soll dabei durch eine der Ziffern {0,...,9}
belegt werden, wobei jede Ziffer nur für einen Buchstaben verwendet und der Buchstabe M nicht durch die Ziffer Null belegt werden sollte.
Das hier vorgestellte Prolog-Programm implementiert einen Brute-Force-Algorithmus, der als Datenstruktur Listen benutzt. Die Liste der in der Gleichung vorkommenden Buchstaben wird mit allen Permutationen der Ziffern {0,...,9} instanziiert
(Zeile 5). Die Richtigkeit der Gleichung wird in Zeile 6 überprüft und ggf. wird die
Lösung für MONEY ausgegeben (Zeile 7).
Es sei darauf hingewiesen, dass die Prädikate perm(_,_). (Zeile 1, 2) und das
dafür benötigte Prädikat select(_,_,_). (Zeile 3, 4) lediglich aus Gründen der
Vollständigkeit mit angegeben wurden. In nahezu allen Implementierungen von Prolog liegt bereits ein Built-In-Prädikat zur Erzeugung von Permutationen vor.
Es folgt der Quellcode zur Wissensbasis:
1 perm ([] ,[]) .
2 perm ( Liste ,[ X | Perm ]) : - select (X , Liste , Rest ) , perm ( Rest , Perm ) .
3
select (X ,[ X | Rest ] , Rest ) .
4
select (X ,[ Kopf | Liste ] ,[ Kopf | Rest ]) : - select (X , Liste , Rest ) .
5
generiere (S ,E ,N ,D ,M ,O ,R , Y ) : - perm ([ S ,E ,N ,D ,M ,O ,R ,Y ,_ , _
] ,[1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,0]) .
19
Kapitel 5: Zusammenfassung und Fazit
6
gleichung (S ,E ,N ,D ,M ,O ,R , Y ) : - ( S *1000+ E *100+ N *10+ D *1) + ( M
*1000+ O *100+ R *10+ E *1) =:= ( M *10000+ O *1000+ N *100+ E *10+ Y *1) .
7
loese : - generiere (S ,E ,N ,D ,M ,O ,R , Y ) , gleichung (S ,E ,N ,D ,M ,O ,R ,
Y ) , not ( M =:=0) ,! , write ( M ) , write ( O ) , write ( N ) , write ( E ) , write
(Y).
Aufgerufen wird das Programm mit der Anfrage ?- loese. am Prompt. Der Interpreter bestimmt daraufhin ein mögliches Ergebnis und gibt dieses aus:
1 ? - loese .
10652
true .
Aus dem Ergebnis lassen sich die Belegungen für die verschiedenen Buchstaben
in MONEY ablesen. Auf Wunsch könnte natürlich auch die Belegung jedes einzelnen
Buchstaben durch Anpassung von Zeile 7 ausgegeben werden.
Es sei an dieser Stelle noch auf den Cut in Zeile 7 hingewiesen. Dieser verhindert,
dass das Ergebnis ein zweites Mal ausgegeben wird. Dieses würde dadurch geschehen,
dass es eine weitere Permutation der Ziffern {0,...,9} gibt, die lediglich die Positionen
der nicht benötigten Ziffern 3 und 4 ändert1 .
5
Zusammenfassung und Fazit
Nachdem innerhalb dieser Arbeit die Entstehungsgeschichte aus dem Ursprung in
der Logik, der Aufbau von Programmen und die Funktionsweise des Interpreters der
Programmiersprache Prolog erläutert sowie auch die typischen Anwendungsgebiete
herauskristallisiert wurden, sollen abschließend noch einmal auf Vorteile von Prolog
eingegangen und schließlich Gründe für das bisherige Scheitern identifiziert werden.
Durch die enge Verbindung der Programmiersprache zur Logik und damit zur Mathematik lassen sich im Gegensatz zu imperativen Programmiersprachen häufig Korrektheitsbeweise über Programme führen, so dass für kritische Anwendung in dieser
Hinsicht ein großer Vorteil besteht. Wie im Kapitel 4.1 zu Expertensystemen aufgezeigt, ist es in Prolog möglich den Quellcode, d. h. im Rahmen von Prolog die
Wissensbasis, dynamisch zur Laufzeit zu verändern, so dass es möglich ist PrologProgramme lernfähig zu gestalten. Diese Eigenschaft war und ist insbesondere im
Bereich der künstlichen Intelligenz eine wünschenswerte Eigenschaft einer Programmiersprache.
1
Gesamte Gleichung: 9567 + 1085 = 10652, die Ziffern 3 und 4 wurden also nicht benötigt
20
Kapitel 5: Zusammenfassung und Fazit
Prolog zeigt seine Stärken in logischen Problemstellungen und ist speziell für die
Anwendungsgebiete der künstlichen Intelligenz entwickelt worden, jedoch wurde der
Programmiersprache in den 1970er und 1980er Jahren durch Neuronale Netze ein
starker Konkurrent in diesem Bereich entgegen gestellt. Ein weiterer Punkt, der Prolog ins Hintertreffen geraten ließ, ist der Fakt, dass die Ausführungsgeschwindigkeit
im Vergleich zu Programmen in imperativen Sprachen meist geringer ist. Auch der
in Kapitel 3.4 vorgestellte Cut zur Effizienzsteigerung kann dieser Tatsache nicht
entscheidend entgegenwirken. Neben den bereits genannten Nachteilen eignet sich
Prolog zudem nicht sehr gut, um arithmetische Operationen, die Grundbestandteile
vieler Programme darstellen, auszuführen.
Bedauerlicherweise sind selbst die in Kapitel 1.2 genannten ISO-Standards noch
nicht in allen Prolog-Systemen umgesetzt, so dass weiterhin auf eine Konvergenz
zu warten bleibt. Als letzter Punkt seien die lange Zeit zueinander inkompatiblen
Prolog-Systeme, die für einen größeren Nutzerkreis sicherlich nicht förderlich waren,
angeführt.
Alle genannten Gründe leisteten ihren Beitrag dazu, dass das von der japanischen
Regierung 1982 mit einem Budget von 400 Millionen Dollar initiierte, international
beachtete Projekt zu den Rechnersystemen der 5. Generation“ 1992 für geschei”
tert erklärt wurde [FG92]. Während alle vorherigen Rechnergenerationen auf eine
Erhöhung der Anzahl der logischen Bausteine in einer einzelnen CPU setzten, sollten
viele parallel arbeitende Prozessoren in Kombination mit einer logischen Programmiersprache (Prolog) die neue Architektur bestimmen.
Betrachtet man die Entwicklung der heutigen Rechnerarchitekturen in Richtung
Parallelität, so mag der Satz Either it [the Fifth Generation Project] was a failure,
”
or it was ahead of its time.“ 2 [FG00] zum Nachdenken anregen.
Als Fazit bleibt zu sagen, dass in Prolog die Möglichkeit besteht, Probleme aus speziellen Bereichen schneller, einfacher und eleganter lösen zu können. Es gibt jedoch
auch eine Vielzahl von Problemen, für die Prolog nur bedingt einsetzbar ist und in
denen andere Programmiersprachen ihre Stärken ausspielen können.
2
Entweder es [das 5. Generation Projekt] war ein Fehlschlag, oder es war seiner Zeit voraus.“
”
21
Kapitel A: Anhang
A
Anhang
A.1
Code-Beispiel Stammbaum
/* Welche Menschen gibt es in unserer " Welt "? */
mensch ( florian ) .
mensch ( thomas ) .
mensch ( reinhold ) .
5
mensch ( doris ) .
mensch ( hermann ) .
mensch ( katharina ) .
/* Die Beziehungen innerhalb der Familie väterlicherseits .
vater ( reinhold , florian ) sagt aus : Reinhold ist der Vater
von Florian . */
10
vater ( reinhold , florian ) .
vater ( reinhold , thomas ) .
vater ( hermann , reinhold ) .
/* Die Beziehungen innerhalb der Familie mü tterli cherse its .
mutter ( doris , florian ) sagt aus : Doris ist die Mutter von
Florian . */
15
mutter ( doris , florian ) .
mutter ( doris , thomas ) .
mutter ( katharina , reinhold ) .
/* Defintion von Eltern : X ist ein Elternteil von Y , wenn es
entweder ein X gibt , sodass X Vater von Y ist oder es ein
X gibt , sodass X Mutter von Y ist . */
20
elternteil (X , Y ) : - vater (X , Y ) .
elternteil (X , Y ) : - mutter (X , Y ) .
/* Defintion von Vorfahren : X ist ein Vorfahre von Y , wenn er
entweder ein direkter Elternteil von Y ist , oder es gibt
einen Elternteil Z von Y , der selbst widerum X als
Vorfahren hat . */
25
vorfahre (X , Y ) : - elternteil (X , Y ) .
vorfahre (X , Y ) : - elternteil (Z , Y ) , vorfahre (X , Z ) .
22
Kapitel A: Anhang
A.2
Wahrheitstabelle zur Resolutionsprüfung
Wahrheitstabelle zur Formel ¬a ∧ e ∧ c ∧ (d ∨ ¬e) ∧ (b ∨ ¬c ∨ ¬d) ∧ (a ∨ ¬b):
a
b
c
d
e
¬a
e
c
(d ∨ ¬e)
(b ∨ ¬c ∨ ¬d)
(a ∨ ¬b)
Gesamt
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
1
1
1
0
0
1
1
0
0
0
0
1
0
1
0
0
1
1
1
0
0
0
0
1
1
1
1
0
1
1
1
0
0
0
1
0
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
0
1
0
0
0
1
1
1
1
1
1
1
0
1
0
0
1
0
0
0
1
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
1
0
1
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
1
1
0
1
0
1
1
1
0
0
0
1
1
1
1
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
1
0
0
1
1
0
1
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
1
0
1
0
1
1
1
0
1
0
1
0
0
0
0
1
1
1
1
0
1
0
1
0
1
0
1
1
0
1
1
0
1
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
1
0
1
1
1
0
1
0
1
1
0
0
0
0
0
0
1
1
1
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
1
0
0
0
0
1
1
1
0
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
0
0
0
0
1
1
1
1
0
1
1
1
0
1
0
1
1
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
0
23
Kapitel A: Anhang
A.3
Abarbeitungsreihenfolge von Anfragen an den PrologInterpreter (trace)
Hinweis zu den Angaben Call, Redo, Exit und Fail:
• Call: Beginn eines neuen Teilbeweises.
• Redo: Wiederholung eines Teilbeweises mit anderer Variableninstanziierung.
• Exit: Erfolgreiches Beenden eines Teilbeweises.
• Fail: Scheitern eines Teilbeweises.
Des Weiteren sei innerhalb des trace auf das _L165, welches die interne Repräsentation
einer Variablen darstellt, und das creep (zu Deutsch: schleichen, kriechen), welches
den Programmfluss widerspiegelt, hingewiesen.
? - trace , vorfahre ( hermann , florian ) .
Call : (9) vorfahre ( hermann , florian ) ? creep
Call : (10) elternteil ( hermann , florian ) ? creep
Call : (11) vater ( hermann , florian ) ? creep
Fail : (11) vater ( hermann , florian ) ? creep
Redo : (10) elternteil ( hermann , florian ) ? creep
Call : (11) mutter ( hermann , florian ) ? creep
Fail : (11) mutter ( hermann , florian ) ? creep
Redo : (9) vorfahre ( hermann , florian ) ? creep
Call : (10) elternteil ( _L165 , florian ) ? creep
Call : (11) vater ( _L165 , florian ) ? creep
Exit : (11) vater ( reinhold , florian ) ? creep
Exit : (10) elternteil ( reinhold , florian ) ? creep
Call : (10) vorfahre ( hermann , reinhold ) ? creep
Call : (11) elternteil ( hermann , reinhold ) ? creep
Call : (12) vater ( hermann , reinhold ) ? creep
Exit : (12) vater ( hermann , reinhold ) ? creep
Exit : (11) elternteil ( hermann , reinhold ) ? creep
Exit : (10) vorfahre ( hermann , reinhold ) ? creep
Exit : (9) vorfahre ( hermann , florian ) ? creep
true .
24
Literaturverzeichnis
Literatur
[Be86] F. Belli: Einführung in die logische Programmierung mit Prolog, Bibliografisches Institut Mannheim, 1986.
[Be88] F. Belli: Prolog-Systeme in der Praxis, Mannheim, 1988.
[Bo87] Wilhelm Bolkart: Programmiersprachen der 4. Und 5. Generation, Hamburg,
1987.
[CM03] William F. Clocksin, Christopher S. Mellish: Programming in Prolog, Springer, 2003.
[CL90] R. Cordes, R. Kruse, H. Langendörfer, H. Rust: Prolog: Eine methodische
Einführung, Vieweg, 1990.
[KS88] Hans Kleine Büning, Stefan Schmittgen: Prolog: Grundlagen und Anwendungen, Teubner, 1988.
[KS89] Esther König, Roland Seiffert: Grundkurs Prolog fur Linguisten, UTB Linguistik, 1989.
[Sch00] Uwe Schöning: Logik für Informatiker, Spektrum, 2000.
[Sa89] Dr. Stuart E. Savory: Expertensysteme: Nutzen für Ihr Unternehmen, R.
Oldenbourg Verlag, 1989.
[IF08] Applikationen, die auf IF/Prolog basieren
URL: http://www.ifcomputer.de/Consulting/home de.html
Abrufdatum: 04. März 2009.
[ISO95] International Organization for Standardization
URL: http://www.iso.org/iso/iso catalogue/catalogue tc/cataloguedetail.htm?csnumber=21413
Abrufdatum: 04. März 2009.
Der Originaltext zum ISO Standard ist nicht frei zugänglich.
Einen Überblick von J.P.E. Hodgson über den ISO Standard (Prolog: The ISO
Standard Documents) gibt es hier:
URL: http://pauillac.inria.fr/ deransar/prolog/docs.html
Abrufdatum: 04. März 2009.
25
Literaturverzeichnis
[ISO00] International Organization for Standardization
URL: http://www.iso.org/iso/iso catalogue/catalogue tc/catalogue detail.htm?csnumber=20775
Abrufdatum: 04. März 2009.
Der Originaltext zum ISO Standard ist nicht frei zugänglich.
[FG00] Fifth Generation Project
URL: http://encyclopedia.vbxml.net/Fifth Generation Computer
Abrufdatum: 04. März 2009.
[FG92] New York Times, 05.06.1992
URL: http://query.nytimes.com/gst/fullpage.html?res=9E0CE1DB1031F936A35755C0A964958260
Abrufdatum: 04. März 2009.
26