Prolog: Einführung

EinführungBearbeiten

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-BasisBearbeiten

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.

AtomeBearbeiten

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ädikateBearbeiten

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

VariablenBearbeiten

Entgegen anderen, allgemein bekannten Programmiersprachen (Java, C, Pascal, Visual Basic) ist es in Prolog nicht notwendig, Variablen zu deklarieren. Diese werden durch das Zuweisen von Werten initialisiert. Prolog erkennt Variablen, wie bereits erwähnt, anhand des ersten, groß geschriebenen Buchstabens oder mittels Voranstellen eines Unterstriches. Die Zuweisung von Werten erfolgt nach den Regeln des folgenden Beispiels:


 Beispiel 4
Variable1 = 'Text'.   % Der Variable Variable1 wird ein Text zugewiesen.
Variable2 = 2.        % Der Variable Variable2 wird ein Integerwert (also hier die Zahl 2) zugewiesen.
_strasse = 'Allee 1'. % Der Variable _strasse wird ein Text zugewiesen.


Wie in den drei Variablenzuweisungen erkennbar, wird jede fertige Syntaxzeile mit einem Punkt beendet.

VergleichsoperatorenBearbeiten

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

==Bearbeiten

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.

=:=Bearbeiten

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.

\=Bearbeiten

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 VariablenBearbeiten

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üpfungenBearbeiten

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)Bearbeiten

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)Bearbeiten

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 - OderBearbeiten

(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.

ÜbungenBearbeiten

Übung 1Bearbeiten

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 2Bearbeiten

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ösungenBearbeiten

Lösung zu Übung 1Bearbeiten

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 2Bearbeiten

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.