PROLOG: addOne predicate, what happens when temp. variable hits the base clause, how does Prolog call values?

Question

I need some help with understanding the following Prolog source code:

addone([],[]).
addone([H|T],[H1|T1]):-H1 is H + 1, addone(T,T1).

This code, takes a given list and therefore prints out another one which has +1 added to each argument of it.

I don't understand how exactly this work, if I trace it:

[trace] 69 ?- addone([1,2,3],X).
   Call: (6) addone([1, 2, 3], _G1196) ? creep
   Call: (7) _G1273 is 1+1 ? creep
   Exit: (7) 2 is 1+1 ? creep
   Call: (7) addone([2, 3], _G1274) ? creep
   Call: (8) _G1279 is 2+1 ? creep
   Exit: (8) 3 is 2+1 ? creep
   Call: (8) addone([3], _G1280) ? creep
   Call: (9) _G1285 is 3+1 ? creep
   Exit: (9) 4 is 3+1 ? creep
   Call: (9) addone([], _G1286) ? creep
   Exit: (9) addone([], []) ? creep
   Exit: (8) addone([3], [4]) ? creep
   Exit: (7) addone([2, 3], [3, 4]) ? creep
   Exit: (6) addone([1, 2, 3], [2, 3, 4]) ? creep
X = [2, 3, 4].

I get to the point:

Call: (9) addone([], _G1286) ? creep
   Exit: (9) addone([], []) ? creep

From here I don't understand how when I reach the base clause Prolog recalls its saved values?

Can you please explain me how this thing works, what is the logic behind it?

Thank you in advance, Petar!

Each Exit is a return from a recursive call back to a point in addone where there were pending values/results. So you're seeing all those recursive calls finally return and the final results going in their place. — lurker

Unknown Unknown · Accepted Answer · 2015-02-23T10:31:24

I guess the answer you might be looking for is:

When Prolog sees a predicate defined like this (most simple example):

foo([]).
foo([_|_]).

This predicate will now be deterministic on proper lists. In other words, it will succeed exactly once. This is because Prolog can recognize by loooking at the two clauses that they are mutually exclusive. In other words, for any non-empty list the second clause only can apply, and for an empty list the first clause only can apply.

In other words, for a proper list of length Len, after Len calls of the second clause, a call of the first clause will follow. At that point it succeeds, and all recursive calls (which were tail recursive) will succeed, in reverse order of how they were called.

In your example, before the recursive call is even made, a value is calculated and ready to be used when the call succeeds.

One thing here is that when you call with it a second argument a variable, you will keep on unifying this variable with a head of a list (the number you calculated) and a free tail [H1|T1], which you pass to the recursive call addone(T, T1). Only when the first argument is the empty list, will the second argument also be unified with an empty list: addone([], []). Now, on the return from the recursive calls, the list of values (growing from behind) will be unified with the free tails [4|[]], [3|[4|[]]] [2|[3|[4|[]]]], eventually building the final list in the second argument.

PROLOG: addOne predicate, what happens when temp. variable hits the base clause, how does Prolog call values?

1 Answers