Prolog中的全局堆栈错误

Question

我试图在Prolog中运行以下程序。

mama_mia1(A,M,LI,HI,LO,HO,AA) :-
   p1(A,M,LI,HI,LO,HO,PROGS),
   reverse(PROGS,PROG),
   atom_chars(AA,PROG),
   !.

p1(_,_,LO,LO,LO,_,[]).
p1(_,_,HO,HO,_,HO,[]).
p1(_,_,LO,HO,LO,HO,[]).
p1(_,_,X,LO,LO,HO,[]) :- X>LO,X<HO.
p1(_,_,X,HO,LO,HO,[]) :- X>LO,X<HO.
p1(_,_,LO,Y,LO,HO,[]) :- Y>LO,Y<HO.
p1(_,_,HO,Y,LO,HO,[]) :- Y>LO,Y<HO.
p1(_,_,X,Y,LO,HO,[]) :- X>LO,X<HO,Y>LO,Y<HO.
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X1 is X+A,  H1 is HO+1, X1<H1, Y1 is Y+A,  Y1<H1 )
   -> append(PROG1,['A'],PROG),
      p1(A,M,X1,Y1,LO,HO,PROG1)
   ;  false).
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X2 is X * M,  H1 is HO+1, X2<H1, Y2 is Y * M,  Y2<H1)
   -> append(PROG2,['M'],PROG),
      p1(A,M,X2,Y2,LO,HO,PROG2)
   ;  false).

程序应该计算一个适当的加法和乘法路径，从li和hi之间的每个数字到lo和ho之间的结果。加法对应于字母A，乘法对应于M.在程序结束时，我们应该得到一个As和Ms字符串，对应于我们找到的路径。

该程序运行良好，但在尝试测试用例时：

mama_mia1(70000,17,2,5,89000,89900,P) 

我得到一个“错误：超出全局堆栈”的消息。

任何想法代码有什么问题？

Answer 1

该计划运行良好但......

真？让我们尝试一个最小的案例：

?- p1(1,3,1,1,1,2,P).
   P = []
;  P = "A"
;  *LOOPS*

也就是说，即使在这个非常简单的情况下，程序也会循环。然而，碰巧找到了两个答案！第二个答案使用library(double_quotes)来代替"A"打印['A']。

在Prolog你不会得到一个答案，你可能会得到其中几个......

直接检测此类非终止问题的简单方法是在查询中添加目标false：

?- p1(1,3,1,1,1,2,P), false.
   *LOOPS*

我们可以在您的计划中添加更多此类目标false。严格来说，只有当你的程序是一个纯粹的，单调的程序时才有可能。你正在使用cut和if-then-else，它们在一般情况下都会破坏这些属性。但是，在您的情况下，它们可以在以下failure-slice中丢弃

p1(_,_,LO,LO,LO,_,[]) :- false.
p1(_,_,HO,HO,_,HO,[]) :- false.
p1(_,_,LO,HO,LO,HO,[]) :- false.
p1(_,_,X,LO,LO,HO,[]) :- false, X>LO,X<HO.
p1(_,_,X,HO,LO,HO,[]) :- false, X>LO,X<HO.
p1(_,_,LO,Y,LO,HO,[]) :- false, Y>LO,Y<HO.
p1(_,_,HO,Y,LO,HO,[]) :- false, Y>LO,Y<HO.
p1(_,_,X,Y,LO,HO,[]) :- false, X>LO,X<HO,Y>LO,Y<HO.
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X1 is X+A,  H1 is HO+1, X1<H1, Y1 is Y+A,  Y1<H1 )
   -> append(PROG1,['A'],PROG), false,
      p1(A,M,X1,Y1,LO,HO,PROG1)
   ;  false ).
p1(A,M,X,Y,LO,HO,PROG) :- false,
   (  (X2 is X * M,  H1 is HO+1, X2<H1, Y2 is Y * M,  Y2<H1)
   -> append(PROG2,['M'],PROG),
      p1(A,M,X2,Y2,LO,HO,PROG2)
   ;  false ).

考虑这个目标append(PROG1,['A'],PROG)。变量PROG1首次出现在这里，因此它永远不会被实例化。 PROG也没有实例化。因此，这个目标将循环。

用append(PROG1,['A'],PROG)替换PROG = ['A'|PROG1]。现在元素以相反的方向出现，因此不需要反转。

查询mama_mia1(70000,17,2,5,89000,89900,P)现在只是像false那样失败了。

Answer 2

该

错误：超出全局堆栈

消息意味着您的程序需要更多内存。要么它停留在消耗所有内存的某个无限循环中，要么它没有任何问题，输入太大，因此需要更多内存。

考虑到你的输入看起来很大，并假设你已经测试了较小的输入并且没有出现问题，我会说你只需要更多的内存

你可以扩大stack的大小，或者你可以尝试使用更少的内存。

当然，如果这是提交某个地方进行检查的某种练习，那么你可以获得多少内存：b