Kurs:Algorithmen und Datenstrukturen/Vorlesung/Prolog

Aus Wikiversity




Prolog[Bearbeiten]

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

Beispiel 1[Bearbeiten]

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[Bearbeiten]

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

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

t(b). t(d).

Anfragen[Bearbeiten]

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[Bearbeiten]

Problem: Wegfindung in gerichteten Graphen

  • Gegeben ein Graph mit Knoten
  • Gibt es einen Weg zwischen Knoten (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[Bearbeiten]

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[Bearbeiten]

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.


Discussion