![[UACA]](../../img/escudo02.gif)
|
|
|
|
|
Init(o) y no a o.Init(). El nombre
genérico de tipos de datos que se usa al especificar cada
operación es "TObj", el que
en la práctica debe ser sustituido por el nombre del tipo
abstracto de datos que el programador está
implementando.
Cada operación se especifica en una sección aparte, que contiene primero la especificación en Pascal de la operación. Como estas operaciones son muy generales, pues pueden ser definidas para cualquier ADT independientemente de cuál será su uso, se incluye también una breve discusión que justifica la existencia de la operación. La idea es que la especificación Pascal que aparece en cada sección, es la plantilla de la especificación que el programador usará en sus programas, y los comentarios adicionales son el sustento teórico que sustenta cada especificación. En la Figura 3.2 está la lista de operaciones descritas en este capítulo.
El código Pascal está escrito de acuerdo con las convenciones expuestas en [DiM-88a].
4.1
Init(o)
![[<>]](../../img/index.gif)
![[\/]](../../img/bottom.gif)
![[/\]](../../img/top.gif)
![[<>]](../../img/star.gif)
PROCEDURE Init( { EXPORT } { ADH }
{-} VAR o : TObj { SELF }
);
{ RESULTADO
Inicializa a "o" para que tenga el valor nulo. }
Init(o)
En la Figura 4.1 está la
especificación genérica del constructor
Init() para un objeto "o" de tipo
"TObj". Init(o) inicializa la variable
"o", posiblemente usando
memoria dinámica o dando
valores a los campos del
Rep del ADT. Por ejemplo, si
el ADT se
implementa
usando punteros, entonces Init() puede encargarse de
inicializarlos a NIL para que luego puedan ser
utilizados en las otras operaciones.
En muchas ocasiones la implementación de
Init(o) se reduce a llenar de ceros binarios
[0000] el Rep(o), mientras que en otros
será necesario crear en memoria dinámica complicadas
estructuras desde "o".
Para cada
variable debe haber exactamente
una invocación al constructor; algunos prefieren ponerla al
principio del bloque en que está definida la variable.
Además, si el espacio para la
instancia fue obtenido de la
memoria dinámica mediante
NEW(), inmediatamente después de esa
invocación debe estar el llamado al constructor
Init(), para que quede en un estado inicial
válido, listo para utilizarlo en cualquier
operación. Algunos lenguajes avanzados, como C++, al
compilar un programa generan la invocación a
Init() en el lugar en que cada
objeto está definido, lo
que ayuda mucho al programador, pues reduce la posibilidad de que
use objetos que no han sido inicializados correctamente. Una
discusión compacta y completa de constructores y
destructores se encuentra en el artículo
[Car-96].
Todas las operaciones de un ADT sólo trabajan sobre objetos que
han sido adecuadamente inicializados mediante Init().
Los programadores conocen tan bien esta regla que lo usual es no
mencionarla siquiera. No inicializar un ADT es un pecado mortal,
hasta el punto de que el inicializar correctamente las variables
es una de las primeras reglas que aprende cada programador. Sólo
el constructor Init() es capaz de inicializar el
Rep del ADT.
La tentación de no inicializar objetos es muy grande. No en pocas ocasiones se han propuesto esquemas para "liberar" al programador del "tedio" de la inicialización [Wie-86]. Acostumbrarse a usar objetos no inicializados presenta al menos estos problemas:
Lo mejor es usar el enfoque de C++: permitirle al programador definir qué hacer cada vez que se necesita inicializar un objeto, y hacer al compilador responsable de invocar las rutinas de inicialización inmediatamente después de que el objeto ha sido creado.
4.2
Clear(o)
PROCEDURE Clear( { EXPORT } { ADH }
{?} VAR o : TObj { SELF }
);
{ RESULTADO
Deja al objeto "o" exactamente en el estado que
tuvo inmediatamente después de que Init() lo
inicializó.
- El valor anterior de "o" desaparece. }
Clear(o)
En la Figura 4.2 está la
especificación genérica para la operación
Clear(o), que se encarga de reinicializar la variable
"o". El valor anterior de "o" se pierde,
y su valor actual pasa a ser exactamente el que tuvo
inmediatamente después de que se le inicializó por
medio de Init(o). O sea que Clear() es
un "destructor suave", pues no inutiliza totalmente a
"o", aunque sí le borra totalmente su anterior
contenido. Esta operación se menciona en este trabajo
porque es fácil de especificar, y sirve para definir con
exactitud qué significa limpiar el valor de una variable,
lo que ocurre con frecuencia cuando se usan contenedores.
Puede decirse que el efecto de invocar Clear() es
equivalente a invocar
Done() seguido
inmediatamente
de
Init(). Como a veces
invocar primero Done() y luego Init()
produce efectos secundarios no deseados, es conceptualmente
más simple usar Clear(). En otros casos sucede
que una vez que un objeto ha sido destruido con
Done(), ya no es posible reconstruirlo con
Init(). Por ejemplo, si uno de los campos del ADT es
un archivo, entonces al aplicar Done() sobre la
variable el archivo quedaría cerrado, que seguramente no es
lo más adecuado para el
programador cliente.
A veces no es posible implementar Clear().
Además, si el efecto que tendría sobre un objeto es
devastador, no tiene sentido definir la operación. Esto es
lo que ocurre con los objetos que serán almacenados en un
contenedor parametrizado con la
técnica desarrollada en esta
investigación, pues no se puede borrar el valor de un
elemento almacenado en un contenedor sin sacarlo del contenedor.
Lo peor del caso, es que al anular con Clear() el
valor de un
ADT contenido, como efecto
secundario el contenedor que lo contiene quedaría
destrozado.
Como Clear() anula completamente el valor del ADT,
conviene contar con una operación menos destructiva, como
Erase(), que se discute en
la siguiente sección.
4.3
Erase(o)
PROCEDURE Erase( { EXPORT } { ADH }
{?} VAR o : TObj { SELF }
);
{ RESULTADO
Borra el valor del objeto.
- Su efecto es similar al de Clear(), pero no es
una operación tan devastadora. }
Erase(o)
En la Figura 4.3 está la
especificación genérica para la operación
Erase(o), que sirve para limpiar la variable. El
significado de la palabra "borrar" que se usa en esta
especificación es, por supuesto, diferente para cada ADT.
Otros nombres adecuados para esta operación son
Reset() o ReInit()
[Mof-86], aunque es mejor no
usar Reset() porque ese es el nombre del
procedimiento estándar Turbo Pascal para abrir archivos en
modo de lectura.
En la práctica el
programador cliente necesita
usar Erase(), pero como esta operación no se
puede especificar genéricamente, conviene contar con la
especificación de
Clear(), para usarla como
referencia.
Erase() es una operación que ha nacido por la
necesidad de definir lo que significa limpiarle el valor a un
objeto, pero sin inutilizarlo. Por
analogía, el efecto de Erase() es similar a
asignarle cero a una variable numérica, o NIL
a un puntero. Erase() existe porque algunas
operaciones del ADT cambian el valor original del objeto, y
necesitan dejarlo con un valor preestablecido que permita usarlo
luego; lo cómodo sería usar el mismo valor que
Init() le asignó al inicializarlo, que es
precisamente el efecto de usar
Clear(), pero ese estado
en muchos casos limpia más de lo que el
programador cliente necesita.
Clear() vs Erase()
Un ejemplo de la diferencia entre
Clear() e
Erase() es el resultado de borrarle el valor a un
objeto como el que aparece en la
Figura 4.3a, que tiene varios
punteros a valores almacenados en
memoria dinámica. El
efecto de Erase() en este caso sería, por
ejemplo, dejar el campo ".v" en cero, sin devolver la
memoria dinámica asociada al objeto, que es lo que
seguramente debería hacer Clear().
En aquellas ocasiones en que es imposible implementar la
operación Clear(), a veces es posible
implementar Erase(), que no deja al ADT exactamente
como lo dejara
Init(), pero que lo deja
suficientemente limpio y listo para ser usado.
Erase() es una versión restringida de
Clear(), que tiene sus
beneficios pero no sus limitaciones.
4.4
Done(o)
PROCEDURE Done( { EXPORT } { ADH }
{?} VAR o : TObj { SELF }
);
{ RESULTADO
Destruye totalmente al objeto "o".
- En general, la destrucción de un objeto consiste
en devolverle al manejador de memoria dinámica
toda la memoria dinámica que usa, y cerrar sus
archivos.
- "o" queda inusable, hasta el punto de que la única
manera de volver a utilizarlo es reinicializándolo
por medio de Init(). }
Done(o)
En la Figura 4.4 está la
especificación genérica para Done(o),
el destructor del ADT, que generalmente se encarga de retornar al
sistema toda la
memoria dinámica que el
objeto usa. Done() es el inverso de
Init(), pues es una
operación totalmente terminante. Deja completamente
inservible el objeto "o", hasta el punto de que para
volver a utilizarlo es necesario inicializarlo de nuevo con
Init() .
Para toda variable debe hacerse exactamente una invocación
a Done(). Si la variable "o" está
definida en un procedimiento, entonces el programador debe
asegurarse de invocar a Done(o) antes de que el
procedimiento retorne. Si la instancia del ADT está en
memoria dinámica, pues fue creada por medio de
NEW(), el programador debe asegurarse de que se
invoque Done() antes del llamado a
DISPOSE() que liberará la memoria de la
instancia. Si la instancia fue creada en un procedimiento al que
no se retornará porque al producirse una excepción
el control del programa saltará directamente al
procedimiento en donde está definido el contexto de
excepción activo más cercano, entonces es necesario
destruir de alguna manera el objeto antes de que el programa
continúe su ejecución normal.
Init() y Done() pueden verse como los
paréntesis que encierran la existencia de cada objeto, pues
nunca puede usarse una variable antes de inicializarla con
Init() o después de destruirla con
Done().
Si en un programa se usa el paquete de excepciones descrito en
[DiM-94j], al destruir el
objeto también se le desliga de su contexto de
excepción, por lo que si se reinicializa de nuevo con
Init() el resultado será que queda ligado al
contexto actual de excepción, y no al anterior. Este es un
ejemplo de por qué Clear() no es siempre
equivalente a invocar Done() seguido inmediatamente
de Init().
En algunos casos un programador diestro puede retardar el uso de
Init(), o adelantar el de Done(), para
ahorrar memoria, pero esto debe hacerlo con sumo cuidado, pues es
muy difícil corregir los errores de programación que
se producen al usar objetos inadecuadamente inicializados. Un
error muy difícil de detectar es invocar varias veces el
destructor de un objeto, pues este error puede provocar la
destrucción de las estructuras de datos que se usan para
manejar la memoria dinámica.
El compilador C++ se encarga de insertar en el código
generado la invocación a Done(), de la misma
forma en que se encarga de insertar el llamado a
Init(), y esto facilita mucho la programación.
Desafortunadamente, en Pascal el programador debe ser muy
disciplinado al inicializar y destruir cada instancia de un ADT,
de tal modo que siempre incluya exactamente un llamado a
Init() y otro a Done() para cada
instancia de un ADT.
Muchos
autores tienen la opinión de que el compilador debe cargar
con la responsabilidad de liberar la memoria, por lo que apoyan el
uso de lenguajes que incorporan un Recolector de
basura, que realiza esta tarea automáticamente,
sin intervención o control del programador. Aunque, para
que un programa esté correcto, es esencial que todas sus
variables estén debidamente inicializadas mediante
Init(), no es tan importante destruirlas porque,
después de todo, Done() se invoca precisamente
porque una variable no se usará más. Sin embargo,
hay por lo menos tres razones por las que los programadores
prefieren no usar sistemas de recolección de basura:
Los programas que no tienen entre sus requerimientos alcanzar un alto grado de eficiencia pueden ser implementados usando recolectores de basura, pero, en el caso contrario, el programador se rehusará a usar un lenguaje que no le permita desactivar este mecanismo para recuperar la memoria dinámica que ya no está en uso.
En muchos casos las operaciones Init(),
Clear(), Erase() y Done()
están implementadas de la misma manera, aunque
conceptualmente son muy diferentes.
4.5
Copy(x,y)
PROCEDURE Copy( { EXPORT } { ADH }
{?} VAR x : TObj; { SELF }
{+} VAR y : TObj { objeto fuente a copiar }
);
{ RESULTADO
Copia todo el valor del objeto "y" sobre "x", de
forma que el nuevo valor de "x" sea un duplicado
exacto del valor del "y".
- El valor anterior de "x" se pierde.
- El objeto "y" mantiene su valor anterior.
- Luego de la copia, cuando el valor de "y" cambia,
el de "x" no cambiará, y viceversa, pues la copia
es una copia profunda; no es superficial.
- Si "x" es "y" entonces su valor no cambia.
- Después de esta operación siempre ocurre que
Equal(x,y) es TRUE. }
Copy(x,y)
En la Figura 4.5 está la
especificación genérica para Copy(x,y),
que se encarga de crear en "x" un duplicado exacto de
"y". Por analogía a la instrucción de
asignación de Pascal
"x := y;" la
dirección de copia es de derecha a izquierda:
x <- y (esta forma
de ordenar los parámetros viene desde los días de
programación en lenguaje Ensamblador).
Cuando se hace una copia profunda del objeto "y"
sobre "x" no puede quedar memoria compartida entre
estas dos
instancias, y resulta que ambos
objetos ocupan un espacio diferente en la memoria del computador.
Algunos programadores novatos creen que el trabajo realizado por
Copy() siempre es equivalente al que se obtiene al
escribir la asignación Pascal
"x := y;". Esta instrucción lo que
hace es hacer una copia superficial bit por bit de todo el
contenido del
Rep de la variable
"y" sobre la variable "x", pero, si se
trabaja con objetos complejos, lo usual es que una parte de ellos
esté en
memoria dinámica, y en
estos casos al copiar únicamente los campos que forman el
Rep no se copiarían todos los demás datos
que aparecen en otros lugares de la memoria. O sea que, en lugar
de obtener una copia profunda, en el mejor de los casos se
obtendría una copia superficial.
Por ejemplo, si el objeto por copiar es un árbol con una
complicada estructura de punteros, al copiarlo habría que
recorrerlo todo y reproducir cada uno de sus nodos y cada una de
sus conexiones. Para copiar el árbol no basta sólo copiar
su nodo raíz, es necesario también copiar todos los
nodos a ella conectados. Si para hacer el duplicado se usara la
instrucción de asignación Pascal
"x := y;", se copiaría
únicamente el nodo raíz, y el resultado sería
dos nodos raíz que apuntan al mismo conjunto de
descendientes. Si ambos árboles comparten algunos
componentes, entonces, al cambiar el valor de uno de ellos,
cambiaría también el del otro, pues tienen partes en
común: serían árboles siameses.
Existen ADT's que no se pueden copiar. Uno muy sencillo es un objeto cuyo valor depende de la posición física de memoria en donde está almacenado: al copiarlo, el valor obtenido sería diferente del valor original (ver Figura 4.6b). Pese a todas estas consideraciones, para la mayoría de los objetos la copia se puede hacer simplemente copiando bit por bit los campos del Rep.
Copy() es una operación muy importante, hasta
el punto de que en C++ el compilador genera su
implementación automáticamente si el programador no
escribe la implementación. Para evitar los problemas que
conlleva el hacer una copia superficial bit por bit, el compilador
C++ invoca el Copy() de cada uno de los campos que
forman el Rep del objeto.
Es muy común que en la implementación de
Copy() se invoque
Clear(), o
Erase(), para limpiar el
valor de la variable resultado. Como a veces no es fácil
programar Copy(), es prudente que el programador sea
cuidadoso al implementarla. A veces es difícil evitar que
la copia comparta memoria con el objeto original. En este caso se
corre el riesgo de introducir un error en el programa que es muy
difícil de detectar, pues la falla se puede manifestar
mucho después de hecha la copia.
En otras ocasiones hay que evitar copiar objetos debido al costo
en uso de memoria y tiempo de ejecución que esta
operación conlleva. Por ejemplo, lo usual es no copiar
árboles, porque generalmente son muy grandes y contienen
información que no se necesita duplicar. Muchas veces lo
que hace falta es trasladar el valor del árbol de una
variable a otra. En estos casos, tiene sentido usar el
Move() en lugar del
Copy(). Mucho se ha escrito sobre cómo usar
Copy() correctamente, pues es una de las operaciones
más usadas en cualquier programa. Por ejemplo, en
[Din-92] se muestra la
relación que hay entre esta operación y la
eficiencia al evaluar expresiones.
Como Copy() es una operación relativamente
cara de ejecutar, es usual que los argumentos se pasen por
referencia a las subrutinas. Además, como Pascal no invoca
automáticamente la operación Copy()
para pasarle a un procedimiento argumentos que no pasan por
referencia, lo que sí hace C++, la copia que recibe el
procedimiento invocado no es una copia adecuadamente construida.
El programador novato a veces no entiende estos detalles, e
introduce errores muy difíciles de detectar en su programa.
Por eso todo procedimiento que recibe un ADT como argumento, debe
definirlo como un parámetro VAR.
Aunque es un poco complicado, es posible definir con exactitud
cuál trabajo debe hacer Copy(). Lo mismo no
ocurre con la operación de copia superficial
Shallow_Copy(), en cuya implementación el
programador puede evitar hacer una copia profunda y ahorrar un
poco de recursos en tiempo de ejecución. El valor que
Shallow_Copy() produce dependerá mucho de cada
ADT.
4.6
Clone(o,p)
PROCEDURE Clone( { EXPORT } { ADH }
{?} VAR o : TObj; { SELF }
{?} VAR p : PObj { Dónde dejar el duplicado }
);
{ RESULTADO
Crea en "p^" un duplicado del valor del objeto "o".
- Si p=NIL entonces el espacio para almacenar al
nuevo valor será tomado de la memoria dinámica.
- De otra manera el valor anterior de "p^" se pierde.
- "o" siempre mantiene su valor anterior.
- Luego de la copia, cuando el valor de "p^" cambia,
el de "o" no cambiará, y viceversa, pues la copia
es una copia profunda; no es superficial.
- Si "p = @o", entonces el valor de "o" no cambia. }
Clone(o,p)
En algunos casos es más cómodo para el programador,
o más eficiente, duplicar el valor de una variable
invocando Clone(o,p) en lugar de
Copy(). La
especificación de esta operación está en la
Figura 4.6.
Clone(o,p)
Si ya el ADT tiene la operación Copy(), una
manera de implementar Clone() es la que se muestra en
la
Figura 4.6a. En forma
análoga se puede implementar Copy() invocando
a Clone().
Como se muestra con el ejemplo de la
Figura 4.6b, existen ADT's para
los que sí se puede implementar
Clone() pero no
Copy(). Por ejemplo, un
objeto puede incluir un campo que apunte hacia sí mismo, lo
que implica que puede ser duplicado con Clone(), pero
no copiado, pues en la especificación de
Copy() explícitamente se exige que la
función de comparación
Equal() siempre debe
retornar verdadero cuando se compara un objeto con su copia.
Aunque Clone() y Copy() representan
conceptos muy similares, y sus especificaciones son muy parecidas,
en la práctica cada programador puede encontrar situaciones
que tornan diferentes estas dos operaciones.
4.7
Move(x,y)
PROCEDURE Move( { EXPORT } { ADH }
{?} VAR x : TObj; { SELF }
{?} VAR y : TObj { objeto por trasladar }
);
{ RESULTADO
Traslada el valor de "y" a "x".
- El valor anterior de "x" se pierde.
- El nuevo valor de "x" es el que "y" tuvo.
- "y" queda en el estado en que lo dejaría
Erase().
- Si "x" es "y" entonces su valor no cambia.
- En general, después de esta operación casi
nunca ocurre que Equal(x,y) es TRUE. }
{ EFICIENCIA
<< nota sobre la eficiencia relativa de >>
<< Move() repecto a Copy(). >>. }
Move(x,y)
En la Figura 4.7 está la
especificación genérica de la operación
Move(x,y), que traslada el valor de "x"
y lo deja "y". En esta especificación se hace
referencia al estado en que
Init() deja un objeto
después de inicializarlo, pues en muchos casos la
implementación de Move(x,y) lo que hace es
"quitarle" el valor a "y" para pasárselo a
"x", lo que deja "sin valor" a "y";
generalmente, ese es el estado inicial de una variable
después de que Init() la ha inicializado. La
existencia de la operación Move(x,y) justifica
la de
Erase() (o la de
Clear()). Para ADT's
simples, la operación Move(x,y) se implementa
con una simple asignación seguida de una invocación
a Erase(y) (o a Clear(y)).
La operación Move() existe porque es mucho
más eficiente de implementar que Copy(), para
aquellos ADT's de estructura complicada que mantienen parte de su
valor en
memoria dinámica, como
ocurre con la mayoría de los contenedores. Por ejemplo,
para trasladar el valor del árbol "Ty" a
"Tx", invocando a Move(Tx,Ty), basta
copiar únicamente el nodo raíz de "Ty"
sobre "Tx", y tal vez actualizar algunos punteros que
antes apuntaban hacia "Ty" para que apunten a
"Tx". El trabajo total es mucho menor que el
necesario para hacer una copia profunda completa de
"Ty". Move() se puede usar en los casos
en que no es necesario conservar en la variable fuente el valor
original, lo que es común, pues generalmente se necesita
que en la memoria exista sólo una copia del objeto
trasladado.
En general, casi todas las implementaciones de
Move(x,y) comienzan limpiando el objeto resultado
invocando
Erase().
Move() puede verse como un método de
programación, que permite pasar un objeto de un lugar a
otro de una manera eficiente (o rápida). Es muy útil
para insertar un objeto en una estructura de datos complicada como
un árbol o una lista, y también sirve para ordenar
los objetos que están en un vector.
Como parte de la especificación de Move() es
prudente que el programador defina si la implementación
Move() es más eficiente que la de
Copy(), o si ocurre lo
contrario. Para esto el programador debe calcular el costo de
recursos en que incurren Copy() y
Move(). Por eso en la especificación de la
Figura 4.7 se incluye la
anotación "EFICIENCIA".
Ocurre a veces que no es posible implementar la operación
Move(). Por ejemplo, es imposible trasladar a un
objeto de tipo TClone_SI_Copy_NO si se le define como
en la
Figura 4.6b, pues al colocarlo
en otro lugar, necesariamente cambiará su valor, lo que
contradice la especificación de Move().
La operación Move() es un buen ejemplo de
cómo la práctica en la implementación de
ADT's ayuda a definir cuál es la abstracción
correcta para una operación. Move() existe
porque en algunos casos sirve para mejorar la eficiencia de los
programas, requerimiento que el buen programador no puede dejar de
lado al definir su abstracción. Al
final de la
sección 2.3 (Diferencias de
este trabajo) se afirma que
los programas no se construyen de lo abstracto a lo concreto, pues
muchas veces hay que tomar en cuenta cuestiones de
implementación para definir una abstracción:
Move() es un ejemplo de cómo la
implementación fuerza cambios en la abstracción. No
es sino hasta que una abstracción se usa en programas
reales, que es posible separar lo esencial de lo subsidiario.
Swap(x,y)
En la parte superior de la
Figura 4.8 está la
especificación genérica para Swap(x,y),
que intercambia el valor de "x" por el de
"y", usando en el proceso una cantidad mínima
de esfuerzo. Puede verse esta operación como una buena
mezcla de las implementaciones de
Copy() y
Move(), y de hecho se
puede implementar usando cualquiera de estas dos operaciones, por
lo que conviene utilizar la que produzca un mejor rendimiento.
Para algunos ADT's es posible escribir implementaciones de
Swap() mucho más eficientes (por ejemplo, se
pueden usar tres XOR's binarios consecutivos para
intercambiar los valores de dos variables).
Swap() es una operación fundamental para
ordenar vectores, pues la mayor parte de los algoritmos de
ordenamiento intercambian los valores del vector hasta que queda
ordenado, lo que justifica con creces incluirla en este estudio,
pues una de las principales funciones que realizan los
computadores es ordenar valores.
x y y
Aunque resulte paradójico, a veces la operación
Swap() toma mucho menos esfuerzo que
Copy() o
Move(). Por ejemplo, si
los objetos tienen su valor almacenado en
memoria dinámica, para
intercambiar sus valores basta intercambiar dos punteros.
Contrasta este esfuerzo con el borrado sistemático que
deben realizar tanto Copy() como Move(),
pues estas dos operaciones deben limpiar uno de sus operandos por
medio de
Erase() (o
Clear()). Pero en otras
ocasiones la implementación de Swap() requiere
un poco más de cuidado, como ocurre cuando el valor de un
objeto incluye punteros desde la memoria dinámica, como se
muestra en la
Figura 4.8a. En este caso, al
hacer el intercambio de valores hay que recordar cambiar
también los punteros desde la memoria dinámica.
En la implementación de la mayor parte de los contenedores
lo usual es utilizar
Copy() para insertar un
nuevo
elemento en el contenedor, por
lo que la operación Swap() pasa desapercibida.
Esto no es lo mejor, como se argumenta en dos artículos que
muestran la importancia de Swap(): primero
está
[HW-91] en donde se discuten las
ventajas de usar Swap() en lugar de
Copy() para manipular valores en un programa. Luego
hay que tomar en cuenta el estudio para mejorar el
QuickSort() que aparece en
[BM-93] (pg 1254), en donde
experimentalmente se muestra el peso de Swap() en la
complejidad de qsort().
4.9
Equal(x,y)
FUNCTION Equal( { EXPORT } { ADH }
{+} VAR x : TObj; { SELF }
{+} VAR y : TObj { objetos por comparar }
) {>>>>>>>} : BOOLEAN;
{ RESULTADO
Devuelve TRUE cuando el valor de "x" es el mismo que
el de "y", y FALSE en caso contrario.
- Dos objetos pueden ser iguales aun cuando no
ocupen exactamente la misma memoria. }
Equal(x,y)
En la Figura 4.9 está la
especificación genérica para
Equal(x,y), que compara los valores de
"x" y de "y" y regresa TRUE
si son iguales. Esta función es un caso particular de una
operación
examinadora, pues nunca
modifica el valor de sus argumentos.
Al definir la igualdad a veces es necesario exigir que las
variables sean iguales sólo cuando "x" y
"y" ocupan exactamente la misma localización
de memoria, condición que verifica la función
(Equal x y) de Lisp. A esto se le llama la
"semántica Is_Shared"
[Boo-87]. En muchos casos esta
manera de computar la igualdad puede inducir errores en el
programa
[Gon-91]: después de
Copy(), la operación Equal() es
la más utilizada en los programas, por lo que conviene que
el programador sea cuidadoso al implementarla.
En la mayoría de las ocasiones se necesita una
definición de igualdad que constate que la estructura de
"x" es isomórfica con la de "y",
o sea que, campo por campo, los valores del
Rep sean iguales. En algunas
ocasiones la definición de igualdad es mucho más
relajada; por ejemplo, se puede considerar que dos instancias del
objeto TPersona son iguales si tienen el mismo
número de identificación, aunque difieran algunos de
sus atributos. Si el programador encuentra necesario definir
así la igualdad, es mejor que le agregue a su
ADT la operación
Similar(x,y), pues lo razonable es que la
definición de Equal() sea la que el cliente
del ADT espera, y no una que requiera una alambicada
especificación. De todas maneras, es importante que no sea
necesario conocer la implementación de un ADT para
determinar si el concepto de igualdad que Equal()
implementa es el correcto.
4.10
Less(x,y)
FUNCTION Less( { EXPORT } { ADH }
{+} VAR x : TList; { SELF }
{+} VAR y : TList { objetos por comparar }
) {>>>>>>>} : BOOLEAN; { TRUE cuando (x < y) }
{ RESULTADO
Devuelve TRUE si "x < y" y FALSE en otro caso. }
Less(x,y)
En la Figura 4.10 está la
especificación genérica para Less(x,y),
que compara los valores de "x" y de "y"
y regresa TRUE si el primero es menor que el segundo.
En general no es posible definir una relación de orden para
cualquier ADT. Por ejemplo, para el ADT TConjunto la
relación de inclusión es un orden parcial, pero no
siempre se cumple que dos instancias sean comparables. Por
ejemplo, si x = [1,2,3] y
y = [1,2,3,4,5,6], entonces se cumple que
TConjunto.Less(x,y) = TRUE, pero si
z = [8,9], no es cierto que
TConjunto.Less(x,z) = TRUE ni que
TConjunto.Less(z,x) = TRUE. Por eso no
siempre es posible implementar la operación
Less().
Cuando una relación de orden es asimétrica se cumple
que:
Less(x,y) AND Less(y,x) ==> Equal(x,y)
Sin embargo, muchas veces ocurre que esta propiedad no se cumple,
por lo que es saludable que en la especificación de
Less() se aclare este punto.
Greater_Equal(x,y)
Una vez que se han definido Equal() y
Less(), es posible definir las otras operaciones de
comparación. Por ejemplo, la función
Greater_Equal() se muestra en la
Figura 4.10a.
4.11
OK(o)
FUNCTION OK( { EXPORT } { ADH }
{+} VAR o : TObj { SELF }
) {>>>>>>>} : BOOLEAN;
{ RESULTADO
Verifica que el objeto "o" cumpla con la invariante
de "TObj", o sea, que esté construido
adecuadamente. }
{ REQUIERE
- Retorna TRUE si "o" es un objeto bien construido.
En caso contrario, es posible que no retorne, o
que el programa se cancele.
- OK() no es un procedimiento realmente correcto,
pues es posible que no regrese si la invariante
del ADT no se cumple para la instancia "o". }
OK(o)
En la Figura 4.11 está la
especificación genérica para OK(o), que
verifica que la
invariante del ADT se cumpla,
sin cambiar el valor de la
instancia. La invariante es un
predicado, a veces expresado en forma matemática, que
siempre se cumple para una instancia del ADT. Por ejemplo, en una
lista la invariante puede ser que a cada nodo siguiente le apunte
el anterior, y que la lista nula se representa como
NIL. En este ejemplo, OK(L) será
verdadero siempre que la lista "L" esté
correctamente construida, y que también lo estén sus
elementos.
La operación OK() es, en general, muy
difícil de implementar, pues es natural que el programador
crea que funcionará aun si la
instancia del ADT tiene un
valor inválido. Pero corregir el valor de una instancia no
siempre es posible, y casi siempre es muy difícil, por lo
que esta operación ha sido definida de manera que retorne
TRUE siempre que la instancia del ADT cumple con su
invariante y, cuando no es ese el caso, pues se hace un esfuerzo
para retornar el valor FALSE.
En buena teoría, toda implementación de cualquier
ADT debe garantizar que el uso de las operaciones nunca invalide
la invariante que OK() vigila. Desafortunadamente, en
la práctica las cosas no siempre son tan perfectas, pues no
existe forma de garantizar que un programa está libre de
errores
[Mye-78]. Para aquellos ADT's
para los que sí es posible implementar OK(), a
veces el costo de hacerlo brinda grandes réditos. Por
ejemplo, es conveniente que los estudiantes que comienzan a
programar usen ADT's para los que la operación
OK() sí está implementada, para que al
usarla detecten rápidamente los errores que cometen y de
esa manera aprendan en menos tiempo.
Como ejemplo de la dificultad de implementar OK() se
puede usar una lista enlazada por punteros. Es muy difícil
saber si una cadena está realmente rota, por lo que en la
implementación de List.OK(L) lo que se hace es
recorrer la lista "L" hasta que suceda una de tres
cosas:
2^64 veces. Como no hay suficiente
memoria para implementar una lista tan grande, se puede
entonces deducir que la lista está rota, o que tiene
un ciclo interno.
Pero no siempre es posible saber dónde está mala la
lista. En el último caso puede ser que OK()
simplemente no pueda sobreponerse a la destrucción de la
instancia del ADT, y el resultado sea un programa incorrecto o que
nunca termine. Más aún, es posible que
OK() regrese TRUE aun cuando la
invariante no se cumpla. En
[TB-86] se discute esto en el
contexto de un sistema para experimentar con estructuras de datos
dañadas.
OK() es ejemplo de una operación muy deseable
para implementar programas robustos, pero que en la
práctica puede resultar imposible de programar.
4.12
Fix(o)
PROCEDURE Fix( { EXPORT } { ADH }
{?} VAR o : TObj { SELF }
);
{ RESULTADO
Corrige el valor del objeto "o" si no cumple con la
invariante de "TObj". En este caso, lo usual es que
"o" quede en el mismo estado en que lo dejó Init()
después de inicializarlo.
- Fix() puede implementarse como un Init(), pero
puede que esto no sea ni lo mejor o ni lo menos
costoso.
- Para muchos ADT's es imposible implementar esta
operación. }
Fix(o)
En la Figura 4.12 está la
especificación genérica para Fix(), que
se encarga de reparar una instancia del ADT que está
incorrecta, o quebrada. Esto ocurre cuando la instancia no cumple
con la invariante del ADT.
Si en la práctica a veces es imposible programar
OK(), es aún más difícil
implementar Fix(). Por ejemplo, para ADT's que usan
punteros para enlazar a sus componentes es casi imposible
implementar de manera segura y correcta esta operación,
pues un puntero quebrado puede apuntar a cualquier parte de la
memoria del computador, y no hay forma de saber con certeza
cuál es el valor que debe tener.
Esta operación se ha incluido en este estudio porque lo hace más completo, no porque sea sano que el programador del ADT disponga de herramientas que le permitan ser descuidado al programar. Quien implementa un ADT tiene la responsabilidad de hacer un trabajo adecuado, y quien lo usa debe cumplir con los requerimientos de cada operación antes de invocarla. Sin embargo, como es de humanos errar, a veces es posible, o resulta barato, incluir un poco de programación defensiva en el programa, que ayude a detectar errores. Nunca dejará de ser necesario el exigir calidad en los programas.
4.13
Store(o,F)
PROCEDURE Store( { EXPORT } { ADH }
{+} VAR o : TObj; { SELF }
{?} VAR F : FILE { archivo por grabar }
);
{ RESULTADO
Graba en el archivo "F" el contenido de "o".
- "F" se graba secuencialmente, de forma que Load()
pueda luego reconstruir todo el contenido de "o".
- El archivo queda posicionado exactamente en el
BYTE siguiente a la última posición grabada. }
{ REQUIERE
- F debe ser un archivo sin tipo.
- F debe haber sido abierto usando
Reset(F,1); o ReWrite(F,1);
- El tamaño de bloque de "F" debe ser 1.
- F debe tener espacio suficiente para grabar todo
el contenido de "o" completo. Si no es así, el
programa se cancelará en tiempo de ejecución. }
{ EJEMPLO
- F debe abrirse usando uno de los comandos:
Assign(F,"nombre"); Assign(F,"nombre");
... o ...
Reset(F,1); ReWrite(F,1);
pues de lo contrario Turbo Pascal usará un
tamaño incorrecto al leer o grabar. }
Store(o,F)
En la Figura 4.13 está la
especificación genérica para
Store(o,F), operación que se encarga de
almacenar en un archivo binario el valor del objeto
"o". Como la memoria del computador es
volátil, es muy importante contar con operaciones que
permitan que los valores de los objetos persistan después
de que los programas terminan. Store() es un
tímido comienzo en esta dirección; ya existe la
tecnología de bases de datos orientadas a los objetos
precisamente para administrar los objetos que existen fuera de la
memoria del programa
[ADM-90].
La memoria de los computadores está en sus unidades de
almacenamiento secundario: sin esta memoria los computadores
serían totalmente inútiles. Por eso es muy
importante poder almacenar el valor de los datos en archivos.
Algunas razones adicionales que justifican la existencia de
Store(), o de una operación similar, son
estas:
La especificación de Store(o,F) de la
Figura 4.13 es muy limitada, y
depende mucho del ambiente en que corre el programa. En el caso
del compilador Turbo Pascal, necesariamente "F", el
archivo en que se graba el valor de "o", debe ser un
archivo Turbo Pascal sin tipo, lo que obliga al programador a usar
en la implementación los procedimientos
System.BlockRead() y
System.BlockWrite(), que son exclusivos de Turbo
Pascal.
La entrada / salida de datos es una función muy importante, hasta el punto de que muchos lenguajes incorporan construcciones sintácticas para esta tarea. Se ha dicho que la falta de facilidades para manipular archivos contribuyó mucho a que Algol no tuviera un resonante éxito en la industria, y que una de las cartas de presentación de C++ es precisamente su extensa biblioteca para manejo de archivos y bases de datos.
La especificación de Store() se incluye para
hacer más completo este trabajo, pues es muy instructivo
conocerla, pero no es este el sitio para estudiar cómo
lograr que un objeto sea persistente, por ser este un problema es
muy complejo. Baste aquí mencionar algunos de los enfoques
que han sido propuestos en la literatura para hacer persistentes a
los objetos:
Por las mismas razones que a veces no es posible implementar el
Copy() para un ADT, a veces es también muy
difícil implementar la pareja Load() /
Store(). En general, una vez que el programador ha
implementado Copy() le resulta sencillo implementar
tanto Load() como Store(), pues esos
algoritmos son bastante parecidos.
4.14
Load(o,F)
PROCEDURE Load( { EXPORT } { ADH }
{?} VAR o: TObj; { SELF }
{?} VAR F: FILE { archivo a leer }
);
{ RESULTADO
Lee del archivo "F" el nuevo valor para "o".
- El archivo queda posicionado exactamente en el
BYTE siguiente a la última posición leída.
- El contenido anterior de "o" se pierde. }
{ REQUIERE
- "F" debe ser un archivo sin tipo.
- "F" debe haber sido grabado por medio de Store().
- "F" debe estar abierto.
- "F" debe contener el valor "o" completo. }
{ EJEMPLO
- "F" debe abrirse usando uno de los comandos:
Assign(F,"nombre"); Assign(F,"nombre");
... o ...
Reset(F,1); ReWrite(F,1);
pues de lo contrario Turbo Pascal usará un
tamaño incorrecto al leer o grabar. }
Load(o,F)
En la Figura 4.14 está la
especificación genérica para Load(o,F)
que es la operación que se encarga de obtener del archivo
binario "F" el valor del objeto "o".
Lo usual es que la operación Load() siempre
debe estar acompañada de
Store(), pues no tiene
sentido almacenar el valor de un dato en un archivo si luego no se
le puede recuperar. Sin embargo, una buena razón para
implementar sólo una de ellas, es escribir dos programas
que sirvan para trasladar de plataforma el valor del objeto,
tal vez mediante el uso de una red.
4.15
Print(o,F)
PROCEDURE Print( { EXPORT } { ADH }
{+} VAR o : TObj; { SELF }
{?} VAR F : TEXT { archivo a grabar }
);
{ RESULTADO
Imprime el valor del objeto "o" en el archivo de
texto "F", de forma que sea legible usando un editor
de textos. }
{ REQUIERE
- "F" debe estar abierto.
- "F" debe tener espacio suficiente para grabar todo
el contenido de "o" completo. }
Print(o,F)
En la Figura 4.15 está la
especificación genérica para
Print(o,F), que se encarga de imprimir el valor del
objeto "o" en el archivo de texto "F".
Como se discute en
[Cha-96], el valor de un objeto
se puede grabar en almacenamiento secundario en dos formatos:
ASCII o binario; Print() representa el primero y
Store() representa el
segundo.
Es poco usual que los programadores implementen la
operación Print() para sus ADT's pues hay
muchas formas válidas y diferentes de imprimir el valor de
un objeto; su especificación se incluye aquí para
hacer más completo este estudio. Algunas veces lo que se
hace es ponerle muchos parámetros a Print(),
para que pueda desplegar el valor de un ADT de muchas formas.
Realmente Print() es un representante de una clase
muy grande de operaciones que sirven para desplegar el valor de un
ADT, las que generalmente se agrupan en una sofisticada biblioteca
para realizar la entrada / salida de datos. En C++ esto se logra
mediante las clases "stream".
Los problemas que existen para implementar
Store() también
existen para Print(), con el agravante adicional de
que muchas veces no es posible expresar exactamente en letras y
números el valor de un ADT. Por ejemplo, si uno de los
campos es un número de punto flotante, en muchos casos su
representación con dígitos decimales no es exacta.
Tal vez una mejor manera de implementar el trabajo que
Print() hace, es incluir en el ADT una
operación que transforme el valor del objeto en una tira de
caracteres, que pueda luego ser desplegada cómodamente
usando los procedimientos Write() y
WriteLn() pero, como en Pascal las hileras son muy
cortas, para algunos ADT's esta manera de hacer las cosas es muy
restrictiva. De todas maneras, si un programador necesita imprimir
el valor del ADT siempre lo puede obtener mediante las operaciones
examinadoras para luego
imprimir los valores así obtenidos.
4.16
Read(o,F)
PROCEDURE Read( { EXPORT } { ADH }
{?} VAR L : TObj; { SELF }
{?} VAR F : TEXT { archivo a leer }
);
{ RESULTADO
Lee del archivo de texto "F" el nuevo valor para el
objeto "o". }
{ REQUIERE
- "F" debe estar abierto.
- "F" debe contener el valor "o" completo.
- En general, "o" debe haber sido escrito en "F"
usando Print(o,F). }
Read(o,F)
En la Figura 4.16 está la
especificación genérica para Read(o,F)
que sirve para obtener del archivo de texto "F" el
valor de "o".
Así como
Load() es el complemento
de
Store(),
Read() es el de
Print(); en buena
teoría, Read() debe ser capaz de reconstruir
un objeto cuyo valor fue escrito en un archivo de texto mediante
Print(). En la práctica no es tan simple
lograr este cometido.
Tst_Insert()
Un ejemplo de una aplicación interesante de
Print() es el procedimiento Tst_Insert()
que se especifica en la
Figura 4.16a y que sirve para
probar la operación List.Insert(). Al
implementar Tst_Insert() se ha usado una facilidad de
Turbo Pascal que permite crear un manejador de dispositivo
(Device Driver) para leer o escribir el valor de una
hilera desde un archivo (en el manual de Turbo Pascal
[BI-88] está la
explicación de este método, cuya
implementación está en el archivo
StrTEXT.pas). Como
para cualquier lenguaje existe una forma de implementar este mismo
método, no hace falta especificar con mayor detalle las
operaciones To_STRING() / From_STRING() que pueden
transformar el valor de una ADT en una hilera, y viceversa.
Tst_Insert() es ejemplo de cómo el programador
puede escribir sus casos de prueba como procedimientos, los que
luego sirven para ejercitar las operaciones de su ADT. Estos
procedimientos de prueba son muy importantes porque facilitan
verificar que los cambios en la implementación del ADT no
han introducido errores de programación, y que por lo tanto
la nueva implementación es correcta
[Mye-78].
4.17
Get(o,v)
PROCEDURE Get( { EXPORT } { ADH }
{+} VAR o : TObj; { SELF }
{?} VAR v : TType { valor obtenido de e }
);
{ RESULTADO
Devuelve en la variable "v" el contenido de "o". }
Get(o,v)
En la Figura 4.17 se muestra una
posible especificación para la operación
Get(o,v) que sirve para obtener el valor almacenado
en la variable "o".
La mayor parte de los objetos con que se trabaja en un programa
son complejos, pues contienen muchos campos o incluso se obtienen
por agregación de otros objetos más simples. Por eso
es usual que para un mismo objeto se definan muchos operadores
similares a Get(), cada uno encargado de retornar uno
de diferentes valores que el objeto contiene.
En la especificación de Get() se incluye el
parámetro "v", de tipo "TType",
para que ahí quede el valor extraído de
"o". Perfectamente el programador puede incluir
más de un parámetro para Get(), pues a
veces estas operaciones
examinadoras obtienen del
objeto más de un valor en cada invocación.
4.18
Put(o,v)
PROCEDURE Put( { EXPORT } { ADH }
{?} VAR o : TObj; { SELF }
{+} VAR v : TType { valor obtenido de o }
);
{ RESULTADO
Cambia el valor contenido en "o" por "v".
- El valor de "v" no cambia. }
Put(o,v)
Para cambiar el valor almacenado en un ADT es necesario ejecutar
una operación que lo haga adecuadamente, lo cual se conoce
como un "mutador". Como un ADT es
una agregación de campos, en muchos casos hacen falta
muchos mutadores. Genéricamente, en este trabajo se les
llama a todos ellos Put(). La
Figura 4.18 es una
especificación de la operación Put(o,v)
que representa a los mutadores para el tipo
"TObj".
Otro nombre adecuado para la operación Put()
es Let() pues, en BASIC,
LET es una etiqueta que marca las instrucciones de
asignación. Un mejor nombre sería
Set(), pero ese identificador no se
puede usar en Pascal porque SET es la palabra
reservada del lenguaje que se usa para definir conjuntos de
escalares.
A veces un mutador cambia más de un campo en el
Rep, y otras veces cambia
sólo uno. El programador tiene muchas opciones para definir
cuáles son los parámetros de las operaciones
Put() que necesita. Más aún, es posible
definir algunos mutadores que también son
examinadores.
Get() y Put()
son las operaciones que realmente caracterizan a un ADT. Por
ejemplo, una pila se caracteriza por sus mutadores
Push() y Pop(); una cola por
En_Queue() y De_Queue().
El programador que implementa un ADT debe ser muy cuidadoso para garantizar que los mutadores siempre dejen el ADT en un estado en que se cumpla su invariante. En muchos casos la eficiencia del ADT depende de la eficiencia con que están implementados sus mutadores.
Copyright © 1999 Adolfo Di Mare
![[<==]](../../img/back.gif)
|
|
![[==>]](../../img/next.gif)
|