第一个参数索引

Question

我想知道在各种Prolog实现上如何实现智能的第一个参数索引.

特别是,简单的类型测试目标,例如integer/1在"颈部"条款之后,可以有助于更好的索引.考虑:

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

通过这个子句排序,我希望目标foo([],_)能够成功而不会留下任何无用的选择点.

不幸的是,SWI Prolog没有弄明白:

?- 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] ...

其他Prolog实现做得更好吗？

Answer 1

是的,ECLiPSe系统就是这样做的.

正如您所建议的那样,它会考虑许多简单的内置谓词(例如integer/1, =/2, !/0)以用于索引目的.然后,对于foo/2实例化第一个参数的所有调用,您的示例将在没有选择点的情况下确定性地执行.此外,ECLiPSe会在任何争论中做到这一点,而不仅仅是第一个.

您可以在ECLiPSe文件中找到更多细节- 从LP到CLP.

要回答您的后续问题:不需要额外的VM功能,生成的VM代码如下所示:

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 是另一个提供谓词子句扩展索引的 Prolog 系统：

$ 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.

关于 YAP 索引功能的一些相关论文有：

• Prolog 子句的需求驱动索引
• Prolog中动态谓词的即时索引