prolog - sencillos - Obtener un orden en la resolución de predicados

prolog pdf

Question

Mira los siguientes objetivos (estoy usando swi-prolog con clpfd de Markus Triska):

result(Input,Result) :-
    Input #> 10,
    Result=decline.
result(Input,Result) :-
    Input in 0..20,
    Result=offer.

Una posible consulta se ve así:

?- result(15,B).
B = decline ;
B = offer.

Quiero agregar una orden o algún tipo de prioridad de solución. Si "declive" es una respuesta válida para Input=15 , entonces el segundo objetivo no se debe considerar más, de modo que solo B=decline es una solución pero no B=offer .

Sé que podría agregar un !/0 pero al revés no funcionaría. Dame todas las respuestas posibles para este predicado.

Teniendo en cuenta este ejemplo, una Result=offer solo debería ser cierta para la Input 0..10 , porque de lo contrario el objetivo de disminución anterior más alto debería dispararse.

¿Estoy pensando que es demasiado imperativo cuando trato de considerar un orden dentro de los predicados?

Answer 1

Algunas ideas de la negación constructiva podrían ayudar aquí.

Teoría

Hay una manera simple de tener un corte lógico. Especialmente para restricciones, ya que las restricciones generalmente son negación completa. Entonces, si tiene una restricción C, generalmente puede encontrar una restricción C ''con la siguiente propiedad:

C'' <=> ~C

Para imponer una preferencia entre dos cláusulas que se leen de la siguiente manera:

p :- C, q.
p :- r

Solo haz lo siguiente:

p :- C, q.
p :- C'', r.

Si su solucionador de restricciones proporciona una negación reificada, como (#/)/1 , podría incluso definir un operador para eso:

:- op(1050,xfy,#?).
:- op(1100,xfy,#:).
(A #? B #: C) :- (A, B); (#/ A, C).

Y luego escribe lo siguiente:

p :- C #? q #: r.

Permite aplicar esta estrategia a tu ejemplo:

Ejemplo

Tu código actualmente dice lo siguiente:

result(Input, Result) :-
    Input #> 10,
    Result = decline.
result(Input, Result) :-
    Input in 0..20,
    Result = offer.

Luego haz lo siguiente:

result(Input, Result) :-
    Input #> 10,
    Result = decline.
result(Input, Result) :-
    Input #=< 10, Input in 0..20,
    Result = offer.

Aquí hay un ejemplo de ejecución:

?- result(15, X).
X = decline ;
false.

?- result(8, X).
X = offer.

Y ahora usando (#?)/2 que es posible, por ejemplo, en SWI-Prolog, ya que la biblioteca CLP (FD) admite la reificación. Suponiendo que hemos consultado la biblioteca CLP (FD) y luego definido (#:)/2 como se indica anteriormente:

 result(Input, Result) :-
    Input #> 10 
    #? 
       Result = decline 
    #: 
       Input in 0..20,
       Result = offer.

Aquí hay un ejemplo de ejecución:

?- result(15, X).
X = decline ;
false.

?- result(8, X).
X = offer.

Renuncia

La sintaxis posterior de (#?)/2 y (#:)/2 está inspirada en los operadores Java if-then-else (?)/2 y (:)/2 . No es posible una sintaxis más inspirada en Prolog, ya que no podemos anular o ampliar la definición (;)/2 .

Para obtener más información sobre la reificación, consulte, por ejemplo , la sección A.8.4 Reificación. Lo que no hicimos fue reificar la conjunción y la disyunción en nuestra definición de CLP (FD) if-then-else, ya que en ese momento y en la otra parte podría contener otras metas y luego restricciones CLP (FD).

Adiós

Answer 2

Hay varios problemas aquí, comencemos primero con los más obvios:

Problemas de modelado

Usted tiene una relación (el result/2 quizás no sea el mejor nombre), y se supone que esta relación debe modelar cuando el decline y cuando la offer debe ser verdadera. Antes de leer su programa, prefiero preguntar a Prolog:

?- result(X, decline), result(X, offer). X in 11..20 ; false.

Entonces, para los valores de 11 hasta 20, su relación es ambigua. Si quiere tomar una decisión, primero corrija esta relación. En realidad, comenzaría con

• un mejor nombre para la relación que deja en claro que es una relación
• sin verborrea imperativa (como Input o imperativos)
• una formulación más compacta, no necesita tantos (=)/2 objetivos en su programa. En cambio, puedes escribirlo así:

heigth_decision(I, decline) :- I #< 10.

Respuestas y éxito vs. soluciones en CLP

Y luego hay otro problema que es más fundamental. Esto es mucho más serio, ya que todas las respuestas SO hasta ahora ignoran este aspecto por completo. Se trata de la noción de respuestas y el éxito y, por otro lado, la noción de soluciones.

Cuando hace una consulta en Prolog, lo que obtiene es una respuesta . Tal respuesta podría contener soluciones, como la respuesta L = [_,_] que contiene infinitas soluciones. O una respuesta puede contener exactamente una solución como Decision = decline . Pero hay mucho más en el medio si está utilizando restricciones como la library(clpfd) .

Ahora puede obtener infinitamente muchas soluciones:

?- abs(X) #< 3. X in -2..2.

O infinitamente muchos:

?- X #> Y. Y#=<X+ -1.

Pero también puede obtener exactamente una solución, que no se ve como una:

?- 2^X #= 1. 2^X#=1.

Entonces, solo para repetir esto: aquí tenemos exactamente una solución en los enteros, pero para Prolog esto es demasiado complejo. Lo que obtuvimos fue una respuesta que dice: Sí, eso es todo cierto, siempre que _{toda esta letra pequeña sea verdadera} .

Peor aún, a veces recibimos respuestas que no contienen ninguna solución.

?- X^X#=0. X^X#=0.

Si Prolog fuera lo suficientemente inteligente, respondería false . Pero no siempre puede ser tan inteligente, simplemente porque puede formular fácilmente problemas indecidibles. Tal respuesta a veces se llama inconsistencia . La noción alemana Scheinlösung (solución falsa, pero con una connotación menos negativa) transmite la idea un poco mejor.

Entonces, una respuesta puede contener soluciones, pero algunas respuestas no contienen soluciones en absoluto. Por esta razón, el éxito de un objetivo no puede tomarse como la existencia de una solución. Es decir, todas las SO-respuestas que sugieren algún tipo de confirmación como (;) / 2 - si-entonces-otra, una vez / 1 o! / 0 son todas incorrectas, si toman el éxito como una solución. Para ver esto, pruébalos con:

?- X^X#=0, result(X,decline). X in 11..sup, X^X#=0 ; false. ?- X^X#=0, result(X,offer). X in 0..20, X^X#=0.

Entonces, ¿cómo puedes estar seguro de algo?

• Puede confiar en el fracaso de un objetivo.

• Puedes probar el labeling/2 , pero esto solo funciona en dominios finitos.

• Puede usar call_residue_vars/2 y copy_term/3 para determinar si hay restricciones "pendientes"

• Desafortunadamente, no puede confiar completamente en el nivel de SWI que oculta restricciones que no están relacionadas con las variables en una respuesta. Solo SICStus los muestra correctamente.

Answer 3

La parte que me desconcierta es cuando dices "al revés no funcionaría". ¿Por qué quieres ir al revés?

Este es un caso claro de búsqueda determinista y la forma de hacerlo en Prolog es con un corte. Si se cumple la primera regla, no mantenga las otras ramas abiertas. Alternativamente, puede hacer que los rangos que verifique sean mutuamente exclusivos.

Si no solo está jugando y está tratando de implementar algo serio, le recomiendo que lea las reglas con prioridad y reglas teleo-reactivas . Debería poder encontrar marcos construidos encima de Prolog que puedan usarse para resolver su problema sin reinventar la rueda.

Answer 4

Orden de predicados es una parte esencial de los programas Prolog. Esto se debe a que la búsqueda de pruebas continúa en un orden estrictamente definido, aplicando la resolución de SLD .

Su predicado da resultados razonables:

?- result(X,Y).
Y = decline,
X in 11..sup ;
Y = offer,
X in 0..20.

En lugar de un corte en el resultado / 2, podría usar una vez / 1 al llamarlo, conservando la definición adecuada para uso general.

?- once(result(X,Y)).
Y = decline,
X in 11..sup.