Returning a value after a recursion in Prolog

prolog logic

25,224

Solution 1

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.

Solution 2

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).

25,224

Author by

petr

Updated on February 03, 2020

Comments

petr about 4 years
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?
petr over 14 years

I believe that my problem is a little bit different. Look at my sample: I ask Prolog test(A, B, 0). Prolog goes though predicates and counts N1 until N1 is > 2. When this happen predicate calls recursively test(A, final, N). So at this step A is 3, N is 3 and B is final. nonvar(B) succeeds, B = final succeeds so true is called. At this step Prolog stars backtracking and in the end returns true. But I asked about A and B, not true. I need the value A returned by Prolog.
petr over 14 years

I don't know how to force the predicate to terminate at the point where value A is assigned. I tried cuts but no success.
petr over 14 years

I need to return a value of variable A which is 3 when true is called. How do I achieve that? Your code above doesn't do that. Thanks, Petr
Diego Barbaresco over 14 years

How about like this then? (I'll make this code work in 2h time when I'm back home)
Diego Barbaresco over 14 years

The code above seems to run fine, I just tried it. Can you give me an example of a sample input/output?
petr over 14 years

It looks that your solution works. I have to go now so I'll test it tomorrow. But I'm confused. Why does Prolog returns true when there is only a single A and why does it return the value when there are two As in the first predicate?
petr over 14 years

It just seems to me that the variable Result is redundant.
Diego Barbaresco about 14 years

It's not redundant. It basically only gets unified/assigned when you get to the end of the recursion so you can retrieve its value at the top level call.
Charles Stewart about 14 years

Vincent is right. For a less noisy debug, try test(A, B, N):- write(triple(A,B,N)), N1 is N + 1, test(N1, B, N1). as the last clause.