Should I avoid tail recursion in Prolog and in gen

问题:

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).

回答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.

回答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.

回答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

回答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.