If all arguments in a query or a calling predicate are variables, then there is clearly no better way to proceed other than in the above way. On the other hand, when some of the arguments are at least partially instantiated, that information can be used to skip all (or at least some of) those clauses that do not fit these arguments. In analogy to databases, techniques to achieve this are summarized as ``indexing'' techniques.
The main difference between database and PROLOG indexing is that the former handles a set of items while the latter deals with a (textually ordered) sequence of items (since PROLOG clauses are tried from top to bottom).
The standard PROLOG indexing method described in [War83], [GLLO85], and [AK90] uses the first argument of each procedure for indexing.
In the less example, the first clause has to be tried only if the first argument is the constant 0 or a free variable. Analogously, the second clause has only to be tried if the first argument is a unary structure with functor s or is a free variable.
The WAM instruction set must therefore include an instruction to determine the type of an argument. This instruction is called switch_on_term. It takes as many arguments as there are types in PROLOG (e.g. constants, structures, lists, and empty lists) plus one argument for free variables:
switch_on_term Const, Struct, List, Nil, Var.
All these arguments are labels to jump at if the first procedure argument has the corresponding type.
In case of constants and structures, the constants and the functors can also be used for indexing, thus two more switching instructions are used: switch_on_constant N, T and switch_on_structure N, T where T is a hash table of size N containing entries of the form constant:label or structure/arity:label. Actual constants and structures not appearing in the hash table lead to failure.
Replacing the try instructions by these switching instructions in the less example, the following WAM assembler code results:
less/2
switch_on_term const, struct, fail, fail, var
const % X1 must here be *some* constant
switch_on_constant 1, {0:1} % jump to clause 1 if X1 = 0
struct % X1 must here be *some* structure
switch_on_structure 1, {s/1:2} % jump to clause 2 if X1 = s(...)
% else fail
var % jump to both clauses if X1 is a free variable:
try 1 % first try clause with label 1,
trust 2 % then the clause with label 2
1 get_constant 0, X1
proceed
2 allocate 0
get_structure s/1, X1 % less(s(
unify_variable X3 % M),
get_structure s/1, X2 % s(
unify_variable X4 % N)) :-
put_value X3, X1 %
put_value X4, X2
call less/2, 0 % less(M, N).
deallocate
proceed
Hassan At-Kaci in [AK90] called this the three-level-indexing scheme:
If the first argument of a procedure contains variables, one has to divide
the procedure into several ``blocks'' or ``partitions''
, i.e. maximal
three-level-indexable subportions of a procedure either having a variable as
the first argument (one-clause blocks) or not (general blocks).
The following procedure has to be split into four blocks:
f(1,a). % block 1 f(2,b). f(X,X). % block 2 f(X,d). % block 3 f(3,e). % block 4 f(4,f).
Blocks 1 and 4 can be compiled using the above described indexing instructions, blocks 2 and 3 are compiled straight forward. The four blocks are then glued together by the try, retry, and trust instructions:
f/2 try block1
retry block2
retry block3
trust block4
Together with the discrimination on name and arity, which can also be viewed as part of the indexing, we now have a five-level-indexing scheme:
