Prolog - 避免无限循环

Question

我目前正在学习逻辑编程,并学习Prolog该案例.

我们可以有一个Knowledge Base,它可以引导我们到一些results,而Prolog由于它扩展谓词的方式将进入无限循环.

假设我们有以下内容 logic program

p(X):- p(X).
p(X):- q(X).
q(X).

查询p(john)将进入无限循环,因为Prolog默认情况下会扩展统一的第一个谓词.但是,p(john)如果我们开始扩展第二个谓词,我们可以得出结论.

那么为什么不Prolog扩展所有匹配谓词(像时间片一样实现线程/进程模型),以便在KB可以得出结论的情况下得出结论？

例如,在我们的例子中,可以创建两个进程,一个用p(X)扩展,另一个用q(X)扩展.因此,当我们稍后扩展q(X)时,我们的程序将得出结论q(john).

Answer 1

因为Prolog用于匹配谓词的搜索算法是深度优先的.因此,在您的示例中,一旦匹配第一个规则,它将再次匹配第一个规则,并且永远不会探索其他规则.

如果算法是广度优先或迭代深化,则不会发生这种情况.

通常由您来重新排序KB,以便这些情况永远不会发生.

但是,可以使用改变搜索顺序的元解释器在Prolog中编码广度优先/迭代加深搜索.这是一种非常强大的技术,在Prolog世界之外并不为人所知."Prolog的艺术"详细描述了这种技术.

你可以在这里,这里和这里找到一些元解释器的例子.