Prolog

Ein Prolog-Programm ist eine Menge von Hornklauseln und Fakten (=Atome ohne Variablen)

Beispiel 1

grandparent(X,Y) :- parent(X,Z), parent(Z,Y).

brother(X,Y) :- male(X), male(Y), parent(Z,X), parent(Z,Y).

hasUncle(X) :- parent(Y,X), brother(Y,_).

parent(bob, anna).

parent(carl, bob).

male(bob).

Anmerkung: „_“ ist eine beliebige (unbenannte) Variable

Beispiel 2

s(X,Y) :- r(X,Y), t(Y).

r(a,b). r(a,e). r(c,d).

t(b). t(d).

Anfragen

Prolog ist eine Anfrage-basierte Programmiersprache. Das bedeutet jede Ausführung eines Prolog-Programms muss mit einer Anfrage parametrisiert werden.

Die Anfragen zu oben gezeigten Prolog Programm aus Beispiel 1 lauten:

?grandparent(carl,anna) → Antwort YES
?male(anna) → Antwort NO (Closed World Assumption)

Anfragen können aber auch Variablen enthalten, so wie in Beispiel 2.

?s(a,X) → Antwort X=b
?r(a,X) → Antwort X=b, X=e

Die Semantik logischer Programme leitet sich direkt von der klassisch logischen Semantik der Prädikatenlogik ab (siehe Logik-Vorlesung).

Techniken:

Grundierung des Programms (ersetze Variablen durch alle Kombinationen von Konstanten) und aussagenlogische Verarbeitung
Unifikation des Anfrageterms und Backtracking

Beispiel

Problem: Wegfindung in gerichteten Graphen

Gegeben ein Graph mit Knoten $a_{1},...,a_{n}$
Gibt es einen Weg zwischen Knoten $a_{i}~und~a_{j}$ (für beliebige i,j)?

Lösung als Prolog-Programm:

path(X,Y) :- edge(X,Y).
path(X,Y) :- path(Z,Y), edge (X,Z).
edge(a1,a2). edge(a2,a3). edge(a2,a4). edge(a5,a1).

Anfragen:

?path(a1,a3) → Antwort YES
?path(a5,X) → Antwort X=a1, X=a2, X=a3, X=a4 (alle von a5 erreichbare Knoten)

Logische vs. Funktionale Programmierung

Hornklauseln sind Funktionen im Sinne von atomaren Operationen. Sie haben gemeinsam, dass sie die Rekursion als zentrales Paradigma haben und eine mathematische Basis. Zu den Unterschieden zählt, dass sie Atome entweder wahr oder falsch sind und dass die Funktionswerte beliebige Typen haben können.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.4.1 zu finden.

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Prolog

Inhaltsverzeichnis