prolog - Usando /==/2 o dif/2

prolog-dif logical-purity

Question

Si quiero asegurarme de que dos variables no ejemplifican el mismo término, ¿cuál es la forma preferida de hacerlo?

Digamos que necesito encontrar bordes dirigidos en un gráfico, y un nodo no puede tener un borde en sí mismo:

node(a, x, y). node(b, z, x). node(c, y, y).

(los bordes aquí son a -> c, b -> a, pero no c -> c)

Los siguientes trabajos:

edge(A, B) :- node(A, _, X), node(B, X, _), A /== B.

Esto también funciona [swi-prolog]:

edge(A, B) :- dif(A, B), node(A, _, X), node(B, X, _).

Esto no funciona, aparentemente (¿porque ni A ni B están instanciados todavía?):

edge(A, B) :- A /== B, node(A, _, X), node(B, X, _).

Supongo que mi problema con la primera solución es que, con un predicado de node más complejo, pueden ocurrir muchas unificaciones innecesarias antes de que falle el edge . La dif por otro lado, está en una biblioteca, lo que sugiere que no está destinado a ser utilizado en un caso tan simple (aunque tiene la función exacta que parece estar buscando).

Answer 1

En primer lugar, dif/2 y (/==)/2 significan lo mismo cuando ambos argumentos se basan, eso es variable libre. Por lo tanto, si puede asegurarse de que los argumentos se fundamentarán, o que se creará una instancia suficiente de manera que otras instancias no afecten el resultado de (/==)/2 , entonces no hay una diferencia.

En su ejemplo, tendríamos que estar seguros de que las respuestas para el node/3 siempre contienen un primer argumento. En ese caso, el programa (/==)/2 está bien. En casos raros puede ser menos eficiente que la versión dif/2 . Piense en el edge(X, X) de la meta edge(X, X) .

En muchas situaciones, el (/==)/2 o incluso (/=)/2 es significativamente más eficiente. Por otro lado, ¿qué tan importante es la eficiencia en comparación con la corrección?

Otra forma de ver esto, es considerar (/==)/2 y (/=)/2 como aproximaciones desde dos lados: solo si ambos están de acuerdo, tenemos un resultado final seguro.

Históricamente, dif/2 es uno de los predicados incorporados más antiguos. Estaba presente en el primer sistema Prolog, que a veces se llama Prolog 0 para distinguirlo de la próxima versión que a menudo se percibe como el primer Prolog: el Prolog de Marsella - Prolog 1. El Prolog 1 ya no tenía dif/2 . Es en esta forma que Prolog llegó a Edimburgo. Además, dif/2 no es parte de la norma ISO (actualmente), ya que requiere algún mecanismo similar a la coroutinación. Y muchos sistemas Prolog (bastante antiguos) no tienen tal mecanismo. Sin embargo, incluso en ISO Prolog uno podría hacerlo mejor:

iso_dif(X, Y) :-
   X == Y,
   !,
   fail.
iso_dif(X, Y) :-
   X /= Y,
   !.
iso_dif(X, Y) :-
   throw(error(instantiation_error,iso_dif/2)).

(Aquí hay otra implementación, probablemente más eficiente )

Observe cómo los casos problemáticos están cubiertos por un error que detiene todo el cálculo.

Los sistemas Prolog actuales que admiten dif/2 directamente desde la caja son B, SICStus, SWI, YAP. Está en una biblioteca de IF, Ciao, XSB.

Véase también esta respuesta .

Para apoyar mi reclamo sobre los gastos generales, aquí hay una prueba en varios Prólogos en la misma máquina. En SWI, hay una sobrecarga de un factor de 10, en B, no hay sobrecarga. Como ha señalado @nfz, los números son ligeramente diferentes al compilar cosas. Así que su millaje puede variar.

SWI 6.3.4-55

?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )). % 22,999,020 inferences, 5.162 CPU in 5.192 seconds (99% CPU, 4455477 Lips) false. ?- 1000=I,time(( between(1,I,X), between(1,I,Y), X /== Y, false )). % 2,000,001 inferences, 0.511 CPU in 0.521 seconds (98% CPU, 3912566 Lips) false.

B 7.8

| ?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )). CPU time 0.364 seconds. no | ?- 1000=I,time(( between(1,I,X), between(1,I,Y), X /== Y, false )). CPU time 0.356 seconds. no

LADRAR

?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )). % 2.528 CPU in 2.566 seconds ( 98% CPU) no ?- 1000=I,time(( between(1,I,X), between(1,I,Y), X /== Y, false )). % 0.929 CPU in 0.963 seconds ( 96% CPU) no

Answer 2

Las consultas son metainterpretadas y la sobrecarga puede superar las diferencias de dif(X,Y) y X/==Y Debes comparar estos dos predicados:

t1:-
    1000=I,
    time(t1(I)).


t1(I):-
    dif(X,Y), 
    between(1,I,X), 
    between(1,I,Y), 
    false.

t2:-
    1000=I,
    time(t2(I)).


t2(I):-
    between(1,I,X), 
    between(1,I,Y), 
    X/==Y,
    false.

En B-Prolog, obtuve los siguientes resultados:

| ?- cl(t)
Compiling::t.pl
compiled in 0 milliseconds
loading::t.out

yes
| ?- t1
CPU time 0.14 seconds.
no
| ?- t2
CPU time 0.078 seconds.
no
| ?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )).
CPU time 0.234 seconds.
no
| ?- 1000=I,time(( between(1,I,X), between(1,I,Y), X /== Y, false )).
CPU time 0.218 seconds.

Answer 3

Solo por razones de elegancia y didácticas, dif/2 es claramente preferible aquí y también en la gran mayoría de los demás casos, ya que, como ya se ha señalado, "muchas unificaciones innecesarias pueden tener lugar" de lo contrario, y también porque dif/2 es una pura y un buen predicado declarativo que se puede usar en todas las direcciones y en cualquier lugar del cuerpo de la cláusula sin cambiar el significado del programa, en contraste con (/==)/2 . dif/2 también es un predicado con carga automática en SWI-Prolog, lo que significa que no necesita importar ninguna biblioteca explícitamente para usarla, y dif/2 está disponible como cualquier predicado incorporado.

Si usa dif/2 puede razonar mucho más fácilmente sobre su código. Por ejemplo, en tu caso, comienzas con:

edge(A, B) :- node(A, _, X), node(B, X, _), dif(A, B).

y luego, como saben que dif/2 es un predicado completamente puro, saben que también pueden escribir esto como:

edge(A, B) :- dif(A, B), node(A, _, X), node(B, X, _).

Además, como sabe que dif/2 siempre termina, usted sabe que este cambio puede, como máximo, mejorar las propiedades de terminación de su programa.

Como todas las restricciones, dif/2 está destinado a ser utilizado. Lo recomiendo altamente en lugar de predicados impuros que no son conmutativos.

En caso de que esté preocupado por el rendimiento, aquí hay una pequeña comparación, simplemente comparando dif/2 con el no declarativo (/==)/2 en un caso de uso donde los dos predicados se pueden usar de manera intercambiable:

?- N = 1_000_000, time((between(1,N,_),dif(a,b),false)). % 11,000,005 inferences, 0.352 CPU in 0.353 seconds (100% CPU, 31281029 Lips) ?- N = 1_000_000, time((between(1,N,_),a/==b,false)). %@ % 3,000,001 inferences, 0.107 CPU in 0.107 seconds (99% CPU, 28167437 Lips)

Por lo tanto, a veces hay ventajas de rendimiento al usar (/==)/2 . Sin embargo, también hay inconvenientes mucho más graves cuando se utiliza un predicado de tan bajo nivel: es más difícil de entender, más propenso a errores y no declarativo.

Por lo tanto, recomiendo simplemente usar dif/2 para expresar que dos términos son diferentes.