Saber cuándo usar cut en prolog

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?

TL; DR: No.

El corte corta el árbol de búsqueda de Prolog. Es decir, dado un progtwig Prolog puro sin cortes y el mismo progtwig con cortes, la única diferencia es que el progtwig con cortes puede pasar menos tiempo en twigs infructuosas, y por lo tanto es más eficiente; podría tener menos respuestas; también podría terminar mientras que el progtwig 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 progtwig 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 progtwig 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 progtwig existente. Deben estar en ese progtwig 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 progtwig 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 sum 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.

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

Debe usarse entonces cuando el progtwigdor 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 metaprogtwigción, para captar cláusulas sin alterar su ‘estructura’. Desde el punto de vista operativo, está claro (?) Qué está pasando, pero el progtwig 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 stack 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 …

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

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 “statement de qué hacer” sobre X

Sin once , esto podría tener que estar plagado de cortes. Por ejemplo, en 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)). 

El predicado de corte evita el retroceso. El predicado de corte se especifica como un signo de exclamación (!). Corta el árbol de búsqueda y acorta la ruta de acceso mediante el intérprete de prólogo. Semanticamente siempre tiene éxito.

 read(a). read(b). color(p, red) :- red(p). color(p,black) :- black(p),!. color(p,unknown). ?-color(X,Y). X = a, Y = red; X = b, Y = black; 

Sin corte, los objectives muestran Y = desconocido después de Y = negro.

Hay dos tipos de predicado de corte:

Green Cut: Green Cut es un tipo de corte que no tuvo ningún efecto en el significado declarativo. Solo se usa para mejorar la eficiencia y para evitar cálculos innecesarios. La eliminación de corte verde del progtwig no cambia el significado del progtwig.

Corte rojo: el corte rojo es uno que tuvo efecto sobre el significado declarativo. La eliminación del corte rojo del progtwig cambia el significado del progtwig.

    Intereting Posts