indexing - sesion - indexar en linea sud

Primera indexación de argumentos

Question

Quiero saber cómo se implementa la indexación inteligente de los primeros argumentos en varias implementaciones de Prolog.

En particular, los objetivos simples de la prueba de tipo como integer/1 justo después de una cláusula "cuello" podrían contribuir a una mejor indexación. Considerar:

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

Con esta cláusula de ordenación, me gustaría que la meta foo([],_) tenga éxito sin dejar puntos de elección inútiles.

Desafortunadamente, SWI Prolog no lo resuelve:

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

¿Mejoran otras implementaciones de Prolog?

Answer 1

Hasta donde sé, la indexación de cláusulas en Prolog se basa solo en la sintaxis de los argumentos de predicado (generalmente solo el primero), de modo que se puede hacer en tiempo de compilación. En su ejemplo, mover la última cláusula a la parte superior e insertar un corte después del integer(X) , al menos en algunas implementaciones, hará que las otras cláusulas se indexen y se cree inicialmente un único punto de elección para una llamada a este predicado . Mirar el primer objetivo en el cuerpo ralentizaría el proceso de indexación con, en general, un beneficio demasiado pequeño en el tiempo de ejecución.

Answer 2

Recientemente hemos agregado la indexación de guardias a Jekejeke Prolog. La siguiente indexación de guardia ya existe por un tiempo:

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

Extendimos este tratamiento ahora a más guardias. Esto estará disponible en la próxima versión 1.3.4:

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

Estas nuevas protecciones funcionan bien, ya que generan claves de cláusulas adicionales que ya forman parte de los índices existentes.

Pero actualmente nuestro índice existente no permite buscar un tipo de Prolog, solo valores atómicos, por lo que no podemos realizar una guarda de número entero (X) en este momento, aunque la detección en sí no sea muy difícil.

La realización es muy simple, no necesitamos buscar algunas instrucciones. En su lugar, podemos buscar directamente los literales del cuerpo en el formato intermedio más simple de Jekejeke Prolog:

Código abierto: índice de clase Java, método getGuard ()
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/model/rope/Index.java#L105

Answer 3

Sí, el sistema ECLiPSe hace esto.

Como sugiere, toma en cuenta una serie de predicados integrados simples (como integer/1, =/2, !/0 ) para fines de indexación. Su ejemplo luego se ejecuta de manera determinista, sin puntos de elección, para todas las llamadas de foo/2 con el primer argumento instanciado. Además, ECLiPSe haría esto en cualquier argumento, no solo en el primero.

Puede encontrar un poco más de detalle en el documento ECLiPSe - de LP a CLP .

Para responder a su pregunta de seguimiento: No se necesitan funciones de VM adicionales, el código de VM generado se ve así:

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 4

YAP es otro sistema Prolog que proporciona un índice extendido de cláusulas de predicado:

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

Algunos artículos relevantes sobre las características de indexación de YAP son:

• Indización basada en la demanda de cláusulas de prólogo
• Indización en tiempo justo de predicados dinámicos en Prolog