序言: avoid redundant choice points (non-determinism) with and without cut operator

Question

首先，我已经阅读了SO上所有其他有关在Prolog中使用削减的文章，并且肯定会看到与使用削减有关的问题。但是，对我来说仍然有些不确定，我想一劳永逸地解决这个问题。

在下面的简单示例中，我们递归遍历列表，并检查每个第二元素是否等于1。这样做时，递归过程可能会在以下基本情况之一中结束:空列表或仅包含一个元素的列表。

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T).

执行时:

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 99502 Lips)
   false.

?- time(base([3,1,3])).
   % 2 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 304044 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 122632 Lips)
   false.

在这种情况下，我总是在第二种基本情况下使用显式的cut运算符(即表示列表中剩余一个元素的那个)，如下所示，以消除冗余的选择点。

base([]).
base([_]) :- !.
base([_,H|T]) :- H =:= 1, base(T).

现在我们得到:

?- time(base([1])).
   % 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 49419 Lips)
   true.

?- time(base([3,1,3])).
   % 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 388500 Lips)
   true.

我知道此剪切的行为特定于规则的位置，可以认为是不良做法。

但是，继续进行下去，可以将案件重新定位为以下形式:

base([_,H|T]) :- H =:= 1, base(T).
base([_]).
base([]).

这也可以不使用剪切就消除多余的选择点，但是，当然，我们只是将选择点转移到具有偶数个数字的列表的查询中，如下所示:

?- time(base([3,1])).
% 2 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 99157 Lips)
true ;
% 2 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 96632 Lips)
false.

因此，这显然也不是解决方案。但是，我们可以按如下所示调整规则的顺序:

base([_,H|T]) :- H =:= 1, base(T), !.
base([_]).
base([]).

因为这实际上不会留下任何选择点。看一些查询:

?- time(base([3])).
% 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 157679 Lips)
true.

?- time(base([3,1])).
% 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 138447 Lips)
true.

?- time(base([3,1,3])).
% 3 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 393649 Lips)
true.

但是，再次，由于规则的顺序，这种切割的行为只能正确地起作用。如果有人将基本案例重新定位回原始形式，如下所示:

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T), !.

我们仍然会得到不需要的行为:

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 119546 Lips)
   false.

在这种情况下，我总是在第二种基本情况下使用单一剪切，因为我是唯一经历过代码的人，并且我已经习惯了。但是，在另一篇SO帖子的答案之一中，我被告知，不建议使用cut运算符，并且我应尽量避免使用它。

这使我想到了一个两方面的问题:

如果剪切(无论剪切规则所在的位置)，是否会更改行为而不是解决方案(如上述示例)，是否仍然被认为是不好的做法？

如果我想取消上面示例中的一个典型的冗余选择点，以便使谓词完全具有确定性，是否有其他建议的方法来实现此目的，而不是使用削减？

提前致谢!

Answer 1

总是尽量避免!/0。 !/0几乎总是会破坏程序的声明性语义。

可以通过模式匹配表示的所有内容都应该通过模式匹配来表示。在您的示例中:

每一秒([])。
every_second([_ | Ls]):-
every_second_(Ls)。

每一秒_([])。
every_second _([1 | Rest]):-every_second(Rest)。

就像在不纯的版本中一样，发布的示例没有任何选择要点:

？-every_second([1])。
真的。

？-every_second([3,1])。
真的。

？-every_second([3,1,3])。
真的。

还请注意，在此版本中，所有谓词都是完全纯净的，并且可以在所有方向使用。正如我们从逻辑关系中所期望的那样，该关系也适用于最一般的查询并生成答案:

？-every_second(Ls)。
Ls = []；
Ls = [_G774]；
Ls = [_G774，1];
Ls = [_G774，1，_G780];
Ls = [_G774，1，_G780，1]。

由于您使用的谓词不正确或非声明性谓词(!/0，(=:=)/2)，因此您发布的所有版本均无法做到这一点!

在推理列表时，几乎总是可以单独使用模式匹配来区分情况。如果无法做到这一点，请使用if_/3进行逻辑纯净，同时仍保持可接受的性能。