Was ist PROLOG?
Transcrição
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