Should I avoid tail recursion in Prolog and in general?

Question

I'm working through "Learn Prolog now" online book for fun.

I'm trying to write a predicate that goes through each member of a list and adds one to it, using accumulators. I have already done it easily without tail recursion.

addone([],[]).
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys).

But I have read that it is better to avoid this type of recursion for performance reasons. Is this true? Is it considered 'good practice' to use tail recursion always? Will it be worth the effort to use accumulators to get into a good habit?

I have tried to change this example into using accumulators, but it reverses the list. How can I avoid this?

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],A,A).
addone(List,Result) :- accAddOne(List,[],Result).

Gianna

addone is already fully tail-call-optimizable. It is tail recursive "modulo cons", and Prolog does have this optimization -- the new cons cell [Y|Ys] is allocated first with the two "holes" in it (two as yet uninstantiated logvars, Y and Ys), then Y is instantiated inside the rule's body (by is/2), and then the recursive call instantiates the logical variable Ys. There's thus no need to return from the recursive call into this rule's body. – Styles

LPN! Nowadays has a whole chapter on showing the difference through examples. To my knowledge Prolog is tail recursion optimized and therefore it is desirable because it effectively turns N steps into N/2 by not stepping back. LPN: learnprolognow.org/… Chapter 5.3, january 2018. – Malignant

IOW the first snippet is the best. Prolog is already the most excellent in producing / processing / building its lists in the top-down manner. the inferior languages force you to build the list in reverse, and then reverse it back, but that's because they are inferior. Top-down is the best. – Styles

Answer 1

Short answer: Tail recursion is desirable, but don't over-emphasize it.

Your original program is as tail recursive as you can get in Prolog. But there are more important issues: Correctness and termination.

In fact, many implementations are more than willing to sacrifice tail-recursiveness for other properties they consider more important. For example steadfastness.

But your attempted optimization has some point. At least from a historical perspective.

Back in the 1970s, the major AI language was LISP. And the corresponding definition would have been

(defun addone (xs)
  (cond ((null xs) nil)
    (t (cons (+ 1 (car xs))
         (addone (cdr xs))))))

which is not directly tail-recursive: The reason is the cons: In implementations of that time, its arguments were evaluated first, only then, the cons could be executed. So rewriting this as you have indicated (and reversing the resulting list) was a possible optimization technique.

In Prolog, however, you can create the cons prior to knowing the actual values, thanks to logic variables. So many programs that were not tail-recursive in LISP, translated to tail-recursive programs in Prolog.

The repercussions of this can still be found in many Prolog textbooks.

Literal

Answer 2

Your addOne procedure already is tail recursive.

There are no choice points between the head and the last recursive call, because is/2 is deterministic.

Accumulators are sometime added to allow tail recursion, the simpler example I can think of is reverse/2. Here is a naive reverse (nreverse/2), non tail recursive

nreverse([], []).
nreverse([X|Xs], R) :- nreverse(Xs, Rs), append(Rs, [X], R).

if we add an accumulator

reverse(L, R) :- reverse(L, [], R).
reverse([], R, R).
reverse([X|Xs], A, R) :- reverse(Xs, [X|A], R).

now reverse/3 is tail recursive: the recursive call is the last one, and no choice point is left.

Opportunism

Your advice on cut is not OK. Minimal counterexample: freeze(Ys,(true;true)), addone([0],Ys) should give two answers, not one as in your version with cut. – Literal

I appreciate your example, and removed my advice. To be true, I can't understand freeze' behaviour... – Opportunism

Simple rule-of-thumb: A cut that has general unification in its guard is almost always a red cut. So mostly only cuts with clean read-only tests are green. – Literal

Your cut is red due to freeze/2 or when/2 or similar constructs. Quite often (not in this example) such cuts are also red with clpfd. – Literal

@false: Of course it make sense (i saw some explanation here). I think (not really sure) I got the advice from Clocksin Mellish... – Opportunism

@Opportunism I think the first line of the accumulator part is going to fail because you try to unify reverse(L,R) with reverse(L,[],R). – Hyperbolism

Answer 3

O.P. said:

But I have read that it is better to avoid [tail] recursion for performance reasons. Is this true? Is it considered 'good practice' to use tail recursion always? Will it be worth the effort to use accumulators to get into a good habit?

It is a fairly straightforward optimization to convert a tail-recursive construct into iteration (a loop). 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. Tail-recursive construct, with the optimization applied have the following benefits:

• Slightly faster execution as new stack frames don't need to be allocated/freed; further, you get better locality of reference, so arguably less paging.
• No upper bound on the depth of recursion.
• No stack overflows.

The possible downsides?

• loss of useful stack trace. Not an issue if TRO is only applied in a release/optimized build and not in a debug build, but...
• developers will write code that depends on TRO, which means that code will run fine with TRO applied will fail without TRO being applied. Which means that in the above case (TRO only in release/optimized builds), a functional change exists between release and debug builds, essentially meaning one's choice of compiler options generates two different programs from identical source code.

This is not, of course, an issue, when the language standard demands tail recursion optimization.

To quote Wikipedia:

Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination, or tail call optimization.

See also:

• What Is Tail Call Optimization?
• The Portland Pattern Repository on the matter
• and even Microsoft's MSDN

I've never understood why more languages don't implement tail recursion optimization

Britain

The situation in Prolog is significantly more complex than in other languages due to logic variables and non-determinism. In fact it is the major source of complexity in Prolog machines: In the WAM it causes a very complex (and clever) variable classification scheme, which often results in implementations that leave out some part of it. The ZIP requires an expensive dynamic scan of the related variables and some overhead during GC. – Literal

Answer 4

I don't think that the first version of addone should lead to less efficient code. It is also a lot more readable, so I see no reason why it should be good practice to avoid it.

In more complex examples, the compiler might not be able to transfer the code automatically to tail recursion. Then it may be reasonable to rewrite it as an optimization, but only if it is really necessary.

So, how can you implement a working tail recursive version of addone? It may be cheating but assuming that reverse is implemented with tail-recursion (e.g., see here), then it can be used to fix your problem:

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],Acc,Result) :- reverse(Acc, Result).
addone(List,Result) :- accAddOne(List,[],Result).

It is extremly clumsy, though. :-)

By the way, I cannot find a simpler solution. It may because of the same reason as foldr in Haskell is normally not defined with tail recursion.

Undrape

+1 because only you noticed that accAddOne by the OP is wrong. – Tobit

@Tobit it is not wrong, the OP already says it produces the result in reverse. – Styles

the first version of addone should lead to the most efficient code. – Styles

Answer 5

In contrast to so some other programming languages, certain Prolog implementations are well suited for tail recursive programs. Tail recursion can be handled as a special case of last call optimization (LCO). For example this here in Java doesn't work:

public static boolean count(int n) {
    if (n == 0) {
        return true;
    } else {
        return count(n-1);
    }
}

public static void main(String[] args) {
    System.out.println("count(1000)="+count(1000));
    System.out.println("count(1000000)="+count(1000000));
}

The result will be:

count(1000)=true
Exception in thread "main" java.lang.StackOverflowError
    at protect.Count.count(Count.java:9)
    at protect.Count.count(Count.java:9)

On the other hand major Prolog implementations don't have any problem with it:

 ?- [user].
 count(0) :- !.
 count(N) :- M is N-1, count(M).
 ^D

The result will be:

?- count(1000).
true.
?- count(1000000).
true.

The reason Prolog systems can do that, is that their execution is most often anyway trampolin style, and last call optimization is then a matter of choice point elimination and environment trimming. Environment trimming was already documented in early WAM.

But yes, debugging might be a problem.

Adham