Is the `append` predicate tail-recursive?

Question

A typical code example of list processing in Prolog is append:

append([], Ys, Ys).
append([X | Xs], Ys, [X | Zs]) :- append(Xs, Ys, Zs).

My question is whether this program is tail recursive or not. I guess not from my experience in functional languages. However, I find it more difficult to judge for Prolog programs. It seems to we have to take unification into consideration.

Answer 1

Yes, your (and hence the Prolog "standard" version of) append/3 is tail-recursive. You can see this easily because the final goal is a call to append/3 itself. Notice that a typical implementation of append in functional languages is not tail recursive, because the final call is an operation equivalent to cons in Lisp, corresponding for example to:

lisp_append([], Ys, Ys).
lisp_append([X|Xs], Ys, Zs) :-
        lisp_append(Xs, Ys, Zs0),
        Zs = [X|Zs0].

Example query, yielding a local stack overflow because tail call optimization cannot be applied:

?- length(Ls, 10_000_000), lisp_append(Ls, [], _).
ERROR: Out of local stack

Whereas your natural Prolog version of append/3 works:

?- length(Ls, 10_000_000), append(Ls, [], _).
Ls = [_G8, _G11, _G14, _G17, _G20, _G23, _G26, _G29, _G32|...].

Notice that more predicates are naturally tail recursive in Prolog than in functional languages, due to the power of unification which lets you pull the description of partial results before a tail call. +1 for a good question.

Answer 2

No, your code is NOT tail-recursive. Tail-recursive means that at the bottom of the recursion you get the answer that you ask for at the beginning directly.

If you trace your code, for exampleappend([1,2,3],[a,b,c],Out), your get:

Call:append([1, 2, 3], [a, b, c], _G4702)
Call:append([2, 3], [a, b, c], _G4756)
Call:append([3], [a, b, c], _G4759)
Call:append([], [a, b, c], _G4762)
Exit:append([], [a, b, c], [a, b, c])
Exit:append([3], [a, b, c], [3, a, b, c])
Exit:append([2, 3], [a, b, c], [2, 3, a, b, c])
Exit:append([1, 2, 3], [a, b, c], [1, 2, 3, a, b, c])

The values of the variables(_G4762,_G4759,_G4756) are passed up to _G4702, and _G4702 is the answer.

We may have a tail-recursive version of append:

ap_tail_r([H|T],B,Ac,Out):-
   ap_tail_r(T,B,[H|Ac],Out).

ap_tail_r([],B,[H|Ac],Out):-
   ap_tail_r([],[H|B],Ac,Out).

ap_tail_r([],Out,[],Out).

Let trace again ap_tail_r([1,2,3],[a,b,c],[],Out):

Call:ap_tail_r([1, 2, 3], [a, b, c], [], _G4786)
Call:ap_tail_r([2, 3], [a, b, c], [1], _G4786)
Call:ap_tail_r([3], [a, b, c], [2, 1], _G4786)
Call:ap_tail_r([], [a, b, c], [3, 2, 1], _G4786)
Call:ap_tail_r([], [3, a, b, c], [2, 1], _G4786)
Call:ap_tail_r([], [2, 3, a, b, c], [1], _G4786)
Call:ap_tail_r([], [1, 2, 3, a, b, c], [], _G4786)
Exit:ap_tail_r([], [1, 2, 3, a, b, c], [], [1, 2, 3, a, b, c])
Exit:ap_tail_r([], [2, 3, a, b, c], [1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([], [3, a, b, c], [2, 1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([], [a, b, c], [3, 2, 1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([3], [a, b, c], [2, 1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([2, 3], [a, b, c], [1], [1, 2, 3, a, b, c])
Exit:ap_tail_r([1, 2, 3], [a, b, c], [], [1, 2, 3, a, b, c])

The only variable that we are keeping tract of is _G4786, which is the answer that we look for at the first place.

What exactly the tail-recursive code does is: a. reverse the first part, b. put the reversed first part to the second part head by head, c. when the reserved first part is empty, the updated second part is the appended result.