Menu
I am trying to write a solution for AdventCode day 6 in Prolog. (http://adventofcode.com/day/6)
Previously I wrote a solution that dynamically created and replaced predicates, to keep track of the lights. Unsurprisingly, it's rather slow, so I decided to try and write it using a more "functional" style; i.e. create a list containing all the lights, then manipulate that list.
I am trying to construct the initial list, which would consist of a million elements, each a term light(X, Y, Status). I figured I'd start with a list [light(0, 0, off)], then prepend new terms to it. To do this, I look at the first element of the list, then determine what the next element should be, then prepend that. Repeat.
I have a predicate next_light/2 which takes a light and determines what the next light (to be prepended) should be. If no more lights need to be added, it returns 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).
Then I attempt to construct the list with this code:
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).
However, when I run init_lights(L) in SWI-Prolog, I get "ERROR: Out of local stack". So there's a stack overflow, but when I look at the code, it looks tail recursive to me. add_light and gen_lights are mutually recursive; not sure if that is a problem.
I tried inspecting the calls with the debugger, but apparently SWI-Prolog turns off tail call optimization when using trace, so that was no help.
(For the record, when I changed the code to use 3 rather than 999 as the maximum coordinate, init_lights(L) seemed to produce the correct list, and didn't hang or cause a stack overflow.)
I'm probably overlooking something, but I am not seeing it. Any tips welcome! ^_^
294
An easy way to tell if a recursive function is a tail recursive is if it returns a concrete value in the base case. Meaning that it doesn't return 1 or true or anything like that. It will more than likely return some variant of one of the method parameters.
Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call. For example the following C++ function print() is tail recursive.
Tail recursion is a type of recursive function when the last thing executed is a recursive call. It doesn't mean much, I know. But simplified, it is a more optimized recursion. So to explain it better, I am going back to the example above.
A tail recursive method is one way to specify an iterative process.
You are very close to the solution: Your clauses are tail recursive, but tail recursion optimisation only helps if the code is deterministic! In your code, next_light/2 leaves choice-points because the compiler cannot tell which cases are mutually exclusive, so the frames cannot be reclaimed after the tail recursive call.
You can improve the determinism in several ways. The ugliest and most error-prone way is to add !/0 in some strategic places: Be careful with this, because this will destroy many nice declarative properties of your code.
Slightly better, but also almost always declaratively wrong, is to use features like if-then-else.
A safer and more general way is to use features like zcompare/3 with clpfd constraints.
70
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
