Prolog

PROLOG
*RECURSIVIDAD
Para definir reglas más generales y flexibles, es necesario un mecanismo adicional.
Para ello se utilizará el concepto de recursividad.
Para definir el concepto antecesor_de puede definirse de una forma iterativa:

antecesor_de(X,Y):-padre_de(X,Y). %padre
antecesor_de(X,Y):-padre_de (X,Z), padre_de (Z,Y). %abuelo
antecesor_de(X,Y):-padre_de (X,Z1). %bisabuelo:-padre_de (Z1,Z2).
:-padre_de (Z2,Y).
antecesor_de(X,Y):-padre_de (X,Z1). %tatarabuelo
:-padre_de (Z1,Z2).
:-padre_de (Z2,Z3).
:-padre_de (Z3,Y).
…
Este mecanismo no es eficiente, dado que no nos permite generalizar fácilmente
el concepto de antecesor. Prolog permite utilizar definiciones recursivas, que
resuelven el problema de forma elegante.
antecesor_de(X,Y):-padre_de(X,Y).antecesor_de(X,Y):-padre_de (X,Z), antecesor (Z,Y).
Problemas con el uso de la recursividad
Uno de los peligros que conlleva la recursividad, es la de realizar definiciones
circulares o que el intérprete de Prolog no sea capaz de resolver.
antecesor_de(X,Y):-antecesor_de(X,Y)
Esta cláusula es declarativamente correcta, pero el intérprete de Prolog no podrá
resolverla nunca y se quedaráatrapado en un bucle infinito.
por ejemplo si se define la siguiente base de hechos sobre las amistades de una
persona:
amigos(pedro,antonio).
amigos(pedro,flora).
……
amigos(Fernando,pedro).
Si consideramos que el concepto amistad tiene una relación conmutativa,
entonces posiblemente nos interesaría definir la relación de amistad inversa o
complementaria:

amigos(X,Y):-amigos(X,Y). %Peligro ,recurrencia

Esta definición aparentemente lógica provoca un error. La forma correcta de
definirlo sería a través de un nuevo predicado:
son_amigos(X,Y):-amigos(X,Y).
son_amigos(X,Y):-amigos(Y,X).





BACKTRACKING
Supongamos que disponemos de dos predicados p/1 y q/1 que tienen varias soluciones (el orden es significativo):
p(1) tiene éxito.
p(2) tiene éxito.
q(2) tiene éxito.No hay más soluciones que éstas.
Y a continuación consideramos la siguiente secuencia: p(X),q(X).
Ahora ejecutamos la secuencia tal y como explicamos en la lección anterior:
Ejecutamos p(X) con éxito y la variable queda ligada al valor 1 (primera solución).
Ejecutamos q(X), pero la variable ya no esta libre, luego estamos ejecutando realmente q(1). El predicado falla porque no es una de sussoluciones.
La conjunción falla.
El resultado ha sido fallo, pero nosotros sabemos que para X = 2 existe una solución para la conjunción.
Aquí es donde entra en juego el backtracking. Esto consiste en recordar los momentos de la ejecución donde un objetivo tenía varias soluciones para posteriormente dar marcha atrás y seguir la ejecución utilizando otra solución como alternativa.
Elbacktracking funciona de la siguiente manera:
Cuando se va ejecutar un objetivo, Prolog sabe de antemano cuantas soluciones alternativas puede tener. En un futuro capítulo veremos cómo puede llegar a saber esto. Cada una de las alternativas se denomina punto de elección. Dichos puntos de elección se anotan internamente y de forma ordenada. Para ser exactos, se introducen en una pila.
Se escoge el primerpunto de elección y se ejecuta el objetivo eliminando el punto de elección en el proceso.
Si el objetivo tiene éxito se continúa con el siguiente objetivo aplicandole estas mismas normas.
Si el objetivo falla, Prolog dá marcha atrás recorriendo los objetivos que anteriormente sí tuvieron éxito (en orden inverso) y deshaciendo las ligaduras de sus variables. Es decir, comienza el backtracking.Cuando uno de esos objetivos tiene un punto de elección anotado, se detiene el backtracking y se ejecuta de nuevo dicho objetivo usando la solución alternativa. Las variables se ligan a la nueva solución y la ejecución continúa de nuevo hacia adelante. El punto de elección se elimina en el proceso.
El proceso se repite mientras haya objetivos y puntos de elección anotados. De hecho, se puede...