Eine Einführung in das ECLiPSe System

Einführung in Prolog

• Geschichte der logischen Programmierung
• Programmierparadigmen
• Das Prinzip von Prolog
• Fakten
• Variablen
• Regeln
• Listenverarbeitung
• Arithmetik
• Arbeitsweise der Prolog Maschine

Die Geschichte der logischen Programmierung ist nicht sehr lang. In den frühen siebziger Jahren legten Green und Kowalski die theoretischen Grundlagen zur prozeduralen Interpretation logischer Formeln. Eine Gruppe um Alain Colmerauer in Marseille implementierte 1972 den ersten PROLOG-Interpreter in FORTRAN. Anfang der achziger Jahre waren die ersten kommerziellen Interpreter am Markt. Warren entwarf ein Modell einer abstrakten Maschine, die Prolog verarbeitete, auf deren Basis dann schnellere Übersetzer entwickelt wurden. Der weltweite Durchbruch gelang, als die Japaner Prolog als Sprache der Rechner der 5. Generation wählten.

Imperatives Programmieren

Es wird beschrieben, WIE ein bestimmtes Problem zu lösen ist.
Vertreter dieser Art sind z.B.:

• Assembler
• Basic
• C/C++
• Pascal
• ... und viele weitere

Funktionales Programmieren

Eine Programm besteht aus einer Folge von Funktionen.
Vertreter dieser Art sind z.B.:

• Scheme
• Haskell
• Logo
• Lisp

Deklaratives Programmieren

Es wird beschrieben, WAS das Problem ist, nicht wie es zu lösen ist. Die Lösung muß der Computer finden.
Vertreter dieser Art sind z.B.:

• PROLOG
• Goedel
• Escher
• Elf
• Mercury

Ein logisches Programm besteht aus Fakten und Regeln, die zusammen eine sogenannte Daten- oder Wissensbasis bilden. Die aktuelle Wissensbasis besteht aus allen Fakten und Regeln, die momentan konsultiert werden. Auf diese Wissensbasis wird mit Fragen zugegriffen. Die gestellten Fragen werden aufgrund der Wissensbasis durch die Prolog Interferenz Maschine entweder als beweisbar oder als nicht beweisbar ausgewertet. Fakten, Regeln und Anfragen sind die aus der Prädikatenlogik bekannten Horn Klauseln. Der Oberbegriff für Fakten und Regeln ist Klausel oder auch Prädikat.

Aus der Sicht von Prolog besteht die Welt aus Dingen, aus Eigenschaften von Dingen und aus Beziehungen zwischen Dingen. Ein kleines Beispiel erläutert dieses:

Fakten sind die einfachste Art von Klauseln. Ihre Bezeichnung charakterisiert ihre Verwendung, denn sie dienen in Prolog der Beschreibung von Tatsachen, die immer wahr sind. Die allgemeine Form eines Fakts ist:

funktor(Arg1,...,ArgN).

Wir greifen das in der obigen Tabelle angeführte Beispiel auf: mag(daniel,melanie)
mag ist hierbei der funktor und Daniel und Melanie die Argumente.
Hierbei ist zu berücksichtigen, daß die Reihenfolge der Argumente eine wichtige Rolle spielt. Es ist ein Unterschied, ob man mag(daniel,melanie) oder mag(melanie,daniel) schreibt. Das wird jedoch auch bei der umgangssprachlichen Betrachtung deutlich, schließlich ist es ein Unterschied, ob Melanie den Daniel mag oder Daniel die Melanie.

Die Anzahl der Argumente nennt man Stelligkeit. Übrigens sind auch nullstellige Klauseln möglich und häufig sinnvoll.

Beispiel

Wir definieren:	mag(daniel,melanie)
Eine Anfrage an den Prolog Interpreter:	?- mag(daniel,melanie)
Die Antwort:	Yes

Der Prolog Interpreter durchsucht die Wissensbasis und wird fündig. Die Frage ?- mag(Melanie,Daniel) wird hingegen mit No beantwortet. Das heißt aber nicht, daß diese Annahme nicht richtig ist, sondern nur, daß Prolog diese Annahme aufgrund der vorhandenen Wissensbasis nicht beweisen konnte.

Variablen beginnen mit einem Großbuchstaben oder einem Unterstrich. Die Verwendung von Variablen kann am besten an einem kurzen Beispiel deutlich gemacht werden:

Regeln drücken die Abhängigkeiten eines Faktums von anderen Fakten aus.

Eine Liste wird in Prolog als Aufzählung ihrer Elemente, mit Kommata getrennt und in eckige Klammern eingeschlossen, geschrieben.

[Element1,Element2,...,ElementN]

[Listenkopf | Restliste]

Auch in Prolog gibt es die Möglichkeit der Errechnung von Werten, wenn sie auch - durch die üblichen Einsatzgebiete dieser Sprache bedingt - weit weniger gebraucht wird als bei üblichen Programmieraufgaben. Als Beispiel soll die Prolog Implementation der Errechnung der Fakultät dienen, im Vergleich zu einer Pascal Implementation.

Pascal	Prolog
function fak(N : Integer) : Integer begin if N = 0 then fak := 1 else if N > 0 then fak := N* fak(N-1); end;	fak(0,1). fak(N,X) :- N >0, M is N-1, fak(M,X), N is N*Y.

Der Operator is ist der arithmetische Auswertungsoperator. Für seine Operanden gelten strenge Einschränkungen.
In Ergebnis is NumerischeStruktur darf Numerische Struktur nur die arithmetischen Operatoren +,-,*,/ enthalten. Sie haben ihre übliche Bedeutung.

Prolog arbeitet mit einem speziellen Resolutionsverfahren, das unter der Abkürzung SLD-Resolution (Linear resolution with Selection for Definite clauses) bekannt ist. Um einen Klauselkopf zu beweisen, müssen alle Elemente des Klauselkörpers, die Teilziele, bewiesen werden. Dies geschieht in der Reihenfolge des Auftretens von links nach rechts.
Es handelt sich um eine Lösungssuche nach dem Depth-First Suchverfahren. Eine graphische Darstellung des Beweisvorganges ist der Suchbaum.

Beispiel

Wissensbasis:

arbeitet_in(meier, raum1).
arbeitet_in(mueller, raum1).
arbeitet_in(otto, raum2).
telefon_existiert(raum2).

anrufbar(P) :- arbeitet_in(P,R), telefon_existiert(R).


Anfrage

?- anrufbar(Wer).

Suchbaum



Der Suchbaum wird von oben nach unten durchlaufen. Gerät der Suchprozeß in eine Sackgasse(false), so wird zurück nach oben gegangen und ein alternativer Weg gesucht. Dieses Zurückgehen im Suchbaum heißt backtracking.