Prolog (Programmiersprache)

Kernidee und Bedeutung

Prolog ist eine logische und deklarative Programmiersprache. Deklarativ bedeutet: Man beschreibt vor allem Wissen und Beziehungen, nicht Schritt für Schritt einen Ablauf. Prolog wurde Anfang der 1970er Jahre maßgeblich von Alain Colmerauer entwickelt; Philippe Roussell war Entwickler. Das Erscheinungsjahr ist 1972. Prolog gilt als wichtigste logische Programmiersprache. Der Name steht für „programmation en logique“, also „Programmieren in Logik“.

Prolog-Programme bestehen aus einer Wissensdatenbank. Deren Einträge heißen Fakten und Regeln. Der Benutzer stellt Anfragen an diese Wissensdatenbank. Der Prolog-Interpreter versucht dann systematisch, aus Fakten und Regeln eine Antwort abzuleiten. Ein positives Ergebnis bedeutet, dass die Anfrage logisch ableitbar ist. Ein negatives Ergebnis bedeutet nur, dass aus der vorhandenen Datenbasis keine Ableitung gefunden wurde. Das hängt mit der Closed world assumption zusammen: Nur das, was ausdrücklich bekannt oder aus Bekanntem folgerbar ist, gilt für das System als wahr.

Wichtige Implementierungen sind SICStus, SWI-Prolog, GNU Prolog, XSB und YAP-Prolog. Zu den Dialekten gehören ISO-Prolog, Edinburgh Prolog, BinProlog, Visual/Turbo Prolog und historisch micro-Prolog. Der Edinburgh-Dialekt wurde zum Quasistandard und 1995 Grundlage des ISO-Standards ISO/IEC 13211-1, auch ISO-Prolog genannt. Prolog ist schwach und dynamisch typisiert.

Fakten, Regeln und Anfragen

Ein typisches erstes Prolog-Programm ist keine Ausgabe wie „Hallo Welt“, sondern eine kleine Wissensdatenbank, zum Beispiel über einen Stammbaum. Ein Fakt wie mann(tobias). bedeutet: Tobias ist ein Mann. Ein Fakt wie vater(tobias, frank). bedeutet: Tobias ist der Vater von Frank.

Anfragen werden im Interpreter gestellt. Die Eingabeaufforderung ?- zeigt, dass eine Anfrage erwartet wird. Eine Anfrage wie mann(tobias). wird mit yes. oder true. beantwortet, wenn sie bewiesen werden kann. mann(heinrich). ergibt dagegen no. oder false., wenn über Heinrich kein passender Fakt und keine passende Regel vorhanden ist. Auch frau(heinrich). ergibt dann no., nicht weil bewiesen wäre, dass Heinrich keine Frau ist, sondern weil die Datenbasis keinen Beweis liefert.

Variablen beginnen in Prolog mit einem Großbuchstaben. Eine Anfrage wie frau(X). sucht Werte für X, mit denen die Aussage wahr wird. Wenn die Datenbasis frau(eva)., frau(daniela). und frau(ulrike). enthält, liefert Prolog diese Belegungen. Die Zuordnung einer Variablen zu einem passenden Wert heißt Unifikation.

Regeln beschreiben Folgerungen. Der Operator :- wird wie ein umgedrehter Implikationspfeil gelesen. Eine Regel grossvater(X, Y) :- vater(X, Z), vater(Z, Y). bedeutet: X ist Großvater von Y, wenn es ein Z gibt, sodass X Vater von Z ist und Z Vater von Y ist. Das Komma steht dabei für logisches Und, also eine Konjunktion. Der linke Teil einer Regel heißt Head oder Konsequenz. Mehrere Regeln mit gleicher Konsequenz wirken wie ein Oder: Die Konsequenz folgt, wenn mindestens eine der Regeln erfüllt ist.

Syntax und Datenstrukturen

Prolog verwendet logische Operatoren direkt in Anfragen und Regeln. Das logische Und wird durch ein Komma geschrieben, das logische Oder durch ein Semikolon. So ist true,true. wahr, true,false. falsch, true;false. wahr und false;false. falsch.

Für Vergleiche gibt es verschiedene Operatoren, die unterschiedliche Bedeutungen haben. == prüft, ob zwei Muster übereinstimmen, etwa anton == anton. \== prüft, ob Muster nicht übereinstimmen. Numerische Gleichheit wird mit =:= geprüft, zum Beispiel ist 3 =:= 1+2 wahr. Numerische Ungleichheit wird mit =\= geprüft. =< bedeutet kleiner oder gleich; <= ist dafür nicht zulässig. >= bedeutet größer oder gleich. Der Operator \= prüft, ob eine Unifikation unmöglich ist.

Prolog kennt die Grundrechenarten Addition +, Subtraktion -, Multiplikation *, Division / und Modulo mod. Eine Variable erhält mit is einen Wert. Anders als in imperativen Programmiersprachen können Variablenwerte in Prolog nicht überschrieben werden.

Listen sind in Prolog rekursive Datenstrukturen. Sie bestehen aus einem Kopf, dem Head, und einem Rest, dem Tail. Der Rest kann wiederum eine Liste sein. Beispiele sind [1, 2], ['one', 'two'], [1, 'two'] oder [1, 2, 3]. Zum Prüfen, ob ein Element in einer Liste vorkommt, wird häufig member verwendet. Die leere Liste wird mit [] geschrieben. Der Unterstrich _ ist die anonyme Variable: Sie erlaubt an einer Stelle jeden Wert, ohne ihn weiter zu benennen.

Rekursion, Listen und dynamische Datenbasis

Für die Prolog-Programmierung sind Rekursion und Listen besonders wichtig. Rekursion bedeutet, dass sich eine Regel mittelbar oder unmittelbar selbst verwendet. In vielen Programmiersprachen ist Rekursion nur eine Alternative zu Schleifen; in Prolog ist sie die einzige Möglichkeit, Schleifen zu erzeugen.

Eine allgemeine Vorfahr-Beziehung kann rekursiv beschrieben werden. Zunächst kann ein Elternteil dadurch definiert werden, dass jemand Mutter oder Vater einer Person ist. Dann gilt: X ist Vorfahr von Z, wenn X Elternteil von Z ist. Außerdem gilt: X ist Vorfahr von Z, wenn X Elternteil von Y ist und Y Vorfahr von Z ist. Damit kann Prolog auch über mehrere Generationen hinweg Beziehungen ableiten.

Listen sind nützlich, wenn die Anzahl von Elementen variabel ist. Eine Familie könnte zum Beispiel als familie(heinz, jutta, [peter,laura]). oder familie(karl, gertrud, []). dargestellt werden. Mit der Anfrage familie(X, _, []). werden alle Männer gesucht, bei denen die Kinderliste leer ist; im Beispiel wäre das X=karl.

Eine Besonderheit von Prolog ist, dass die vorhandene Datenbank während der Laufzeit erweitert oder gelöscht werden kann. Mit retract kann ein einzelnes passendes Element entfernt werden. retractall() löscht alle gleichen Elemente auf einmal. Mit asserta() wird ein Element oben in die Datenbank eingefügt, mit assertz() unten. Dadurch können spätere Anfragen andere Ergebnisse liefern als frühere, weil sich die Wissensdatenbank verändert hat.

Typische Anwendungen und Beispiele

Prolog eignet sich besonders für Probleme, die sich als Beziehungen, Bedingungen und Suche formulieren lassen. Ein Beispiel ist ein mathematisches Rätsel, bei dem die Buchstaben A bis H jeweils für eine Ziffer von 0 bis 9 stehen. In Prolog werden zunächst alle möglichen Belegungen durch eine Permutation erzeugt. Danach werden die Gleichungen des Rätsels in Prolog-Syntax notiert, etwa mit numerischen Vergleichen wie =:= und Wertzuweisungen mit is. Eine Lösungsregel verbindet die Bedingungen und gibt das gesuchte Ergebnis aus. Der Artikel betont daran, dass man nicht Schleifen programmieren muss, sondern vor allem Fakten, Bedingungen und das gewünschte Ergebnis beschreibt.

Ein weiteres Beispiel ist die Bearbeitung hierarchischer Strukturen wie SGML oder XML. Ein XML-Baum kann in Prolog als rekursive Liste von Elementen der Form element(TagName, Attribute, Kinder) dargestellt werden. Mit rekursiven Regeln kann ein Baum durchlaufen werden. So lassen sich Tags löschen oder nebeneinanderstehende Tags zusammenführen, indem Listen verarbeitet und Teilbäume neu aufgebaut werden.

Auch Planungssysteme lassen sich in Prolog ausdrücken. Ein Planungssystem sucht einen Weg von einem Ausgangszustand zu einem Zielzustand. Beim einfachsten Ansatz wird eine blinde Tiefensuche verwendet: Es wird ein anwendbarer Operator gesucht, der zu einem neuen zulässigen Zustand führt, der noch nicht besucht wurde. Für Straßennetze kann dies vereinfacht als Suche nach Straßenverbindungen formuliert werden. Bei realen Problemen reicht blinde Suche oft nicht aus. Dann nutzt man Breitensuche, Heuristiken, Best-first-Suche oder A*-Heuristik. Die A*-Heuristik ist die Summe aus bisher erbrachtem Aufwand und geschätztem Restaufwand zum Ziel, zum Beispiel zurückgelegte Fahrtstrecke plus Luftliniendistanz.

Das sogenannte Einsteins Rätsel, eine Version des Zebrarätsels, wird ebenfalls als Prolog-Beispiel dargestellt. Die angebliche Autorschaft Albert Einsteins und die Behauptung, nur 2 % der Weltbevölkerung könnten es lösen, sind nicht belegt. In Prolog werden die fünf Häuser als Listen mit Farbe, Nationalität, Getränk, Zigarettenmarke und Haustier beschrieben. Hilfsprädikate wie erstes, mittleres, links und neben formulieren räumliche Beziehungen. Die Hinweise des Rätsels werden dann als Bedingungen notiert, bis Prolog die gesuchte Person mit dem Fisch ableitet.

Logische Sicht und Einsatzgebiete

Aus logischer Sicht ist ein Prolog-Programm eine geordnete Liste von Horn-Klauseln. Horn-Klauseln sind eine eingeschränkte Form der Prädikatenlogik erster Ordnung. Wenn eine Anfrage gestellt wird, versucht Prolog, sie auf Grundlage der Datenbasis durch Resolution zu beweisen. Das Ergebnis einer Anfrage ist yes oder no. Ein Prolog-System kann deshalb als effizienter, aber eingeschränkter automatischer Theorembeweiser verstanden werden. Die eingebaute Suchstrategie ist Tiefensuche mit Backtracking. Backtracking bedeutet, dass Prolog bei einer Sackgasse zu früheren Entscheidungspunkten zurückkehrt und andere Möglichkeiten ausprobiert.

Für Parser bieten viele Prologsysteme Definite Clause Grammars. Das ist eine besser lesbare Schreibweise für Regeln, die der Beschreibung kontextfreier Sprachen ähnelt. Ein Präprozessor ergänzt Platzhalter und erzeugt daraus Prolog-Logik-Formeln. Durch zusätzliche Attribute können mit Definite Clause Grammars auch komplexere Sprachen als kontextfreie beschrieben werden.

In den 1980er Jahren spielte Prolog eine wichtige Rolle beim Bau von Expertensystemen. Heute wird die Sprache noch in der Computerlinguistik und in der Künstlichen Intelligenz verwendet. Sprachverarbeitungskomponenten des durch seinen Auftritt bei Jeopardy! bekannt gewordenen KI-Systems Watson sind in Prolog geschrieben. Außerdem gibt es kommerzielle Anwendungen im Systemmanagement, bei denen asynchrone Ereignisse mit Prolog oder darauf basierenden proprietären Erweiterungen verarbeitet werden. Ein Beispiel ist Tivoli Enterprise Console (TEC) von IBM, das auf IBM-Prolog basiert. Der 1986 in Japan von Sega veröffentlichte Sega AI Computer nutzte Prolog als ins ROM integrierte Programmiersprache, die sofort nach dem Einschalten verfügbar war.