Prolog Nim游戏-本地堆栈错误

Question

我最近做了一些开场白。我还读过“序的艺术”这本书。他们在那里有一个Nim游戏实现。因此，我将其重写为SWI-Prolog，除了这个本地堆栈错误之外，一切似乎都很好。经过调试，我发现它似乎在程序的这一部分永远循环：

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

有没有人遇到过这样的问题？有什么替代实现的建议吗？

Answer 1

为了避免“栈外”问题，通常需要以“最后调用优化”或“尾递归”的形式编写递归谓词。

这里似乎应该颠倒nim_/3事实的两个子句(将"fact“子句放在前面，这是终止条件)。然后，在具有主体的子句中对nim_sum/3进行的调用将不会打开任何回溯点(假设binary/2和nim_add/3是确定性的)。

尝试将这两个子句替换为nim_sum，让我们知道它是如何工作的。

补充道：在进一步思考nim_add/3之后，我怀疑Prolog引擎可能不会检测到它是确定性的，即只以一种方式成功。这是一份适合裁员的工作！操作符。最简单的解决方案是在nim_sum/3调用自身的位置前面添加一个cut，这样在进行递归调用时肯定没有回溯打开的点。然而，这更多的是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).  

同样，这假设binary/2是确定性的，假设转换为整数(非负？)转换成0和1的列表，最低有效位在前。