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

Question

В последнее время я занимаюсь прологом. И я прочитал книгу «Искусство Пролога». Там есть игра 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). 

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

Answer 1

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

Здесь два предложения для nim_sum/3 следует отменить (сначала ставится предложение «факт», что является условием завершения). Тогда вызов nim_sum/3 делает себе в предложении, который имеет тело будет сделано без каких-либо точек BACKTRACK открытых (предполагая, что двоичный/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). 

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