@(#)README	1.6 05 Oct 1993

Author: Tom Howland (derived from work by Anil Nair)

This software is free: please copy it and/or modify it. Do with it what
you like.  It is a gift from KnowledgeWare Inc.

The basic idea is that we want people to be able to write in their
programs

:- index <indexspecs>.

where

<indexspecs> --> <indexspec> ( [','] -> <argspecs> | [])
<indexspec> --> <pred> (<argspec>)
<argspecs> --> <argspec> ( [','] -> <argspecs> | [])
<argspec> --> [+] | [*] | [i] | [n] | [?]

You should use a '*' in an argument position if you wish to hash on that entire
term. If a '+' is used only 1 level of that term is used for hashing. An 'i' is used
if that argument is already an integer, and therefore need not be run through
"hash_term/2".

The argspec [n] is a pragmatic extension and can not be used in conjunction with the
other specifiers aside from [?]. It stands for "nonvar" and is not run through hash
term and thus can not be used in combination with others within a particular index
specification. It is often the fastest thing to use. For example, I found that all I
needed in one instance was

      :- index((db_section_type(n, ?), db_section_type(?, n))).

Here is an extended example:

---------
$ cat t.pl
:- module(t, [foo/4]).

:- load_files(indexer, [when(compile_time),if(changed)]).

:- index foo(+,?,*,i), foo(?,?,?,i).

foo(a,b,c(d),9).
foo(e,f,g(h),11) :- foo(a,b,c(d),9).
foo(_,z,_,_) :- baz.
$ prolog
Quintus Prolog Release 3.1.4 (Sun-4, SunOS 5.2)
Copyright (C) 1993, Quintus Corporation.  All rights reserved.
2100 Geng Road, Palo Alto, California U.S.A. (415) 813-3800

| ?- load_files(t,[all_dynamic(true)]).
% compiling file /home/tom/kwi/adw/kc/indexer/t.pl
%  compiling file /home/tom/kwi/adw/kc/indexer/indexer.pl
%   compiling file /home/tom/kwi/adw/kc/indexer/low.pl
%    loading file /opt/quintus/generic/qplib3.1.4/library/types.qof
%    types.qof loaded, 0.150 sec 2,812 bytes
%    module types imported into low
%   low.pl compiled, 1.717 sec 8,968 bytes
%   module low imported into indexer
%   loading file /opt/quintus/generic/qplib3.1.4/library/addportray.qof
%   addportray.qof loaded, 0.133 sec 3,564 bytes
%   module add_portray imported into indexer
%  indexer.pl compiled, 2.500 sec 15,380 bytes
%  module indexer imported into t
% t.pl compiled, 2.800 sec 18,432 bytes
% module t imported into user

yes
| ?- module(t).

yes
[t]
| ?- listing.

foo(A,B,C,D) :- 
        (   integer(D),
            ground(C),
            nonvar(A) ->
            hash_term(C,E),
            functor(A,F,G),
            hash_term(F,H),
            I is\(D,\(E,H)),
            '** foo/4 index 1 **'(I,J)
        ;   integer(D) ->
            '** foo/4 index 2 **'(D,J)
        ;   true
        ),
        '** foo/4 **'(J,A,B,C,D).

'** foo/4 **'(0,a,b,c(d),9).
'** foo/4 **'(1,e,f,g(h),11) :- 
        foo(a,b,c(d),9).
'** foo/4 **'(2,A,z,B,C) :- 
        baz.

'** foo/4 index 1 **'(165,0).
'** foo/4 index 1 **'(179,1).
'** foo/4 index 1 **'(A,2).

'** foo/4 index 2 **'(9,0).
'** foo/4 index 2 **'(11,1).
'** foo/4 index 2 **'(A,2).

yes
[t]
| ?- ^D

---------

The reason we use "load_files(t, [all_dynamic(true)])" is so that listing/0 will
work. Don't do this in your code: it defeats the whole purpose of compiling!

Usage Note: it is best to organize your indexes such that the best indexes are tryed
first. For example if one of your indexes maps into equivalance classes, whereas
another gives a one-to-one mapping, mention the one-to-one mapping first. Suppose
baz/3 is such that the one-to-one mapping occurs in the 3rd argument position, and
the equivalence class mapping occurs in the first, then we would say

	:- index baz(?,?,*), baz(*,?,?).

Given the above restrictions on baz/3, the first directive in

	:- index baz(?,*,*), baz(?,?,*), baz(*,?,?).

is pointless since the 3rd argument is already a perfect index.

You might notice that some of the indexes have a variable on the left-most argument
position. This is because some of the rules did not match the indexing specification
sufficiently. Indexing works best on rule heads that perfectly match the indexing
specification.  This is not a bug.

I would say that indexing works best on ground heads, but that is too
restrictive. Note that the index directive '+' only requires that the argument be
"nonvar". Further, there is no loss of performance if some of the non-indexed
arguments are not bound.

We hash each individual argument here and then xor them together.  The other way of
hashing would be to combine all the arguments which need to be hashed into a term
and doing one hash_term/2 on that term. But this would mean that we would be
building heap.  Peter Schachte of Quintus suggested the method used in this module
to Anil Nair, also of Quintus.  Anil Nair had an early draft of this. Tom Howland of
KnowledgeWare hacked Anil's copy very much, which is what we have here.

This library is an extension of the idea in "library(indexer)" to provide more
powerful indexing schemes for predicates in Quintus Prolog.  It is different from
"library(indexer)" in the following ways.

"library(indexer)" lets you pick different arguments to index on.  This library
provides different combinations of arguments to index on.  e.g. "library(indexer)"
can be used to index on the first or third argument of a procedure but this library
will let you index on the first and third argument or the second and the third
argument.

"library(indexer)" generates index tables of the form Nth_arg-1st_arg to index on
the Nth argument. This means that you could get redundant solutions. This package
adds an extra unique "clause number" argument to each fact to get around this.

"library(indexer)" can be used only for dynamic facts. This directory contains files
for static rules (indexer.pl), dynamic facts (dynamic_indexer.pl), and
module-partitioned dynamic facts (module_indexer.pl).

The following example listings were created with the simple command eek/1:

------------

eek(F) :-
    see(F),
    r,
    seen.

r :-
    read(X),
    (   X == end_of_file
    ->  true
    ;   expand_term(X, Y), portray_clauses(Y), r
    ).

portray_clauses([]).
portray_clauses([H|T]) :- !, portray_clauses(H), portray_clauses(T).
portray_clauses(X) :- nl, portray_clause(X).

------------

Here is an example of dynamic indexing:

------------

$ cat u.pl
:- module(u, [foo/4, kill_foo/4]).

:- load_files(dynamic_indexer, [when(compile_time),if(changed)]).
:- use_module(indexed).

:- dynamic_index foo(+,?,*,i), foo(?,?,?,i).

kill_foo(A, B, C, D) :- indexed_retract(foo(A,B,C,D)).

-----------
Expands to
-----------

:- module(u,[foo/4,kill_foo/4]).

:- load_files(dynamic_indexer,[when(compile_time),if(changed)]).

:- use_module(indexed).

:- dynamic
        '** foo/4 index 1 **'/2.

:- dynamic
        '** foo/4 index 2 **'/2.

:- dynamic
        '** foo/4 **'/7.

:- discontiguous
        '** indexed assert **'/1.

:- discontiguous
        '** indexed retract **'/1.

:- discontiguous
        '** indexed **'/1.

'** indexed **'(foo(A,B,C,D)).

foo(A,B,C,D) :- 
        '** hash foo/4 **'(A,B,C,D,E),
        '** foo/4 **'(E,A,B,C,D,F,G).

'** indexed assert **'(foo(A,B,C,D)) :- 
        (   retract('clause count foo/4'(E)) ->
            true
        ;   E is 0
        ),
        F is E+1,
        assert('clause count foo/4'(F)),
        hash_term(C,G),
        functor(A,H,I),
        hash_term(H,J),
        K is\(D,\(G,J)),
        assert('** foo/4 index 1 **'(K,E),L),
        assert('** foo/4 index 2 **'(D,E),M),
        assert('** foo/4 **'(E,A,B,C,D,L,M)).

'** indexed retract **'(foo(A,B,C,D)) :- 
        '** hash foo/4 **'(A,B,C,D,E),
        retract('** foo/4 **'(E,A,B,C,D,F,G)),
        erase(F),
        erase(G).

'** hash foo/4 **'(A,B,C,D,E) :- 
        (   integer(D),
            ground(C),
            nonvar(A) ->
            hash_term(C,F),
            functor(A,G,H),
            hash_term(G,I),
            J is\(D,\(F,I)),
            '** foo/4 index 1 **'(J,E)
        ;   integer(D) ->
            '** foo/4 index 2 **'(D,E)
        ;   true
        ).

kill_foo(A,B,C,D) :- 
        indexed_retract(foo(A,B,C,D)).

---------------

Retraction is optimized as much as possible. There is no look-up of the
indices. Once the indexed clause is retracted, each index to it is erased.

Future work: a limitation is that there is no facility for translating rules or
in-source definitions of foo/4. One work-around would be to supply and
initialization directive that calls indexed_assert/1 for each of the inline dynamic
facts. There is also no facility for dealing with dynamic rules.

The last example is for module indexing. The thing to notice about module indexing
is that it generates code just like dynamic indexing, but provides for partitioning
of the database by modules. This is done by generating a place for an additional
argument to the indexed predicate indicating the desired module.

----------

$ cat v.pl
:- module(v, [foo/5, kill_foo/5]).

:- load_files(module_indexer, [when(compile_time),if(changed)]).
:- use_module(indexed).

:- module_index foo(+,?,*,i), foo(?,?,?,i).

kill_foo(A, B, C, D, E) :- indexed_retract(foo(A,B,C,D,E)).
$ prolog
Quintus Prolog Release 3.1.4 (Sun-4, SunOS 5.2)
Copyright (C) 1993, Quintus Corporation.  All rights reserved.
2100 Geng Road, Palo Alto, California U.S.A. (415) 813-3800

| ?- load_files(v,[all_dynamic(true)]).
% compiling file /home/tom/kwi/adw/kc/indexer/v.pl
%  compiling file /home/tom/kwi/adw/kc/indexer/module_indexer.pl
%   compiling file /home/tom/kwi/adw/kc/indexer/low.pl
%    loading file /opt/quintus/generic/qplib3.1.4/library/types.qof
%    types.qof loaded, 0.217 sec 2,900 bytes
%    module types imported into low
%   low.pl compiled, 1.800 sec 9,116 bytes
%   module low imported into module_indexer
%   loading file /opt/quintus/generic/qplib3.1.4/library/addportray.qof
%   addportray.qof loaded, 0.183 sec 3,592 bytes
%   module add_portray imported into module_indexer
%  module_indexer.pl compiled, 2.617 sec 15,436 bytes
%  module module_indexer imported into v
%  loading file /home/tom/kwi/adw/kc/indexer/indexed.qof
%  indexed.qof loaded, 0.433 sec 11,668 bytes
%  module indexed imported into v
% v.pl compiled, 3.466 sec 30,404 bytes
% module v imported into user

yes
| ?- module(v).

yes
[v]
| ?- listing.

foo(A,B,C,D,E) :- 
        '** hash foo/4 **'(A,B,C,D,E,F),
        call(A:'** foo/4 **'(F,B,C,D,E,G,H)).

kill_foo(A,B,C,D,E) :- 
        indexed_retract(v:foo(A,B,C,D,E)).

'** indexed assert **'(foo(A,B,C,D,E)) :- 
        (   retract(A:'clause count foo/4'(F)) ->
            true
        ;   F is 0
        ),
        G is F+1,
        assert(A:'clause count foo/4'(G)),
        hash_term(D,H),
        functor(B,I,J),
        hash_term(I,K),
        L is\(E,\(H,K)),
        assert(A:'** foo/4 index 1 **'(L,F),M),
        assert(A:'** foo/4 index 2 **'(E,F),N),
        assert(A:'** foo/4 **'(F,B,C,D,E,M,N)).

'** indexed retract **'(foo(A,B,C,D,E)) :- 
        '** hash foo/4 **'(A,B,C,D,E,F),
        retract(A:'** foo/4 **'(F,B,C,D,E,G,H)),
        erase(G),
        erase(H).

'** indexed **'(foo(A,B,C,D,E)).

'** hash foo/4 **'(A,B,C,D,E,F) :- 
        (   integer(E),
            ground(D),
            nonvar(B) ->
            hash_term(D,G),
            functor(B,H,I),
            hash_term(H,J),
            K is\(E,\(G,J)),
            call(A:'** foo/4 index 1 **'(K,F))
        ;   integer(E) ->
            call(A:'** foo/4 index 2 **'(E,F))
        ;   true
        ).

yes
[v]
| ?- ^D

As peculiar as module indexing may seem, it happens to be the most heavily used
indexing method here at KnowledgeWare.

Note that in practice you should use indexed:indexed_module_initialize/1 when using
module indexing. This predicate ensures that a newly created module has all the
right dynamic declarations.
