Prolog Nim Game - Errore di stack locale esaurito
-
12-11-2019 - |
Domanda
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?
Soluzione
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.