Prolog und lineare Resolution

von: Christian Brüser

Inhaltsverzeichnis

Einleitung  3

Kapitel 1: Allgemeine Informationen über Prolog  4

1.1 Geschichtliches  4
1.2 Einsatzgebiete von Prolog 5
1.3 Was unterscheidet Prolog von anderen Programmiersprachen?  5

Kapitel 2: Aufbau eines Prolog Programms 6

2.1 Fakten 6
2.2 Regeln  8
2.3 Fragen  9

Kapitel 3: Die Lösungssuche in Prolog  10

3.1 SLD Resolution  10
3.2 SLD-Suchbäume, Depth-First-Verfahren und Backtracking 12

Schlussbemerkung  17

Literaturverzeichnis 18

Bilderverzeichnis 18

Einleitung

Diese Ausarbeitung beschäftigt sich mit der Programmiersprache Prolog und der linearen Resolution. Das erste Kapitel soll dem Leser, dem Prolog möglicherweise noch völlig unbekannt ist, die Sprache zunächst kurz vorstellen. Dazu wird auf die geschichtliche Entwicklung, sowie die heutigen Einsatzgebiete eingegangen und es wird versucht, Prolog gegenüber (herkömmlichen) imperativen Programmiersprachen abzugrenzen, indem die Unterschiede zwischen imperativem und deklarativem Programmierstil erläutert werden. Das zweite Kapitel beschäftigt sich mit dem grundlegenden Aufbau von Prolog-Programmen. Ziel ist es, die Konstrukte zur formalen Problembeschreibung in Prolog einzuführen und ein Gefühl dafür zu schaffen, was Programmieren in Prolog beinhaltet. Auf die Syntax von Fakten, Regeln und Anfragen wird dabei sehr genau eingegangen. Im dritten Teil wird Prologs Auswertungsalgorithmus dargestellt und auf die Resolution zurückgeführt. An Beispielen wird die Lösungssuche verdeutlicht und in der Programmiersprache eingesetzte Konzepte wie das Depth-First-Verfahren und Backtracking erläutert. Voraussetzung zum Verständnis dieser Ausarbeitung sind Grundlagen der Aussagen- und Prädikatenlogik, sowie der aussagenlogischen Resolution wie sie zum Beispiel in [4] zu finden sind.

Kapitel 1: Allgemeine Informationen über Prolog

1.1 Geschichtliches

Die Geschichte der logischen Programmierung begann Anfang der 70er Jahre. Eine Marseiller Forschergruppe unter der Leitung des französischen Wissenschaftlers und Informatikers Alain Colmerauer entwickelte 1972 die erste Implementierung eines Prolog-Systems. Zwei Jahre später wurden die zugrunde liegenden Theorien von Rober Kowalski begründet. Mitte der 70er Jahre wurde versucht, die Programmiersprache weltweit zu verbreiten, indem man sie an verschiedene Universitäten in der ganzen Welt verschickte. Doch dies brachte zunächst keinen Erfolg. Ganz im Gegenteil – die Verbreitung kam stark ins Stocken, so dass Prolog in den frühen Achtziger Jahren beinahe fast ganz verschwunden wäre. Dies lag unter anderem daran, dass sich in den USA LISP in den Bereichen der KI bereits so stark etabliert hatte, dass man Prolog wahrscheinlich unterschätzte.

Doch im Rahmen des „Fifth Generation Project“, einem japanischen Forschungsprojekt, bei dem es um wirtschaftliche Interessen ging und auch darum, dem wachsenden amerikanischen Computermarkt etwas entgegenzusetzen, wurde die Programmiersprache wieder aufgegriffen. Ziel war es, neue Rechner zu entwerfen, deren Hardware für die Logikverarbeitung vorbereitet sein sollte, und bei denen Prolog als „Maschinensprache des Logikprozessors“ eingesetzt werden sollte. Obwohl das Projekt scheiterte, erlangte Prolog dadurch jedoch den entscheidenden Durchbruch. Die Amerikaner behielten zwar weiterhin ihre Vormachtsstellung im Bereich der KI und auch LISP war in Übersee weiterhin die führende Sprache in diesem Bereich, jedoch in Europa und Japan war es fortan Prolog. Das neu geweckte Interesse führte dazu, dass immer neue Prolog-Versionen entwickelt wurden, und schließlich auch kommerzielle Prolog-Interpreter auf den Markt kamen. 1995 wurde Prolog sogar nach der ISO-Norm standardisiert und hat es bis heute geschafft, sich neben LISP als Hauptimplementierungssprache der künstlichen Intelligenz zu etablieren. Nun noch kurz zur Entstehung des Namens: Prolog entstand durch eine Idee, die der Ehefrau von Phillippe Roussels – ebenfalls ein Mitglied der Forschergruppe – gekommen war. Prolog sollte eine Abkürzung für „Programmation en Logique“ sein. Heutzutage findet man auch häufig die englische Übersetzung „Programming in Logic.“ Vgl. [1,2,3]

1.2 Einsatzgebiete von Prolog

Wie bereits in Kapitel 1.1 erwähnt, spielt Prolog im Bereich Künstliche Intelligenz eine große Rolle, allgemein lässt sich die Sprache für alle Anwendungen verwenden, die sich mit Symbolverarbeitung befassen. [3] führt einige Beispiele der heutigen Einsatzgebiete auf:

• Expertensysteme: Hierbei handelt es sich um Programme, die das Wissen eines Experten für ein bestimmtes Fachgebiet enthalten, z.B. Auswertung von Krankheitssymptomen
• Verarbeitung natürlicher Sprache:
• Parsing
• Übersetzung
• Textverstehen
• natürlichsprachliche Datenbankschnittstellen
• mechanisches Theorembeweisen: Beweisen von Theoremen eines Axiomensystems

1.3 Was unterscheidet Prolog von anderen Programmiersprachen?

Prolog verfolgt im Vergleich zu anderen Programmiersprachen eine andere Strategie um Probleme zu lösen. Der entscheidende Unterschied besteht darin, dass der Programmierer keinen Algorithmus angibt, wie ein bestimmtes Problem zu lösen ist, sondern lediglich das Problem in einer geeigneten Weise formuliert. Während ein imperativer Programmierstil bei herkömmlichen Programmiersprachen dadurch gekennzeichnet ist, dass eine Folge von Anweisungen angegeben werden muss (tue erst das, dann das,…, und dann das!) kommt bei Prolog der deklarative Programmierstil zum Einsatz, bei dem spezifiziert wird, aus welchen Teilproblemen ein vorliegendes Problem besteht, und wie diese untereinander in Beziehung stehen. Mit Hilfe dieser Angaben findet Prolog dann selbst die gesuchte Lösung, ohne dass der genaue Lösungsweg vom Programmierer erarbeitet werden muss. Vgl. [2,3]

Kapitel 2: Aufbau eines Prolog-Programms

[...]