第一个参数索引

Question

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

特别是，像 integer/1 紧跟在子句 "neck" 之后的简单类型测试目标可以 有助于更好的索引。考虑：

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

据我所知，Prolog 中的子句索引仅基于谓词参数（通常仅第一个）的语法，因此可以在编译时完成。在您的示例中，将最后一个子句移动到顶部并在 integer(X) 之后插入一个剪切，至少在某些实现中，会导致其他子句被索引，并且最初会为调用此创建一个选择点谓词。查看正文中的第一个目标会减慢索引过程，通常对执行时间的好处太小。

Answer 2

是的，ECLiPSe 系统会这样做。

正如您所建议的，它考虑了一些简单的内置谓词（例如 integer/1, =/2, !/0）以用于索引目的。然后，您的示例在没有选择点的情况下确定地执行 foo/2 的所有调用，并实例化第一个参数。此外，ECLiPSe 会在任何参数上执行此操作，而不仅仅是第一个。

您可以在论文中找到更多细节 ECLiPSe - from LP to 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 3

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 索引功能的相关论文是：

Answer 4

我们最近向 Jekejeke Prolog 添加了保护索引。以下保护索引已经存在一段时间了：

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

我们现在将这种处理扩展到更多的警卫。这将在即将发布的 1.3.4 版本中提供：

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

这些新的守卫工作得很好，因为它们会生成额外的子句键，这些键已经是现有索引的一部分。

但目前我们现有的索引不允许查找 Prolog 类型，只能查找原子值，因此我们目前无法实现整数 (X) 保护，即使检测本身不会很困难。

实现很简单，一些指令我们不需要查。相反，我们可以直接搜索更简单的 Jekejeke Prolog 中间格式的正文：

开源：Java class 索引，方法 getGuard()
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/model/rope/Index.java#L105

第一个参数索引

First argument indexing

indexing

prolog