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:

% Prolog Text mit Fakten
mann(adam).
mann(tobias).
mann(frank).
frau(eva).
frau(daniela).
frau(ulrike).
vater(adam, tobias).
vater(tobias, frank).
vater(tobias, ulrike).
mutter(eva, tobias).
mutter(daniela, frank).
mutter(daniela, ulrike).

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:

?- mann(tobias).
yes.
?- mann(heinrich).
no.

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:

?- frau(X).
X=eva
X=daniela
X=ulrike

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:

?- mann(heinrich).
no.
?- frau(heinrich).
no.

Zusätzlich zu Fakten lassen sich in Prolog Regeln formulieren.

Der Regeloperator :- ist dabei wie ein umgedrehter Implikationspfeil zu lesen. Beispiel:

% Prolog Text mit Regel
grossvater(X, Y) :-
    vater(X, Z),
    vater(Z, Y).

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:

grossvater(X, Y) :-
    vater(X, Z),
    mutter(Z, Y).

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:

?- grossvater(adam, ulrike).
yes.
?- grossvater(X, frank).
X=adam

Syntax

?- true,true.
true.

?- true,false.
false.

?- false,true.
false.

?- false,false.
false.

?- true;true.
true.

?- true;false.
true.

?- false;true.
true.

?- false;false.
false.

?- 3 < 4.
true.

?- 3 > 4.
false.

?- anton == anton. % == prüft ob das muster links und rechts übereinstimmt
true.

?- 3 == 1+2. % muster stimmt nicht überein
false.

?- 3 \== 1+2. %  \== prüft ob das muster links und rechts nicht übereinstimmt
true.

?- 3 =:= 1+2. % =:= ist der numerische vergleich
true.

?- 3 =\= 4. % =\= die numerische Ungleichheit
true.

?- 3 =\= 1+2. % 3=3
false.

?- 3 =< 4. % =< bedeutet kleiner/gleich; '<=' ist nicht zulässig
true.

?- 3 >= 4. % >= bedeutet größer/gleich
false.

?- 4 \= 2. % \= die muster können durch unifikation nicht ident gemacht werden
true.

?- X + 4 \= 2 + Y. % Durch X=2 und Y=4 werden die muster ident
false.

% Wenn X Vater von Z ist und Z  Vater von Y ist, dann ist X Großvater von  Y
grossvater(X, Y) :-
    vater(X, Z),
    vater(Z, Y).

% Adam ist der Vater von Tobias
vater(adam, tobias).

% Tobias ist der Vater von Frank
vater(tobias, frank).

% Abfrage ob Adam der Großvater von Frank ist
?- grossvater(adam, frank).
true.

% anton und berta sind ein Ehepaar
ehepaar(anton, berta).

% das Ehepaar X Und Y ist genau dann ein Ehepaar,
% wenn ein Ehepaar Y Und X existiert
ehepaar(X, Y) :- ehepaar(Y, X).

% Abfrage ob Berta und Anton ein Ehepaar sind
?- ehepaar(berta, anton).
true.

% Head ist die Zahl 1
% Tail ist die Liste [2]
[1, 2]

% Head ist die Zeichenkette 'one'
% Tail ist die Liste ['two']
['one', 'two']

% Listen können auch gemischt sein
[1, 'two']

% Head ist die Ziffer 1
% Tail ist die Liste [2,3]
[1, 2, 3]

member(X, [X|_]).
member(X, [_|T]) :-
    member(X, T).

?- member(2, ['anton','berta','caesar']).
false.

?- member('berta', ['anton','berta','caesar']).
true.

?- [user]. % tippe Prolog-Text direkt ein
append([], X, X).
append([X|Y], Z, [X|T]) :- append(Y, Z, T).
^D

?- consult('append.pl'). % lade Prolog Text-aus Datei
true.

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“):

% X ist genau dann ein elternteil von Y,
% wenn X die mutter von Y ist Oder
% wenn X der vater von Y ist.
elternteil(X, Y) :-
    mutter(X, Y);
    vater(X, Y).

% X ist einerseits dann ein vorfahr von Z,
% wenn X ein elternteil von Z ist.
vorfahr(X, Z) :- elternteil(X, Z).

% X ist andererseits dann ein vorfahr von Z, wenn
% X ein elternteil von Y ist Und
% Y ein vorfahre von Z ist
vorfahr(X, Z) :-
    elternteil(X, Y),
    vorfahr(Y, Z).

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:

familie(heinz, jutta, [peter,laura]).
familie(karl, gertrud, []).

Dann ließen sich z. B. mit einer Abfrage alle Männer ohne Kinder anzeigen:

?- familie(X, _, []).
X=karl

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:

auto(bmw, rot).
auto(bmw, blau).

autofarbe(Automarke, X) :-
    retract(auto(bmw, _)),
    auto(Automarke, X).

Die Abfrage:

?- auto(bmw, X).

ergibt (anfänglich) ganz normal:

X=rot;
X=blau;
No

Die Abfrage:

?- autofarbe(bmw, X).

würde beim ersten Mal:

X=blau;
No

beim zweiten Mal nur noch:

No

liefern, da die Informationen:

auto(bmw, rot).
auto(bmw, blau).

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

ABB - CD = EED
 -     -    *
FD  + EF = CE
 =     =    =
EGD * FH = ???

gen(A,B,C,D,E,F,G,H) :-
    permutation([A,B,C,D,E,F,G,H,_,_], [0,1,2,3,4,5,6,7,8,9]).

gl1(A, B, C, D, E) :-
    ((A * 100 + B * 10 + B) - (C * 10 + D)) =:= (E * 100 + E * 10 + D).
gl2(C, D, E, F) :-
    ((F * 10 + D) + (E * 10 + F)) =:= (C * 10 + E).
gl3(A, B, D, E, F, G) :-
    ((A * 100 + B * 10 + B) - (F * 10 + D)) =:= (E * 100 + G * 10 + D).
gl4(C, D, E, F, H) :-
    ((C * 10 + D) - (E * 10 + F)) =:= (F * 10 + H).
gl5(C, D, E, F, G, H, X) :-
    ((E * 100 + E * 10 + D) * (C * 10 + E)) =:=
    ((E * 100 + G * 10 + D) * (F * 10 + H)), X is ((E * 100 + G * 10 + D) * (F * 10 + H)).

loesung :-
    gen(A, B, C, D, E, F, G, H),
    gl1(A, B, C, D, E),
    gl2(C, D, E, F),
    gl3(A, B, D, E, F, G),
    gl4(C, D, E, F, H),
    gl5(C, D, E, F, G, H, X),
    write(X).

<buch titel="Peer Gynt">
    <autor name="Henrik Ibsen" nat="norwegisch"/>
    ...
</buch>

[element(buch, [titel='Peer Gynt'], [
    element(autor, [name='Henrik Ibsen', nat='norwegisch'], []),
    ...])
]

transform(delete, [element(DelTag, _, _) | Siblings], DelTag, ResTree) :-
    transform(delete, Siblings, DelTag, ResTree).

transform(concat, [Element1, Element2 | Siblings], ConTag, ResTree) :-
    Element1 = element(Contag, Attr, Children1),
    Element2 = element(Contag, _, Children2),
    append(Children1, Children2, Children),
    transform(concat, [element(ConTag, Attr, Children) | Siblings], ConTag, ResTree).

transform(_, [], _, []).

transform(Trans, [element(CTag, Attr, Children) | Siblings], Tag, ResTree) :-
    \+ Tag = CTag,
    transform(Trans, Children, Tag, ResChildren),
    transform(Trans, Siblings, Tag, ResSiblings),
    ResTree = [element(CTag, Attr, ResChildren) | ResSiblings].

transform(_, [Atom], _, [Atom]) :-
    atomic(Atom).

weg(Ziel, Ziel, Zustandsliste) :-
    write(Zustandsliste), nl.               % Ziel erreicht, Abbruch der Rekursion und Ausgabe

weg(Start, Ziel, Zustandsliste) :-          % Es gibt einen Weg vom Start zum Ziel, wenn ...
    operator(Op),                           % ... es einen Operator gibt, ...
    anwendbar(Op, Start),                   % ... der im Startzustand anwendbar ist, ...
    fuehrt_zu(Op, Start, Neu),              % ... von dort zu einem neuen Zustand fuehrt, ...
    not(member(Neu, Zustandsliste)),        % ... der noch nie da war (Verhinderung von Schleifen) ...
    zulaessig(Neu),                         % ... und zulaessig ist, ...
    weg(Neu, Ziel, [Neu|Zustandsliste]).    % ... und es von dort einen Weg zum Ziel gibt.

weg(Ziel, Ziel, Ortsliste):-
    write(Ortsliste), nl.                   % Ziel erreicht, Abbruch der Rekursion und Ausgabe

weg(Start, Ziel, Ortsliste):-               % Es gibt einen Weg vom Start zum Ziel, wenn ...
    strasse(Start, Neu),                    % ... es eine Strasse vom Start zu einem neuen Ort gibt, ...
    not(member(Neu, Ortsliste)),            % ... in dem man noch nicht war (Verhinderung von Schleifen), ...
    weg(Neu, Ziel, [Neu|Ortsliste]).        % ... und von dem es einen Weg zum Ziel gibt.

weg(Ziel, Ziel, Ortsliste, Strecke):-
    write(Ortsliste), nl, write(Strecke), nl.                   % Ziel erreicht, Abbruch der Rekursion und Ausgabe

weg(Start, Ziel, Ortsliste, Strecke):-                      % Es gibt einen Weg vom Start zum Ziel, wenn...
    findall(Ort, strasse(Start, Ort), Neuliste),                % ...es eine Liste erreichbarer neuer Orte gibt,...
    bewerte(Neuliste, Start, Strecke, Ziel, BewerteteListe),    % ...von denen jeder bewertet und ...
    sort(BewerteteListe, SortierteListe),                       % ...durch Sortieren der Liste...
    member([_, Sgesamt, Neu], SortierteListe),                  % ...der beste gesucht wird,...
    not(member(Neu, Ortsliste)),                                % ...in dem man noch nicht war,...
    weg(Neu, Ziel, [Neu|Ortsliste], Sgesamt).                   % ...und von dem es einen Weg zum Ziel gibt.

erstes(E, [E|_]).
mittleres(M, [_,_,M,_,_]).

links(A, B, [A,B|_]).
links(A, B, [_|R]) :- links(A, B, R).

neben(A, B, L) :-
    links(A, B, L);
    links(B, A,  L).

run :-
    X = [_,_,_,_,_],                                % Es gibt (nebeneinander) 5 (noch unbekannte) Häuser
    member([rot,brite,_,_,_], X),                   % Der Brite lebt im roten Haus
    member([_,schwede,_,_,hund], X),                % Der Schwede hält einen Hund
    member([_,daene,tee,_,_], X),                   % Der Däne trinkt gern Tee
    links([gruen,_,_,_,_], [weiss,_,_,_,_], X),     % Das grüne Haus steht links vom weißen Haus
    member([gruen, _, kaffee, _, _], X),            % Der Besitzer des grünen Hauses trinkt Kaffee
    member([_,_,_,pallmall,vogel], X),              % Die Person, die Pall Mall raucht, hält einen Vogel
    mittleres([_,_,milch,_,_], X),                  % Der Mann, der im mittleren Haus wohnt, trinkt Milch
    member([gelb,_,_,dunhill,_], X),                % Der Besitzer des gelben Hauses raucht Dunhill
    erstes([_,norweger,_,_,_], X),                  % Der Norweger wohnt im 1. Haus
    neben([_,_,_,marlboro,_], [_,_,_,_,katze], X),  % Der Marlboro-Raucher wohnt neben dem, der eine Katze hält
    neben([_,_,_,_,pferd], [_,_,_,dunhill,_], X),   % Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht
    member([_,_,bier,winfield,_], X),               % Der Winfield-Raucher trinkt gern Bier
    neben([_,norweger,_,_,_], [blau,_,_,_,_], X),   % Der Norweger wohnt neben dem blauen Haus
    member([_,deutsche,_,rothmans,_], X),           % Der Deutsche raucht Rothmans
    neben([_,_,_,marlboro,_], [_,_,wasser,_,_], X), % Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt
    member([_,N,_,_,fisch], X),                     % Der mit der Nationalität N hat einen Fisch
    write(X), nl,                                   % Ausgabe aller Häuser
    write('Der '), write(N),
    write(' hat einen Fisch als Haustier.'), nl.    % Antwort auf die Frage

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.

Siehe auch

• Liste von Programmiersprachen
• Zeittafel der Programmiersprachen
• Axiom, Deduktion
• Schnittregel
• Erlang (begann als Prolog-Interpreter, auch die Syntax ist davon inspiriert, ebenfalls personelle Nähe, denn der Erfinder von Erlang Joe Armstrong hat am Swedish Institute of Computer Science (SICS) gearbeitet)

Literatur

• Rüdeger Baumann: Prolog Einführungskurs, Klett Verlag, 1991, ISBN 3-12-717721-6.
• Patrick Blackburn, Johan Bos, Kristina Striegnitz: Learn Prolog Now! College Publications, 2006, ISBN 1-904987-17-6.
• David L. Bowen, Lawrence Byrd, Fernando C. N. Pereira, Luís M. Pereira und David H. D. Warren: DECsystem-10 Prolog User’s Manual. Occasional Paper 27, 1982. Department of Artificial Intelligence, University of Edinburgh, Edinburgh, Scotland. (Download; Doc; 192 kB)
• Hans Kleine Büning, Stefan Schmittgen: PROLOG: Grundlagen und Anwendungen. B.G. Teubner, Stuttgart 1986, ISBN 3-519-02484-5.
• Ivan Bratko: Prolog Programming for Artificial Intelligence. 4. Auflage, Addison-Wesley, Harlow 2012, ISBN 0-321-41746-1.
• William F. Clocksin: Clause and Effect. Prolog Programming for the Working Programmer. Springer, Berlin 2005, ISBN 3-540-62971-8.
• William F. Clocksin, Christopher S. Mellish: Programming in Prolog. 5. Aufl., Springer, Berlin 2003, ISBN 3-540-00678-8.
• Michael A. Covington, Donald Nute, André Vellino: Prolog Programming in Depth. Prentice Hall, 1996, ISBN 0-13-138645-X.
• H. Göhner, B. Hafenbrak: Arbeitsbuch PROLOG. DÜMMLER, Bonn 1995, ISBN 3-427-46863-1.
• Richard A. O'Keefe: The Craft of Prolog. MIT Press, Cambridge 1990, ISBN 0-262-15039-5.
• Esther König, Roland Seiffert: Grundkurs PROLOG fur Linguisten. UTB Linguistik, 1989, ISBN 3-7720-1749-5.
• Leon S. Sterling, Ehud Shapiro: The Art of Prolog. Advanced Programming Techniques. 2. Aufl., MIT Press, Cambridge 1994, ISBN 0-262-69163-9.
• Leon S. Sterling: The Practice of Prolog. MIT Press, Cambridge 2003, ISBN 0-262-51445-1.
• Gerhard Röhner: Informatik mit Prolog. Amt für Lehrerbildung (AfL), 2007, ISBN 3-88327-499-2.
• Wilhelm Weisweber: Prolog. Logische Programmierung in der Praxis. Thomson, 1997, ISBN 3-8266-0174-2.

Weblinks

Einzelnachweise und Anmerkungen

1. ↑ A. Colmerauer und P. Roussel: The birth of prolog. History of programming languages II. 1996, S. 331–367. (PDF-Dokument; 2,1 MB)
2. ↑ In Ermangelung einer formalen Spezifikation für Edinburgh Prolog wurde meist das DEC-10 PROLOG Manual von Bowen u. a. (1982) oder Programming in Prolog von Clocksin und Mellish herangezogen.
3. ↑ Adam Lally, Paul Fodor: Natural Language Processing With Prolog in the IBM Watson System. The Association for Logic Programming, 31. März 2011, abgerufen am 18. Oktober 2001 (englisch).