Re: [eclipse-clp-users] Tail recursion in eclipse?

Hi Martin,

Martin Wegner wrote:
> Hi,
> 
> does the eclipse compiler support and optimize tail recursion?

This is actually a fairly fundamental question about Prolog 
implementations, and indeed about how to use Prolog effectively. A full 
explanation is beyond the scope of this mailing list, but you should 
find discussion of last call optimisation in any Prolog text books.

The short answer is: yes, with some restrictions. ECLiPSe (as well as 
most other non-interpreter based Prolog systems) implements a 
generalised form of tail-recursion optimisation called `last call 
optimisation', where the system will try to reuse the space occupied by 
the environment (stack frame) of the parent goal when the last body goal 
in the predicate is executed. However, there are restrictions, because 
you cannot reuse the parent environment if you can backtrack into the 
other body goals. The ECliPSe abtract machine is able to detect if there 
are any choicepoints between the parent and the last call when the call 
is made, and the environment is reused if there are no such choicepoints.

To use your example:

> randomGame(CurrentState, CurrentState, ActionPathsTemp, ActionPathsTemp)
> :- terminal_State(CurrentState).
> 
> randomGame(CurrentState, TerminalState, ActionPaths, ActionPathsTemp) :-
>                  findall(Move, random_Move(CurrentState, _Role, Move),
> Moves),
>                  nextState(CurrentState, Moves, NextState),
>                  randomGame(NextState, TerminalState, ActionPaths,
> [Moves|ActionPathsTemp]).
> 

When tail-recursive randomGame/4 is called, the parent randomGame/4's 
environment can be resued if your call to nextState/3 does not produce 
any choicepoints that are still arond when the call is made. If you 
intend that nextState/3 to be non-determinate, i.e. it can produce 
multiple answers, then there would be no reuse.

On the other hand, if you did not intend nextState/3 to be determinate, 
then reuse of the environment depends on how nextState/3 was written, 
and on how smart the ECLiPSe compiler is -- the compiler should be smart 
enough to figure out most cases of determinacy and not allocate 
choicepoints, but you may have to add a cut before the last randomGame/3 
call, i.e.

                   nextState(CurrentState, Moves, NextState),
                   !,
                   randomGame(NextState, TerminalState, ActionPaths,

but this should be avoided if possible.

Another point is that if you create complex data structures such as 
compound terms, then the spaces for these are not allocated in the 
environment, but on the `global stack', and this space is not 
recoverable by last call optimisation (it will only be recovered on 
backtracking or via garbage collection, if it is no longer used).

Cheers,

Kish


-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.