Next: The Determinacy Checker, Previous: Indexing, Up: Writing Efficient Programs [Contents][Index]
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.