Prolog Nim Game - Ошибка локального стека - PullRequest
Новая
       37

Prolog Nim Game - Ошибка локального стека

0 голосов
/ 11 февраля 2011

В последнее время я делаю Пролог. И я прочитал книгу «Искусство пролога». У них там есть реализация игры Nim. Поэтому я переписал его в SWI-Prolog, и все выглядит нормально, кроме этой ошибки Out of local stack. После отладки я обнаружил, что в этой части программы кажется, что она зациклена навсегда: 

nim_sum([N|Ns],Bs,Sum):-
      binary(N,Ds), nim_add(Ds,Bs,Bs1), nim_sum(Ns,Bs1,Sum).
nim_sum([],Sum,Sum).

nim_add(Bs,[],Bs).
nim_add([],Bs,Bs).
nim_add([B|Bs],[C|Cs],[D|Ds]):-
    D is (B+C) mod 2, nim_add(Bs,Cs,Ds).

Кто-нибудь сталкивался с такой проблемой? Есть предложения по альтернативной реализации?

1 Ответ

2 голосов
/ 11 февраля 2011

Чтобы избежать проблем "вне стека", часто необходимо записать рекурсивные предикаты в форме "оптимизации последнего вызова" или "хвостовой рекурсии".

Здесь, кажется, два предложения для nim_sum / 3 следует перевернуть (ставя сначала «факт», что является условием завершения).Тогда вызов nim_sum / 3 , сделанный сам себе в предложении, которое имеет тело, будет выполнен без открытых точек возврата (при условии binary / 2 и nim_add / 3 являются детерминированными).

Попробуйте поменять эти два предложения на nim_sum и сообщите нам, как это работает.

Добавлено: Подумав о nim_add / 3 , я подозреваю, что механизм Пролога, вероятно, не обнаружит, что он является детерминированным, то есть успешно выполняется только одним способом.Это работа для кроя!оператор.Самое простое решение - добавить один отрезок прямо перед тем, где nim_sum / 3 вызывает себя, чтобы точно не было точек возврата, открытых во время выполнения рекурсивного вызова.Однако это более "в духе" Пролога: 

nim_sum([],Sum,Sum).  
nim_sum([N|Ns],Bs,Sum):-  
    binary(N,Ds),  
    nim_add(Ds,Bs,Bs1),  
    nim_sum(Ns,Bs1,Sum).  

nim_add(Bs,[],Bs) :- !.  
nim_add([],Bs,Bs) :- !.  
nim_add([B|Bs],[C|Cs],[D|Ds]):-  
    D is (B+C) mod 2,  
    nim_add(Bs,Cs,Ds).

Опять же, это предполагает, что binary / 2 является детерминированным, предположительно, преобразуя целое число (неотрицательное?) В список 0 и1, младшие биты вначале.

...