[UACA]
[<==] [\/] [/\] [==>]


Reutilización de Contenedores Parametrizables con Lenguajes de Semántica Limitada


Capítulo 4: Operaciones básicas

      En las secciones que siguen se especifican cada una de las operaciones principales, comunes a todo tipo abstracto de datos. Para darle mayor generalidad al trabajo se usa la notación de ADT's en lugar de la de OOP: por eso, se especifica a 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].

UNIT Obj;   { File: Obj.pas }

INTERFACE

TYPE                 TYPE                           
  PObj = ^TObj;        Rep_Obj = RECORD            
  TObj =  RECORD         { Campos privados del ADT }
    Rep : Rep_Obj;       {...}                      
  END;                 END;

PROCEDURE Init(  {-} VAR s : TObj);
PROCEDURE Clear( {?} VAR s : TObj);
PROCEDURE Erase( {?} VAR s : TObj);
PROCEDURE Done(  {?} VAR s : TObj);

PROCEDURE Copy(  {?} VAR x : TObj; {+} VAR y : TObj);
PROCEDURE Clone( {?} VAR o : TObj; {?} VAR p : PObj);
PROCEDURE Move(  {?} VAR x : TObj; {?} VAR y : TObj);
PROCEDURE Swap(  {?} VAR x : TObj; {?} VAR y : TObj);

FUNCTION  Equal( {+} VAR x, y: TObj) {>>>>>} : BOOLEAN;
FUNCTION  Less(  {+} VAR x, y: TObj) {>>>>>} : BOOLEAN;

FUNCTION  OK(    {+} VAR s : TObj) {>>>>>>>} : BOOLEAN;
PROCEDURE Fix(   {?} VAR s : TObj);

PROCEDURE Store( {+} VAR s : TObj; {?} VAR F : FILE);
PROCEDURE Load(  {?} VAR s : TObj; {?} VAR F : FILE);

PROCEDURE Print( {+} VAR s : TObj; {?} VAR F : TEXT);
PROCEDURE Read(  {?} VAR s : TObj; {?} VAR F : TEXT);

PROCEDURE Get(   {?} VAR s : TObj; {?} VAR val : TYPE);
PROCEDURE Put(   {?} VAR s : TObj; {+} VAR val : TYPE);

IMPLEMENTATION
   {...}
END.

{ EOF: UNIT Obj.pas }
Figura 4.0: Operaciones de un ADT elemental

4.1 Init(o) [<>] [\/] [/\] [<>]

PROCEDURE Init(          { EXPORT }     { ADH }
  {-} VAR o : TObj       { SELF }
);
{ RESULTADO
  Inicializa a "o" para que tenga el valor nulo. }
Figura 4.1: 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:

  1. Usar objetos no inicializados es un error grave, que da como resultado programas incorrectos y fallas que son intermitentes, pues a veces ocurre que un programa funciona correctamente aun cuando algunas de sus variables no están inicializadas. Es muy difícil encontrar el error pues generalmente ocurre que el objeto no inicializado ha inducido la corrupción de otros objetos, que es en los que se detecta la falla.
  2. El tratar de evitar la inicialización penaliza fuertemente el rendimiento del programa, pues obliga a verificar, en tiempo de ejecución, el valor almacenado en cada instancia, y esto hay que hacerlo cada vez que se usa el valor.

      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. }
Figura 4.2: 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. }
Figura 4.3: 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.

               ╔═══════╗
               ║ v = 9 ║
               ╚═══╤═══╝
                   │
              ┌─┬─┬┴┬─┬─┐
              │*│*│*│*│ │
              └┼┴┼┴┼┴┼┴─┘
    ┌──────────┘ │ │ └──────────┐
    │        ┌───┘ └───┐        │
    │        │         │        │
┌───┴───┐ ┌──┴────┐ ┌──┴────┐ ┌─┴─────┐
│       │ │       │ │       │ │       │
└───────┘ └───────┘ └───────┘ └───────┘
Figura 4.3a: 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(). }
Figura 4.4: 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:

  1. Eficiencia: En [DDZ-94] los autores defienden a lo largo de todo su artículo un recolector de basura para C y C++ y, pese a que apoyan indirectamente su uso, obtienen resultados que ponen en clara desventaja a los programas que usan un recolector de basura, pues resultan menos eficientes (más lerdos).
  2. Disciplina: No es correcto que los programadores se acostumbren a hacer mal su trabajo. Si invocan en su programa el constructor de un objeto, también deben invocar el destructor. Si como es el caso de C++, el lenguaje permite definir constructores y, además, se encarga de invocarlos sin intervención de programador, entonces también debe permitirle definir los destructores para sus objetos.
  3. Completitud: No es válido suponer que los destructores únicamente se encargan de retornar memoria dinámica, pues en muchos casos realizan otras tareas. Por ejemplo, pueden tener la misión de cerrar archivos o de concluir procesos hijos; estos tipos de tarea requieren de un manejo muy particular por lo que no es factible que un simple recolector de basura pueda realizar esta labor.

      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. }
Figura 4.5: 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. }
Figura 4.6: 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.

PROCEDURE Clone(     { EXPORT }     { ADH }
  {?} VAR o : TObj;  { SELF }
  {?} VAR p : PObj   { Dónde dejar el duplicado }
);
BEGIN { Clone }
  IF p = @o THEN BEGIN
    EXIT;  { evita autocopia }
  END;
  IF p = NIL THEN BEGIN
    System.NEW(p);
    Init(p^);
  END;

  Copy(p^, o);
END;
Figura 4.6a: 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().

TYPE
  PClone_SI_Copy_NO =^TClone_SI_Copy_NO;
  TClone_SI_Copy_NO = RECORD
    m_p : PClone_SI_Copy_NO;  { @SELF }
  END;

PROCEDURE Clone(
  {?} VAR o: TClone_SI_Copy_NO;
  {?} VAR p: PClone_SI_Copy_NO
);
BEGIN { Clone }
  IF p = NIL THEN BEGIN
    System.NEW(p);
    p^.m_p := p;  { Init(p^); }
  END;
END;  { Clone }
Figura 4.6b: Objeto duplicable pero no copiable

      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().             >>. }
Figura 4.7: 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.

4.8 Swap(x,y) [<>] [\/] [/\] [<>]

PROCEDURE Swap(          { EXPORT }     { ADH }
  {?} VAR x : TObj;      { SELF }
  {?} VAR y : TObj       { qué intercambiar   }
);
{ RESULTADO
  Intercambia los valores de "x" y "y". }
VAR
  tmp : TObj;
BEGIN { Swap }
  Init(tmp);
    Move(    tmp,  x     );
    Move(    x,    y     );
    Move(    y,    tmp   );
  Done(tmp);
END;  { Swap }
Figura 4.8: 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  ├──┐
│  └─────┘  │         │  └─────┘  │
│           │         │           │
│  ┌─────┐  │         │  ┌─────┐  │
└──┤ @ X │<─┘         └──┤ @ Y │<─┘
   └─────┘               └─────┘
Figura 4.8a: Intercambio de 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. }
Figura 4.9: 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. }
Figura 4.10: 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.

FUNCTION  Greater_Equal( { 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. }
BEGIN { Greater_Equal }
  Greater_Equal := NOT Less(x,y);
END;  { Greater_Equal }
Figura 4.10a: 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". }
Figura 4.11: 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:

  1. Se encuentra el último elemento de la lista.
  2. Se itera una gran cantidad de veces sobre la lista, por ejemplo 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.
  3. Se encuentra un elemento que no está bien construido.

      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. }
Figura 4.12: 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. }
Figura 4.13: 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:

  1. Permite que el valor de los datos que usa el programa sean usados por otros programas. En particular, permite escribir programas que pueden reiniciarse automáticamente, pues algunos programas hacen cálculos que tardan semanas o meses.
  2. Permite enviar de una máquina a otra copias de objetos, lo que es muy importante en sistemas distribuidos o cuando los sistemas son muy grandes.
  3. Permite programar sistemas en varios lenguajes de programación diferentes, pues los programas pueden comunicarse a través de los valores que manipulan.
  4. Cuando cuesta mucho construir el valor de una variable, es cómodo hacerlo sólo una vez, y luego cargar este valor cada vez que se ejecuta el programa. Por ejemplo, es usual que los objetos que implementan la interfaz de los programas residan en los llamados "archivos de recursos". Existen "editores de recursos", que son programas especializados para cambiar el valor de un ADT almacenado en un archivo.
  5. Facilita la depuración de módulos, pues es más fácil leer el valor de un dato que computarlo.

      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. }
Figura 4.14: 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. }
Figura 4.15: 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). }
Figura 4.16: 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.

PROCEDURE Tst_Insert(                   { Adolfo }
  {+} VAR L: STRING;     { Lista original        }
  {+}     n: WORD;       { Posición de inserción }
  {+} VAR c: CHAR;       { caracter a insertar   }
  {+} VAR R: STRING      { Lista Resultado       }
);
{ RESULTADO
  Construye una lista con base en el valor de la hilera "L",
  y le inserta el caracter "c" en la n-ésima posición.
  Luego verifica que la lista así obtenida sea igual a la
  lista que corresponde al valor de la hilera "R".
  - Si el resultado obtenido al insertar en "L" el caracter
    "c" en la posición "n" no es "R", entonces imprime
    un mensaje de error y aborta el programa.
  - Las listas que se usan son listas de caracteres. }
{ EJEMPLO
  Tst_Insert("[b, c]", 1, "a", "[a, b, c]");
  Tst_Insert("[a, b]", 3, "c", "[a, b, c]");
  Tst_Insert("[]",     1, "h", "[h]");        }
Figura 4.16a: 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". }
Figura 4.17: 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. }
Figura 4.18: 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
Derechos de autor reservados © 1999 Adolfo Di Mare <adolfo@di-mare.com>
[<==] [/\] [<>] [<>] [/\] [==>]