PDF de programación - Tema 5: Tipos abstractos

Tema 5: Tipos abstractos

5.1 Introducción

En este tema, nos centraremos en un tipo especial de dependencia, aquella observada
entre un cliente de un tipo abstracto de dato, para con la representación de este tipo, y
veremos el modo de evitar esta dependencia. Trataremos también brevemente el
concepto de campos de especificación para la definición de tipos abstractos, la
clasificación de las operaciones y los beneficios del uso de las representaciones.

5.2 Tipos definidos por el usuario

A comienzos de la era informática, un lenguaje de programación venía con tipos (como
integers (enteros), booleans (booleanos), strings (cadenas), etc.) y procedimientos
incorporados; p. ej., para la entrada y salida de datos. Los usuarios podían definir sus
propios procedimientos, y de este modo se construyeron programas de gran tamaño.
La idea de tipos abstractos supuso un gran avance en el desarrollo de software. Según
esta idea, se podría diseñar un lenguaje de programación que admitiese también tipos
definidos por el usuario. Esta idea surgió del trabajo de muchos investigadores, en
particular Dahl (creador del lenguaje Simula), Hoare (quién desarrolló muchas de las
técnicas que se utilizan actualmente para trabajar con tipos abstractos), Parnas (que
acuñó el concepto “ocultación de datos”, y que por primera vez articuló la idea de
organizar los módulos de un programa de acuerdo con el contenido que encapsulaban),
y, ya por último, Barbara Liskov y John Guttag, profesores de MIT, que realizaron un
trabajo clave en relación con la especificación de tipos abstractos, y con el soporte de
un lenguaje de programación para éstos (y que por cierto, desarrollaron el presente
curso).

La abstracción de datos parte de la idea de que lo que caracteriza a un tipo determinado
son las operaciones que se pueden realizar en él. Un número es algo que se puede
sumar y multiplicar; una string es algo que se puede concatenar y que puede tomar una
substring (subcadena); un tipo booleano es algo que se puede negar, y así
sucesivamente. En cierto modo, los usuarios podían ya definir sus propios tipos en los
primeros lenguajes de programación: era posible crear un tipo date a través de un
recurso de programación record; por ejemplo, con campos integer para el día, el mes y
el año. No obstante, la originalidad de los tipos abstractos radicaba en el énfasis en las
operaciones: el usuario del tipo no necesitaba preocuparse por cómo sus valores se
almacenaban, del mismo modo en que un programador puede ignorar cómo el
compilador guarda los integers. Lo que interesa aquí son las operaciones.

En Java, como en muchos lenguajes de programación modernos, la separación entre
tipos incorporados y tipos definidos es un tanto imprecisa. Las clases del paquete
java.lang, como Integer y Boolean son incorporadas; la cuestión de si considerar o no
que todas las colecciones de java.util sean incorporadas es un asunto menos claro (y no
muy importante de todas formas). Java complica este tema al tener tipos primitivos que
no son objetos. El conjunto de estos tipos, como int y boolean, no puede ser extendido
por el usuario.

5.3 Clasificación y tipos de operaciones



50

Los tipos, ya sean incorporados o definidos por el usuario, pueden clasificarse como
mutables o inmutables. Los objetos de un tipo mutable pueden ser alterados, es decir,
facilitan operaciones que, cuando son ejecutadas, hacen que los resultados de otras
operaciones sobre el mismo objeto provoquen resultados diferentes. Por tanto, Vector
es mutable porque usted puede llamar a addElement y observar la alteración con la
operación size, que provocará un resultado distinto en cada ejecución de addElement.
Sin embargo, String es inmutable porque sus operaciones crean nuevos objetos String,
en vez de alterar los ya existentes. En algunas ocasiones, un tipo se facilitará de dos
formas, una mutable y otra inmutable. StringBuffer, por ejemplo, es una versión
mutable de String (aunque los dos no son, sin duda alguna, el mismo tipo dentro del
lenguaje Java, y por tanto, no se pueden intercambiar).
Por lo general, se trabaja mejor con tipos inmutables. El fenónemo llamado Aliasing1 no
es un problema, ya que el reparto no puede ser observado. Algunas veces, la utilización
de tipos inmutables es más eficiente, ya que podemos tener más reparto. Sin embargo,
muchos problemas se expresan de forma más natural mediante el uso de tipos mutables,
que resultan más eficaces cuando se trata de alteraciones locales en grandes estructuras.
Las operaciones de un tipo abstracto se clasifican de la siguiente forma:


• Constructores: crean nuevos objetos de un determinado tipo. Un constructor
puede recibir un objeto como argumento, pero no un objeto del tipo que está
siendo construido.



• Productores: crean nuevos objetos a partir de objetos ya existentes; los términos

son sinónimos. El método concat de una String, por ejemplo, es un productor:
recibe dos strings y produce una nueva que represente la concatenación.

• Mutadores o modificadores: cambian el valor de los objetos. El método

addElement de la clase Vector, por ejemplo, altera un vector al añadir un
elemento al final del mismo.

• Observadores: reciben objetos de un determinado tipo abstracto y devuelven

objetos de un tipo distinto.El método size de la clase Vector, por ejemplo,
devuelve un entero.



Podemos resumir estas distinciones esquemáticamente de la siguiente forma:
constructor: t -> T
productor: T, t -> T
mutador: T, t -> void
observador: T, t -> t

Este esquema muestra de modo informal el formato de las operaciones en las diversas
clases. Cada T es un tipo abstracto por sí sólo; cada t representa a algún otro tipo. En
general, cuando un tipo aparece en la parte izquierda, indica que puede darse más de
una vez. Por ejemplo, un productor puede recibir dos valores de un determinado tipo
abstracto, al igual que el método concat de String recibe dos strings. Las apariciones de
t a la izquierda pueden omitirse también; los observadores no reciben ningún


1 El fenómeno Aliasing se explica detalladamente en la sección 9.7 del tema 9.



51

argumento que no sea de tipo abstracto (como size, por ejemplo), y otros pueden recibir
varios.

Esta clasificación proporciona una terminología bastante útil, pero no llega a ser
perfecta. En tipos de datos complejos, por ejemplo, pueden existir operaciones que son
a la vez productores y mutadores. Hay quién utiliza el término productor para enfatizar
que no se da ninguna transformación de datos.

Otro término que conviene conocer es iterator. Un iterator es normalmente un tipo de
método especial (no disponible en Java) que devuelve una colección de objetos,
devolviendo uno cada vez; como, por ejemplo, los elementos que están en un conjunto.
En Java, un iterator es una clase que proporciona métodos que pueden usarse luego
para obtener una colección de objetos, devolviendo uno cada vez. La mayoría de las
clases de colecciones están provistas de un método con el nombre iterator, que
devuelve un objeto de tipo java.util.Iterator, para que sus objetos sean extraídos por un
iterador propiamente dicho.

5.4. Ejemplo: Lista

Observemos un ejemplo de un tipo abstracto: la lista. Una lista, en Java, es como un
array. Facilita métodos para extraer al elemento de un determinado índice y para
sustituirlo en un determinado índice. Sin embargo, a diferencia del array, posee
también métodos para insertar o quitar un elemento de un determinado índice. En
Java, el tipo List es una interfaz con muchos métodos, pero por ahora, supongamos
que es una clase simple que comprende los siguientes métodos:

public class List {
public List ();
public void add (int i, Object e);
public void set (int i, Object e);
public void remove (int i);
public int size ();
public Object get (int i);
}

Los métodos add, set y remove son mutadores; los métodos size y getson observadores.
Es normal que un tipo mutable no tenga productores (y que un tipo inmutable, sin duda,
no pueda tener mutadores).
Para especificar estos métodos, nos hará falta alguna expresión que nos permita explicar
cómo es una lista. Utilizaremos para ello el concepto de campos de especificación.
Puede pensar que un objeto de un determinado tipo posee estos campos, pero acuérdese
de que éstos no tienen que ser necesariamente campos de la implementación, y que no
hace falta que el valor de un campo de la especificación se pueda obtener por medio de
algún método. En este caso, describiremos las listas con un único campo de
especificación,

seq [Object] elems;


donde para una lista l, la expresión l.elems indicará la secuencia de objetos almacenados
en ella, indexada desde cero. Veamos ahora algunos métodos especificados:



52

public void get (int i);
// throws
// IndexOutOfBoundsException if i < 0 or i > length (this.elems)
// returns
// this.elems [i]
public void add (int i, Object e);
// modifies this
// effects
// throws IndexOutOfBoundsException if i < 0 or i > length (this.elems)
// else this.elems’ = this.elems [0..i-1] ^ <e> ^ this.elems [i..]
public void set (int i, Object e);
// modifies this
// effects
// throws IndexOutOfBoundsException if i < 0 or i >= length (this.elems)
// else this.elems’ [i] = e and this.elems inalterado en cualquier otro lugar

En la poscondición de add, he utilizado s[i..j] para referirme a la subsecuencia de s que
va desde elíndice i hasta j, y s[i..] para indicar la secuencia de elementos a partir del
sufijo i. El acento circunflejo hace referencia a la concatenación de secuencias. Por
tanto, la poscondición dice que, cuando el valor del índice pasado como argumento está
dentro de los límites del array, el nuevo elemento se coloca junto al índice pa