Prolog Nim Game - Errore di stack locale esaurito

Question

Ultimamente ho fatto un po' di Prolog.E ho letto il libro The Art Of Prolog.Lì hanno un'implementazione del gioco Nim.Quindi l'ho riscritto in SWI-Prolog e tutto sembra a posto tranne questo errore Out of local stack.Dopo il debug ho scoperto che sembra che il ciclo continui all'infinito in questa parte del programma:

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

Qualcuno si è imbattuto in questo tipo di problema?Qualche suggerimento per qualche implementazione alternativa?

Answer 1

Per evitare problemi di "out of stack" è spesso necessario scrivere i predicati ricorsivi in ​​una forma di "ottimizzazione dell'ultima chiamata" o "coda ricorsiva".

Qui sembrano le due clausole for somma_nim/3 dovrebbe essere invertito (mettendo prima la clausola "fatto", che è la condizione di risoluzione).Poi la chiamata somma_nim/3 fa a se stesso nella clausola che ha un corpo sarà fatto senza alcun punto di backtrack aperto (assumendo binario/2 E nim_aggiungi/3 sono deterministici).

Prova a scambiare queste due clausole con nim_sum e facci sapere come funziona.

Aggiunto: Dopo averci pensato ulteriormente nim_aggiungi/3, sospetto che il motore Prolog probabilmente non rileverà che è deterministico, cioèriesce in un solo modo.Questo è un lavoro da tagliare!operatore.La soluzione più semplice è aggiungere un taglio proprio davanti a dove somma_nim/3 chiama se stessa, in modo che non vi siano sicuramente punti di backtrack aperti nel momento in cui viene effettuata la chiamata ricorsiva.Tuttavia questo è più "nello spirito" di 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).  

Ancora una volta questo presuppone binario/2 è deterministico, presumibilmente converte un numero intero (non negativo?) in un elenco di 0 e 1, partendo prima dai bit meno significativi.