Game Prolog Nim - Out d'erreur de pile locale

Question

J'ai fait du prolog ces derniers temps. Et j'ai lu l'art de Prolog Book. Ils y ont une implémentation de jeu NIM. Je l'ai donc réécrit à Swi-Prolog et tout semble bien, sauf cela de l'erreur de pile locale. Après le débogage, j'ai découvert qu'il semble boucle pour toujours dans cette partie du programme:

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

Quelqu'un a-t-il rencontré ce genre de problème? Des suggestions pour une mise en œuvre alternative?

Answer 1

Pour éviter les problèmes "hors de la pile", il est souvent nécessaire d'écrire les prédicats récursifs dans une forme "dernière optimisation d'appel" ou "queue récursive".

Ici, il semble que les deux clauses nim_sum / 3 devrait être inversé (mettre la clause "FACT" en premier, qui est la condition de résiliation). Puis l'appel nim_sum / 3 se fait dans la clause dont un corps sera fait sans aucun point de retour en arrière-plan (en supposant binaire / 2 et NIM_ADD / 3 sont déterministes).

Essayez d'échanger ces deux clauses pour nim_sum Et faites-nous savoir comment cela fonctionne.

Ajoutée: Après avoir réfléchi davantage à NIM_ADD / 3, Je soupçonne que le moteur Prolog ne détectera probablement qu'il est déterministe, c'est-à-dire que la même manière. C'est un travail pour la coupe! opérateur. La solution la plus simple consiste à ajouter une coupe juste devant nim_sum / 3 s'appelle lui-même, de sorte qu'il n'y a certainement pas de points de retour en arrière-plan au moment où l'appel récursif est passé. Cependant, c'est plus "dans l'esprit" de 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).  

Encore une fois, cela suppose binaire / 2 Est-ce que déterministe, vraisemblablement convertit un entier (non négatif?) En une liste de 0 et 1, les moins significatifs.