Logische Programmierung: Prolog Proseminar Programmiersprachen WS 2003/2004 Jochen Frey Betreuer: Prof. Dr. Gert Smolka

Logische Programmierung:Prolog

Proseminar Programmiersprachen WS 2003/2004

Jochen FreyBetreuer: Prof. Dr. Gert Smolka

Jochen Frey Logische Programmierung: Prolog 2

Übersicht


Deklarative Programmierung

• Zwei Interpretationen:– Prozedurale Interpretation:

„Wie wird etwas berechnet ?“– Deklarative Interpretation:

„Was wird berechnet ?“

• Logische Programmierung ist deklarative Programmierung mit Prädikatenlogik


Geschichte von Prolog

• Entwickelt 1970 (Kowalski, Colmerauer)

• PROrammieren in LOGik• Beeinflusste viele Entwicklungen:

– 5th Generation Project– Deductive Databases– Constraint Logic Programming


Terme

•Grundlegende Datenstruktur in Prolog

•Grammatik:

<Term> ::= <Variable> | <ETerm><ETerm> ::= <Zahl> | <Symbol(Term, …, Term)>

<Fakt> ::= <ETerm>

<Regel> ::= <ETerm :- ETerm, …, ETerm>


Logische Programme

:= Folge von Klauseln (Fakten und Regeln)

Regelkopf Regelkörper

H :- B1, …, B2

Deklarative Semantik Prozedurale SemantikH erfüllt, fall sowohl B1 als auch B2 erfüllt werden können

H erfüllt, falls zuerst B1 und dann B2 erfüllt werden können

Für die Abarbeitung von Prolog-Programmen wird den Programmklauseln eine prozedurale Semantik unterstellt


Beispiel: Biblische Familiefather(terach, abraham).father(terach, nachor).father(terach, haran).father(abraham, isaac).father(haran, lot).father(haran, milcah).father(haran, yiscah).

mother(sarah, isaac).

son(X,Y) :- father(Y,X), male(X).daughter(X,Y) :- father(Y,X), female(X).

Fakten

Regeln

male(terach).male(abraham).male(nachor).male(haran).male(isaac).male(lot).

female(sarah).female(milcah).female(yiscah).


?- father(abraham, isaac).

Anfragen

• Prolog prüft nun, ob die Anfrage eine logische Konsequenz des Programms ist

• Ist dies der Fall so antwortet Prolog mit Yes

• Andernfalls mit No• Hier:

Yes


Unifikation

Lösen von Gleichungen zwischen Termen

durch Unifikation: – finden einer Substitution s zwischen

Termen t1 und t2, mit s(t1) = s(t2)

– allgemeinste Lösung wird als allgemeinster Unifikator bezeichnet


Ein Unifikations-Algorithmus1. f(s1, …, sn) = f(t1, …, tn) ersetzen durch

s1=t1, …, sn=tn 2. f(s1, …, sn) = g(t1, …, tm), mit f≠g Fehler

3. x=x löschen

4. t=x, wobei t keine Variable ist ersetzen durch x=t

5. x=t, wobei x nicht in t aber woanders Substitution vorkommt {x/t} anwenden

6. x=t, wobei x in t vorkommt und x≠t Fehler


Beispiele

X=abrahamY=isaac

Y=father(X,isaac)

nicht unifizierbar

nicht unifizierbar

• father(X, isaac)father(abraham, Y)

• Yfather(X, isaac)

• father(haran, lot)father(abraham, isaac)

• father(X, isaac)mother(sarah, isaac)


Beispiel: Biblische Familie

father(terach, abraham).father(terach, nachor).father(terach, haran).father(abraham, isaac).father(haran, lot).father(haran, milcah).father(haran, yiscah).

mother(sarah, isaac).

?- father(abraham, isaac).

Datenbasis Anfrage Antwort

Yes


Auswertungsmechanismus

• Prolog sucht eine Auflösungssequenz um eine Anfrage zu beantworten durch:

– Backward-Chaining (top-down)– Tiefensuche

Jochen

Beschreibung anhand der nachfolgenden Suchbäumeoder kurze suchbäume noch einfügen


Beispiel?- son(X,abraham).

father(abraham,X),male(X).

father(abraham,isaac).father(haran,lot).father(haran,milcah). father(haran,yiscah).

male(isaac).male(lot).female(milcah).female(yiscah).


X=isaacmale(isaac).

Output: X=isaac


Rücksetzen

Problem:Bei der Unifikation innerhalb einer Resolution einer Anfrage tritt ein Fehler auf

Lösung:– Rückschritt zum letzten Punkt an dem

Prolog eine Auswahl treffen musste – Rückgängigmachen der

Variablenbindungen– Nächste Klausel auswählen


Rücksetzen ?- daughter(X,haran)?

father(abraham,isaac).father(haran,lot).father(haran,milcah). father(haran,yiscah).

male(isaac).male(lot).female(milcah).female(yiscah).


father(haran,X),female(X).

X=lotfemale(lot).

X=milcahfemale(milcah).

X=yiscahfemale(yiscah).

No Output: X=milcah Output: X=yiscah

;


Beispiel: membermember(X, [X|Xs]).member(X, [Y|Ys]) :- member(X, Ys).

?- member(X, [1,2,3]).

?- member(X, [2,3]).X=1

?- member(X, [3]).; X=2

; X=3


Beispiel: appendappend([], Ys, Ys).append([X|Xs], YS, [X|Zs]) :- append(Xs, Ys, Zs).

?- append([a,b],[c,d],[a,b,c,d]).

?- append([b],[c,d],[b,c,d]).

?- append([],[c,d],[c,d]).

Yes


Beispiel: lastlast([X], X).last([Y|Ys], X) :- last(Ys, X).

?- last([1,2,3], X).

?- last([2,3], X).

?- last([3], X).

X=3

Alternative: last(List, Last) :- append(_, [Last], List).


Evaluation arithmetischer Ausdrücke

built-in Prädikat is/2:• nimmt eine Variable und ein Term als

Argumente• berechnet den Term • und bindet die Variable an den berechneten

Term • falls linkes Argument keine Variable

Vergleich • Fehlermeldung wenn im rechten Argument

eine ungebundene Variable steht


Beispiele

• 5 is 2+3 Yes• X is 2+3 X=5

• X is Y+3 Fehler

Unterschied: X = 2+3 Unifikation


Beispiele

if_then_else: „if P then Q else R“Intuitiv:

if_then_else(P, Q, R) :- P, Q.if_then_else(P, Q, R) :- not P, R.

if_then_else(P, Q, R) :- P, Q. if_then_else(P, Q, R) :- R.

Lösung mit Cut:if_then_else(P, Q, R) :- P, !, Q.if_then_else(P, Q, R) :- R.

ineffizient

falsch


built-in Prädikat cut („ ! “)

Idee: Suchbäume „stutzen“ um unnötige Berechnungen zu vermeiden

2 Arten:– grüne cuts: schneiden Suchbäume weg, die

nicht zur Lösung beitragen Effizienssteigerung

– rote cuts: schneiden Suchbäume weg, die Lösungen enthalten

Bedeutung des Prog. wird geändertmeistens Programmierfehler


Negation

• Implementierung mit cut:not(X) :- X, !, fail.not(X).

• Unterscheiden von Fehlschlagen und Erfolg einer Berechnung

• Beispiel: alle Elemente einer Liste ≠ 3:?- member(X, [1,2,3,4]), not(X=3).

Jochen

not(X=3), member(X,[1,2,3,4,5]) terminiert nicht, da?- not(X=3)No.


Problem mit built-in Prädikaten

• Der Programmierer muss über die Resolution nachdenken

• Es besteht also keine deklarative Semantik mehr• Falsche Reihenfolge führt zu Fehlern

Beispiele:

?- X is Y+3, Y = 2. ?- Y = 2, X is Y+3.

?- member(X, [1,2,3,4]), not(X=3). ?- not(X=3), member(X, [1,2,3,4]).

X = 5 Fehler

X = 1;X = 2; X = 4

No.


freeze

• Die Ausführung eines Ziels kann verzögert werden, bis die Variable X gebunden wird

• Somit kann z. B. die Problematik von einigen built-in Prädikaten behoben werden

freeze(X, Goal).

?- freeze(Y,(X is Y+3)), Y = 2. X = 5

?- freeze(X, not(X=3)), member(X, [1,2,3,4]). X = 1;X = 2; X = 4


N-Dame-ProblemAuf einem N x N Schachbrett sollen N Damen so angeordnet werden, dass sie sich nicht gegenseitig schlagen können

1

2

3

4

Lösung: [2,4,1,3]


N-Dame-Problemqueens(N,Qs) :- range(1,N,Ns), permutation(Ns,Qs), safe(Qs).

range(M,N,[M|Ns]) :- M < N, M1 is M+1, range(M1,N,Ns).range(N,N,[N]).

permutation(Xs,[Z|Zs]) :- select(Z,Xs,Ys), permutation(Ys,Zs).permutation([],[]).

safe([Q|Qs]) :- safe(Qs), not(attack(Q,Qs)).safe([]).

attack(X,Xs) :- attack(X,1,Xs).

attack(X,N,[Y|Ys]) :- X is Y+N.attack(X,N,[Y|Ys]) :- X is Y-N.attack(X,N,[Y|Ys]) :- N1 is N+1, attack(X,N1,Ys).


Zusammenfassung

• deklarative Programmiersprache• Suche eingebaut • sehr effiziente Techniken für Rück-

setzen und Unifikation• fehlende Typen• keine Module• problematische Arithmetik• spezifische Kontrollmechanismen


Anwendungen

• Automatisierte Beweise• Expertensysteme• Computerlinguistik• Rapid Prototyping• ...


Literatur

Kowalski, R.: Algorithm = Logic + Control, Communication of the ACM 22, pp.424-436, 1979

Mitchell, J.C.: Concepts in Programming Languages. 1.Aufl., Cambridge University Press, 2003

Sterling, L.; Shapiro, E.: The Art of Prolog. 1. Aufl., MIT, 1986

Documents

Logische Programmierung: Prolog Proseminar Programmiersprachen WS 2003/2004 Jochen Frey Betreuer: Prof. Dr. Gert Smolka