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.