Prolog:检查简单事实的传递性 [英] Prolog: check transitivity for simple facts

问题描述

我的目的是在 Prolog 中实现一个简单的传递性示例(仅针对我自己).

这些是我的事实:

trust_direct(p1, p2).trust_direct(p1, p3).trust_direct(p2, p4).trust_direct(p2, p5).trust_direct(p5, p6).trust_direct(p6, p7).trust_direct(p7, p8).trust_direct(p100, p200).

我写这个谓词是为了检查 A 是否信任 C，只要有一个 B 信任 C 和 A 信任这个 B:

trusts(A, B) :-trust_direct(A, B).信托(A，C):-信托(A，B)，信托(B，C).

谓词为 trusts(p1, p2) 或 trusts(p1, p5) 返回 true，但 trusts(p5, p6) 已经返回ERROR: Out of local stack.

Prolog 会这么快地淹没堆栈吗?

或者我对 trusts 的想法/实现是否糟糕/浪费系统内存?

解决方案

是的，Prolog 正在以如此快的速度淹没本地堆栈.

要看到这一点，只考虑以下程序片段就足够了:

<预>信托(A，C):-信托(A，B)，假，信任(B，C).

这称为 failure-slice:我插入了false/0，这样false/0之后的所有内容都可以被忽略.我用 strikeout 文本表示可以忽略的部分.

这意味着该代码段实际上等同于:

<预>信托(A，C):-信托(A，B)，错误的.

现在，使用上述任一片段，我们立即得到:

<预>?- 信任(p5，p6).错误:超出本地堆栈

要解决这个问题，您必须更改剩余的片段.出于这个原因，这样的片段可以作为问题的解释.

例如，考虑以下版本:

<预>信托(A，B):-trust_direct(A, B).信托(A，C):-trust_direct(A, B),信托(B，C).

示例查询:

<预>?- 信任(p5，p6).真;错误的.

这现在按预期工作.它在声明上等同于您发布的版本，并且具有更好的终止属性:

<预>?- 信任(X，Y)，假.错误.

这表明该程序现在普遍终止.

替代解决方案是:

• 使用 Prolog 系统的表格设施
• 使用传递闭包的定义立>
• 等

My intention was to implement a simple example (just for myself) of transitivity in Prolog.

These are my facts:

trust_direct(p1, p2).
trust_direct(p1, p3).
trust_direct(p2, p4).
trust_direct(p2, p5).
trust_direct(p5, p6).
trust_direct(p6, p7).
trust_direct(p7, p8).
trust_direct(p100, p200).

I've written this predicate to check whether A trusts C, which is true whenever there is a B that trusts C and A trusts this B:

trusts(A, B) :-
    trust_direct(A, B).

trusts(A, C) :-
    trusts(A, B),
    trusts(B, C).

The predicate returns true for trusts(p1, p2) or trusts(p1, p5) for example, but trusts(p5, p6) already returns ERROR: Out of local stack.

Is Prolog flooding the stack this quickly?

Or is my idea/implementation of trusts bad / wasting system memory?

解决方案

Yes, Prolog is flooding the local stack this quickly.

To see this, it suffices to only consider the following program fragment:

trusts(A, C) :-
        trusts(A, B),
        false,
        trusts(B, C).

This is called a failure-slice: I have inserted false/0, so that everything after false/0 can be ignored. I indicate parts that can be ignored with strikeout text.

This means that the snippet is actually equivalent to:

trusts(A, C) :-
        trusts(A, B),
        false.

Now, with either of the above snippets, we immediately get:

?- trusts(p5, p6).
ERROR: Out of local stack

To get rid of this problem, you have to change the remaining fragment. For this reason, such a fragment serves as an explanation of the problem.

For example, consider the following version:

trusts(A, B) :-
        trust_direct(A, B).
trusts(A, C) :-
        trust_direct(A, B),
        trusts(B, C).

Sample query:

?- trusts(p5, p6).
true ;
false.

This now works as expected. It is declaratively equivalent to the version you posted, and has much better termination properties:

?- trusts(X, Y), false.
false.

This shows that the program now terminates universally.

Alternative solutions are:

• use your Prolog system's tabling facilities
• use the definition of transitive closure
• etc.

这篇关于Prolog:检查简单事实的传递性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！