Prolog递归永远循环

问题描述 投票:4回答:2
inside(a,b).
inside(a,c).
inside(b,d).
r_inside(X,Y) :- inside(X,Y).
r_inside(X,Y) :- inside(X,Z), r_inside(Z,Y).

当我尝试在with:r_inside(a,X)中找到任何内容时,上面的代码工作正常。我得到X = b,c,d,这是对的。但如果我将最后一行代码更改为:

r_inside(X,Y) :- r_inside(X,Z), inside(Z,Y).

然后我输入:r_inside(a,X),程序永远循环,为什么?

recursion prolog
2个回答
2
投票

Prolog是从语言处理研究中发明的,它展示了这种传统。你描述的问题被称为left recursion。最近,SWI-Prolog推出了其他Prologs模型,作为克服这种限制的通用工具。


4
投票

所以,为了清楚起见,我们正在谈论这个计划:

inside(a,b).
inside(a,c).
inside(b,d).

r_inside(X,Y) :- inside(X,Y).
r_inside(X,Y) :- r_inside(X,Z), inside(Z,Y).

和查询:

?- r_inside(a, X).
X = b ;
X = c ;
X = d ;
nontermination

为了突出查询的“不确定”方面(不会被任何具体的解决方案分心),我们可以使用:

?- r_inside(a, X), false.
nontermination

为了找到不确定的原因,我们可以使用基于程序切片的强大的声明性调试方法(参见)。我们的想法是在程序中的点处插入false/0,以便找到仍未终止的较小(理想情况:最小)代码片段。

例如,请考虑以下版本的代码:

inside(a,b) :- false.
inside(a,c) :- false.
inside(b,d) :- false.

r_inside(X,Y) :- false, inside(X,Y).
r_inside(X,Y) :- r_inside(X,Z), false, inside(Z,Y).

有了这个版本,我们仍然得到:

?- r_inside(a, X), false.
nontermination

我现在正在使用 三振出局 文本以删除前一版本中可以忽略的那些部分,因为它们不会导致无法终止:

inside(a,b) :- false.
inside(a,c) :- false.
inside(b,d) :- false.

r_inside(X,Y) :- false, inside(X,Y).
r_inside(X,Y) :- r_inside(X,Z), false, inside(Z,Y).

因此,我们将其简化为以下对非终止的解释,因为这是唯一剩下的片段:

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

这个片段本身已经导致不确定。没有你添加的事实,并且在单个剩余目标之后没有添加的目标可以阻止这一点。

因此,要解决此问题,您必须更改此片段。

您还可以通过考虑Prolog的实际执行策略来解释操作中的非终止。特别是,您可以使用其执行的深度优先方面进行争论。但是,为什么要这么低级别的解释呢?您可以自动生成故障切片,它们可以让您更直接地直接查看不确定的实际原因。

© www.soinside.com 2019 - 2024. All rights reserved.