错误:在我的 Prolog 代码中超出本地堆栈 [英] ERROR: Out of local stack in my Prolog code
问题描述
我无法弄清楚为什么来自给定 Prolog 代码的以下查询会生成错误 Out of local stack
.
序言代码:
喜欢(g,c).喜欢(c,a).喜欢(c,b).喜欢(b,a).喜欢(b,d).喜欢(X,Z): - 喜欢(X,Y),喜欢(Y,Z).
查询
?- 喜欢(g,X).
结果
X = c ;X = 一个;X = b;错误:超出本地堆栈
编辑 1 这是我认为 Prolog 应该处理这个查询的方式,
likes(g,c) 是事实,所以 X={c}likes(g,b) <= likes(g,c) 和 likes(c,b),所以 X={c,b}likes(g,a) <= likes(g,b) 和 likes(b,a),所以 X={c,b,a}likes(g,d) <= likes(g,b) 和 likes(b,d),所以 X={c,b,a,d}likes(g,a) 和 false,所以没有什么可添加到 Xlikes(g,d) 和 false,所以没有什么可添加到 X回溯搜索结束.
编辑 2 通过对代码的以下修改,我设法得到了我想要的东西:
喜欢(g,c).喜欢(c,a).喜欢(c,b).喜欢(b,a).喜欢(b,d).间接喜欢(A,B): - 喜欢(A,B).间接喜欢(A,C):-喜欢(B,C),间接喜欢(A,B).
查询
?-indirect_likes(g,Which).
结果
Which = c ;哪个 = 一个;哪个 = b;哪个 = 一个;其中 = d;错误的.
但是,我仍然无法弄清楚背后的原理.如果我将最后一条规则更改为
indirect_likes(A,C):-indirect_likes(A,B), likes(B,C).
然后我得到 ERROR: Out of local stack
!据我所知,逻辑合取是可交换的.
要获得 传递闭包二元关系R_2
,使用元谓词 closure/3
像这样:
让我们一起运行 closure/3
和 likes/2
的示例查询!
当我们使用 indirect_likes/2
时,我们得到相同的答案,但顺序不同:
正如您在对@C.B. 的回答的评论中所述,二元关系不一定是自反和/或对称的.根据您给出的定义,likes/2
都不是:
?- 喜欢(X,X).错误的.% 不自反(甚至不接近)?- 喜欢(X,Y),喜欢(Y,X).错误的.% 不对称(甚至不接近)
<小时>
到目前为止,一切都很好!
让我们暂时将以下附加事实添加到您的数据库中:
喜欢(b,b).
有了这个扩展定义,indirect_likes/2
表现不正常:
我们能做什么?让我们使用 meta-predicate closure/3
和 likes/2
的扩展版本!
<小时>
底线?
在纯 Prolog 中,就逻辑意义而言,连词是可交换的.
由于 Prolog 的 SLD 解析,目标 false,repeat
有限失败,但 repeat,false
不会.程序员需要处理终止,但通常这是为 Prolog 提供的原始性能和控制所付出的很小的代价.
在这个答案中,我将终止担忧"传递给了 元谓词 closure/3
:)
I cannot figure out why the following query from the given Prolog code generates the error Out of local stack
.
Prolog code:
likes(g,c).
likes(c,a).
likes(c,b).
likes(b,a).
likes(b,d).
likes(X,Z) :- likes(X,Y), likes(Y,Z).
the query
?- likes(g,X).
results in
X = c ;
X = a ;
X = b ;
ERROR: Out of local stack
Edit 1 This is the way I think that Prolog should deal with this query,
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.
Edit 2 I managed to get what I was looking for by the following modification of the code:
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).
the query
?- indirect_likes(g,Which).
results in
Which = c ;
Which = a ;
Which = b ;
Which = a ;
Which = d ;
false.
However, there is still something which I cannot figure out the rationale behind. If I change the last rule to be
indirect_likes(A,C):- indirect_likes(A,B), likes(B,C).
Then I get ERROR: Out of local stack
! As far as I know, logical conjunction is commutative.
To get the transitive-closure of binary relation R_2
, use meta-predicate closure/3
like so:
?- 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)
So far, so good!
Let's tentatively add the following additional fact to your database:
likes(b,b).
With this expanded definition, indirect_likes/2
behaves erratically:
?- 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
What can we do? Let's use meta-predicate closure/3
with the expanded version of 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
The bottom line?
In pure Prolog, conjunction is commutative, as far as the logical meaning is concerned.
Due to Prolog's SLD resolution, the goal false,repeat
finitely fails, but repeat,false
does not.
The programmer needs to take care of termination, but usually this is a small price to pay for the raw performance and control that Prolog offers.
In this answer I passed "termination worries" on to the implementor of meta-predicate closure/3
:)
这篇关于错误:在我的 Prolog 代码中超出本地堆栈的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!