Prolog中超出全局堆栈错误 [英] Out Of Global Stack Error in Prolog

问题描述

我正在尝试在Prolog中运行以下程序.

I am trying to run the following program in 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字符串.

The program should calculate an appropriate path of additions and multiplications leading from every number between li and hi to a result between lo and ho. An addition corresponds to the letter A and multiplication corresponds to M. At the end of the program we are supposed to get a string of As and Ms corresponding to the path we found.

程序运行良好，但是在尝试测试用例时:

The program runs well but when trying the test case :

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

我收到错误:超出全局堆栈"消息.

I get an "ERROR: out of global stack " message.

任何想法代码有什么问题吗?

Any ideas what is wrong with the code?

推荐答案

程序运行良好，但是...

The program runs well but ...

真的吗?让我们尝试一个最小的情况:

Really? Let's try out a minimal case:

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

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

That is, even in this very simple case your program loops. However, it happened to find two answers! The second answer uses library(double_quotes) for printing "A" in place of ['A'].

在Prolog中，您不仅会得到一个答案，而且可能会得到几个答案...

In Prolog you do not get just one answer, you may get several of them...

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

An easy way to directly detect such problems of non-termination is to add a goal false to your query:

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

我们可以将进一步的目标false添加到您的程序中.严格来说，只有在您的程序是纯单调的程序时才有可能.在一般情况下，您使用的是cut和if-then-else，它们都会破坏此类属性.但是，对于您而言，可以将它们丢弃在以下失败切片

We can add further such goals false into your program. Strictly speaking, this is only possible if your program is a pure, monotonic one. You are using cut and if-then-else which both destroy such properties in the general case. However, in your case, they can just be discarded in the following 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也没有实例化.因此，这个目标将会循环.

Consider this goal append(PROG1,['A'],PROG). The variable PROG1 occurs here for the first time and thus it is never instantiated. Also PROG is not instantiated. And thus this goal will loop.

将append(PROG1,['A'],PROG)替换为PROG = ['A'|PROG1].现在，这些元素沿相反的方向出现，因此不需要反转.

Replace append(PROG1,['A'],PROG) by PROG = ['A'|PROG1]. Now the elements occur in opposite direction and thus no reversing is needed.

现在查询mama_mia1(70000,17,2,5,89000,89900,P)就像false一样失败.

The query mama_mia1(70000,17,2,5,89000,89900,P) now simply fails just like false did.

这篇关于Prolog中超出全局堆栈错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！