Concepto de abstracción
El concepto de
abstracción en el proceso de compresión de un problema, lleva consigo el
destacar los detalles importantes e ignorar los irrelevantes.
La abstracción
es usada constantemente a la hora de programar.
Un claro ejemplo
de ello es el uso de funciones y procedimientos. Ambos, ocultan los detalles
sobre como se consigue el resultado que ofrecen y desde fuera son vistos como
lo que hacen y no el cómo lo consiguen hacer.
La abstracción
siempre lleva asociada la ocultación de información.
Se separa el QUÉ
del CÓMO.
O dicho de otra
manera, se separa la especificación (el qué) de la implementación (el cómo).
Abstracción de acciones
El uso de
procedimientos y funciones nos permite abstraernos de las instrucciones que
realmente se están ejecutando para conseguir los resultados que obtenemos.
Tenemos una
acción (en el caso de procedimientos) o valor (en el de las funciones) virtual
parametrizada.
Se está
ocultando información: los datos locales y la secuencia de instrucciones del
subprograma.
Recordemos, se
separa la especificación (el qué: lo que hace la función o el procedimiento) de
la implementación (el cómo: las instrucciones concretas que lo hacen).
Tipo abstracto de datos (TAD)
Un TAD es una
colección de valores y de operaciones definidos mediante una espeficación
independiente de cualquier representación.
La programación
con TADs requiere dos pasos.
è Definición del tipo. Establecer los valores que puede tomar el tipo y las
operaciones necesarias para manipular los valores y especificar su interfaz.
Esto tiene dos partes:
·
Parte sintáctica. Cómo se llama la operación,
si es una función o un procedimiento, que parámetros tiene, en que orden y de
qué tipo.
·
Parte semántica. Qué hace la operación con los
parámetros de entrada, cómo modificar los de salida y qué devuelve (si se trata
de una función). En otras palabras, para qué sirve esa operación y cuál es su
comportamiento.
è Implementación del tipo. Elegir la representación de los valores e implementar las
operaciones
Encapsulación
El concepto
fundamental subyacente bajo la programación de TADs es la encapsulación.
La encapsulación
consiste basicamente en:
è La privacidad de la
representación (el usuario no conoce los detalles del tipo)
è La protección del tipo (el
usuario sólo puede utilizar las operaciones previstas)
Diseño modular
La programación
a gran escala exige la partición del código en módulos.
Un módulo es una
unidad del programa que puede ser desarrollada independientemente del resto.
La
descomposición en módulos debe cumplir unos requisitos.
è Que cada módulo tenga una
conexión mínima con el resto. La interfaz
è Que la mayor parte de los
cambios del programa afecten sólo a un número pequeño de módulos.
è Que el tamaño de cada módulo
sea adecuado (si es muy grande es dificil hacer cambios, si es muy pequeño es
costoso por los trabajos adicionales de especificación, documentación, control
de versiones…)
Un TAD puede
encapsularse en un módulo.
è La interfaz es reducida. El
nombre del tipo y los encabezamientos de las operaciones.
è Puede cambiarse la
implementación independientemente (para mejorarla, por ejemplo), siempre y
cuando mantengamos la interfaz.
El tamaño del
módulo suele ser suficientemente grande (implementación de las operaciones).
TADs como base del diseño modular
El uso de
procedimientos y funciones (diseño descendente) facilita la programación a
pequeña escala (programas pequeños).
Sin embargo esto
es insuficiente para la programación a gran escala. Es necesario utilizar el
diseño modular.
Programas =
datos + algoritmos
Programas =
datos + (algoritmos de control)
Programas =
(datos + algoritmos de datos) + algoritmos de control
Programas = TADs
+ algoritmos de control
Hasta ahora
conocíamos la forma de abstraer algoritmos (mediante funciones y procedimientos
que podemos agrupar en módulos). Ahora conocemos la forma de abstraer datos
(mediante TADs que también pueden constituir módulos).
TADs genéricos y algoritmos genéricos
Se pueden
definir TADs genéricos (o tipos parametrizados) con algunas características
indefinidas.
Estas
características pueden ser concretadas posteriormente de diversas formas según
las necesidades, obteniendo ejemplares de TADs concretos distintos.
La genericidad
facilia la reutilización de algoritmos. Por ejemplo, si se implementa un
algoritmo de ordenación de vectores, los tipos de datos de los índices y de los
elementos del vector no afectan al algoritmo, siempre y cuando se disponga de
una función de orden que diga si un elemento es mayor que otro.
Módulo de declaración
ordenacion_g.ads
generic
type ind is (<>); -- cualquier
tipo discreto
type elem is private; -- cualquier
tipo
type vector is array (ind range
<>) of elem;
with funcion “>”(a,b:elem) return
boolean;
package
ordenacion_g is
procedure ordena (v:in out vector);
end; -- del módulo de declaración
Módulo de implementación ordenacion_g.adb
package
body ordenacion_g is
procedure ordena (v: in out vector)
is
i,j:ind; m,t:elem;
n:integer;
begin
--iniciailización
i:=v'first;
j:=v'last;
n;=ind'pos(i)
n=n+ind'pos(j)
n=n/2;
m=v(ind'val(n));
-
partición del vector en dos
while
i<=j loop
while
n>v(i) loop
i=ind'succ(i);
end
loop;
while
v(j)>m loop
j:=ind'pred(j);
…
end ordenacion_g
Uso desde un programa de un ejemplar concreto de vector
with
ordenacion_g;
procedure
mi_programa is
type color is (rojo, azul, gris);
type dia is (lu,ma,mi,ju,vi,sa,do);
type vect is array (day range
<>) of color;
x:vect(ma..vi):=(gris,azul,rojo,gris);
package o is new ordenacion_g(dia,color,vect,”>”);
begin
…
o.ordena(x);
…
end mi_programa;
¿Qué gano además con los TADs y la modularidad?
Pues oculto
totalmente como se representa la información y cómo se implementan los
algoritmos.
Podría cambiar
en el futuro ambas cosas, y mientras mantenga la interfaz, el usuario del
módulo ni lo notará.
De esta manera,
podría hacer una versión rápida que funcionara, y después hacer versiones
sucesivas que fueran refinando y mejorando las anteriores, especialmente en
cuanto a eficiencia, funcionalidad o capacidad.
Ejemplo. Una pila
Por ejemplo
supongamos que tengo un problema para el que necesito una pila, y me urge tener
una pila disponible para hacer pruebas, porque lo importante es probar el
problema en sí mismo.
De hecho, el
problema lo va a resolver otra persona, a mi me encargan que tenga cuanto antes
una pila operativa… Y yo no sé ni lo que es un puntero.
Pila. La interfaz
Lo más
importante es que yo tenga claro lo que es una pia, aunque no tenga muy claro
cómo implementarla, y que el que la va a usar también lo tenga claro (la
implementación a él le va a dar igual completamente, a mi no). Y que lo que él
va a usar es exactamente lo mismo que yo voy a implementar.
Es decir, hace
falta definir antes de empezar a trabajar cada uno por su lado, que operaciones
va a hacer, que atributos van a tener, de qué tipo, en qué orden y qué hace
exactamente cada operación y en qué condiciones funciona.
Podrían ser las
siguientes:
-
Crear pila: à Pila
-
Apilar: Pila elemento à Pila
-
Parcial desapilar: Pila à Pila
-
Parcial cima: Pila à Elemento
-
esVacia: Pila à Booleano
Especificación formal
especificación pila
usa
booleanos
parametro
formal
generico
elemento
generico
pila
operaciones
creaPila:->pila
Crear pila: → pila
apilar: pila elemento → pila
parcial desapilar:
pila → pila
parcial cima: pila →
elemento
esVacia: pila → booleano
dominios de definicion p:pila, e:elemento
desapilar(apilar(p,e))
cima(apilar(p,e))
ecuaciones p:pila, e:elemento
desapilar(apilar(p,e))=e
cima(apilar(p,e))=e
esVacia(creaPila)=verdad
esVacia(apilar(p,e))=falso
fin especificación
Implementación estática
Mientras pienso
en cómo dar una solución definitiva al problema que tengo entre manos (y
mientras me estudio cómo funcionan los punteros en el lenguaje de programación
en el que tengo que hacer el desarrollo), lo que voy a hacer es montar algo que
funcione, aunque sea una solución de andar por casa, ya que total, nadie sabrá
jamás que he hecho eso, y mi jefe estará contento porque el otro programador tendrá
en dos horas una pila operativa para hacer las pruebas sobre ella.
Así que sin más
puedo simular una pila conun vector con espacio para un número máximo de
elementos, y un contador cima que me dice hasta dónde lo he llenado.
Implementación dinámica.
Luego con
tranquilidad, cuando ya domine los punteros, desarrollo en los días siguientes
una pila “de verdad”.
Sin más que
mantener la interfaz, el otro programador ni se enterará del cambio.
Esta pila por
supuesto tendrá sus nodos y sus punteros al nodo siguiente, y todo lo que yo
estime necesario.
Si en el futuro
quiero mejorar alguna función o procedimiento, haciendo una nueva versión
mejorada de la pila, siempre y cuando mantenga la interfaz, podré hacerlo sin
ningún problema, sin que el otro programador tenga que modificar ni una línea,
y sin que ni siquiera se llegue a enterar del cambio, ya que él no apreciará
diferencia alguna (salvo posiblemente en capacidad o eficiencia).
Es decir:
Pilas:
è Implementación estática. Un vector y un entero que diga que componente es la cima
è Implementación dinámica. Colección de nodos enlazados mediante punteros. Se inserta
siempre por el principio y un puntero apunta siempre a la cima (que es el
principio).
Cola:
è Implementación estática. Vector circular (el siguiente elemento del últmo es el
primero) y dos índices que digan que componente son la primera y última.
è Implementación dinámica. Nodos enlazados por punteros (uni o bidireccionalmente
según necesidades) y dos punteros que apuntan al primero y último.
