Is the `append` predicate tail-recursive?
logic-programming, prolog
Solution
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.
Problem
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.