sentencia - sintaxis de prolog

Saber cuándo usar cut en prolog

Question

Tomé un curso en el que aprendí un prólogo. No pude entender cómo / cuándo usar los cortes. Aunque tengo una idea general de los cortes, parece que no puedo usarlos correctamente. ¿Alguien puede explicarlo brevemente o dar un buen tutorial (que no sea learnprolognow.org) sobre "cortes" que puedan recomendar?

Answer 1

Antes de usar un corte, requiero que mis predicados cumplan con estos dos criterios:

• da respuestas correctas sin un corte
• da respuestas correctas si se reordenan las cláusulas

Una vez que mi predicado se comporta de esa manera, a veces agrego un corte para recortar el no determinismo no deseado.

Por ejemplo, un predicado para probar si un número es positivo, negativo o cero.

sign(N, positive) :-
    N > 0.
sign(N, negative) :-
    N < 0.
sign(N, zero) :-
    N =:= 0.

Cada cláusula es completamente independiente de las demás. Puedo reordenar estas cláusulas o eliminar una cláusula y las cláusulas restantes todavía dan la respuesta esperada. En este caso, podría poner un corte al final de las cláusulas positive y negative solo para decirle al sistema Prolog que no encontrará más soluciones al examinar las otras cláusulas.

Uno podría escribir un predicado similar sin cortar usando -> ; , pero a algunos no les gusta cómo se ve:

sign(N, Sign) :-
    (   N > 0 -> Sign=positive
    ;   N < 0 -> Sign=negative
    ;            Sign=zero
    ).

Answer 2

Un corte compromete el objetivo de Prolog a las elecciones realizadas.

Debe usarse entonces cuando el programador sabe que no se debe probar ninguna alternativa disponible.

El uso más destacado es la implementación de la negación por falla .

fact(a).
fact(b).

/* 1 */ neg(X) :- call(X), !, fail.
/* 2 */ neg(_).

Aquí he (re) definido el operador de negación estándar, normalmente es ( / + ) / 1

?- neg(fact(c)).
true.

call(fact(c)) por la regla 1 no puede ser probada, y la regla alternativa 2 entonces tiene éxito.

?- neg(fact(a)).
false.

porque el fact(a) puede probarse, el corte descarta la alternativa antes de fallar.

?- neg(fact(X)).
false.

existe al menos una X desconocida tal que el hecho (X) tiene éxito.

?- neg(neg(fact(X))).
true.

la doble negación tiene el efecto de que las variables no se unan. Esto puede ser útil al hacer metaprogramación, para captar cláusulas sin alterar su ''estructura''. Desde el punto de vista operativo, está claro (?) Qué está pasando, pero el programa pierde su propiedad declarativa .

Otro uso, útil solo en los intérpretes rudimentarios, era instruir al sistema para realizar la última optimización de la llamada , prefijando la llamada recursiva con un corte. Entonces, el sistema puede evitar asignar el espacio de pila normalmente requerido para realizar un seguimiento del punto alternativo. Un ejemplo ficticio:

print_list([E|Es]) :- print_element(E), !, print_list(Es).
print_list([]).

editar sobre un tutorial: encontré que ''Clause and Effect'' de William Clocksin contiene una encuesta detallada relacionada con cut: el capítulo 4 ''Choice and Commitment'' está totalmente dedicado a recortar pros y contras. En la línea de fondo, principalmente contra ...

Answer 3

TL; DR: No.

El corte corta el árbol de búsqueda de Prolog. Es decir, dado un programa Prolog puro sin cortes y el mismo programa con cortes, la única diferencia es que el programa con cortes puede pasar menos tiempo en ramas infructuosas, y por lo tanto es más eficiente; podría tener menos respuestas; también podría terminar mientras que el programa original no lo hace.

Suena bastante inofensivo ... o incluso útil, ¿no? Bueno, la mayoría de las veces las cosas son más complejas.

Cortes rojos

Los cortes a menudo se usan de forma tal que el programa sin cortes no tiene ningún significado sensible. Tales cortes se llaman cortes rojos. En los mejores casos, se usa para implementar una forma cruda de negación no monotónica. Y en otros casos es mitad negación, mitad de algún significado procedimental que es muy difícil de entender. No solo para el lector del programa sino también para su escritor. De hecho, a menudo tales usos carecen involuntariamente de constancia . En cualquier caso: estos cortes no se colocan en un programa existente. Deben estar en ese programa desde el principio.

Para los usos más estructurados de tales cortes rojos, mejor uso once/1 , (/+)/1 , o (;)/2 - if-then-else like ( If -> Then ; Else ) lugar. Mejor aún, intente proteger tales construcciones contra usos involuntarios emitiendo instantiation_error s. O use when/2 (ofrecido en SWI, YAP, SICStus).

Cortes verdes

Los cortes que eliminan puntos de elección inútiles (y también respuestas redundantes) se llaman cortes verdes. Pero ten cuidado: no puedes colocarlos en tu programa simplemente presionando ! y algunos #00ff00 . La mayoría de las veces necesita un protector limpio de solo lectura para asegurarse de que no haya forma de que este corte gire a #ff0000 . También hay una manera simple de eliminar algunos puntos de elección sobrantes de forma segura: call_semidet/1 . Aquí hay algunos casos relacionados:

• ¿Cuál es el árbol SLD para esta consulta?

• Prolog anexa con operador de corte

• ¿Cuáles son los cortes verdes óptimos para la suma de aritméticos sucesores?

• Implementando "último" en Prolog

Cortar no es cometer

Finalmente, permítanme señalar que cut no es un commit-operator. A veces se parece un poco, pero necesitaría muchas restricciones para ser uno. Un commit-operator no puede ser (ab) utilizado para implementar (/+)/1 . Una confirmación requiere que cada cláusula se pruebe de forma independiente. Cada cláusula necesita una guardia completa; no puede confiar en que se intente solo después de que se hayan probado primero otras cláusulas. Además, un compromiso debería tener lugar en cada cláusula de un predicado. El corte puede ocurrir en cualquier lugar.

Answer 4

Cortó todo pero desapareció de mi código una vez que encontré el predicado de once . Internamente actúa como

once(X) :- X, !.

y lo encontré muy útil para tomar una decisión firme sobre cómo hacer algo antes de hacer algo.

Por ejemplo, aquí está mi metainterpretador estándar. La cláusula maybe1/1 tiene functors únicos en sus argumentos, por lo que una vez que se conocen, se puede seleccionar la derecha, maybe1/1 , perfectamente.

El trabajo de encontrar esa función única se le da al maybe0/2 que establece Y en una "declaración de qué hacer" sobre X

Sin once , esto podría tener que estar plagado de cortes. Por ejemplo, en tal maybe1 , hay tres / dos interpretaciones diferentes de X/Y , or que debemos verificar de arriba hacia abajo. Pero échale un vistazo, sin cortes.

maybe(X) :- 
    once(maybe0(X,Y)), maybe1(Y).

maybe0(true,       true).
maybe0((X,Y),      (X,Y)).
maybe0((X;Y),      or(L))          :- o2l((X;Y),L).
maybe0(X,          calls(X))       :- calls(X).
maybe0(X/Y,        fact(X/Y))      :- clause(X/_, true).
maybe0(X/Y,        rule(X/Y))      :- clause(X/_,_).
maybe0(X/Y,        abducible(X/Y)).
maybe0(or([H|T]),  or([H|T])).
maybe0(or([]),     true).

maybe1(true).
maybe1((X,Y))        :- maybe(X),maybe(Y).
maybe1((X;Y))        :- maybe(X);maybe(Y).
maybe1(abducible(X)) :- assume(X,0).
maybe1(fact(X))      :- assume(X,1), one(X).
maybe1(rule(X))      :- assume(X,2), one(clause(X,Y)), maybe(Y).
maybe1(calls(X))     :- one(clause(X,Y)), maybe(Y).
maybe1(or([H|T]))    :- any(One,Rest,[H|T]), ignore(maybe(One)), maybe(or(Rest)).