Prolog - 红色切割和绿色切割之间的区别

Question

我开始学习 prolog，并想让整个剪辑更清晰。
我读过“绿色剪切不会改变程序的声明性含义，而红色剪切会”。但是，该程序的含义并不是真正纯粹的声明性(只是因为 prolog 实际上回溯了所有选项)。

这是一个例子:

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

据说这是绿切。但是如果我运行这个:

p(X), X =:= 3.

我会得到“真”而没有切割，而“假”有切割。
那么，我想念什么？

提前致谢。

Answer 1

剪辑在操作上非常简单，或者如果您愿意，也可以在程序上解释。然而，由于大多数关于逻辑编程和 Prolog 主题的文献都偏向于 Prolog 程序的声明性含义(有充分的理由)，因此难以解释这种削减。纠正这种情况的一种尝试是根据效果对剪辑进行“着色”。

这是我试图让一切变得不那么清晰的尝试。

切割的操作意义，

来自 SWI-Prolog's reference manual :“丢弃自输入出现切分的谓词以来创建的所有选择点。换句话说，提交切分出现的子句，并丢弃当前子句中切分左侧的目标创建的选择点。”

来自 "The Art of Prolog" by Sterling and Shapiro :“目标成功并 promise Prolog 做出的所有选择，因为父目标与发生剪切的子句的头部统一 [强调不是我的]。虽然这个定义是完整和精确的，但它的后果和含义并不总是直观清晰或明显。”

来自 "The Craft of Prolog" by 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 不允许我们这样做。 “颜色”是程序的预期含义(程序员的意图)和剪辑的操作(程序)效果的结果。

但实际上，试着买一本书并阅读关于削减的部分。甚至两本书。