prolog - 带变量的反向链接

Question

我一直在阅读有关 Prolog/Datalog 中的推理的信息，虽然前向链接似乎很容易掌握，但对于任何类型的复杂示例，我在后向链接方面存在一些问题，这些示例不仅仅是命题或用于确定真值或假值。我正在阅读一篇文章，给出了以下示例：

sg(X,X)
sg(X,Y) :- par(X, X1), par(Y,Y1), sg(X1,Y1)

假设我们要查询sg(a,W)wherea是常量W还是变量。这可以理解为：

给我所有与a.

文章首先指出，这些特定规则将导致 Prolog/Datalog 中的无限循环，但可以通过将第二条规则更改为：

sg(X,Y) :- par(X, X1),  sg(X1,Y1), par(Y,Y1). 

为什么原始结果会循环？其次，这种查询的执行会是什么样子？值何时绑定到这些变量？

Answer 1

这篇文章似乎不是很详细。假设调用是“sg(a,W)”。让我们分析第一种可能性：

sg(X,Y) :- par(X, X1), par(Y,Y1), sg(X1,Y1)

第一个“par”将被查询为“par(X=a,X1)”，接下来是“par(Y=W,Y1)”。最后一个查询是一个完全未绑定的查询，可能是本文试图跳过的内容。

现在，第二种可能性：

 sg(X,Y) :- par(X, X1),  sg(X1,Y1), par(Y,Y1). 

执行为 par(X=a,X1), sg(X1 /* 绑定在前一个/, Y1), par(Y=W,Y1/绑定在前一个 */)。如您所见，在所有查询中，至少有一个参数先前已绑定。