UNIVERSIDAD DE LOS ANDES
COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A DISTANCIA
MERIDA - VENEZUELA
Curso de Lógica y Matemática
Postgrado en Modelado y Simulación de Sistemas
MANUAL de PROLOG - BRATKO
PRIMERAS ESTRUCTURAS DE DATOS EN PROLOG
Esta lección cubre estructuras de datos en PROLOG. La estructura de datos básica en PROLOG es el término, el cual es expresado como: nombre(argumentos...). Si el número de argumentos es cero entonces estamos hablando de un átomo. Un tipo especial de átomo es el número.
ESTRUCTURAS BÁSICAS (en el ejemplo de las fechas)
En esta sección, introducimos una estructura de datos fecha(Dia,Mes,Año) que representa la fecha. Primero necesitamos un constructor de la estructura de datos fecha que hace la estructura de datos de día, mes y año:
hacer_fecha(D,M,A,fecha(D,M,A)).
Segundo, definimos las funciones para accesar los componentes de la estructura de datos de la siguiente forma:
obtener_año(fecha(_,_,A),A).
obtener_mes(fecha(_,M,_),M).
obtener_dia(fecha(D,_,_),D).
obtener_xxx puede ser usado para probar o generar el componente correspondiente de la estructura de datos, pero no puede ser usado para colocar el valor de la componente. Así, tenemos que definir colocar_xxx para colocar valores a los componentes de la estructura de datos fecha.
colocar_año(A,fecha(D,M,_),fecha(D,M,A)).
colocar_mes(M,fecha(D,_,A),fecha(D,M,A)).
colocar_dia(D,fecha(_,M,A),fecha(D,M,A)).
Ahora, es fácil encontrar el "mismo" día en año próximo o anterior respectivamente usando las funciones obtener y colocar.
año_proximo(Hoy,ProximoAño):-
obtener_año(Hoy,A), NA is A+1,
colocar_año(NA,Hoy,ProximoAño).
año_anterior(Hoy,AnteriorAño):-
obtener_año(Hoy,A), PA is A-1,
colocar_año(PA,Hoy,AnteriorAño).
Notar, que la definición siguiente de año_anterior usando año_proximo no es correcta. ¿Tú sabes Por Qué?
año_anterior(Hoy,AnteriorAño):- año_proximo(AnteriorAño,Hoy)). % incorrrecto
Encontrar el año próximo es relativamente fácil pero ¿Qué sucede al encontrar día próximo, es decir, mañana?. Estudiar el siguiente programa para encontrar donde los problemas posibles están ocultos. La definición de probar dia_correcto sigue en la próxima sección que cubre el trabajo con listas.
mañana(Hoy,Tomorrow) :-
obtener_day(Hoy,D), ND is D+1,
colocar_day(Hoy,ND,Tomorrow),
fecha_correcta(Mañana).
%el día dentro del mes,es decir,no el último día del mes
mañana(Hoy,Mañana):-
obtener_mes(Hoy,M), NM is M+1,
colocar_mes(Hoy,NM,Tmp),colocar_dia(Tmp,1,Mañana), fecha_correcta(Mañana).
% Ultimo día del mes
mañana(Hoy,Mañana):-
obtener_año(Hoy,A), NA is A+1,
hacer_fecha(NA,1,1,Mañana).
% Último día del año
Notar que también es posible y quizás más razonable encapsular la prueba fecha_correcta en las definiciones de hacer_fecha y colocar_xxx.
LISTAS
Una lista es estructura de datos ampliamente usada y construida en PROLOG. Es todavía un término, ejemplo, [1,2,3] es equivalente a '.'(1,'.'(2,'.'(3,nulo))). Las siguientes funciones permiten accesar los elementos de la lista.
cabeza(C,[C|_]).
cola(L,[_|L]). % L es una lista
Es fácil accesar el primer elemento de la lista, es decir, la cabeza. Sin embargo, encontrar el último elemento es un proceso que consume tiempo ya que uno tiene que recorrer la lista completa para encontrarlo. Notar que los siguientes "procedimientos" pueden ser usados para encontrar el primero/último elemento de la lista. Podría aún ser usado para generar una lista con el primero/último elemento dado.
primero(P,[P|_]). % El mismo como cabeza
ultimo(U,[U]).
ultimo(U,[C|L]):- ultimo(U,L).
La misma conclusión se mantiene para encontrar prefijo y sufijo respectivamente. De nuevo, el mismo procedimiento puede ser usado para probar o generar prefijo/sufijo respectivamente también como generar una lista con el prefijo/sufijo dado. Pruébalo.
prefijo([],_).
prefijo([C|L1],[C|L2]):-prefijo(L1,L2).
sufijo(S,S).
sufijo([C|T],L):-suffix(T,L).
Probar membresía es un método importante para trabajar con listas. La definición de PROLOG de miembro puede probar la relación de membresía también como generar miembros sucesivos de una lista. Una función similar, miembro_nth, puede también ser usado para probar o generar el miembro n-th de una lista. Sin embargo, no puede ser usado para contar un número de secuencia de un elemento dado (definir la función que cuenta un número de secuencia de un elemento dado como tarea).
miembro(X,[X|_]).
miembro(X,[_|T]):-miembro(X,T).
Miembro_nth(1,[M|_],M).
Miembro_nth(N,[_|T],M):-N>1,N1 is N-1,miembro_nth (N1,T,M).
Otra función popular sobre listas es agregar el cual agrega una lista a otra lista. Puede también ser usada para separar listas. (ver la siguiente definición de prefijo y sufijo). Este procedimiento es uno de los más representativos en la programación lógica. Sugerimos que se le compare con su equivalente en otros lenguajes (Note que no es solamente agregar una lista a otra).
agregar([],L,L).
agregar([C|T],L,[C|LT]):-agregar(T,L,LT).
Ahora, las relaciones prefijo y sufijo pueden ser fácilmente redefinidas usando agregar:
prefijo(P,L):-agregar(P,_,L).
sufijo(S,L):-agregar(_,S,L).
Agregar puede ser exitosamente usado en muchas otras operaciones con listas incluyendo probar (o generar) sublistas. La siguiente regla explota otra vez el carácter declarativo de PROLOG.
sublista(S,L):-agregar(_,S,P),agregar(P,_,L).
Hay (al menos) dos otras formas de como definir sublista, ejemplo, usando las relaciones prefijo y sufijo. Todas estas definiciones son equivalentes. Sin embargo, el procedimiento sublista3 es probablemente lo más cercano al estilo de programación tradicional (no declarativo) ya que usa la técnica conocida como "floating window".
sublista2(S,L):-prefijo(P,L), sufijo(S,P).
sublista3(S,L) :- prefijo(S,L).
sublista3(S,[_|T]) :- sublista3(S,T).
REGRESO AL EJEMPLO DE FECHA
Vamos a retornar a nuestro ejemplo de la estructura de datos fecha. Ahora, vamos a definir la prueba fecha_correcta usando listas.
Primero, agregamos dos hechos a la base de datos PROLOG con la distribución de días:
año(regular,[31,28,31,30,31,30,31,31,30,31,30,31]).
año(bisiesto,[31,29,31,30,31,30,31,31,30,31,30,31]).
Entonces, preparamos la prueba para año bisiesto (versión simplificada):
es_año_bisiesto(A):-
Z is A mod 4, Z=0. % cada cuatro años es bisiesto(simplificada)
Finalmente, es posible probar la correctitud de fecha:
fecha_correcta(fecha(D,M,A)):-
mes_correcto(M),
dia_correcto(D,M,A).
mes_correcto(M):- M>0, M<13.
dia_correcto (D,2,A):- % la única diferencia entre años bisiesto y regular es en febrero
es_año_bisiesto(A),
probar_dia_del_año(D,2,bisiesto).
dia_correcto (D,M,A):-
M\=2,
probar_dia_del_año(D,2,regular).
probar_dia_del_año (Tipo,M,D):-
año(Tipo,Dias),
miembro_nth(M,Dias,Max),
D>0, D=<Max.
Notar, que la definición anteriorde dia_correcto asume que la única diferencia entre años regular y bisiesto es el número de días en febrero el cual es más alto en años bisiestos.