Индексирование первого аргумента

Я хочу знать, как интеллектуальная индексация первого аргумента реализована в различных реализациях 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 лучше?

Ответ 1

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:

Ответ 2

Да, система ECLiPSe делает это.

Как вы предлагаете, он принимает во внимание ряд простых встроенных предикатов (таких как integer/1, =/2, ! /0) для целей индексации. Затем ваш пример выполняется детерминистически, без точек выбора, для всех вызовов foo/2 с созданием первого аргумента. Более того, ECLiPSe сделает это по любому аргументу, а не только по первому.

Вы можете найти немного больше подробностей в статье ECLiPSe - от LP до CLP.

Чтобы ответить на следующий вопрос: никаких дополнительных функций виртуальной машины не требуется, сгенерированный код виртуальной машины выглядит следующим образом:

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

Ответ 3

Недавно мы добавили охранную индексацию в Jekejeke Prolog. Следующая защитная индексация уже существует некоторое время:

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

Мы распространили это лечение теперь на дальнейших охранников. Это будет доступно в следующем выпуске 1.3.4:

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

Эти новые средства защиты работают нормально, так как они генерируют дополнительные ключи предложений, которые уже являются частью существующих индексов.

Но в настоящее время наш существующий индекс не позволяет искать тип Prolog, только атомарные значения, поэтому мы не можем реализовать целочисленную (X) защиту в данный момент, даже если само обнаружение не будет очень трудным.

Реализация очень проста, нам не нужно искать некоторые инструкции. Вместо этого мы можем напрямую искать литералы тела в более простом промежуточном формате Jekejeke Prolog:

Открытый исходный код: индекс класса Java, метод getGuard()
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/model/rope/Index.java#L105

Ответ 4

Насколько я знаю, индексирование предложения в Prolog основано только на синтаксисе предикатных аргументов (обычно только на первом), так что это можно сделать во время компиляции. В вашем примере перемещение последнего предложения вверху и вставка разреза после integer(X) будет, по крайней мере, в некоторых реализациях, заставлять другие клаузулы индексироваться и изначально будет создана одна точка выбора для вызова этого предиката. Взгляд на первую цель в теле замедлит процесс индексирования, в общем, слишком малое преимущество во время выполнения.