Prolog - 红色切割和绿色切割之间的差异

Question

我开始学习prolog,并希望让整个切割更加清晰.我已经读到"绿色切割不会改变程序的声明性含义,而红切不会".但是,程序的意义并不是真正纯粹的声明(仅仅是因为prolog实际上是为所有选项回溯).

这是一个例子:

p(1).
p(2) :- !.
p(3).

据说这是绿色切割.但如果我运行这个:

p(X), X =:= 3.

我会在没有剪辑的情况下获得"真实",并且在剪切时获得"假".所以,我错过了什么？

提前致谢.

Answer 1

在操作上,或者如果您愿意,在程序上进行解释是非常简单的.然而,由于大多数关于逻辑程序设计和Prolog主题的文献偏向于Prolog程序的声明性含义(有充分理由),因此难以解释切割.一种纠正这种情况的尝试是根据其效果"着色"切割.

这是我试图让一切变得更加清晰.

切割的操作含义,

1. 从SWI-Prolog的参考手册:"放弃自进入剪切出现的谓词后创建的所有选择点.换句话说,提交剪切出现的子句并丢弃由左侧目标创建的选择点.现行条款中的削减."

2. 来自Sterling和Shapiro的 " Prolog的艺术":" 目标成功并且让Prolog做出所有选择,因为父母的目标与条款的头部统一,切割发生在 [强调不是我的].虽然这个定义是完整而准确,其后果和影响并不总是直观清晰或明显."

3. 来自O'Keefe的 " Prolog的工艺":"[切割]将选择点的堆栈修剪回到词汇中包含切割的谓词的位置.另一种说法是切割成功,承诺自从父母目标被召唤以来做出的所有选择 [再次强调不是我的]

我建议你至少从上面引用的两本书中阅读有关剪辑及其用途的章节.它肯定会帮助您了解实际情况.

一个常见的讨论是找到解决方案与答案与证据之间的区别.我们(用户,程序员)通常需要答案.评估Prolog谓词的结果是解决方案.然而,Prolog实际上正在寻找的是证明.

举个例子.你有数据库p(1). p(2). p(3)..你现在想问Prolog,"有p(X)这样的X =:= 3,

?- p(X), X =:= 3.
X = 3.

你得到一个解决方案,X = 3.你也得到了你的问题的答案:是的,有这样的p(X),X是3,并且显然没有更多的答案.

(尝试查询?- p(X), X =:= 2..它的行为与原始查询相同吗？)

通过跟踪查询可以看到您的证明树(以某种方式):

?- trace(p/1), trace(=:=).
%         p/1: [call,redo,exit,fail]
%         (=:=)/2: [call,redo,exit,fail]
true.

[debug]  ?- p(X), X =:= 3.
 T Call: (7) p(_G1004)
 T Exit: (7) p(1)
 T Call: (7) 1=:=3
 T Fail: (7) 1=:=3
 T Redo: (7) p(_G1004)
 T Exit: (7) p(2)
 T Call: (7) 2=:=3
 T Fail: (7) 2=:=3
 T Redo: (7) p(_G1004)
 T Exit: (7) p(3)
 T Call: (7) 3=:=3
 T Exit: (7) 3=:=3
X = 3.

基本上,每个条款p/1依次被审判.前两个不会产生证据,因为连接的第二个子目标失败了.每次从最后一个选择点(下一个子句p/1)开始搜索证明.最后一个可以证明,您可以获得解决方案和您的查询答案.

现在你在第二个条款的主体中插入p/1:p(1). p(2) :- !. p(3)..你告诉Prolog(从上面定义3.),当搜索证据到达第二个子句时p/1,将其参数与2统一,将选择点的堆栈修剪到p/1调用时的位置. " 当p/1被调用时,没有选择点.因此,当X =:= 3失败时,对证据的搜索已经完成,无法证明联合,没有解决方案,并且您没有得到答案.

(尝试查询?- p(X), X =:= 2..当你没有剪切时,它是否与同一个查询相同？)

现在到了颜色 .....在连接的背景下p(X), X =:= 3.,这个剪切修剪了解决方案,并证明了.你没有得到你期望的答案.这个切口是红色的.

如果我们能告诉Prolog我们的意思是切割为绿色或红色(或绿色或格子或红色或蓝色),那将是很好的,但Prolog不允许我们这样做."颜色"是程序的预期含义(程序员的意图)和剪切的操作(程序)效果的结果.

但实际上,请尝试获取一本书并阅读有关削减的部分.甚至两本书.