Returning a value after a recursion in Prolog

Question

Hello, I decided to study some logic programming and I stumbled across a problem. It is programmed in SWI Prolog.

test(A, B, N):-
 nonvar(B),
 B = final,
 true.

test(A, B, N):-
 N > 2,
 test(A, final, N).

test(A, B, N):-
 N1 is N + 1,
 test(N1, B, N1).

It is just a sample with no real use except it is driving me crazy.

The problem is that when the code reaches true then it starts tracking back and answers "true". But I need to "return" value A. How do I do that?

Answer 1

I don't have my prolog compiler here but have you tried something along the lines of:

test(A, B, N, A):-
 nonvar(B),
 B = final,
 true.

test(A, B, N, Result):-
 N > 2,
 test(A, final, N, Result).

test(A, B, N, Result):-
 N1 is N + 1,
 test(N1, B, N1, Result).

Answer 2

A is not being Unified with anything in the body of your rules. The way prolog works is via unification of terms. You cannot "return" A as in procedural languages as such. For instance, what do you want the value of A to be when the recursion comes to an end? I have no idea what your code is doing so let me use an example of my own.

  accumulate([], A, A).
  accumulate([H|T], A, N) :- A1 is A + H, accumulate(T, A1, N).

  sum([], 0).
  sum(L, N) :- accumulate(L,0,N).

Here is a sum procedure that will sum the values in a list and "return N", the sum of the values in the list. To call this procedure you can do this:

  sum([2, 3, 4], N).

And Prolog will respond:

  N = 9

Notice the accumulate procedure is using A as an accumulator as the recursion goes on. That is, A keeps the running sum, while N is the final answer it returns. During the recursion N is not unified with any real value.

In the final step of the recursion, that is, when the list is empty, the value of A is unified with N, in effect returning N.

---

Let us do a Trace.

 [trace] 4 ?- test(A, B, 0).
   Call: (7) test(_G417, _G418, 0) ? creep//A unifies with _G417 (internal variable name), B with _G418 and N with 0.
   Call: (8) nonvar(_G418) ? creep
   Fail: (8) nonvar(_G418) ? creep
   Redo: (7) test(_G417, _G418, 0) ? creep//Unifies with clause 2, 
^  Call: (8) 0>2 ? creep
^  Fail: (8) 0>2 ? creep
   Redo: (7) test(_G417, _G418, 0) ? creep //Unifies with clause 3
^  Call: (8) _L183 is 0+1 ? creep
^  Exit: (8) 1 is 0+1 ? creep
   Call: (8) test(1, _G418, 1) ? creep //recursive call, unifies with 
   Call: (9) nonvar(_G418) ? creep
   Fail: (9) nonvar(_G418) ? creep
   Redo: (8) test(1, _G418, 1) ? creep
^  Call: (9) 1>2 ? creep
^  Fail: (9) 1>2 ? creep
   Redo: (8) test(1, _G418, 1) ? creep
^  Call: (9) _L195 is 1+1 ? creep
^  Exit: (9) 2 is 1+1 ? creep
   Call: (9) test(2, _G418, 2) ? creep
   Call: (10) nonvar(_G418) ? creep
   Fail: (10) nonvar(_G418) ? creep
   Redo: (9) test(2, _G418, 2) ? creep
^  Call: (10) 2>2 ? creep
^  Fail: (10) 2>2 ? creep
   Redo: (9) test(2, _G418, 2) ? creep
^  Call: (10) _L207 is 2+1 ? creep
^  Exit: (10) 3 is 2+1 ? creep
   Call: (10) test(3, _G418, 3) ? creep
   Call: (11) nonvar(_G418) ? creep
   Fail: (11) nonvar(_G418) ? creep
   Redo: (10) test(3, _G418, 3) ? creep
^  Call: (11) 3>2 ? creep
^  Exit: (11) 3>2 ? creep
   Call: (11) test(3, final, 3) ? creep
   Call: (12) nonvar(final) ? creep
   Exit: (12) nonvar(final) ? creep
   Call: (12) final=final ? creep
   Exit: (12) final=final ? creep
   Call: (12) true ? creep
   Exit: (12) true ? creep
   Exit: (11) test(3, final, 3) ? creep
   Exit: (10) test(3, _G418, 3) ? creep
   Exit: (9) test(2, _G418, 2) ? creep
   Exit: (8) test(1, _G418, 1) ? creep
   Exit: (7) test(_G417, _G418, 0) ? creep

Now, notice the point in the trace where I marked //A unifies with _G417 (internal variable name), B with _G418 and N with 0.. At that point A is your external variable and _G417 is your internal A. If this call succeeds which it ultimately does prolog will only report the external variable values. Internally _G417 is never unified with anything else. I think the problem is one of understanding how the unification model of Prolog works.