Is this code tail-recursive?

Question

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! ^_^

mat mat · Accepted Answer · 2015-12-25T21:07:08

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.

Is this code tail-recursive?

1 Answers