Prolog - 红色切割和绿色切割之间的区别 [英] Prolog - differences between red cut and green cut

问题描述

我开始学习 prolog，并且想让整个剪辑更清晰.我读过绿色剪切不会改变程序的声明性含义，而红色剪切会".但是，程序的含义并不是真正纯粹的声明性(仅从 prolog 实际上回溯所有选项这一事实).

I started learning prolog, and wanted to make the whole cuts thing clearer. I have read that "green cut doesnt change declarative meaning of the program, while red cut does". But, the meaning of the program isnt really pure declarative (just from the fact that prolog actually backtracks for all options).

这是一个例子:

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

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

it has been said that this is green cut. But if I run this:

p(X), X =:= 3.

没有剪辑我会得到真"，而有剪辑我会得到假".那么，我错过了什么?

I will get "true" without a cut, and "false" with a cut. so, what do I miss?

提前致谢.

推荐答案

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

The cut is very straight-forward to interpret operationally, or if you prefer, procedurally. However, since the majority of literature on the topics of logic programming and Prolog has a bias towards the declarative meaning of Prolog programs (for good reasons), difficulties in explaining the cut arise. One attempt to rectify this is by "coloring" cuts depending on their effects.

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

Here is my attempt to make everything even less clear.

cut的操作意义，

1. 来自 SWI-Prolog 的参考手册:放弃所有选择点自从输入出现切分的谓词后创建.换句话说，提交出现切分的子句，并丢弃当前子句中切分左侧的目标创建的选择点."

1. From SWI-Prolog's reference manual: "Discard all choice points created since entering the predicate in which the cut appears. In other words, commit to the clause in which the cut appears and discard choice points that have been created by goals to the left of the cut in the current clause."

来自 Sterling 和 Shapiro 的Prolog 的艺术":目标成功并将 Prolog 提交给所有选择，因为父目标与发生剪切的子句的头部统一 [强调不是我的].虽然这个定义是完整和精确的，但它的分支和含义并不总是直观清晰或明显."

From "The Art of Prolog" by Sterling and Shapiro: "The goal succeeds and commits Prolog to all the choices made since the parent goal was unified with the head of the clause the cut occurs in [emphasis not mine]. Although this definition is complete and precise, its ramifications and implications are not always intuitively clear or apparent."

来自 O'Keefe 的The Craft of Prolog":[The cut] prunes选择堆栈指向在词法上包含剪切的谓词被调用时所在的位置.另一种说法是 剪切成功并将 Prolog 提交给自调用父目标以来所做的所有选择 [再次强调，不是我的重点]"

From "The Craft of Prolog" by O'Keefe: "[The cut] prunes the stack of choice points back to where it was when the predicate which lexically contains the cut was called. Another way of saying this is that the cut succeeds and commits Prolog to all the choices made since the parent goal was called [again, emphasis not mine]"

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

I suggest you read the sections on the cut and its uses at least from the two books cited above. It will definitely help you understand what is actually going on.

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

One common discussion is on the difference between finding solutions vs. answers vs. proofs. We (users, programmers) usually want answers. The result of evaluating Prolog predicates are solutions. However, what Prolog is actually looking for are proofs.

以你为例.你有数据库p(1).p(2).p(3)..你现在想问 Prolog，是否有一个 p(X) 使得 X =:= 3,

To take your example. You have the database p(1). p(2). p(3).. You now want to ask Prolog, "Is there a p(X) such that X =:= 3,

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

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

You get a single solution, X = 3. You also get an answer to your question: yes, there is such a p(X), and X is 3, and there are clearly no more answers.

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

(Try the query ?- p(X), X =:= 2.. Does it behave identically to the original query?)

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

Your proof tree can be seen (in a fashion) by tracing the query:

?- 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 的下一个子句)开始搜索证明.最后一个可以被证明，你会得到一个解决方案和你的查询的答案.

Basically, each of the clauses of p/1 is tried in turn. The first two do not yield a proof, as the second subgoal of the conjunction fails. The search for a proof continues each time from the last choice point (the next clause of p/1). The last one can be proven, and you get a solution and an answer to your query.

现在你在 p/1 的第二个子句的正文中做了一个删减:p(1).p(2) :- !.p(3)..您告诉 Prolog(根据上面的定义 3)，当搜索证明到达 p/1 的第二个子句时，将其参数与 2 统一的那个，修剪堆栈选择指向调用 p/1 时的位置."当调用 p/1 时，没有选择点.所以，当 X =:= 3 失败时，证明的搜索就完成了，连词不能被证明，没有解，你也得不到答案.

Now you put a cut in the body of the second clause of p/1: p(1). p(2) :- !. p(3).. You tell Prolog (in terms of definition 3. from above), "when the search for a proof reaches the second clause of p/1, the one that unifies its argument with 2, prune the stack of choice points to where it was when p/1 was called." When p/1 was called, there were no choice points. So, when X =:= 3 fails, the search for a proof is complete, the conjunction cannot be proven, there are no solutions, and you get no answers.

(尝试查询 ?- p(X), X =:= 2..它是否与您没有剪辑时相同的查询相同?)

(Try the query ?- p(X), X =:= 2.. Is it identical to the same query when you did not have the cut?)

现在到 colors ....., 和一个证明.你没有得到你期望的答案.这个切口是红色.

Now to the colors..... In the context of the conjunction p(X), X =:= 3., this cut pruned away a solution, and a proof. You didn't get the answer you expected. This cut is red.

如果我们可以告诉 Prolog 我们的意思是绿色或红色(或绿色或灰色或红色或蓝色)的切割，那就太好了，但 Prolog 不允许我们这样做.颜色"是程序的预期含义(程序员的意图)和剪辑的操作(程序)效果的结果.

It would be nice if we could tell Prolog that we mean a cut to be either green or red (or green or grue or red or blue), but Prolog does not allow us to do that. The "color" is a consequence of the intended meaning of the program (the programmer's intention) and the operational (procedural) effects of the cut.

但是说真的，试着买一本书并阅读关于剪辑的部分.甚至两本书.

But really, try to get a book and read the section on cuts. Or even two books.

这篇关于Prolog - 红色切割和绿色切割之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！