理解 Prolog 中的递归性

Question

我有这个例子：

descend(X,Y)  :-  child(X,Y). 
descend(X,Y)  :-  child(X,Z), descend(Z,Y).

child(anne,bridget). 
child(bridget,caroline). 
child(caroline,donna).

效果很好，我明白了。这是一个小练习的解决方案。我的解决方案是相同的，但有所不同：

descend(X,Y) :- descend(X,Z), descend(Z,Y).

即在第二个descend规则中将child改成descend。

如果我在第一个解中查询descend(X, Y).，我得到：

?- descend(X, Y).
X = anne,
Y = bridget ;
X = bridget,
Y = caroline ;
X = caroline,
Y = donna ;
X = anne,
Y = caroline ;
X = anne,
Y = donna ;
X = bridget,
Y = donna ;
false.

这是正确的。但是如果我用相同的解决方案查询，我会得到：

?- descend(X, Y).
X = anne,
Y = bridget ;
X = bridget,
Y = caroline ;
X = caroline,
Y = donna ;
X = anne,
Y = caroline ;
X = anne,
Y = donna ;
ERROR: Out of local stack

没说X = bridget,Y = donna ;也溢出了。我明白为什么它会溢出。我不明白的是为什么它没有找到最后的关系。是溢出的原因吗？如果是这样，为什么？（为什么堆栈这么大，知识库这么小？）。

如果我查询 descend(bridget, donna)，它会回答 yes。

我在想象探索树时遇到问题...

抛开那个问题，我猜原来的解决方案效率更高（忽略我最后进入死循环的事实），不是吗？

谢谢！

Answer 1

I'm having problems imagining the exploration tree...

是的，这在 Prolog 中相当困难。如果你有一个更大的数据库，情况会更糟！但大多数时候没有必要设想非常精确的搜索树。相反，您可以使用几个非常稳健的概念。

记住您是如何制定查询的。您一个接一个地查看解决方案。但您真正感兴趣的是查询是否终止的问题。您可以通过添加 false.

而无需查看解决方案

?- descend(X, Y), false.
ERROR: Out of local stack

这个查询永远不可能为真。它可能会失败、溢出、循环或产生另一个错误。剩下的是一个非常有用的概念：通用终止或者在这种情况下是非终止。

这可以扩展到您的实际程序中：

descend(X,Y) :- false, child(X,Y). 
descend(X,Y) :- descend(X,Z), false, descend(Z,Y).

如果这个名为 failure-slice 的片段没有终止，那么您的原始程序也不会终止。看看你程序的这个悲惨的剩余部分！甚至 child/2 都不再存在了。因此我们可以得出结论 child/2 不影响非终止！ Y 只出现一次。 X 永远不会导致失败。因此 descend/2 终止 never!

所以这个结论比仅仅关于特定搜索树的陈述要普遍得多。这是关于所有个的声明。

如果您仍想推断解决方案的非常精确的顺序，您将不得不深入实际执行。但是为什么要打扰呢？它非常复杂，特别是如果您的 child/2 关系包含循环。您很可能会混淆事物并建立不准确的理论（^{_{至少我做到了}}）。不需要另一个货物崇拜。就我而言，我已经放弃了多达 "step through" 如此多的细节。我不会错过它。

理解 Prolog 中的递归性

Understanding recursivity in Prolog

prolog

failure-slice