Node:Last Clause Determinacy Detection, Next:, Previous:Indexing, Up:Writing Efficient Programs



Last Clause Determinacy Detection

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.