9.5.3 Determinacy Detection

The other advantage of indexing is that it often makes possible early detection of determinacy, even if cuts are not included in the program. For example, consider the following simple predicate, which joins two lists together:

concat([], L, L).
concat([X|L1], L2, [X|L3]) :- concat(L1, L2, L3).

If this predicate is called with an instantiated first argument, then the first argument indexing of SICStus Prolog will recognize that the call is determinate—only one of the two clauses for concat/3 can possibly apply. Thus, the Prolog system knows it does not have to store backtracking information for the call. This significantly reduces memory use and execution time.

Determinacy detection can also reduce the number of cuts in predicates. In the above example, if there was no indexing, then a cut would not strictly be needed in the first clause as long as the predicate was always to be called with the first argument instantiated. If the first clause matched, then the second clause could not possibly match; discovery of this fact, however, would be postponed until backtracking. The programmer might thus be tempted to use a cut in the first clause to signal determinacy and recover space for backtracking information as early as possible.

With indexing, if the example predicate is always called with its first argument instantiated, then backtracking information is never stored. This gives substantial performance improvements over using a cut rather than indexing to force determinacy. At the same time greater flexibility is maintained: the predicate can now be used in a nondeterminate fashion as well, as in

| ?- concat(L1, L2, [a,b,c,d]).

which will generate on backtracking all the possible partitions of the list [a,b,c,d] on backtracking. If a cut had been used in the first clause, then this would not work.

For interpreted code, but not for compiled code, a filtering similar to indexing is done for all argument positions. The primary benefit of this filtering is that it makes it possible to detect determinacy in more cases. This filtering is currently not using hashing techniques, so it is not as performant as the first argument indexing.

We may improve indexing and other filtering techniques in future releases, which may decrease the number of choicepoints created.