5

I am starting Prolog, courtesy of Seven Languages in Seven Weeks, and struggling a bit with understanding how Prolog is handling recursion.

Given the following code:

sum(0, []). sum(Total, [Head|Tail]) :- sum(Sum,Tail), Total is Head + Sum. % executed in the Prolog interpreter: sum(X, [1,2,3]) X = 6

I understand what this code is doing, but I am a little hung up on how the Prolog is resolving the recursive calls of sum. Mainly, it is strange to me that there is no explicit "return" within sum.

My understanding is that something like this happens:

A. The interpreter attempts to unify the rule sum(X, [1,2,3]) by calling sum:

0 Sum(X, [1, 2, 3]) 1 Sum(Y, [2,3] 2 Sum(Z, [3]) 3 Sum(0, []) % our recursive base

B. Once we hit the base fact, it climbs back up the recursive "stack":

3 Sum(0, []), Total = 0 % we start at our base fact 2 Sum(1, [3]), Total = 3 1 Sum(2, [2, 3]), Total = 5 0 Sum(X, [1, 2, 3]) Total = 6 % sweet, sweet unification

Is my understanding of how this is functioning correct? Or is there a better way for my imperative mind to think about/express what is going on above?

Improve this question
2
  • 1
    Also.. Try running the 'trace.' predicate, before your main predicate, press enter to step through, and you can see it hitting the bottom of the recursion [], then unfold itself back out. Commented May 26, 2014 at 6:21
  • The fact that the predicate's recursive calls have to be "unwound" to obtain the total is significant. A more efficient implementation can be done by introducing an "auxiliary argument" for the total, putting the recursive calls into tail-recursive "last call" form, and it is a common optimization in Prolog implementations that avoids any "unwinding" of the stack in such cases. Commented May 26, 2014 at 21:42

3 Answers 3

Reset to default
4

Yup, your thinking is correct. I'll reword slightly what you said just so that it's maybe a bit clearer.

The first thing to do to understand Prolog execution is to realize that Prolog is like a weak theorem prover. It will try to make your queries true. So, when you enter the query ?- sum(X, [1,2,3])., Prolog will do its best to make it true. In that case, as we'll see, it will require binding X to 6, let's see how.

The only elements you gave Prolog to prove that sum(X, [1, 2, 3]) is true are

sum(0, []).

and

sum(Total, [Head|Tail]) :- sum(Sum,Tail), Total is Head + Sum.

Obvisouly, Prolog can't do anything with the first clause, because it can't unify [] and [1, 2, 3]. So it tries to prove your query by using the second clause.

Then what happens is that it tries to prove sum(Sum,Tail) and Total is Head + Sum sequentially. Proving the first of those two options will induce the recursive call and ultimately it will be called with Tail = []. At this point, Prolog will use the first clause you gave it and will deduce that Sum is therefore 0. It will now have the elements to prove the second part (Total is Head + Sum) at the last step of the recursion. Then the recursion is worked back up to the initial predicate as you guessed.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

This is correct. The role of an explicit "return" is played by the unique way of satisfying the sum of an empty list in the predicates that define sum/2.

You may convince yourself of this by executing the goal sum(X,[ ]) at the interpreter.

Improve this answer

Comments

1

Your understanding of how Prolog handles recursion is absolutely correct! You've accurately traced the steps of the recursive calls and how unification works to find the solution. Let me make you clear with a few key points:

  1. The interpreter starts by trying to unify the goal sum(X, [1,2,3]) with the head of a rule. In this case, it matches the second rule sum(Total, [Head|Tail]).

  2. Unification requires matching the second argument ([1,2,3]) with [Head|Tail]. This succeeds by binding Head to 1 and Tail to [2,3]. Now, the interpreter needs to satisfy the subgoals in the body of the rule:

    • sum(Sum, Tail): This calls the sum predicate again with Sum and Tail.This creates a new recursive call.
    • Total is Head + Sum:This part is evaluated after the recursive call returns.

  3. The interpreter continues recursively until it reaches the base case sum(0, []). This fact succeeds immediately, unifying Sum with 0.

  4. Now, backtracking starts. The interpreter substitutes 0 for Sum in the second subgoal (Total is Head + Sum). This becomes Total is 1 + 0, which unifies Total with 1.

  5. The process continues back up the recursive calls. At each step, the bindings for Sum and Total are updated based on the previous call. Finally, the original goal sum(X, [1,2,3]) is unified with X = 6.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.