1. Darstellung von Listen in PROLOG
2. Simulation eines nichtdeterministischen Automaten
Eine vierelementige Liste,die als Elemente Objekte a,b,c,d enthält,kann in PROLOG
als [a,b,c,d] geschrieben werden.Die leere Liste wird durch [] bezeichnet.Eine Liste L ist
folgendermaßen definiert:
(1) L ist leer,in diesem Fall wird die Liste als PROLOG-Atom geschrieben
(2) L ist nicht leer,dann besteht sie aus zwei Teilen:dem Kopf(ein beliebiges Objekt)
und dem Rest der Liste,der wiederum eine Liste repräsentiert.
Für die Repräsentation einer Liste verwendet man folgende Schreibweisen:
[Element1,Element2,...]
[Kopf | Rest]
[Element1,Element2,...| Rest]
Zur Veranschaulichung der Behandlung von Listen in POLOG wollen wir als erstes
die Mitgliedschaftsrelation implementieren.Die Relation mitglied(X,L) ist wahr,falls das
Objekt X in der Liste L auftritt,und falsch ansonsten.Die Implementation von mitglied/2
kann auf folgenden Beobachtungen aufgebaut werden: X ist Mitglied von L,wenn:
X der Kopf von L ist,oder
X ein Mitglied des Restes von L ist.
Dies kann in zwei Klauseln beschrieben werden:
mitglied(X,[X|Rest]).
mitglied(X,[Kopf|Rest]):-
mitglied(X,Rest).
Als nächstes wollen wir die Konkatenation zweier Listen definieren.Sie wird als eine
dreistellige Relation programmiert,die als letztes Argument das Ergebnis der Konkatenetion
von zwei ersten Argumenten liefert.So ist zum Beispiel konk([a,b],[c,d],[a,b,c,d]) wahr.
Bei der Definition von konk/2 werden wiederum zwei Fälle unterschieden:
(1) Ist das erste Argument die leere Liste,so müssen das zweite und das dritte Argument gleich sein.Dies wird durch den Fakt konk([],L,L) ausgedrückt.
(2) Ist das erste Argument nicht leer,dann besteht es aus einem Kopf und einem Rest:
[X | L1].Das Ergebnis der Konkatenation ist [X | L3],wobei L3 die Konkatenation
von L1 und L2 ist (mit L2 ist hier das zweite Argument gemeint).In PROLOG kann
dies in folgende Klauseln umgesetzt werden:
konk([X | L1],L2,[X | L3]):-
konk(L1,L2,L3).
Unser Programm sieht dann wie folgt aus:
konk([],L,L).
konk([X | L1],L2,[X | L3]):-
konk(L1,L2,L3).
Dieses Programm kann nun zum Konkatenieren von Listen verwendet werden,zum
Beispiel:
?-konk([a,b,c],[1,2,3],L).
L=[a,b,c,1,2,3]
?-konk([a,[b,c],d],[a,[],b],L).
L=[a,[b,c],d,a,[],b]
Das konk-Programm,wie die meisten PROLOG-Programme,kann flexibel auf verschiedene
Arten benutzt werden.Zum Beispiel für das Zerlegen einer Listen in zwei Listen:
?-konk(L1,L2,[a,b]).
L2=[a,b]
L1=[] ;
L2=[b]
L1=[a] ;
L2=[]
L1=[a,b] ;
No
Die Mitgliedschaftsrelation kann unter Anwendung von konk/3 mit der Klausel
mitglied(X,L):-
konk(L1,[X | L2],L).
programmiert werden.Diese Klausel geht davon aus,daß X Mitglied einer Liste L ist,wenn L
so in zwei Listen zerlegt werden kann,daß die zweite Liste X als Kopf hat.
Weiterhin können wir unseres Programm benutzen,um nach bestimmten Mustern in
einer Liste zu suchen.Zum Beispiel können wir Elemente einer Liste,die vor einem bestimmten
Element liegen,und Elemente,die diesem Element folgen,wie folgt finden:
?-konk(Vorher,[e | Nachher],[a,b,c,d,e,f,g,h,i]).
Nachher = [f,g,h,i]
Vorher = [a,b,c,d]
In dem folgendem Beispiel wird ein nichtdeterministischer endlicher Automat in
PROLOG simuliert.Der Automat ist in der Abbildung 2.1 dargestellt.
Abbildung 2.1.
Er hat also vier Zustände(z1,z2,z3,z4,wobei z3 ein Endzustand ist).Die Simulaiton
des Automaten besteht offensichtlich in einer Implementierung der Übergangsfunktion.
Unser Programm entscheidet,ob das in der Anfrage angegebene Wort vom Automaten
akzeptiert bzw. verworfen wird.Dazu einige Überlegungen:
(1) Es wird eine Transformationsrelation trans(Z1,X,Z2) eingeführt,die anzeigt,ob es
einen Übergang von Zustand Z1 nach Zustand Z2 mittels Zeichens
X gibt(X![]()
).
Für
-Übergänge
wird in unserem Programm extra eine Relation
namens epsilon vorgesehen.((Man könnte im Prinzip epsilon/2 in trans/3 einbetten,
worauf der Übersichtlichkeit wegen verzichtet wird)).
(2)Die Relation endzustand/1 gibt an,ob das Argument einen Endzustand des Auto-
maten darstellt.
Die eforderliche Datenbank,die den Automaten vollständig beschreibt,sieht dann
wie folgt aus:
endzustand(z3).
trans(z1,a,z1).
trans(z1,a,z2).
trans(z1,b,z1).
trans(z2,b,z3).
trans(z3,b,z4).
epsilon(z2,z4).
epsilon(z3,z1).
Damit ist die Frage,ob ein in der Anfrage angegebenes Wort vom Automaten akzep-
tiert wird,noch nicht beantwortet.Dies tut eine zweistellige Relation akzeptiert/2.Bei der
Implementierung dieser Relation gehen wir davon aus,daß der Automat ein Wort genau
dann akzeptiert,wenn es einer der folgenden Fälle auftritt:
Die angeführten drei Fälle werden in drei Klauseln umgesetzt:
akzeptiert(Z,[]):- endzustand(Z).
akzeptiert(Z,[X|Rest]):-
trans(Z,X,Z1),
akzeptiert(Z1,Rest).
akzeptiert(Z,Wort):-
epsilon(Z,Z1),
akzeptiert(Z1,Wort).
erzwungen.Auf Anfragen,wie etwa
?- X=1+2
antwortet PROLOG mit X=1+2 und nicht X=3,wie man erwarten könnte.Das liegt
daran,daß der Ausdruck 1+2 lediglich einen PROLOG-Term darstellt,in dem Objekte 1
und 2 durch den +-Funktor verknüpft sind.Die Auswertung eines Ausdrucks (d.h.das Akti-
vieren der Additionsoperation) ermöglicht der is-Operator.Unter Anwendung des Opera-
tors sieht die obige Anfrage wie folgt aus:
?- X is 1+2.
X=3
Nun wollen wir anhand einiger Beispiele die Benutzung des is-Operators erläutern.
Unser erstes Programm soll die Länge einer gegebener Liste zurückliefern.Dabei ist es
nützlich,zwei Fälle zu unterscheiden:
(1) Die Länge der leeren Liste ist Null.
(2) Wenn die Liste nicht leer ist,dann hat sie die Form [Kopf | Rest],die Länge dieser
Liste ist gleich 1 + die Länge der restlichen Liste [Rest].
Das entspricht folgendem Programm:
laenge([],0).
laenge([ Kopf | Rest],N):-
laenge(Rest,N1),
N is 1+N1.
Unser nächstes Beispiel beschäftigt sich mit Berechnung des größten gemeinsamen
Teilers.Es wird nach folgenden Regeln berechnet: Seien X und Y ganze Zahlen,deren ggT
zu berechnen ist,dann gilt es:
(1) Sind X und Y gleich,so ist ggT gleich X
(2) Ist X<Y,dann ist ggT(X,Y) = ggT(X,Y-X)
(3) Ist Y<X,so sind X und Y zu vertauschen,und die ggT-Funktion erneut
aufzurufen.
Der Algorithmus benötigt offensichtlich einige Vergleichsoperatoren.Für Vergleichs-
operatoren gelten in PROLOG folgende Schreibweisen:
|
X<Y |
X ist kleiner als Y |
|
X>Y |
X ist größer als Y |
|
X>=Y |
X ist größer als oder gleich Y |
|
X<=Y |
X ist kleiner als oder gleich Y |
|
X=:=Y |
X ist gleich Y |
|
X=\=Y |
X und Y sind nicht gleich |
Jetzt können die obigen Regeln in drei PROLOG-Klauseln geschrieben werden
(das dritte Argument repräsentiert dabei das Ergebnis):
ggT(X,X,X).
ggT(X,Y,T):-
X<Y,
Y1 is Y-X,
ggT(X,Y1,T).
ggT(X,Y,T):-
Y<X,
ggT(Y,X,T).
daß sie sich nicht paarweise bedrohen.Die Lösung wollen wir als unäre Relation
loesung(Stellung) programmieren.
Die Stellung wird durch eine aus Koordinatenpaaren bestehende Liste repräsentiert.
Sie hat also die Gestalt [X1/Y1,X2/Y2,...,X8/Y8],wobei das "/"-Zeichen nicht für Divisions-
operator steht,sondern nur als Trennzeichen verwendet wird(solange kein is-Operator
angewendet ist,wird keine Divisionsoperation hervorgerufen(s.Arithmetik in PROLOG)).
Da alle Damen auf verschiedenen Spalten stehen müssen,können wir die Lösung in
der Form [1/Y1,2/Y2,3/Y3,...,8/Y8] suchen.
Die Lösung des Problems kann unter Betrachtung folgender zwei Fälle formuliert
werden:
(1) Die leere Liste ist eine Lösung,da es keinerlei Bedrohung gibt.
(2) Die Liste der Damen ist nicht leer,dann hat sie die Form:[X/Y | Weitere].
Soll dies die Lösung sein,dann muß folgendes gelten:
(a) Die Liste Weitere muß auch eine Lösung sein.
(b) X und Y sind ganze Zahlen aus dem Bereich [1...8].
(c) X/Y darf keine Dame der Liste Weitere bedrohen.
Der erste Fall wird mit dem Fakt
loesung1([]).
programmiert,der zweite mit
loesung1([X/Y | Weitere]) :-
loesung1(Weitere),
mitglied(Y,[1,2,3,4,5,6,7,8]),
bedroht_nicht(X/Y,Weitere).
Wir haben uns vereinbart,daß die Lösung die Form [1/Y1,...,8/Y8] hat.Das wird mit
muster([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).
loesung(L) :- muster(L),
loesung1(L).
realisiert.
Es ist noch die bedroht_nicht-Relation in unserem Programm zu definieren:
bedroht_nicht(D,D_Liste).Es sind wider zwei Fälle zu unterscheiden:
(1) D_Liste ist leer,dann ist die Relation wahr.
(2) D_Liste ist nicht leer,dann hat sie die Form [D1 | D_Liste1] und es
müssen zwei Bedingungen erfüllt sein:
(a) Die Dame D darf die Dame D1 nicht bedrohen
(b) Die Dame D1 darf keine Dame der Liste D_Liste1 bedrohen.
Das wird wie folgt programmiert:
bedroht_nicht( _ ,[]).
bedroht_nicht( X / Y , [ X1 / Y1 | Weitere ] ) :-
Y =\= Y1,
Y1-Y =\= X-X1,
Y1-Y =\= X1-X,
bedroht_nicht( X / Y , Weitere).
Das vollständige Programm hat dann das folgende Aussehen:
loesung(L) :- muster(L),
loesung1(L).
loesung1([]).
loesung1([X/Y | Weitere]) :-
loesung1(Weitere),
mitglied(Y,[1,2,3,4,5,6,7,8]),
bedroht_nicht(X/Y ,Weitere).
bedroht_nicht([]).
bedroht_nicht(X/Y , [X1/Y1 | Weitere]) :-
Y =\= Y1,
Y1-Y =\= X-X1,
Y1-Y =\= X1-X,
bedroht_nicht( X/Y , Weitere).
mitglied(X , [X | _ ]).
mitglied(X , [_ | L) :-
mitglied( X , L).
eines Ziels notwendig ist.Automatisches Backtracking ist ein nützliches Programmierkonzept,
das den Programmierer von der Last befreit,explizites Backtracking vorzunehmen.Manch-
mal ist es aber sinnvoll automatisches Backtracking (aus Effizienzgründen) abzuschalten,um
unerwünschte Folgen des unkontrollierten Backtracking zu verhindern.Dies wird in PROLOG
mit dem "Cut" gemacht.Anwendung des Cut wird mit folgendem einfachem Beispiel
demonstriert.Wir betrachten die Funktion:

Sie kann in Prolog als binäre Relation f(X,Y) implementiert werden:
f(X,0) :- X<3.
f(X,2) :- 3=<X,X<6.
f(X,4) :- 6<=X.
Angenommen,wir haben in der Anfrage folgendes angegeben:
?- f(1,Y),2<Y.
Bei Berechnung des ersten Ziels wird Y zu 0 instanziiert.Das zweite Ziel 2<0 scheitert,und
damit die gesamte Zielliste.Nach dem Scheitern des Ziels 2<0 werden in PROLOG die
Regeln 2 und 3 versucht,obwohl das sinnlos ist und zu Ineffizienzen führt.In der Abbildung
5.1 wird dies ausführlich gezeigt.

Abbildung 5.1.
Unter Anwendung des Cut sieht unser Programm wie folgt aus:
f(X,0) :- X<3, ! .
f(X,2) :- 3=<X , X<6 , ! .
f(X,4) :- 6=<X.
Cut ist ein Pseudoziel,das immer erfüllt ist und mit "!" bezeichnet wird.Wird an einer
Stelle das Symbol "!" erreicht,so wird kein Backtracking mehr durchgeführt.Wenn wir die
gleiche Zielliste in der Anfrage für die zweite Variante des Programms angeben,werden die
Regeln 2 und 3 wegen Anwendung des Cut nicht versucht,was offensichtlich effizienter ist.
Wir könnten das Programm unter Berücksichtigung der Reihenfolge der Regeln noch verkür-
zen.Dies wird bei einer ökonomischer Formulierung der Regeln erreicht:
Wenn X<3,dann Y=0,
ansonsten,wenn X<6,dann Y=2,
ansonsten Y=4.
Das führt zu einer dritten Version des Programms:
f(X,0) :- X<3 , ! .
f(X,2) :- X<6 , ! .
f(X,4).
Dieses Programm liefert die gleichen Ergebnisse,ist aber effizienter und kürzer als das ursprüngliche.
Wir befassen uns mit noch einem Beispiel für die Anwendung des Cut : Berechnung
des Maximums zweier Zahlen.Ohne Cuts sieht das Programm wie folgt aus:
max(X,Y,X) :- X >=Y.
max(X,Y,Y) :- X<Y.
Die beiden Regeln schließen sich gegenseitig aus,was in der zweiten Version des Programms
genutzt wird:
max(X,Y,X) :- X>=Y , ! .
max(X,Y,Y).
In PROLOG gibt es auch zwei vordefinierte Pseudoziele true und fail,das erste gelingt
immer,wohingegen das zweite immer scheitert.
Wir können unter Anwendung dieser Ziele und des Cut die not-Relation
programmieren.Wir werden die Relation wie folgt definieren:
Wenn Z gelingt,dann scheitert not(Z),
ansonsten gelingt not(Z).
In PROLOG wird dies folgendermaßen geschrieben:
not(P) :-
P , ! , fail
; true.
Es sollte angemerkt werden,daß not als Scheitern definiert ist,und nicht exakt der
Negation der mathematischen Logik entspricht.