Problema con `\ +` en consultas de Prolog con variables

Question

Estoy leyendo "Siete idiomas en siete semanas" atm, y estoy perplejo por alguna consulta Prolog a la que no entiendo la respuesta 'no'.

El archivo friends.pl se parece a esto:

likes(wallace, cheese). 
likes(grommit, cheese). 
likes(wendolene, sheep). 

friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y, Z). 

Puedo hacer algunas preguntas triviales sobre el mismo, tales como:

| ?- ['friends']. 
compiling /home/marc/btlang-code/code/prolog/friends.pl for byte code... 
/home/marc/btlang-code/code/prolog/friends.pl compiled, 12 lines read - 994 bytes written, 8 ms 

yes 
| ?- friend(wallace,grommit). 

yes 
| ?- friend(wallace,wendolene). 

no 

Esto es todo como se esperaba. Ahora, quiero introducir una variable en la consulta. Mi intención es que Prolog me dé una lista de todos los amigos de Wallace. Estoy esperando X = grommit, pero yo estoy no:

| ?- trace. 
The debugger will first creep -- showing everything (trace) 

yes 
{trace} 
| ?- friend(wallace,X). 
     1 1 Call: friend(wallace,_16) ? 
     2 2 Call: \+wallace=_16 ? 
     3 3 Call: wallace=_16 ? 
     3 3 Exit: wallace=wallace ? 
     2 2 Fail: \+wallace=_16 ? 
     1 1 Fail: friend(wallace,_16) ? 

no 
{trace} 

ni siquiera tratar de unificar X (_16) con grommit. ¿Por qué?

Answer 1

Es la definición de amigo:

friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y, Z). 

Lo importante aquí es que comience con \+(X = Y) la que normalmente se define como:

\+ Goal :- Goal,!,fail 

Tenga en cuenta que esto significa que si el objetivo tiene éxito, estás seguro de fallar Las variables libres (las que no se han asignado) siempre se unificarán, y por lo tanto serán iguales, por lo que siempre fallará con una variable libre. Por lo tanto, nunca asignará un valor a X o Y si aún no tiene uno.

lugar

friend(X, Y) :- likes(X, Z), likes(Y, Z), \+(X = Y) 

se comportan más como espera.

El problema aquí es que prolog le ofrece formas potentes de controlar el flujo de programas, pero eso realmente no encaja bien con su diseño más orientado a la lógica. Debería ser posible expresar las restricciones de tipo "negación como falla" de una manera que no produzca estos problemas. No soy un gran fanático de los prólogos por este motivo.

Answer 2

El primer subgrupo de friend/2 es \+(X = Y). Esto se ejecuta tratando primero de encontrar una solución para X = Y, y luego anula ese resultado. El predicado =/2 es aproximadamente el equivalente a unify/2, es decir, trata de unificar el operando izquierdo con el operando correcto. Ahora, cuando realiza consultas usando, p. friend(wallace, gromit), los dos átomos wallace y gromit no se unifican; pero cuando se lanza una variable libre a la mezcla, siempre se unifica con cualquier término, por lo que X = Y siempre es exitoso, por lo tanto \+(X = Y) siempre falla, y la ejecución nunca pasa ese primer subgrupo.

Answer 3

Con respecto al comentario de Philip JF arriba:

Debería ser posible expresar "negación como fracaso" restricciones de tipo de una manera que no produce estos problemas .

Esto es posible: la solución moderna para tales problemas son las limitaciones. En este caso, use por ejemplo dif/2, disponible en todos los sistemas Prolog serios.

Answer 4

Otro problema con tener la restricción de desigualdad primero es: no es posible encontrar un enlace para el X sin encuadernar (excluyendo el caso trivial de unificarlo con grommit por el momento). Prolog encuentra enlaces al ejecutar a través de su base de datos, tratando de unificar la variable independiente. Es por eso que likes(grommit, Z) encontrará algunos enlaces para Z que luego se pueden seguir procesando, porque hay likes cláusulas en la base de datos. Pero no hay tales cláusulas para la desigualdad de Grommit con algo, por lo que Prolog no puede producir ningún enlace. Tal como están las cosas, el predicado friend tiene que asegurarse de que todas las variables estén vinculadas antes de poder probar la desigualdad.