프롤로그 NIM 게임 - 로컬 스택 오류가 발생했습니다

Question

나는 최근에 프롤로그를 해왔다.프롤로그 북의 예술을 읽었습니다.거기에는 NIM 게임 구현이 있습니다.그래서 저는 Swi-Prolog에 다시 작성하며 이는 로컬 스택 오류가 발생하지 않으면 모든 것이 좋습니다. 디버깅 후에 프로그램 의이 부분에서 영원히 반복되는 것처럼 보입니다.

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

"스택 아웃"문제를 피하려면 "마지막 호출 최적화"또는 "Tail Retursive"양식에 재귀 조건을 쓸 필요가있는 경우가 많습니다.

여기 nim_sum / 3 의 두 조항이 반전되어야합니다 (종료 조건 인 "사실"을 첫 번째 "제 먼저 넣는 것). 그런 다음 nim_sum / 3 은 백 트랙 포인트가 열리지 않고 몸이 만들어지지 않는 조항에서 자체적으로 만듭니다 ( 바이너리 / 2 및 nim_add / 3 은 결정 론적입니다.

nim_sum 에 대한 두 조항을 교환하고 작동하는 방법을 알려주십시오.

add : nim_add / 3 에 대해 더 생각한 후, 프롤로그 엔진이 그것이 결정론자임을 탐지하지 않을 것이라고 의심하지 않는다고 생각합니다. 즉, 단지 한 가지 방법으로 성공합니다. ...에 이것은 컷을위한 일입니다! 운영자. 가장 간단한 솔루션은 nim_sum / 3 자체의 앞에 하나의 절단을 추가하는 것입니다. 따라서 재귀 호출이 이루어지면 백 트랙 포인트가 열리지 않도록하십시오. 그러나 이것은 Prolog의 "영혼"입니다.

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의 목록으로 변환하는 것으로 가정합니다.