知道何时使用cut in prolog

Question

我参加了一门课程,学习了一些序言.我无法弄清楚如何/何时使用削减.即使我得到了切割的一般概念,我也似乎无法正确使用它们.任何人都可以简单地解释一下,或者给出一个他们可以推荐的"削减"的好教程(那不是learnprolognow.org)吗？

Answer 1

TL; DR:不要.

剪切修剪Prolog的搜索树.也就是说,鉴于纯粹的Prolog程序没有削减和相同的程序削减,唯一的区别是削减计划可能花费更少的时间在没有结果的分支,因此更有效; 可能会有更少的答案; 它也可能会终止,而原始程序则不会.

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

红色削减

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

对于这样的红色削减的更有条理的用途,更好地利用once/1,(\+)/1或者(;)/2- IF-THEN-ELSE状( If -> Then ; Else )来代替.更好的是,尝试通过发布instantiation_errors 来防止此类构造违背意外使用.或使用iwhen/2会产生实例化错误或when/2(在SWI,YAP,SICStus中提供)延迟目标.

绿色削减

删除无用选择点(以及冗余答案)的削减称为绿色削减.但要注意:你不能把它们放入你的程序只需按下!有的#00ff00.大多数情况下,您需要一个干净的只读防护装置,以确保此切割无法进行#ff0000.还有一种简单的方法可以安全地删除一些剩余的选择点:call_semidet/1.以下是一些相关案例:

• 这个查询的SLD树是什么？

• Prolog附加切割操作符

• 继承算术总和的最佳绿色削减是什么？

• 在Prolog中实现"最后"

剪切不是提交

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

Answer 2

裁员承诺 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) 可以证明,切割在失败前丢弃替代品.

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

存在至少一个未知的X,使得事实(X)成功.

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

双重否定有变量的影响不获取绑定.这在进行元编程时非常有用,可以在不改变其"结构"的情况下获取子句.从操作的角度来看,很清楚(？)发生了什么,但程序确实失去了声明性属性.

另一个仅在基本解释器中有用的用途是指示系统执行最后一次调用优化,为递归调用添加前缀.然后系统可以避免分配通常所需的堆栈空间来跟踪备用点.一个虚拟的例子:

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

编辑一个教程:我发现William Clocksin的"Clause and Effect"包含了与剪辑有关的详细调查:第4章"选择和承诺",它完全致力于削减利弊.在底线,主要是...

Answer 3

在使用剪切之前,我要求我的谓词符合以下两个标准:

• 它没有削减就给出了正确的答案
• 如果条款重新排序,它会给出正确的答案

一旦我的谓词表现得那样,我有时会添加一个剪切来消除不必要的非确定性.

例如,用于测试数字是正数,负数还是零的谓词.

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

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

人们可以编写一个类似的谓词而不使用切割-> ;,但有些人不喜欢它看起来如何:

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