Prolog (Programmiersprache)
# Prolog (Programmiersprache)

Prolog (vom Französischen: programmation en logique, dt.: „Programmieren in Logik“) ist eine Programmiersprache, die Anfang der 1970er-Jahre maßgeblich von dem französischen Informatiker Alain Colmerauer entwickelt wurde und ein deklaratives Programmieren ermöglicht. Sie gilt als die wichtigste logische Programmiersprache.
Erste Implementierungen wichen in ihrer Syntax stark voneinander ab, aber der Edinburgh-Dialekt setzte sich bald als Quasistandard durch. Er war jedoch nicht formal definiert, bis er 1995 zur Grundlage eines ISO-Standards wurde (ISO/IEC 13211-1), der auch ISO-Prolog genannt wird.
Der erste Prolog-Interpreter wurde in Marseille in ALGOL W realisiert. Der erste Ansatz für einen Compiler stammte von David H. D. Warren aus Edinburgh. Dieser hatte als Zielsprache die des Logik-Prozessors Warren’s Abstract Machine und erlaubte deshalb weder dynamische Änderungen noch einen Anschluss rücksetzbarer Prädikate in anderen Programmiersprachen. Der erste voll nutzbare Compiler, der beides erlaubte, wurde von Preben Folkjaer und Christian Pichler in München entwickelt. Er verwandte einen anderen, von der TU Wien stammenden, Zwischencode, der inkrementell kompiliert wurde; wurden Prädikate verändert, wurde das Kompilat gelöscht und beim nächsten Aufruf neu kompiliert.

## Grundprinzip

Prolog-Programme bestehen aus einer Wissensdatenbank, deren Einträge sich Fakten und Regeln nennen. Der Benutzer formuliert Anfragen an diese Wissensdatenbank. Der Prolog-Interpreter benutzt die Fakten und Regeln, um systematisch eine Antwort zu finden. Ein positives Resultat bedeutet, dass die Anfrage logisch ableitbar ist. Ein negatives Resultat bedeutet nur, dass aufgrund der Datenbasis keine Ableitung gefunden werden kann. Dies hängt eng mit der Closed world assumption zusammen (siehe unten).
Das typische erste Programm in Prolog ist nicht wie in prozeduralen Programmiersprachen ein Hallo-Welt-Beispiel, sondern eine Wissensdatenbank mit Stammbauminformationen.
Folgendes Beispiel repräsentiert den Stammbaum einer kleinen Familie. Das erste Faktum in Form einer Aussage mann(tobias). liest sich als: Tobias ist ein Mann. vater(tobias, frank). definiert das Faktum: Tobias ist der Vater von Frank. Für Hinweise zum Laden von Prolog Texten siehe entsprechenden Abschnitt:
In einem Prolog-Interpreter können nun interaktiv Anfragen an die Datenbasis gestellt werden. Das Ausführen eines Prolog-Programms bedeutet immer das Stellen einer Anfrage. Das System antwortet entweder mit yes./true. oder no./false., abhängig davon, ob die Anfrage bewiesen werden konnte. Der Interpreter signalisiert mit der Eingabeaufforderung ?-, dass er eine Anfrage erwartet:
Eine Anfrage mit einer Variablen liefert als Antwort zusätzlich Belegungen, mit denen die Anfrage wahr wird. Man nennt eine solche Variablenbelegung Unifikation und sagt, die Variable wird mit diesem Wert unifiziert. Variablen sind in Prolog Token, die mit einem Großbuchstaben beginnen:
no ist die Antwort auf die um die vorher ausgegebenen Antworten reduzierte Faktenliste.
Der Interpreter liefert nur positive Antworten auf Anfragen, die explizit definiert oder folgerbar sind (Closed world assumption). So liegen etwa über heinrich keinerlei Informationen in der Datenbasis:
Zusätzlich zu Fakten lassen sich in Prolog Regeln formulieren. Der Regeloperator :- ist dabei wie ein umgedrehter Implikationspfeil zu lesen. Beispiel:
Die Regel besagt: X ist Großvater von Y, wenn es ein Z gibt, sodass X Vater von Z ist und Z Vater von Y. Damit ist der Großvater väterlicherseits definiert. Eine zweite Regel für den Großvater mütterlicherseits sieht so aus:
Der Operator , in dieser Regel definiert eine Konjunktion und wird und gesprochen. Der Term links vom Implikationsoperator nennt sich auch Head oder Konsequenz. Haben zwei Regeln (wie oben) die gleiche Konsequenz, folgt diese, wenn mindestens in einer Regel die Vorbedingung erfüllt ist (Disjunktion).
Durch die Definition von Regeln können auch Fakten geschlossen werden, die nicht explizit in der Datenbasis stehen:

## Syntax
### Boolesche Algebra

Das logische Und wird durch ein Komma dargestellt:
Das logische Oder wird durch ein Semikolon dargestellt:

### Arithmetik

Prolog kennt die Grundrechenarten, also Addition +, Subtraktion -, Multiplikation *, Division / und Modulo mod. Die Zuweisung eines Wertes zu einer Variable erfolgt mit dem Schlüsselwort is. Im Gegensatz zu imperativen Programmiersprachen können in Prolog Variablenwerte nicht überschrieben werden.

### Listen

Listen sind rekursive Datenstrukturen bestehend aus einem Kopf (Head) und einem Rest (Tail). Der Rest kann hierbei wieder aus Listen bestehen.
Um zu prüfen ob ein bestimmtes Element in einer Liste enthalten ist, wird die vordefinierte Funktion member verwendet:

### Laden von Prolog-Texten

Ein Prolog-Text kann direkt über die Konsole eingegeben werden. Dazu kann man auf der Eingabezeile [user] tippen. Die Eingabe der Klauseln muss mit einem Dateienendezeichen abgeschlossen werden (^D oder ^Z je nach Plattform):
Alternativ kann ein Prolog-Text in einer Datei gespeichert werden und z. B. mit dem Prädikat consult geladen werden. Das Prädikat nimmt einen physischen Pfad zu einem Prolog-Text entgegen:

## Weitere Techniken

Entscheidend für die Prolog-Programmierung sind die Techniken der Rekursion und die Nutzung von Listen.
Ist die Rekursion in den meisten Programmiersprachen nur eine zusätzliche Variante zur Iteration, ist sie bei der Prolog-Programmierung die einzige Möglichkeit, Schleifen zu produzieren. Benötigt man in obigem Beispiel eine allgemeine Vorfahr-Relation, wird das wie folgt realisiert („;“ zeigt in der Klausel die Disjunktion bzw. das logische „oder“):
Dies lässt sich wie folgt lesen: X ist ein Vorfahr von Z, wenn X Elternteil von Z ist (Regel 1) oder es ein Y gibt, das Vorfahr von Z ist und gleichzeitig X Elternteil von Y (Regel 2) (Es wurde hier elternteil statt mutter oder vater verwendet.)
Auch Listen sind ein entscheidender Bestandteil von Prolog. Die meisten Prolog-Implementationen bringen dafür viele Basisfunktionen mit („concat“ = Anhängen von Werten, „count“ = Anzahl der Werte etc.), die sich aber auch alle selbst definieren lassen. In einer gedachten Familienstruktur muss die Anzahl der Kinder ja variabel sein. Folgendes wäre denkbar:
Dann ließen sich z. B. mit einer Abfrage alle Männer ohne Kinder anzeigen:
Dabei ist X die Variable, deren verschiedene Werte ausgegeben werden sollen. Der Unterstrich _ ist in Prolog die anonyme Variable, wodurch Prolog veranlasst wird hier jeden Wert zuzulassen. Die eckigen Klammern stehen für die leere Liste, welche die nicht vorhandenen Kinder repräsentiert.
Eine weitere Eigenschaft und Besonderheit gegenüber anderen Programmiersprachen ist, dass Prolog in der Lage ist, während der Laufzeit seine vorhandene Datenbank zu erweitern oder zu löschen. Ein Beispiel für das Löschen eines einzelnen Elements:
Die Abfrage:
ergibt (anfänglich) ganz normal:
Die Abfrage:
würde beim ersten Mal:
beim zweiten Mal nur noch:
liefern, da die Informationen:
aus der Datenbank gelöscht wurden. Auch ?- auto(bmw,X) liefert jetzt nur noch No. Zum Löschen aller gleichen Elemente (also z. B. auto) auf einmal benutzt man retractall, zum Ausgeben asserta (oben in der Datenbank) und assertz (unten in der Datenbank).

## Beispiele
### Lösen eines mathematischen Rätsels

A bis H stehen jeweils für eine Ziffer 0 bis 9, wobei nicht klar ist, welche Ziffer welchem Buchstaben entspricht. Gesucht ist die Zahl, die bei den Fragezeichen stehen muss. Dieses Problem ist in Prolog sehr einfach zu lösen. Man schreibt zunächst eine Regel, die bewirkt, dass A bis H später mit allen möglichen Kombinationen von 0 bis 9 belegt werden (Permutation):
Nun müssen nur die fünf entstehenden Gleichungen (ABB – CD = EED, FD + EF = CE, ABB – FD = EGD, CD – EF = FH und EED * CE = EGD * FH = X) in Prolog-Syntax geschrieben werden:
Interessiert nur X, wird eine Lösungsregel angelegt, die alles zusammenführt und X ausgibt:
Wird nun die Abfrage loesung. eingegeben, wird die Lösung ausgegeben. Wie man sieht, benötigt man zur Lösung dieses Problems fast keine Programmierkenntnisse über Schleifen oder ähnliches, sondern gibt nur die Fakten ein und welches Ergebnis man benötigt. Prolog steht in der Abstraktionshierarchie aus genau diesem Grund über imperativen und objektorientierten Sprachen.

### Bearbeitung hierarchischer Strukturen

Eine häufig gestellte Aufgabe an Programmiersprachen ist die Verarbeitung hierarchischer Strukturen, wie z. B. SGML oder XML. Insbesondere für XML bildet Prolog eine sehr wirkungsvolle und ausdrucksstarke Alternative zu der verbreitetsten Verarbeitungssprache XSLT.
Ein typischer XML-Baum wie
wird unter Prolog als rekursive Liste von Elementen element(TagName, Attribute, Kinder) dargestellt.
Ein sehr einfaches Paradigma (untere drei Klauseln) erlaubt es, jeden Baum rekursiv zu durchlaufen. Folgende Beispiele löschen (oberste Klausel mit delete) und konkatenieren (zweite Klausel von oben mit concat) bestimmte Tags. Der erste Unifikator ist die Operation (delete oder concat), der zweite die zu bearbeitende Struktur, der dritte das spezifizierte Tag, der vierte der Ergebnisbaum. append ist ein Befehl zum Konkatenieren von Listen.
Stößt der Backtracker bei der Operation delete auf ein Tag, das wie das zu löschende heißt, so wird dieses entfernt und bei den Nachbarn weitergesucht. Ein entsprechender Aufruf ist z. B. transform(delete, Tree, autor, ResTree)., der alle Autoren entfernt.
Ähnlich können durch transform(concat, Tree, paragraph, ResTree). alle nebeneinanderstehenden Paragraphen miteinander verschmolzen werden. Dazu werden zunächst deren Inhalte konkateniert, daraus eine neue Paragraphstruktur erzeugt und diese weiterverarbeitet.

### Planungssysteme

Planungssysteme suchen eine Möglichkeit, von einem Ausgangszustand in einen gewünschten Zielzustand zu gelangen. Sie lassen sich für die Suche von Straßen- oder Verkehrsverbindungen, aber auch für allgemeinere Problemstellungen einsetzen. Zunächst der allgemeinste Ansatz für eine blinde Tiefensuche (d. h., es ist unbekannt, ob der einzelne Schritt auch näher zum Ziel führt):
Nur die Prädikate operator, anwendbar, fuehrt_zu und zulaessig sowie die Beschreibung eines Zustands sind problemspezifisch zu formulieren. Aufgerufen wird das Prädikat mit einer Zustandsliste, die den Anfangszustand enthält.
Abhängig vom Problemtyp lässt sich einiges vereinfachen und/oder weglassen; für eine Wegesuche in einem Straßennetz ergibt sich z. B.
Bei realen Problemen führt eine blinde Suche selten zum Ziel; man benutzt eine Breitensuche, bei der alle vom Start aus erreichbaren neuen Zustände ermittelt, mit einer Heuristikfunktion bewertet und nur der beste (Heuristische Suche) oder eine sortierte Liste der besten (Best-first-Suche) weiterverfolgt werden. (Die einfache heuristische Suche kann dazu führen, dass nicht immer die optimale Lösung gefunden wird, da bestimmte Lösungsschritte, die fälschlicherweise als ungünstig aussortiert wurden, sich als bessere Lösung ergeben würden.) Die Kunst liegt in der richtigen problemspezifischen Formulierung der Heuristikfunktion. In vielen Fällen hilft die A*-Heuristik, das ist die Summe aus bisher erbrachtem Aufwand und geschätztem Restaufwand zum Ziel (z. B. zurückgelegte Fahrtstrecke + Luftliniendistanz zum Zielort):
Jedes Element von BewerteteListe hat die Struktur [Heuristikwert,gesamte Fahrtstrecke,Ort]; zur Berechnung der A-Heuristik sind die bisherige Strecke, der letzte Ort und der Zielort (Luftlinie) erforderlich.

### Einsteins Rätsel

Dies ist eine Version des Zebrarätsels. Es wurde angeblich von Albert Einstein im 19. Jahrhundert verfasst. Einstein wird oft der Vermerk zugeschrieben, nur 2 % der Weltbevölkerung seien im Stande, das Rätsel zu lösen. Es existiert jedoch kein Hinweis auf jedwede Autorenschaft. Hier soll es ein Beispiel für ein Problem darstellen, das mit Prolog lösbar ist.
* Es gibt fünf Häuser mit je einer anderen Farbe.
* In jedem Haus wohnt eine Person anderer Nationalität.
* Jeder Hausbewohner bevorzugt ein bestimmtes Getränk, raucht eine bestimmte Zigarettenmarke und hält ein bestimmtes Haustier.
* Keine der fünf Personen trinkt das gleiche Getränk, raucht die gleichen Zigaretten oder hält das gleiche Tier wie seine Nachbarn.
Frage: Wem gehört der Fisch?
Hinweise:
* Der Brite lebt im roten Haus.
* Der Schwede hält einen Hund.
* Der Däne trinkt gern Tee.
* Das grüne Haus steht direkt links neben dem weißen Haus.
* Der Besitzer des grünen Hauses trinkt Kaffee.
* Die Person, die Pall Mall raucht, hält einen Vogel.
* Der Mann, der im mittleren Haus wohnt, trinkt Milch.
* Der Besitzer des gelben Hauses raucht Dunhill.
* Der Norweger wohnt im ersten Haus.
* Der Marlboro-Raucher wohnt neben dem, der eine Katze hält.
* Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht.
* Der Winfield-Raucher trinkt gern Bier.
* Der Norweger wohnt neben dem blauen Haus.
* Der Deutsche raucht Rothmans.
* Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt.
Lösung:
Jedes Haus ist eine Liste der Form [Farbe, Nationalität, Getränk, Zigarettenmarke, Haustier].
Zuerst vier einfache Hilfsprädikate zur Listenbearbeitung:
Lösungsprädikat:

## Definite Clause Grammar

Um Regeln für Parser zu schreiben, haben die meisten Prologsysteme einen Präprozessor implementiert. Er erlaubt es, die Regeln in einer besser lesbaren Form zu notieren, die in der Form den Regeln entsprechen, die verwendet wird, um eine kontextfreie Sprache zu beschreiben. Der Präprozessor ergänzt Platzhalter und erzeugt die oben erwähnten Prolog-Logik-Formeln. Durch Übergabe weiterer Attribute ist es möglich, mit Definite Clause Grammars auch komplexere Sprachen als die kontextfreien zu beschreiben.

## Prolog aus logischer Sicht

Ein Prolog-Programm ist eine geordnete Liste so genannter Horn-Klauseln, einer eingeschränkten Form der Prädikatenlogik erster Ordnung. Stellt man dem System eine Anfrage (Query), versucht es, diese auf der Grundlage dieser Datenbasis mittels Resolution zu beweisen. Das Ergebnis einer Query ist yes oder no. Seine eigentliche Wirkung entfaltet ein Prolog-Programm streng genommen durch Nebenwirkungen, die während der Beweissuche auftreten. Also kann ein Prolog-System auch als ein sehr effizienter – wenn auch eingeschränkter – automatischer Theorembeweiser verstanden werden. Die einzige in Prolog eingebaute Suchstrategie bei der Beweisfindung ist Tiefensuche mit Backtracking.

## Anwendungsgebiete

In den 1980er-Jahren spielte die Sprache eine wichtige Rolle beim Bau von Expertensystemen. Die Sprache wird heute noch in den Bereichen Computerlinguistik und Künstliche Intelligenz verwendet. Zum Beispiel sind Sprachverarbeitungskomponenten des durch seinen Auftritt bei Jeopardy! bekannt gewordenen KI-Systems Watson in Prolog geschrieben. Außerdem gibt es einige kommerzielle Anwendungen im Bereich des Systemmanagements, bei denen asynchrone Ereignisse (Events) mit Hilfe von Prolog oder darauf basierenden proprietären Erweiterungen verarbeitet werden. Ein Beispiel hierzu ist das Produkt Tivoli Enterprise Console (TEC) von IBM, das auf IBM-Prolog basiert. Der 1986 in Japan von Sega veröffentlichte Sega AI Computer benutzte Prolog als ins ROM integrierte und somit sofort nach dem Anschalten des Computers nutzbare Programmiersprache.