Prolog: Problem bei Rekursion bei Listen

Cyless · Nov 10, 2012

Hey..
Haben im ersten Semester mit Prolog angefangen, und diese schöne Sprache macht mich echt fertig ^^

Ich habe folgendes Beispiel:

Code:

doppelt([], []).
doppelt([H|T], [H|[H|R]]).

Damit kann ich in der Eingabe aus

Code:

doppelt([1,2,3],X).

Code:

X=[1,1,2,2,3,3]

zaubern..

Nun, ich verstehe, dass Prolog bei Listen einen Head|Tail hat..
das wäre beim ersten Schritt :

Code:

H=1  T=[2,3]

danach

Code:

H=2 T=[3]

dann

Code:

H=3 T=[]

dann

Code:

H=[] T=[]

und ab hier verstehe ich Prolog nicht mehr..

Wo sind die anderen Zahlen in der zwischen zeit? Bzw. wie geht
Das "Trace Tool" verfolge ich schon seit guten 4 Stunden, versuche die Schritte zu analysieren, aber irgendwie erkenne ich kein "Muster".

Vielleicht weiß jemand eine Antwort darauf..
Kämpfe seit guten 10 Stunden dran, vllt. bin ich zu dumm

Lg

CDW · Nov 10, 2012

Wo sind die anderen Zahlen in der zwischen zeit? Bzw. wie geht

Prolog ist kein C & Co

Die Variablen sind entweder frei oder "belegt" (substituiert) und können dann keine neuen Werte "zugewiesen" bekommen. Dies gilt aber nur für den jeweiligen Aufruflevel (oder wie auch immer dieser korrekt genannt wird - schon länger her

). Also landen alle Werte auf dem Aufruferstack. Für jeden Aufruf "extra".

Bsp:
ich gehe erstmal davon aus, dass der Code doch eher so ausschaut:

Code:

doppelt([], []).
doppelt([H|T], [H|[H|R]]):-
  doppelt(T, R).

Wie war das noch mal - Matching, Unifikation/Substitution und Backtracking.
Frag mich aber bitte nicht nach dem genauen Unterschied zwischen Matching und Unifikationsschritten (im Folgendem als MU bezeichnet).

Code:

Eingabe <- doppelt([1,2],X).

(Aufruf)Level 1:
MU: doppelt([], []). | nein, da Param1 schon gebunden ist.
MU: doppelt([H|T], [H|[H|R]]) :- doppel ... | ja, matcht.
Vars: H wird mit 1 unifiziert, T mit [2,[]], R bleibt frei,
der Body wird aufgerufen:
doppelt([2,[]], R) => Level2

Level2:
MU: doppelt([],[]).  |nein
MU: doppelt([H|T], [H|[H|R]]) :- doppel ... | jep, matcht, 
Vars: H wird mit 2 unifiziert, T mit [] und R bleibt frei.
Body wird ausgeführt:
doppelt([], R)

Level3:
MU: doppelt([],[]). | jep, matcht, Parameter 2 des Aufrufers (der aus Level 2) ist nun mit [] unifiziert.
Fertig. Alles erfüllt. Nix mehr in diesem "Level" zu tun.

=> Level2: also lässt sich R aus mit [] unifiziert 
Vars: H = 2, T = [], R = []
und der Teil aus dem Head:
[H|[H|R]] = [2|[2|R]] wird nun zum [2|[2|[]]. Fertig.

=> Level1: [2|[2|[]] ist die "Antwort" für R. 
Vars: H=1, T = [2, []], R = [2|[2|[]]
Im Head "steht" nun 
[H|[H|R]] = [1|[1|R]]  => [1|[1|[2|[2|[]]]]. Fertig.

=> Aufrufer: ja, das X kann nun als [1|[1|[2|[2|[]]]]"aufgelöst" werden und das ist  eine andere Schreibweise für [1,1,2,2] :)

Disclaimer:
Keine Garantie für korrekte Nutzung von Begriffen sowie 100% Übereinstimmung mit dem tatsächlichen Auflösen der Anfrage. Aber es dürfte zumindest im groben zeigen, wie ~~die schwarze Magie hinter~~ Prolog so funktioniert :wink:

Cyless · Nov 11, 2012

Ich danke dir sehr für diese ausführliche Antwort..
Ich werde es morgen mal richtig durchstudieren..Jetzt sind mir wenigstens die ersten 3. lvl klar, aber dann wieder von 3. auf 2 und 1. ist noch so eine Sache.

Bleibe aber dran! Das komische bei Prolog ist, sobald es bei neuen Sachen "klick" macht, ist es selbstverständlich und einfach

CDW · Nov 12, 2012

Ich dachte, mit den "Aufrufleveln" wäre es einfacher zu verstehen - zumindest wenn man sonst eine der "üblicheren" Programmiersprachen kennt

Offizieller wäre die Erklärung eher so *~~unter'm Bett kram~~UB-DB befrag*:
0. Vergiss die Aufruferlevel/Stacks/Rückgabewerte und den ganzen "viel zu Low-Level" Krams. Das sind alles Krüken :evil:

1.Grundbegriffe:
------------
Substituierung: Assoziierung einer Variable mit einem Term, oft sind darunter
auch mehrere Assoziierungen gleichzeitig gemeint:
{ X <- [], Y <-[]} (Binde X mit [], Y mit [] )

Unifizierbarkeit: Terme können "gleich" gemacht werden durch Substituierungen.
Unifizierer:
eine Substituierung, die zwei Terme gleich "macht":
durch { X <- [], Y <-[]}
werden
doppelt([],[]) = doppelt(X,Y)
äquivalent.

Wobei meist nicht irgendeiner von vielen möglichen, sondern der allgemeinste
(MGU = most general unifiier, in Büchern oft auch als theta θ bezeichnet) gemeint ist.
Da die Unifizierung wichtig zum Verständnis ist:
http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/3_1.html (Unifizierungsbeispiel)
http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse5
http://matuszek.org/prolog/prolog-unification.html
Es gibt auch entsprechende Algorithmen zum Unifizieren - aber wie gesagt, grob gesehen
geht es darum, eine/mehrere Substituierungen zu finden, die zwei Terme "gleich" machen.

Beispiel:
Prologeingabe:

Code:

doppelt([],[]) = doppelt(X,Y).

wird true zurückgeben zusammen mit "X=[], Y=[]"
Oder:

Code:

user_rights('Cyless', 'user').
user_rights('CDW', 'mod').

wenn wir nun eine Anfrage stellen:

Code:

user_rights(Name, 'mod').
Versuch einer Unifizierung:
user_rights('Cyless', 'user') = user_rights(Name, 'mod').
{Name <- 'Cyless'}, aber 'user' <- 'mod' lässt sich nicht unifizieren (beides sind gebundene Variablen) und 'user' ungleich 'mod'
Versuch einer Unifizierung:
user_rights('CDW', 'mod') = user_rights(Name, 'mod').
{Name <- 'CDW'} und 'mod' = 'mod'
Also unifizierbar mit Name = 'CDW', anders gesagt: 
user_rights('CDW', 'mod') = user_rights(Name, 'mod') sind gleich, wenn Name durch 'CDW' substituiert wird:
user_rights('CDW', 'mod') = user_rights('CDW', 'mod')
Antwort: true, Name = 'CDW'

Andere Anfrage:

Code:

user_rights('CDW',Who)
=> das gleiche wie oben
=> Antwort: Who = 'mod'

Oder:

Code:

user_rights(User, Who)
Versuch einer Unifizierung:
user_rights('Cyless', 'user') = user_rights(User, Who).
{User <- 'Cyless', Who <- 'user'}
Anders gesagt:
user_rights('Cyless', 'user') = user_rights(User, Who) sind gleich, wenn User durch 'Cyless' und Who durch 'user' substituiert werden:
user_rights('Cyless', 'user') = user_rights('Cyless', 'user').
Weitere Klauseln vorhanden? => ja, also ist es ein Choicepoint, merken
Eine Antwort: 
true
User = 'Cyless', Who = 'user' ?
Es gibt weitere Antworten (je nach Prologkonsole irgendwie gekennzeichnet)
Weitere Antwort:
Versuch einer Unifizierung mit der nächsten Klausel:
user_rights('CDW', 'mod') = user_rights(User, Who).
{User <- 'CDW', Who <- 'mod'}
Antwort:
User = 'CDW', Who = 'mod'

Auf praktische Probleme, wie z.B Rücksicht auf rekursive Konstrukte:
X = doppelt(X), die Reihenfolge der Substituierungen usw.
möchte ich nicht weiter eingehen (die sind in Prolog mehr oder weniger schon gelöst)
--------------------------------------------
--------------------------------------------

2. Die ganze Lösungsgeschichte in Prolog lässt sich prinzipiell auf eine Unifizierung der Terme zurückführen.
Weitere Stichworte für die Vertiefung: Horn Clauseln, SLD - Resolution.

Der grobe Lösungsalgo von Prolog (SLD-Resolution):

Suche eine zur Query passende Klausel
-- Versuche den Head zu unifizieren:
-----ist unifizierbar: speichere die MGU und löse die Query mit dieser Klausel
-----ist nicht unifizierbar: suche nächste Klausel.

Dabei: benenne Variablen so um, dass es keine Kollisionen gibt.
Falls gelöst: Antwort aus den Unifizierungen (MGUs) "ableitbar", sonst "fail"

-------------------------------------
-------------------------------------
3. Auf den Code angewendet:

Also wir haben:
Klauseln:

Code:

doppelt([], []) :- true.
doppelt([H|T], [H|[H|R]]):-  doppelt(T, R).

Query:

Code:

doppelt([1,2], DoppelList).

Schritt1:
--------

Code:

Suche Klausel:
doppelt([],[]) => Head nicht mit doppelt([1,2], DoppelList) unifizierbar. 
Warum:
doppelt([], []) :- true. ist eigentlich nichts anderes als:
doppelt(Param1, Param2) :- Param1 = [], Param2 = [], true.
Oder: für alle x,y gilt: (doppelt(x,y) => x = [], y = [])

Es gibt keine Lösung für die Anforderung:
(Param1 = [] UND Param1 = [1,2]) <=> [] = [1,2]).
Bzw. ist Param1  schon an [] gebunden und damit kommt es gleich beim Unifikationsversuch zum Vergleich: 
[1,2] = []
der fehlschlägt (und damit die ganze Unifikation) => also nächste Klausel suchen:

doppelt([H1|T1],  [H1|[H1|R1]]):- doppelt(T1, R1).
Header unifizierbar:
MGU1 = {H1 <- 1, T1 <- [2,[]],  [H1|[H1|R1]] <- DoppelList}

Nun nach Algo: Header unifizierbar => löse die Query mit dieser Klausel
=> also bildet der Body dieser Klausel unsere neue Query:
doppelt(T1, R1)
da T1 mit [2,[]] unifiziert:
doppelt([2,[]], R1)

Schritt2:
--------

Code:

Suche Klasel:
doppelt([], []) => nicht mit [2,[]] unifizierbar. 
 => nächste Klausel:

doppelt([H2|T2],  [H2|[H2|R2]]):- doppelt(T2, R2).
Header unifizierbar:
MGU2 = {H2 <- 2, T2 <- [], [H2|[H2|R2]] <- R1}

Nun nach Algo: Löse die Query mit dieser Klausel => neue Query:
doppelt(T2,R2), da T2 mit [] unifiziert:
doppelt([], R2)

Schritt3:
--------

Code:

Suche Klausel:
doppelt([], []):- true.
Header unifizierbar:
MGU3 = {R2 <- []}

Nach Algo Löse mit dieser Klausel: => true => fertig!

Nun haben wir folgende MGUs:

Code:

MGU1 = {H1 <- 1, T1 <- [2,[]],  [H1|[H1|R1]] <- DoppelList}
MGU2 = {H2 <- 2, T2 <- [], [H2|[H2|R2]] <- R1}
MGU3 = {R2 <- []}

Ohne auf die formalen Sachen mit MGUs einzugehen:
daraus lässt sich die Antwort "erstellen".

Dazu:
wende einfach die vorhandenen Substituierungen (X <- Y) an:
MGU3 (R2 <- []) auf MGU2:
-------------------------

Code:

{H2 <- 2, T2 <- [], [H2|[H2|[]]] <- R1}

R2 also mit [] ersetzt.

=> Die Substituierungen in diesem Ergebnis nun auf sich selbst anwenden
(hier habe ich keine Ahnung, ob das formal so passt - prinzipiell
hätte man schon während der einzelnen Schritte [H2|...] Zusammengesetzte Terme mit vorhandenen
Substitudionen wie H2 <-2 ersetzen sollen/können? Sollte aber imho mit diesen Zwischenschritten
verständlicher sein):

Ergebnis:

Code:

{H2 <- 2, T2 <- [], [2|[2|[]]] <- R1}

H2 im zusemmengesetzten Term [H2|[H2|[]]] durch 2 ersetzt.

Das Ergebnis nun auf MGU1 anwenden:

Code:

{H1 <- 1, T1 <- [2,[]],  [H1|[H1|[2|[2|[]]]]] <- DoppelList, H2 <- 2, T2 <- []}

R1 also mit [2|[2|[]]] ersetzt. Für T2, H2 passiert nix.

Wende es auf sich selbst an:
Ergebnis:

Code:

{H1 <- 1, T1 <- [2,[]],  [1|[1|[2|[2|[]]]]] <- DoppelList, H2 <- 2, T2 <- []}

Da die Variablen immer so umbenannt wurden, dass sie einzigartige Bezeichner haben, können wir die MGUs auch einfach
"in einem Haufen" schreiben:

Code:

{H1 <- 1, T1 <- [2,[]],  [H1|[H1|R1]] <- DoppelList, H2 <- 2, T2 <- [], [H2|[H2|R2]] <- R1, R2 <- []}

und dann solange Substituierung darauf anwenden, bis sich nichts mehr ändert.
Dabei müsste man eventuell noch die Reihenfolge der Substituierungen und andere Feinheiten beachten - aber auch dafür gibt es
Regeln und Definitionen (wie auch Optimierungen, die Prolog dabei macht):
=>

Code:

1.{H1 <- 1, T1 <- [2,[]],  [H1|[H1|R1]] <- DoppelList, H2 <- 2, T2 <- [], [H2|[H2|R2]] <- R1, R2 <- []}
2.{H1 <- 1, T1 <- [2,[]],  [1|[1|R1]] <- DoppelList, H2 <- 2, T2 <- [], [H2|[H2|R2]] <- R1, R2 <- []}
3.{H1 <- 1, T1 <- [2,[]],  [1|[1|R1]] <- DoppelList, H2 <- 2, T2 <- [], [2|[2|R2]] <- R1, R2 <- []}
4.{H1 <- 1, T1 <- [2,[]],  [1|[1|[2|[2|R2]]]] <- DoppelList, H2 <- 2, T2 <- [], [2|[2|R2]] <- R1, R2 <- []}
5.{H1 <- 1, T1 <- [2,[]],  [1|[1|[2|[2|[]]]]] <- DoppelList, H2 <- 2, T2 <- [], [2|[2|R2]] <- R1, R2 <- []}

Gebe es aus:

Code:

true.
H1 = 1
T1 = [2,[]]
DoppelList =  [1|[1|[2|[2|[]]]]] 
H2 = 2
T2 = []

Da der User allerdings nicht an internen Variablen interessiert sein dürfte,
werden nur die Query-Variablen ausgegeben:
DoppelList = [1|[1|[2|[2|[]]]]]