Ich versuche eine Lösung für AdventCode Tag 6 in Prolog zu schreiben. ( Ссылка )
Zuvor habe ich eine Lösung geschrieben, die Prädikate dynamisch erstellt und ersetzt, um die Lichter im Auge zu behalten. Es ist nicht überraschend, dass es ziemlich langsam ist, also entschied ich mich, es zu versuchen und es mit einem "funktionaleren" Stil zu schreiben; h., erstellen Sie eine Liste mit allen Lichtern und manipulieren Sie diese Liste.
Ich versuche, die anfängliche Liste zu erstellen, die aus einer Million Elementen bestehen würde, jeder ein Begriff light(X, Y, Status) . Ich dachte mir, ich würde mit einer Liste [light(0, 0, off)] beginnen und dann neue Begriffe hinzufügen. 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 , das ein Licht nimmt und bestimmt, was das nächste Licht (das vorangestellt wird) sein sollte. Wenn keine weiteren Lichter hinzugefügt werden müssen, wird done :
Dann versuche ich, die Liste mit diesem Code zu erstellen:
%Vor% Wenn ich jedoch init_lights(L) in SWI-Prolog starte, bekomme ich "ERROR: Out of local stack". 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 inspizieren, aber anscheinend deaktiviert SWI-Prolog die Tail-Call-Optimierung, wenn trace verwendet wird, also war das keine Hilfe.
(Für den Datensatz, als ich den Code so änderte, dass er 3 anstatt 999 als maximale Koordinate verwendete, schien init_lights(L) die korrekte Liste zu erzeugen und blieb nicht hängen oder verursachte einen Stapelüberlauf.)
Ich übersehe wahrscheinlich etwas, aber ich sehe es nicht. Irgendwelche Tipps willkommen! ^ _ ^
Sie sind der Lösung sehr nahe: Ihre Klauseln sind tail rekursiv, aber die Tail Recursion-Optimierung hilft nur, wenn der Code deterministisch ist! In Ihrem Code gibt next_light/2 Auswahlpunkte zurück, weil der Compiler nicht erkennen kann, welche Fälle sich gegenseitig ausschließen, sodass die Frames nach dem rekursiven Tail-Aufruf nicht zurückgenommen werden können.
Sie können den Determinismus auf verschiedene Arten verbessern. Der hässlichste und fehleranfälligste Weg ist das Hinzufügen von !/0 an einigen strategischen Orten: Seien Sie vorsichtig damit, da dies viele nette deklarative Eigenschaften Ihres Codes zerstören wird.
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 Features wie zcompare/3 mit clpfd Einschränkungen.
Tags und Links prolog tail-recursion