Clause Indexing

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:

First Argument Indexing: When the defined predicate is called with a non-variable first argument then the functor of this argument is used in a hash table lookup to find a smaller set of clauses for scanning.

Non-First Argument Indexing: If the first argument is a variable then the calling goal is searched for another argument which is non-variable and the functor of this argument is then picked for a hash table lookup.

Multi-Argument Indexing: The hash table does not point to clause sets but to further hash tables so that recursively after a found non-variable argument further non-variable arguments can be searched in the calling goal.

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.

Clause Indexing

Kommentare

Herunterladen