Probleme beim Verständnis eines bestimmten rekursiven Prolog-Prologs

Question

Ich lerne gerade Prolog.
Ich habe dieses rekursiven Prädikat:

add (0, Y, Y).
hinzufügen (Succ (X), Y, Succ (Z)): -
hinzufügen (X, Y, Z).

In Ordnung, so erfahrene Prolog Programmierer werden wahrscheinlich verstehen, was dieses Prädikat tut. Auf den ersten Blick scheint es nicht zu schwer zu verstehen; Wenn zwei Zahlen als erstes und zweites Argument angegeben werden, wird das Ergebnis der Addition als drittes Argument zurückgegeben. Klingt einfach? Tatsächlich.

Aber ich habe ein großes Problem zu verstehen, wie das eigentlich funktioniert. Ich habe die Beschreibung dieses Prädikats viele Male neu gelesen, aber ich kann nicht verstehen, wie es tatsächlich funktioniert. Und darum bitte ich um Hilfe.

Durch diese Abfrage:
add(succ(succ(succ(0))), succ(succ(0)), R).
Prolog instanziert und damit R als succ(succ(succ(succ(succ(0))))) zurückzukehren. Fein. Das muss stimmen. Ich habe jedoch keine Ahnung, warum es so ist.

Was ich Probleme Verständnis ist wie und warum Prolog den äußersten succ Funktor aus der ursprünglichen Abfrage abstreift. Da es rekursiv ist, gibt es die Ergebnisse als Argumente an sich selbst weiter und entfernt damit den äußersten Funktor succ, bis das Ziel vereinheitlicht werden kann. Ich verstehe, wie die succ(Z) und das Argument R funktioniert, aber ich bin scheinbar nicht in der Lage zu verstehen, wie es tatsächlich entfernt die äußerste succ Funktor, wie erwähnt. Für mich scheint es, als ob es eine succ anstatt es zu entfernen, wegen succ(X) in der Prädikatdefinition ist.

Jede Hilfe ist sehr geschätzt. Danke im Voraus!

Answer 1

Prolog sieht die Zeile add(succ(X),Y,succ(Z)) ... und denkt "Oh, es kann mit der Abfrage add(succ(succ(succ(0))), succ(succ(0)), R). abgeglichen werden, weil ich X = succ (succ (0)), Y = succ (succ (0)) setzen (vereinheitlichen) kann, succ (Z) = R! " Die wichtige Bedingung für Prolog, die, die es bestimmt kann es tun ist, dass succ(succ(succ(0))) kann auf succ(X) abgestimmt werden, der Rest ist nur einfach, weil Y und R in diesem ersten Schritt willkürlich gesetzt werden können (sie sind noch nicht vereinheitlicht) . Und succ(succ(succ(0))) kann auf succ(X) abgestimmt werden, nur weil Succ (A) zu Succ (B) passt jedes Mal, wenn A B zugeordnet werden kann - Sie sehen, es ist nicht sehr schwer für den Computer, es zu entscheiden. Der nächste Schritt ist, dass Prolog den Rest der Zeile betrachtet (: - add(X,Y,Z)) und die Abfrage add(succ(succ(0)), succ(succ(0)), Z) generiert. Denken Sie daran, dass succ (Z) = R und es wird nicht ändern, bis (wenn) der Berechnungspfad zurückgewiesen wird. Die nächste Abfrage lautet add(succ(0), succ(succ(0)), Z'), wobei succ (Z ') = Z ist. Dann add(0, succ(succ(0)), Z''), wo Succ (Z '') = Z '.

Dann kann Prolog die erste Regel verwenden, bestimmen, dass Z''=Y=succ(succ(0)). Dann gibt es nichts mehr zu tun, also schreibe einfach in den Ausgang R=succ(Z)=succ(succ(Z'))=succ(succ(succ(Y)))=succ(succ(succ(succ(succ(0))))).