Prolog - 避免无限循环
Prolog - Avoid Infinite Loop
我目前正在学习逻辑程序设计，并为此学习Prolog。
我们可以有一个 Knowledge Base，它可以将我们引向一些 results，而 Prolog 将进入无限循环，因为它扩展谓词的方式。
假设我们有以下 logic program
p(X):- p(X).
p(X):- q(X).
q(X).
查询 p(john) 将进入无限循环，因为 Prolog 默认扩展第一个统一的谓词。但是，如果我们开始扩展第二个谓词，我们可以得出结论 p(john) 为真。
那么，如果 KB 可以得出结论，那么为什么 Prolog 不展开所有匹配的谓词（像 threads/processes 带有时间片的模型一样实现），以便得出结论？
例如，在我们的例子中，可以创建两个进程，一个用 p(X) 扩展，另一个用 q(X) 扩展。所以当我们稍后扩展 q(X) 时，我们的程序将得出 q(john).
因为Prolog匹配谓词的搜索算法是depth-first。因此，在您的示例中，一旦匹配了第一条规则，它将再次匹配第一条规则，并且永远不会探索其他规则。
如果算法是breadth-first or iterative-deepening，就不会发生这种情况。
通常由您重新排序 KB，这样这些情况就不会发生。
但是，编码是可能的breadth-first/iterative-deepening search in Prolog using a meta-interpreter that changes the search order. This is an extremely powerful technique that is not well known outside of the Prolog world. 'The Art of Prolog'详细描述了这种技术。
我目前正在学习逻辑程序设计，并为此学习Prolog。
我们可以有一个 Knowledge Base，它可以将我们引向一些 results，而 Prolog 将进入无限循环，因为它扩展谓词的方式。
假设我们有以下 logic program
p(X):- p(X).
p(X):- q(X).
q(X).
查询 p(john) 将进入无限循环，因为 Prolog 默认扩展第一个统一的谓词。但是，如果我们开始扩展第二个谓词，我们可以得出结论 p(john) 为真。
那么，如果 KB 可以得出结论，那么为什么 Prolog 不展开所有匹配的谓词（像 threads/processes 带有时间片的模型一样实现），以便得出结论？
例如，在我们的例子中，可以创建两个进程，一个用 p(X) 扩展，另一个用 q(X) 扩展。所以当我们稍后扩展 q(X) 时，我们的程序将得出 q(john).
因为Prolog匹配谓词的搜索算法是depth-first。因此，在您的示例中，一旦匹配了第一条规则，它将再次匹配第一条规则，并且永远不会探索其他规则。
如果算法是breadth-first or iterative-deepening，就不会发生这种情况。
通常由您重新排序 KB，这样这些情况就不会发生。
但是，编码是可能的breadth-first/iterative-deepening search in Prolog using a meta-interpreter that changes the search order. This is an extremely powerful technique that is not well known outside of the Prolog world. 'The Art of Prolog'详细描述了这种技术。