PDF de programación - Clase 6: Invariantes de representación y funciones de abstracción

Clase 6: Invariantes de representación y funciones de abstracción

6.1 Introducción

En esta clase, vamos a describir dos herramientas utilizadas para la comprensión de tipos de datos
abstractos: los invariantes de representación y la función de abstracción. El invariante de representación
describe si una instancia de un determinado tipo está bien formada; la función de abstracción nos indica
cómo debemos interpretarla. Los invariantes de representación pueden aumentar el poder de las pruebas.
Resulta imposible codificar un tipo abstracto o modificarlo sin comprender la función de abstracción, al
menos informalmente. Escribir tal función es útil, especialmente para el mantenimiento del software, y
resulta crucial en situaciones complicadas.

6.2 ¿Qué es un invariante Rep?

Un invariante de representación, o invariante Rep, en forma abreviada, es una restricción que, desde el
punto de vista de la representación, caracteriza si una instancia de un tipo de datos abstracto está o no
bien formada. Matemáticamente, es una fórmula relacionada con la representación de una instancia;
puede considerarla como una función que recibe objetos de un determinado tipo abstracto y devuelve los
valores true o false dependiendo de si están o no bien formadas:

RI : Object -> Boolean

Considere la implementación de lista encadenada que estudiamos en el tema anterior. Aquí le mostramos
su modelo de objeto:

next

?

?

List

?
header

!

Entry

element

?
Object

?

?

prev

La clase LinkedList posee un campo, header, que mantiene una referencia a un objeto de la clase Entry.
Este objeto posee a su vez tres campos: element, que mantiene una referencia a un elemento de la lista;
prev, que apunta a la entrada anterior de la lista de datos; y next, que apunta al elemento posterior a lo
largo de la lista.

Este modelo de objeto muestra la representación del tipo de datos abstracto. Como hemos mencionado

59

antes, los modelos de objeto pueden diseñarse en varios niveles de abstracción. Desde el punto de vista
del usuario de la lista, se podría elidir el recuadro que representa a Entry, y simplemente mostrar un
campo de especificación de List para Object. Este diagrama muestra ese modelo de objeto en negro, con
la representación en dorado (Entry y sus arcos entrantes y salientes) escondida:

elems[]

next

?

?

List

?
header

!

Entry

element

?
Object

?

?

prev

El invariante de representación es una restricción válida para todas las instancias del tipo. Nuestro modelo
de objeto nos ofrece algunas de sus propiedades:
· Muestra, por ejemplo, que el campo header mantiene una referencia para un objeto de la clase
Entry. Esta propiedad es importante, pero no demasiado interesante, ya que el campo ya se ha
declarado para poseer ese tipo; este tipo de propiedad es más interesante cuando se utiliza para
expresar el contenido de contenedores polimórficos, como los vectores, cuyo tipo de elemento no
puede expresarse en código fuente.

· El signo de multiplicidad ! al final de la flecha del campo header indica que el campo header no puede

ser nulo. (El símbolo ! indica exactamente uno).

· El signo de multiplicidad ? al final de las flechas de los campos next y prev indica que cada flecha de

next y prev apunta como máximo a una entrada. (El símbolo ? denota cero o uno).

· El signo de multiplicidad ? al inicio de las flechas de los campos next y prev indican que cada entrada

(objeto Entry) es apuntada como máximo por otro campo next, y como máximo por otro campo prev. (El
símbolo ? denota cero o uno).

· El símbolo de multiplicidad ? al final de la flecha del campo element indica que cada Entry apunta como

máximo a un Object.

Algunas propiedades del modelo de objeto no son parte del invariante de representación. Por ejemplo, el
hecho de que los objetos Entry no estén compartidos entre las listas (lo cual está indicado por la
multiplicidad al inicio de la flecha del campo header) no es una propiedad de ninguna lista individual.

Existen propiedades del invariante de representación que no se muestran en el modelo gráfico de objeto:
· Cuando hay dos entradas e1 y e2 en la lista, si e1.next = e2, entonces e2.prev =

e1.

60

· La entrada opcional en cabeza de lista posee un campo element.
Existen también propiedades que no aparecen porque el modelo de objeto sólo muestra objetos y no
valores primitivos. La representación de LinkedList posee un campo size que mantiene el tamaño de la
lista. Una propiedad del invariante Rep es que el valor de size es igual al número de entradas de la
representación de la lista menos uno (dado que la primera entrada es un auxiliar).

En realidad, en la implementación de Java java.util.LinkedList, el modelo de objeto posee una restricción
adicional, reflejada en el invariante Rep. Toda entrada, es decir, todo objeto Entry, posee campos no nulos
como next y prev:

next

!

!

List

?
header

!

Entry

element

?
Object

!

!

prev

Observe los signos de multiplicidad en negrita en las flechas next y prev. Aquí puede observar una lista de
ejemplo de dos elementos (y por tanto, tres entradas, si incluimos el elemento auxiliar):

( List )

header

( Entry )

next

( Entry )

element

next

prev

prev

next

prev

( Entry )

element

( Object )

( Object )

61

Cuando se examina un invariante de representación, es importante darse cuenta no sólo de qué
restricciones están presentes, sino también de cuáles faltan. En este caso, no es necesario que el campo
element sea non-null, ni que no se compartan los elementos. De este modo podemos esperar lo siguiente:
una representación permite que una lista contenga referencias null, y que posea al mismo objeto en
múltiples posiciones.

Resumamos nuestro invariante Rep informalmente:
Para cada ejemplo de la clase LinkedList

el campo header es non-null
el campo header posee un campo element con valor null
existen (size + 1) entradas
las entradas forman un ciclo que se inicia y acaba con la entrada header
para cualquier entrada, tomar prev y luego next, le devuelve a la entrada, es decir, al mismo lugar

Podemos escribir esto también de un modo algo más formal:

para todo p: LinkedList |

p.header != null
&& p.header.element = null
&& p.size + 1 = | p.header.*next |
&& p.header = p.header.next
&& para todo e en p.header.*next | e.prev.next = e

p.size + 1

Para comprender esta fórmula, es necesario que sepa que:
· para cualquier expresión que represente a un conjunto de objetos, y para cualquier campo f: e.f
representa el conjunto de objetos que se alcanza cuando se sigue a f a partir de cada objeto en e;
· e.*f representa el conjunto de objetos obtenidos al seguir f un número arbitrario de veces a partir de

cada uno de los objetos en e;

· | e | es el número de objetos del conjunto representado por e.
Así que p.header.*next, por ejemplo, representa al conjunto de todas las entradas de la lista, ya que este
conjunto se consigue a través de la lista p, siguiendo al campo header y luego al campo next cualquier
número de veces.
Lo que se ve muy claro a través de esta fórmula, es que el invariante de representación hace referencia a
una única lista encadenada p. Otro modo de escribir el invariante sería éste:

R(p) =

p.header != null
&& p.header.element = null
&& p.size + 1 = | p.header.*next|
&& p.header = p.header.next
&& para todo e en p.header.*next | e.prev.next = e

p.size + 1

en la que consideramos al invariante como una función booleana. Éste es el punto de vista que
adoptaremos cuando convirtamos el invariante en código como una aserción en tiempo de ejecución.

La elección del invariante puede tener un efecto importante tanto en la dificultad de escribir el código de la
implementación del tipo abstracto, como en la evaluación del funcionamiento de dicho código.
Imagine que reforzamos nuestro invariante, al ser necesario que el campo element de todas las entradas,
a excepción de header, sea non-null. Esta alteración nos permitiría detectar la entrada header, al
comparar su campo element con el valor null; con el invariante que actualmente estamos utilizando como
ejemplo, las operaciones que requieran atravesar la lista, deben contener entradas en vez de comparar el
campo element de header.

62

Imagine, por el contrario, que debilitamos el invariante en los punteros next y prev y permitimos que prev
al inicio y next al final, tengan cualquier valor. El resultado será la necesidad de un tratamiento especial
para las entradas al inicio y al final, dando como resultado un código menos uniforme. Exigir que tanto
prev al inicio como next al final, sean valores null, no sirve de mucha ayuda.

6.3 Razonamiento por inducción

El invariante de representación hace que el razonamiento modular sea posible. No es necesario verificar
ningún otro método para comprobar si una operación se ha implementado correctamente. En su lugar,
hacemos un llamamiento al principio de inducción. Garantizamos que cada constructor crea un objeto que
satisface el invariante, y que cada método mutador y productor conserva al invariante, es decir: si se da un
objeto que satisface estos requisitos, se produce otro que también los cumple. De este modo, podemos
decir que cada objeto de un determinado tipo satisface el invariante Rep, dado que éste debe haber sido
producido por un constructor o alguna secuencia de aplicaciones mutadoras o productoras.

Para ver cómo funciona esto, observemos algunos ejemplos de operaciones de nuestra clase LinkedList.
En Java, la representación es declarada como se muestra a continuación:

public class LinkedList {

Entry header;
int size;
class Entry {

Object element;
Entry prev;
Entry next;
Entry (Object e, Entry p, Entry n) {element = e; prev = p; next =