Ошибка глобального стека в прологе - PullRequest
Новая
       8

Ошибка глобального стека в прологе

1 голос
/ 20 июля 2011

Я пытаюсь запустить следующую программу в Прологе. 

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)

Я получаю сообщение «ОШИБКА: из глобального стека».

Есть идеи, что не так с кодом?

Ответы [ 2 ]

1 голос
/ 13 февраля 2019

Программа работает хорошо, но ...

В самом деле? Давайте попробуем минимальный случай: 

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

То есть даже в этом очень простом случае ваша программа зацикливается. Однако оказалось, что нашли два ответа! Второй ответ использует library(double_quotes) для печати "A" вместо ['A'].

В Прологе вы не получаете только один ответ, вы можете получить несколько из них ...

Простой способ непосредственно выявить такие проблемы, не связанные с терминацией, - добавить цель false к вашему запросу: 

?- p1(1,3,1,1,1,2,P), <b>false</b>.
   *LOOPS*

Мы можем добавить еще такие цели false в вашу программу. Строго говоря, это возможно только в том случае, если ваша программа является чисто монотонной. Вы используете cut и if-then-else, которые уничтожают такие свойства в общем случае. Однако в вашем случае их можно просто отбросить в следующем 

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

Считайте эту цель append(PROG1,['A'],PROG). Переменная PROG1 встречается здесь впервые и, следовательно, никогда не создается. Также PROG не создается. И, таким образом, эта цель будет повторяться.

Заменить append(PROG1,['A'],PROG) на PROG = ['A'|PROG1]. Теперь элементы располагаются в противоположном направлении, и, таким образом, обратное движение не требуется.

Запрос mama_mia1(70000,17,2,5,89000,89900,P) теперь просто не выполняется, как false.

0 голосов
/ 21 июля 2011

ОШИБКА: вне глобального стека

Сообщение

означает, что вашей программе требуется больше памяти. Либо он застрял в некотором бесконечном цикле, который потребляет всю память, либо в этом нет ничего плохого, и вход слишком велик, поэтому ему требуется больше памяти.

Учитывая, что ваши входные данные выглядят довольно большими и при условии, что вы протестировали меньшие входные данные и никаких проблем не возникало, я бы сказал, что вам просто нужно больше памяти

Вы можете увеличить размер стека ИЛИ вы можете попытаться использовать меньше памяти.

Конечно, если это какое-то упражнение, поданное где-то для проверки, могут быть ограничения в количестве памяти, которое вы можете получить: b

...