Tail recursion but stack runs out

General
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