prolog - why this strange trace

Question

here is the prolog code (which i sort of follow).

len([],0).
len([_|T],N) :- len(T,X), N is X+1.

and here is the trace for it (im running linux, swi)

    [trace]  ?- len([d,f,w,c],X).
   Call: (7) len([d, f, w, c], _G314) ? 
   Call: (8) len([f, w, c], _L182) ? 
   Call: (9) len([w, c], _L201) ? 
   Call: (10) len([c], _L220) ? 
   Call: (11) len([], _L239) ? 
   Exit: (11) len([], 0) ? 
^  Call: (11) _L220 is 0+1 ? 
^  Exit: (11) 1 is 0+1 ? 
   Exit: (10) len([c], 1) ? 
^  Call: (10) _L201 is 1+1 ? 
^  Exit: (10) 2 is 1+1 ? 
   Exit: (9) len([w, c], 2) ? 
^  Call: (9) _L182 is 2+1 ? 
^  Exit: (9) 3 is 2+1 ? 
   Exit: (8) len([f, w, c], 3) ? 
^  Call: (8) _G314 is 3+1 ? 
^  Exit: (8) 4 is 3+1 ? 
   Exit: (7) len([d, f, w, c], 4) ? 
X = 4.

i know prolog runs down these 'trees' but im having trouble figuring out why the increment to the variable is only done when it is exiting - any explainations of the mechanics of this?

Many thanks!

Answer 1

The reason for this, is that N is X+1 is the last part to the predicate.

Think of it like this: to calculate N is X+1, we need to know the value of X, which is calculated by calling len(T,X). But the process of calculating X requires yet another call to len, all the way to the situation where you end up with an empty list.

It is at that point that the list length is known, namely 0. Thus that value is "returned". Only then 0 + 1 can calculated and "returned". And then 1 + 1. Etc.

Thinking of it another way, observe that for any two predicates a and b, a, b yields true iff both a and b are true. In Prolog, b will only be evaluated if it is known that a is true (otherwise there is no point in evaluating b, since the result is known to be false).

As a result, all additions are done after the recursive calls to len.