Prolog - Rekursion

[Franz]

Hi,

kann mir einer den genauen Ablauf von Prolog erklären.

Hier ein Beispiel:

letztes_element(X,[X]). /* 1 Regel */
letztes_element(X,[Y|YS]) :- letztes_element(X,YS). /* 2 Regel */

?- letztes_element(X,[5,3,1]).

1.) Prolog guckt ob es bei der 1 Regel zutrifft. Nein, da wir mehr als ein Element haben.

2.) Prolog geht in die 2 Regel und führt den Teil letztes_element(X,YS) aus. Also ist X = [3,1].

Was folgt nun ?

Ich bin sehr dankbar für alle Antworten.

[Stefan Bach]

Hallo Franz,

letztes_element(X,[X]). /* 1 Regel */
letztes_element(X,[Y|YS]) :- letztes_element(X,YS). /* 2 Regel */

?- letztes_element(X,[5,3,1]).

Am besten kann dir das sicherlich Prolog selber erklären:

| ?- trace.
|
| Yes
| [trace] ?- letztes_element(X,[5,3,1]).
|    Call: (7) letztes_element(_G504, [5, 3, 1]) ? creep
|    Call: (8) letztes_element(_G504, [3, 1]) ? creep
|    Call: (9) letztes_element(_G504, [1]) ? creep
|    Exit: (9) letztes_element(1, [1]) ? creep
|    Exit: (8) letztes_element(1, [3, 1]) ? creep
|    Exit: (7) letztes_element(1, [5, 3, 1]) ? creep
|
| X = 1
|
| Yes

Wenn du letztes_element(X,[5,3,1]) als Abfrage eingibst, dann versucht Prolog das ganze so zu matchen, dass er für X etwas passendes einsetzt, so dass dein Prädikat erfüllt wird. Dabei geht Prolog Backtracking-mäßig von oben nach unten durch und probiert so lange rum, bis entweder was passt oder alles fehlschlägt.

Also probiert er erst Regel 1, die klappt nicht, weil [5, 3, 1] nicht auf [X] passt, Regel 2 kann aber angewandt werden und besagt, dass deine Abfrage dann klappt, wenn letztes_element(X,[3, 1]) wahr ist. Jetzt geht die Sache wieder von oben los, Rgegel zwei passt und besagt, dass dies der Fall ist, wenn letztes_element(X,[1]) wahr ist.
Bei dem dritten Durchlauf von oben passt die Aussage auf den Kopf von Regel 1, wenn die Substitution [1/X] angwendet wird. Da Regel 1 ein Faktum ist, kann deine Eingabe also für X = 1 erfüllt werden, und das gibt dir Prolog auch aus.

Solltest du noch ein paar Prolog Aufgaben suchen, dann darfst du übrigens gerne unter http://eins2003.info.uni-karlsruhe.de/uebungsblaetter.php gucken.
Wie kommst du eigentlich auf Prolog? So zum Spaß? Ich darf recht bald meine Info 1 Klausur schreiben, mag sein, dass es da auch dran kommt.

Viele Grüße,

Stefan

[Tim Tepaße]

Hallo Franz,

kann mir einer den genauen Ablauf von Prolog erklären.

Stefan hat - für mich relativ Unkundigem in Prolog - schon recht einleuchtend
geantwortet. Vor einer Woche gab es genau dieselbe Frage schonmal; dort wurde
ebenso ausführlich geantwortet: </archiv/2004/1/70281/>

Ist das zur Zeit eine Übungshausaufgabe irgendwo?

(Ich habe mir vor längerer Zeit mal dieses Prologtutorial gebookmarkt:
http://www.coli.uni-sb.de/~kris/learn-prolog-now/)

Tim

[Stefan Bach]

Hallo,

Vor einer Woche gab es genau dieselbe Frage schonmal; dort wurde
ebenso ausführlich geantwortet: </archiv/2004/1/70281/>

Ich hab da grade mal reingeschaut, wenn ich mich recht entsinne, dann sollte man aber auf eines wirklich genau achten. Prolog ruft meines Wissens keine Funktionen auf. Es ist nicht so, als dass eine Funktion sich selbst rekrusiv aufrufen könnte oder ähnliches, hier geht es lediglich drum eine Substitution zu finden, welche einen wahren Ausdruck liefert.

Hier noch ein direkter Link zu der ersten Übung, die Prolog beinhaltete: http://eins2003.info.uni-karlsruhe.de/folien/ue06.pdf#page=8, ist zwar eine wirklich sehr kurze Einleitung, aber vielleicht kanns ja helfen.

Ist das zur Zeit eine Übungshausaufgabe irgendwo?

Das würde mich auch mal interessieren...

Viele Grüße,

Stefan

[Tom]

Hello Franz,

wird dieder weltfremde Schwachsinn an den Unis immer noch gelehrt? Damit habe ich mich schon vor Jahrzehnten rumplagen müssen.

Liebe Grüße aus http://www.braunschweig.de

Tom