Is this doing TCO, and if so how?

Help!
2

I have been told (by Jan himself) that I can check if tail-call optimization is performed by using prolog_current_frame/1. If it is the same in consecutive calls, then it is indeed optimized.

Like this:

double([], []).
double([H|T], [HOut|TOut]) :-
    prolog_current_frame(Frame),
    format("~w~n", [Frame]),
    HOut is 2 * H,
    double(T, TOut).

And when you run it:

?- double([1,2,3,4], R).
168
168
168
168
R = [2, 4, 6, 8].

I admit this is a functional readout but the good thing about it is that I don’t need to understand the mechanism in order to make a meaningful conclusion.

Here starts the part where I say a lot of stupid things and someone corrects me. I will attempt an explanation that does not involve looking at byte code or the VM:

As you go deeper in the recursion, you are progressively unifying a free variable (the tail of the list in the second argument) with a new list with one element and a free variable as a tail. The algorithm itself only needs to hold on to that free variable, so it is “constant space” (but creates a data structure that grows).

This is identical to having to hold on to only the last element in a linked list if you want to copy it to another one.

4 Likes