Rekursion und Listen

Rekursion und Listen
Wiederholung: Bratko Kapitel 1 und 2, was haben wir gelernt
Prinzip der Rekursion
Listen, Listen, Listen
Etwas komplexere Beispielprogramme
Datenobjekte in Prolog
Datenobjekte
einfache Objekte
Variablen
Konstanten
Atome
Zahlen
Strukturen
Zusammenfassung Bratko 1.1
Es ist einfach in Prolog Relationen zu definieren, indem man
die n-tupel angibt, die die Relation erfüllen. Beispiel etwa die
Elternrelation.
Der Benutzer kann das Prolog System sehr leicht zu den
definierten Relationen befragen indem ein oder mehrere Ziele
an das System übergeben werden
Ein Prolog Programm besteht aus Klauseln, die mit einem
Punkt enden.
Die Argumente von Relationen können sein: einfache Objekte
als Konstanten bzw. Variable und komplexe Objekte,
Strukturen.
Die Antwort von Prolog ist entweder positiv oder negativ je
nachdem ob die angefragte Sequenz von Zielen erfüllbar ist.
Falls vorhanden werden Variablenbelegungen ausgegeben.
Wenn mehrere Wege zur Erfüllung des Ziels führen wird
Prolog auf Anforderung alle ausgeben
Zusammenfassung Bratko 1.2
Ein Fakt ist unbedingt, d.h. unabhängig von irgendwelchen
Bedingungen wahr.
Beispiel Fakt: scheibe(erde).
Eine Regel ist wahr wenn bestimmte Bedingungen erfüllt sind.
Beispiel Regel: kugel(X) :- umrundbar(X).
Eine Regel hat einen bedingten Teil (condition part) = Rumpf
(body) und einen schließenden Teil (conclusion part) = Kopf
(head)
Ist die Bedingung wahr tritt die Konsequenz ein.
Zusammenfassung Bratko 1.2
Graphendiagramme von Relationen: Knoten
korrespondieren mit Objekten = Argumente der
Relationen.
Einfache (unäre) Relationen werden neben
das entsprechend Objekt geschrieben.
Gerichtete Kanten (Pfeile) korrespondieren mit
binären Relationen. Relationen die durch
andere Relationen definiert sind (abgeleitet)
werden durch gestrichelte Kanten
repräsentiert.
Wenn die durchgehenden Kanten erfüllt sind
so sind auch die abgeleiteten gestrichelten
Kanten erfüllt.
Zusammenfassung Bratko 1.2
X
elternteil
female
mutter
Y
mutter(X,Y):- parent (X,Y), female(X).
Übung: schreiben Sie die schwester-Relation als
Graphendiagramm
Zusammenfassung
Erster Eindruck der Rekursion: Vorfahren-Relation
Schlüssel ist die Verwendung von predecessor in der
Definition der Relation selbst.
Wir bauen die Relation aus zwei Regeln, dem direkten
Vorfahren und den indirekten Vorfahren.
Wichtig 1: Abbruchregel
Wichtig 2: die Argumente der Rekursion bewegen sich auf die
Abbruchregel zu
Deklarative und prozedurale
Bedeutung Bratko 1.5
Der deklarative Aspekt eines Prolog Programms betrifft nur die
Relationen, die im Programm definiert sind.
Der prozedurale Aspekt betrifft die Art und Weise wie der
Output des Programms zustande kommt.
Vorteil von Prolog: übernimmt weite Teile der prozeduralen
Aspekte selbst. Damit kann sich der Programmierer auf die
normalerweise leichter zu verstehenden deklarativen Aspekte
konzentrieren. Späterhin kommt man jedoch nicht umhin sich
auch mit dem internen Programmablauf zu befassen und
diesen etwa durch geschickte Anordnung der Klauseln oder
direkte Eingriffe wie den Cut zu beinflussen.
Zusammenfassung Bratko 2.1
Variablen: Strings beginnend mit
Grossbuchstaben oder Underscore. Annonyme
Variable: _
Tritt eine anonyme Variable in der selben
Klausel mehrmals auf, so repräsentiert sie
jeweils eine neue anonyme Variable.
Der Skopus von Variablennamen ist eine
Klausel. D.h. wenn der Variablenname X15 in
zwei Klauseln erscheint, bezeichnet er zwei
verschiedene Variablen. Wenn er in derselben
Klausel zweimal erscheint bezeichnet er
dieselbe Variable.
Konstanten hingegen bezeichnen für alle
Prozedurale Steuerung
Prozedur Execute (Bratko S.42) List of Goals G1,G2,.. Gm
- Ist die goal-Liste leer, terminiere mit success, yes, true
- Ist die goal-Liste nicht leer, mache weiter mit SCANNING
- SCANNING: scanne durch die Programmklauseln top-down
bis die erste Klausel C gefunden wird, so dass head(C) mit
dem ersten Ziel G1 matcht.
Falls keine Klausel gefunden wird, terminiere mit fail
Falls C matcht und C die Gestalt H:- B1,...Bn hat, alle
Variablen in H umbenenen zu C', so dass es keine
gemeinsamen Variablen zwischen G1- Gm und C' gibt
H' :- B1'...Bn'
Matche H und G1 mit Instantierung der Variablen S.
In der Zielliste ersetze G1 mit B1'..Bn'
so dass die Zielliste jetzt: B1'..Bn', G2..Gm
Substituiere die Variablen in er neuen Zielliste gemäß S
Zielliste: B1'',..,Bn'',G2'',..Gm''
Prozedurale Steuerung
Wenn C ein Fakt ist: n = 0, die Zielliste wird kürzer → in
Richtung erfolgreiche Terminierung.
Arbeite rekursiv mit derselben Prozedur die neue Zielliste ab.
Ist diese Zielliste erfolgreich, so soll auch die originale Zielliste
erfolgreich sein.
Ist diese Zielliste nicht erfolgreich, verwerfe die Zielliste und
gehe zu Scanning. Setze Scanning fort, mit der Klausel die
unmittelbar auf Klausel C folgt und versuche eine andere
Klausel zu finden die mit dem ersten Ziel der noch
vorhandenen Zielliste matcht.
Vgl. auch Pascalstyle des Abarbeitungsalgorithmus in Bratko,
Seite 45
Monkey Banana Problem
Beispiel zum Formulieren eines komplexeren
Problems mit Prolog.
"Ein Affe steht an der Tür zu einem Raum. In
der Mitte hängt eine Banane von der Decke.
Der Affe will die Banane, kann sich aber nicht
weit genug strecken. Am Fenster gibt es eine
Kiste."
Aktionen: walk, climb, push, grasp
Monkey Banana Problem
Die Monkeyworld ist immer in irgendeinem
Zustand, der sich über Aktionen verändern
kann.
Initialzustand
- Affe an der Tür
- Affe auf dem Boden
- Kiste am Fenster
- Affe hat die Banane nicht
nicht alle moves sind in jeder Situation
möglich. grasp etwa nur dann wenn der Affe
auf der Kiste direkt unter der Banane steht und
sie noch nicht hat
move(State1, Move, State2)
Monkey Banana Problem
move(state(middle, onbox, middle, hasnot),
grasp,
state(middle, onbox,middle, has)).
Affe onfloor kann zu jeder Position gehen egal
wie Box und Banana beleg sind.
move(state(Pos1, onfloor,Box, Has),
walk,
state(Pos2, onfloor,Box, Has)).
Monkey
Banana
Problem
zentrales Anfrageprädikat canget(State), muss
wahr sein, wenn der Affe die Banane schon
hat.
canget(state(_,_,_,has).
canget(State1):- move(State1,Move,State2),
canget(State2).
Deklarative Programmformulierung,
möglicherweise korrekt, zugleich prozedural
inkorrekt.
Für das monkey-banana Problem wichtig, dass
grasp, climb, push und walk in dieser
Reihenfolge im Programm sind (Bratko S. 49)
Monkey Banana Problem
move(state(middle,onbox,middle,hasnot),
grasp,
state(middle,onbox,middle,has)).
move(state(P,onfloor,P,H),
climb,
state(P,onbox,P,H).
move(state(P1,onfloor,P1,H),
push(P1,P2),
state(P2,onfloor,P2,H).
move(state(P1,onfloor,B,H),
walk(P1,P2),
state(P2,onfloor,B,H).
canget( state(_,_,_,has).
canget( State1):move(State1, Move, State2),
canget(State2).
Rekursion
Definition: "a backward movement, return"
Anwendung: beschreibe Strukturen, die
andere Strukturen als Komponenten enthalten.
Programme, die eine Kopie von sich selbst
erfüllen müssen, bevor sie selbst terminieren.
Funktionen die durch sich selbst definiert sind.
fakultät_rekursiv(n)
{
wenn n <= 1
dann return 1
sonst return ( n * fakultät_rekursiv(n-1) )
}
Listen
Listen sind eine Datenstruktur, die sehr
gebräuchlich in der nicht-numerischen
Programmierung ist.
Liste: "geordnete Folge von Elementen
beliebiger Länge"
Elemente: beliebige Terme, Konstanten,
Variablen, Strukturen → insbesondere andere
Listen.
Wichtig: Listen können praktisch jede Art von
Struktur repräsentieren, die man in der
symbolischen Programmierung verwenden will
Beispiel: Parsebäume, Grammatiken,
Listen
Listen als spezieller Baum:
- eine Liste ist entweder die leere Liste [ ] oder
eine Struktur mit zwei Komponenten: head
und tail
- das Ende der Liste ist tail als leere Liste
- head und tail sind Komponenten des
Funktors '.'
Liste aus einem Element 'a': .(a,[ ]) oder [a]
.(a,.(b,.(c,[ ]))) oder [a,b,c] komma-getrennt in
..
eckigen Klammern.
a
[]
Beispiele legaler Listen
[]
[the, men, [like,to,fish] ]
[a,V1,b,[X,Y]]
Jeder horizontale Level ist eine Liste mit
einer
bestimmten Anzahl von Elementen.
[a,V1,b,[X,Y]]
[]
1. Level: 4
2. Level: 2
a V1 b
[]
X
Y
Splitte dieRestlistenoperator
Liste in Head und Tail. Kopf der Liste
ist das erste Element des '.' Funktors bzw. das
erste Element nach der öffnenden eckigen
Klammer.
Kopf: erstes Element
Schwanz: alle bis auf das erste Element
Die leere Liste hat weder Kopf noch Schwanz
Spezielle Notation [X|Y]: Liste mit Kopf X und
Schwanz Y, '|' heisst Restlistenoperator
Beispiele: p([1,2,3]).
p([the, cat, sat, [on,the,mat]]).
?- p([X|Y]).
X=1 Y= [2,3]
X=the, Y=[cat,sat,[on,the,mat]].
Listenmanipulation
Drucke eine Liste aus: built-in 'write' Prädikat,
druckt das Argument auf den Bildschirm.
drucke([ ]).
drucke([X|L]) :- write(X), drucke(L).
Abbruchregel tritt bei leerer Liste als Eingabe
auf.
Rekursion macht Liste immer kürzer, bewegt
sich also auf die Abbruchregel zu.
Rekursive Suche in Listen
Wir suchen in einer Listenach Information.
Liste von Städten:
[shanghai, manchester, vancouver, portland]
Aufgabe: ist eine bestimmte Stadt in der Liste?
(1) head ist die stadt
(2) stadt ist in tail →
(1') head of tail ist die stadt
(2') stadt ist in tail of tail
(1'') head of tail of tail ist die stadt
(2'') stadt ist in tail of tail of tail
Rekursive Suche in Listen
Prologimplementation:
member(X,Y). true wenn X in der Liste ist , die
durch Y repräsentiert ist
(1) member(X,[Y|_] :- X=Y.
(2) member(X,[_|Y]) :- member(X,Y).
(1) als Grenzbedingung, (2) als Rekursionsfall
Rekursionsbewegung auf ein Ende zu: jeder
Neuaufruf bekommt eine kürzere Liste
Alternative Schreibweise:
(1) member(X,[X|_].
Rekursion Fallen
Vorsicht vor zirkulären Definitionen
parent(X,Y) :- child(Y,X).
child(A,B) :- parent(B,A).
Anfrage parent oder child führt zu niemals
endender Suche
Vorsicht Linksrekursion: Eine Regel verursacht
ein neues Ziel welches mit demjenigen
äquivalent ist, das dazu führte, dass die Regel
aufgerufen wurde.
person(X):-person(Y), mother(X,Y).
person(adam).
?- person(X). % erste Regel wird ewig
Rekursion Fallen
Die bloße Angabe der relevanten Fakten und
Regeln stellt nicht sicher, dass Prolog sie
immer finden wird: wie sucht Prolog, welche
Variablen werden wie instantiert wenn eine der
Regeln benutzt wird.
Generell: Fakten vor Regeln, wann immer
möglich
Rekursion Fallen
islist([A|B]) :- islist(B).
islist([ ]).
?- islist([ a,b,c,d]).
?- islist([ ]).
?- islist(f(1,2,3)).
?- islist(X).
Rekursiver Vergleich
Prolog besitzt eingebaute Prädikate um Integer
zu vergleichen. Ein Strukturvergleich ist
komplizierter. Es müssen alle Komponenten
verglichen werden. Sind Komponenten
Strukturen, muss der Vergleich rekursiv sein.
Beispiel Verbrauchsstatistik. Fahre
verschiedene Autos auf verschiedenen Routen
und messe den Benzinverbrauch
fuel_consumed(suv,[13.1,10.4,...]).
fuel_consumed(sedan,...).
fuel_consumed(hybrid,...).
Rekursiver Vergleich
Ein Autotyp soll gleich oder besser als ein
anderer sein, wenn seine Verbrauchsmenge
mindestens 5% besser ist als der Durchschnitt
beider ist.
Entsprechend 1/40 der Summe beider
Verbrauchswerte.
Infromal:
equal_or_better_ongas(Good, Bad):Threshold is ((Good + Bad)/2*0.95), Good =<
Threshold.
Rekursiver Vergleich
Eine Liste ist immer besser als eine andere,
wenn ihr Kopf equal_or_better_ongas erfüllt.
und ihr Schwanz always_better erfüllt.
→ Prädikat geht beide Testlisten nach rechts
bis sie am Ende sind.
→ Dann muss ein Abbruchprädikat die
Rekursion beenden.
→ Wenn nur einmal equal_or_better scheitert,
scheitert always_better und damit das
Vergleichsprädikat prefer
Rekursiver Vergleich
prefer(Auto1, Auto2):fuelconsumed(Auto1, Mengen1),
fuelconsumed(Auto2, Mengen2),
always_better(Mengen1,Mengen2).
always_better([ ],[ ]).
always_better([Strecke_a|Rest_a],[Strecke_b|
Rest_b]) :- equal_or_better_ongas(Strecke_a,
Strecke_b), always_better(Rest_a,Rest_b).
Rekursiver Vergleich
Aufgabe: implementieren Sie das Ganze mit
einem Prädikat sometimes_better das schon
matcht wenn einmal equal_or_better_ongas
zutrifft.
Join von Strukturen
Dreistelliges Prädikat, das zwei Listen in einer
neuen Liste zusammenhängt
?- append([a,b,c],[3,2,1],[a,b,c,3,2,1]).
?- append([alpha,beta],[gamma,delta],X).
X=[alpha,beta,gamma,delta]
append(X,[b,c,d],[a,b,c,d]).
X=a.
%was ist hier falsch?
Join
von
Strukturen
Grenzbedingung: erste Liste ist leere Liste
jede Liste, die der leeren
Liste
angehängt wird ist diese
Liste
Rekursionsfall: (1) das erste Element der
ersten Liste wird das erste Element der dritten
Liste (Ausgabeliste)
(2) dem Schwanz (Rest) der ersten Liste wird
die zweite Liste angehängt um den Schwanz
der dritten Liste zu bilden
(3) verwende append selbst um (2)
durchzuführen
(4) da im Rekursionsfall das erste Argument
Join von Strukturen
append([ ], L,L).
append([X|L1],L2[X|L3]):- append(L1,L2,L3).
Join von Strukturen
Aufruf von myappend mit:
[trace] 26 ?- myappend([1,2],[3,4],N).
Call: (7) myappend([1, 2], [3, 4],N=_G485) ? creep
entspricht:
myappend([X=1|L1=[2]],L2=[3,4],[1,G_554]) :myappend([2],[3,4],_G554).
Call: (8) myappend([2], [3, 4],_G554) ? creep
entspricht:
myappend([X=2|L1=[]], L2=[3,4],[2,_G557]) :myappend([],[3,4],_G557).
Call: (9) myappend([], [3, 4], _G557) ? creep
Join von Strukturen
das das erste Argument die leere Liste ist, wird die
Terminierungsregel aufgerufen und _G557 bekommt den
konkreten Startwert:
_G557=[3,4]
Exit: (9) myappend([], [3, 4], [3, 4]) ? creep
Um den gesuchten Wert von N zu erhalten müssen die
Hilfsvariablen _G485 und _G554 zurückverfolgt werden um
daraus N zu rekonstruieren.
_G554 = [2,_G557] = [2,3,4]
Exit: (8) myappend([2], [3, 4], [2, 3, 4]) ? creep
_G485 = [1,_G554] = [1,2,3,4]
Exit: (7) myappend([1, 2], [3, 4], [1, 2, 3, 4]) ? creep
und schließlich:
N = G_485
N = [1, 2, 3, 4]
Listenzerlegung mit append
Durch Einsatz von Variablen kann append
auch in die andere Richtung zur
Listenzerlegung benutzt werden.
?- append( L1,L2,[a,b,c]).
L1 = [ ] L2=[a,b,c];
L1 = [a] L2=[b,c];
L1 = [a,b] L2=[c];
L1 = [a,b,c ] L2=[];
no
Erzeugung einer bestimmten Liste
mit append
Wir können nach einem bestimmten Pattern in
einer Liste suchen.
?- append( Before,[may|After],
[jan,feb,mar,apr,may,jun.jul,aug,sep,oct,nov,de
c]).
Before = [jan,feb,mar,apr]
After = [jun,jul,aug,sep,oct,nov,dec]
Zusammenfassung
Schreiben Sie Beispiele zum (my)append Prädikat
Schreiben Sie ein Prädikat odd das nur Listen mit gerader
Zahl von Argumenten akzeptiert (Hinweis, die leere Liste sei
odd; Hinweis, vor dem Restlistenoperator dürfen auch
mehrere Argumente stehen.
Lesen Sie Bratko Kapitel 3
adding
deleting
sublist
permutationen