Prolog Nim Game - Out of local stack error

Question

I've been doing some Prolog lately. And I've read The Art Of Prolog book. They have a Nim game implementation there. So I've rewritten it to SWI-Prolog and everything seems fine except this Out of local stack error. After debugging I've found out that it seems to loop forever in this part of the program:

nim_sum([N|Ns],Bs,Sum):-
      binary(N,Ds), nim_add(Ds,Bs,Bs1), nim_sum(Ns,Bs1,Sum).
nim_sum([],Sum,Sum).

nim_add(Bs,[],Bs).
nim_add([],Bs,Bs).
nim_add([B|Bs],[C|Cs],[D|Ds]):-
    D is (B+C) mod 2, nim_add(Bs,Cs,Ds).

Did anybody run into this kind of problem? Any suggestions for some alternative implementation?

Answer 1

To avoid "out of stack" problems it is often necessary to write the recursive predicates in a "last call optimization" or "tail recursive" form.

Here it seems the two clauses for nim_sum/3 should be reversed (putting the "fact" clause first, which is the termination condition). Then the call nim_sum/3 makes to itself in the clause that has a body will be made without any backtrack points open (assuming binary/2 and nim_add/3 are deterministic).

Try swapping those two clauses for nim_sum and let us know how it works.

Added: After thinking further about nim_add/3, I'm suspecting that the Prolog engine will probably not detect that it is deterministic, i.e. succeeds in only one way. This is a job for the cut ! operator. The simplest solution is to add one cut right in front of where nim_sum/3 calls itself, so that there are definitely no backtrack points open at the time the recursive call is made. However this is more "in the spirit" of Prolog:

nim_sum([],Sum,Sum).  
nim_sum([N|Ns],Bs,Sum):-  
    binary(N,Ds),  
    nim_add(Ds,Bs,Bs1),  
    nim_sum(Ns,Bs1,Sum).  

nim_add(Bs,[],Bs) :- !.  
nim_add([],Bs,Bs) :- !.  
nim_add([B|Bs],[C|Cs],[D|Ds]):-  
    D is (B+C) mod 2,  
    nim_add(Bs,Cs,Ds).  

Again this assumes binary/2 is deterministic, presumably converting an integer (nonnegative?) into a list of 0's and 1's, least significant bits first.