PDF de programación - Capitulo 4 - Prolog

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.12 – Recursividad

Escuela de Ingeniería Informática

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.12 – Recursividad

Escuela de Ingeniería Informática

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:

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).
En vez de:
%padre
antecesor_de(X,Y):-padre_de(X,Y).
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).

:-padre_de (Z1,Z2).
:-padre_de (Z2,Z3).
:-padre_de (Z3,Y).
…

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

:-padre_de (Z1,Z2).
:-padre_de (Z2,Z3).
:-padre_de (Z3,Y).
…

%tatarabuelo

%tatarabuelo

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

Escuela de Ingeniería Informática

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.12.1 – Problemas con el uso de la recursividad

4.12.1 – Problemas con el uso de la recursividad

Escuela de Ingeniería Informática

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.

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:

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:

Esta definición aparentemente lógica provoca un error. La forma correcta de
definirlo sería a través de un nuevo predicado:

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.12.2 – Directivas para el uso de la recursividad

Escuela de Ingeniería Informática

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.13 – Mecanismo de resolución

Escuela de Ingeniería Informática

El siguiente conjunto de directivas pueden utilizarse para lograr que la ejecución
de nuestro programa Prolog sea lo más eficiente posible.

Primero los objetivos más sencillos

Ordenación de Cláusulas
1º las más específicas.
2º las más generales (con recursividad).
antecesor_de(X,Y):-padre_de(X,Y).
antecesor_de(X,Y):-padre_de (X,Z), antecesor (Z,Y).
Ordenación de Términos
1º los términos más específicos.
2º los términos más generales (recursivos).
antecesor_de(X,Y):-padre_de (X,Z), antecesor (Z,Y).

Prolog utiliza un mecanismo conocido como Resolución lineal con unificación
para resolver las preguntas que se le plantean.
El mecanismo consiste en realizar una búsqueda en profundidad y retroceso
(backtracking) tratando de unificar la cláusula objetivo con las contenidas en la
base de hechos, hasta lograr alcanzar la cláusula vacía.
1º Se extrae la primera meta eliminándola de la lista.
2º Mientras sea posible:
3º Buscar un hecho o una regla que satisfaga la meta.
4º Si se encuentra:
5º Si ListaMetas no está vacía llamar al procedimiento de búsqueda de forma
recursiva con ListaMetas y las variables equiparadas.
6º Si ListaMetas está vacía provocar un retorno con las metas satisfechas y las
variables equiparadas.
7º Si hay solución de las metas al volver de la llamada en 5º, provocar un retorno
con las soluciones.
8º En caso contrario, seguir en bucle, paso 3º.
9º Si no se ha encontrado solución alguna, provocar un retroceso, e.d. un retorno
sin solución.

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

1

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.13 – Mecanismo de resolución

Escuela de Ingeniería Informática

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.14 – Listas

Escuela de Ingeniería Informática

ListaMetas = { peligroso(X), grande(X) }
Resultado = Proc_Busqueda (ListaMetas, X)

Pmeta = primera (ListaMetas) = peligroso(X)
ListaMetas = resto (ListaMetas) = { grande(X) }
Mientras sea posible

peligroso(zorro).
peligroso(oso).
grande(oso).
astuto(zorro).

?-peligroso(X), grande(X).

Primer hecho: ¿peligroso(zorro) satisface PMeta?,si;
Resultado = Proc_Busqueda (ListaMetas, x = zorro)
PMeta = primera (ListaMetas) = grande(X), X = zorro.
ListaMetas = resto (ListaMetas) = { }
Mientras sea posible

Primer hecho: ¿grande(oso) satisface PMeta?, no;
Retroceso sin solución para grande(X).

Resultado = Proc_Busqueda (ListaMetas) = False.
Siguiente hecho: ¿peligroso(oso) satisface PMeta?, si;
Resultado = Proc_Busqueda (ListaMetas, X = oso)

PMeta = primera (ListaMetas) = grande(X), X = oso.
ListaMetas = resto (ListaMetas) = { }
Mientras sea posible

Primer hecho: ¿grande(oso) satisface PMeta?, si;
ListaMetas vacia
Provocar retorno con Solución { X = oso }

Provocar retorno con Solución { X = oso }

Imprimir Solución X = oso.

Una lista es una secuencia ordenada de elementos que pueden tener cualquier
longitud. Los elementos de una lista pueden ser cualquier tipo de términos
(constantes, variables o estructuras), o incluso otra lista.
Una lista está formada por dos elementos: la cabeza (primer elemento de la
lista) y la cola (resto de elementos de la lista).

• [a, b, c] Lista con los tres elementos a, b y c
• [ ] Lista vacía.
• [a | L] Lista con el elemento a en la cabecera y el resto en la variable L (cola).
• [a, b | L] Lista con los elementos a y b en la cabecera y el resto en la variable L
(cola).
• [X | L] Lista con el primer elemento instanciado en la variable X y el resto en la
variable L (cola).
• [X, Y | L] Lista con el primer elemento instanciado en la variable X, el segundo en
Y y el resto en la variable L (cola).
• [X|_] Lista con el primer elemento instanciado en la variable X
• [_|L] Lista con el resto en la variable L.

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.14.1 – Manejo de listas

Escuela de Ingeniería Informática

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.14.1 – Manejo de listas

Escuela de Ingeniería Informática

Algunos predicados útiles para el manejo de listas:

longitud([ ], 0).
longitud([X | Xs], N) :- longitud(Xs, N1), N is N1+1.

pertenece(X, [X|_]).
pertenece(X, [_|L]) :- pertenece(X, L).

concatena([ ],L,L).
concatena(L,[ ],L).
concatena([X|L1],L2,[X|L3]):-concatena(L1,L2,L3).

ultimo([X],X).
ultimo([_|T],X):-ultimo(T,X).

vecinos(X,Y,[X,Y|_]).
vecinos(X,Y,[_|Z]):-vecinos(X,Y,Z)

agregar(X,[],[X]).
agregar(X,[X|T],[X|T]).
agregar(X,[H|T],[X,H|T]):-X<H.
agregar(X,[H|T],[H|L]):-agregar(X,T,L).

elimina(X,[X|C],C).
elimina(X,[Y|C1],[Y|C2]) :- elimina(X,C1,C2).

ordenada([ ]).
ordenada([X]).
ordenada([X,Y|T]):-X<Y,ordenada([Y|T]).

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.14.2 – Ordenamiento de listas

Inserción

Escuela de Ingeniería Informática

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.14.2 – Ordenamiento de listas

Mezcla (mezcla dos listas ordenadas)

Escuela de Ingeniería Informática

ordenains([ ],[ ]).
ordenains([X|Y],Z):-ordenains(Y,W),agregar(X,W,Z).

Quicksort

particion(X,[Y|Ys],[Y|Ps],Gs):-Y<X,particion(X,Ys,Ps,Gs).
particion(X,[Y|Ys],Ps,[Y|Gs]):-Y>=X,particion(X,Ys,Ps,Gs).
particion(X,[ ],[ ],[ ]).

quicksort([ ],[ ]).
quicksort([X|Xs],Ys):-particion(X,Xs,Ps,Gs),quicksort(Ps,PsO),quicksort(Gs,GsO),
concatena(PsO,[X|GsO],Ys).

mezcla(Xs,[ ],Xs).
mezcla([ ],[Y|Ys],[Y|Ys]).
mezcla([X|Xs],[Y|Ys],[X|Zs]):-X<Y,mezcla(Xs,[Y|Ys],Zs).
mezcla([X|Xs],[Y|Ys],[Y|Zs]):-X>=Y,mezcla([X|Xs],Ys,Zs).

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

Desarrollado por
Ricardo Soto De Giorgis

Escuela de Ingeniería

Informática

INF 152 – Programación en Lógica

2

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.15 – Predicados sobre estructuras

Functor(estructura, functor, número de argumentos)

Escuela de Ingeniería Informática

PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO

Capítulo 4 – PROLOG

4.15 – Predicados sobre estructuras

Escuela de Ingeniería Informática

Arg(N,estructura,A)
Permite retornar uno de los parámetros presentes en una estructura.

3 ?- functor(a*b,F,N).

F = *
N = 2

4