LbP Programmiertechniken

Wiki-Quelltext dieser Seite.

<language>Prolog</language>
==Programmiertechniken mit Logik-orientierten Sprachen==
===Generate and test===
Hierbei wird die inhärent nichtdeterministische Lösungssuche von Prolog ausgenutzt, indem fortlaufend Lösungsvorschläge erzeugt und anschliessend verifiziert werden. Als Regel formuliert, heisst das
 find(S) :- generate(S), test(S).
Diese Lösungstechnik bietet sich vor allem für NP-vollständige Probleme an, da für diese kein effizientes Lösungsverfahren bekannt ist. Aufgrund der in Prolog üblicherweise eingebauten Tiefensuche und Backtracking, arbeitet auch <tt>generate</tt> nach diesem Prinzip. 

Effizienzverbesserungen lassen sich erzielen, wenn man <tt>generate</tt> und <tt>test</tt> miteinander verzahnt. D.h., unmittelbar nach Bereitstellung eines Kandidaten für eine Teillösung wird geprüft, ob sich die Fortsetzung der Suche in der eingeschlagenen Richtung noch lohnt. Auf diese Weise können aussichtslose Teile des Suchbaumes ausgespart werden.

Beispiel: "Vierfarbenproblem für Deutschlandkarte" 
Färben einer Landkarte mit 4 Farben, so dass keine 2 benachbarten Regionen die gleiche Farbe haben. Das Viefarbenproblem wurde 1976 gelöst. <tt>member/2</tt> soll als Systemprädikat angenommen werden.
<code id="4b8bd315ad197" hidden>
member(X,[X|Xs]).
member(X,[Y|Ys]) :- member(X,Ys).
</code>
<code id="4b8bd315adcca">
faerbe([],Farben).
faerbe([Region|Restkarte],Farben) :- 
faerbe_region(Region,Farben),
faerbe(Restkarte,Farben).

faerbe_region(region(Name,Farbe,Nachbarn),Farben) :-
select(Farbe,Farben,Restfarben),
sublist(Nachbarn,Restfarben).

select(X,[X|Ys],Ys).
select(X,[Y|Ys],[Y|Zs]) :- select(X,Ys,Zs).

sublist([X|Xs],Ys) :- member(X,Ys), sublist(Xs,Ys).
sublist([],Ys).
start :- faerbe(
[
region(schleswig-holstein, 	SH, 	[HH,N,MP]),
region(hamburg,			HH,	[SH,N]),
region(niedersachsen,		N,	[SH,HH,SA,TH,H,NRW,HB]),
region(bremen,			HB,	[N]),
region(nordrhein-westfalen,	NRW,	[N,H,RP]),
region(hessen,			H,	[NRW,RP,BW,BY,TH]),
region(rheinland-pfalz,		RP,	[NRW,H,BW,SL]),
region(saarland,		SL,	[RP]),
region(baden-wuerttemberg,	BW,	[RP,H,BY]),
region(bayern,			BY,	[H,BW,TH,S]),
region(thueringen,		TH,	[H,BY,N,S,SA]),
region(sachsen,			S,	[BY,TH,SA,BB]),
region(sachsen-anhalt,		SA,	[TH,N,MP,BB,S]),
region(brandenburg,		BB,	[B,MP,S,SA]),
region(berlin,			B,	[BB]),
region(mecklenburg-vorpommern,  MP,	[SH,N,SA,BB])
], [rot,gelb,blau,gruen]),
write(SH),write(' '),write(HH),write(' '),
write(N),write(' '),write(HB),write(' '),
write(NRW),write(' '),write(H),write(' '),write(RP),write(' '),
write(SL),write(' '),write(BW),write(' '),write(BY),write(' '),
write(TH),write(' '),write(S),write(' '),write(SA),write(' '),
write(BB),write(' '),write(B),write(' '),write(MP).
</code>
<eval id="4b8bd315b596a">start.</run>  

Die berechnete Farbfolge korrespondiert mit der <tt>write</tt>-Reihenfolge der Bundesländerkürzel.

<tt>select</tt> und <tt>sublist</tt> können im Verlauf der Berechnung mit instanziierten und nichtinstanziierten Variablen aufgerufen werden. Diese Bidirektionalität lässt sie einmal in der Funktion eines ''Generatorprädikates'' und einmal in der eines ''Testprädikates'' auftreten.

Beispiel: Permutationssortieren (Übungsaufgabe)
Die "generate and test"-Idee bedeutet für dieses Beispiel: Erzeugung je einer Permutation und sofortige Prüfung, ob sie eine sortierte Liste darstellt.
<code id="4b8bd315ae4c6">
perm_sort(Xs,Ys) :- permutation(Xs,Ys), geordnet(Ys).

geordnet([X]).
geordnet([X,Y|Ys]) :- X=<Y, geordnet([Y|Ys]).

permutation([],[]).
permutation(Xs,[Z|Zs]) :-            /* erstes Element Z festhalten, Rest perm. */
	auswahl(Z,Xs,Liste_ohne_Z), permutation(Liste_ohne_Z,Zs).

auswahl(X,[X|Xs],Xs).   /* Auswahl des ersten Listenelements */
auswahl(Y,[X|Xs],[X|Zs]) :- auswahl(Y,Xs,Zs).  /* Beide Listen koepfen. */
</code>
<eval id="4b8bd315b6149">perm_sort([1,2,8,3,5,34,23,4,6,77,4],X).</run>

Das Verfahren ist natürlich sehr ineffizient, sodass schon bei kleinen Listen erhebliche Wartezeiten entstehen können.

===Akkumulatortechnik===

Die Idee besteht darin, ein n+1-stelliges Prädikat aus einem n-stelligen zu konstruieren, indem eine zusätzliche Variable angefügt wird. Man spricht von ''Akkumulatorvariable''. In dieser wird das Resultat schrittweise aufgebaut. (Das Verfahren ist auch im funktionsorientierten Programmieren populär.)

<tt>myreverse/2</tt> aus dem Abschnitt über [[Listen]] arbeitet ineffizient. Zur Erinnerung wird hier die Definition wiederholt.
<code id="4b8bd315aed65">
myreverse([],[]).
myreverse([X|Xs],Ys) :- myreverse(Xs,Zs),append(Zs,[X],Ys).

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]):- append(Xs,Ys,Zs).
</code>
<eval id="4b8bd315b690e">myreverse([a,b,c],L).</run>

Verfolgen Sie alle Berechnungsschritte - auch mit Handrechnung. Die rekursive Abarbeitung geht n Schritte in die Tiefe und hat dann noch den ebensolangen Aufstieg zu erledigen, wenn n die Länge der zu spiegelnden Liste ist. Der Zeitaufwand liegt also in O(n²).

Unter Verwendung einer Akkumulatorvariablen kann die rekursive in eine zugehörige iterative Berechnung umgewandelt werden. Für unser Beispiel zeigt <tt>myrev/3</tt> eine Lösung. Hinweis: Um Verwechslungen vorzubeugen, verwenden wir <tt>myrev/3</tt> anstelle <tt>myreverse/3</tt>, da Menschen - ganz im Gegensatz zu Prolog - <tt>myreverse/2</tt> und <tt>myreverse/3</tt> nicht so klar zu unterscheiden vermögen.

<code id="4b8bd315af84e">
myrev([],R,R).
myrev([X|Xs],R,Ys) :- myrev(Xs,[X|R],Ys).
</code>
<eval id="4b8bd315b70fa">myrev([a,b,c],[],L).</run>
Die Umkehrliste wird nun in einer Zeit in O(n) berechnet. Analysieren Sie dies mittels Handrechnung!

===Differenzlisten===
Eine [[Liste]] ist eine Datenstruktur zur Repräsentation einer Folge von Elementen. Listen sind in Prolog eingebaute Basisdatentypen. Zur externen Repräsentation von Listen werden eckige Klammern [, ] verwendet.

Die ''Differenzlistentechnik'' geht von einer speziellen Darstellungsform von Listen als Differenz zweier Listen, kurz: <tt>L1\L2</tt>, aus. Elementsequenzen können alternativ auch als Differenzlisten repräsentiert werden. Beispielsweise kann die Liste <tt>[1,2,3]</tt> als <tt>[1,2,3,4,5]\[4,5]</tt> geschrieben werden, wobei klar ist, dass dies nicht die einzige Möglichkeit ist. Ebensogut wäre <tt>[1,2,3,4,5,a,b,c]\[4,5,a,b,c]</tt> möglich. 

Allgemein gilt <tt>[1,2,3] = [1,2,3|Xs]\Xs</tt>, wobei man <tt>Xs</tt> als ''Lückenvariable'' im Sinne eines Platzhalters bezeichnet. <tt>[1,2,3|Xs]</tt> ist der Kopf (head) der Differenzliste und <tt>Xs</tt> ist ihr Rest (tail). 

Eine beliebige Liste <tt>Ls</tt> lässt sich als Differenz aus <tt>Ls</tt> und der leeren Liste, also durch <tt>Ls\[]</tt>, darstellen. Die zur leeren Liste <tt>[]</tt> gehörende Differenzliste ist <tt>Ls\Ls</tt>, wobei <tt>Ls</tt> eine beliebige Liste ist.

Zur Definition eines Prädikats <tt>reverse_dl</tt>, auf das wir weiter unten eingehen werden, wird daher für den Fall der leeren Liste geschrieben als <tt>reverse_dl([], Ls-Ls)</tt>.
Obwohl man Differenzlisten auch durch zwei Parameter (head, tail) darstellen könnte, stellt SWI-Prolog das (zweistellige) Prädikat <tt>-</tt> in Infixnotation zur Verfügung. Diese Darstellung erleichtert das Lesen von Differenzlisten enorm.

Durch den Gebrauch von Differenzlisten kann die Effizienz bestimmter Operationen oder Prädikate beachtlich verbessert werden. Beispielsweise wird für die Verkettung zweier Listen <tt>As</tt> und <tt>Bs</tt> unter Verwendung des im Folgenden definierten Prädikats <tt>myappend</tt> eine Zeit in O(n) benötigt, wobei n die Länge der ersten Liste (<tt>As</tt>) bezeichnet.
<code id="4b8bd315b0023">
myappend([],Xs,Xs).
myappend([X|Xs],Ys,[X|Zs]) :-
    myappend(Xs,Ys,Zs).
</code>
<eval id="4b8bd315b789b">myappend([1,2,3],[a,b,c,d,e],Xs).</run>

Fügen Sie in der Definition von myappend an geeigneten Stellen write-Anwendungen ein, um den Prozess der Abarbeitung zu protokollieren. Bedingt durch Rekursion (Abstieg/Aufstieg) sind gerade 2n Schritte notwendig, um die Verkettungsliste zu bilden.

Unter Verwendung von Diffenzlisten für <tt>As</tt> und <tt>Bs</tt> gelingt die Verkettung mit <tt>append_dl</tt> sogar in konstanter Zeit. Die Definition lautet:
<code id="4b8bd315b0826">append_dl(Xs-Ys,Ys-Zs,Xs-Zs).</code>.
<eval id="4b8bd315b8010">append_dl([1,2,3|Xs]-Xs, [a,b,c,f]-[], Ys-[]).</run>
<!-- Hier ist das zugehörige Protokoll
44 ?- append_dl([1,2,3|Xs]-Xs, [a,b,c,f]-[], Ys-[]).
   Call:  (  8) rl_add_history("append_dl([1,2,3|Xs]-Xs, [a,b,c,f]-[], Ys-[]).") ? creep
   Exit:  (  8) rl_add_history("append_dl([1,2,3|Xs]-Xs, [a,b,c,f]-[], Ys-[]).") ? creep
   Call:  (  8) append_dl([1, 2, 3|_G381] - _G381, [a, b, c, f] - [], _G401 - []) ? creep
   Exit:  (  8) append_dl([1, 2, 3, a, b, c, f] - [a, b, c, f], [a, b, c, f] - [], [1, 2, 3, a, b, c, f] - []) ? creep
Xs = [a, b, c, f]
Ys = [1, 2, 3, a, b, c, f] 
Yes -->
Die Unifikation sorgt dafür, dass die Resultatliste nur durch Anwendung des head-tail-Separators entsteht. Intern ist also nur eine Zeigeroperation nötig, nämlich das Richten des Endezeigers von <tt>As</tt> auf den Anfang von <tt>Bs</tt>.

Beispiel: Umkehrliste <tt>reverse_dl(As,Bs)</tt> - <tt>Bs</tt> ist die Umkehrliste von <tt>As</tt>
<code id="4b8bd315b0fbb">
reverse_dl([],Xs-Xs).
reverse_dl([X|Xs],Ys-Zs) :- reverse_dl(Xs,Ys-[X|Zs]).
</code>
<eval id="4b8bd315b87e6">reverse_dl([1,2,3,4],Xs-[]).</run>

In diesem Beispiel bleibt die rekursive Idee der Erzeugung der Umkehrliste erhalten.
Im Übrigen kann man eine Definitionszeile ergänzen, um die Gebrauch von <tt>reverse_dl</tt> von der Repräsentation der Folgen durch Differenzlisten abzukoppeln (representation independence).
<code id="4b8bd315b1872">
reverse_dl1(Xs,Ys) :- reverse_dl(Xs,Ys-[]).
reverse_dl1([],Xs-Xs).
reverse_dl1([X|Xs],Ys-Zs) :- reverse_dl(Xs,Ys-[X|Zs]).
</code>
Die Differenzlistendarstellung ist dann allerdings noch an der Ergebnisausgabe erkennbar:
<eval id="4b8bd315b8fba">reverse_dl1([1,2,3,4],Xs).</run>

Beispiel: "Glätten" einer Liste: <tt>flatten_dl</tt><br/>
flat (engl.) bedeutet flach; flatten heißt dann soetwas wie "flach machen", besser "ebnen". Angewandt auf Listen heißt das: Eine beliebig verschachtelte Liste wird in eine unverschachtelte überführt, indem die atomaren Elemente der Teillisten als Elemente der "flachen" Resultatliste erscheinen.

Wir geben zunächst eine Definition, die Standard-Listen (nicht Differenzlisten) verwendet.
<code id="4b8bd315b26a8">
myflatten([],[]).
myflatten(X,[X]) :- atomic(X), not(X=[]).
myflatten([X|Xs],Ys) :-
	myflatten(X,Ys1),
	myflatten(Xs,Ys2),
	append(Ys1,Ys2,Ys).
</code>
<eval id="4b8bd315b978f">myflatten([1,['i',[4,a],6,[7]],8],Xs).</run>

Wir wollen <tt>myflatten</tt> nun so zu <tt>flatten_dl</tt> umschreiben, dass die Differenzlistentechnik eingesetzt wird.
<code id="4b8bd315b2e12">
flatten_dl([],Xs-Xs).
flatten_dl(X,[X|Xs]-Xs) :- atomic(X), not(X=[]).
flatten_dl([X|Xs],Ys-Zs) :-
	flatten_dl(X,Ys-Ys1),
	flatten_dl(Xs,Ys1-Zs).
</code>
<eval id="4b8bd315ba046">flatten_dl([1,['i',[4,a],6,[7]],8],Xs-[]).</run>

Es ist durchaus sinnvoll, ein Prädikat <tt>flatten_akku</tt> unter Benutzung der Akkumulatortechnik zu schreiben.

Beispiel: Sortieren einer Liste mit Quicksort mit <tt>quicksort</tt><br/>
In <tt>quicksort(As,Bs)</tt> ist <tt>As</tt> eine beliebige Permutation einer Menge von Elementen und <tt>Bs</tt> ist die aufsteigend sortierte Liste aus den Elementen von <tt>As</tt>.
Die verwendeten Symbole wurden so benannt, dass sie an bestimmte Bedeutungen erinnern:
<tt>T</tt>  ... Trennelement
<tt>Ls</tt> ... linke Teilliste
<tt>Rs</tt> ... rechte Teilliste 
<code id="4b8bd315b360f">
quicksort_dl([],Xs-Xs).
quicksort_dl([T|Xs],Ys-Zs) :-
	partition(Xs,T,Ls,Rs),
	quicksort_dl(Ls,Ys-[T|Ys1]),
	quicksort_dl(Rs,Ys1-Zs).
partition([],T,[],[]).
partition([X|Xs],T,[X|Ls],Rs) :- X=<T, partition(Xs,T,Ls,Rs).
partition([X|Xs],T,Ls,[X|Rs]) :- X>T, partition(Xs,T,Ls,Rs).
</code>
Zur Sortierung der Liste <tt>[2,4,1,8,5,3,9,2,7]</tt> beantwortet Prolog die Frage
<eval id="4b8bd315ba816">quicksort_dl([2,4,1,8,5,3,9,2,7],Xs-[]).</run>  


===Memoizing und adaptive Programme===
Die Idee, die dieser Technik zugrunde liegt, ist die Modifikation eines Prolog-Programms während der Laufzeit. Dies bedeutet, dass Fakten oder Regeln während des Berechnungsprozesses ergänzt, entfernt oder modifiziert werden können.

Zum Anfügen neuer Klauseln am Anfang, also vor evtl. vorhandenen Klauseln mit gleichnamigem Funktor und gleicher Stelligkeit, verwendet man <tt>asserta(&lt;klausel&gt;)</tt>.
Soll dies am Ende geschehen, nimmt man <tt>assert</tt> bzw. <tt>assertz</tt>.
Das Entfernen eines zweistelligen Prädikats erledigt <tt>retractall(&lt;funktor(_,_)&gt;)</tt>.

Dem Interpreter muss allerdings mittels <tt>dynamic</tt> mitgeteilt werden, dass sich die Definition des betreffenden Prädikats zur Laufzeit ändern wird. 

<code id="4b8bd315b3eb4" hidden>
succ(Pred, Succ) :-
	integer(Pred),
	!,
	Pred >= 0,
	Succ is Pred+1.
succ(Pred, Succ) :-
	integer(Succ),
	!,
	Succ > 0,
	Pred is Succ-1.
succ(Pred, Succ) :-
	var(Pred), var(Succ),
	succ_with_both_arguments_unbound.
</code>
Beispiel: Fibonacci ohne bzw. mit Memoizing<br/>
<code id="4b8bd315b4579">/* Fibonacci ohne memoizing */
fib(0,1).
fib(1,1).
fib(X,Y) :- 
    succ(X1,X), succ(X2,X1), 
    fib(X1,Y1), fib(X2,Y2), 
    Y is Y1+Y2.
</code>
<code id="4b8bd315b4dca">
/* Fibonacci mit memoizing */
fibmem(0,1).
fibmem(1,1).
fibmem(X,Y) :- 
    succ(X1,X), succ(X2,X1), 
    fibmem(X1,Y1), fibmem(X2,Y2), 
    Y is Y1+Y2,
    asserta(fibmem(X,Y)).

:- dynamic(fibmem/2).
</code>
Die Ergebnisse der folgenden Anfragen beindrucken insbesondere durch die sehr unterschiedliche Bearbeitungszeit.
<eval id="4b8bd315baef1">fib(21,F).</run> 
Es kann durchaus einige Minuten dauern, bis das Resultat, nämlich 17711, vorliegt. 
Im Gegensatz dazu, kann sogar 
<eval id="4b8bd315bb6c7">fibmem(1000,F).</run>
in Sekundenbruchteilen berechnet werden.

Mit dem Modifizieren vorhandener Prädikate werden wir uns hier nicht befassen. Es kann als Kopieren, Löschen des alten Prädikats und Anfügen der modifierten Kopie realisiert werden.

===Übungsaufgaben===
# Schreiben Sie ein Prolog-Programm zur Sortierung einer Liste von Zufallszahlen. Es soll jeweils eine Permutation erzeugt werden, die anschliessend auf "Sortiertheit" untersucht wird (generate and test). Vergleichen Sie Ihr Resultat mit dem Programm in obigem Text.
# Schreiben Sie ein Prolog-Programm zum Primzahltest.
# Realisieren Sie die Berechnung der n-ten Fibonaccizahl mit memoizing. Memoizing bedeutet, dass einmal berechnete Werte aufbewahrt werden. Vor jeder Neuberechnung wird geprüft, ob das gesuchte Resultat schon vorliegt. Ist dies das Fall, wird es genommen.
Memoizing realisiert man mit Prolog durch dynamisches Ergänzen von Fakten in der Datenbasis. Machen Sie sich zu diesem Zweck mit asserta vertraut. Berechnen Sie die 1000-te Fibonaccizahl unter Benutzung der bekannten rekursiven Definition und memoizing.
# Schreiben Sie ein Prädikat <tt>reverse_dl/2</tt> für die Bestimmung der Umkehrliste mit Differenzlistentechnik.