The Jekejeke Prolog system is capable of dynamically creating
indexes for multiple argument positions and that might span
multiple arguments. We will describe in more detail the used
technique. The point of departure for clause indexing is a naïve
implementation of Prolog without any indexing. In this
implementation defined predicates are always scanned in full to
find a matching clause. Clause indexing now implements the
following indexes on the clause set of a predicate:
Older Prolog systems did first argument indexing. This indexing was done independent of the call pattern so that the index was already created during the consult of the clauses. Jekejeke Prolog follows a different strategy. When clauses are consulted no indexes are necessarily maintained. Only after a defined predicate has been first invoked and the arguments have been analysed indexes are created. Additional indexes might later be dynamically created when the predicate is called with new non-variable argument patterns.
To explain the optimization 1), 2) and 3) we can use the following example Prolog text. We will use a binary predicate for illustration but the clause indexing method has also been implemented for defined predicates for less or more arguments:
r(a, b).
r(a, c).
r(d, c).
r(d, e).
We have four facts. We will be able to see what clause sets are picked in that we can see whether a choice point is left for the last clause in the set or not. In the naïve implementation always the full clause set is picked. We can test this as follows:
?- set_prolog_flag(sys_clause_index, off).
Yes
?- r(a, X).
X = b ;
X = c ;
No
The set_prolog_flag/2 system predicate allows us to switch off clause indexing. When we invoke r(a, X) then we see that after the first and second solution the system will prompt. This indicates that choice points are still around since the full clause set is scanned. Now let’s run the example with clause indexing enabled. We can use the directive set_prolog_flag/2 to switch on clause indexing:
?- set_prolog_flag(sys_clause_index, on).
Yes
?- r(a, X).
X = b ;
X = c
As could be seen we don’t get a prompt anymore after the last
solution of r(a, X). Therefore the clause indexing provided us
with a smaller clause. This verifies the working of clause
indexing in situation 1).
To explain situation 2) we can use the following query:
?- set_prolog_flag(sys_clause_index, off).
Yes
?- r(X, c).
X = a ;
X = d ;
No
When we invoke r(X, c) then we see that after the first and second solution the system will prompt. This indicates that choice points are still around since the full clause set is scanned. Now let’s run the example with clause indexing enabled:
?- set_prolog_flag(sys_clause_index, on).
Yes
?- r(X, c).
X = a ;
X = d
As could be seen we don’t get a prompt anymore after the last
solution of r(a, X). Therefore the clause indexing provided us
with a smaller clause.
We can use the following query to finally explain situation 3):
?- set_prolog_flag(sys_clause_index, off).
Yes
?- r(a, c).
Yes ;
No
When we invoke r(a, c) then we see that after the success the system will prompt. This is an indicative that choice points are still around since the full clause set is scanned. Now let’s run the example with clause indexing enabled:
?- set_prolog_flag(sys_clause_index, on).
Yes
?- r(a, c).
Yes
As could be seen, after the success of r(a, c) we will did not get a prompt anymore.