Prolog：检查简单事实的传递性

Question

我的目的是在 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).

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

谓词 returns true 例如 trusts(p1, p2) 或 trusts(p1, p5)，但是 trusts(p5, p6) 已经 returns ERROR: Out of local stack。

Prolog 如此快速地填充堆栈吗？

或者我的 idea/implementation of trusts 坏/浪费系统内存？

Answer 1

是的，Prolog 正在这么快地淹没本地堆栈。

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

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

这叫做 failure-slice：我插入了 false/0，因此 false/0 之后的所有内容都可以忽略 。我用 ~~删除线~~ 文本表示可以忽略的部分。

这意味着代码片段实际上等同于：

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

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

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

要解决这个问题，您必须更改剩余的片段。因此，这样的片段作为问题的解释。

例如，考虑以下版本：

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

示例查询：

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

这现在可以正常工作了。它在声明上等同于您发布的版本，并且具有更好的终止属性：

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

这表明程序现在普遍终止。

替代解决方案是：

使用您的 Prolog 系统的制表设施
使用transitive closure
等等

Prolog：检查简单事实的传递性

Prolog: check transitivity for simple facts

prolog

predicate

failure-slice

transitive-closure

transitivity