SWI Prolog不会终止

Question

:- use_module(library(clpfd)).

fact(treated=A) :- A in 0..1.
fact(numYears=B) :- B in 0..sup.
fact(numDrugs=C) :- C in 0..sup.
fact(treated2=D) :- D in 0..1.
fact(cParam=E) :- E in 0..4.

is_differentfact(X,X) :- false.
is_differentfact(Element=_,OtherElement=_) :-
    dif(Element,OtherElement).

is_fakt([]).
is_fakt([X|Xs]) :-
    fact(X),
    maplist(is_differentfact(X),Xs),
    is_fakt(Xs).

为什么?- is_fakt(X)返回一个结果列表的答案,但在一些结果答案后它会挂起.我不知道为什么Prolog无法返回X的所有可能值.

Answer 1

你问:

为什么?- is_fakt(L)...但一些后,结果 答案它挂起.

你说一个数字.这个数字是62次,SPACE以达到循环的那一刻.好久不是吗？你的程序很小.您将如何有机会通过更大的计划做同样的事情？别担心,有帮助.但是你需要从不同的角度来看待这个程序.

在Prolog中,理解非常精确地执行具体查询几乎是不可能的.你有两种不同类型的控制流交错加上奇怪的数据结构,不需要存在,但后来"进来"; 有时.所有这些都打开了一个真正可能的执行痕迹,这些痕迹充满了细节,你的思绪会溢出 - 更糟糕的是:你的思想仍然会假装你了解一切,但事实并非如此.并且错误在你的程序中有很大的聚会时间.这些错误将在未来的某个时间点出现,但仅限于基于错误的基础.这可能非常令人沮丧.毕竟,该程序非常小,应该易于理解(按照命令式语言的标准).但是,对于其他语言非常复杂的问题,Prolog程序往往非常紧凑.

尝试使用跟踪器来查看我的意思.你会看到各种各样的事情发生.而且大多数都是无关紧要的.

幸运的是,有很多方法可以理解Prolog,但在这里你必须依赖语言本身的优秀属性.对于非终止的本地化原因,最好是开始考虑故障片.通过在程序中添加目标,可以从程序中获取故障片false.如果结果程序仍然没有终止,我们有理由也为什么我们的原始程序不会终止.

想一想:我们不是试图理解你的程序,而是做一些人类更擅长的事情:做出有根据的猜测.这个猜测可能会出错,但我们可以轻松检查.一开始你会猜测得非常糟糕.很快你会发现你可以系统地做很多事情.现在变得无关紧要的所有代码都会被扼杀.

:- use_module(library(clpfd)).

fact(treated=A) :- A in 0..1.     
fact(numYears=B) :- B in 0..sup, false.
fact(numDrugs=C) :- C in 0..sup, false.
fact(treated2=D) :- D in 0..1, false.
fact(cParam=E) :- E in 0..4, false.

is_differentfact(X,X) :- false.
is_differentfact(Element=_,OtherElement=_) :-
    dif(Element,OtherElement).

is_fakt([]).
is_fakt([X|Xs]) :-
    fact(X),
    maplist(is_differentfact(X),Xs),
    is_fakt(Xs).

我们获得了什么？我们可以更快地缩小问题的范围:

?- is_fakt(Xs).
Xs = [] ;
Xs = [treated=_G180099],
_G180099 in 0..1 ;
**loops**

在继续之前,我试着理解你的意思is_fakt/1.你可能的意思是:所有事实都按照他们的名字,并确保没有重复.现在我们只有命名的事实treated,所以我们只能生成一个长度为1的列表.然后它循环.

你说:

我不知道为什么Prolog无法返回所有可能的值X.

要挑剔,那不是真的.Prolog确实列举了所有可能的值X.但后来它没有终止.

((有些评论要考虑:你真的想以这种方式得到那个列表吗？你会得到所有的排列!有一个长度为n的列表,你会得到n!不同的答案.对于n = 10,这是3628800.这是,你想要什么？可能不是.))

但是,让我们首先坚持确定不终止的确切原因.

为了更好地确定原因,让"关闭"所有答案.所以我们用以下方法查询is_fakt(L),false:

:- use_module(library(clpfd)).

fact(treated=A) :- A in 0..1.     
fact(numYears=B) :- B in 0..sup, false.
fact(numDrugs=C) :- C in 0..sup, false.
fact(treated2=D) :- D in 0..1, false.
fact(cParam=E) :- E in 0..4, false.

is_differentfact(X,X) :- false.
is_differentfact(Element=_,OtherElement=_) :-
    dif(Element,OtherElement).

is_fakt([]) :- false.
is_fakt([X|Xs]) :-
    fact(X),
    maplist(is_differentfact(X),Xs), false,
    is_fakt(Xs).

这是一个最小的故障片.所以它maplist/2不是首先终止的.你的想法是确保X有一个与事实名称不同的事实名称Xs.但如果Xs没有约束,那将永远不会终止.我们来试试吧:

?- maplist(is_differentfact(X),Xs).
Xs = [] ;
X = (_G496=_G497),
Xs = [_G508=_G509],
dif(_G496, _G508) ;
X = (_G552=_G553),
Xs = [_G564=_G565, _G570=_G571],
dif(_G552, _G570),
dif(_G552, _G564) ;
X = (_G608=_G609),
Xs = [_G620=_G621, _G626=_G627, _G632=_G633],
dif(_G608, _G632),
dif(_G608, _G626),
dif(_G608, _G620) ;
X = (_G664=_G665),
Xs = [_G676=_G677, _G682=_G683, _G688=_G689, _G694=_G695],
dif(_G664, _G694),
dif(_G664, _G688),
dif(_G664, _G682),
dif(_G664, _G676) ;
X = (_G720=_G721),
Xs = [_G732=_G733, _G738=_G739, _G744=_G745, _G750=_G751, _G756=_G757],
dif(_G720, _G756),
dif(_G720, _G750),
dif(_G720, _G744),
dif(_G720, _G738),
dif(_G720, _G732) ...

不太好看......但我们可以做得更好:

?- maplist(is_differentfact(X),Xs), false.
**loops**

所以它循环.这是不终止的原因.要解决这个问题,我们必须在故障切片的剩余可见部分做一些事情......

有关更多信息,请查找标记为failure-slice的其他解释

Answer 2

根据错误评论编辑版本。

:- use_module(library(clpfd)).
:- use_module(library(lists)).

fact(treated-X) :- X in 0..1.
fact(numYears-X) :- X in 0..sup.
fact(numDrugs-X) :- X in 0..sup.
fact(treated2-X) :- X in 0..1.
fact(cParam-X) :- X in 0..4.

facts(Facts) :-
findall(X,fact(X),Facts).

is_fact2(_, []).
is_fact2(Facts, [X|Xs]) :-
    member(X,Facts),
    select(X,Facts,Remaining),
    is_fact2(Remaining,Xs).

is_fakt(X) :-
    facts(Facts),
    is_fact2(Facts,X),
    keysort(X,X).

这件事现在结束了。