Menu
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.
779
Since the tail (recursive) call is the last thing done, the stack frame can be reused in the recursive call, making the recursion, for all intents and purposes, a loop, by simply jumping to the beginning of the predicate/function/method/subroutine. Thus, a tail recursive predicate will not overflow the stack.
What is tail recursion? A recursive function is tail recursive when a recursive call is the last thing executed by the function. For example the following C++ function print() is tail recursive.
The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use (See this for more details). Can a non-tail recursive function be written as tail-recursive to optimize it?
It is a non-tail-recursive function. Although it looks like a tail recursive at first look. If we take a closer look, we can see that the value returned by fact (n-1) is used in fact (n), so the call to fact (n-1) is not the last thing done by fact (n) The above function can be written as a tail recursive function.
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.
166
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
