Upload
karlotte-stein
View
122
Download
1
Embed Size (px)
Citation preview
Einführung in PROLOG
Referat zur Veranstaltung „Informatik VI“
(18.635)
StD G. Noll
Rhein Gymnasium
Sinzig
Februar 2001
g ( x )
f ( )
g ( )
f ( x )
barbarasterblich(A) :- mensch(A).mensch(x).
2
PROL G
© G. Noll 2001
Logik
Gottlob Frege: Begriffsschrift (1879)
Bertrand Russel, Alfred North WhiteheadPrincipia Mathematica (1910)
Colmerauer e.a. System-Q (1971)
Aristoteles: Syllogismen (~ 330 v. Chr.)
3
PROL G
© G. Noll 2001
PROLOG
PROgrammieren in LOGik
Anfang der 70er Jahre in Edinburgh von Kowalski und van Emden entwickelt
in Marseille von Colmerauer zum ersten Mal implementiert
in der Mitte der 80er Jahre weltweiter Durchbruch als Sprache der KI und bei der Entwicklung von Expertensystemen
heute hat das Interesse an PROLOG nachgelassen
4
PROL G
© G. Noll 2001
Vorteile für die Schule
interaktive Programmerstellungdeklaratives Programmieren als Gegenstück zum imperativen Konzept
kostenlose (gepflegte) PROLOG-Implementationen im InternetSWI-Prolog www.swi.psy.uva.nl/projects/SWI-Prolog/Strawberry Prolog www.dobrev.com/Visual Prolog www.visual-prolog.com/
überschaubare Syntax
5
PROL G
© G. Noll 2001
PROLOG-Programm
Programmieren in PROLOG bedeutet das Erstellen einer Wissensbasis die Formulierung intelligenter Anfragen
PROLOG - Programm
Wissensbasis Anfrage
6
PROL G
© G. Noll 2001
Wissensbasis
Daten führen über eine Interpretation zur Information
Daten werden für PROLOG in einer Wissensbasis gespeichert
Wissen ist die Fähigkeit zur sachgerechten Interpretation von Daten
7
PROL G
© G. Noll 2001
PROLOG - System
WissensbasisFakten
Regeln
InferenzmaschineSuchstrategien
Logik
Benutzerin Benutzer
Anfrage
Antworten
Eingabe vonDaten
8
PROL G
© G. Noll 2001
Klauseln
Faktum
Regel
Fakten Eigenschaften von Objekten oderBeziehungen zwischen ihnen
Regeln „wenn-dann“ Aussagen
9
PROL G
© G. Noll 2001
Fakten
Mit Fakten stellt man Konstanten, Eigenschaften von Objekten oder Beziehungen zwischen Objekten dar
sonnig.frau(elisabeth).mutter(elisabeth,gregor).
Fakten bestehen aus einem Klauselkopf, d. h. einem Funktor mit keinem, einem oder mehreren Argumenten
10
PROL G
© G. Noll 2001
Regeln
Sie bestehen aus einem (Klausel-) Kopf und einem Körper mit Termen (Zielen)
frau(X) :- mutter(X,_).
Der Körper beschreibt eine Folge von Voraussetzungen, aus deren Gültigkeit auf die Gültigkeit des Kopfes geschlossen wird
Mit Regeln beschreibt man „wenn-dann“ Aussagen ( d. h. bedingte Beziehungen) zwischen Objekten
11
PROL G
© G. Noll 2001
Terme
Operationen old(X) :- X > 80.
Systemprozeduraufrufe out(X) :- write(X), nl.
Im Körper einer Regel können als Terme auftreten:
Klauselköpfe frau(X) :- mutter(X,_).
12
PROL G
© G. Noll 2001
Termverknüpfungen
Terme im Regelkörper lassen sich
logisch miteinander verbinden:
ein Komma , steht für UND
ein Semikolon ; für ODER
Die ODER-Verknüpfung wird selten
verwendet. Stattdessen fügt man eine
weitere Regel hinzu.
opa(O,E) :- vater(O,V),
vater(V,E).
opa(O,E) :- vater(O,M),
mutter(M,E).
13
PROL G
© G. Noll 2001
Prädikate
Alle Klauseln mit gleichem Funktor und gleicher Stelligkeit bilden ein Prädikat
Klauseln werden identifiziert über ihren eindeutigen Bezeichner, den Funktor, und ihre Stelligkeit.
mutter(claudia). mutter/1mutter(else,pia). mutter/2
14
PROL G
© G. Noll 2001
Syntax
Bezeichner für Funktoren beginnen mit einem Kleinbuchstaben
Bezeichner für Konstanten beginnen mit einem Kleinbuchstaben
Bezeichner für Variable beginnen mit einem Großbuchstaben
der Unterstrich _ bezeichnet eine anonyme Variable
Bezeichner werden aus Buchstaben, Ziffern und Unterstrich gebildet
Klauseln und Abfragen enden mit einem Punkt .
Kommentare stehen zwischen /* und */
15
PROL G
© G. Noll 2001
Anfragen
?- mutter(claudia). Antwort: yes
?- mutter(M,pia). Antwort: M=elsemore (y/n)?
Erkenntnisse aus einer Datenbasis gewinnen wir durch Anfragen. Diese werden interaktiv an das System als Ziele (goals) in Form von Klauselköpfen gestellt:
16
PROL G
© G. Noll 2001
Übung 1
Definieren Sie eine Regel für opa(Opa,Enkelkind) und stellen Sie geeignete Anfragen, u.a. nach dem Opa von FritzUntersuchen Sie, was passiert, wenn Sie die Reihenfolge der Klauseln im Programm ändernWie findet PROLOG die Antworten auf Ihre Anfragen
Geben Sie in das PROLOG-System folgende Daten ein:vater(egon,hans). /* vater(Vater,Kind) */vater(hans,fritz).vater(emil,maria).mutter(maria,fritz). /* mutter(Mutter,Kind) */
17
PROL G
© G. Noll 2001
Semantik
Anfragen werden mit Hilfe der Klauseln solange auf einfachere Aussagen zurückgeführt, bis diese Fakten des Programms sind. Dies leistet die Inferenzmaschine.
PROLOG besitzt neben der deklarativen Semantik auch eine prozedurale.
deklarativ logische Bedeutung des Programms
prozedural Abarbeitung des Programms
18
PROL G
© G. Noll 2001
Matching
Eine Klausel passt zu einem Ziel („matched“), wenn der Klauselkopf mit dem Ziel unifiziert („verschmilzt“):
Klausel und Ziel haben den gleichen Namen und gleiche Stelligkeitdie Parameter passen zueinander, d. h. sie sind entweder identisch oder mindestens ein Parameter ist eine Variable
Im Prozess der Unifikation werden die Variablen an die Parameter des anderen Ausdrucks gebunden: sie werden instantiiert (instanziert) oder gleichgesetzt
Das Systems geht auf die Suche nach einer passenden Klausel
19
PROL G
© G. Noll 2001
Backtracking
Ein damit verbundenes Zurücksetzen auf einen früheren Zustand im Suchprozess wird Backtracking genanntDie Rückkehr ist verbunden mit der Freigabe aller Variablenbindungen, die seit dem ersten Anlauf des früheren Zustandes vorgenommen wurden
Der Suchprozess nach einer passenden Klausel kann in Sackgassen gelangen:
eine ausgewählte passende Klausel führt nicht zum Ziel, so dass später eine alternative, ebenfalls passende Klausel versucht werden muss
20
PROL G
© G. Noll 2001
UND-ODER-Baum
Die Nachfolgeknoten enthalten die Klauseln des PrädikatesBei Regeln bilden die Klauseln des Rumpfes die Nachfolgeknoten
UND-Verknüpfungen von Klauseln werden mit einem Winkelbogen dargestellt.
An der Wurzel steht der Funktor des Prädikats, das mit der Anfrage matched.
21
PROL G
© G. Noll 2001
opa(Opa,fritz).
opa / 2
opa(O,E)
vater(O,V) vater(V,E)
opa(O,E)
vater(O,M) mutter(M,E)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
vater(egon,hans) vater (hans,fritz)
vater(emil,maria)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
mutter(maria,fritz)
Ident: O=Opa
Inst: E=fritz
Inst: O=egon
Inst: V=hans
V=hans
E=fritz
Opa = egon
Inst: O=hans
Inst: V=fritz
V=fritz
E=fritz
22
PROL G
© G. Noll 2001
V=fritz
E=fritz
opa(Opa,fritz).
opa / 2
opa(O,E)
vater(O,V) vater(V,E)
opa(O,E)
vater(O,M) mutter(M,E)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
vater(egon,hans) vater (hans,fritz)
vater(emil,maria)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
mutter(maria,fritz)
Ident: O=Opa
Inst: E=fritz
Inst: O=hans
Inst: V=fritz
Inst: O=hans
Inst: V=maria
V=maria
E=fritz
23
PROL G
© G. Noll 2001
V=maria
E=fritz
opa(Opa,fritz).
opa / 2
opa(O,E)
vater(O,V) vater(V,E)
opa(O,E)
vater(O,M) mutter(M,E)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
vater(egon,hans) vater (hans,fritz)
vater(emil,maria)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
mutter(maria,fritz)
Ident: O=Opa
Inst: E=fritz
Inst: O=hans
Inst: V=maria
Ident: O=Opa
Inst: E=fritz
24
PROL G
© G. Noll 2001
opa(Opa,fritz).
opa / 2
opa(O,E)
vater(O,V) vater(V,E)
opa(O,E)
vater(O,M) mutter(M,E)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
vater(egon,hans) vater (hans,fritz)
vater(emil,maria)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
mutter(maria,fritz)
Ident: O=Opa
Inst: E=fritz
Inst: O=egon
Inst: M=hans
M=hans
E=fritz
Inst: O=hans
Inst: M=fritz
M=fritz
E=fritz
25
PROL G
© G. Noll 2001
opa(Opa,fritz).
opa / 2
opa(O,E)
vater(O,V) vater(V,E)
opa(O,E)
vater(O,M) mutter(M,E)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
vater(egon,hans) vater (hans,fritz)
vater(emil,maria)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
mutter(maria,fritz)
Ident: O=Opa
Inst: E=fritz
Inst: O=hans
Inst: M=fritz
Inst: O=emil
Inst: M=maria
M=fritz
E=fritz
M=maria
E=fritz
26
PROL G
© G. Noll 2001
opa(Opa,fritz).
opa / 2
opa(O,E)
vater(O,V) vater(V,E)
opa(O,E)
vater(O,M) mutter(M,E)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
vater(egon,hans) vater (hans,fritz)
vater(emil,maria)
vater(egon,hans)
vater (hans,fritz) vater(emil,maria)
mutter(maria,fritz)
Ident: O=Opa
Inst: E=fritz
Inst: O=emil
Inst: M=maria
Opa = emil
M=maria
E=fritz
27
PROL G
© G. Noll 2001
Trace
call das Ziel wird das erste Mal aufgerufenexit das Ziel ist erfolgreich abgearbeitet wordenredo nach erfolgreicher Abarbeitung wird das Ziel zu einem
späteren Zeitpunkt nochmals über Backtracking aktiviertfail der Versuch das Ziel zu beweisen scheitert
Klausel, die dem Ziel entspricht
call exit
redofail
Einem Trace liegt das Vier-Port-Boxmodell zugrunde
28
PROL G
© G. Noll 2001
fixPROLOG Trace
CALL: opa(Opa_1,fritz)COMP: opa(O_2,E_2) :- vater(O_2,V_2) , vater(V_2,E_2)IDEN: O_2 <-- Opa_1INST: E_2 <-- fritzCALL: vater(O_2,V_2)COMP: vater(egon,hans)INST: Opa_1 <-- egonINST: V_2 <-- hansEXIT: vater(egon,hans)
Die Trace-Implementation von fixPROLOG entspricht leider nicht dem Standard
CALL:vater(hans,fritz)COMP:vater(egon,hans)FAIL:vater(hans,fritz)REDO:vater(hans,fritz)COMP:vater(hans,fritz)EXIT: vater(hans,fritz) Opa = egon REDO:vater(hans,fritz)
?- opa(Opa,fritz).
29
PROL G
© G. Noll 2001
Übung 2
Verwenden Sie auch die Möglichkeit, die Arbeit der Inferenzmaschine mit einem Trace zu verfolgen.
Bearbeiten Sie die Arbeitsanweisungen des Kapitels 4.4 der Handreichung „Wissensverarbeitung mit PROLOG“
30
PROL G
© G. Noll 2001
Rekursion
In der Wissenbasis sei das Ergebnis eines kleinen Wettlaufs erfasst. Dabei besagt das Prädikat vor/2 beim Faktum vor(L1,L2). , dass L1 unmittelbar vor L2 ins Ziel kommt.
vor(lisa,tom). vor(tom,elke). vor(elke,karl).
vor(karl,petra). vor(petra,ria). vor(ria,mario).
Wir wollen ein Prädikat besser/2 definieren mit folgender Bedeutung besser(L1,L2). /* L1 hat eine bessere Zeit als L2 */
Eine besondere Stärke erfährt PROLOG durch die Möglichkeit, eine Beziehung durch Rückgriff auf sich selbst definieren zu können.
31
PROL G
© G. Noll 2001
besser/2
Ein erster Ansatz wäre
besser(L1,L2) :- vor(L1,L2).
L1 braucht aber nicht unmittelbar vor L2 ins Ziel zu kommen, um eine bessere Zeit zu haben, deshalb wären
besser(L1,L2) :- vor(L1,L3),vor(L3,L2). oder
besser(L1,L2) :- vor(L1,L3),vor(L3,L4),vor(L4,L2). usw.
ebenfalls mögliche Klauseln.
32
PROL G
© G. Noll 2001
besser/2
vor
besser
L1 L2
vor vor
besser
L2 L1 L3
vor vor vor
besser
L1 L2 L4 L3
besser(L1,L2) :- vor(L1,L3), besser (L3,L2).
vor
besser
besser
L3 L1 L2 ...
33
PROL G
© G. Noll 2001
Testen Sie das Prädikat besser/2 z. B. mit der Anfrage besser(tom,petra).
besser/2
besser(L1,L2) :- vor(L1,L3), besser(L3,L2).besser(L1,L2) :- vor(L1,L2).
Leider erhalten Sie nicht die erwarteten Antworten!
Es fehlt eine Abbruchbedingung für die Rekursion
34
PROL G
© G. Noll 2001
besser/2
Testen Sie, wie sich für besser/2eine Vertauschung der beiden Klauselneine Vertauschung der Ziele im Regelrumpf
auf die Abfragen auswirken
35
PROL G
© G. Noll 2001
Übung 3
Untersuchen Sie auch hier die Wirkung einer Vertauschung der beiden Klauseln
Wir betrachten das Prädikat wechsel/2 mit den Klauseln
wechsel(a,b).
wechsel(X,Y) :- wechsel(Y,X).
Welche Ausgabe liefert die Anfrage wechsel(A,B) ?
36
PROL G
© G. Noll 2001
Übung 4
Bearbeiten Sie die Arbeitsanweisungen des Kapitels 4.5
der Handreichung „Wissensverarbeitung mit PROLOG“
37
PROL G
© G. Noll 2001
Die Liste ist die zentrale Datenstruktur in PROLOG.Sie besteht aus einer Folge beliebiger Elemente
liste([ ]).
liste([Kopf | Rest]) :- liste(Rest).
Listen
Beispiele: [a,b,c] [a,b,[c,d]] /*geschachtelte Liste*/
[ ] /* leere Liste */
38
PROL G
© G. Noll 2001
Listenstruktur
?- [a,b,c,d] = [K | Rs]. /* Rs Listenvariable */
K = a
Rs = [b,c,d]
Die Zerlegung einer Liste in Kopf und Rest ist sehr flexibel:
[rhein,ahr,mosel] = [rhein | [ahr,mosel] ] =[rhein,ahr | [mosel]] = [rhein,ahr,mosel | [ ] ]
39
PROL G
© G. Noll 2001
Listenoperationen
member/2
/* member(X,Xs) X ist Element der Liste Xs */
member(X,[X|Ls]).
member(X,[Y|Xs]) :- member(X,Xs).
Listen sind rekursive Datenstrukturen. Dementsprechend sind auch die Operationen auf Listen rekursiv erklärt.
40
PROL G
© G. Noll 2001
member/2
als Zugehörigkeitstest ?- member(c,[a,b,c]). Antwort: yes ?- member(e,[a,b,c]). Antwort: no
zur Erzeugung aller Elemente einer Liste?- member(X,[a,b,c]). Antwort: X=a; X=b; X=c; no
zur Erzeugung von Listen, die ein bestimmtes Element enthalten?- member(a,Ls). Antwort: Ls = [a|Rs_2]; Ls = [X_2,a|Rs_3]; Ls = [X_3,X_3,a|Rs_4]
Wir können member/2 auf dreierlei Arten verwenden
41
PROL G
© G. Noll 2001
laenge/2 - append/3
laenge([ ],0).laenge([X|Xs],N) :- laenge(Xs,N1), N is N1+1.
append/3
/* append(Xs,Ys,Es) die Liste Es ist die Verkettung von Xs und Ys*/
append([ ],Ls,Ls).append([X|Xs],Ys,[X|Es]) :- append(Xs,Ys,Es).
laenge/2
/* laenge(Xs,N) die Liste Xs hat N Elemente */
42
PROL G
© G. Noll 2001
delete/3 - insert/3
delete(X,[X|Ls],Ls).delete(X,[Y|Ys],[Y|Es]) :- delete(X,Ys,Es).
insert/3
/* insert(X,Xs,Es) die Liste Es ist die Liste Xs mit eingefügtem X*/
insert(X,Xs,Es) :- delete(X,Es,Xs).
delete/3
/* delete(X,Xs,Es) Es ist die Liste Xs ohne das Element X */
43
PROL G
© G. Noll 2001
Beispiel für insert/3
Die Anfrage verlangt den Beweis von delete(3,Es,[1,2])
Die erste delete-Klausel delete(X,[X|Ls],Ls) passt dazu mit den Instantiierungen X 3, Ls [1,2] und damit Es [3|[1,2]]
Als Ergebnis wird somit Es = [3,1,2] ausgegeben
Wie verarbeitet PROLOG die Anfrage insert(3,[1,2],Es) ?
insert(X,Xs,Es) :- delete(X,Es,Xs).
44
PROL G
© G. Noll 2001
Ablaufsteuerung
max(X,Y,X) :- X >= Y. /* X = max(X,Y) */max(X,Y,Y) :- X < Y. /* Y = max(X,Y) */
Das Systemprädikat ! („Cut“) verhindert die Suche nach alternativen Lösungen
über nachfolgende Klauseln des gerade bearbeiteten Prädikatsüber Ziele des Regelkörpers, die vor dem Cut stehen
Bei der Bearbeitung einer Anfrage führt PROLOG automatisch Backtracking durch, wenn dies zur Erfüllung des Ziels erforderlich ist. Manchmal ist dies aber nicht notwendig oder nicht gewünscht.
45
PROL G
© G. Noll 2001
Bei Verwendung des Cut erhalten wir je nach Klauselreihenfolge eventuell verschiedene logische Bedeutungen
Probleme mit dem Cut
Bei Programmen ohne Cut spielt die Reihenfolge der Klauseln für die Lösung höchstens hinsichtlich der Effizienz der Lösungssuche eine Rolle
p a b a c
p c a b
p :- a, !, b.p :- c.
p :- c.p :- a, !, b.
46
PROL G
© G. Noll 2001
Verneinung
Neben den logischen Standardverknüpfungen UND und ODER gibt es das Systemprädikat NOT/1
not(X) :- X, !, fail. /* X ist beweisbar */not(X). /* X ist nicht beweisbar */
Die Verwendung von not/1 ist nicht unproblematisch:frau(else). frau(petra). mann(peter). mann(frank).
?- not frau(karin). ?- mann(heinz).
Antwort: yes Antwort: no „closed world assumption“
47
PROL G
© G. Noll 2001
Übung 5
Laden Sie das „Inssort“-Programm. Stellen Sie geeignete Anfragen und analysieren Sie die Prädikate insertsort/2 und fuege_ein/3
Laden Sie das „Menue“-Programm. Stellen Sie geeignete Anfragen und analysieren Sie die Prädikate start/0 und null_auffuellen/1
48
PROL G
© G. Noll 2001
start :- reconsult('menue.dtb'), write('Menues unter 20 DM'),nl, write('-----------------------------'),nl, write('Gregor Noll 2001'),nl,nl,nl, menue(V,H,N,DM,Pf), DM<20, write(V),tab(15),write(H),tab(15),write(N),tab(15),write(DM),write(','),write(Pf), null_auffuellen(Pf), tab(15),write('DM'),nl, nl, fail.
Startprädikat
Querydatei für die Datenbasis menue.dtb
null_auffuellen(Pf) :- Pf=0,!, write('0').null_auffuellen(Pf).
49
PROL G
© G. Noll 2001
start :- L=[-2,22,1,10,-3,4,2,-1,5,9,4,32], nl,nl,nl,nl,nl, write('Insertsort '),nl,nl, write(L),nl,nl, insertsort(L,S), write(S),nl,nl, fail.
Sortieren
Sortieren durch Einfügen
insertsort([ ],[ ]).
insertsort([X|Rest],Sortiert) :-
insertsort(Rest,Sortierter_Rest),fuege_ein(X,Sortierter_Rest,Sortiert).
fuege_ein(X,Sortierter_Rest,Sortiert).
fuege_ein(X,[Y|Sortiert],[Y|Sortiert1]) :- X>Y,!, fuege_ein(X,Sortiert,Sortiert1).
fuege_ein(X,Sortiert,[X|Sortiert]).
50
PROL G
© G. Noll 2001
Endliche Automaten
Laden Sie das Programm „Akzeptor“ und analysieren Sie seine Funktionsweise
Laden Sie das Programm „RightShi“ und analysieren Sie seine Funktionsweise
Mit PROLOG lassen sich besonders durchsichtige Simulationsprogramme für endliche Automaten schreiben
51
PROL G
© G. Noll 2001
Akzeptor
start :- akzeptiert ([a,b,a,b,a,b,a]),!,fail.
akzeptiert(W) :-
nl,schreibe(W), startzustand(S), akzeptiert(S,W), write(' <--- Wort akzeptiert'),nl,nl, !,fail.
akzeptiert(W) :-
write(' <--- Wort nicht akzeptiert'),nl,nl. akzeptiert(S,[K|Rs]) :-
pfeil(S,K,S1),
akzeptiert(S1,Rs).
akzeptiert(S,[ ]) :-
endzustand(S).
startzustand(s). endzustand(s). pfeil(s,a,r). pfeil(r,b,s).
s r
a
b
schreibe([K|Rs]) :- write(K), schreibe(Rs). schreibe([ ]).
52
PROL G
© G. Noll 2001
Right - Shifter
start :- nl,write('RIGHT-SHIFTER'),nl,nl,transduktor([1,0,1,1,0,1,0]),!,fail.
transduktor(Eingabe) :-schreibe(Eingabe),write(' ---> '),startzustand(S),transduktor(S,Eingabe).
transduktor(Zustand,[E|Rest]) :-pfeil(Zustand,E,A,Neuer_Zustand),write(A),transduktor(Neuer_Zustand,Rest).
transduktor(S,[ ]) :- nl,nl.
startzustand(s). pfeil(s,0,0,n). pfeil(s,1,0,e).pfeil(n,0,0,n). pfeil(n,1,0,e).pfeil(e,0,1,n). pfeil(e,1,1,e).
schreibe([K|Rs]) :- write(K), schreibe(Rs). schreibe([ ]).
e
s
1,0
n0,0
0,11,0
1,1
0,0
53
PROL G
© G. Noll 2001
Literatur
Wissensverarbeitung mit PROLOGHandreichung zum Lehrplan InformatikKoblenz 1995 (LMZ)informatikag.bildung-rp.de
Bothe,K. / Stojanow,St.Praktische Prolog-ProgrammierungBerlin 1991 (ISBN 3-341-01035-7)
Göhner,H. / Hafenbrak,B.Arbeitsbuch PROLOGBonn 1991 (ISBN3-427-46861-5)