Prolog anexa con operador de corte

prolog-cut

Question

¿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].

Answer 1

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

Answer 2

Pruebe por ejemplo la consulta más general:

?- append2(X, Y, Z).

Answer 3

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

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

Pero volvamos a su programa 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:

?- append([], Ys, Zs). Ys = Zs. ?- append(Xs, Ys, []). Xs = Ys, Ys = [] ; false.

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

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

El programa 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 programador tiene que ayudar un poco.

Answer 4

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