永无止境的填充方法，返回答案但不退出的无限循环 [英] Never-ending fill method, infinite loop that returns answer but doesn't exit

问题描述

所以我正在编写一些序言，并且遇到了一个我不明白为什么会出现的问题.这个问题实际上发生在我的一些方法中，但希望我能通过这种方法的一些指导来解决它.

So I'm working on some prolog,and have been running into an issue that I don't understand why is appearing. The issue actually happens in a few of my methods, but hopefully I can figure it out with just some guidance in this method.

fill(3,a,L) -> L = [a,a,a]

这是我的代码

fill(0,x,[]).
fill(N,A,[A | As]) :-
  N1 is N-1,
  fill(N1,A,As).

推荐答案

第一个子句应该是:

fill(0, _, []).

您的代码留下了一个选择点(用于您的示例查询):当计数器达到零时，两个子句标题都与当前目标一致.只有尝试使用第二个子句，才能达到 N1 >= 0 的目标.这个目标将失败(因为此时 N1 是 -1).因此，第二条将无法提供替代解决方案.但是 Prolog 解释器在找到第一个解决方案时并不知道这一点.因此，提出了第一个解决方案，然后 Prolog 顶级解释器等待您的输入.键入返回通常意味着您不希望 Prolog 推理引擎回溯并寻找替代解决方案.如果您键入分号;"，您将要求其他解决方案.

Your code leaves a choice-point (for your sample query): when the counter reaches zero, both clause heads unify with the current goal. Only by trying to use the second clause, will the N1 >= 0 goal be reached. This goal will fail (as N1 is -1 at this point). Thus, the second clause will fail to provide an alternative solution. But the Prolog interpreter doesn't know that when it finds the first solution. Therefore, the first solution is presented and then the Prolog top-level interpreter waits for your input. Typing a return usually means that you don't want the Prolog inference engine to backtrack and look for alternative solutions. If you type a semi-colon instead, ";", you will be asking for alternative solutions.

您可以更改您的 fill/3 谓词以不留下选择点.一个快速的解决方案是在第一个子句中添加一个剪切！/0":

You can change your fill/3 predicate to not leave a choice-point. A quick solution is to add a cut, "!/0", to the first clause:

fill(0, _, []) :-
    !.
fill(N, A, [A| As]) :-
    N > 0,
    N1 is N - 1,
    fill(N1, A, As).

剪辑是一个令人讨厌的小混蛋，它总是正确的，但它的副作用是:丢弃选择点.

A cut is a nasty little bugger that's always true but that's used for its side-effect: throwing away choice-points.

上述快速解决方案的一个问题是，一般来说，删减会使您的代码的声明性降低并引入微妙的(而不是那么微妙的错误).在这种情况下，有一个明显更好的解决方案:只需交换两个子句的顺序:

One issue with the quick solution above is that cuts, in general, make your code less declarative and introduce subtle (and not so subtle bugs). In this case, there's an apparently better solution: simply swap the order of the two clauses:

fill(N, A, [A| As]) :-
    N > 0,
    N1 is N - 1,
    fill(N1, A, As).
fill(0, _, []).

只有当 N > 时才会尝试第二个子句.0第一个子句中的测试失败.但是请注意，并非所有 Prolog 顶级解释器都检测到查询没有(更多)解决方案.

The second clause will only be tried when the N > 0test in the first clause fails. However, be aware that not all Prolog top-level interpreters detect that a query have no (more) solutions.

但是这个解决方案也有它自己的问题，这取决于 Prolog 系统以及它如何索引或不索引子句.你能发现吗?我给你一个提示:空间复杂度.

But this solution also have its own problem, depending on the Prolog system and how it indexes, or not indexes, clauses. Can you spot it? I will give you a hint: space complexity.

这篇关于永无止境的填充方法，返回答案但不退出的无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！