First argument indexing

Question

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?

Answer 1

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  

Answer 2

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:

• Demand-Driven Indexing of Prolog Clauses
• On Just in Time Indexing of Dynamic Predicates in Prolog