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, 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, 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, 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, this would not work.