Download 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 pasado como
argumento.
5.5 Cómo diseñar un tipo abstracto
El diseño de un tipo abstracto supone la elección de buenas operaciones y la
definición de su comportamiento. Algunos consejos generales serían:
• Es mejor tener unas cuantas operaciones simples que se puedan combinar para
realizar funciones más complejas, que tener un gran número de operaciones
complicadas.
• Cada operación debe tener un propósito bien definido y mostrar un
comportamiento coherente, y no un despliegue de casos especiales.
• El conjunto de operaciones debe ser apropiado, y constar de un número de
operaciones suficiente para realizar los tipos de cómputos que probablemente
necesiten los clientes. Una buena prueba consiste en comprobar que cada
propiedad de un objeto de un determinado tipo puede extraerse. Por ejemplo, si
no hubiese una operación get, no podríamos averiguar cuáles son los elementos
de la lista.
La obtención de información básica no debería ser una complicación para el
cliente. El método size no es estrictamente necesario, ya que podríamos aplicar el
método get sobre los valores incrementales del índice, pero esto resultaría
ineficaz y poco práctico.
• El tipo puede ser genérico: una lista o conjunto, o un grafo, por ejemplo. Puede
ser también específico del dominio: un mapa de calle, una base de datos de
empleados, una guía telefónica, etc. Sin embargo, no se deberían mezclar
características genéricas con aquellas específicas del dominio.
5.6 La elección de las representaciones
53
Hasta ahora, nos hemos centrado en la caracterización de tipos abstractos a través de
sus operaciones. En el código, una clase que implemente a un tipo abstracto facilita
una representación: la estructura de datos propiamente dicha que sustenta las
operaciones. La representación consistirá en una colección de campos, cada uno de los
cuales posee algún otro tipo de Java; en una implementación recursiva, puede que un
campo tenga un tipo abstracto (una clase), pero esto rara vez se hace en Java.
Por ejemplo, las listas encadenadas constituyen una representación común de listas. El
siguiente modelo de objeto muestra una implementación de una lista encadenada
semejante (pero no idéntica) a la clase LinkedList que se encuentra en la librería
estándar de Java:
El objeto lista posee un campo header que hace referencia a un objeto Entry. Un objeto
Entry es un registro con tres campos: next y prev, que pueden mantener referencias a
otros objetos Entry (o pueden ser nulos), y element, que mantiene una referencia a un
objeto que, de hecho, es un elemento almacenado en la lista. Los campos next y prev
son enlaces que apuntan hacia delante o hacia atrás a lo largo de la lista. En la mitad de
la lista, después de una llamada consecutiva a los métodos next y prev , el puntero de la
lista apuntará al objeto apuntado al comienzo, antes de las llamadas a los métodos.
Supongamos que la lista encadenada no almacena referencias nulas como elementos.
Habrá siempre un elemento Entry auxiliar al comienzo de la lista, cuyo campo element
es nulo, pero éste no se interpretará como un elemento.
El siguiente diagrama de objetos muestra una lista con dos elementos:
54
Otra representación diferente de listas utiliza un array. El siguiente modelo de objeto
muestra cómo se representan las listas en la clase ArrayList de la librería estándar de
Java.
A continuación ofrecemos una lista con dos elementos en su representación.
55
Estas representaciones poseen distintas ventajas. La representación de la lista
encadenada será más eficaz cuando haya muchas inserciones en su parte delantera, ya
que puede sumarse un nuevo elemento a la cadena simplemente modificando un par de
punteros. La representación por array, durante una inserción, tiene que promover todos
los elementos que se encuentren por encima del índice del elemento insertado hacia
arriba, aunque si el array es demasiado pequeño, es posible que sea necesario asignar
uno nuevo, mayor que el anterior, y copiar todas las referencias para la creación de una
nueva lista. Sin embargo, si hay muchas operaciones get y set, la representación de la
lista por arrayresulta más conveniente, dado que proporciona acceso aleatorio en tiempo
constante, mientras que la lista encadenada tiene que realizar una búsqueda secuencial.
Es posible que no sepamos qué operaciones predominarán cuándo estemos escribiendo
código para la representación de una lista. La cuestión crucial es entonces, cómo
podemos tener la certeza de que será fácil cambiar las representaciones posteriormente.
5.7 Independencia de representación
La independencia de representación implica el asegurar que el uso de un determinado
tipo abstracto es independiente de su representación, de modo que las alteraciones en
ésta no causen efectos en el código exterior que utiliza el código del tipo abstracto.
Examinemos qué es lo que falla si no hay independencia de representación, y luego
centrémonos en algunos mecanismos del lenguaje que nos ayuden a garantizar la
independencia. Imagine que sabemos que nuestra lista está implementada como un
array de elementos. Estamos intentando utilizar un código que cree una secuencia de
objetos pero, desafortunadamente, este código almacena una secuencia en un objeto
Vector y no en un List. El tipo de datos List que estamos utilizando no ofrece un
constructor capaz de recibir un objeto de tipo Vector y hacer la conversión
automáticamente. Descubrimos que Vector posee un método llamado copyInto que copia
los elementos del vector en un array. Escribimos por tanto, el siguiente código:
List l = new List ();
v.copyInto (l.elementData);
donde v. representa una instancia de un objeto Vector.
Se trata de un truco muy hábil pero que, como la mayoría de los trucos, sólo sirve para
cosas puntuales. Suponga que el implementador de la clase List decide alterar la
representación de la versión que utiliza array para una versión de lista encadenada.
Ahora la lista l no tendrá un campo elementData, como había cuando usaba la
representación de array. Además, el compilador rechazará el programa. Esto es un
fallo de independencia de representación: tendremos que cambiar todos los lugares del
código en los que hicimos esto, es decir, copiar un Vector para un List.
El fallo en la compilación no es tan grave como parece. Sería mucho peor si
funcionara y la alteración averiara el programa, lo que ocurriría del siguiente modo:
En general, el tamaño de un array tendrá que ser mayor que el número de elementos
de la lista, dado que de lo contrario, sería necesario crear un nuevo array cada vez que
un elemento se añade o se quita. Por tanto, debe existir algún modo de marcar el final
de un segmento del array que contenga los elementos. Imagine que el implementador
56
de la lista lo ha diseñado asumiendo que el final de la lista está marcado por una única
referencia nula, que una vez encontrada, se interpretará como el final de la lista de
elementos, o por el final del array propiamente dicho, que se encontró primero.
Afortunadamente (o en este caso, desafortunadamente), nuestro truco sólo funciona
bajo estas circunstancias.
Ahora, nuestro implementador se da cuenta de que esta era una decisión poco acertada,
ya que para definir el tamaño de la lista es necesario realizar una búsqueda secuencial, y
de este modo encontrar la primera referencia nula. Por lo tanto, añade un campo size y
lo actualiza cada vez que una operación altera el contenido de la lista. Esta es una mejor
solución, ya que encontrar ahora el tamaño de la lista puede realizarse en tiempo
constante. Además, la lista podrá manipular de forma natural referencias nulas como
elementos de la lista, motivo por el cual la implementación LinkedList de Java utiliza
esta solución.
En este caso, es probable que nuestro audaz truco produzca algún comportamiento
erróneo cuya causa será difícil de encontrar. La lista que creamos tenía un campo size
con valor cero, a pesar de los muchos elementos que había en la lista (ya que, durante la
copia, actualizamos solamente el array y no el campo size). Las operaciones get y set
aparentemente funcionan; sin embargo, la primera llamada al campo size fallará sin
razón aparente.
Aquí mostramos otro ejemplo. Imagine que tenemos la implementación de la lista
encadenada, y que añadimos una operación que devuelve el objeto Entry
correspondiente a un índice en concreto.
public Entry getEntry (int i)
Nuestro fundamento se basa en que si existen muchas llamadas al método set en el
mismo índice, esto evitará la búsqueda secuencial que consistía en obtener el
elemento reiteradamente. En vez de
l.set (i, x); ... ; l.set (i, y)
podemos escribir ahora
Entry e = l.getEntry (i);
e.element = x;
...
e.element = y;
una alternativa basada en el conocimiento de la representación del dato abstracto que
puede ofrecer ventajas en función del rendimiento, ya que la búsqueda secuencial es
relativamente costosa.
No obstante, esta alternativa también viola la independencia de representación, ya que
cuando haya una alteración en la implementación de List para la representación de
array, no existirán más objetos Entry. Podemos ilustrar el problema con un diagrama
de dependencia de módulos:
57
Debería existir únicamente una dependencia del tipo Client sobre la clase List
(y sobre la clase del tipo element, que es, en este caso, Object). La dependencia de
Client sobre Entryes la causa de nuestros problemas. Volviendo a nuestro modelo de
objeto para esta representación, queremos que la clase Entry y sus asociaciones sean
internas a List. Podemos representar esto de manera informal, pintando de rojo las
partes que deberían ser inaccesibles a la parte Client (si está leyendo una impresión en
blanco y negro, esta parte correspondería a Entry, con todos sus arcos entrantes y
salientes), y de amarillo, la parte denominada Entry, y añadiendo un campo de
especificación elems que oculte la representación:
58
La representación queda explicada en el ejemplo de Entry. Una presentación más
aceptable, y bastante común, surge de la implementación de un método que devuelve
una colección. Cuando la representación contiene ya un objeto colección del tipo
adecuado, resulta tentador devolverlo directamente. Por ejemplo, imagine que List
posee un método toArray que devuelve un array de elementos correspondientes a los
elementos de la lista. Si hubiésemos implementado la lista como un array, podríamos
simplemente devolver el array propiamente dicho. Si el campo size estuviese basado
en el índice en el que una referencia nula aparece por primera vez, una modificación en
este array podría impedir el cálculo del tamaño del mismo.
a =l.toArray (); // expone la representación
a[i] = null; //Mmm..
…
l.get (i); // ahora tiene un comportamiento impredecible
Una vez que size se ha calculado erróneamente, todo puede fallar: las operaciones
posteriores pueden tener un comportamiento imprevisible.
5.8 Mecanismos del lenguaje
Para evitar que se acceda a las representación, podemos definir los campos como
privados, lo que impide poner en práctica el truco del array anteriormente explicado;
por ejemplo, la sentencia
v.copyInto (l.elementData);
sería rechazada por el compilador porque la expresión l.elementData estaría haciendo
referencia, ilegalmente, a un campo privado desde un lugar externo a su clase. El
problema del campo Entry no es tan fácil de resolver. No hay acceso directo a la
representación, sino que la clase List devuelve un objeto Entry que pertenece a la
representación. Esto se conoce como exposición de la representación, y no puede
evitarse únicamente por mecanismos del lenguaje. Es necesario que comprobemos que
las referencias a los componentes mutables internos de la representación no sean
pasados a los clientes externos, y que la representación no se construya a partir de
objetos mutables pasados como argumentos para una representación interna.
En la representación por array, por ejemplo, no podemos permitir un constructor que
reciba un array y lo atribuya al campo interno. Las interfaces están provistas de otro
método para conseguir la independencia de representación. En la librería estándar de
Java, las dos representaciones de listas que tratamos anteriormente son en realidad
clases distintas: ArrayList y LinkedList. Ambas están declaradas como extensiones de
la interfaz List. La interfaz rompe la dependencia entre el cliente y otra clase, en este
caso la clase de representación:
59
Este enfoque es bueno porque una interfaz no puede tener campos (no estáticos), por lo
que nunca se plantea la cuestión de acceder a la representación. Sin embargo, debido a
que las interfaces de Java no pueden tener constructores, puede ser incómodo utilizar
este recurso en la práctica, ya que la información relativa al modo de invocar a los
constructores compartidos entre las clases de la implementación que están en una
misma interfaz, no puede expresarse a través de ésta. Además, dado que el código
cliente debe, en algún punto, construir objetos, existirán dependencias sobre clases
concretas (que obviamente trataremos de localizar) y no sólo sobre la interfaz, como
supone la práctica del desacoplamiento. El patrón Factory, que iremos viendo a lo largo
de esta asignatura, trata este problema en particular.
5.9 Resumen
Los tipos abstractos se caracterizan por sus operaciones. La independencia de
representación hace posible la alteración de la representación de un tipo, sin que sus
clientes tengan que ser alterados también. En Java, los mecanismos de control de
acceso y las interfaces pueden ayudar a garantizar la independencia de representación.
No obstante, la exposición de la representación es más complicada, ya que puede forzar
la utilización de un tipo abstracto, y es por tanto necesario, que sea manipulada dentro
de una esmerada disciplina de programación.
60
61