Prolog ist eine deklarative Programmiersprache, die auf der Prädikatenlogik der ersten Stufe basiert und deren zentraler Mechanismus die Unifikation ist. Programmiert wird, indem in einer Wissensbasis (d.h. einer Datenbank) Prädikate mithilfe von Fakten und Regeln definiert werden, die in Abfragen (queries) benutzt werden können, um Informationen zu erhalten. Dazu wird vom System die Eingabe mit passenden Klauseln (Fakten oder Regeln) aus der Datenbank unifiziert und es werden Variablenbindungen ausgegeben. Der Unifikations-Mechanismus wird im Anschluss an die Beispiele erklärt.
Prolog ist ein hervorragendes Beispiel für den deklarativen Stil, weil hier nur das Was definiert werden kann. Zuweisung und Sprünge sind nicht möglich. Es wird stattdessen mit Variablenbindung, Rekursion und Backtracking gearbeitet. Zudem ist Prolog eine mächtige, aber recht kompakte Sprache. Eine abschließende Bewertung folgt am Ende dieses Abschnitts.
Ein zentraler Vorteil von Prologprogrammen ist die Richtungsunabhängigkeit von Prädikaten. Das klassische Beispiel ist die das Prädikat Append, die zwei Listen zu einer konkatenierten Liste transformieren kann. Gleichzeitig kann es in anderen Aufrufvarianten benutzt werden, z.B. zur Extraktion von Prä- und Suffixen und zur Generierung von Listen-Teilen.
Eine Liste ist entweder die leere Liste (geschrieben als [], auch Nil genannt) oder ein Element gefolgt von einer Liste (angedeutet durch [_|_], auch Cons genannt).
append([], X, X). append([Head|Tail], X, [Head|Result]) :- append(Tail, X, Result). /* Beispiele: append([1,2], [3,4], L). -> L = [1,2,3,4]. append([1,2], Suf, [1,2,3,4]). -> Suf = [3,4]. append(Pre, [3,4], [1,2,3,4]). -> Pre = [1,2]. append(Pre, Suf, [1,2,3,4]). -> Pre = [], Suf = [1,2,3,4]; Pre = [1], Suf = [2,3,4]; Pre = [1,2], Suf = [3,4]; Pre = [1,2,3], Suf = [4]; Pre = [1,2,3,4], Suf = []. */
Auffällig ist die Kürze des Append-Prädikats. Nur Zwei Zeilen sind nötig, um die Eigenschaften von Append zu formulieren:
Die erste Zeile lässt sich so beschreiben: Die Konkatenation der leeren Liste mit einer anderen Liste ist die andere Liste. Diese Zeile stellt den Rekursionsabbruch dar.
Die zweite Zeile besagt: Um eine nicht-leere Liste aus Head und Tail mit einer anderen Liste zu konkatenieren, wird der Head in die Ergebnisliste übernommen und der Rest des Ergebnisses wird durch die Konkatenation des Tails und der anderen Liste geliefert. Hier geschieht die Konsumption, die für das Terminieren der Rekursion wichtig ist, auf der ersten Argumentstelle.
Ein anderes wichtiges Prädikat, das mehrere Aufgaben erfüllt, die mit der Enthaltenseinbeziehung zusammenhängen, ist das Member-Prädikat:
member(Head, [Head|_]). member(Element, [_|Tail]) :- member(Element, Tail). /* Beispiele: member(E, [1,2,3,4]). -> E = 1; E = 2; E = 3; E = 4. member(3, [1,2,3,4]). -> yes. member(5, [1,2,3,4]). -> no. member(5, L). -> L = [5|_]; L = [_,5|_]; L = [_,_,5|_]; ... */
Wieder lässt sich eine natürlichsprachliche Formulierung finden: Der Kopf der Liste ist Element der Liste, ebenso wie Elemente des Restes der Liste.
Mit dem Prädikat kann man durch eine Liste iterieren, Werte auf Enthalten-sein prüfen und es lassen sich (unendlich viele) Listen generieren, die ein bestimmtes Element enthalten. Die letzte Ausgabe zeigt außerdem eine weitere Besonderheit von Prolog: die Verwendung von freien Variablen in Datenstrukturen. Eine weitere Eigenschaft von Prädikaten wird deutlich: Die Klauseln, aus denen das Prädikat besteht, müssen einander nicht ausschließen.
Unifikation
Der Unifikations-Mechanismus versucht, zwei Werte gleich zu machen, indem Variablenbindungen hergestellt werden. Sind zwei Terme nicht unifizierbar, ist das Ergebnis false (was zum Abbruch des Prädikats führt), andernfalls werden die Bindungen hergestellt und das Ergebnis ist true (was zur weiteren Ausführung des Prädikats führt).
Der Mechanismus unterscheidet, welche zwei Werte miteinander unifiziert werden sollen. Es gibt in Prolog als Werte nur Atome (wie Symbole, Zahlen, Bool’sche Werte), Variablen und Strukturen.
Da Unifikation symmetrisch ist, gibt es nur die folgenden Fälle (gebundene Variablen entsprechen ihrem gebundenen Wert, daher gibt es hier nur freie Variablen):
FreieVariable = FreieVariable führt zur Koreferenz von zwei Variablen (wird im Folgenden eine der beiden gebunden, wird es die andere auch).
FreieVariable = konstante führt zur Bindung der Variablen an die Konstante.
FreieVariable = struktur(...) führt zur Bindung der Variablen an die Struktur.
konstante = konstante unifiziert, weil die Konstanten gleich ist.
struktur(...) = struktur(...) unifiziert, wenn die Stelligkeit der Strukturen übereinstimmt und alle Argumente rekursiv unifiziert werden können.
Einordnung von Prolog
Prolog wird oft für Wissensdatenbanken verwendet, denn Datenbankanfragen sind leicht zu schreiben, z.B. ist kunde(2, Name) die Abfrage des Namens des Kundens mit der Nummer 2. Voraussetzung ist das Wissen über die genaue Struktur der Datenbank; in dem Beispiel die Kenntnis, dass kunde eine zweistellige Relation ist, deren ersten Argumentstelle die Kundennummer und die zweite Stelle der Name ist. Eine Datenbank besteht aus Fakten:
kunde(1, john). kunde(2, paul). kunde(3, george). kunde(4, ringo).
Die Ausgabe für die Beispielabfrage kunde(2, Name) ist Name = paul.
Der Bezug zur Definition Formulieren von Regeln und Zusammenhängen ist durch folgende Eigenschaften hergestellt:
- Formulieren ist das Schreiben von Prädikaten.
- Regeln sollen Fälle unterscheiden: Das passiert in Prolog mithilfe von Prädikaten, die Fälle klassifizieren. Die Unterscheidungen nimmt der Prolog-Programmierer durch geeignete Klausel-Köpfe vor (im Append-Beispiel durch Unterscheidung nach [] oder [Head|Tail]). Zudem können Fälle im Klausel-Körper mithilfe von beliebigen Prädikaten genauer unterschieden werden.
- Zusammenhänge führen zum Berechnungsergebnis. Dies ist mit funktionalen Zusammenhänge der Form X is Y + Z möglich, aber vor allem durch Verwendung der mithilfe von Prädikaten definierten Relationen.
Mithilfe von Prolog kann das Problem auf hoher Abstraktionsebene beschrieben werden und das System übernimmt die Suche nach Lösungen. Prolog eignet sich zur Lösung von Logikrätseln, Beschreibung von Spielregeln, Datenbankabfragen, Listenverarbeitung, Suche in Hierarchien, Sprachverarbeitung und Anwendungen im Bereich der Künstlichen Intelligenz (KI). Eine weitere große Stärke ist Metaprogrammierung (Code-Generierung und -Auswertung) und die Definition eigener Operatoren, um eine eigene (domänen-spezifische) Sprache zu entwickeln.
Berechnung von arithmetischen Ausdrücken wird durch die Vorgabe, Prädikate zu verwenden, erschwert. Das Schreiben von funktionalen Ausdrücken wie N - 1 führt zur Erstellung der Struktur -(N, 1), welche mit dem is-Prädikat ausgerechnet werden kann. Die Quadrierungsfunktion 
Zustandsabhängige Programmierung ist durch spezielle Prädikate wie assert und retract (zur Veränderung der Wissensbasis) möglich.
Außen vor gelassen wurde in dieser Betrachtung die Negation und der Cut, welche beide in realen Prolog-Anwendungen häufig verwendet werden.
Prolog ist dynamisch typisiert, was insbesondere Listenverarbeitung leicht macht, wodurch sich aber einige Programmier-Fehler erst zur Laufzeit bemerkbar machen.
Prolog und funktionale Programmierung
Die Erben von Prolog sind unter anderem Curry und Mercury, zwei logikfunktionale Sprachen, die unter anderem schnellen C-Quelltext produzieren und dem Programmierer Features von Prolog und funktionalen Programmiersprachen wie Haskell (im Fall von Curry) bieten.
Aktuell sind funktional-objektorientierte Sprachen wie Scala und F# auf dem Weg, populär zu werden. Das lässt sich durch aussagekräftigeren und kürzeren Quelltext, aber auch durch Vorteile bei paralleler Programmierung erklären. Es ist abzuwarten, ob sich logikfunktionale Sprachen durchsetzen werden. An der Universität in Kiel wird beispielsweise Curry gelehrt, wobei funktionale und Logik-Programmierung mittels einer Programmiersprache unterrichtet werden kann [Curry, S. 334].
Das Konzept Pattern matching spielt in Miranda und anderen funktionalen Programmiersprachen eine wichtige Rolle. Pattern matching ist eine eingeschränkte Form der Unifikation, bei der nur die linke der beiden Seiten Variablen enthalten darf.
Deklarativ, wenn möglich; imperativ, wenn nötig 