TEMA 4: Tipos de Datos

A partir de Algol-68 todos los lenguajes ofrecen una serie de tipos básicos y unos constructores para poder formar nuevos datos estructurados.

4.1	Tipos de datos primitivos

• Son tipos no definidos en términos de otros tipos. Con estos tipos de datos primitivos y con los constructores de tipos se pueden definir tipos estructurados. Los tipos de datos primitivos que aparecen en la mayoría de los lenguajes de programación son:

• Entero

• Real o Flotante

• Booleano

• Carácter

• Entero: Ada, C: short, long ( para cambiar el rango )

C: unsignal (enteros sin signo )

• Real o Flotante: real o float

double ( precisión )

• Booleano: True, False -> Rango de este tipo

(excepción -> C ) => 0 : Falso

!= 0 : Verdadero

• Carácter: se almacena el código asociado al carácter.

4.2	Tipos ordinales definidos por el usuario

• Un tipo ordinal es aquel cuyo rango de posibles valores puede asociarse fácilmente con el conjunto de los enteros positivos. Podemos establecer un orden dentro del tipo.

• En Pascal son ordinales: Entero, Booleano y Carácter.

• Muchos lenguajes le permiten al usuario definir nuevos tipos ordinales. Formas:

• Mediante Enumerados

• Subrango

4.2.1. ENUMERACION.

• En un tipo enumeración el programador enumera en la definición del tipo los posibles valores (constantes simbólicas).

Ej: ( Pascal )

type

dia = {Lunes, Martes, Miercoles, Jueves, Viernes, Sábado, Domingo }

• ¿ A la hora de diseñar el lenguaje, en un mismo entorno de referencia, puedo definir un tipo ?. ¿ Un mismo literal puede pertenecer a dos grupos diferentes ?.

type

fin_de_semana = { Sábado, Domingo }

• Pascal y C no permiten que un mismo literal pertenezca a dos tipos distintos en un mismo entorno de referencia.

• Ada si lo permite. A este problema se le llama Sobrecarga de Literales: están sobrecargando los literales sábado y domingo. Ada lo resuelve analizando el contexto en el que aparezca el literal sobrecargado. Y si lo puede resolver lo resuelve, si no da un error de ambigüedad. Si no el programador dispone de una herramienta para resolver el problema ( lo soluciona de forma explícita ).

dia ` Sabado

fin_de_semana ` Sábado caso de que el compilador no pueda resolverlo.

• Implementación del tipo enumeración. Asignar un entero no negativo diferente a cada uno de los literales. La mayoría de los lenguajes prohibe realizar operaciones ( sumar, multiplicar, ... ) entre los literales. C es una excepción. Entre literales solo pueden hacerse operaciones de comparación ( = , < , <= , >= , > ,... ). Los literales ni pueden leerse ni imprimirse.

4.2.2. SUBRANGO.

• Un subrango es una subsecuencia contigua de un tipo ordinal.

Ej: ( Pascal )

type

mayúsculas = `A' ... `Z';

indice = 1 ... 100;

laborable = Lunes ... Viernes;

• Para realizar la conexión entre el tipo de que proviene y el tipo subrango se asocia el tipo carácter a mayúsculas, mirando de cual proviene.

Además en tiempo de ejecución tendrá que comprobar que esa asignación ( el valor ) está dentro del rango lo que supone un sobrecarga.

4.3	Tipos Compuestos

• Un tipo compuesto es un tipo estructurado o formado por valores simples. Los lenguajes de programación aportan gran cantidad de tipos estructurados: uniones, registros, conjuntos, arrays, lista, árboles, archivos, ...

• Se pueden estudiar de una manera formal y reducirse a:

• Producto Cartesiano: tuplas, registros.

• Uniones Disjuntas: registros variantes, uniones.

• Aplicaciones: arrays.

• Conjuntos Potencia: conjunto.

• Tipos recursivos: estructuras dinámicas.

4.3.1. PRODUCTO CARTESIANO.

• El producto cartesiano de dos tipos S y T: S x T es el conjunto de todos los pares ordenados de valores tal que el primer valor pertenece al conjunto S y el segundo valor pertenece al conjunto T.

S x T = { (x, y) / x ∈ S, y ∈ T}

• La cardinalidad ( número de elementos ) del conjunto producto cartesiano:

|| S x T || = || S || ∙ || T || || S ||: cardinalidad de S.

• Para n conjuntos:

S1 x S2 x ... x Sn --> n tuplas (S1, S2, ... , Sn)

S x S = S2

S x S x S = S3

... Si n=0

S x ... x S = Sn S0 = ( ) ó 0-tupla ó Unit

( n veces ) tupla vacía

• PASCAL y ADA: implementan el producto cartesiano con registro.

• C: estructuras.

Ej: (Pascal)

Type

Fecha = record

Mes:mes;

Día:1..31;

End;

Estamos definiendo: { enero, ... , diciembre } x { 1 ... 31 }

• Para un conjunto cartesiano de n conjuntos existen n Operaciones de Proyección. Permiten extraer el valor que ocupa la posición i-ésima. En el ejemplo de Pascal:

f.mes

f.dia Ambas son operaciones de proyección.

• En el momento de la ejecución del programa, las celdas de memoria que se asocian para cada campo, ocupan posiciones contiguas. En general, cada uno de estos campos puede ser de un tipo distinto, lo que implica que cada campo tendrá un tamaño diferente. Por ello hay que guardar:

• Tipo correspondiente a cada campo.

• Desplazamiento correspondiente a cada campo a partir de la dirección base ( para poder hacer una operación de proyección ).

La estructura:

DESCRIPTOR TIPO DE LA ESTRUCTURA REGISTRO EN TIEMPO DE COMPILACIÓN.

( en tiempo de ejecución no se necesita ningún descriptor ).

Nombre Registro

Nº Componentes

Nombre1

Tipo1

Desplazamiento1

Nombre2

Tipo2

Desplazamiento2

.......

NombreN

TipoN

DesplazamientoN

Dirección

Dirección base en la que comienza el registro.

4.3.2. UNIONES DISJUNTAS O SUMA.

• La unión disjunta o suma de valores pertenecientes a dos tipos S y T (se denota S+T) es el conjunto de valores en el que cada valor se elige de cada uno de los conjuntos S ó T y se etiqueta para indicar el conjunto del que ha sido elegido.

S y T, S + T etiqueta

S + T = { ( true, x ) | x ∈ S } ∪ { ( false , y ) | y ∈ T }

“true y false son etiquetas”

• Cardinalidad: || S + T || = || S || + || T ||

• Sobre los valores del conjunto S + T se pueden realizar dos operaciones básicas:

• Comprobar el valor de la etiqueta para conocer el conjunto del que proviene el segundo elemento.

• Proyección del valor original en S ó T.

• Las uniones se pueden extender: S1 + S2 + ... + Sn ( necesitamos una etiqueta que tome n valores diferentes ).

• ¿ Como se ven reflejadas las uniones disjuntas en los lenguajes de programación ?

• Registros Variantes: Ada, Pascal.

• Uniones: C.

• Cuando un lenguaje de programación decide adoptar la unión disjunta se debe plantear 2 questiones:

• Problema de la comprobación de tipos.

• Forma concreta que adopta la union.

• La mayoria de los lenguajes de programación incluyen la unión disjunta relacionada con la estructura registro ( es el caso de Ada o Pascal ). Sin embargo en C, la estructura unión es una estructura diferente de la estructura registro. En C, no se definen etiquetas para las uniones.

Ej de registro variante en Pascal:

Type

Forma = ( punto, circulo, rectangulo );

Figura = record

x,y: real;

case forma_figura: forma of

punto: ( ); “tupla vacia ( Unit ) ”

circulo: ( radio: real );

rectangulo: ( lado1, lado2: real );

end;

Figura = real x real x ( Unit + real + ( real x real ) )

Producto cartesiano: real x real

Unión Disjunta: Unit + real + ( real x real )

El conjunto de valores que yo estoy definiendo para el tipo figura es más que un producto cartesiano, es un producto cartesiano por una unión disjunta.

• Implementación:

Se utiliza la misma dirección base para cada uno de los elementos variantes, y se reserva espacio para el elemento variante de mayor tamaño. Tendremos que guardar en el descriptor que empleamos en tiempo de compilación: la etiqueta, el tipo de la etiqueta y la asociación entre el tipo de la etiqueta y la tabla de casos.

Descriptor:

• Si el lenguaje no hace una comprobación de tipos en tiempo de ejecución entonces en tiempo de ejecución no se almacena nada. ( C y Pascal ).

4.3.3.APLICACIONES.

• Consideremos una aplicación m que aplica cada valor x del conjunto S a un valor en el conjunto T. Ese valor en el conjunto T se llama imagen de x bajo m, m(x).

m: S T

entonces

S T = conjunto de todas las posibles aplicaciones posibles de S en T.

S T = { m / x ∈ S ⇒ m(x) ∈ T }

• Cardinalidad: || S T || = || T || || S ||

• ¿ En qué estructura de datos se ve reflejada la aplicación ?. En los arrays (vector, matriz o tabla).

El array es lo que se llama una aplicación finita por que es una aplicación que va desde un conjunto finito que se denomina conjunto índice a otro conjunto finito que se llama conjunto componente.

Ej Pascal:

array [ S ] of T;

S T ( estamos definiendo esta aplicación ).

• Muchos lenguajes de programación permiten definir arrays multidimensionales ( matrices ).

Ej: (Pascal) (array n-dimensional)

Type

a = array[ i1 .. s1, i2 .. s2, ... , in .. sn ] of T

( aplicación que va desde un solo índice al conjunto T ).

a = { i1 .. s1} x { i2 .. s2 } x ... x { in .. sn } T

( aplicación entre una n-tupla y el conjunto T ).

• Problemas con los que nos encontramos a la hora de adoptar una aplicación:

• Tipo de los índices ( de qué tipo puede ser S ) y limite inferior de los índices.

• En C: el tipo de los indices es un subrango de los enteros.

• En Pascal o Ada: el tipo de los indices es cualquier tipo ordinal.

• Algunos lenguajes fijan ellos el límite inferior ( 0 ó 1 ). C lo fija a 0 y en otros lenguajes lo decide el programador.

• Vinculación de índices y categorias de arrays. La vinculación del tipo del índice a un array normal se hace de manera estática. Sin embargo, el rango de valores que puede adoptar ese índice a veces no se vincula de manera estática al array, sino de manera dinámica. Hay cuatro tipos de arrays:

• Array estático: Vinculación de valores de los índices y asignación de espacio al array estática.

Ej:

Pascal: array global → array estático.

C: static ⇒ array estático.

• Array dinámico de pila fijo: Vinculación de rango de valores de los índices estática y asignación de espacio dinámica ( en la pila de ejecución ).

Ej:

Pascal, C, Ada: arrays definidos en un subprograma ( arrays locales ).

• Array dinámico de Pila: Vinculación de rango de índices y asignación de espacio dinámicas. Pero una vez se fija no puede cambiarse.

Ej: (Ada)

get (long _ lista); leemos un dato entero.

declare se crea un nuevo bloque en la pila de ejecución.

lista: array ( 1 ..long_lista ) of integer;

begin

{ cuerpo de la ejecución }

end;

• Array dinámico de heap: Vinculación del rango de índices y asignación de espacio dinámicas ( en tiempo de ejecución). Pero ahora puede cambiar el tamaño o la dirección en tiempo de ejecución.

• Implementación del tipo array: Los elementos del array se almacenan en celdas contiguas de memoria. El código para acceder al elemento del array se genera en tiempo de compilación y es en tiempo de ejecución cuando se produce el direccionamiento a ese código.

• Arrays unimensionales; Para calcular la dirección de un elemento del array:

@v[ k] = @v[ li ] + ( k - li ) * e @v[ li ]: direccion base del array.

⇒ @v[ k] = ( @v[ li ] - li*e ) + k * e ( @v[ li ] - li*e ): es cte y puede calcularse en t de comp

li: limite inferior.

e:tamaño de un elemento del array.

• Descriptor de la estructura en t. de compilación:

Nombre del Array

Tipo del elemento

Tipo del índice

Límite Inferior

Límite Superior

Dirección base del array

Si alguna de estas estructuras se vincula en tiempo de ejecución, tendriamos que mantener esta parte del descriptor en tiempo de ejecución.

• Arrays Multidimensionales:

Ej: una matriz; Hay dos posibilidades:

• Almacenamiento por Filas.

• Almacenamiento por Columnas.

El programador no debería obviar esto del lenguaje de programación. Un uso ineficiente del lenguaje podría provocar un fallo de página ( por la paginación ).La mayoria de los lenguajes de programación hacen un almacenamiento por filas.

La dirección del elemento ij:

@m[ i, j ] = @m [ fi, ci ] + ( (i - fi ) n + ( j - ci ) ) * e

m: nombre de la matriz

@m [ fi, ci ]: dirección base del primer elemento de la matriz.

e: tamaño del elemento de la matriz.

⇒ @m[ i, j] = @m[ fi, ci ] - ( fi*n + ci )*e + (i*n + j) *e

(i*n + j) *e: parte variable

@m[ fi, ci ] - ( fi*n + ci )*e: parte constante. Se puede calcular en tiempo de compilación ( si la asignación de espacio se realiza de manera estática).

Descriptor en tiempo de compilación:

Nombre Array

Tipo Elemento

Numero Dimensiones

Tipo Indice 1

Lim_Inf Indice 1

Lim_Sup Indice 1

.................

Tipo Indice N

Lim_Inf Indice N

Lim_Sup Indice N

Dirección

Si alguna de las partes del descriptor no se conociera hasta el tiempo de ejecución, deberá mantenerse el descriptor hasta el tiempo de ejecución.

4.3.4. CONJUNTOS POTENCIA.

• Consideremos un conjunto S. Al conjunto de todos los conjuntos de S se le denomina conjuntos potencia o conjunto de las partes de S. Formalmente:

P(s) = { s | s ⊆ S }

• Operaciones con los conjuntos Potencia:

• Pertenencia

• Inclusión (contenido)

• Unión

• Intersección

• Cardinalidad: || P(s) || = 2 || S ||

• El único lenguaje imperativo que implementa directamente los conjuntos potencia es Pascal: set of T

Ej:

Type

Color = ( rojo, verde, azul );

Var

C = set of color; P(color)

valores que puede tomar C (son ellos mismos conjuntos):

{ }, { rojo }, { verde }, { azul }, { rojo, verde }, { rojo, azul }, { verde, azul },

{ rojo, verde, azul }.

En Pascal solo se pueden construir conjuntos de tipo ordinal.

• Implementación: Una posible implementacion del tipo conjuntos potencia es representar los conjuntos como cadenas de bits:

Ej:

Type

Nota = set of `A' .. ` E `;

[ `A', `D', `E' ] 1 0 0 1 1 ( representación asociada a ese conjunto:

A B C D E )

( cada elemento del conjunto nota se representa con 5 bits ).

• Ventajas: Permite que las operaciones típicas de conjuntos puedan realizarse mediante operaciones lógicas que permiten todos los tipos de lenguajes máquina.

• Unión conjuntos OR

• Pertenencia

`B' in nota AND

01000

4.3.5. TIPOS RECURSIVOS.

• Un tipo recursivo es aquel cuyos valores están compuestos de valores del mismo tipo. Un tipo recursivo está definido en términos de él mismo, (T = .... T ....), se define mediante una ecuación de conjuntos recursiva.

• La cardinalidad de un tipo recursivo es siempre infinita ( no podemos enumerar todos sus valores) aunque la cardinalidad de los conjuntos que aparecen en la parte de la derecha se finita.

• Implementación. Si el lenguaje es imperativo: (Pascal, Ada, C) debe realizarse la implementación utilizando el tipo puntero.

• Si el lenguaje es funcional (Haskell) sobre todo los que se llaman modernos, debe realizarse la implementación definiendo tipos recursivos directamente.

Ej: Tipo recursivo lista.

Lista: secuencia de valores de cualquier numero de componentes incluido ninguno.

Longitud: numero de componentes de la lista.

Lista vacía: lista de longitud cero (sin componentes).

Lista homogenea: todos los elementos son del mismo tipo.

Lista Enteros:

ListaEnteros = Unit + ( Entero * ListaEnteros )

0-tupla ( )

( de otra manera ):

ListaEnteros = { ( nil, ( ) ) } ∪ { ( cons, ( i, l ) ) | i ∈ Entero, l ∈ ListaEnteros }

etiqueta elto etiqueta par

Podríamos intentar buscar soluciones sucesivas a esa ecuación. Los elementos del conjunto solución a esa ecuación:

( nil, ( ) ) ≡ nil ( para simplificar )

( cons, ( i, nil ) ) i ∈ entero

( cons, ( i, cons( j, nil) ) ) i, j ∈ entero

(cons, ( i, cons, ( j, cons( k, nil) ) ) ) i, j, k ∈ entero

• Algunos autores incluyen un notación especial para hacer referencia a un lista: S*

S* = Unit + ( S x S* ) S: tipo base de la lista

• ¿ Cómo definiríamos una lista en Haskell ?

data Bool = True | False ( definición del tipo booleano ).

| alternativa

data [a] = [ ] | a: [a] : constructor

data Lista a = Nil | a `cons' ( lista a )

`cons' operador de construcción

( lista a ) constructor

Otro ejemplo: Definición del tipo recursivo árbol binario:

ArbolBEnteros = Unit + ( Entero x ArbolBEnteros x ArbolBEnteros )

subárbol izq. subárbol dcho

• Soluciones a esta ecuación:

( nil, ( ) ) ≡ nil

( nodo, ( i, nil, nil ) ) i ∈ Entero Árbol con 1 elemento.

( nodo, ( i, nodo( j, nil, nil ), nil ) ) i, j ∈ Entero

( nodo, ( i, nodo( j, nil, nil ), nodo( k, nil, nil ) ) ) i, j, k ∈ Entero

• Una definición para este tipo en Haskell:

Data ArbolB t = Nil | Nodo t ( ArbolB t ) ( ArbolB t )

4.4	Tipo Puntero

• El tipo puntero define variables cuyo rango toma valores que hacen referencia a direcciones de memoria y a un valor especial: nil.

• Nil es una dirección inválida que se emplea para indicar que el puntero no hace referencia a ningún objeto válido.

• Uso de los punteros:

• Para realizar direccionamiento indirecto. Es muy utilizado en el lenguaje ensamblador. Caso del C incorpora este uso al tipo puntero.

• Administración del almacenamiento dinámico en el Heap.

• Operaciones con los punteros:

• Asignación. En la operación de asignación lo que se hace es fijar el puntero a la dirección de un objeto.

• Dar referencia. En la operación dar referencia cuando un puntero aparece en una expresión o bien hace referencia al contenido de la celda de memoria a la que se está vinculado, o bien hace referencia a un objeto cuya dirección de memoria se almacena en la celda a la que está vinculada el puntero.

Este último caso es el de Dar referencia (lo que hace es resolver la referencia indirecta ).

• Problemas a la hora de decidir los punteros:

• Comprobación de tipos: El tipo del objeto al que pueda apuntar un puntero se denomina “tipo dominio“.

• PL / I: Primer lenguaje imperativo que incorporo el tipo puntero. Permitio que cambiara de manera dinámica ( tiempo de ejecución ) el tipo dominio de un puntero. A partir de entonces se resolvió este problema ( se asigna de manera estática el tipo dominio ).

• Punteros colgantes ( Danghing pointers ). Un puntero o referencia colgante es un puntero que contiene una referencia a una variable dinámica que ya ha sido desasignada.

Ej: C

Int *p, j;

Void f (void)

{

int i;

p = &i;

.....

}

.....

f( );

j = *p + 5;

Otro tipo de manifestación de los punteros colgantes:

Ej: Pascal

var

suma, p: ^real;

.....

new (suma);

p := suma;

dispose (suma);

Varios apuntadores apuntando a una variable dinámica y hacemos un dispose de esa variable dinámica.

• Objetos pérdidos. Un objeto perdido es un objeto de asignación dinámica que ya no es accesible por el programa de usuario ( aunque ese objeto contenga datos ). A estos objetos perdidos se le llama basura por:

• Por definición no se pueden acceder.

• El sistema no puede reincorporarlo a la zona de espacio disponible en el heap.

Ej Pascal

Var

Suma:^real;

..................

new (suma)

suma^:27.7;

..................

new (suma); ó suma:=p;

2 formas de crear un objeto perdido

Se le asigna otra dirección

Los tipos puntero se incluyen en la mayoría de los LP imperativos (si no seria imposible definir tipos recursivos de datos).

• Implementación del tipo Puntero:

• 1) SOLUCIONES AL PROBLEMA DE LAS REFERENCIAS COLGANTES:

Cuando el problema: haber hecho un dispose de una variable dinámica (2º uso de los punteros únicamente)

Utilización de “lapidas”

HEAP

P

VA Variable dinámica

q

r

Hago un dispose ( se libera memoria)

• El resto de punteros hacen referencia a una dirección invalida (problema).

• Solución: Ahora los punteros hacen referencia a otro objeto del Heap: Lapida

P

VA

q

r Variable dinámica

Dispose (r)

Nunca se libera espacio que ocupa lapida ahora apunta a NILL

• Esta solución conlleva un costo en tiempo en espacio:

• Hay que reservar espacio en el Heap para cada una de las variables dinámicas (la Lapida y las variables dinámicas)

• En tiempo: Cada referencia necesita resolver 2 indirecciones.

b) “Cerradura y llave”

• En este caso los apuntadores se implementan como un par ordenado:

(llave, dirección) La del elemento al que hace referencia en el Heap

Entero

• A las variables dinámicas del Heap se le añade una cabecera,

en esta se almacena un valor entero que se llama cerradura.

• En el momento de la asignación : New (p)

• Se crea un valor entero

• Se reserva espacio en el Heap para

• Se coloca en “dirección”, la dirección del objeto

P (17, ) r (17, )

Si hacemos una asignación q:=p

(17, )

• Todos los apuntadores que hacen referencia a ese objeto tienen el mismo valor en la llave. Para realizar un acceso se comprueba que el valor de la llave del apuntador coincide con el valor de la cerradura.

• A la hora de realizar la desasignacion, Dispose (r), se le asigna a la cerradura un valor invalido.

P (17, )

Entonces

r(-1, )

• 2) SOLUCIONES AL PROBLEMA DE LOS OBJETOS PERDIDOS

• Cuando teníamos un objeto en el Heap al que no podíamos hacer referencia desde ninguna variable del programa. Ni tampoco podría reutilizarse ese espacio. Soluciones:

a) Método del contador de referencias (Garbage collection)

Necesitamos reservar espacio en el heap para almacenar el objeto, reservamos también espacio para el contador (numero de punteros que referenciamos a ese objeto).

P P

Q q

Así es fácil localizar objetos perdidos objetos con el contador a cero

b) Método de la recogida de Basura

• La asignación de espacio en el heap se realiza cuando se pide (no se tiene precaución).

Problema: Cuando ya no hay espacio en el heap.

Algoritmo de Recogida de basura.

Necesitemos espacio adiciona en el heap.

1º) Marcar todos los objetos del heap como basura

2º) Se inspeccionan los punteros del programa

Los objetos a los que apuntan estos apuntadores se desmarcan.

Se desmarcan

.

.

.

3º) Los objetos que siguen marcados se incorporan a la lista de espacio disponible.

Este algoritmo tiene un costo de tiempo bastante fuerte.

Tema 4: Tipos de Datos LPR

1

16

X

Lapida

X

Cabecera

Objeto dinámico

Entero

Objeto dinámico

Cerradura

Objeto dinámico

Cerradura -1

Objeto dinámico

Se libera este espacio

Como no coincide 17 con -1 ya no se puede acceder.

Imposible acceder a una referencia invalida

0

Objeto

2

Objeto

X

Objeto

Objeto

Objeto

Objeto

Este objeto podría contener referencia a otros objetos del heap

Toma la dirección de i (objeto dinámico de pila: acaba con la ejecución de la función ) y se la asigna al puntero p.

Error o referencia no válida. *p ya no está dentro de la función f.