2

我无法弄清楚为什么来自给定 Prolog 代码的以下查询会生成错误Out of local stack。

序言代码：

likes(g,c).
likes(c,a).
likes(c,b).
likes(b,a).
likes(b,d).

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

查询

?- likes(g,X).

结果是

X = c ;
X = a ;
X = b ;
ERROR: Out of local stack

编辑1这是我认为Prolog应该处理这个查询的方式，

likes(g,c) is a fact, so X={c}
likes(g,b) <= likes(g,c) and likes(c,b), so X={c,b}
likes(g,a) <= likes(g,b) and likes(b,a), so X={c,b,a}
likes(g,d) <= likes(g,b) and likes(b,d), so X={c,b,a,d}
              likes(g,a) and false, so nothing to add to X
              likes(g,d) and false, so nothing to add to X 
end of backtracking search.

编辑 2通过以下代码修改，我设法得到了我想要的东西：

likes(g,c).
likes(c,a).
likes(c,b).
likes(b,a).
likes(b,d).

indirect_likes(A,B):- likes(A,B).
indirect_likes(A,C):- likes(B,C), indirect_likes(A,B).

查询

?- 间接喜欢（g，哪个）。

结果是

Which = c ;
Which = a ;
Which = b ;
Which = a ;
Which = d ;
false.

但是，仍然有一些我无法弄清楚背后的理由。如果我将最后一条规则更改为

indirect_likes(A,C):- indirect_likes(A,B), likes(B,C).

然后我得到ERROR: Out of local stack！据我所知，逻辑合取是可交换的。

4

2 回答 2

3

要获得二元关系的R_2，请使用 closure/3，如下所示：

?- 闭包（R_2，从，到）。

closure/3让我们一起运行一个示例查询likes/2！

?- 闭包（喜欢，X，Y）。
  X = g，Y = c
; X = g, Y = a
; X = g，Y = b
; X = g, Y = a                     %冗余
; X = g，Y = d
; X = c, Y = a
; X = c, Y = b
; X = c, Y = a                     %冗余
; X = c, Y = d
; X = b，Y = a
; X = b，Y = d
; 错误的。% 查询普遍终止

当我们使用 时，我们得到相同的答案indirect_likes/2，但顺序不同：

?- 间接喜欢（X，Y）。
  X = g，Y = c
; X = c, Y = a
; X = c, Y = b
; X = b，Y = a
; X = b，Y = d
; X = g, Y = a
; X = g，Y = b
; X = c, Y = a                     %冗余
；X = g, Y = a                     %冗余
; X = c, Y = d
; X = g，Y = d
; 错误的。% 查询普遍终止

正如您在对@CB 答案的评论中所说，二元关系不一定是自反和/或对称的。根据您给出的定义，likes/2既不是：

?- likes(X,X).
false.                            % not reflexive (not even close)

?- likes(X,Y), likes(Y,X).
false.                            % not symmetric (not even close)

到目前为止，一切都很好！

让我们暂时将以下附加事实添加到您的数据库中：

likes(b,b).

使用这个扩展的定义，indirect_likes/2行为异常：

?- 间接喜欢（b，b）。
  真的
; 真的
; 真的
... %不会普遍终止

?- 间接喜欢（X，Y），假的。% 我们得到有限的失败吗？
... ％ 不！查询不会普遍
终止

我们能做什么？让我们使用带有扩展版本的 ！closure/3likes/2

?- 闭包（喜欢，b，b）。
  true % 不确定地成功
; 错误的。% 查询普遍终止

?- 闭包（喜欢，X，Y），假的。% 我们得到有限的失败吗？
错误的。％ 是的！查询普遍终止

底线？

在纯 Prolog 中，连词是可交换的，就逻辑意义而言。

由于 Prolog 的SLD 分辨率，目标false,repeat有限地失败，但repeat,false没有。程序员需要处理终止，但通常这是为 Prolog 提供的原始性能和控制付出的小代价。

在这个答案中，我将“终止担忧”传递给 closure/3的实现者 :)

于 2015-09-03T13:49:31.017 回答
2

你会陷入无限递归。

一旦你到达likes(b,a)，你调用likes(a,_G4382)，它没有定义事实，所以它切换到规则likes(X,Z) :- likes(X,Y), likes(Y,Z).所以它一遍又一遍地调用likes(a,_G4383)which 。likes(X,Z) :- likes(X,Y), likes(Y,Z).

您可能想要定义和辅助谓词aux_likes/2来承载您的所有事实。这只有在没有循环关系时才有效，即aux_likes(b,c)和aux_likes(c,b)。您还需要定义likes(X,X).这本质上是一个图问题，在图论中，节点必须连接到自身。如果您将它用作生成器，它将进入无限递归（如果您有循环），除非您添加cuts不理想的。

如果使用swi-prolog，请随意输入debug或spy查询以查看发生了什么。

代码：

aux_likes(g,c).
aux_likes(c,a).
aux_likes(c,b).
aux_likes(b,a).
aux_likes(b,d).

likes(X,Z) :- aux_likes(X,Y), likes(Y,Z).

likes(X,X).

带有新谓词的输出：

?- likes(g,X),print(X),nl,fail.
a
a
d
b
c
g
false.

这表示g可以a通过c或通过b。它喜欢d通过b，它喜欢b通过c，它c直接喜欢。它也必须喜欢它自己才能像这样查询。如果您希望使用模式(+,+)意味着您同时提供术语和不提供变量（作为检查器），您可以这样做

?- likes(g,c).
true .
于 2014-01-07T19:18:18.513 回答