0

我最近一直在做一些Prolog。我读过序言的艺术这本书。他们在那里有一个 Nim 游戏实现。所以我将它重写为 SWI-Prolog，除了这个 Out of local stack 错误之外，一切似乎都很好。调试后我发现它似乎在程序的这一部分永远循环：

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

有人遇到过这种问题吗？对一些替代实施有什么建议吗？

4

1 回答 1

2

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

这里似乎nim_sum/3的两个子句应该颠倒（将“事实”子句放在第一位，这是终止条件）。然后nim_sum/3在具有主体的子句中对其自身进行的调用将在没有打开任何回溯点的情况下进行（假设binary/2和nim_add/3是确定性的）。

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

补充： 在进一步考虑nim_add/3之后，我怀疑 Prolog 引擎可能不会检测到它是确定性的，即仅以一种方式成功。这是一份工作！操作员。最简单的解决方案是在nim_sum/3调用自身的前面添加一个剪切，这样在进行递归调用时绝对没有打开的回溯点。然而，这更符合 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 的列表，首先是最低有效位。

于 2011-02-11T13:58:42.867 回答