无休止的填充方法，返回答案但不退出的无限循环 [英] 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 test失败时，才会尝试第二个子句.但是，请注意，并非所有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屋！