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
FLUJO DE DATOS Y RECURSIÓN
En ésta lección hablaremos acerca del flujo de datos especialmente durante la manipulación con estructuras de datos recursivas. Recursión es una técnica básica que es usada para manipular datos para los cuales su tamaño no es conocido al comienzo (por otro lado iteración es probablemente más conveniente). Usualmente, tales datos son representados usando definición recursiva.
REPRESENTACIÓN UNARIA DE LOS NÚMEROS
PROLOG tiene su propia representación de los números. Sin embargo, para propósito de éste tutorial, definiremos otra representación de los números naturales. Ésta simple representación unaria nos ayudará a presentar un flujo de datos durante la recursión. Notar que es un ejemplo típico de definición recursiva donde la "semilla" (cero) es definida y otros elementos (números) son sucesivamente creados de elementos definidos previamente.
0 es representado como 0
N+1 es representado como s(X),donde X es una representación de N
La recursión puede ser naturalmente expresada en PROLOG (¿recuerdas la definición de último o miembro en la lección anterior?). Así, es fácil definir una prueba si una estructura dada es un número unario. Notar otra vez que el mismo procedimiento, es decir, num_unario, puede también ser usado para sucesivamente generar "todos" los número naturales. Intentalo.
num_unario(0).
num_unario(s(X)):-num_unario(X).
Ahora, la suma de dos números usando el predicado recursivo suma(X,Y,Z) (X+Y=Z).
suma(0,X,X). % 0+X=X
suma(s(X),Y,Z) :- suma(X,s(Y),Z). % (X+1)+Y=Z <== X+(Y+1)=Z
recursión ---^ ^--- acumulador
El predicado suma usa una estructura de datos llamada acumulador para acumular el subresultado durante el calculo recursivo. Mira el siguiente rastro (trace) del calculo para comprender la idea principal de acumulador.
?-suma(s(s(s(0))), s(0) ,Sum). ^ Sum=s(s(s(s(0))))
?-suma( s(s(0)) , s(s(0)) ,Sum). | Sum=s(s(s(s(0))))
?-suma( s(0) , s(s(s(0))) ,Sum). | Sum=s(s(s(s(0))))
?-suma( 0 ,s(s(s(s(0)))),Sum). | Sum=s(s(s(s(0))))
?-suma( 0 ,s(s(s(s(0)))),s(s(s(s(0))))). %copia acumulador a resultado.
^-- el resultado es acumulado aquí
Es también posible definir la operación suma sin acumulador usando composición de sustituciones.
suma2(0,X,X). % 0+X=X
suma2(s(X),Y,s(Z)): - suma(X,Y,Z). % (X+1)+Y=Z+1 <== X+Y=Z
^--- composición de sustituciones
Mira el siguiente rastro (trace) de ejecución para ver la diferencia entre acumulador y composición de sustituciones.
?-suma2(s(s(s(0))),s(0),S1). ^ S1=s(S2)=s(s(s(s(0))))
?-suma2( s(s(0)) ,s(0),S2). | S2=s(S3)=s(s(s(0)))
?-suma2( s(0) ,s(0),S3). | S3=s(S4)=s(s(0))
?-suma2( 0 ,s(0),S4). | S4=s(0)
?-suma2( 0 ,s(0),s(0)).______|
las sustituciones son compuestas aquí ----^
En este caso particular, la complejidad computacional de ambos enfoques es similar. Además, suma y suma2 son completamente declarativos y pueden ser usados para calcular suma de números también como la diferencia de números y, algunas restricciones, para generar todos los pares de números y, con algunas restricciones, generar todos los pares de números para los cuales la suma está dada (intenta ?-suma(X,Y,s(s(s(0)))).).
Siguiendo las cuatro cláusulas se muestra varias definiciones de resta (X,Y,Z) (X-Y=Z) usando suma y suma2 respectivamente.
resta1a(X,Y,Z):-suma(Y,Z,X).
resta1b(X,Y,Z):-suma(Z,Y,X).
resta2a(X,Y,Z):-suma2(Y,Z,X).
resta2b(X,Y,Z):-suma2(Z,Y,X).
Por supuesto, resta puede también ser definida desde cero usando recursión.
resta(X,0,X). % X-0=X
resta(s(X),s(Y),Z) :- resta(X,Y,Z). % (X+1)-(Y+1)=Z <== X-Y=Z
Compáralo con el próximo procedimiento resta2 el cual está basado sobre otra característica de la operación resta. Notar que resta2 requiere la existencia de solución (intenta ?-resta2(0,s(0),Z). ¿Qué sucede?)
resta2(X,X,0). % X-X=0
resta2(X,Y,s(Z)) :- resta(X,s(Y),Z). % X-Y=Z+1 <== X-(Y+1)=Z
LISTAS (continuación)
Lista es otra estructura de datos recursiva típica. Puede ser definida de la siguiente manera:
[] es una lista
[H|T] es una lista si T es una lista y H es un termino (miembro de la lista).
Algunos ejemplos de las operaciones con listas pueden ser encontrados en la lección anterior. Recuerda que la definición de agregar presentada allá usa composición de sustituciones. En el caso de agregar no es natural usar el acumulador. La definición de la operación borrar(X,L,DL) (borra un elemento X dado desde la lista L, la lista resultante es DL) es también más natural usar composición de sustituciones. Compara los siguientes dos procedimientos: borrar es definido usando composición de sustituciones mientras que borrar2 es definido usando acumulador.
borrar(X,[X|T],T).
borrar(X,[Y|T],[Y|NT]) :- borrar(X,T,NT).
borrar2(X,L,DL) :- del2(X,L,[],DL).
del2(X,[X|T],A,DL) :- agregar(A,T,DL).
del2(X,[Y|T],A,DL) :- del2(X,T,[Y|A],DL).
En este caso particular, la definición de borrar es también más efectiva que borrar2 (omitimos agregar).
Los ejemplos de agregar y borrar no implican que la técnica de acumulador no es útil. Lo opuesto es verdad y, en muchos casos, es más natural y efectivo usar acumulador. El siguiente ejemplo es el caso donde usar acumulador es más efectivo computacionalmente que la composición de sustituciones. El procedimiento revertir revierte una lista dada. La definición de revertir parece natural pero no es efectivo debido a que agrega un elemento al final de la lista usando agregar en cada paso. revertir2, el cual usa acumulador, es más eficiente.
revertir([],[]).
revertir([H|T],Rev):-revertir(T,RT),agregar(RT,[H],Rev)
revertir2(L,RL):-rev_acc(L,[],RL).
rev_acc([],Acc,Acc). % La lista revertida está en Acc
rev_acc([H|T],Acc,Rev):-rev_acc(T,[H|Acc],Rev).
% Acc contiene parte de la lista revertida hasta ahora.
Algunas veces, es posible combinar ambas técnicas acumulador y composición de sustituciones para alcanzar la solución. Mira la definición de partir la cual también explota la unificación para probar si ambas mitades tienen la misma longitud. Sin embargo, probar la longitud en cada paso, la cual es ejecutada por la primera cláusula hv, no es muy efectiva y por lo tanto partir no es realmente rápido.
partir(L,A,B) :- hv(L,[],A,B).
hv(L,L,[],L).
hv([H|T],Acc,[H|L],B) :- hv(T,[_|Acc],L,B).
La siguiente definición de partir2 es más eficiente que el partir original. partir2 también usa unificación para distribuir la lista en dos mitades pero es hecho una vez al final del calculo solamente. Compare partir y partir2 sobre ejemplos grandes (una lista con 100 000+ miembros) para ver la diferencia real.
partir2(L,A,B) :- hv2(L,L,A,B).
hv2([],R,[],R).
hv2([_,_|T],[X|L],[X|L1],R) :- hv2(T,L,L1,R).
¿ Sabes como hacer el procedimiento hv2 aún más eficiente? Hay un cambio pequeño.
Para terminar la lección de hoy, hay dos ejemplos de "vacaciones". Esperamos que estén claros cada uno de ellos. Compare subpart con la definición de sublista de la sección anterior.
subpart([],_).
subpart([H|T],[H|T2]) :- subpart(T,T2).
subpart(L,[H|T]) :- subpart(L,T).
par_impar(L,E,O) :- impar(L,E,O).
impar([],[],[]).
impar([H|T],E,[H|O) :- par(T,E,O).
par([],[],[]).
par([H|T],[H|E],O) :- impar(T,E,O).
Otra solución a la distribución par-impar de una lista.
par_impar2([],[],[]).
par_impar2([H|T],E,[H|O]):-par_impar2(T,O,E).
La Recursión es poder.