%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%    REEVALUACION Y CORTE    %%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

/*

Ante un objetivo que admite varias soluciones,
Prolog explora en profundidad su arbol SLD 
intentando encontrar todas ellas (indeterminismo 
"don't know"). El algoritmo  de busqueda es 
capaz  por tanto de hacer "vuelta atras" 
(backtracking) en ciertos momentos para 
intentar recorrer  caminos alternativos 
que lleven a nuevas soluciones. A este 
efecto se le llama REEVALUACION, y consiste
basicamente en poder pasar de un subobjetivo
cualquiera al inmeditamente precedente (lo que
se implementa mediante el uso de una pila) 
ante las siguientes situaciones:


a) cuando se alcanza una hoja de fallo 
  (Reev. AUTOMATICA).

b) cuando se alcanza una hoja de exito y 
   el usuario introduce ; (Reev. MANUAL).

Existen dos excepciones a este hecho:

1) Si el objetivo es basico (ground), solo se
  produce reevaluacion en el caso a), pues 
  obviamente en el b)  el sistema devuelve yes 
  y no precisa buscar nuevas hojas de exito 
  porque estas no aportan informacion relevante 
  (el objetivo no tiene variables).

2) Si aparece el predicado ! (corte), se 
  produce un tipo especial de reevaluacion, 
  que pasa, ya no al subobjetivo immediatamente 
  precedente, sino al que precede a este ultimo.

El corte admite las siguientes lecturas:

A) SEMANTICA:

A.1) La Sem. Declarativa (respuestas correctas) 
     no se altera pues el predicado ! siempre 
     se cumple (equivale a  true).

A.2) La Sem. Operacional se reduce porque el 
     predicado ! poda ramas sobre el arbol SLD 
     y el conjunto de soluciones Prolog puede
     disminuir.


B) COMPLETITUD:

B.1) La poda de ramas infinitas ayuda a 
     restaurar la  completitud perdida de Prolog 
     debido a la busqueda en profundidad.

B.2) En contrapartida, la incompletitd de Prolog 
     puede agravarse cuando se podan ramas de exito.
     En este caso, ni siquiera una búsqueda en 
     anchura garantizaria completitud total.


C) USO:

C.1) Ganancia en eficiencia ya que al reducirse 
     el espacio de busqueda se obtienen beneficios
     tanto en tiempo como en espacio.

C.2) Posibles efectos indeseados, perdida de 
     legibilidad y tambien de propiedades 
     declarativas (reversibilidad, completitud,
     correccion, etc..). El abuso del corte puede
     generar programas con mayor inspiracion 
     imperativa que declarativa.

------------------------------------------------


%%%%%%%%  DEFINICION DEL CORTE  %%%%%%%%%%%%%%%%

Es un predicado estandar que siempre se cumple
pero nunca se puede resatisfacer o reevaluar. 
El predicado padre de un corte es aquel que 
aparece en la cabeza de la clausula donde 
aparece !. Cuando se encuentra un corte como 
objetivo, desde ese momento el sistema se ve 
forzado a mantener todas las opciones hechas 
desde que se llamo al objetivo padre. Todas 
las demas alternativas se desechan. Por lo 
tanto cualquier intento de resatisfacer cualquier
objetivo entre el objetivo padre y el objetivo
de corte fracasará.


Ejemplo: 
.
.
 p:-....,q,...
.
.
 q:-a,b,!,c,d.
.
.

Si en algun momento al evaluar un objetivo 
cualquiera se obtiene alguna solucion por
aplicacion de las clausula anteriores, 
entonces para obtener mas soluciones se 
probaran con todas las clausulas que definen
c y d, pero una vez hecho esto, la reevaluacion
no reevalua usando nuevas clausulas de b ni a,
ni siquiera de q, sino que directamente se pasa
a nuevas clausulas de p.


---------------------------------------------


%%%%%%%%  USOS COMUNES DEL CORTE  %%%%%%%%%%


Aunque existen muchas y muy diferentes 
situaciones  donde el uso del corte puede 
ser mas o menos beneficioso, muchas de ellas
pueden verse como casos particulares de 
confirmacion de la eleccion de una regla,
combinacion con fail, o finalizacion de 
un algoritmo "comprobar+generar".


%----------------------------------------------------


A) CONFIRMACION DE ELECCION DE CLAUSULA

Version directa del factorial: el primer 
parametro siempre debe estar instanciado 
por el uso de <= e is.

*/

fact1(N,1):-N=<1.
fact1(N,M):-N1 is N-1,fact1(N1,M1),
		M is N*M1.

% Una vez que obtenemos la primera solucion, 
% el sistema no debe dar mas soluciones, lo
% que se consigue con un corte en el caso base.

fact2(N,1):-N=<1,!.
fact2(N,M):-N1 is N-1,fact2(N1,M1),
		M is N*M1.


% Este uso del corte puede evitarse 
% sustituyendolo por una aplicacion 
% adecuada de not

fact3(N,1):-N=<1.
fact3(N,M):-not(N=<1),N1 is N-1,
		fact3(N1,M1),M is N*M1.

% En este caso todavia se puede mejorar
% la implementacion cambiando not(N1=<1)
% por >. 


% En general, aunque el cambio de ! por
% not genera un programa mas legible y 
% seguro, tambien es mas ineficiente.


%---------------------------------------------


%B) COMBINACION CON fail

% Implementacion de la negacion en Prolog
% (predicado not o \+)

not(X):-X,!,fail.
not(_).

% Version inversa del factorial (el segundo
% parametro debe estar instanciado)

nat(0).
nat(X):-nat(Y),X is Y+1.

fact4(N,M):-nat(N),
		(fact2(N,M),!;N>M,!,fail).

% Observar las diferencias con:

fact5(N,M):-nat(N),test(N,M).

test(N,M):-fact2(N,M),!.
test(N,M):-N>M,!,fail.


% Una version alternativa del factorial 
% inverso sin uso de cortes puede obtenerse
% haciendo uso de parametros acumuladores.

fact6(N,M):-fact6(N,M,0,1).

fact6(N,M,N,M).
fact6(N,M,R,S):-	M>S,R1 is R+1,
			S1 is S*R1,fact6(N,M,R1,S1).
fact6(nada,M,_,S):-S>M.



%-------------------------------------------


% C) FINALIZAR "GENERAR+COMPROBAR"

% Este es el caso de los factoriales inversos
% fact4 y fact5, pero tambien de la siguiente 
% version de factorial inverso (basada en
% "comprobar+generar") que devuelve 'imposible'
% en caso de que no exista.

fact7(N,M):- nat(S),fact2(S,R),
		(R=M,N=S;R>M,N=imposible),!.


% Las versiones mas generales y reversibles
% del problema (donde ambos parametros pueden
% estar sin instanciar) pueden hacerse en 
% funcion tanto del factorial directo 
% como del inverso

fact8(N,M):-nat(N),fact2(N,M).
fact9(N,M):-nat(M),fact7(N,M).