更好地理解序言 [英] Understanding prolog better

问题描述

我正在尝试了解 Prolog 及其使用的解析算法.我找到了这个例子:

讨厌(1, 2).讨厌(2, 3).讨厌(3, 4).嫉妒(A，B): - 嫉妒(A，C)，嫉妒(C，B).嫉妒(A，B): - 讨厌(A，B).

但是当我试图说 jealous(1,4) 然后它不断溢出并且永远不会产生真，这很奇怪，好像 1 讨厌 2 和 2 讨厌 3 并且 3 讨厌 4，然后1也应该讨厌4.

但是我尝试改变它，所以它是这样的:

讨厌(1, 2).讨厌(2, 3).讨厌(3, 4).嫉妒(A，B): - 讨厌(A，B).嫉妒(A，B): - 嫉妒(A，C)，嫉妒(C，B).

然后当我说 jealous(1,4) 时它起作用了.

解决方案

<块引用>

然后当我说 jealous(1,4)

时它起作用了

不，它没有.或者，嗯，有点.只需键入 SPACE 即可看到它再次循环.那么立即循环的 jealous(4,1) 怎么样?

要理解这一点，只需查看程序的一小部分即可:

<预>嫉妒(A，B):- 假，讨厌(A，B).嫉妒(A，B):-嫉妒(A，C)，假， 嫉妒(C，B).

注意变量 B 在可见部分从未使用过.所以它不会对终止产生任何影响.并注意刚刚交给第一个目标的 A.所以这两个参数在这个程序中都没有影响.因此该程序永不终止.它可能会在这里和那里找到解决方案，但当被要求找到所有解决方案时，它永远不会终止.

这个小片段被称为 failure-slice 如果它没有终止，那么你的整个程序也会终止！也就是说，根本不需要阅读你对hates/2的定义¹.

如果你想掌握 Prolog 的执行，你需要掌握失败切片的概念.因为，有经验的程序员或多或少是凭直觉做到这一点的.因此，他们不会阅读整个程序，他们只是扫描相关部分.Prolog 的好处在于，这样的切片与整个程序之间存在真正的因果关系.

要解决此问题，您需要更改故障切片突出显示的部分中的某些内容.这是一种可能的变化:

jealous(A,B) :- 讨厌(A,B).嫉妒(A，B): - 讨厌(A，C)，嫉妒(C，B).

但是一旦您在 hates/2 中有循环，这将不再有效.然后，考虑closure/3:

jealous(A, B) :-关闭(讨厌，A，B).

另一种方法是使用表格.但请注意，制表解决了这一问题，但在有约束的情况下将不再有效(您迟早会遇到这种情况).

---

^{1) 前提是你有一个纯单调的程序.}

I'm trying to understand Prolog and how the resolution algorithm it uses. I have this example that I found:

hates(1, 2).
hates(2, 3).
hates(3, 4).
jealous(A, B) :- jealous(A, C), jealous(C,B).
jealous(A,B) :- hates(A,B).

But when I try to say that jealous(1,4) then it keeps overflowing and never yields true, which is weird as if 1 hates 2 and 2 hates 3 and 3 hates 4, then 1 should also hate 4.

But but I tried change it so it was like this:

hates(1, 2).
hates(2, 3).
hates(3, 4).
jealous(A,B) :- hates(A,B).
jealous(A, B) :- jealous(A, C), jealous(C,B).

And then it works when I say jealous(1,4).

解决方案

And then it works when I say jealous(1,4)

No, it did not. Or, well, kind of. Just type SPACE to see that it loops again. And what about jealous(4,1) which loops immediately?

To understand this, it suffices to look at a very tiny part of your program, namely this one:

jealous(A,B) :- false, hates(A,B).
jealous(A, B) :- jealous(A, C), false, jealous(C,B).

Note the variable B which is never used in the visible part. So it cannot have any influence on termination. And note A which is just handed to the first goal. So both arguments have no influence in this program. Thus this program terminates never. It might find a solution here and there, but it will never terminate when asked to find all of them.

This tiny fragment is called a failure-slice and if it does not terminate so does your entire program! That is, there is no need to read your definition of hates/2 at all¹.

If you want to master Prolog's execution, you need to master that notion of a failure slice. For, experienced programmers do this more or less by intuition. Thus, they do not read the entire program, they just scan for relevant parts. The nice thing here in Prolog being that there is a truly causal relationship between such a slice and the entire program.

To solve this problem, you need to change something in the part that has been highlighted by the failure slice. Here is one such possible change:

jealous(A,B) :- hates(A,B).
jealous(A, B) :- hates(A, C), jealous(C,B).

But once you have cycles in hates/2, this no longer works. Then, consider closure/3:

jealous(A, B) :-
   closure(hates, A, B).

Another way is to use tabling. But be warned, tabling solves this one problem but will no longer work in the context of constraints (which sooner or later you will encounter).

---

^{1) provided you have a pure monotonic program as you do.}

这篇关于更好地理解序言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！