Kurze Einf"uhrung in Prolog (F.R. 10.11.95) =========================================== 1. Was ist Prolog? ----------------- Um Prolog zu verstehen, m"ussen ein paar S"atze zur Logikprogrammierung gesagt werden. Die Logikprogrammierung hat ihre Anf"ange in den fr"uhen siebziger Jahren. Sie wurde im wesentlichen von Kowalski [Kowalski 1974] und Colmerauer eingef"uhrt. Die theoretischen Grundlagen der Logikprogrammierung gehen auf Arbeiten des Logikers Herbrand [Herbrand 1930] zur"uck. Herbrand benutzte eine eingeschr"ankte Form der Pr"adikatenlogik erster Stufe, die sogenannte Horn-Logik, um Fragen der Berechenbarkeit von Funktionen zu studieren. Die Horn-Logik l"a"st nur spezielle pr"adikatenlogische Formeln zu, die sogenannten Hornklauseln (positiv definite Klauseln). Die Horn-Logik wurde durch die Erfindung des Resolutionsprinzips durch Robinson [1965 Robinson] auch f"ur den praktischen Einsatz interessant. Die fundamentale Idee von Kowalski und Colmerauer war, die Horn-Logik als Programmiersprache zu verwenden, wobei das Prinzip der Resolution den essentiellen Mechanismus der operationellen Semantik von Logikprogrammen darstellt. Kurz gesagt ist der Grundgedanke von PROLOG: PROgramming in LOGic Die klassische Einf"uhrung in die Programmierung in Prolog findet sich im Buch [Clocksin,Mellish]. 2. Wie programmiert man in Prolog? ---------------------------------- In Prolog formulieren wir einen Algorithmus, indem wir Objekte einf"uhren und verschiedene Relationen beschreiben, die zwischen den Objekten bestehen. Betrachten wir dazu die Aufgabe 1 auf dem "Ubungsblatt 1. V = {(s0, s1), (s1, s0), (s1, s2), (s2, s1), (s2, s3), (s2, s4), (s3, s2), (s3, s4), (s4, s2), (s4, s3)} Die zweistellige Relation V wird durch die Aufz"ahlung aller Paare beschrieben, die in Relation zueinander stehen. Wir legen also durch Aufz"ahlung fest, welche Paare in V sind. In Prolog spricht man hierbei von `Fakten'. Eine Prolog Notation f"ur obige Aufz"ahlung w"are etwa: Fakten: ======= v1rel(s0, s1). v1rel(s1, s0). v1rel(s1, s2). v1rel(s2, s1). v1rel(s2, s3). v1rel(s2, s4). v1rel(s3, s2). v1rel(s3, s4). v1rel(s4, s2). v1rel(s4, s3). Dadurch teilen wir Prolog mit, da"s wir eine zweistellige Relation v1rel definieren. F"ur die Namensgebung ist unter anderem wichtig, da"s Relationennamen klein geschrieben werden und alphanumerische Bezeichner verwendet werden. Die Syntax f"ur Elemente ist etwas freiz"ugiger, jedoch d"urfen keine gr"o"sen Anfangsbuchstaben verwendet werden. Namen, die mit Gro"sbuchstaben beginnen, sind Variablennamen!!! (dazu sp"ater mehr) Durch die Zeile v1rel(s0, s1). teilen wir Prolog einen Fakt mit. Der Punkt nach v1rel(s0, s1) ist wichtig. Mit obiger Aufz"ahlung haben wir unser erstes Prologprogramm geschrieben. Nehmen wir an, da"s die Aufz"ahlung in der Datei `einfuehrung.pl' steht. Wir starten das Prologsystem mit dem Befehl eclipse und geben dann folgenden Befehl ein [einfuehrung]. Das System liest dann die Datei einfuehrung.pl ein und erf"ahrt so etwas "uber unsere Definition der Relation v1rel. Nun k"onnen wir das System "uber die Relation v1rel befragen. Stellen wir die Frage v1rel(s2, s3). (der Punkt ist wichtig), antwortet das System mit yes Stellen wir hingegen die Frage v1rel(s2, s2). so antwortet das System mit no (more) solution. Eine solche Anfrage hei"st im Prolog-Jargon Ziel (goal) oder Anfrage (question, query). Wie macht das Prologsystem das? ------------------------------- Prolog hat unsere Datei einfuehrung.pl gelesen und die Fakten in einer internen Datenbank abgespeichert. Wir stellen nun die Anfrage v1rel(s2, s3). am Systemprompt. Daraufhin geht Prolog Schritt f"ur Schritt die Datenbank durch und vergleicht die vorhandene Fakten mit unserer Anfrage. Pa"st ein Fakt, so gibt das System `yes' aus, andernfalls `no'. Variablen, Matching: ==================== Das ist bisher nicht sehr spannend! Nun wollen wir wissen, welche St"adte si mit der Stadt s3 in Relation v1rel stehen. Wir stellen die Anfrage v1rel(s3,X). Prolog erkennt an der Schreibweise, da"s X eine Variable sein soll. Das System antwortet X = s2 More? (;) Wir tippen `;' ein, und das System antwortet X = s4 yes. Prolog ist wieder die einzelnen Fakten durchgegangen (in Aufschreibungsreihenfolge). Es teilt uns (nach Aufforderung mit `;') alle Belegungen der Variablen X mit, f"ur die v1rel(s3,X) aus unserer Datenbank ableitbar ist. Dabei hat Prolog versucht, die Variable X in unserer Anfrage mit den Konstanten si aus unseren Fakten zur Deckung zu bringen. Man spricht von `Matching'. Regeln, Rekursion: ================== Wenn wir unsere Relation v1rel genauer betrachten f"allt uns auf, da"s v1rel symmetrisch ist. Wenn also v1rel(si,sj) gilt, dann gilt auch v1rel(sj,si). Dies k"onnen wir auch Prolog miteilen. Wir schreiben unser Programm einfuehrung.pl um bzw. "andern es ab, indem wir folgende Fakten v2rel(s0, s1). v2rel(s1, s2). v2rel(s2, s3). v2rel(s2, s4). v2rel(s3, s4). und die `Regel' v2rel(Y,X):- v2rel(X,Y). spezifizieren. Mit Fakten kennen wir uns bereits aus. Die Regel v2rel(Y,X):- v2rel(X,Y). ist folgenderma"sen zu lesen: Wenn wir wissen, da"s v2rel(X,Y), dann wissen wir auch da"s v2rel(Y,X) Oder anders ausgedr"uckt: Um abzuleiten, da"s v2rel(Y,X) gilt, gen"ugt es zu zeigen, da"s v2rel(X,Y) gilt. Hier sehen wir das erste mal einen Hauch von Logik in unserem Prologprogramm aufscheinen. Weiterhin haben wir nun durch die Regeln eine Rekursion eigebaut. Um mit Hilfe der Regel etwas "uber die Relation v2rel abzuleiten, benutzen wir schon Information "uber die Relation v2rel. Stellen wir die Anfrage v2rel(s4, s2). so findet das System die Antwort auf unsere Anfrage nicht, indem es nur die ihm bekannten Fakten "uber die Relation v2rel pr"uft. Es mu"s auch die Symmetrie-Regel benutzen, die wir zus"atzlich angegeben haben. Beide Versionen unserer Beschreibung der Relation V sind gleichwertig. Fakten und Regeln zusammen nennt man in der Logik (Horn-)Klauseln. Wenn Prolog versucht, unsere Anfrage v2rel(s4, s2) mit Hilfe der Symmetrieregel zu beantworten f"uhrt es wieder Matching durch, diesmal aber in umgekehrter Richtung. Es versucht die Konstanten s4 und s2 in unserer Anfrage mit den Variablen X und Y in unserer Regel zur Deckung zu bringen. Genauer gesagt matcht es s4 mit Y und s2 mit X. Dies gelingt, und gem"a"s der Regel versucht es dann v2rel(s2,s4) abzuleiten. Dies gelingt mit Hilfe der Fakten. Unifikation: ============ Nun kommt eine weitere Steigerung! Wir stellen die Anfrage v2rel(s4, Z). Auch hier mu"s die Symmetrieregel benutzt werden. Das System antwortet: Z = s2 More? (;) Wir verlangen mit Eingabe ; weitere L"osungen Z = s3 More? (;) Z = s2 More? (;) Z = s3 More? (;) Z = s2 More? (;) Z = s3 More? (;) Z = s2 More? (;) ... Zwei Dinge sind zu erw"ahnen. a. Das System mu"s bei Anwendung der Symmetrieregel in beiden Richtungen matchen v2rel(s4, Z) mit v2rel(Y,X) Man spricht von Unifikation. Welche Belegung der Variablen X,Y,Z macht die beiden Ausdr"ucke gleich (unifiziert sie)? Unifikationsprobleme und Algorithmen f"ur ihre L"osung treten in vielen Bereichen der Informatik auf. Beispiele sind die automatische Typinferenz in funktionalen Sprachen oder das Finden von passenden Inferenzregeln in Theorembeweisern. Im Fall von Prolog ist das Unifikationsp roblem noch relativ einfach, und es gibt Unifikationsalgorithmen, die vollst"andig und korrekt sind (Stichwort: allgemeinster Unifikator). b. Das System generiert zyklisch die Antworten Z = s2 More? (;) Z = s3 More? (;) Das liegt daran, da"s beim Herleitungsversuch f"ur v2rel(s4, Z) beliebig oft die Symmetrieregel verwendet werden kann. Die Rekursion terminiert nicht. Prolog bietet die M"oglichkeit, solche Merfachberechnung von L"osungen zu verbieten (Stichwort: cut !). Durch Verwendung des cut verl"a"st man aber die reine logische Programmierung. Wir gehen nicht n"aher darauf ein. 3. Standard-Datentypen in Prolog; Listen ---------------------------------------- Bisher haben wir nur Konstanten (s1,s2,...) f"ur Individuen und Variablen (X,Y,Z..) betrachtet. Nun besch"aftigen wir uns mit dem Datentyp der Listen. "Uber diesem Datentyp lassen sich viele interessante rekursive Funktionen programmieren bzw. in Prolog induktiv Relationen spezifizieren. Wichtig: In Prolog m"ussen alle Funktionen f(x) = E(x) als Relationen f-rel(x,E(x)) programmiert werden. Notation f"ur Listen: [] bezeichnet die leere Liste [x1,...,xn] bezeichnet die endliche Liste der Elemente x1 bis xn [c|XS] bezeichnet die Liste, die mit dem Element c angeht und von einer Restliste XS gefolgt wird (Pattern in Klauselk"opfen) bzw. Konkatenation zur Bildung neuer Listen. Ein erstes Programm mit Listen; Test auf Vorkommen isin: -------------------------------------------------------- Wir wollen ein Programm schreiben, das testet ob ein Element in einer Liste enthalten ist. In Prolog m"ussen wir unsere Aufgabe relational ausdr"ucken. Wir definieren die Relation isin: Elm x Elm List zwischen Elementen und Listen, die ein Element x mit einer Liste L genau dann in Relation setzt, wenn x in L vorkommt. In Prolog geht das folgenderma"sen: isin(X,[X|YS]). isin(X,[Y|YS]):- isin(X,YS). Die erste Regel (Klausel) fragt ab, ob die Liste gerade mit dem Element beginnt, auf dessen Enthaltensein wir testen. Die zweite Regel pr"uft, ob das Element in der Restliste vorkommt (Rekursion). Eine Anfrage isin(x,[y,x,x]). veranla"st das System zur Antwort `yes.' Die Anfrage isin(x,[y,y,y]). f"uhrt zur Antwort `no (more) solution.' Wir k"onnen aber auch folgende Anfrage stellen: isin(Z,[y,x,x]). F"ur welche Belegung der Variablen Z ist die Relation isin erf"ullt? Das System antwortet mit Z = y More? (;) Z = x More? (;) Z = x More? (;) no (more) solution. Hier sehen wir einen ganz neuen Aspekt der Kodierung von Funktionen als Relationen. Relationen sind nicht gerichtet, und somit k"onnen wir die Menge aller Urbilder einer Funktion erfragen. Diese Umkehrung von Funktionen ist nur m"oglich, wenn keine schmutzigen `unlogischen' Konstrukte wie der cut in Programmen benutzt werden. 4. Noch mehr Listenprogramme ============================ % append von Listen append([],L,L). append([X|L1],L2,[X|L3]):-append(L1,L2,L3). % Alle Vorkommen eines Elements aus einer Liste streichen del(X,[],[]). del(X,[X|XS],Z):- del(X,XS,Z). del(X,[Y|XS],[Y|Z]):- X \= Y, del(X,XS,Z). % Alle Duplikate aus einer Liste streichen squeeze([],[]). squeeze([X|XS],[X|Z]):- del(X,XS,Z1), squeeze(Z1,Z). % direktes Bild einer Menge M unter Relation R % Menge und Relation als Listen kodiert % Bild eines einzelnen Elements dom1(X,[],[]). dom1(X,[(X,Y)|R],[Y|Z]):- dom1(X,R,Z). dom1(X,[(W,Y)|R],Z):- X \= W, dom1(X,R,Z). % Wende dom1 auf ganze Menge an dom2([],_,[]). dom2([X|XS],R,Z):- dom1(X,R,B), dom2(XS,R,BS), append(B,BS,Z). % mach Duplikate raus dom(L,R,Z):- dom2(L,R,Z1),squeeze(Z1,Z). % die Relation V als Liste vrel([(s0, s1),(s1, s0),(s1, s2),(s2, s1),(s2, s3),(s2, s4), (s3, s2),(s3, s4),(s4, s2),(s4, s3)]). Ein paar Anfragen: - vrel(R), dom1(s0,R,Z). R = [(s0, s1), (s1, s0), (s1, s2), (s2, s1), (s2, s3), (s2, s4), (s3, s2), (s3, s4), (s4, s2), (s4, s3)] Z = [s1] More? (;) - vrel(R), dom1(s2,R,Z). R= ... Z = [s1, s3, s4] More? (;) - vrel(R), dom2([s1,s3],R,Z). R = ... Z = [s0, s2, s2, s4] More? (;) - vrel(R), dom([s1,s3],R,Z). R = ... Z = [s0, s2, s4] More? (;) ======================================================================= Literatur: [Clocksin,Mellish 1984] Clocksin,Mellish, Programming in Prolog, Springer 1984, 2nd Edition [Herbrand 1930] Researches in the Theory of Demonstrations. In From Frege to G"odel: A Source Book in Matehmatical Logic, 1979-1931 Harvard MA: Harvard University [Kowalski 1974] Predicate logic as a Predicate Logic, IFIP 74 [Robinson 1965] A Machine-Oriented Logic Based on the Resolution Principle. JACM, 12(1),23-41