Prolog eLearning
Tutorial

1: Fakten, Regeln

Zu den Aufgaben Folien ansehen Musterlösungen herunterladen

Prolog (aus dem franz. Programming en Logique) ist eine logische Programmiersprache, die in den 1970er Jahren von dem Informatiker Alain Colmerauer entwickelt wurde.

Der Ursprung der logischen Programmierung liegt in dem automatisierten Beweisen mathematischer Sätze.

Die logische Programmierung basiert auf der Syntax der Prädikatenlogik erster Stufe (PL1), die in der zweiten Hälfte des 19. Jahrhunderts von Gottlob Frege aufgestellt wurde.

Grundprinzip:

  • Prolog-Programme bestehen aus einer Wissensdatenbank, die aus Fakten und Regeln bestehen.
  • Der Benutzer formuliert Anfragen an die Wissensdatenbank.
  • Prolog versucht mittels bestehender Fakten und Regeln eine Antwort zu finden.
  • Wenn Prolog eine Antwort findet, bedeutet dies, dass die Anfrage logisch ableitbar ist.
  • Der Programmier-Ansatz von Prolog folgt dem deklarativen Programmierparadigma.

Anwendungsgebiete:

  • Entwicklung von Expertensystemen
  • Computerlinguistik
  • künstliche Intelligenz
  • Die Sprachverarbeitungskomponenten des KI-Systems Watson von IBM wurden in Prolog geschrieben.
Watson bei Jeopardy (the IBM Challenge)

Programmierparadigmen

  • Ein Programmierparadigma ist ein fundamentaler Programmierstil/-ansatz.
  • Bei der Programmierung wird zwischen zwei grundlegenden Programmierparadigmen unterschieden: Imperative Programmierung und deklarative Programmierung
  • Einige Sprachen der imperativen Programmierung:
    prozedural (C, Fortran), Objekt-orientiert (C++, Java, Python)
  • Einige Sprachen der deklarativen Programmierung: Abfragesprachen (SQL), funktionale Sprachen (Lisp, Haskell), logische Sprachen (Prolog)

Vergleich der Programmierparadigmen

  • Bei imperativen Programmiersprachen (links) (Python) wird beschrieben WIE ein Problem gelöst werden soll (algorithmischer Ablauf ).
  • Bei deklarativen Programmiersprachen (rechts) (Prolog) wird beschrieben WAS gelöst werden soll (Deklaration der Zusammenhänge). 
def istGluecklich(n):
   if n == "tobi":
     print "true"
   else:
     print "false"> istGluecklich("tobi")
> true
> istGluecklich(ötto")
> false 
istGluecklich(tobi).
?- istGluecklich(tobi).
true.
?- istGluecklich(otto).
false.

Verständnis für Prolog

  • Das richtige Verständnis des deklarativen Programmierparadigmas bedeutet das entsprechende Denk- oder Handlungsmuster zu verinnerlichen und gilt als essentielle Grundvorraussetzung für die Programmierung in Prolog.
  • Prolog ist eine deklarative Programmiersprache!
  • Für den Umgang mit Prolog ist es zwingend erforderlich sich vom imperativen Programmierparadigma zu lösen.

Der Interpreter

  • Der Interpreter von Prolog benötigt Informationen um eine Anfrage (query) zu beantworten.
  • Diese Informationen werden in einer Wissensbasis (knowledge base) gespeichert.
  • Eine Wissensbasis besteht aus Klauseln (clauses). Klauseln sind entweder Fakten (facts) oder Regeln (rules)

Wissensbasis:

hund(pluto).
hund(snoopy).
seemann(popeye).
mag(popeye,spinat).
ist_stark(popeye) :- mag(popeye, spinat).

Anfragen:

-? hund(pluto). % true
-? mag(pluto, spinat). % false
-? hund(garfield). % false.
-? man(popeye). % false
-? ist_stark(popeye) % true

Der Prolog-Interpreter wird die erste und letzte Frage bejahen und die anderen verneinen. Für Prolog ist alles ‘wahr’ oder ‘beweisbar’, was als Fakt in der Wissensbasis steht oder sich mithilfe von Regeln in der Wissensbasis aus diesen Fakten herleiten lässt.

Eine Wissensbasis in Prolog

Diese Wissensbasis besteht aus vier Fakten und einer Regel. Sie definiert vier unterschiedliche Prädikate (predicates) nämlich hund/1, seemann/1, mag/2 und ist_stark/1.

Das Symbol :- steht für ‘wenn’ oder ‘folgt aus’. Die Regel ‘ist_stark(popeye):- mag(popeye, spinat).’ kann gelesen werden als “ ‘ist_stark(popeye)’ ist wahr, wenn ‘mag(popeye, spinat)’ wahr ist”.

Prolog’s Programmierparadigma

Eine ganz einfache Wissensbasis in Prolog erlaubt uns vier unterschiedliche Anfragen zu stellen: 

mag(pluto,eis).
mag(pluto,orangen).
mag(popeye,eis).

Was mag Pluto? 

mag(pluto,X).
X = eis;
X = orangen;

Wer mag was? 

mag(X,Y).
X = pluto ,
Y = eis;
X = pluto, | X = popeye,
Y = orangen; | Y = eis

Fakten, Regeln, Klauseln

  • Die linke Seite einer Regel nennt man Regelkopf (head of the rule) und die rechte Seite Regelkörper (body of the rule).
  • Fakten und Regeln einer Wissensbasis nennt man Klauseln (clauses).
  • Bei einem Fakt kann man auch von einer leeren Regel (einer Regel ohne Regelkörper) sprechen: ‘mag(popeye, spinat).’ ist äquivalent zu ‘mag(popeye, spinat):- .’.

Datenstrukturen

  • Die grundlegende Datenstruktur in Prolog sind Terme (terms ).
  • Sie sind entweder einfach oder zusammengesetzt.
  • Einfachen Terme in Prolog sind Konstanten (constants) und Variablen (variables )
  • Die Konstanten sind Atome (atoms) und Zahlen (numbers).
  • Zusammengesetzte Terme werden auch komplexe Terme oder Strukturen genannt.

Einfache Terme: Atome, Zahlen und Variablen

Atome sind Zeichenfolgen, die mit Kleinbuchstaben beginnen und nur aus Buchstaben, Zahlen und dem Unterstrich bestehen, oder Zeichenfolgen, die in Anführungszeichen stehen:
popeye, hund13XYZ, my_dog, „Lea?!@“, ’Homer Simpson’.

Zahlen sind ganze Zahlen (integers) oder Kommazahlen (floats): 123, 89.5, 0, -323.

Variablen sind Zeichenfolgen, die mit einem Grossbuchstaben oder einem Unterstrich beginnen und nur aus Buchstaben, Zahlen und dem Unterstrich bestehen:
X, Variable, _123, Hund_123.

Hinweise:

  • Verwenden Sie bitte immer ‘sprechende’ Namen für ihre Terme.
  • Die Variable _, die nur aus dem Unterstrich besteht, ist die anonyme Variable (kommt später im Kurs). Sie sollte zunächst nicht von Ihnen verwendet werden.

Programmiertips:

  • Alle Klauseln werden mit einem Punkt abgeschlossen.
  • Alle Klauseln, die zu einem Prädikat gehören, stehen direkt beieinander.
  • Die Verwendung zweier Prädikate mit identischem Funktor aber unterschiedlicher Stelligkeit geschieht nur im wohldurchdachten Ausnahmefall.
  • Jedes Prädikat wird kommentiert (Kommentarzeichen ‘%’).
  • Die Reihenfolge der Argumente ist bedeutsam ‘kind(otto,piet) = kind(piet,otto).
  • Wir können selber festlegen, welche Argumentposition wofür stehen sollen. Einmal getroffene Konvention beibehalten und kommentieren.

Zusammengesetzte bzw. komplexe Terme

  • Zusammengesetzte bzw. Termen bestehen aus einem Funktor (functor) und beliebig vielen Argumenten (arguments).
  • Der Funktor ist immer ein Atom.
  • Die Argumente sind einfache oder komplexe Terme.
  • Beispiel für komplexe Terme: mag(popeye,spinat)
  • Beispiel für komplexe verschachtelte Terme: befreundet(X,vater(vater(popeye)))
  • Unter der Stelligkeit (arity) eines komplexen Terms versteht man die Anzahl der Argumente.

Prädikate

  • Betrachtet man die Fakten einer Wissensbasis als leere Regeln, dann definieren alle Klauseln, deren Regelköpfe denselben Funktor und dieselbe Stelligkeit haben, zusammen ein Prädikat.
  • Vorsicht: Enthält eine Wissensbasis die beiden Fakten befreundet(popeye,pluto,garfield) und befreundet(X,mickey) so definiert sie zwei verschiedene Prädikate, nämlich befreundet/3 (3-stellig) und befreundet/2 (2-stellig).
  • Für einen guten Programmierstil beachte folgende Regeln:
    • Alle Klauseln, die zu einem Prädikat gehören, stehen direkt beieinander. • Die Verwendung zweier Prädikate mit identischem Funktor aber unterschiedlicher Stelligkeit geschieht nur im wohldurchdachten Ausnahmefall.
    • Jedes Prädikat wird kommentiert (Kommentarzeichen ‘%’)