PDF de programación - Tipos Abstractos de Datos (TAD)

Tipos Abstractos de Datos (TAD)

Programación de Sistemas de Telecomunicación

Informática II

Departamento de Sistemas Telemáticos y Computación (GSyC)

Octubre de 2017

GSyC - 2017

Tipos Abstractos de Datos (TAD)

1

©2017 Grupo de Sistemas y Comunicaciones.
Algunos derechos reservados.
Este trabajo se distribuye bajo la licencia
Creative Commons Attribution Share-Alike
disponible en http://creativecommons.org/licenses/by-sa/2.1/es

GSyC - 2017

Tipos Abstractos de Datos (TAD)

2

Contenidos

1

Introducción

2 Tipos Abstractos de Datos

3 Definición de TADs mediante Tipos privados y privados limitados

4 Clases de subprogramas de un TAD

GSyC - 2017

Tipos Abstractos de Datos (TAD)

3

Contenidos

Introducción

1

Introducción

2 Tipos Abstractos de Datos

3 Definición de TADs mediante Tipos privados y privados limitados

4 Clases de subprogramas de un TAD

GSyC - 2017

Tipos Abstractos de Datos (TAD)

4

Tipos en Ada (1)

Introducción

Tipos escalares
A veces denominados tipos primitivos o tipos básicos.
Los valores u objetos del tipo tienen un único componente que no
puede ser descompuesto por el programa en sus partes:

Tipos numéricos: enteros, de coma flotante, de coma fija
Tipos enumerados: Character, Boolean
Tipos acceso (punteros)

Los tipos escalares numéricos y enumerados tienen los
atributos First, Last, Range
Los tipos escalares discretos (enteros y enumerados) tienen
además los atributos Pos, Val, Pred, Succ
En el paquete Standard se definen los tipos escalares
predefinidos del lenguaje Ada (ver manual de referencia). Este
paquete no requiere que se haga with de él.

GSyC - 2017

Tipos Abstractos de Datos (TAD)

5

Tipos en Ada (2)

Introducción

Tipos compuestos
A diferencia de los escalares, los valores de los tipos compuestos
están formados por componentes a los que se puede acceder:

Record: sus componentes son los campos del registro
Array: sus componentes son los elementos del array

GSyC - 2017

Tipos Abstractos de Datos (TAD)

6

Operaciones de los tipos en Ada

Introducción

Hay tres operaciones básicas que están predefinidas
automáticamente para cualquier tipo en Ada (escalares,
compuestos, definidos por el usuario):

Asignación o copia :=
Comparación de igualdad =
Comparación de desigualdad /=

La asignación copia todo el valor, incluyendo sus componentes si es
un tipo compuesto (array o record).
Si el valor es un puntero (tipo access) se copia la dirección, no el
objeto apuntado.
Las dos comparaciones comparan todo el valor, incluyendo los
componentes si es un tipo compuesto (array o record).

GSyC - 2017

Tipos Abstractos de Datos (TAD)

7

Tipos Abstractos de Datos

Contenidos

1

Introducción

2 Tipos Abstractos de Datos

3 Definición de TADs mediante Tipos privados y privados limitados

4 Clases de subprogramas de un TAD

GSyC - 2017

Tipos Abstractos de Datos (TAD)

8

Tipos Abstractos de Datos

Tipo Abstracto de Datos (TAD)

¿Qué es un TAD?
Una especificación abstracta de un tipo de datos en la que se describen:

los valores del tipo
su interfaz: las operaciones que pueden realizarse con los valores del
tipo

Ejemplo: el tipo Integer

Valores:
type Mi_Tipo_Enteros is range Min_Integer..Max_Integer:

el rango depende de los bits que usemos para representar cada entero

Interfaz (operaciones):

Aritméticas: +, -, *, /, rem, mod, **
Comparación: <, <=, =, /=, >, >=

GSyC - 2017

Tipos Abstractos de Datos (TAD)

9

Tipos Abstractos de Datos

Programas cliente que usan TADs

Programa cliente
Los programas que usan un TAD se denominan programas cliente
del TAD

1 El código del cliente no debe depender del código fuente de la

implementación del TAD, sólo de su interfaz:

el cliente no conoce la representación interna de los valores del
TAD
el cliente no conoce cómo están implementadas las
operaciones del TAD

2 El código del TAD no debe depender del código fuente de

ningún cliente en particular

GSyC - 2017

Tipos Abstractos de Datos (TAD)

10

Tipos Abstractos de Datos

Programas cliente que usan TADs

Encapsulación: ventajas de la independencia entre el TAD y los
programas cliente

Si el programador del TAD decide cambiar la implementación
de una de las operaciones del TAD el código fuente de los
clientes no se ve afectado: no hay que cambiarlo, aunque sí
recompilarlo
Si el programador del TAD decide cambiar la forma en que se
representan los valores del tipo tampoco se ve afectado el
código fuente de los clientes: no hay que cambiarlo, aunque sí
recompilarlo
El TAD es reusable para múltiples clientes ya que su código no
depende de ningún cliente en particular

GSyC - 2017

Tipos Abstractos de Datos (TAD)

11

Tipos Abstractos de Datos

Representación de los valores del tipo

Un valor de tipo Integer ocupa normalmente lo mismo que el
tamaño de palabra del procesador.
Variable’Size es el tamaño en bits de Variable.
Cuando los valores del tipo están compuestos de varios
componentes se utilizan tipos compuestos como arrays y
registros para representarlos
Los valores de tipos primitivos como Integer se almacenan en
variables que deben haberse declarado de tipo Integer
Los valores de un TAD T definido por el programador se
almacenan en variables que deben haberse declarado de tipo T
A veces utilizamos la palabra objeto para referirnos al valor de
un TAD

GSyC - 2017

Tipos Abstractos de Datos (TAD)

12

Tipos Abstractos de Datos

Mecanismos de Ada para definir TADs

Subtipos: subtype Small is Integer range -10..10;
Tipos derivados:
type Small is new Integer range -100..100;
Nuevos tipos enumerados, registros y arrays: Ej:
type Message_Type is (Init, Writer, Server);
Paquetes: proporcionan encapsulación, ocultación de información
Tipos private y limited private: refuerzan la encapsulación de los
paquetes para que el cliente sólo pueda manipular el objeto a
través de la interfaz definida por el TAD
Sobrecarga de operadores: permite redefinir los operadores
aritméticos y de comparación para nuevos tipos
Excepciones definidas por el usuario: el programador del TAD
puede definir excepciones que eleva la implementación del TAD
para que el cliente las pueda capturar
Subprogramas y paquetes genéricos
Tipos etiquetados: programación Orientada a Objetos (OO) con
herencia, polimorfismo y despacho dinámico en Ada

GSyC - 2017

Tipos Abstractos de Datos (TAD)

13

Tipos Abstractos de Datos

TADs en lenguajes Orientados a Objetos (OO)

Los conceptos básicos asociados a la programación OO son la
encapsulación, el polimorfismo, el despacho dinámico y la
herencia.
En lenguajes orientados a objetos como Java o C++ los TADs
se implementan como clases: un concepto que engloba la
definición de un nuevo tipo y la encapsulación que
proporcionan en Ada los paquetes.
En C++ o en Java, cada clase define un tipo
La encapsulación que proporciona la clase la proporciona en
Ada el paquete, dentro del que se define uno o más tipos
En Ada la encapsulación del paquete se refuerza mediante los
tipos privados
En Ada los tipos etiquetados (tagged) aportan la herencia, el
polimorfismo y el despacho dinámico.

GSyC - 2017

Tipos Abstractos de Datos (TAD)

14

Definición de TADs mediante Tipos privados y privados

limitados

Contenidos

1

Introducción

2 Tipos Abstractos de Datos

3 Definición de TADs mediante Tipos privados y privados limitados

4 Clases de subprogramas de un TAD

GSyC - 2017

Tipos Abstractos de Datos (TAD)

15

Definición de TADs mediante Tipos privados y privados

limitados

Tipos privados en Ada (1)

Tipos privados
En la especificación de un paquete se puede declarar un tipo como private.
La declaración completa del tipo se hace al final del paquete, en la sección private
del paquete.

package P is

-- Representación del TAD NO visible para clientes del paquete
type T is private;
-- Interfaz definida para el TAD
procedure P (e: T);
function
...

F (e1: T; e2: T) return T;

private

-- Representación del TAD visible en el cuerpo del paquete
type T is new Integer range 1..10;

end P;

GSyC - 2017

Tipos Abstractos de Datos (TAD)

16

Definición de TADs mediante Tipos privados y privados

limitados

Tipos privados en Ada (2)

La definición completa del tipo NO puede ser utilizada por los
clientes del paquete en el que se define el tipo privado.

el ámbito de las definiciones que aparecen en la parte pública
(es decir, antes de la parte privada) es el resto de la parte
pública de la especificación, la parte privada, el body, y
cualquier paquete o programa que haga with de éste
el ámbito de las definiciones de la parte private es el resto de la
parte private y el body.

Los tipos privados tienen sólo 3 operaciones predefinidas:
asignación/copia := y los comparadores de igualdad = y
desigualdad /=

Ejemplo: Si es un entero, el cliente no puede usar los
operadores aritméticos
Ejemplo: Si es un registro/array, el cliente no puede acceder a
sus componentes/elementos, salvo que algún subprograma de
la interfaz del TAD lo permita

¿Qué más operaciones se puede realizar con los objetos del
tipo privado? ¡Sólo las que se definan en la interfaz!
Tipos Abstractos de Datos (TAD)

GSyC - 2017

17

Definición de TADs mediante Tipos privados y privados

limitados

Ejemplo: Definición de un TAD sin private (1)

with Ada.Strings.Unbounded;

package Lists is

package ASU renames Ada.Strings.Unbounded;

type Cell;
type Cell_A is access Cell;

type Cell is record

Name : ASU.Unbounded_String;
Count: Natural := 0;
Next : Cell_A;

end record;

-- Interfaz
procedure Add (List

: in out Cell_A;

A_Name : in
A_Count: in Natural);

ASU.Unbounded_String;

procedure Print_All (List: in Cell_A);

end Lists;

GSyC - 2017

Tipos Abstractos de Datos (TAD)

18

Definición de TADs mediante Tipos privados y privados

limitados

Ejemplo: Definición de un TAD sin private (2)

with Ada.Text_IO;

package body Lists is
procedure Add (List

: in out Cell_A;

A_Name : in
A_Count: in Natural) is

ASU.Unbounded_String;

P_Aux : Cell_A;

begin

P_Aux := new Cell;
P_Aux.all.Name := A_Name;
P_Aux.all.Count := A_Count;
P_Aux.all.Next := List;
List := P_Aux;

end Add;

p