Was ist PROLOG?

Einführung in PROLOG
Christian Stocker
Inhalt
●
●
Was ist PROLOG?
Der PROLOGInterpreter
–
–
●
Welcher Interpreter?
SWI-Prolog
Syntax
–
–
–
–
–
–
Einführung
Fakten, Regeln,
Anfragen
Operatoren
Rekursion
Listen
Cut
●
Funktionsweise
–
–
●
●
So arbeitet Prolog
Warrens Abstrakte
Maschine
Codebeispiele
Zusammenfassung
Was ist PROLOG? (1)
●
●
●
●
●
●
●
PROLOG = Programming in Logic
1972 von Alain Colmerauer entwickelt
Keine prozedurale Programmiersprache
sondern eine deklarative mit prozeduralen
Elementen
Nichtlineares Programmieren wird betrieben
„Maschinensprache des Logikprozessors“
Prolog wird Interpretiert
Interpreter erstmals in LISP programmiert
Was ist PROLOG? (2)
●
●
●
●
Prolog-Programm besteht nur aus
Datenbasis
Es wird beschrieben, WAS das Problem ist,
nicht jedoch wie dieses zu lösen ist
Arbeitet auf Prädikatenlogik
Prolog-Programm ist Sammlung von
Hornklauseln
Der PROLOG-Interpreter(1)
●
SWI-Prolog
–
–
–
●
Gnu-Prolog
–
–
–
●
●
●
Wird hier für Beispiele benützt
Für Windows, Linux und MacOS verfügbar
www.swi-prolog.org
Für Constraint Programming besser geeignet
Für Windows und Linux verfügbar
http://pauillac.inria.fr/~diaz/gnu-prolog/
Qu-Prolog
Minerva
SICStus Prolog
SWI-Prolog(1)
●
●
●
●
●
●
●
Leistungsfähiger Prolog-Interpreter
Entwickelt auf Uni Amsterdam
Freeware
Sehr große Bibliothek
Installationen für Windows, Linux und
MacOS verfügbar
Integrierter Debugger
Basiert auf einer eingeschränkten Version
der Warren Abstract Machine
SWI-Prolog(2)
●
●
●
●
●
●
Start auf Shell mit pl
Prolog-Files mit Texteditor schreiben
Programm im Interpreter öffnen:
[name]. Oder consult(name).
Anfrage aus Interpreter stellen
Interpreter beenden:
halt.
Hilfe mit help(Topic) oder
apropos(Topic)
Syntax
●
●
●
●
●
●
Einführung
Fakten, Regeln, Anfragen
Operatoren
Rekursion
Listen
Cut
Syntax/Einführung
●
●
●
●
Prolog Statements werden immer mit Punkt
(.) abgeschlossen
Prädikate und Konstanten werden klein
geschrieben
Variablen beginnen mit Großbuchstaben
Unterscheidung zwischen
–
–
–
●
●
Fakten
Regeln
Anfragen
Einzeilige Kommentare: % <Comment>
Mehrzeilige: /* <Comment> */
Syntax/
Fakten, Regeln, Anfragen
●
Fakten
–
–
–
–
–
Beispiel: „John ist männlich“:
maennlich(john).
Beispiel: „John mag Mary“:
mag(john,mary).
Ein Fakt besteht aus einem Prädikat und dessen
Argumenten. Die Anzahl der Argumente
beschreibt die Stelligkeit
Ein Fakt kann beliebig viele Argumente haben
Ein Fakt muss immer mit einem Kleinbuchstabe
beginnen
Syntax/
Fakten, Regeln, Anfragen
●
Regeln
–
–
–
–
–
Regeln drücken die Abhängigkeit eines Faktums
von einem oder mehreren anderen Fakten aus
Bsp: „Mary mag jeden, der Wein mag“
mag(mary,X) :- mag(X,wein).
:- kann als umgedrehter Implikationspfeil
gelesen werden
Die linke Seite ist wahr, wenn die rechte Seite
bewiesen werden kann
X ist eine Variable, mary und wein sind
Konstanten
Syntax/
Fakten, Regeln, Anfragen
●
Regeln
–
–
–
–
–
Ein Komma zwischen zwei Fakten auf der
rechten Seite entspricht einer logischen UND
Verknüpfung
Ein Semikolon entspricht einem logischen ODER
Bsp: eltern(X,Y) :- vater(X,Y);
mutter(X,Y).
opa(X,Y) :- vater (X,Z), vater(Z,Y).
Mit not kann eine Klausel verneint werden
mann(X) :- not frau(X).
Regeln müssen als Hornklauseln formuliert
werden.
Syntax/
Fakten, Regeln, Anfragen
●
Anfragen
–
–
–
–
–
Anfragen werden im Prolog-Interpreter gestellt
Beispiel: „Ist John männlich?“
?- maennlich(john).
Interpreter antwortet mit yes, wenn dies
Beweisbar ist.
Beispiel: „Wen mag Mary?“
?- mag(mary,X).
Interpreter antwortet mit X=john
Falls es mehrere Antworten gibt, kann mit 'n' die
nächste Antwort angesehen werden.
Syntax/
Fakten, Regeln, Anfragen
●
Anfragen
–
–
–
Analog zu den Regeln können auch hier logische
Verknüpfungen angewandt werden.
'_' steht für ein leeres Argument. Hier ist es
sozusagen egal, was an dieser Stelle gilt.
Beispiel: „Wer mag alles irgendjemanden?“
?- mag(X,_).
Syntax/Operatoren
●
●
●
●
●
●
●
●
●
:==
=:=
\=
>=
=<
is
not
* /
Regeloperator
Gleichheitsoperator
Gleichheitsoperator für Zahlenwerte
Ungleichungsoperator
Größer/Gleich
Kleiner/Gleich
Zuweisungsoperator für Zahlenwerte
Verneinung für Klauseln
+ - Rechenoperationen
Syntax/Rekursion
●
Ohne Rekursion
–
–
–
–
grosselter(X,Y):- elter(X,Z),
elter(Z,Y).
urgrosselter(X,Y):- elter(X,Z),
grosselter(Z,Y).
ururgrosselter(X,Y):- elter(X,Z),
urgrosselter(Z,Y).
urururgrosselter(X,Y):elter(X,Z),ururgrosselter(Z,Y).
Syntax/Rekursion
●
Mit Rekursion
–
●
vorfahr(X,Y) :- elter(X,Y).
vorfahr(X,Y) :- elter(X,Z),
vorfahr(Z,Y).
Rekursion in Prolog analog zu anderen
bekannten Programmiersprachen
Syntax/Listen
●
●
Listen werden durch eckige Klammern
definiert. Listen können Elemente mit
unterschiedlichen Typen aufnehmen.
Beispiele:
–
–
–
–
–
[1,2,3,4,5]
[1,2,3,[4,5]]
[hugo,'Hallo',4,5,mag(john,mary)]
[] leere Liste
[Head|Tail] = [1,2,3,4]
Head=1
Tail=[2,3,4]
Syntax/Listen
●
●
●
Bestimmen der Länge einer Liste
list_length([],0).
list_length([H|T],N) :list_length(T,M),N is M+1.
Prüfen, ob Element in Liste vorhanden
member(E,[E|T]).
member(E,[H,T] :- member(E,T).
Listen anhängen
append([1,2,3],[4,5],Target).
Syntax/Cut
●
●
●
●
Beispiel:
loesung(X):-zahl(X),X =:= 2*X-4.
zahl(1).
zahl(N) :- zahl(M), N is M+1.
Problem: Programm findet zwar Lösung X=4
aber es termiert nicht.
Lösung:
loesung(X):-zahl(X),X=:= 2*X-4,!.
Cut verhindert weiteres Backtracking nach
gefundener Lösung
Funktionsweise
●
●
So arbeitet PROLOG
Warrens Abstrakte Maschine
So arbeitet PROLOG
●
●
●
●
PROLOG vergleicht eine Anfrage der Reihe
nach mit den Fakten aus der Datenbasis.
Eine Variable kann mit jeder Konstante
matchen.
Werden mehrere Ziele benötigt, versucht
Prolog erst das erste und schaut, ob das
nächste Ziel erfüllt werden kann, ansonsten
kommt es zum Backtracking.
Bsp: ?- elter(daisy,X), maennl(X).
Trifft maennl(X) nicht zu, wird X
zurückgesetzt und neu belegt.
Warren's abstrakte Maschine
●
●
●
●
Prolog wird in einen Zwischencode (ähnl.
Java, managed .NET) übersetzt. Dieser
Zwischencode wird von der WAM
interpretiert und ausgeführt.
Die WAM ist eine Virtuelle Machine. Es ist
somit möglich WAM Code auf jeder
Hardware zu betreiben.
In SWI-Prolog arbeitet eine sehr
eingeschränkte WAM.
Literatur: Warren's Abstract Machine a tutorial reconstruction
Beispiele
●
●
●
Ein Familienstammbaum
Einfärben von Flächen
Ein mathematisches Rätsel
Ein Familienstammbaum
Einfärben von Flächen
1
2
4
3
Farben rot, blau, gelb für Einfärbung verfügbar
Ein mathematisches Rätsel
ABB - CD = EED
*
FD + EF = CF
=
=
=
EGD * FH = ???
Zusammenfassung
●
●
Was ist PROLOG?
Der PROLOGInterpreter
–
–
●
Welcher Interpreter?
SWI-Prolog
Syntax
–
–
–
–
–
–
Einführung
Fakten, Regeln,
Anfragen
Operatoren
Rekursion
Listen
Cut
●
Funktionsweise
–
–
●
So arbeitet Prolog
Warrens Abstrakte
Maschine
Codebeispiele
Ende
Unterlagen zum Vortrag auf
/pub/stud/stud/stockerc/prolog/
eMail
[email protected]
(C)2006 Christian Stocker