Я хочу знать, как интеллектуальная индексация первого аргумента реализована в различных реализациях 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 лучше?
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:
Да, система 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
Недавно мы добавили охранную индексацию в 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
Насколько я знаю, индексирование предложения в Prolog основано только на синтаксисе предикатных аргументов (обычно только на первом), так что это можно сделать во время компиляции. В вашем примере перемещение последнего предложения вверху и вставка разреза после integer(X) будет, по крайней мере, в некоторых реализациях, заставлять другие клаузулы индексироваться и изначально будет создана одна точка выбора для вызова этого предиката. Взгляд на первую цель в теле замедлит процесс индексирования, в общем, слишком малое преимущество во время выполнения.