Questo codice è ricorsivo in coda?

Question

Sto provando a scrivere una soluzione per AdventCode il giorno 6 in Prolog. (http://adventofcode.com/day/6)

In precedenza ho scritto una soluzione che creava dinamicamente e sostituiva i predicati, per tenere traccia delle luci. Non sorprende che sia piuttosto lento, così ho deciso di provare a scriverlo usando uno stile più "funzionale"; Creare una lista contenente tutte le luci, quindi manipolare quella lista.

Sto provando a costruire la lista iniziale, che consisterebbe di un milione di elementi, ognuno un termine light(X, Y, Status). Ho pensato di iniziare con una lista [light(0, 0, off)], quindi anteporre nuovi termini ad essa. Per fare ciò, osservo il primo elemento dell'elenco, quindi determina quale dovrebbe essere il prossimo elemento, quindi anteponilo. Ripetere.

Ho un predicato next_light/2 che prende una luce e determina quale dovrebbe essere la luce successiva (da anteporre). Se non più luci devono essere aggiunti, restituisce done:

next_light(light(X, Y, _), NextLight) :- 
    X < 999, 
    NextX is X + 1, 
    NextLight = light(NextX, Y, off). 
next_light(light(999, Y, _), NextLight) :- 
    Y < 999, 
    NextY is Y + 1, 
    NextLight = light(0, NextY, off). 
next_light(light(999, 999, _), done). 

Poi ho tentativo di costruire la lista con questo codice:

init_lights(Lights) :- 
    gen_lights([light(0, 0, off)], Lights). 

gen_lights(Lights, AllLights) :- 
    [Light|_] = Lights, 
    next_light(Light, NextLight), 
    add_light(Lights, NextLight, AllLights). 

add_light(Lights, done, Lights). 
add_light(Lights, NextLight, AllLights) :- 
    gen_lights([NextLight|Lights], AllLights). 

Tuttavia, quando corro init_lights(L) in SWI-Prolog, I ottieni "ERRORE: Fuori dallo stack locale". Quindi c'è un overflow dello stack, ma quando guardo il codice, sembra coda ricorsiva per me. add_light e gen_lights sono reciprocamente ricorsivi; non sono sicuro se questo è un problema.

Ho provato a ispezionare le chiamate con il debugger, ma a quanto pare SWI-Prolog disabilita l'ottimizzazione delle chiamate tail quando si utilizza trace, quindi non è stato d'aiuto.

(Per la cronaca, quando ho cambiato il codice per utilizzare 3 anziché 999 come la coordinata massima, init_lights(L) sembrava produrre l'elenco corretto, e non appendere o causare un overflow dello stack.)

I probabilmente sto trascurando qualcosa, ma non lo vedo. Qualche consiglio benvenuto!^_^

Answer 1

Vi sono molto vicino alla soluzione: Il tuo clausole sono coda ricorsiva, ma l'ottimizzazione ricorsione di coda aiuta solo se il codice è deterministico! Nel codice, next_light/2 lascia i punti di scelta perché il compilatore non può stabilire quali casi si escludono a vicenda, quindi i frame non possono essere recuperati dopo la chiamata ricorsiva di coda.

È possibile migliorare il determinismo in diversi modi. Il modo più brutto e più incline agli errori è aggiungere   !/0 in alcuni punti strategici: fai attenzione, perché questo distruggerà molte proprietà dichiarative del tuo codice.

Leggermente migliore, ma anche quasi sempre dichiaratamente errato, è utilizzare funzioni come if-then-else.

Un modo più sicuro e più generale è utilizzare funzionalità come zcompare/3 con i vincoli clpfd.