Search code examples
prologlogic-programming

Is the `append` predicate tail-recursive?

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.

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.