Tail recursion but stack runs out

General
1

Sorry for spamming new topics )
I have predicate which is tail-recursive. Each non-termination clause ends strictly with recursion call. Nevertheless, I run out of stack when this predicate runs for several thousands cycles deep into recursion. What can cause this effect? I suspect that there is some rogue nondeterminism, because exception message says there 100+k choicepoints created. Does nondeterminism prevent tail recursion optimization?

4

If you’re at the top level where there are more choices, if you enter “*”, you can see the last choicepoint (entering “;” will get you the next solution…

For more help in detecting non-determinism: SWI-Prolog -- Manual
Also, if you’re tracing or at an error prompt, you can find out things such as choicepoints: SWI-Prolog -- Manual

1 Like
5

Yes, it is the choice point that prevents tail call optimization and this fills up the stack. I made a test:

state(S0) :-
    transition(S0, S1),
    (   S1 rem 1_000_000 =:= 0
    ->  prolog_current_frame(Frame),
        format(user_error, "step ~d frame ~d~n", [S1, Frame])
    ;   true
    ),
    state(S1).

transition(S0, S1) :-
    (   S1 is S0 + 1
    ;   fail
    ).

I used here the same instrumentation as described in this thread to see if tail recursion optimization is actually happening: if the recursive calls are in the same “frame”, then the optimization was in fact done.

Sorry about using printing instead of the debugger… just easier to share the result:

?- state(1).
step 1000000 frame 31000112
step 2000000 frame 62000112
step 3000000 frame 93000112
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.8Gb, global: 0.1Gb, trail: 27.9Mb
ERROR:   Stack depth: 3,659,450, last-call: 0%, Choice points: 3,659,442
ERROR:   Possible non-terminating recursion:
ERROR:     [3,659,448] user:state(3659439)
ERROR:     [3,659,447] user:state(3659438)

If you now remove the ; fail from there, it will go on forever:

state(S0) :-
    transition(S0, S1),
    (   S1 rem 1_000_000 =:= 0
    ->  prolog_current_frame(Frame),
        format(user_error, "step ~d frame ~d~n", [S1, Frame])
    ;   true
    ),
    state(S1).

transition(S0, S1) :-
    (   S1 is S0 + 1
    %;   fail
    ).

You should run it, it goes much faster, too:

?- state(1).
step 1000000 frame 174
step 2000000 frame 174
step 3000000 frame 174
step 4000000 frame 174
step 5000000 frame 174
step 6000000 frame 174
step 7000000 frame 174
step 8000000 frame 174
step 9000000 frame 174
step 10000000 frame 174
step 11000000 frame 174
step 12000000 frame 174
^CAction (h for help) ? abort
% Execution Aborted
7

Hmm… I still don’t get it.

I thought I did, this was the first version of the code, with the ; fail in it. I am also not quite getting it, what would garbage collection matter? Without actually reading the compiler and VM code I would assume that as long as a choice point remains open, something will have to be left somewhere, and will eventually fill up. What am I missing?

What is interesting is that in this particular case, we (the readers of the program) can tell that the choice point is not a real one, it is just a ; fail. This is another thing I don’t quite understand: would it be allowed to discard this choice point and still have a “Prolog”?

10

Well, it was really call to non-deterministic predicate that saturated the stack. I’ve found it, wrapped it into once and the problem was gone - tail recursion stopped generating stack frames.