Can anyone please explain the steps prolog makes with this recursive program?

Question

I have recently started learning prolog, but I'm having a hard time with recursive rules. I understand the simple rules but I'm having trouble with this example I found of a program that gives the sum of all elements in a list:

addup([], 0).

addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   
    Total is FirstNumber + TotalOfRest.

Now if I trace this, I get the following:

[trace]  ?- addup([3, 5, 7], Total).
   Call: (7) addup([3, 5, 7], _G322)
   Call: (8) addup([5, 7], _L1)
   Call: (9) addup([7], _L2)
   Call: (10) addup([], _L3)
   Exit: (10) addup([], 0)    % I understand what it does till here
^  Call: (10) _L2 is 7+0
^  Exit: (10) 7 is 7+0
   Exit: (9) addup([7], 7)
^  Call: (9) _L1 is 5+7
^  Exit: (9) 12 is 5+7
   Exit: (8) addup([5, 7], 12)
^  Call: (8) _G322 is 3+12
^  Exit: (8) 15 is 3+12
   Exit: (7) addup([3, 5, 7], 15)
Total = 15.

I understand the first few steps; it keeps cutting the head of and making new TotalOfRest's untill the original list is empty and it matches with the first fact. That makes the third TotalOfRest (I called it _L3) equal to 0. But what now? How does prolog make the step that L2 is equal to 7 + 0. I understand that prolog starts backtracking, but what matches with what to reach that conclusion? Is Total now 7? Or are there three different Total's with different values's like with TotalOfRest? And is RestofList still equal to [] and FirstNumber still 7?

So basically: how does prolog go from having figured out L3 to the end conclusion?

I'm very new to this so if anyone could explain it for me really slowly, I would appreciate it so much!

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2017-09-14T11:33:09

Mind that your recursive call introduces a new variable:

addup([], 0).
addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   
    Total is FirstNumber + TotalOfRest.

At each recursion level, a new TotalOfRest variable is created. Mind that the TotalRest of the upper recursive level is not the same one as the ones that are deeper in the recursion.

The trace could be more convenient by using the name of the variable:

[trace]  ?- addup([3, 5, 7], Total).
   Call: (7) addup([3, 5, 7], _Total)
   Call: (8) addup([5, 7], _TotalOfRest1)
   Call: (9) addup([7], _TotalOfRest2)
   Call: (10) addup([], _TotalOfRest3)
   Exit: (10) addup([], 0)
^  Call: (10) _TotalOfRest2 is 7+0
^  Exit: (10) 7 is 7+0
   Exit: (9) addup([7], 7)
^  Call: (9) _TotalOfRest1 is 5+7
^  Exit: (9) 12 is 5+7
   Exit: (8) addup([5, 7], 12)
^  Call: (8) _Total is 3+12
^  Exit: (8) 15 is 3+12
   Exit: (7) addup([3, 5, 7], 15)
Total = 15.

So what happens is in case the recursive call is performed is that a new variable _TotalOfRest1 is created. The calls are done recursively until _TotalOfRest3. Now at that level _TotalOfRest3 = 0 is set to 0. But there are still commands in the recursion that needs to be resolved: the Total is FirstNumber + TotalOfRest.. Mind that all these Totals are local variables (this also holds for TotalOfRest and FirstNumber). So at every level this is resolved. Mind that a Total at recursion level two for instance is actually _TotalOfRest2 for the caller.

So the recursion looks like:

addup([3, 5, 7], Total) :-
    % FirstNumber = 3
    % RestOfList = [5, 7]
    % Total = Total
    addup([5,7], _TotalOfRest1) :-
         % FirstNumber = 5
         % RestOfList = [7]
         % Total = _TotalOfRest1
         addup([7], _TotalOfRest2) :-
             % FirstNumber = 7
             % RestOfList = []
             % Total = _TotalOfRest2
             addup([],_TotalOfRest3),
             % resolved to _TotalOfRest3 = 0
             Total is 7 + 0.
             % resolved to Total = 7
         % resolved to _TotalOfRest2 = 7
         Total is 5 + 7.
         % resolved to Total = 12
     % resolved to _TotalOfRest1 = 12
     Total is 3 + 12.
     % resolved to Total = 15
% resolved tot Total = 15

The code parts are written in boldface and you see that at every level there are local variables that are grounded and communicated back to the outer scope.

Can anyone please explain the steps prolog makes with this recursive program?

1 Answers