First argument indexing

18
votes

I want to know how smart first argument indexing is implemented on various Prolog implementations.

In particular, simple type-test goals like integer/1 right after a clause "neck" could contribute to better indexing. Consider:

foo(h(X),X).
foo([],nil).
foo([_|_],cons).
foo(X,Y) :- integer(X), Y = n(X).

With this clause ordering I would like the goal foo([],_) to succeed without leaving any useless choicepoints.

Unfortunately, SWI Prolog does not figure it out:

?- length(Xs,10),
   maplist(=([]),Xs),
   statistics(trailused,T1),
   maplist(foo,Xs,Ys),
   statistics(trailused,T2).

T1 = 5792,
T2 = 5968,
Xs = [[], [], [], [], [], [], [], [], [], []],
Ys = [nil, nil, nil, nil, nil, nil, nil, nil, nil, nil] ...

Do other Prolog implementations do better?

4
indexingprolog
Please note the irregularity, even impurity, of your example: While it is all fine for foo(X,Y) when nonvar(X), it gets quite illogical for X being a variable: The first three clauses succeed, while the last fails. Optimizing for this particular mode appears to be a waisted effort: It would not occur in any pure program. – false
@false. The actual use I had in mind was more along the lines of "the first argument is either inf or sup or an integer X" (without the need for boxing the integer)... – repeat

4 Answers

4
votes

YAP is another Prolog system providing extending indexing of predicate clauses:

$ yap
YAP 6.3.4 (x86_64-darwin14.3.0): Wed Apr 22 22:26:34 WEST 2015
 ?- [user].
 % consulting user_input...
foo(h(X),X).
|     foo([],nil).
|     foo([_|_],cons).
|     foo(X,Y) :- integer(X), Y = n(X).
|      % consulted user_input in module user, 1 msec 0 bytes
true.
 ?- foo([],_).
true.

Some relevant papers on YAP indexing features are:

7
votes

Yes, the ECLiPSe system does this.

As you suggest, it takes into account a number of simple built-in predicates (such as integer/1, =/2, !/0) for indexing purposes. Your example then executes deterministically, without choicepoints, for all calls of foo/2 with the first argument instantiated. Moreover, ECLiPSe would do this on any argument, not just the first.

You can find a little more detail in the paper ECLiPSe - from LP to CLP.

To answer your followup question: No extra VM features are necessary, the generated VM code looks like this:

foo / 2:
    switch_on_type           a(1) 
            list:           ref(L5)
            structure:      ref(L1)
            bignum:         ref(L7)
            []:             ref(L4)
            integer:        ref(L7)
            meta:           ref(L0)
label(L0):
    try                      0     2     ref(L1) 
    retry                    0     ref(L3) 
    trust                    0     ref(L5) 
label(L1):
    get_structure            a(1)     h / 1     ref(L2) 
    write_value              a(2) 
    ret                  
label(L2):
    read_value               a(2) 
    ret                  
label(L3):
    get_nil                  a(1) 
label(L4):
    get_atom                 a(2)     nil 
    ret                  
label(L5):
    get_list                 a(1)     ref(L6) 
    write_void               2 
label(L6):
    get_atom                 a(2)     cons 
    ret                  
label(L7):
    get_structure            a(2)     n / 1     ref(L8) 
    write_value              a(1) 
    ret                  
label(L8):
    read_value               a(1) 
    ret
0
votes

We recently added guard indexing to Jekejeke Prolog. The following guard indexing exists already for a while:

p(..., X, ...) :- ..., var(X), ...

We extended this treatment now to further guards. This will be available in the upcoming release 1.3.4:

p(..., X, ...) :- ..., X = f(...), ...
p(..., X, ...) :- ..., functor(X, f, ...), ...

These new guards work fine, since they generate additional clause keys that are already part of the existing indexes.

But currently our existing index does not allow to lookup a Prolog type, only atomic values, so we cannot realize an integer(X) guard at the moment, even though the detection itself would not be very difficult.

The realization is very simple, we do not need to lookup some instructions. Instead we can directly search the body literals in the simpler Jekejeke Prolog intermediate format:

Open Source: Java class Index, method getGuard()
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/model/rope/Index.java#L105

-2
votes

As far as I know clause indexing in Prolog is based only on the syntax of the predicate arguments (usually only the first one) so that it can be done at compile time. In your example moving the last clause to the top and inserting a cut after integer(X) will, at least in some implementations, cause the other clauses to be indexed and a single choice-point would be initially created for a call to this predicate. Looking at the first goal in the body would slow down the indexing process with, in general, a too small benefit in the execution time.