Prolog anexa con operador de corte

¿Qué problema puede ocurrir cuando usamos append with cut operator?

append2([],L,L):-!. append2([H|T],L,[H|TL]):-append2(T,L,TL). 

He probado varias entradas diferentes, pero siempre tiene éxito.

 ?- append2([1,2],[5],L). L = [1, 2, 5]. ?- append2([1,2],[1,2],L). L = [1, 2, 1, 2]. ?- append2([],[1,2],L). L = [1, 2]. ?- append2([1,2],[],L). L = [1, 2]. 

Hay dos tipos de cortes ; cortes verdes y cortes rojos. Los cortes verdes se insertan solo para mejorar la eficiencia y no cambian la semántica del progtwig. Los cortes rojos, por otro lado, sí. Por definición, los cortes verdes no causan ningún problema.

Entonces, ¿hay alguna forma de que el comportamiento cambie si el corte no estuviera allí?

Veamos; para que la primera cláusula coincida, L1 debería ser unificable con [], L2 con L y L3 con L o, en otras palabras, L2 unificable con L3.

Cuando L1 es [] la segunda cláusula no puede coincidir; entonces el corte no tiene ningún efecto

Cuando L1 no se crea una instancia: si la longitud de L2 y L3 se conoce en este punto, entonces deben ser iguales; de lo contrario, la primera cláusula no coincidiría; por lo tanto, la segunda cláusula no puede coincidir ya que en cada paso la longitud de L3 se reduce en 1 y la única manera de terminar requiere L2 = L3

si no se conoce la longitud de L3 o L2, entonces tenemos un problema ya que la segunda cláusula puede producir soluciones.

En efecto:

  3 ?- append2(L1,L2,[1,2,3]). L1 = [], L2 = [1, 2, 3]. 4 ?- append2(L1,[1,2,3],L3). L1 = [], L3 = [1, 2, 3]. 5 ?- append2(L1,L2,L3). L1 = [], L2 = L3. 6 ?- append2(L1,[E1,E2],L3). L1 = [], L2 = [E1, E2]. 7 ?- append2(L1,L2,[E1,E2]). L1 = [], L2 = [E1, E2]. 

mientras esperamos

 8 ?- append(L1,L2,[1,2,3]). L1 = [], L2 = [1, 2, 3] ; L1 = [1], L2 = [2, 3] ; L1 = [1, 2], L2 = [3] ; L1 = [1, 2, 3], L2 = [] ; false. 9 ?- append(L1,[1,2,3],L3). L1 = [], L3 = [1, 2, 3] ; L1 = [_G24], L3 = [_G24, 1, 2, 3] ; L1 = [_G24, _G30], L3 = [_G24, _G30, 1, 2, 3] ; L1 = [_G24, _G30, _G36], L3 = [_G24, _G30, _G36, 1, 2, 3] ; L1 = [_G24, _G30, _G36, _G42], L3 = [_G24, _G30, _G36, _G42, 1, 2, 3] ; ... 10 ?- append(L1,L2,L3). L1 = [], L2 = L3 ; L1 = [_G22], L3 = [_G22|L2] ; L1 = [_G22, _G28], L3 = [_G22, _G28|L2] ; .... 11 ?- append(L1,[E1,E2],L3). L1 = [], L3 = [E1, E2] ; L1 = [_G78], L3 = [_G78, E1, E2] ; L1 = [_G78, _G84], L3 = [_G78, _G84, E1, E2] ; L1 = [_G78, _G84, _G90], L3 = [_G78, _G84, _G90, E1, E2] ; ... 12 ?- append(L1,L2,[E1,E2]). L1 = [], L2 = [E1, E2] ; L1 = [E1], L2 = [E2] ; L1 = [E1, E2], L2 = [] ; false. 

A veces, realmente tiene sentido introducir cortes verdes, incluso en append/3 , pero se debe tener cuidado de que dicho corte siga siendo un corte verde. Es decir, un recorte que mejora la eficiencia (en un cierto nivel) y no afecta las respuestas.

Hay una regla empírica muy simple para introducir cortes en verde: si agrega un corte en un progtwig puro y monótono sin ningún tipo de protección, puede estar bastante seguro de que será un corte rojo que destruirá el significado de su progtwig.

Hay muy pocas excepciones a esta regla de oro. Por ejemplo, puede agregar un corte después de un objective libre variable, siempre que no haya más reglas, etc. Definitivamente es un buen entrenamiento para tratar de descubrir los casos que se ven afectados por un corte.

Pero volvamos a su progtwig append2/3 . Actualmente, el corte siempre se corta, incluso si se aplica la regla alternativa, en cuyo caso el corte elimina las respuestas, que es lo que queremos evitar.

Entonces, ¿cuándo será la primera cláusula la única relevante?

Si el primer argumento es [] , así append2([], Xs, Ys). – pero también si el último argumento es [] (hay incluso más casos que son más complejos). Vamos a probar ambos casos con la definición original libre de cortes:

 ? -anexar ([], Ys, Zs).
 Ys = Zs.

 ? -anexar (Xs, Ys, []).
 Xs = Ys, Ys = [];
 falso.

Entonces, en el primer caso, el sistema pudo determinar que hay una solución única de inmediato, mientras produce la respuesta. En el segundo caso, sin embargo, el sistema Prolog no estaba seguro de si sería necesaria o no otra respuesta: “dejó un punto de elección abierto”, por así decirlo. Es una lástima, ya que es bastante trivial determinar que también en este caso, solo existe una respuesta única. Un corte hubiera sido ideal aquí para ayudar. Pero un corte sin protección hace más daño de lo que ayuda.

El corte puede cortar, siempre que el tercer argumento sea un [] :

 append3(Xs, Ys, Zs) :- ( Zs == [] -> ! ; true ), Xs = [], Ys = Zs. append3([X|Xs], Ys, [X|Zs]) :- append3(Xs, Ys, Zs). 

Este progtwig ahora es más eficiente en el sentido de que no deja abierto un punto de elección, si solo se conoce el tercer argumento.

 ? -anexar (Xs, Ys, [1]).
 Xs = [],
 Ys = [1];
 Xs = [1],
 Ys = [];
 falso.

 ? - append3 (Xs, Ys, [1]).
 Xs = [],
 Ys = [1];
 Xs = [1],
 Ys = [].

El progtwig no es necesariamente más rápido, ya que la prueba en sí misma puede ser costosa. Idealmente, un sistema Prolog sería capaz de hacer tales cosas internamente, pero a veces el progtwigdor tiene que ayudar un poco.

Pruebe por ejemplo la consulta más general:

 ?- append2(X, Y, Z). 

No funcionará cuando los primeros dos argumentos sean variables:

 ?- append(X, Y, [1, 2, 3]). X = [], Y = [1, 2, 3] ; X = [1], Y = [2, 3] ; X = [1, 2], Y = [3] ; X = [1, 2, 3], Y = [] ; false. ?- append2(X, Y, [1, 2, 3]). X = [], Y = [1, 2, 3]. 
    Intereting Posts