Ist dieser Code tail-rekursiv?

Question

Ich versuche eine Lösung für AdventCode Tag 6 in Prolog zu schreiben. (http://adventofcode.com/day/6)

Zuvor schrieb ich eine Lösung, die Prädikate dynamisch erstellt und ersetzt, um die Lichter zu verfolgen. Es ist nicht überraschend, dass es ziemlich langsam ist, also entschied ich mich, es zu versuchen und es mit einem "funktionaleren" Stil zu schreiben; d. h. erstellen Sie eine Liste mit allen Lichtern und manipulieren Sie diese Liste.

Ich versuche, die erste Liste zu konstruieren, die aus einer Million Elemente bestehen würde, jeder ein Begriff light(X, Y, Status). Ich dachte mir, ich würde mit einer Liste beginnen [light(0, 0, off)], dann neue Begriffe vor. Um dies zu tun, schaue ich auf das erste Element der Liste, dann bestimme, was das nächste Element sein soll, und dann das vor. Wiederholen.

Ich habe ein Prädikat next_light/2, die ein Licht nimmt und bestimmt, was das nächste Licht (zu sein) sollte sein. Wenn keine weiteren Lichter hinzugefügt werden müssen, gibt es 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). 

Dann versuche ich die Liste mit diesem Code zu konstruieren:

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

Allerdings, wenn ich init_lights(L) in SWI-Prolog laufen, ich Erhalte "FEHLER: Außerhalb des lokalen Stapels". Es gibt also einen Stack-Überlauf, aber wenn ich mir den Code anschaue, sieht er für mich rekursiv aus. add_light und gen_lights sind gegenseitig rekursiv; nicht sicher, ob das ein Problem ist.

Ich habe versucht, die Aufrufe mit dem Debugger zu überprüfen, aber anscheinend SWI-Prolog schaltet die Tail-Call-Optimierung bei der Verwendung trace, so dass keine Hilfe war.

(Für das Protokoll, wenn ich den Code geändert 3 zu verwenden, anstatt 999 als die maximale Koordinate, init_lights(L) schien die richtige Liste zu produzieren, und nicht einen Stapelüberlauf hängen oder verursachen.)

I Ich übersehe wahrscheinlich etwas, aber ich sehe es nicht. Irgendwelche Tipps willkommen!^_^

Answer 1

Sie sind sehr nah an der Lösung: Ihre Klauseln sind Schwanz rekursiv, aber Endrekursion Optimierung nur hilft, wenn der Code deter ist! In Ihrem Code gibt next_light/2 Auswahlpunkte zurück, da der Compiler nicht unterscheiden kann, welche Fälle sich gegenseitig ausschließen. Daher können die Frames nach dem rekursiven Tail-Aufruf nicht zurückgenommen werden.

Sie können den Determinismus auf verschiedene Arten verbessern. Der hässlichste und fehleranfälligste Weg ist es, an einigen strategischen Stellen   !/0 hinzuzufügen: Seien Sie vorsichtig damit, denn dadurch werden viele nette deklarative Eigenschaften Ihres Codes zerstört.

Etwas besser, aber auch fast immer deklarativ falsch, ist die Verwendung von Features wie if-then-else.

Eine sicherere und allgemeinere Methode ist die Verwendung von Funktionen wie zcompare/3 mit clpfd Einschränkungen.