44

我参加了一门课程，其中我学到了一些序言。我不知道如何/何时使用削减。即使我了解削减的一般概念，但我似乎无法正确使用它们。任何人都可以简要解释一下，或者就他们可以推荐的“削减”提供一个很好的教程（不是 learnprolognow.org）吗？

4

5 回答 5

26

TL; DR：不要。

剪切修剪 Prolog 的搜索树。也就是说，给定一个没有切割的纯 Prolog 程序和有切割的相同程序，唯一的区别是有切割的程序可能在无结果的分支上花费的时间更少，因此效率更高；可能有更少的答案；它也可能会终止，而原始程序不会。

听起来很无害……甚至有用，不是吗？嗯，大多数时候事情都比较复杂。

红色切割

剪辑的使用方式常常使得没有剪辑的程序根本没有任何有意义的意义。这种切割称为红色切割。在更好的情况下，它用于实现非单调否定的粗略形式。而在其他一些情况下，它一半是否定，一半是非常难以理解的程序意义。不仅适用于程序的读者，也适用于其作者。事实上，这样的使用往往在无意中缺乏坚定性。无论如何：这些削减不会放入现有程序中。他们应该从一开始就参与该计划。

对于此类红色切割的更结构化用途，最好使用once/1,(\+)/1或(;)/2– if-then-else like( If -> Then ; Else )代替。更好的是，尝试通过发出instantiation_errors 来防止此类构造被意外使用。或使用iwhen/2会产生实例化错误或when/2（在 SWI、YAP、SICStus 中提供）会延迟目标。

绿色削减

删除无用选择点（以及冗余答案）的切割称为绿色切割。但请注意：您不能简单地将它们放入您的程序中!，然后按一些#00ff00. 大多数情况下，您需要一个干净的只读保护程序，以确保不会出现这种情况#ff0000。还有一种简单的方法可以安全地删除一些剩余的选择点：call_semidet/1. 以下是一些相关案例：

剪切不是提交

最后，让我指出 cut 不是提交操作符。它有时有点像它，但需要很多限制才能成为一个。提交运算符不能（ab）用于实现(\+)/1. 提交要求每个子句彼此独立地尝试。因此，每个子句都需要一个完整的保护；它不能依赖于仅在先尝试了其他一些条款之后才进行尝试。此外，必须在谓词的每个子句中发生提交。切割可以发生在任何地方。

于 2013-01-28T05:34:41.437 回答
14

削减承诺将 Prolog 目标证明为已完成的选择。

当程序员知道不能尝试任何可用的替代方案时，必须使用它。

最突出的用途是通过失败实现否定。

fact(a).
fact(b).

/* 1 */ neg(X) :- call(X), !, fail.
/* 2 */ neg(_).

在这里，我（重新）定义了标准的否定运算符，通常是 ( \+ )/1

?- neg(fact(c)).
true.

call(fact(c))无法证明规则 1，则替代规则 2 成功。

?- neg(fact(a)).
false.

因为fact(a) 可以证明，cut 在失败之前放弃了替代方案。

?- neg(fact(X)).
false.

至少存在一个未知的 X 使得 fact(X) 成功。

?- neg(neg(fact(X))).
true.

双重否定的效果是变量不受约束。这在进行元编程时很有用，可以在不改变其“结构”的情况下获取子句。从操作的角度来看，很清楚（？）发生了什么，但程序确实失去了它的声明性属性。

另一个只在初级解释器中有用的用途是指示系统执行最后一次调用优化，在递归调用前面加上一个cut。然后系统可以避免分配通常需要跟踪替代点的堆栈空间。一个虚拟的例子：

print_list([E|Es]) :- print_element(E), !, print_list(Es).
print_list([]).

关于教程的编辑：我发现 William Clocksin 的“Clause and Effect”包含与 cut 相关的详细调查：第 4 章“Choice and Commitment”完全致力于 cut 的利弊。归根结底，主要是缺点...

于 2013-01-27T00:53:47.933 回答
14

在使用切割之前，我要求我的谓词满足以下两个条件：

  • 它给出了正确的答案，没有删减
  • 如果重新排序子句，它会给出正确的答案

一旦我的谓词表现得那样，我有时会添加一个剪切来修剪不需要的不确定性。

例如，用于测试数字是正数、负数还是零的谓词。

sign(N, positive) :-
    N > 0.
sign(N, negative) :-
    N < 0.
sign(N, zero) :-
    N =:= 0.

每个条款完全独立于其他条款。我可以对这些子句重新排序或删除一个子句，而其余子句仍然给出预期的答案。positive在这种情况下，我可能会在and子句的末尾删减，negative只是为了告诉 Prolog 系统它不会通过检查其他子句来找到更多解决方案。

可以使用 using 编写类似的谓词而不使用 cut -> ;，但有些人不喜欢它的外观：

sign(N, Sign) :-
    (   N > 0 -> Sign=positive
    ;   N < 0 -> Sign=negative
    ;            Sign=zero
    ).
于 2013-01-28T16:16:49.597 回答
1

剪切谓词可防止回溯。剪切谓词被指定为感叹号 (!)。Cut 修剪搜索树并通过 prolog 解释器缩短路径轨迹。从语义上讲，它总是成功的。

read(a).
read(b).
color(p, red) :- red(p).
color(p,black) :- black(p),!.
color(p,unknown).

?-color(X,Y).
  X = a,
  Y = red;
  X = b,
  Y = black;

如果没有切入，则在 Y=black 之后，Y=unknown 会显示 Y=unknown。

有两种类型的切割谓词：

绿切：绿切是一种对陈述意义没有影响的切分。它仅用于提高效率并避免不必要的计算。从程序中删除绿色剪辑不会改变程序的含义。

红切：红切是对陈述意义有影响的一种。从程序中删除红色剪切改变了程序的含义。

于 2018-07-14T04:16:12.183 回答
1

once找到谓词后，所有内容都从我的代码中消失了。在内部它的行为就像

once(X) :- X, !.

我发现它对于在我做某事之前就如何做某事做出坚定的决定非常有用。

例如，这是我的标准元解释器。该maybe1/1子句在其参数中具有独特的函子，因此一旦它们知道，就maybe1/1可以完美地选择正确的。

找到该独特功能的工作交给了maybe0/2预处理器，该预处理器设置Y了关于X.

如果没有once，这将不得不充满削减。例如maybe1，有三/两种不同的解释X/Y，or我们需要以自上而下的方式检查。但检查一下 - 没有削减。

maybe(X) :- 
    once(maybe0(X,Y)), maybe1(Y).

maybe0(true,       true).
maybe0((X,Y),      (X,Y)).
maybe0((X;Y),      or(L))          :- o2l((X;Y),L).
maybe0(X,          calls(X))       :- calls(X).
maybe0(X/Y,        fact(X/Y))      :- clause(X/_, true).
maybe0(X/Y,        rule(X/Y))      :- clause(X/_,_).
maybe0(X/Y,        abducible(X/Y)).
maybe0(or([H|T]),  or([H|T])).
maybe0(or([]),     true).

maybe1(true).
maybe1((X,Y))        :- maybe(X),maybe(Y).
maybe1((X;Y))        :- maybe(X);maybe(Y).
maybe1(abducible(X)) :- assume(X,0).
maybe1(fact(X))      :- assume(X,1), one(X).
maybe1(rule(X))      :- assume(X,2), one(clause(X,Y)), maybe(Y).
maybe1(calls(X))     :- one(clause(X,Y)), maybe(Y).
maybe1(or([H|T]))    :- any(One,Rest,[H|T]), ignore(maybe(One)), maybe(or(Rest)).
于 2017-10-27T21:53:27.570 回答