Programación. ADA. Tipos abstractos de datos

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.