Out Of Global Stack Error in Prolog

Question

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).

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?

Answer 1

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.

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'].

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

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.

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 ).

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.

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

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

Answer 2

The

ERROR: out of global stack

message means that your program needs more memory. Either it's stuck in some infinite loop that consumes all the memory or there is nothing wrong with it and the input is just too large so it needs more memory.

Considering that your input looks quite large and assuming that you have tested smaller inputs and no problem occurred I would say that you just need more memory

You can expand the size of the stack OR you can try to use less memory.

Of course, if this is some sort of exercise submitted somewhere to be checked, there could be limits in how much memory you could get :b