了解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). 

它工作得很好,我理解它.这是一个小练习的解决方案.我的解决方案是一样的,但改变了:

下降(X,Y): - 下降(X,Z),下降(Z,Y).

也就是说,改变child为descend第二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

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

是的,在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终止!

因此,这个结论比仅仅关于特定搜索树的声明更为通用.这是关于所有这些的陈述.

如果您仍然想要解释解决方案的非常精确的顺序,那么您将不得不深入了解实际的执行情况.但为什么要这么麻烦？它非常复杂,特别是如果您的child/2关系包含循环.有可能你会混淆事物并建立不准确的理论(^{_{至少我做过}}).不需要另外的货物崇拜.举个例子,我已经放弃了"逐步完成"如此无数的细节.我不会错过它.