Zum Inhalt springen

Prolog (Programmiersprache)

Dies ist ein als lesenswert ausgezeichneter Artikel.
aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 4. April 2005 um 15:16 Uhr durch Zahnstein (Diskussion | Beiträge). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Prolog („Programming in Logic“) ist eine Programmiersprache, die maßgeblich von Alain Colmerauer, einem französischen Informatiker, Anfang der 1970er Jahre entwickelt wurde und zur Familie der logischen Programmiersprachen zählt. Sie ist eine Vertreterin des Paradigmas der deklarativen Programmierung.

Man kann die Sprache als "Maschinensprache eines Logik-Prozessors" bezeichnen, da sie auf den mathematischen Grundlagen der Prädikatenlogik beruht. Ein Prolog-Programm ist eine Sammlung von so genannten Horn-Klauseln.

Grundprinzip

Prolog-Programme bestehen aus einer Datenbasis, die Fakten und Regeln umfasst. Der Benutzer formuliert Anfragen an diese Datenbasis. Der Prolog-Interpreter benutzt die Fakten und Regeln, um systematisch eine Antwort zu finden. Ein positives Resultat bedeutet, dass die Antwort logisch ableitbar ist. Ein negatives Resultat bedeutet nur, dass aufgrund der Datenbasis keine Antwort gegeben werden kann. Dies hängt eng mit der Closed world assumption zusammen (siehe unten).

Das typische erste Programm in Prolog ist nicht wie in prozeduralen Programmiersprachen ein Hallo-Welt-Beispiel, sondern eine Datenbasis mit Stammbauminformationen.

Folgendes Beispiel repräsentiert den Stammbaum einer kleinen Familie. Die Aussage mann(tobias) liest sich als: Tobias ist ein Mann. vater(tobias, frank) wird hier verwendet als: Tobias ist der Vater von Frank. 

   mann(adam).
   mann(tobias).
   mann(frank).
   frau(eva).
   frau(daniela).
   frau(ulrike).
   vater(adam,tobias).
   vater(tobias,frank).
   vater(tobias,ulrike).
   mutter(eva,tobias).
   mutter(daniela,frank).
   mutter(daniela,ulrike).

In einem Prolog-Interpreter können nun interaktiv Anfragen an die Datenbasis gestellt werden. Das Ausführen eines Prolog-Programms bedeutet immer das Stellen einer Anfrage. Das System antwortet entweder mit yes. oder no., abhängig davon, ob die Anfrage bewiesen werden konnte, oder es gibt zusätzlich eine Liste von Variablenbelegungen an. Variablen sind in Prolog alle Token, die mit einem Großbuchstaben beginnen. Beispiel: 

   ?- mann(tobias).
   yes.
   ?- mann(heinrich).
   no.
   ?- frau(X).
   X=eva ;
   X=daniela ;
   X=ulrike ;
   no. (keine weiteren Antworten).

Das System kann nur positive Antworten zu Anfragen geben zu denen es Fakten in der Datenbasis vorliegen hat. Wenn etwas fehlt ist die Antwort no (nein), die bedeutet, dass aufgrund der Datenbank nichts ableitbar ist (Closed world assumption). Im Beispiel oben ist dies durch die Anfrage 

   ?- mann(heinrich).
   no.

illustriert (heinrich kann in der Datenbasis nicht gefunden werden).

Zusätzlich zu der Möglichkeit, Fakten zu spezifizieren, bietet Prolog die Möglichkeit, Regeln zu formulieren. Der Regeloperator :- ist dabei wie ein umgedrehter Implikationspfeil zu lesen. Beispiel: 

   grossvater(X,Y) :-
       vater(X,Z),
       vater(Z,Y).

Die Regel besagt: X ist Großvater von Y, wenn es ein Z gibt, so dass X Vater von Z ist und Z Vater von Y. Damit ist der Großvater väterlicherseits definiert. Eine zweite Regel für den Großvater mütterlicherseits sieht so aus: 

   grossvater(X,Y) :-
       vater(X,Z),
       mutter(Z,Y).

Regeln mit gleichem Head, das heißt gleichem Term vor dem Regeloperator, werden als oder-verknüpfte Alternativen betrachtet. Jetzt sind Anfragen wie die folgenden möglich: 

   ?- grossvater(adam,ulrike).
   yes.
   ?- grossvater(X,frank).
   X=adam

Weitere Techniken

Entscheidend für die Prolog-Programmierung sind die Techniken der Rekursion und die Nutzung von Listen.

Ist die Rekursion in den meisten Programmiersprachen nur eine zusätzliche Variante zur Iteration, ist sie bei der Prolog-Programmierung die einzige Möglichkeit, "Schleifen" zu produzieren. Benötigt man in obigem Beispiel eine allgemeine "Vorfahr"-Relation, wird das wie folgt realisiert: 

   vorfahr(X,Z) :-
       elternteil(X,Z).
  
   vorfahr(X,Z) :-
       elternteil(X,Y),
       vorfahr(Y,Z).

Dies lässt sich wie folgt lesen: X ist ein Vorfahr von Z, wenn entweder X Elternteil von Z ist (Regel 1) oder es ein Y gibt, das Vorfahr von Z ist und gleichzeitig X Elternteil von Y (Regel 2) (Es wurde hier elternteil statt mutter und vater verwendet. elternteil(X,Y) :- mutter(X,Y), vater(X,Y).).

Auch Listen sind ein entscheidender Bestandteil von Prolog. Die meisten Prolog-Implementationen bringen dafür viele Funktionen mit (Anhängen von Werten, Anzahl der Werte, etc.), die sich aber auch alle selbst bauen lassen. In einer gedachten Familienstruktur muss die Anzahl der Kinder ja variabel sein. Folgendes wäre denkbar: 

   familie(heinz,jutta,[peter,laura]).
   familie(karl,gertrud,[]).

Dann ließen sich z.B. mit einer Abfrage alle Familienväter ohne Kinder anzeigen: 

   ?- familie(X, _, []).
   X=karl

Beispiel

Ein Beispiel für die Anwendung ist z.B. das Lösen eines mathematischen Rätsels: 

 ABB -  CD = EED
  -     -     *
  FD +  EF =  CE
  =     =     =
 EGD *  FH = ???

A bis H stehen jeweils für eine Ziffer 0 bis 9, wobei nicht klar ist, welche Zahl an welchen Buchstaben gebunden ist. Gesucht ist die Zahl, die bei den Fragezeichen stehen muss. Dieses Problem ist in Prolog sehr einfach zu lösen. Man schreibt zunächst eine Regel, die bewirkt, dass A bis H später mit allen möglichen Kombinationen von 0 bis 9 belegt werden (Permutation): 

 gen(A,B,C,D,E,F,G,H) :- permutation([A,B,C,D,E,F,G,H,_,_],[0,1,2,3,4,5,6,7,8,9]).

Nun muss man nur die fünf entstehenden Gleichungen (ABB - CD = EED, FD + EF = CE, ABB - FD = EGD, CD - EF = FH und EED * CE = EGD * FH = X) in Prolog-Syntax schreiben: 

 gl1(A,B,C,D,E) :- ((A * 100 + B * 10 + B) - (C * 10 + D)) =:= (E * 100 + E * 10 + D).
 gl2(C,D,E,F) :- ((F * 10 + D) + (E * 10 + F)) =:= (C * 10 + E).
 gl3(A,B,D,E,F,G) :- ((A * 100 + B * 10 + B) - (F * 10 + D)) =:= (E * 100 + G * 10 + D).
 gl4(C,D,E,F,H) :- ((C * 10 + D) - (E * 10 + F)) =:= (F * 10 + H).
 gl5(C,D,E,F,G,H,X) :- ((E * 100 + E * 10 + D) * (C * 10 + E)) =:= 
     ((E * 100 + G * 10 + D) * (F * 10 + H)), X is ((E * 100 + G * 10 + D) * (F * 10 + H)).

Wenn einen nur X interessiert legt man sich eine Lösungsregel an, die alles zusammenführt und X ausgibt: 

 loesung :- gen(A,B,C,D,E,F,G,H), gl1(A,B,C,D,E), gl2(C,D,E,F),
     gl3(A,B,D,E,F,G), gl4(C,D,E,F,H), gl5(C,D,E,F,G,H,X), write(X).

Gibt man nun die Abfrage loesung. ein, wird die Lösung ausgegeben. Wie man sieht, benötigt man zur Lösung dieses Problems fast keine Programmierkenntnisse über Schleifen oder ähnliches, sondern gibt nur die Fakten ein und welches Ergebnis man benötigt. Prolog steht in der Abstraktionshierarchie aus genau diesem Grund über imperativen und objektorientierten Sprachen.

Definite Clause Grammar

Um Regeln für Parser zu schreiben haben die meisten Prologsysteme einen Präprozessor implementiert, der es erlaubt, die Regeln in einer lesbareren Form zu notieren, die in der Form den Regeln entsprechen, die man verwendet um kontextfreie Sprache zu beschreiben. Der Präprozessor ergänzt Platzhalter und erzeugt die oben erwähnten Prolog-Logik-Formeln.

Referenz: http://www.cs.sunysb.edu/~warren/xsbbook/node10.html

Anwendungsgebiete

In den 1980er Jahren spielte die Sprache eine wichtige Rolle beim Bau von Expertensystemen. Die Sprache wird auch heute noch in den Bereichen Computerlinguistik und Künstliche Intelligenz verwendet.

Siehe auch

Literatur

  • Clocksin, William F; Mellish, Christopher S.: Programming in Prolog. Springer, Berlin, 2003, ISBN 3-540-00678-8
  • Sterling, Leon; Shapiro, Ehud: The Art of Prolog. Advanced Programming Techniques. MIT Press, Cambridge, 1994, ISBN 0-262-69163-9
  • Bratko, Ivan: Prolog Programming for Artificial Intelligence. Addison-Wesley, Bonn, 2000, ISBN 0-201-40375-7
  • Bratko, Ivan: Prolog. Programmierung für Künstliche Intelligenz. Addison-Wesley, Bonn, 1987, ISBN 3-925118-63-2
  • Clocksin, William F: Clause and Effect. Prolog Programming for the Working Programmer. Springer, Berlin, 2005, ISBN 3-540-62971-8
  • Schöning, Uwe: Logik für Informatiker. Spektrum, Heidelberg, 2000, ISBN 3-8274-1005-3

Tutorials und Kurse

Interpreter und Werkzeuge

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Prolog_(Programmiersprache)&oldid=5521369“