Prolog Nim 游戏 - 超出本地堆栈错误
我最近一直在做一些Prolog。我读过《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).
有人遇到过这种问题吗？对于一些替代实施有什么建议吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
为了避免“堆栈外”问题，通常需要以“最后调用优化”或“尾递归”形式编写递归谓词。
这里似乎 nim_sum/3 的两个子句应该颠倒（将“fact”子句放在前面，这是终止条件）。然后，在具有主体的子句中对自身进行的调用 nim_sum/3 将在没有打开任何回溯点的情况下进行（假设 binary/2 和 nim_add/3 是确定性的）。
尝试将这两个子句替换为 nim_sum 并让我们知道它是如何工作的。
补充：进一步思考nim_add/3后，我怀疑Prolog引擎可能不会检测到它是确定性的，即仅以一种方式成功。这是一项需要削减的工作！操作员。最简单的解决方案是在 nim_sum/3 调用自身的前面添加一个剪切点，这样在进行递归调用时肯定不会有回溯点打开。然而，这更符合 Prolog 的“精神”：
同样，这假设 binary/2 是确定性的，大概将整数（非负？）转换为 0 和 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:
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.