prolog - 一棵无限成功的树，或不是？

Question

我得到了以下程序:

edge(a,b).
edge(b,c).
edge(a,d).

path(N,M):- path(N,New),edge(New,M).
path(N,M):- edge(N,M).

并询问是否将证明树算法应用于以下查询:

?- path(a,X). 

证明树是无限成功树，还是无限失败树？

现在，在我看来，在构建树的过程中，您会一遍又一遍地应用路径规则 1，创建无限树，而永远不会达到路径规则 2..

从而创建无限失败树。但是我的解决方案说它是无限成功树，我的问题是:我是对的还是我的教授是对的？ :]

Answer 1

不确定您使用的是什么术语，但 Lloyd 逻辑编程基础所使用的常用术语是SLD-tree，其中可能包含成功，< em>无限，失败分支。我假设您使用标准的 Prolog 计算规则(= 选择最左边的原子)。

您示例中的 SLD 树是无限的，并且包含与三个答案替换对应的有限多个成功分支:X = b ; X = c ; X = d。需要注意的是，虽然这棵树有一个无限的失败分支，但它仍然包含所有的解决方案!

计算规则的选择可能会影响 SLD 树的大小和结构。但好处是:无论你的计算规则是什么，我们都会得到成功的分支!保证!嗯，对于那些以巧妙的方式绘制无限 SLD 树并且知道如何使用……明智的人来说，这是有保证的。但对于拥有无限资源和智慧的人来说，没问题。

另一个观察结果是这个 SLD 树的形状完全独立于子句的顺序。因此，无论非递归规则是最后写(如您的情况)还是首先写，对树的形状没有太大影响:它将具有相同的大小(无限或有限)，将包含相同数量的节点，但一些分支会以不同的顺序出现。

Prolog 尝试增量生成该 SLD 树，但它使用最原始的方式来实现。它开始探索一个分支，并在扩展其他分支之前完全探索它。这意味着，Prolog 可以使用非常节省空间的 SLD 树表示(或者准确地说:仅 SLD 树的一部分)，实际上它本质上是一个堆栈，但要付出的代价是一旦遇到无限分支，你就会被卡住——除非你确实拥有无限资源。并且子句的顺序将影响成功分支(= 答案)是否会被找到，或者它们是否会被某个无限分支掩埋。

在实践中，很难想象所有这些无限大的树，我们不太习惯它们。

但是还有其他方法可以让您更好地理解 Prolog 如何执行其证明。

这里的中心概念是查询/目标的普遍终止，在 SLD 树中这意味着:所有分支的有限性。

很容易观察到目标的普遍终止:只需执行 Goal,false 即可。

那么这个 false 对我们的 SLD 树做了什么？本质上，我们现在仅有一个无限或有限的故障分支。所有答案都消失了。

现在，事情变得更好了:我们甚至可以在您的程序中引入 false。生成的程序称为 failure-slice .尽管此程序不再与原始程序相同，但以下属性成立:如果故障片不终止(= 有一个无限分支)，则原始程序也不会终止(= 有一个无限分支)。

故障切片通常要短得多，因此理解起来要快得多。拿你的程序:

?- path(a,X), false.edge(a,b) :- false.edge(b,c) :- false.edge(a,d) :- false.path(N,M):- path(N,New), false, edge(New,M).path(N,M):- false, edge(N,M).

有经验的 Prolog 程序员只看到程序的这个小片段，这更容易理解。他们不会花时间想象无限分支，也不会想象实际的 Prolog 执行 — 好吧，也许有一点，但只是针对片段，而不是整个程序。

从某种意义上说，false 已经向我们展示了计算规则:false 右侧的所有内容/strong> 被划过。

你也可以学会“看”这个，只要关注this link .