Node:Last Clause Determinacy Detection, Next:The Determinacy Checker, Previous:Indexing, Up:Writing Efficient Programs
Even if the determinacy detection made possible by indexing
is unavailable to a predicate call, SICStus Prolog still can detect
determinacy before determinate exit from the predicate. Space for
backtracking information can thus be recovered as early as possible,
reducing memory requirements and increasing performance. For
instance, the predicate member/2 (found in the SICStus Prolog library)
could be defined by:
member(Element, [Element|_]).
member(Element, [_|Rest]) :-
member(Element, Rest).
member/2 might be called with an instantiated first argument in
order to check for membership of the argument in a list, which is passed
as a second argument, as in
| ?- member(4, [1,2,3,4]).
The first arguments of both clauses of member/2 are variables, so
first argument indexing cannot be used. However, determinacy can still
be detected before determinate exit from the predicate. This is because
on entry to the last clause of a nondeterminate predicate, a call
becomes effectively determinate; it can tell that it has no more clauses
to backtrack to. Thus, backtracking information is no longer needed,
and its space can be reclaimed. In the example, each time a call fails
to match the first clause and backtracks to the second (last) clause,
backtracking information for the call is automatically deleted.
Because of last clause determinacy detection, a cut is never needed as the first subgoal in the last clause of a predicate. Backtracking information will have been deleted before a cut in the last clause is executed, so the cut will have no effect except to waste time.
Note that last clause determinacy detection is exploited by dynamic code as well as static code in SICStus Prolog.