Prolog: Einführung

Einführung

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 Beispiel für eine Daten-Basis

Eine Prolog Daten-Basis bezeichnet den Quelltext eines Programmes, welcher in der betreffenden Quelldatei gespeichert ist. Hier ein Beispiel für eine Daten-Basis:

Beispiel 1, ue01.pl
% Daten - Basis.
mensch(gregor).
mensch(stefan).

Erstellen Sie diese Daten-Basis mit einem Text-Editor und speichern Sie diese unter dem Namen ue01.pl. Jetzt können sie die Daten-Basis in Prolog laden:

?- consult(ue01). - laedt die Daten-Basis
% ue01 compiled 0.00 sec, 904 bytes

Yes

Jetzt können wir Anfragen an die Daten-Basis stellen: Z.B. können wir alle Menschen in der Daten-Basis ausgeben lassen. Beachten Sie, dass die Ausgabe nach jedem Fund anhält, bis Sie "r" (redo) drücken.

? - mensch(Name).
Name = gregor;
Name = stefan;
No.

Atome

Atome sind die kleinsten Informationseinheiten, quasi Bausteine , in Prolog. Sie müssen klein geschrieben (oder in Anführungszeichen gesetzt) werden. Im vorigen Beispiel sind dies z.B. gregor und stefan aber auch 'gregor' o.ä. wäre zulässig.

Prädikate

Prädikate in Prolog bezeichnen im einfachsten Fall fest stehende Argumente. So zeigt uns folgendes Beispiel, wie ein in der Prolog-Datenbasis existierendes Argument abgefragt wird:

Beispiel 2
wohnt_in(schneider, hauptstrasse).
wohnt_in(schmidt, hauptstrasse). 
wohnt_in(meier, hauptstrasse).
wohnt_in(mueller, dorfstrasse).
wohnt_in(petram, dorfstrasse).
wohnt_in(kringel, bahnhofstrasse).
wohnt_in(fischer, bahnhofstrasse).

Diese Datenbasis beschreibt Fakten durch das Prädikat wohnt_in(<Familie>, <Strasse>) wohnt_in/2. Die Bezeichnung wohnt_in/2 beschreibt die Existenz eines solchen Prädikats mit zwei Variablen. Bei einer Abfrage wie

?- wohnt_in(schmidt,Strasse). 

geht Prolog die Daten-Basis (DB) durch und sucht nach passenden Fakten innerhalb des Prädikats wohnt_in/2. Wir bekommen die Antwort:

Strasse = hauptstrasse;
No.
?-

Sie sollten sich durch das No. am Ende nicht verwundern lassen. SWI-Prolog gibt zunächst immer eine Lösung aus. Nach der Eingabe von ; oder n wird die nächste Lösung angegeben, welche durch die gegebene DB erfüllt wird. Da keine weitere Lösung existiert, gibt der Compiler ein No. zurück und terminiert die Ausführung.

Prädikate können komplexer aufgebaut werden, woraus sich Abhängigkeitsbeziehungen ergeben, welche Prolog durch systematisches Durchgehen zu beweisen versucht. So haben wir nachstehendes Beispiel, welches die Bewohner einer Strasse und wer Nachbar von wem ist beschreibt. Es wird erfragt, ob die Bewohner schmidt und mueller einen gemeinsamen Nachbarn haben.

Beispiel 3
% DB:
% Prädikate:  
% ist_nachbar_von(NachbarL,NachbarR).
ist_nachbar_von(schmidt,meier).
ist_nachbar_von(meier,mueller).

/*
Anfrage:
*/
?- ist_nachbar_von(schmidt, Nachbar), ist_nachbar_von(Nachbar,mueller).
Nachbar = meier
Yes.

Somit ist das gegebene Prädikat bewiesen.

Wir haben in diesem Beispiel zwei neue Elemente der Syntax kennengelernt. Das Prozentzeichen "%" wird für das Auskommentieren von Textelementen genutzt. Es dient der Auskommentierung der restlichen Zeile. Eine andere Form der Auskommentierung ist /* ... */. Hierbei wird der Bereich von /* bis zum am Ende stehenden */ auskommentiert.

Syntax: Sehen Sie nun noch einmal bewußt auf die Groß- und Kleinschreibung der Anfrage. Ihnen sollte nun aufgefallen sein, dass die Namen der Nachbarn jeweils kleingeschrieben sind. Dies ist eine der Prolog-Syntaxregeln. Fakten und Prädikate beginnen mit Kleinbuchstaben. Variablen beginnen mit Großbuchstaben

Variablen

Entgegen anderen, allgemein bekannten Programmiersprachen (Java, C, Pascal, Visual Basic) werden Variablen in Prolog nicht deklariert. Das einfache Benennen einer Variable führt eine Variable ein. Prolog betrachtet eine Zeichenkette als Variable, wenn der erste Buchstabe groß geschrieben ist oder sie mit einem Unterstrich _ beginnt. Eine Variable hat zunächst keinen Wert. Sie erhält einen möglichen konkreten Wert implizit durch das Prologsystem während der Verarbeitung. Diesen Prozess nennt man Bindung der Variable.

Im folgenden Beispiel wird in der Anfrage die Variable "Nachbar" eingeführt. Das Prologsystem prüft dann die Datenbasis und bindet die Variable an den Wert 'meier'. Mit dieser Bindung ist das Prädikat 'ist_nachbar_von' verifiziert und die Anfrage wird positiv beantwortet ("Yes"). Dabei wird auch die Bindung der Variable ausgegeben.

 Beispiel 4
 % DB:
 % Prädikate:  
 ist_nachbar_von(schmidt,meier).
 ist_nachbar_von(meier,mueller).

 /*
 Anfrage:
 */
 ?- ist_nachbar_von(schmidt, Nachbar).
 Nachbar = meier
 Yes.

Variablen lassen sich auch explizit binden, wie im folgenden Beispiel gezeigt.

 /*
 Anfrage:
 */
 ?- ist_nachbar_von(Variable1, Nachbar), Variable1=schmidt.
 Variable1 = schmidt
 Nachbar = meier
 Yes.

Eine Variable kann beliebige Werte annehmen, wie die folgenden Terme zeigen:

Variable1 = schmidt    % Variable Variable1 wird an Atom schmidt gebunden
Variable1 = 2          % Variable Variable1 wird an an Integerwert (also hier die Zahl 2) gebunden
Variable1 = 'Allee 1'  % Variable Variable1 wird an Zeichenkette 'Allee 1' gebunden
Variable1 = Allee      % Variable Variable1 wird an Variable Allee gebunden! Eine Bindung einer der beiden Variablen z.B. an eine Zahl impliziert auch die Bindung der anderen an diese Zahl

Vergleichsoperatoren

Der Vergleich zweier Variablen ist in Prolog mittels zweier Operatoren möglich.

==

Ersterer (==) prüft, ob der in den Variablen enthaltene Text übereinstimmt. Hier ein Beispiel:

%DB:
text_ist_gleich(Variable1, Variable2) :- Variable1 == Variable2.

%Anfrage:
?- text_ist_gleich(text,text).
Yes.

=:=

Der zweite Vergleichsoperator (=:=) ist für den Vergleich von Zahlwerten zu benutzen. Siehe:

%DB:
zahlen_sind_gleich(Variable1, Variable2) :- Variable1 =:= Variable2.

%Anfrage:
?- zahlen_sind_gleich(1024,1024).
Yes.

\=

Um die Ungleichheit zweier Variablen zu prüfen, ist der Ungleichoperator (\=) verfügbar. Er liefert bei Ungleichheit der Variablen ein Yes. zurück.

%DB:
text_ist_ungleich(Variable1, Variable2) :- Variable1 \= Variable2.

%Anfrage:
?- text_ist_ungleich(pro,log).
Yes.

Rechnen mit Variablen

Das Rechnen mit Variablen ist entgegen Java-ähnlichen Programmiersprachen anders gestaltet. Im kommenden Beispiel werden wir ein Prädikat schreiben, welches das Quadrat einer Zahl zurückliefert.

Beispiel 5
%DB:
quadrat_von(Zahl,Quadrat_der_Zahl):-Quadrat_der_Zahl is(Zahl*Zahl).

Anfrage:
quadrat_von(4,Ergebnis).  % quadrat_von(4,Ergebnis) :- Ergebnis is (4 * 4).
Ergebnis = 16.
Yes.

Wir sehen, dass das Rechnen mit Variablen mit einem Prefix-Operator ermöglicht wird. Wir erhalten bei diesem Ergebnis ein Yes., da wir kein zweites Ergebnis erwarten und somit statt <n> <Enter> gedrückt haben.

Syntax: Mit diesem Beispiel wurde der gilt wenn Operator eingeführt. Wie eingangs beschrieben, ist Prolog eine Programmiersprache, welche versucht eingegebene Anfragen zu beweisen. Daher gilt an dieser Stelle: quadrat_von/2 gilt, wenn Quadrat_der_Zahl is(Zahl*Zahl) gilt. Da die Variable Zahl bereits durch die eingegebene Anfrage an eine feste Zahl gebunden wurde, ist Quadrat_der_Zahl is(Zahl*Zahl) ein Fakt und gilt somit. Ein einfacheres Beispiel verdeutlicht dies:

Beispiel 6
%DB:
weiblich(helene).
ist_Elternteil_von(helene,stefan).
ist_Mutter(Mutter) :- weiblich(Mutter), ist_Elternteil_von(Mutter,_).

%Anfrage:
ist_Mutter(helene).
Yes.

Syntax: Ein Unterstrich wird für anonyme Variablen verwendet. Dies bedeutet, dass es sich hierbei um eine Variable handelt, welche einen beliebigen Wert zugewiesen bekommt. Anonyme Variablen werden nicht ausgegeben!

Achtung! Sollten sich in einem Prädikat zwei dieser anonymen Variablen befinden, sind diese nicht gleichzusetzen. Es handelt sich um zwei verschiedene Variablen, welche nicht weiter genutzt werden können.

Verknüpfungen

Zu den Verknüpfungen zählen das und, das (nicht exklusive) oder sowie die Negation. Allerdings spielt letztere hier erst mal keine Rolle.

Und (auch: Konjunktion)

Wie zu sehen ist, sind in der DB des vorangehenden Beispiels (Bsp. 6) die Fakten, dass helene weiblich ist und Elternteil von Stefan gespeichert. Anhand des Prädikates ist_Mutter wird überprüft, ob es eine weibliche Person gibt, welche gleichzeitig Elternteil eines Kindes ist.

Syntax: In diesem Beispiel haben wir die Und - Verknüpfung kennengelernt. Diese wird mit einem Komma (",") zwischen den Prädikaten realisiert.

Oder (auch: Disjunktion)

Oder-Verknüpfungen werden in Prolog durch ein Semikolon (";") dargestellt. Für die nächsten Anfragebeispiele nutzen wir die folgende DB:

Beispiel 7
%DB:
hat_gestohlen(markus).
hat_gestohlen(stefan).
hat_gestohlen(christine).
hat_randaliert(markus).
hat_randaliert(christine).
hat_sich_entschuldigt(stefan).
% Prädikate:
wird_gesucht(Name) :- 
        hat_gestohlen(Name); 
        hat_randaliert(Name).
ist_frei(Name) :- 
        (
        hat_gestohlen(Name); 
        hat_randaliert(Name)
        ),
        hat_sich_entschuldigt(Name).

Beispiel 7a 
Anfrage: 
wird_gesucht(Name).
Name = markus;
Name = stefan;
Name = christine;
Name = markus;
Name = christine;
No.

Anhand dieser Ausgabe wird die Art der Beweisführung Prologs erkennbar. Prolog durchsucht die DB chronologisch von oben nach unten und versucht die Anfrage mittels findbarer Fakten zu beweisen. Da markus mit zwei Delikten in der DB aufgeführt ist und die Frage gestellt wurde, wer gestohlen oder randaliert hat, wird er in der Ausgabe zweifach aufgeführt, da Prolog die Frage wird_gesucht mit hat_gestohlen oder hat_randaliert beweisen kann. Prolog verwendet bei der Suche nach Fakten für die Beweisführung das Prinzip der Tiefensuche.

Und - Oder

(DB siehe Beispiel7)

Beispiel 7b
Anfrage: 
ist_frei(Name).
Name = stefan;
No.

Wie im Prädikat ist_frei (siehe Beispiel 7) sichtbar, ist die komplexe Verknüpfung von und & oder Verknüpfungen mittels Klammern erfolgreich. Es werden nach den Regeln der Mathematik zunächst die Argumente in der Klammer beachtet.

Mit dem bis hierher gewonnenen Wissen sollten Sie nun bereits einige kleine Programme schreiben können.

Übungen

Übung 1

Formuliere für die folgende DB mit dem Prädikat kind(<Elternteil>,<Kind>):

kind(hanna,sabine). kind(hanna,peter). kind(robert,sabine).
kind(robert,peter). kind(peter,jana). kind(peter,christine).
kind(claudia,jana). kind(claudia,christine). kind(claudia,jutta).
kind(jana,jakob). weiblich(claudia). weiblich(jana). 
weiblich(christine). weiblich(jutta). weiblich(sabine).
weiblich(hanna). maennlich(peter). maennlich(robert).
maennlich(jakob).

die folgenden Anfragen:

a) Welche Schwestern hat Jana? (keine Halbschwestern!)

b) Welche Tanten hat Christine?

c) Welche Nichten hat Sabine?

d) Wer hat Geschwister? (auch Halbgeschwister!)

Gib jeweils die Anfrage und Antwort in Prolog an!

Übung 2

Formuliere eine Prolog-Regel (Prädikat) für die Verwandtschaftsbeziehung eines Neffen: (neffe( X, Y), was bedeutet: Y ist Neffe von X) Nutze hierfür die DB der Übung 1. Die Schwester oder der Bruder von X, dessen Kind Neffe von X ist, soll dabei eine leibliche Schwester bzw. ein leiblicher Bruder (keine Halbgeschwister) sein!

Formuliere des Weiteren folgende Anfragen:

a) Hat Claudia einen Neffen?

b) Wer hat einen Neffen?

c) Wessen Neffe ist Jakob?

Gib jeweils die Anfrage und Antwort in Prolog an!

Lösungen

Lösung zu Übung 1

a)

?- kind(Mutter,jana), 
kind(Mutter,Geschwister), 
kind(Vater,jana), 
kind(Vater,Geschwister), 
weiblich(Mutter),
maennlich(Vater),
weiblich(Geschwister), 
Geschwister\==jana.

Mutter = claudia
Geschwister = christine
Vater = peter;
No.

b)

?- kind(Elternteil, christine),
kind(Grosselternteil, Elternteil),
kind(Grosselternteil, Tante),
weiblich(Tante).

Elternteil = peter
Grosselternteil = hanna
Tante = sabine ;
Elternteil = peter
Grosselternteil = robert
Tante = sabine ;
No.

c)

?- kind(Elternteil, sabine),
kind(Elternteil,Geschwister),
kind(Geschwister, Nichte),
weiblich(Nichte).

Elternteil = hanna
Geschwister = peter
Nichte = jana ;
Elternteil = hanna
Geschwister = peter
Nichte = christine ;
Elternteil = robert
Geschwister = peter
Nichte = jana ;
Elternteil = robert
Geschwister = peter
Nichte = christine ;

d)

?- kind(Elternteil, Geschwister1),
kind(Elternteil, Geschwister2),
Geschwister1\==Geschwister2.

Elternteil = hanna
Geschwister1 = sabine
Geschwister2 = peter 
;
Elternteil = hanna
Geschwister1 = peter
Geschwister2 = sabine 
;
Elternteil = robert
Geschwister1 = sabine
Geschwister2 = peter 
;
Elternteil = robert
Geschwister1 = peter
Geschwister2 = sabine 
;
Elternteil = peter
Geschwister1 = jana
Geschwister2 = christine 
;
Elternteil = peter
Geschwister1 = christine
Geschwister2 = jana 
;
Elternteil = claudia
Geschwister1 = jana
Geschwister2 = christine 
;
Elternteil = claudia
Geschwister1 = jana
Geschwister2 = jutta 
;
Elternteil = claudia
Geschwister1 = christine
Geschwister2 = jana 
;
Elternteil = claudia
Geschwister1 = christine
Geschwister2 = jutta 
;
Elternteil = claudia
Geschwister1 = jutta
Geschwister2 = jana 
;
Elternteil = claudia
Geschwister1 = jutta
Geschwister2 = christine 
;
No.

Lösung zu Übung 2

Regeln:

elternteil(KindA,ElternteilA):-
 kind(ElternteilA,KindA).

vollgeschwister(KindA,KindB):-
elternteil(KindA,ElternteilA),weiblich(ElternteilA),
elternteil(KindA,ElternteilB),maennlich(ElternteilB),
elternteil(KindB,ElternteilA),
elternteil(KindB,ElternteilB),
KindA\==KindB.

neffe(Mensch1,Neffe):-
vollgeschwister(Mensch1,Mensch2),
kind(Mensch2,Neffe),
maennlich(Neffe).

Antworten:

a)

?- neffe(claudia,A).
No.

b)

?- neffe(A,B).
A = christine
B = jakob ;
No.

c)

?- neffe(A,jakob).
A = christine ;
No.