Even if the determinacy detection made possible by indexing (see
bas-eff-ind-det)
is unavailable to a predicate call, Quintus 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 Quintus 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 Quintus Prolog.