Indexing

The indexation mechanism restricts the set of clauses to be tried in a procedure by using information about the status of the instantiated arguments of the goal.

The indexation mechanism restricts the set of clauses to be tried in a procedure by using information about the status of the instantiated arguments of the goal.

These arguments are then used as a key, selecting a restricted set of a clauses from all the clauses forming the procedure

As an example, the two clauses for concatenate:

concatenate([],L,L).
concatenate([H|T],A,[H|NT]) :- concatenate(T,A,NT).

If the first argument for the goal is a list, then only the second clause is of interest If the first argument is the nil atom, the system needs to look only for the first clause The indexation generates instructions that test the value of the first argument, and then proceed to a selected clause, or group of clauses

Note that if the first argument was a free variable, then both clauses should be tried In general, indexation will not be useful if the first argument is a free variable

When activating a predicate, a Prolog system needs to store state information This information, stored in a structure known as choice point or fail point, is necessary when backtracking to other clauses for the predicate The operations of creating and using a choice point are very expensive, both in the terms of space used and time spent Creating a choice point is not necessary if there is only a clause for the predicate as there are no clauses to backtrack to With indexation, this situation is extended: in the example, if the first argument was the atom nil, then only one clause would really be of interest, and it is pointless to create a choice point This feature is even more useful if the first argument is a list: without indexation, execution would try the first clause, creating a choice point The clause would fail, the choice point would then be used to restore the previous state of the computation and the second clause would be tried The code generated by the indexation mechanism would behave much more efficiently: it would test the first argument and see whether it is a list, and then proceed directly to the second clause

An important side effect concerns the use of "cut" In the above example, some programmers would use a "cut" in the first clause just to inform the system that the predicate is not backtrackable and force the removal the choice point just created As a result, less space is needed but with a great loss in expressive power: the "cut" would prevent some uses of the procedure, like generating lists through backtracking Of course, with indexation the "cut" becomes useless: the choice point is not even created

Indexation is also very important for predicates with a large number of clauses that are used like tables:

logician(aristoteles,greek).
logician(frege,german).
logician(russel,english).
logician(godel,german).
logician(whitehead,english).

An interpreter like C-Prolog, trying to answer the query:

?- logician(godel,X).

would blindly follow the standard Prolog strategy, trying first the first clause, then the second, the third and finally finding the relevant clause Also, as there are some more clauses after the important one, a choice point has to be created, even if we know the next clauses will certainly fail A "cut" would be needed to prevent some possible uses for the procedure, like generating all logicians In this situation, the indexing mechanism generates instructions that implement a search table In this table, the value of the first argument would be used as a key for fast search of possibly matching clauses For the query of the last example, the result of the search would be just the fourth clause, and again there would be no need for a choice point

If the first argument is a complex term, indexation will select clauses just by testing its main functor However, there is an important exception: if the first argument of a clause is a list, the algorithm also uses the list's head if not a variable For instance, with the following clauses,

rules([],B,B).
rules([n(N)|T],I,O) :- rules_for_noun(N,I,N), rules(T,N,O).
rules([v(V)|T],I,O) :- rules_for_verb(V,I,N), rules(T,N,O).
rules([q(Q)|T],I,O) :- rules_for_qualifier(Q,I,N), rules(T,N,O).

if the first argument of the goal is a list, its head will be tested, and only the clauses matching it will be tried during execution

Some advice on how to take a good advantage of this mechanism:

• Try to make the first argument an input argument
• Try to keep together all clauses whose first argument is not a variable, that will decrease the number of tests since the other clauses are always tried
• Try to avoid predicates having a lot of clauses with the same key For instance, the procedure:

type(n(mary),person).
type(n(john), person).
type(n(chair),object).
type(v(eat),active).
type(v(rest),passive).

becomes more efficient with:

type(n(N),T) :- type_of_noun(N,T).
type(v(V),T) :- type_of_verb(V,T).
 
type_of_noun(mary,person).
type_of_noun(john,person).
type_of_noun(chair,object).
 
type_of_verb(eat,active).
type_of_verb(rest,passive).