Prolog recursion in sum of n natural numbers

Question

I am having trouble to understand how value of Z is constantly changing. The specific step has been indicated in the stack trace output.

Here is the code I am using for finding sum of N natural numbers -

sum1(1,1).
sum1(N, Sum) :-
   Next is N-1,
   sum1(Next, Z),
   Sum is Z + N.

Here is the stack trace -

?- sum1(3,_).
   Call: (8) sum1(3, _2668) ? creep
   Call: (9) _2860 is 3+ -1 ? creep
   Exit: (9) 2 is 3+ -1 ? creep
   Call: (9) sum1(2, _2862) ? creep
   Call: (10) _2866 is 2+ -1 ? creep
   Exit: (10) 1 is 2+ -1 ? creep
   Call: (10) sum1(1, _2868) ? creep
   Exit: (10) sum1(1, 1) ? creep
   Call: (10) _2872 is 1+2 ? creep
   Exit: (10) 3 is 1+2 ? creep
   Exit: (9) sum1(2, 3) ? creep **%How is Z assigned value 3 ?**
   Call: (9) _2668 is 3+3 ? creep
    Exit: (9) 6 is 3+3 ? EOF: exit

Thanks in advance!

Basically, variables are scoped to the call they are in. Any variables between calls are assigned new anonymous variables until they are unified with what is passed to them. This means that if you use Z in multiple locations, Z is uninstantiated, and say Z = A, a new anonymous variable _1234 is created, assigned to both A and all locations where Z is used. — G_V

Scott Hunter Scott Hunter · Accepted Answer · 2018-04-09T17:15:25

It is not "changing"; each proof of sum1 gets its own versions of N, Sum, Next and Z. This is why, in the stack trace, each gets a different generated name (i.e. _2860), so Prolog can tell them apart.

As to your specific question, 2 lines above the line you ask about, that particular Sum is _2872; so proving _2872 is 1+2 requires _2872 to be 3. And this Sum is matched to the previous call sum(1, _2868), where _2868 was that sum1's Z (as you can see from 2 lines above that).

Prolog recursion in sum of n natural numbers

1 Answers