Tema 8c Tipos abstractos de datos

(continuación de EDD con una visión desde Ada)

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 cómo 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 otro modo, 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 caso de 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 que: hace la función o el procedimiento) de la implementación (el cómo: las instrucciones concretas que lo hacen).

¿Abstracción de datos?

¿Podemos hacer lo mismo que hacemos con las acciones de un programa, pero aplicado a los datos?

Es decir, ¿Podemos separar especificación de implementación?

Claro, jde eso va este tema. Si no, ¿para qué tanto rollo?

Al igual que para acciones tenemos los procedimientos, para expresiones las funciones, para datos tenemos los Tipos Abstractos de Datos.

Tipo Abstracto de Dato (TAD)

Un TAD es una colección de valores y de operaciones definidos mediante una especificació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, qué parámetros tiene, en qué orden y de que tipo.

     * Parte semántica: qué hace la operación con los parámetros de entrada, cómo modifica 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 con TADs es la encapsulación.
La encapsulación consiste básicamente 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 en gran escala exige la participació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 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 (mediantes TADs que también pueden constituir módulos).

Punteros Ada

Punteros en Ada

type celda;

type enlace is access celda;

type celda is

            record

                        valor:intenger;

                        siguiente:enlace;

            end record;

e:enlace;

e:=new celda;

e.valor:=13;

e:=new celda'(13, null);

e:=new celda'(7,e); (dibujo)

e,f:enlace;

f:=new celda'(13, null);

e:=f;

f:=new celda'(13, null);

e:=new celda;

e.all:=f.all;

Liberación de memoria de datos inaccesibles: suele proporcionarla la implementación.

También puede hacerlo el programador:

witch unchecked_dealloacation;

produce disponer is new

            uncheked_dealocation(celda, enlace);

e:enlace;

...

disponible(e);

Modulo de declaración

conjuntos.ads > expecificación

package conjuntos is

            type conjcar is private;      //limitado

            procedure vacio (A:out conjcar);

            function esVacio (A: in conjcar)

                        return boolean;

            procedure poner (c:in character;

                        A:in out conjcar);

            ...

            private

            type elementos is array .....

            package ....

            ¿?¿? // recordar que os sube el pdf. No he sabido tomar los apuntes correctamente de este apartado.

           

Algoritmos genéricos

Tipos como parámetros

generic

            type item is private;

procedure conjear (x,y:in out item);

produce canjear (x, y:in out item) is

            aux:item;

begin

            aux:=x;

            x:=y;

            y:=aux;

end;

permite reutilizar el software

....

Otras especificaciones de tipos genéricos:

type t is private; > tipo

type t is limited private;

Hoy esta yendo muy rápido para pillar apuntes... :(

Sintaxis en Ada 2

Vectores

Definiciones restringidas

type t1 is array (1..10) of boolean; //tipo t1 es un vector de 10 posiciones de booleanos;

type t2 is array (dia) of t1; //el vector t2 es un vector de las posiciones de lunes a sabado que componen valores contenidos en el t1;

type t3 is array (lunes..jueves, -10..14) of t1; //es como trabajar con una matriz;

x:t1; y:t2; z:t3; // esto es la declaración de las variables después del tipo;

x(i+j)

y (martes)

y(martes)(i+j)

z(martes, i+j)

x(5..8)

y(martes..viernes)

Definiciones no restringidas

type matriz is array (positive range <>, positive range <>) of real;

function "+" (a,b:matriz) return matriz is begin....¿?¿

Atributos relacionados con los índices

function "+" (a, b:matriz) return matriz is suma: matriz (a'range(1), a'range(2));

begin

     for i in a'range(1) loop

          for j in a'range(2) loop

               suma (i, j) := ...¿?¿?

Constantes de tipos vectoriales

m1:=((1..3=>1.0), (1=>2.0, 2=>3.0,3=>4.0));

m2:=mat23' (1=>(1=>1.0, others=>0.0), 2=>(2=>1.0, others=>0.0));

¡Atención 'others' exige límites conocidos!

Tipo no restringido predefinido: string

type string is array (positiverange <>) of character;

x0: string(1..8);

subtype s1 is string (2..8);

subtype linea is string (1..80);

x1:s1;

l: linea;

1(3..10):=x0;

1(2..4=:=x0 (4..6);

1(1..8):=x0 (1..4) & "A" & x1 (2..4);

Las constantes de tipo cadena se escriben entre comillas.

¡Ojo! ¡x0 es una cadena de caracteres de longitud exactamente 8!

Tipos compuestos:Registros

Registros

type nombre_mes is (ene, feb, marm abr, may, jun, jul, ago, sep, oct, nov, dic);

type fecha is record...¿?¿?

Un registro no puede tener campos de tipo vector no restringido

Hay otras formas de definir tipos registro, por ejemplo, incluyendo partes variantes (ver bibliografía)

Lo siento, hoy llegue muy tarde y no pille los apuntes muy bien. Pero ayer subí el pdf con toda la información que tengo de Ada en la documentación de la segunda evaluación. Así que ya sabes, estudia mucho ;)

Sintaxis de Ada

recuerda:

texto_io > es entrada y salida de caracteres

integer_text_io > es entrada y salida de caracteres numéricos enteros.

Ada tiene 69 palabras reservadas que tu no puedes utilizar para nombrar ninguna variable.

Delimitadores simples:

& >

' >

( >

) >

* >

+ >

- >

. >

: >

; >

< >

= >

> >

| > 

Tipos escalares

pi: constant float:=3.1415; > inicializo una constante pi con valor inicial de 3.1416.

final: constant charactere:='.'; > inicializo una constante final con valor inicial de '.'

i, j, k: integer; > i, j, k son números enteros.

Ada es fuertemente tipado, no se puede asignar valor a una variable de un tipo diferente.

type intenger is-; --predefinido

Subtipos

Sirve para caracterizar un subconjunto de los valores de un tipo.

NO constituye un nuevo tipo (la asignación está permitida)

Tipos definidos por enumeración

Hay dos predefinidos (booleanos y caracteres)

type día is (lunes, martes, miercoles, jueves, viernes, sabado, domingo);

subtype laborable is dia range lunes....viernes;

d1: dia; d2: laborable;

Atributos

dia 'first=lunes // el primero
dia ' last=domingo // el último
dia ' succ (lunes)=martes // el sucesor (siguiente)
dia 'pred(martes)=lunes // el predecesor (anterior)
dia 'pos(lunes)=0 // posición
dia 'val(1)=martes // valor
dia ' image(lunes)="LUNES" //convertir a cadena de texto
dia 'value ("martes")=martes // convertir una cadena de texto al tipo definido

Tipo booleano

type boolean is (false, true);

a, b, c, d:boolean;

((not a) and b) or (c xor d)

or     t     f

t       t     t

f       t     f

xor   t     f

t       f     t

f       t     f

Tipos escalares

Tipos enteros

Hay algunos predefinidos:

type interger is ... ;    //enteros

type short_integer is ...; // enteros cortos

type long_intenger is ...; // enteros largos

subtype natural is intenger range 0.. intenger' last; // desde el 0 adelante

subtype positivo is intenger range 1..intenger 'last; // desde el 1 adelante

¿?¿?

Prioridades:

and, or, xor

not

=, /=, <, <=, >, >=, in, not in

+, -      (binarios)

....

Tipos reales

type mis_reales is digits 7;

No se admite aritmética mixta:

n:integer; x:float;

n+x      //¡incorrecto!

float (n) +x

n+integer (x) // ambos correctos!!

La conversión de real a entero efectúa redondeo.

Estructuras de control

if...then

...

end if;

if...then

...

else

...

end if;

if ....then

....

elsif...then

...

elsif...then

...

else

....

end if;

case...is...    

when .... => .... // 1 opción 
when ....|...|... => ... // varias opciones
when ... . . ... => ... // con rango
when ... => NULL; //nulo
when others => ... //por defecto

end case;

Instrucciones iterativas

while...loop

...

end loop;

for d in dia loop ... end loop;

for d in lunes.. viernes loop

...

end loop;

for d in reverse lunes. . viernes loop

...

end loop;

loop

...

end loop;

loop

...; 

exit;

...;

end loop;

lopp

...

exit when ...;

...

end loop;

Estructuración del control: subalgoritmos (1...)

Procedimientos y funciones

Paso de parámetros:

in (entrada), out(salida), in out(entrada y salida).

Ada por defecto todos sera solo de entrada.

produce toto(x:T1; y: in out T2) is

...

end toto;

toto(e,z);      --llamada normal

toto (y=>z, x=>e);     --llamada nombrada

funciones

function factorial (n:natural) 

     return natural is

begin

     if n in 0..1

         then return 1;

         else return n*factorial (n-1);

     end if;

end factorial;

Existe sobrecarga, puedo llamar a 7 funciones de la misma manera (suma de coches, suma de motos...) el compilador por el contexto de los operandos(enteros, reales, vectores...) que estoy usando me sabrá distinguir a que función me estoy refiriendo. 

Es decir, el significado se distingue por el contexto.

No se pueden modificar la aridad ni la sintaxis de llamada (prefija o infija).

Ada no distingue entre mayúsculas y minúsculas.

En Ada las funciones y podrecimientos deben estar en funciones y procedimientos. En C tenias 3 funciones y el orden de llamada era indistinta. En Ada hay jerarquía, Y el orden importa...

Ada

Características generales (1...)

Lenguaje de propósito general

Profesional (complejo: no pensado para aprendices)

Incorporación de puntos clave de la tecnología de programación:

- Legibilidad: Evita notación demasiado concisa (es más costoso el mantenimiento que la producción de software: "un programa se lee más veces de las que se escribe")

- Fuertemente y estáticamente tipado: Gran cantidad para definir datos de tipos diferentes. Cada dato puede usarse solo en operaciones especificas de su tipo. La utilización inadecuada se detecta en tiempo de compilación.

- Diseño a gran escala: Programación modular. Mecanismos de encapsulación. Compilación separada.

- Abstracción de datos: Separación clara entre especificación y representación e implementación.

- Modulos génericos: Creación ¿¿¿

- Programas concurrente: Descripción de procesos que pueden ejecutarse concurrentemente. Definición de operaciones de sincronización entre esos procesos.

Manejo de excepciones: Definición de comportamientos de recuperación ante situaciones de error no previstas.

Bibliografía fundamental

...

Escribir en Ada

El fichero debe terminar en > .abd

';' >  para finalizar una orden.

>> no hay llaves.

'--' > es un comentario.

witch > incluye paquetes.

ada.txt_io > Caracteres

Ada. intengeur ¿¿> Enteros

procedure ...  is > procedimiento principal

use > hace referencia de paquetes

begin >  comienzo del programa

put (" ") > para cadenas de caracteres.

get (" ") > para capturar un caracter.

constant: declaración de variables.

while   loop / end loop > mientras...haz

if then /end if > Sí... entonces

'/=' > distinto de

':=' > asignar

'=' > comparar

Compilar Ada

Para compilarlo debes introducirte en la terminal de ubuntu:

sudo apt-get update

sudo apt-get install gnat-4.6

Una vez instalado

Para crear el documento gedit nombre del documento e '&'

Para compilar gnatmake junto al nombre del documento (sin la extensión)

Para ejecutarlo './' junto al nombre del documento (sin la extensión)