next up previous
Next: Useful Tip 4 Up: Efficiency Considerations Previous: Useful Tip 2

Useful Tip 3

Take advantage of tail recursion optimisation. This is a technique built into many Prolog systems which allows the space allocated to the head of a clause to be used for the last subgoal, provided that there is no chance of further results on backtracking by the time the last subgoal gets called. Consider, for example, the append/3 predicate:

append([H|T], L1, [H|L2]):-
    append(T, L1, L2).
append([], L, L).
For this predicate, if we are trying to satisfy a goal such as:
| ?- append([a,b], [c,d], X).
and have managed to match on the head of the first clause and are at the point of calling the last (and only) subgoal of that clause then we know that there would be no other ways of finding a solution (since there are no other subgoals within the clause and the 2nd clause wouldn't match to the goal). If the Prolog interpreter is smart enough to spot this, it can get rid of any choice points for the current goal (append([a,b], [c,d], X)) and replace it in memory with the outstanding subgoal (append([b], [c,d], X)). This means that a solution to the append/3 goal can be found using constant memory space, rather than requiring space which increases linearly with the depth of recursion. Of course, this all depends on the interpreter being able to recognise when tail recursion optimisation can be applied - a task which isn't always easy. The append/3 example, above, is comparatively simple but even it isn't straightforward. Suppose that the goal had been:
| ?- append(X, Y, [a,b]).
Then tail recursion optimisation wouldn't apply because the program isn't deterministic at the point where the subgoal of the 1st clause gets called. Some Prolog systems have fancy indexing systems which allow them to detect determinism quite effectively. However, there is one way in which you can make it clear to the Prolog interpreter that no choice points remain at the point where the last subgoal of a clause is about to be called....add a cut. For example, suppose we have the following program which is designed to gobble up space on the machine:
gobble_space:-
    gobble,
    gobble,
    gobble,
    gobble,
    gobble,
    gobble,
    gobble,
    gobble,
    statistics(local_stack, L), write(L), nl,
    gobble_space.
gobble_space.

gobble.
gobble:-
    gobble_space.
The behaviour of this predicate is as follows:
| ?-  gobble_space.
[380,16000]
[652,15728]
......SOME TIME LATER.....
[4190812,2468]
[4191084,2196]
{ERROR: Memory allocation failed}
{ Execution aborted }
i.e. It eats up a lot of space and eventually exceeds the limits of the system. Now let's try the same program but with a cut in the first clause of gobble_space/0 to permit tail recursion optimisation.
gobble_space:-
    gobble,
    gobble,
    gobble,
    gobble,
    gobble,
    gobble,
    gobble,
    gobble,
    statistics(local_stack, L), write(L), nl, !,
    gobble_space.
gobble_space.
The behaviour of this predicate is:
| ?- gobble_space.
[380,16000]
[380,16000]
......SOME TIME LATER.....
[380,16000]
[380,16000]
i.e. It doesn't eat up space and will continue to run indefinitely (or at least for a very long time).



next up previous
Next: Useful Tip 4 Up: Efficiency Considerations Previous: Useful Tip 2



Dave Stuart Robertson
Tue Jul 7 10:44:26 BST 1998