prolog - 错误 : Out of local stack in my Prolog code

Question

我无法弄清楚为什么来自给定 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).

查询

?- indirect_likes(g,Which).

结果

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

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

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

然后我得到错误:本地堆栈不足!据我所知，逻辑合取是可交换的。

Answer 1

获取transitive-closure二元关系 <b>R_2</b> , 使用 meta-predicate closure/3 像这样:

?- closure(R_2,From,To).

Let's run a sample query of closure/3 together with likes/2!

?- closure(likes,X,Y).  X = g, Y = c; X = g, Y = a; X = g, Y = b; X = g, Y = a                    % redundant; X = g, Y = d; X = c, Y = a; X = c, Y = b; X = c, Y = a                    % redundant; X = c, Y = d; X = b, Y = a; X = b, Y = d; false.                          % query terminates universally

We get the same answers when we use indirect_likes/2, but in a different order:

?- indirect_likes(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                    % redundant; X = g, Y = a                    % redundant; X = c, Y = d; X = g, Y = d; false.                          % query terminates universally

As you stated in your comments to @C.B.'s answer, binary relations are not necessarily reflexive and/or symmetric. With the definition you gave, likes/2 is neither:

?- 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行为不稳定:

?- indirect_likes(b,b).  true; true; true...                               % does not terminate universally?- indirect_likes(X,Y), false.    % do we get finite failure?...                               % no! query does not terminate universally

我们能做什么？让我们使用 meta-predicate closure/3与 likes/2 的扩展版本!

?- closure(likes,b,b).  true                            % succeeds non-deterministically; false.                          % query terminates universally?- closure(likes,X,Y), false.     % do we get finite failure?false.                            % yes! query terminates universally

---

底线？

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

由于 Prolog 的 SLD resolution , 目标 false,repeat有限地失败，但是 repeat,false才不是。程序员需要处理终止，但对于 Prolog 提供的原始性能和控制而言，这通常是一个很小的代价。

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