logo标签列表

Prolog - 无限循环

prologfailure-slice
7

我希望检查元素是否在列表的中间。我搜索中间元素，然后检查它是否是列表的成员，但我得到了无限循环。

我的谓词：

remove_first([_,H1|T], [H1|T]).

remove_last([_],[]).
remove_last([H|T], [H|T2]) :- remove_last(T, T2).

remove_first_and_last([X],[X]).
remove_first_and_last(In, Out) :- 
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]).
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X).

member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

is_middle(X, In) :-
    middle(In, Out),
    member(X, Out), !.

当我调用is_middle(1,[2,1,3])时，结果为true。 但是当我调用is_middle(1,[2,2,3])时，则没有返回结果。解释器并没有中断处理。

你尝试测试每个谓词了吗？你应该这样做来缩小范围。当你调用 is_middle(1,[2,2,3]) 时，它会调用 middle([2,3,3], Out)。当你调用它时会发生什么？而 middle([2,3,3], Out) 将调用 remove_first_and_last([2,3,3], Out)，那么当你调用它时会发生什么？等等... - lurker
事实上，我必须纠正其他谓词。谢谢。 - user
通常使用 trace/0 很有用，例如 trace, is_middle(1, [2,2,3])，因为您可以通过它交互式地看到循环的弧线。 - Daniel Lyons
1
如果您的列表元素数量为偶数怎么办？您期望的结果是什么？例如，is_middle(3, [1,2,3,4])应该是真的吗？ - lurker
...并且is_middle(2, [1,2,3,4])也应该是真的吗？ - false
3个回答
9
在您的情况下，您有两个选择。要么浏览另一个答案中所见的大量跟踪文本，要么尝试先减少需要理解的内容。我更喜欢后者，因为我不喜欢阅读太多。
但是您面临的主要问题是这样的。您说：
当我调用 is_middle(1,[2,1,3]) 时，我得到 true。
是的，Prolog找到了一种解决方案，但它不是找到了一次，而是无限多次。只需按空格键或分号即可看到此操作：
?- is_middle(1,[2,1,3]).
   true
;  true
;  true
;  true
;  true
;  ... .

因此，你的第一个查询已经有问题了。最好的方法是将false添加到此查询中：

？- is_middle（1，[2,1,3]），false。
   循环。

现在，让我们尝试缩小查询的范围。我们可以将其缩小为：

？- is_middle（1，[1]），false。
   循环。

有了这个，我们现在可以查看你的程序。在任何其他操作之前，我会删除它。无论如何，它都放错了位置。

为了理解实际发生了什么，我将在其中插入false以缩小你的程序。通过这些额外的目标，可以消除很多不必要的细节。即使剩下的程序称为仍然与我们相关，如果它仍在循环。

remove_first_and_last([X],[X]).
remove_first_and_last(In, Out) :- false,
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]) :- false.
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X), false.
is_middle(X, In) :-
    middle(In, Out), false,
    member(X, Out).

与原始程序相比，这个程序更容易理解。要解决问题，您需要在剩余的代码片段中进行修复。我建议删除事实remove_first_and_last([X],[X])。 这个事实表明已经删除了某些内容，但是在这种情况下，没有任何东西被删除。

使用直接 的解决方案：

is_middle(E, Es) :-
   phrase(middle(E), Es).

middle(E) --> [E].
middle(E) --> [_], middle(E), [_].

这是最短的代码，但它存在一个微小的问题：它不能确定地计算出答案。您可以通过查看答案来了解这一点：
?- is_middle(1, [2,1,3]).
   true
;  false.

这个 ; false 表示 Prolog 无法确定地完成计算，也就是说留下了一些空间。你可能会想使用 cut，但请抵制这种诱惑！
如果您真的追求速度，选择最快的版本：
is_middle(X, Xs) :-
   Xs = [_|Cs],
   middle_el(Cs, Xs, X).

middle_el([], [X|_], X).
middle_el([_,_|Cs], [_|Xs], X) :-
   middle_el(Cs, Xs, X).
如果你想使用@DanielLyons的解释，即允许长度为偶数的列表具有两个中间元素，请看看采用上述语法定义是多么容易。只需添加以下两个规则：
middle(E) --> [E,_].
middle(E) --> [_,E].

或者，将所有四条规则合并成一条：

middle(E) --> [E] | [E,_] | [_,E] | [_], middle(E), [_].

对于最快的解决方案，情况会更加复杂...

is_middle_dl(X, Xs) :-
   Xs = [_|Cs],
   middle_el_dl(Cs, Xs, X).

middle_el_dl([], [X|_], X).
middle_el_dl([_|Cs], Xs, X) :-
   middle_el_dl2(Cs, Xs, X).

middle_el_dl2([], [A,B|_], X) :-
   ( X = A ; X = B ).
middle_el_dl2([_|Cs], [_|Xs], X) :-
   middle_el_dl(Cs, Xs, X).

要检查它，我使用：

?- length(Xs, N), N mod 2 =:= 0, is_middle_dl(X, Xs).
   Xs = [X,_A], N = 2
;  Xs = [_A,X], N = 2
;  Xs = [_A,X,_B,_C], N = 4
;  Xs = [_A,_B,X,_C], N = 4
;  Xs = [_A,_B,X,_C,_D,_E], N = 6
;  Xs = [_A,_B,_C,X,_D,_E], N = 6
;  Xs = [_A,_B,_C,X,_D,_E,_F,_G], N = 8
;  Xs = [_A,_B,_C,_D,X,_E,_F,_G], N = 8
;  Xs = [_A,_B,_C,_D,X,_E,_F,_G,_H,_I], N = 10
;  Xs = [_A,_B,_C,_D,_E,X,_F,_G,_H,_I], N = 10
;  ... .
@DanielLyons：那里的中间是什么？ - false
middle([1,2], [3,1,2,4])，和 is_middle(X, [3,1,2,4]) 应该将 X 统一为 1 然后是 2。 - Daniel Lyons
@DanielLyons：但是OP的问题中并没有要求这样做。 - false
@DanielLyons：无论如何，我已经添加了另外两个版本。 - false
1
虽然没有明确说明，但我从他使用 member/2 和他的辅助谓词返回单例列表而不是单个值推断出来。无论如何，对于你的代码来说这是一个微不足道的改变。 - Daniel Lyons
6

调试Prolog需要一些不同的技能，所以我们需要花费更多时间来了解。

首先，让我们注意到两个样本查询的有趣之处。第一个成功了，这是应该的；第二个应该失败，但却进入了循环。这个细节是一个线索：它表明我们正在尝试处理一个假设情况。这是在使用其他语言后使用Prolog时常见的错误。在Prolog中，通常只需要明确成功的情况，让失败通过失败的统一来发生即可。

调试Prolog的标准工具是trace/0。思路是，您激活跟踪模式，然后运行查询，如下所示：

?- trace,  is_middle(1,[2,2,3]).
< p > trace/0存在的问题在于理解它需要一些努力。每行都以下列四个动词之一开头：call（调用）、exit（退出）、redo（重做）或fail（失败）。然后有一个数字，表示调用的嵌套级别。call和redo告诉你正在进入一次计算；exit和fail告诉你一次计算正在停止，嵌套级别即将减少。Call/exit是正常情况，fail/redo是Prolog特殊之处，即非确定性。通常，无限循环看起来像是一些有意义的工作（或可能不是）的前缀，后面是不断重复输出来自trace的块。我们在此处看到了这种情况。前缀: 

Call: (8) is_middle(1, [2, 2, 3]) ? creep
Call: (9) middle([2, 2, 3], _G1194) ? creep
Call: (10) remove_first_and_last([2, 2, 3], _G1194) ? creep
Call: (11) remove_first([2, 2, 3], _G1194) ? creep
Exit: (11) remove_first([2, 2, 3], [2, 3]) ? creep
Call: (11) remove_last([2, 3], _G1197) ? creep
Call: (12) remove_last([3], _G1190) ? creep
Exit: (12) remove_last([3], []) ? creep
Exit: (11) remove_last([2, 3], [2]) ? creep
Exit: (10) remove_first_and_last([2, 2, 3], [2]) ? creep

重复块：

Call: (10) middle([2], _G1200) ? creep
Exit: (10) middle([2], [2]) ? creep
Exit: (9) middle([2, 2, 3], [2]) ? creep
Call: (9) member(1, [2]) ? creep
Call: (10) member(1, []) ? creep
Fail: (10) member(1, []) ? creep
Fail: (9) member(1, [2]) ? creep
Redo: (10) middle([2], _G1200) ? creep
Call: (11) remove_first_and_last([2], _G1200) ? creep
Exit: (11) remove_first_and_last([2], [2]) ? creep

现在你可以看到，通过这个查询，触发不良行为将变得更加容易：

[trace]  ?- is_middle(2,[3]).
   Call: (7) is_middle(2, [3]) ? creep
   Call: (8) middle([3], _G398) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (8) middle([3], _G398) ? creep
   Call: (9) remove_first_and_last([3], _G398) ? creep
   Exit: (9) remove_first_and_last([3], [3]) ? creep
   Call: (9) middle([3], _G401) ? creep
   Exit: (9) middle([3], [3]) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (9) middle([3], _G401) ? creep

现在可以清楚地看到问题与 middle/2、remove_first_and_last/2和 member/2相互作用有关。你对 member/2的定义恰好是标准定义，因此可能不应受到责备。有趣的是，你让 middle/2 调用了它自己和 remove_first_and_last/2。而且 middle/2 和 remove_first_and_last/2 都有一个相同的子句：m([X], [X])。
这种情况是无限递归的一个极好的生成器，因为 middle/2 在第二个子句中所做的第一件事情正是它在自己的第一个子句中尝试并失败的事情。因此，它会发现自己在第二个子句中以与先前失败调用自身时完全相同的状态进入了递归调用。
解决方案是查看 remove_first_and_last/2 并意识到你在那里的第一个子句实际上没有删除第一个和最后一个元素。移除 remove_first_and_last([X], [X]) 子句可修复代码：
[trace]  ?- is_middle(2,[3]).
   Call: (7) is_middle(2, [3]) ? creep
   Call: (8) middle([3], _G398) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (8) middle([3], _G398) ? creep
   Call: (9) remove_first_and_last([3], _G398) ? creep
   Call: (10) remove_first([3], _G398) ? creep
   Fail: (10) remove_first([3], _G398) ? creep
   Fail: (9) remove_first_and_last([3], _G398) ? creep
   Fail: (8) middle([3], _G398) ? creep
   Fail: (7) is_middle(2, [3]) ? creep
false.

你的这两个测试现在也都可以工作了：

?- is_middle(1,[2,1,3]).
true.

?- is_middle(1,[2,2,3]).
false.

我认为你在这里添加基本情况是出于责任感，但实际上，如果你有一个元素的列表，在任何情况下它都不应该与remove_first_and_last/2一起统一。 这与明确处理Prolog中的错误情况非常相似，这往往会干扰机器的工作。
现在，缺少的一件事是，你想如何处理偶数长度的列表？ 无论您是否更改，现在您所拥有的内容都不能处理偶数长度的列表。 偶数长度的列表没有中间元素; 这是您想要的吗？ 我怀疑不是，因为is_middle/2中出现了member/2。 is_middle/2的评论
你所拥有的东西可以重构如下：
is_middle(X, In) :- middle(In, [X]).

member/2 的使用并没有起到任何作用，因为 middle/2 永远不可能在其第二个参数中生成非单例列表。但是，如果它确实生成了长度为偶数的列表，那么这将是有利可图的。你甚至可以通过向 middle/2 添加第三个子句来使代码按照这种方式工作：

middle([X,Y], [X,Y]).

现在看看middle/2在处理偶数长度的列表时如何工作：
?- middle([2,1,3,4], X).
X = [1, 3] ;
false.

现在切割过程可能会让你陷入麻烦。例如，1和3都是is_middle/2：

?- is_middle(1, [2,1,3,4]).
true.

?- is_middle(3, [2,1,3,4]).
true.

不幸的是，如果您要求获取中间元素，您只会得到1：

?- is_middle(X, [2,1,3,4]).
X = 1.
3发生了什么？你的切割操作阻止了它的生成。我不确定为什么要进行切割操作。我认为你可能是为了控制无限递归而进行切割操作，但这并没有帮助到你，因此请将其删除。

随意添加切割操作进行调试通常不是一个好主意。使用Ulrich Neumerkel的失败片段（failure slice）方法是一个更好的选择（详见这篇论文或者搜索相关标签以获取更多信息）。

DCG奖励

你可以将remove_first_and_last/2重写为DCG规则：

remove_first_and_last --> remove_first, remove_last.

很酷，对吧？ :) 那是因为你在该规则中进行的输入/输出线程与DCG规则完全相同。
更改摘要
remove_first_and_last(In, Out) :- 
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]).
middle([X,Y], [X,Y]).
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X).
6
is_middle(Item,List) :-
    append(Left,[Item|Right],List),
    length(Left,X),
    length(Right,X).

复杂的解决方案往往是不好的解决方案，我的朋友。

?- is_middle(X,[1,2,3,4,5]).
X = 3 ;
false.

完全可逆谓词：

?- is_middle(3,L).
L = [3] ;
L = [_G13, 3, _G19] ;
L = [_G13, _G19, 3, _G25, _G28] ;
3
好的，即使价格相当昂贵也很不错。 - false
不错，但不能处理偶数长度的列表，这似乎是提问者意图的一部分。例如is_middle(1, [2,1,3,4])。 - Daniel Lyons
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接