recursividad - listas en prolog

¿Este código es recursivo?

Question

Intento escribir una solución para AdventCode día 6 en Prolog. ( http://adventofcode.com/day/6 )

Anteriormente escribí una solución que dinámicamente creaba y reemplazaba predicados, para realizar un seguimiento de las luces. Como era de esperar, es bastante lento, así que decidí probar y escribir usando un estilo más "funcional"; es decir, crea una lista que contenga todas las luces, luego manipula esa lista.

Estoy tratando de construir la lista inicial, que consistiría en un millón de elementos, cada uno un término light(X, Y, Status) . Pensé que comenzaría con una lista [light(0, 0, off)] , luego precederé nuevos términos a ella. Para hacer esto, miro el primer elemento de la lista, luego determino cuál debe ser el siguiente elemento, luego lo antepongo. Repetir.

Tengo un predicado next_light/2 que toma una luz y determina cuál debería ser la siguiente luz (que se debe anteponer). Si no se necesitan agregar más luces, vuelve 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).

Luego intento construir la lista con este código:

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

Sin embargo, cuando ejecuto init_lights(L) en SWI-Prolog, obtengo "ERROR: Fuera de la pila local". Entonces hay un desbordamiento de pila, pero cuando miro el código, me parece una cola recursiva. add_light y gen_lights son mutuamente recursivos; no estoy seguro si eso es un problema

Traté de inspeccionar las llamadas con el depurador, pero al parecer SWI-Prolog desactiva la optimización de la cola al usar trace , por lo que no fue de ayuda.

(Para el registro, cuando cambié el código para usar 3 en lugar de 999 como la coordenada máxima, init_lights(L) pareció producir la lista correcta, y no se bloqueó ni causó un desbordamiento de la pila).

Probablemente estoy pasando por alto algo, pero no lo estoy viendo. Cualquier consejo bienvenido! ^ _ ^

Answer 1

Estás muy cerca de la solución: tus cláusulas son recurrentes en la cola, ¡pero la optimización de la recursión de la cola solo ayuda si el código es determinista ! En su código, next_light/2 deja puntos de elección porque el compilador no puede decir qué casos son mutuamente exclusivos, por lo que los marcos no pueden recuperarse después de la llamada recursiva final.

Puedes mejorar el determinismo de varias maneras. La forma más fea y propensa a errores es agregar !/0 en algunos lugares estratégicos: tenga cuidado con esto, ya que esto destruirá muchas buenas propiedades declarativas de su código.

Un poco mejor, pero casi siempre declarativamente incorrecto, es usar funciones como if-then-else.

Una forma más segura y más general es usar funciones como zcompare/3 con restricciones clpfd .