10

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.

1

2 Answers 2

11

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.

2
  • Thanks for the great answer. But I am afraid I did not fully get what you mean by "pull ...". Would you please elaborate a bit?
    – day
    Commented Jul 5, 2013 at 21:58
  • 1
    For example, in lisp_append/3 you can exchange the last two goals and obtain a tail recursive predicate. Going further, you can even pull the unification into the clause head, which is the most natural way to write this in Prolog, and which is what you wrote from the start. You cannot exchange the order of these calls in functional languages because they cannot reason over partially instantiated results like a list [X|Zs0], where Zs0 is not yet known. It is a rather irritating property of functional languages that such basic a function as append is not naturally tail recursive.
    – mat
    Commented Jul 6, 2013 at 0:51
-1

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.

1
  • 1
    What?! Your answer is flawed. Look at above answer by @mat for details.
    – repeat
    Commented Aug 13, 2015 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.