Node:Determinacy Detection, Previous:Data Tables, Up:Indexing
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.