第一个参数索引化

Question

第一个参数索引化

17

我想知道各种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实现是否表现更好？

- repeat

请注意您的示例的不规则性，甚至是不纯度：虽然对于foo（X，Y）when nonvar（X）来说一切都很好，但对于变量X来说就变得相当不合逻辑了：前三个子句成功，而最后一个失败。针对这种特定模式进行优化似乎是一种浪费的努力：它不会出现在任何纯程序中。 - false

@false。我设想中的实际使用更偏向于“第一个参数是无限大、最大值或整数X”（不需要将整数放入框中）…… - repeat

4个回答

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索引特性的一些相关论文包括：

- Paulo Moura

-1

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

- migfilg

你所要求的功能只适用于特定格式的子句，而它所带来的效率提升并不足以弥补索引机制增加的复杂性。 - migfilg

我不明白你拒绝使用cut的原因：通常任何Prolog程序都会显式或隐式地使用它（通过使用条件语句和类似结构）。至于使用functor以启用索引，这是Prolog编程的标准做法：我也不明白为什么要避免使用它。 - migfilg

我同意更复杂的索引机制会对编译时间产生影响。我不明白你所说的“纯代码”是什么意思：如果你省略掉剪切和其衍生物（not/1，条件语句等），以及非逻辑谓词，如类型测试谓词（如integer/1），I/O，算术等，那么你就得到了一个纯逻辑语言（Horn子句谓词演算），它并不足够强大，不能用作任何目的的编程语言。但也许你并不需要图灵机的能力来编写你想要的程序。 - migfilg

你的报价不可接受，而且似乎你没有理解我写的内容。请阅读一些更科学可靠的教材，比如W.F.Clocksin和C.S.Mellish的《Prolog编程》，Springer-Verlag，1994年或R.O'Keefe的《Prolog技艺》，The MIT Press，1990年。 - migfilg

1

我在技术文献中解释了什么是“纯Prolog”：使用分辨率原则作为推理规则的Horn子句演算法，一种没有副作用的纯逻辑语言。也许你想阅读关于分辨率的文章，J.A. Robinson，“基于分辨率原则的面向机器的逻辑”，JACM卷12，1965年，和/或逻辑编程语义的标准书籍：J.W. Lloyd，“逻辑编程基础”，第二版，Springer-Verlag，1987年。 - migfilg

只有在大量插入和撤回子句时，您才无法获得良好的摊销。但对于静态子句，索引只会执行一次，因此分析子句体应该有出色的摊销效果。 - user502187

-1

我们最近在Jekejeke Prolog中添加了守卫索引。以下守卫索引已经存在一段时间：

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

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

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

这些新的守卫很好用，因为它们生成了已经是现有索引一部分的附加子句键。

但是目前我们现有的索引不允许查找Prolog类型，只允许原子值，所以我们目前无法实现integer(X)守卫，即使检测本身并不是非常困难。

实现非常简单，我们不需要查找某些指令。相反，我们可以直接在更简单的Jekejeke Prolog中间格式中搜索主体文字：

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

- user502187

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jschimpf · Accepted Answer

是的，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