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

      La herramienta fundamental que usan los programadores para construir sus programas es la Abstracción, que les permite dividir un problema grande en pequeños problemas que son solubles. La solución del problema original es el agregado de las pequeñas soluciones:

Abstraer:	separar las cualidades de un objeto para considerarlas aisladamente o para considerar el mismo objeto en su pura esencia o noción.
Abstracto:	Que significa alguna cualidad con exclusión del sujeto.

      El concepto fundamental que se usa para lograr la abstracción es el de Módulo, que es una sección de un programa bien construida, con un fin específico, y que puede ser reutilizado. En algunos lenguajes los módulos son una unidad de compilación, como ocurre con Modula-2 o con las unidades de Turbo Pascal, o sea que, en esos lenguajes, cada módulo siempre es un archivo. Sin embargo, en este trabajo se consideran como módulos todos los procedimientos, funciones, métodos y clases o tipos de datos, aunque haya varios en el mismo archivo.

      Tradicionalmente, los módulos se han utilizado para lograr la Compilación separada de un programa, la que permite recompilar únicamente las secciones del programa que han sufrido un cambio cuando el programador codifica la implementación. Es gracias a esta técnica de compilación que es posible crear bibliotecas de programas en las que el código fuente de los algoritmos no tiene que ser accesible al programador cliente.

3.1 Generalidades

      Para el programador, las abstracciones existen en el mundo de las ideas: las realizaciones concretas de cada abstracción son los módulos que conforman un programa. A cada módulo corresponde una abstracción; a cada abstracción le corresponde un módulo. Para lograr esta concreción, el programador define primero la especificación de cada módulo, y luego escribe la implementación en un lenguaje de programación. Algunas veces se identifica el nivel del lenguaje con las facilidades que brinda para expresar especificaciones porque esto facilita la programación, pues libera al programador de escribir la implementación.

      La Especificación puede verse como un contrato en el que están definidos todos los servicios que la implementación del módulo es capaz de dar. La firma o prototipo del módulo siempre forma parte de la especificación, pues si no se definen los tipos y parámetros con que trabaja el módulo es imposible compilarlo o reutilizarlo. Algunos autores consideran que una especificación correcta debe estar escrita en un lenguaje formal, matemático. Pero otros sólo requieren de la especificación un alto rigor, con estas tres cualidades:

• Completa: debe decirse todo lo que hay que decir.
• Correcta: debe omitirse lo que no hay que decir.
• No ambigua

      En pocas palabras, en la especificación no debe sobrar ni faltar nada. Debe estar toda la información esencial para implementar un módulo, y también para usarlo. Además, es conveniente que la especificación sea clara y sencilla de entender, de forma que para usarla el programador no requiera hacer un esfuerzo intelectual más grande de lo necesario.

      Un buen ejemplo de una especificación es el manual del lenguaje Turbo Pascal [BI-88]. Otro lo es la descripción de la biblioteca estándar del lenguaje C. Hay quienes argumentarán que estas dos obras no son completas; pero sí sirven de paradigma para quien tenga una duda razonable sobre el significado que la palabra especificación tiene para el programador.

      Escribir especificaciones es un trabajo intelectual muy duro, pues hay que cuidar cada detalle, de manera que todo encaje. Por eso, aunque el lenguaje sea de un nivel muy alto, el programador no se libera del doloroso parto intelectual que debe vivir antes de ver su programa funcionar correctamente. Lo que ha ocurrido es que al aumentar el nivel de los lenguajes ha sido posible, y necesario, definir abstracciones de más alto nivel; gracias a esto ha sido posible escribir programas más complejos. ¡Imagine el lector lo difícil que sería escribir todo el Sistema Operativo Windows/NT usando solamente lenguaje ensamblador!

      El programador escribe especificaciones para definir exactamente cuáles son los servicios que cada uno de los módulos del programa brindará. Por eso al escribir la especificación debe usar las facilidades que es común encontrar en los lenguajes de alto nivel, como lo son la definición de tipos. Además, cada tipo de módulo se especifica de una forma diferente, y cada uno corresponde a una abstracción diferente. Existen al menos tres tipos de módulos o de abstracciones:

1. Abstracción de Procedimientos
2. Abstracción de Datos
3. Abstracción de Iteradores

      Una de las ventajas más importantes de usar abstracción es que un programador especializado puede dedicarse a depurar la especificación e implementación de un módulo específico. Esta persona se asegurará no sólo de que la implementación sea correcta, sino también de que sea eficiente. De esta manera el programador cliente tendrá acceso a rutinas de alta calidad y confiabilidad. Se evita así reprogramar los "métodos" que forman parte de los programas eficientes.

PROCEDURE Lea_Arbol_Menu( { EXPORT }       { Adolfo Di Mare }
  {?} VAR f     : TEXT;   { archivo de líneas de menú       }
  {+}     mprin : PLinea; { linea leída por el llamador     }
  {-} VAR ultLn : PLinea  { puntero a la última línea leída }
);
{ RESULTADO
  Lee el archivo que describe los menúes de la aplicación.
  En ultLn se retorna un puntero al último ítem leído que
  no corresponde a mprin, sino que es hermano de mprin o
  tal vez hermano de algún ítem con nivel menor que el de
  mprin (ie, que corresponde a un menú más cercano al
  principal que mprin).                                     }
{ REQUIERE
  mprin debe apuntar a un registro de menú, o mprim = NIL.
  El llamado a Lea_Arbol_Menu() se debe hacer para leer
  todos los ítemes del menú mprin.                          }

      Una especificación tiene dos partes: la primera es la que requiere el compilador para compilar el programa, y la otra es la que el programador cliente necesita para poder usar el módulo. En la Figura 3.1 se diferencian estos dos componentes claramente, pues la información que sólo es relevante al programador aparece entre corchetes de comentario ("{" y "}"), para que el compilador la ignore al compilar el programa.

      La abstracción de procedimientos da origen a las rutinas o funciones que forman un programa. Este tipo de abstracción se usa para hacer el diseño de programas de arriba hacia abajo (Top-Down) y para crear las bibliotecas de programación. La Figura 3.1 es un ejemplo de la abstracción de procedimientos, que está escrita en el contexto del lenguaje Pascal.

      Después de que los programadores identificaron la abstracción de procedimientos, se dieron cuenta de que un programa no puede existir sin los datos que manipula. Por eso nace la abstracción de datos (ADT), que es la base para lo que hoy constituye la Programación Orientada a los Objetos (OOP). Un ADT describe la funcionalidad de un tipo de datos.

      Es común que los estudiantes novatos confundan a los ADT's con las estructuras de datos, pues algunos ADT's son módulos que permiten usar alguna estructura de datos. Sin embargo, las estructuras de datos no se especifican con tanto detalle como los ADT's, y puede ocurrir que un ADT use muchas estructuras de datos diferentes. Además, existen ADT's cuya estructura de datos es tan simple que nadie los llamaría estructuras de datos; por ejemplo, un número real es un ADT. De hecho, muchos ADT's no tienen asociadas estructuras de datos sofisticadas.

      Los tipos abstractos de datos se pueden clasificar en dos grandes categorías: simples o elementales, y contenedores. Un ADT es un contenedor si existe para almacenar a otros ADT's. Es a los contenedores a los que, a veces, los estudiantes confunden con las estructuras de datos. Los contenedores más importantes son tres:

1. ADT Arreglo [ARRAY]
2. ADT Lista [List.pas]
3. ADT Árbol [Tree.pas]

      Existen otros ADT's importantes, como Heap.pas [Ben-85], Poly.pas, Matrix.pas, etc., pero la mayoría de las estructuras de datos importantes se obtienen al combinar inteligentemente estos tres ADT's. De todos los contenedores, el más importante es, sin duda alguna, el Arreglo o Vector, hasta el punto de que todos los lenguajes de computación modernos lo incluyen como una construcción sintáctica básica. Los otros dos se discuten e implementan en este trabajo.

      La abstracción de iteración existe para simplificar el acceso a los elementos contenidos en un contenedor. Algún purista podrá decir que esta abstracción sobra, pero se incluye aquí porque todos los iteradores se especifican de la misma forma, y a veces resultan muy útiles para resolver problemas. Son una elegante solución a un problema bien definido.

      Aunque ya hoy en día es claro para todos que los programas se deben diseñar desde lo abstracto hasta lo concreto, combinando abstracciones, lo cierto es que, en la práctica, la primera vez que se escribe un programa, la especificación y su implementación, son incorrectas. En versiones posteriores se llega a definir cuál es la manera adecuada de dividir el problema que el programa resuelve, para desde ahí obtener los módulos que corresponden a la correcta abstracción. La gran ventaja de usar abstracción es que, cuando al fin se logra hacerlo bien, el trabajo queda hecho definitivamente. Es este uno de los motivos que llevaron al autor de esta tesis a concretar en la implementación de una de las abstracciones más importantes: la Lista.

      Una Implementación es un grupo de instrucciones imperativas a ser ejecutadas por el computador, escritas en uno o más lenguajes de programación. Cada implementación es una de las muchas posibles formas de escribir el código de un programa. Cuando se ha usado abstracción como técnica de diseño, cada implementación debe corresponder a alguna especificación pues a partir de la abstracción se llega a la implementación. Mientras con la especificación se define qué hace el programa, en la implementación queda escrito cómo se hace. Por eso, después de que ha sido definida la especificación, en general existen muchas posibles implementaciones diferentes que cumplen con la especificación. Optimizar una implementación significa mejorar el código para escoger una implementación que sea más eficiente.

3.2 Procedimientos y funciones

      Fundamentalmente, la programación modular consiste en usar abstracción de procedimientos. La idea es introducir un conjunto de instrucciones en un módulo, que tiene una interfaz claramente definida, de forma que al arreglar o mejorar el módulo no sea necesario cambiar ninguna otra parte del programa. Para definir la interfaz de un módulo es necesario definir los objetos con que trabaja.

      Un Tipo de Dato es un restricción que define los valores que pueden tomar las variables que se usan en un módulo. En la mayor parte de los lenguajes modernos es posible definir nuevos tipos con base en los ya existentes, para lo que el lenguaje le permite al programador agregar (juntar) campos de cualquier tipo en registros o arreglos, y restringir los tipos ya existentes. El programador debe darle a cada tipo un nombre que lo identifique. (En [CW-85] hay definiciones más precisas de este concepto y de otros relacionados).

      Los datos del programa siempre son de (o pertenecen a) un tipo. Los datos existen porque ocupan memoria en el computador. En los lenguajes de programación tradicionalmente se usan tres tipos de memoria: estática, automática y dinámica. La Memoria automática es la que se asigna de la pila de ejecución del programa. La Memoria estática es la que se usa para almacenar valores constantes y también datos globales, que deben ser visibles en todos los módulos del programa. Cuando un dato está almacenado en la memoria automática, o también en la estática, se dice que es una Variable, porque, para que exista, el programador debe declararlo en su programa; en Pascal esto se logra nombrándolo en la cláusula VAR de cada módulo.

      Toda la memoria de datos que no es automática o estática está disponible al programa como Memoria dinámica, y es administrada por medio de varias rutinas de biblioteca. En el caso de Pascal, la memoria dinámica se administra con los procedimientos NEW() y DISPOSE(), que se encargan de asignar la memoria dinámica en bloques de tamaño variable, de acuerdo con el tamaño del dato que se necesite almacenar. Si un dato ocupa espacio en la memoria dinámica, no se le puede llamar variable, pero sí se le llama instancia. Una Instancia es un dato de algún tipo, que puede estar almacenado tanto en la memoria automática o estática como en la dinámica. Las variables siempre tienen nombre, pero las instancias que están en memoria dinámica no, pues para referirse a ellas hay que usar un Puntero, que es una hilera de bits que representa la posición exacta en que está almacenado un dato (las cosas se complican más cuando se habla de "punteros a punteros" [DY-91]). A la acción de obtener el valor al que apunta un puntero se le llama Derreferenciar el puntero.

      Si el lenguaje soporta OOP, entonces es costumbre llamar a cada instancia Objeto. También se usa la palabra objeto para denotar el concepto de tipo de datos, aunque con menos frecuencia. Una variable es un objeto; una instancia es un objeto; un tipo es un objeto. Al principio es difícil manejar bien estos conceptos de variable, instancia, objeto, tipo de datos y dato, porque, dependiendo del contexto, todas estas palabras pueden significar lo mismo, o más o menos lo mismo, aunque cada una tiene un significado exacto diferente.

      Conviene a veces ocultar el hecho de que un objeto está almacenado en otro lugar de la memoria. En este caso, en el código fuente del programa un puntero se ve como el objeto, pese a que el valor almacenado está en otra parte. A estos punteros escondidos se les llama Referencias, pues para obtener el valor almacenado hay que derreferenciar el puntero. Pascal no cuenta con esta construcción sintáctica, la que es de uso común tanto en Ada como en C++. Si un lenguaje usa Semántica de referencia, un objeto no es el objeto en sí, como sí lo es en Pascal, sino que un objeto es un puntero a la parte de la memoria en que sus datos están almacenados. La semántica de referencia permite lograr un alto grado de reutilización de componentes de programación, pues es la manera de implementar el polimorfismo uniforme [MDC-91]. El costo de esta gran flexibilidad se paga con un decremento en la eficiencia, pues cada vez que se necesita usar un dato hay que derreferenciar el puntero.

      Los tipos son una eficaz herramienta para que el compilador del lenguaje verifique el correcto enlace entre módulos, labor que realiza al corroborar que los tipos de datos de las variables que aparecen en la invocación a un módulo, llamados Argumentos, coincidan con los tipos de los Parámetros formales declarados para el módulo. Se llama Verificación estática de tipos a la verificación fuerte de tipos que se realiza en tiempo de compilación.

      La abstracción de procedimientos le permite al programador separar claramente el cómo del qué: una subrutina contiene la lógica necesaria para ejecutar una tarea, y sus parámetros son los objetos sobre los que trabaja. Al través del tiempo se han usado muchas palabras para nombrar los procedimientos; por ejemplo, se las llama funciones a los procedimientos que retornan algún valor. Esta es una lista parcial de esas palabras:

      Los primeros lenguajes de programación (Fortran, Lisp, Basic y Cobol) no soportan adecuadamente abstracción de procedimientos pues, aunque en ellos es posible definir argumentos para subrutinas, no es necesario especificar tipos de datos, por lo que muchos errores de interfaz, que podrían ser detectados por el compilador, deben ser eliminados manualmente por el programador. Cuando estos lenguajes fueron definidos, lo común era no especificar la interfaz entre módulos, y hacerlo era visto por los programadores como un trabajo poco creativo y engorroso: los programadores se rehusaban a diseñar adecuadamente sus programas. Peyorativamente se llamaba "documentación" a la labor de especificar módulos y sistemas, y se delegaba esta labor en los funcionarios de menos nivel de conocimientos y de sueldo: se creía que lo más importante era escribir el código del programa.

      Con el advenimiento de Algol, y luego de Pascal, poco a poco ha cambiado esta mala percepción sobre la especificación y documentación de programas (aunque los programadores nunca dejarán de resistirse a leer o escribir documentación [Ret-91]). La verificación fuerte de tipos en tiempo de compilación reduce significativamente el tiempo de desarrollo de un programa. Sin embargo, todavía no era clara la importancia y las ventajas de especificar procedimientos. La Figura 3.1 es un ejemplo de la especificación de un procedimiento, escrito de acuerdo con las convenciones de programación definidas en [DiM-88a]. Este es el típico procedimiento que encontramos en un programa. A diferencia de otros ejemplos, la especificación de este procedimiento es bastante completa: muchos programadores no se molestarían en escribir tanto para una "escuálida" subrutina.

      Para el compilador importa únicamente el nombre y el tipo de los parámetros de la rutina, llamada el Encabezado, firma o prototipo (header, signature, prototype) del procedimiento o función. Para completar la especificación el programador debe complementar el encabezado con que declara el procedimiento con comentarios que explican en forma clara, concisa y completa, qué es lo que hace. El ejemplo de la Figura 3.1 está escrito en Pascal; los lenguajes más modernos, como Ada y C++, le permiten al programador definir con más detalle los parámetros de cada rutina.

      En el procedimiento Lea_Arbol_Menu() se oculta cómo se logra el objetivo descrito en la cláusula RESULTADO de la especificación. Un programador puede usar este procedimiento sin necesidad de conocer el código fuente de la rutina, con sólo disponer de una copia del código objeto producido al compilarla. Obviamente, debe asegurarse de que la cláusula REQUIERE se cumpla de hecho, o su programa estaría incorrecto. Muchos autores llaman Precondición y Poscondición a las cláusulas REQUIERE y RESULTADO.

      Las bibliotecas de programas comerciales están formadas por procedimientos como éste. Estas bibliotecas generalmente proveen información adicional al programador, en la que se describe el contexto de uso de cada procedimiento.

      Es un poco difícil entender lo que Lea_Arbol_Menu() hace. Por ejemplo, no se explica en ningún lado qué es un menú, o una PLinea (o sea, un puntero a una TLinea). Es cierto que los identificadores son significativos, pero eso no es suficiente para lograr incorporar este procedimiento en un programa real. Hace falta mucha más información.

      De este ejemplo se pueden sacar dos conclusiones: primero, que el no usar abstracción de procedimientos es contraproducente. Una rutina como ésta realmente ayuda a dividir un problema complejo en partes manejables, lo que garantiza no sólo una conclusión rápida del proceso de programación, sino que además permite reutilizar programas en la forma de procedimientos. C, el lenguaje usado en el sistema operativo UNIX, ha logrado gran aceptación precisamente por contar con una amplia biblioteca de procedimientos disponible para el programador.

      Lo segundo que se puede concluir es que para obtener un sistema modular no basta con describir, mediante la abstracción de procedimientos, lo que hace cada subprograma. También es necesario describir los datos, y las relaciones que hay entre ellos. Por eso es necesario crear módulos que definen los datos, mediante la abstracción de datos.

3.3 Tipos Abstractos de Datos

      Después de varios años de experiencia usando programación modular, se hizo obvio para todos que es necesario usar módulos que representan a los datos. Así nace la Abstracción de datos, cuya expresión son los Tipos Abstractos de Datos (ADT) y, más recientemente, la Programación orientada a los objetos (OOP).

      En cualquier programa es necesario combinar los tipos básicos de datos, como números y caracteres, para formar estructuras más complejas y así representar información dentro del computador. En general existe una fuerte relación entre todos los datos manipulados por un programa, por lo que es conveniente que esa relación esté claramente especificada y controlada, de forma que cada parte del programa vea sólo lo que necesita. Así se incrementa la modularidad del programa.

      Al separar el programa en partes independientes, o módulos, se evita que cambios en una parte produzcan errores en otras partes del programa. Por ejemplo, en un programa que usa varios arreglos y matrices para almacenar información, es frecuente que, al aumentar el tamaño de una dimensión, se olvide aumentar la de los demás arreglos, con lo que el mantenimiento del programa se hace más difícil. Al aislar todas estas dependencias en un módulo aparte se logra que los cambios puedan ser hechos con un mínimo de esfuerzo y en una forma localizada. Es muy importante minimizar la posibilidad de que en el momento de darle mantenimiento al programa haya cambios que requieran un detallado examen de toda la implementación.

      Al especificar un tipo abstracto de datos el programador decide cuáles procedimientos son fundamentales para manipular ese tipo de datos: estos procedimientos se llaman las Operaciones del tipo de datos. En un solo módulo se encapsula el nuevo tipo de datos junto con sus procedimientos.

      Es usual llamar al programador que usa una biblioteca de programas Programador cliente de la biblioteca. Cualquier módulo de programación debe ser especificado e implementado por un programador, y luego son los programadores clientes quienes reutilizan los módulos cuando construyen sus programas. Por eso en este trabajo se le llama programador cliente del ADT a quien lo usa. También se le llama cliente al módulo que necesita de otros módulos.

      Uno de los principales beneficios de usar abstracción para construir programas es la separación que se obtiene entre la especificación y la implementación de cada módulo; en el caso de los tipos abstractos de datos, a esta separación se la conoce como Ocultamiento de datos. El ocultamiento de datos es muy importante para lograr una mejor modularización, pues garantiza que el programador cliente tenga acceso controlado al valor almacenado en una instancia del ADT, evitando así que destruya inadvertidamente alguna relación definida en la representación del valor del tipo de datos.

      La especificación es el qué, y en la implementación está el cómo. Al usar abstracción se logra el ocultamiento, que impide que se vea a nivel de la especificación todo lo que concierne sólo a la implementación. De esta forma es posible cambiar la implementación de un módulo, para mejorar el programa, sin necesidad de cambiar todos los otros módulos. El poder escoger entre varias alternativas de implementación es la razón principal para usar abstracción de datos: los detalles de implementación quedan totalmente ocultos dentro de las barreras del ADT, y es posible hacer modificaciones locales, generalmente para mejorar la eficiencia, que no tengan una repercusión global. Por eso el uso de abstracción da dividendos cuando se da mantenimiento a los programas.

      Para almacenar en el computador los valores del ADT es necesario agregar varios campos, y escoger una o más formas de interrelación entre ellos. Esta organización de los campos del ADT constituye su "representación privada", mejor conocida por el acrónimo "Rep" [LG-86]. A la relación que siempre deben cumplir los campos del Rep se la conoce como la Invariante del tipo de datos; la ventaja de que un ADT cuente con operaciones es que quien las programa puede asegurarse de que el valor que queda en el dato después de cada operación siempre es adecuado, o sea, que siempre se cumplirá la invariante después de invocar a una operación. Mediante el ocultamiento de datos se evita que el Rep del ADT sea accesible al programador cliente, se le garantiza que los valores almacenados en el ADT son correctos y se le libera de preocuparse de cómo lograrlo.

      El asociar un tipo de datos con sus procedimientos en un módulo se conoce como Encapsulamiento. En las primeras versiones de Pascal, el encapsulamiento se simula mediante unidades, y en Modula-2 usando los módulos del lenguaje. Otros lenguajes, como Smalltalk, Simula y C++, incluyen construcciones sintácticas que permiten encapsular un tipo de datos con sus procedimientos. Las rutinas que están encapsuladas en el tipo de datos se conocen por los nombres Procedimiento miembro o Método. Estos términos son sinónimos de operación, aunque fueron acuñados en el contexto de OOP. Un método es una rutina propia del tipo de datos; sirve para manipularlo, examinarlo o cambiarlo.

      Paradójicamente, Smalltalk y Simula son los primeros lenguajes que soportan abstracción y encapsulamiento de datos, pero no ocultamiento de datos. Tal vez ocurrió que los diseñadores de esos lenguajes no conocían este concepto, o lo consideraron innecesario. Su equivocación puede haber afectado la popularidad de estos lenguajes, pues están cayendo en desuso.

UNIT Elem;

INTERFACE

TYPE
  Rep_Elem = RECORD
    { Campos privados del ADT }
    {...}
  END;

  PElem = ^TElem;
  TElem =  RECORD
    Rep : Rep_Elem;
  END;

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

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

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

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

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

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

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

IMPLEMENTATION
   {...}
END. { UNIT Elem.pas }

      Ahora es claro que al implementar un ADT deben definirse, al menos, dos cosas:

1. Los campos que se necesitan para almacenar los valores del dato.
2. Las operaciones que permiten utilizarlo.

Si no se usa OOP, la modularización de un ADT se logra introduciendo todo el código en una misma unidad Turbo Pascal, como se muestra en la Figura 3.2. A todas estas operaciones se las llama Operaciones Básicas u Operaciones Elementales porque sirven para cualquier ADT, sea este un contenedor o no.

TYPE
  PElem = ^TElem;
  TElem =  OBJECT

  PUBLIC
    PROCEDURE Init;
    PROCEDURE Clear;
    PROCEDURE Erase;
    PROCEDURE Done;

    PROCEDURE Copy(  {+} VAR y : TElem);
    PROCEDURE Clone( {?} VAR p : PElem);
    PROCEDURE Move(  {?} VAR y : TElem);
    PROCEDURE Swap(  {?} VAR y : TElem);

    FUNCTION  Equal( {+} VAR y: TElem) {>>>} : BOOLEAN;
    FUNCTION  Less(  {+} VAR y: TElem) {>>>} : BOOLEAN;

    FUNCTION  OK     {>>>>>>>} : BOOLEAN;
    PROCEDURE Fix;

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

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

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

  PRIVATE
    { Campos privados del ADT }
    {...}
  END;

      En buena teoría los términos "tipo abstracto de dato" y "objeto" deberían ser sinónimos; en la práctica se diferencian porque se habla de objetos cuando el lenguaje soporta encapsulamiento y, si no, a los tipos de datos se les degrada a ser simplemente abstractos. La Figura 3.2 es un tipo abstracto de datos; el mismo tipo definido como objeto se muestra en la Figura 3.3. Cuando el compilador soporta tanto encapsulamiento (OBJECT) como ocultamiento de datos (PUBLIC, PRIVATE), el programador puede expresar las mismas ideas usando mucho menos código. Por eso en la Figura 3.3 no hace falta que cada objeto esté definido en un archivo diferente, como ocurre con el ADT de la Figura 3.2, que ha sido definido sin usar el encapsulamiento de OOP.

      Algunos lenguajes, en particular Modula-2 y Ada, usan tipos ocultos de datos, o tipos opacos, como mecanismo para implementar tipos abstractos de datos. En estos lenguajes se insta al programador a definir los tipos como punteros, para que la definición de los campos que forman el ADT esté en un módulo aparte. Esto quiere decir que en realidad los tipos opacos son una manera de implementar el ocultamiento de datos si el lenguaje no tiene soporte directo para ello.

      En el lenguaje C++, una Clase es un tipo abstracto de datos que ha sido definido junto a sus operaciones, utilizando las facilidades de encapsulamiento que brinda el lenguaje de programación; "Clase" es el término preferido para llamar a los tipos de datos en los lenguajes que soportan OOP. La Figura 3.3 es un ejemplo de una clase. (Paradójicamente, en Delphi, el sucesor de Turbo Pascal, las clases siempre residen en memoria dinámica, y el lenguaje las trata como referencias; esto sirve para hacer programas en la plataforma Windows [BI-95]).

      Suponer que en todo programa orientado a objetos obligatoriamente se debe usar herencia y encapsulamiento es incorrecto. Por ejemplo, para la clase C++ money, que sirve para manipular cantidades monetarias, no se usa herencia del todo [DiM-92]. Además, la mayor parte de las operaciones de esta clase no son miembros encapsulados en la definición. OOP es una herramienta útil, no una panacea.

    ADT                         OOP
UNIT Punto;

TYPE                           TYPE
  Rep_Punto = RECORD             TPunto = OBJECT
    color : WORD;                PRIVATE
  END;                             color : WORD;
                                 PUBLIC
  TPunto =  RECORD                 { ... }
    Rep : Rep_Punto; { TRUCO }     PROCEDURE MoveTo(x,y: WORD);
  END;      { p/ocultamiento }     PROCEDURE Show;
                                 END;
  PROCEDURE MoveTo(
              VAR p: TPunto;
              x,y  : WORD);
  PROCEDURE Show(
              VAR p: TPunto);
  { ... }
END. { UNIT Punto }

VAR                            VAR
  p: TPunto;                     p: TPunto;
  { ... }                        { ... }

x := 0;                        x := 0;
Punto.Show(p);                 p.Show;
WHILE NOT done DO BEGIN        WHILE NOT done DO BEGIN
  INC(x, 7);                     INC(x, 7);
  IF x > 640 THEN BEGIN          IF x > 640 THEN BEGIN
    x := 0;                        x := 0;
  END;                           END;
  Punto.MoveTo(p, x, 100);       p.MoveTo(x, 100);
  Delay(3500);                   Delay(3500);
END;                           END;

      En la Figura 3.4 se compara cómo debe codificarse un programa usando ADT's y cómo usando OOP. A la izquierda está la implementación que requiere más código, pues como no se usa OOP, se hace indispensable usar complejos métodos de programación para lograr el ocultamiento de datos. Por ejemplo, el ADT completo está definido e implementado en una unidad Pascal, aparte, de manera que se pueda simular el encapsulamiento al no incluir dentro de la unidad del ADT procedimientos que no correspondan a la implementación de sus operaciones. Esto hace que aumente mucho el número de unidades que forman un programa. Como en realidad no existe el encapsulamiento apoyado por el compilador, las operaciones del ADT quedan definidas aparte de los campos que lo componen. La versión OOP del mismo código es más sucinta, lo que muestra que, efectivamente, OOP aumenta la expresividad de un lenguaje de programación.

      Al invocar cualquier operación del ADT TElem definido en la Figura 3.2, es necesario que la variable (el objeto) sobre la que trabaja sea explícitamente nombrada como argumento, en tanto que si se usa OOP, como ocurre en la parte derecha de la Figura 3.4, el nombre de la variable se antepone al de la operación, hecho que marca la diferencia sintáctica, si bien no muy significativa, entre la programación procedimental y la programación por objetos.

      Como en OOP la variable aparece antes del nombre del método, se justifica hablar de programas Orientados a Objetos, pues los objetos aparecen antes que las operaciones en el código del programa. Un lenguaje que soporta adecuadamente OOP le permite al programador expresar el mismo programa más sucintamente, pero desafortunadamente no lo libera de la responsabilidad de escribir los algoritmos; esto no cambia, independientemente de si se llama a los objetos variables, o si se dice que un tipo es un objeto.

      OOP ha recibido más atención de la necesaria. Básicamente lo que le permite al programador es invocar de una manera diferente los procedimientos en sus programas, pues en lugar de escribir "Punto.Show(p)" para invocar el procedimiento "Show()" en la "variable p", lo que hace es enviarle el "mensaje Show()" al "objeto p": "p.Show();". Lo que se ha hecho es permitirle al programador poner la variable "p" antes del nombre de la operación "Show()". Esto representa una mejora sintáctica, que algunos llaman con propiedad "azúcar sintáctico" [Set-92]. De nuevo ocurre lo que había pasado con otros lenguajes: una mejora en la expresividad sintáctica del lenguaje es percibida por algunos como un portentoso avance tecnológico, que en realidad no lo es tanto.

      Independientemente de los epítetos con que se califique a los tipos de datos, la contribución realmente importante de su uso en programación ha sido el elevar el tipo de datos al rango de módulo, a la par de los procedimientos. Una vez que se acepta que un tipo de datos es un módulo, es sencillo clasificar en grupos las operaciones que pueden aplicarse a cualquier ADT:

1. Constructores y destructores. Estas operaciones son las encargadas de inicializar y destruir a cada una de las instancias del ADT. En general, es vital que el programador inicialice todos los objetos o variables que usa; el usar una variable antes de inicializarla es siempre un error, aunque algunos programadores tienen la suerte de incurrir en esta omisión sin que les falle su programa. El destructor es particularmente importante si el lenguaje no incluye un recolector de basura, pues en general la labor del destructor es devolver toda la memoria dinámica asociada a un objeto una vez que el objeto ya no se usará más en el programa.
         Por convención, en Pascal los nombres para estas operaciones son Init(), Clear(), Erase() y Done().
2. Copiadores. Este grupo de operaciones es importantísimo, pues el programador con frecuencia necesita copiar los objetos en su programa. Existen muchas maneras de copiar variables, entre las que destacan las siguientes:
   1. Copia profunda: se caracteriza porque hace una copia de todos los componentes del dato, aun de aquellos que están profundamente encajados en la estructura. La ventaja de este tipo de copia es que al modificar la copia nunca es posible que el original sea modificado.
   2. Copia superficial: esta es una forma de copiar sólo aquellos elementos que sean esenciales, pero no todos los que conforman un objeto. El problema de este tipo de copia es que, en algunos casos, al modificar la copia también queda modificado el original, porque ambos comparten algunos componentes de datos. La ventaja que tiene la copia superficial es que para algunos ADT's puede implementarse con un menor gasto de recursos, lo que a veces la hace más eficiente. A veces un ADT sólo tiene copia superficial porque la profunda resulta muy difícil de implementar.
   3. Copia por traslado: Cuando se requiere trasladar el valor de una variable a otra pero sin mantener el valor en variable de origen es muy útil usar la copia por traslado, la que para muchos ADT's se puede implementar con mayor eficiencia. Por ejemplo, para trasladar una lista que contiene sus elementos en memoria dinámica basta copiar el puntero a la cadena de elementos.
            Lo usual es que la copia por traslado sea eficiente sólo para ADT's que usan memoria dinámica, pues para ADT's simples muchas veces la operación de traslado es menos eficiente que la copia profunda.
   
         Por convención, en Pascal los nombres para estas operaciones son Copy(), Clone(), Shallow_Copy(), Move() y Swap(). En este trabajo se asume que al copiar siempre se usa una copia profunda, pues esta es la forma de asegurar que si cambia el valor del objeto copiado no cambie también el del original.
3. Comparadores. Estas son las operaciones que permiten comparar el valor de una instancia con el de otra. Como ocurre con la copia de valores, al compararlos también hay varios estilos. Por ejemplo, en el lenguaje Lisp la comparación con la función (eq a b) retorna verdadero sólo cuando los objetos "a" y "b" son el mismo, esto es, si están almacenados en la misma posición de memoria, mientras que (equal a b) hace una comparación profunda de las listas "a" y "b". El homólogo del copiador profundo es (equal a b), mientras que (eq a b) es muy eficiente, pues se limita a constatar que los punteros que corresponden a "a" y "b" son iguales.
         Por convención, los nombres para estas operaciones son Equal(), Less(), Greater(), etc.
4. Verificadores de invariantes. Estas operaciones se encargan de verificar o restaurar la invariante del ADT. Como a veces es imposible implementarlas, es muy raro que un ADT las incluya, pero conceptualmente tiene mucha utilidad definirlas.
         Por convención, los nombres para estas operaciones son OK() y Fix().
5. Cargadores y escritores. Permiten grabar o leer el valor de una instancia a una unidad de almacenamiento secundario, o también darle formato usando letras y números.
         Por convención, los nombres para estas operaciones son Load() y Store(), o Read() y Print().
6. Examinadores. Estas son las operaciones que permiten obtener el valor de la variable, pero sin cambiarlo.
         Estas operaciones tienen nombres que dependen mucho del tipo de datos. En este trabajo se les llama genéricamente Get(), porque obtienen uno o más valores de la instancia; en la práctica, el programador siempre escoge nombres mucho más significativos que éste.
         Muchas veces el programador decide llamar a esta operación con un nombre similar al del campo que se obtiene al invocarla. Por ejemplo, si el tipo de datos tiene un campo que se llama "_age", entonces un buen nombre para el extractor de ese campo es AGE() o age().
7. Mutadores. Estas son las operaciones que permiten cambiarle el valor a la variable.
         Estas operaciones tienen nombres que dependen mucho del tipo de datos. En este trabajo se les llama genéricamente Put(), porque almacenan uno o más valores en la instancia; en la práctica, el programador siempre escoge nombres mucho más significativos que éste.

      Al diseñar sus programas, el programador debe poner especial atención al definir los examinadores y mutadores de sus ADT's. Para definir las demás operaciones no hace falta hacer un esfuerzo intelectual grande, pues siempre hacen lo mismo. Es más, las operaciones importantes de cualquier ADT son los mutadores y examinadores, hasta el punto de que muchos programadores sienten que invertir tiempo en las otras es perderlo. Como esas otras operaciones son necesarias, en muchos lenguajes el compilador las provee sin costo intelectual para el programador. Por ejemplo, C++ facilita mucho el uso de constructores y destructores, mientras que todas las bibliotecas de clases que un programador Smalltalk usa, pueden trabajar con objetos persistentes, lo que libera al programador de la tediosa labor de almacenar en dispositivos de almacenamiento secundario los valores de las variable de su programa [BDG-93].

      La anterior clasificación cubre todas las operaciones, y un purista de la programación podría argumentar que una clase no está bien definida si no se le definen todos estos tipos de operación. En la práctica, para el programador es muy tedioso definir todas esas operaciones, pues muchos ADT's tienen una aplicación muy restringida, y no tiene sentido implementar para ellos toda esta batería de operaciones abstractas. Por ejemplo, en un programa que dibuja un círculo es necesario definir un tipo para representar una coordenada:

TYPE
  TCord = OBJECT
    x, y: WORD;
  END;

      Como el tipo TCord existe para desplegar una coordenada de referencia, el programador cliente nunca necesitará comparar dos valores mediante la operación TCord.Less(), por lo que para el tipo TCord sobra la operación Less(), pues en su programa el programador cliente nunca necesita comparar dos coordenadas. Sin embargo, el programador cliente puede verse forzado a implementar esta operación al usar una lista de coordenadas, si la lista tiene una operación TList.Less(), la que necesariamente debe invocar a TCord.Less(). En este caso el programador cliente debe definir la operación de comparación TCord.Less() no porque se necesita en el programa, sino porque de otra manera el programa no compilaría, pues para compilar la operación TList.Less() de la lista es necesario que exista la operación TCord.Less(). Esto quiere decir que el programador se ha visto obligado a simular la existencia de la operación TCord.Less(), a sabiendas de que en su programa nunca será invocada, pues de otra manera el compilador no aceptará el programa.

      Lo mejor para el programador cliente es usar bibliotecas de programas que no le obliguen a hacer trabajo extra. Desde esta perspectiva, las bibliotecas que obligan al programador cliente a hacer trabajo extra le estorban en su labor de programación, porque lo obligan a distraerse de su trabajo para cumplir con los requerimientos de la biblioteca. Por eso, lo más conveniente es construir las bibliotecas de programación de manera que no estorben la labor del programador cliente, obligándole a hacer trabajo irrelevante. En este trabajo se incluye un módulo, llamado Binder.pas, que sirve para suplirle a los contenedores las operaciones básicas de los valores almacenados, de manera que los programadores clientes de un contenedor no se vean obligados a crear operaciones para sus ADT's como requisito para usar un contenedor parametrizable.

      La utilidad principal de conocer esta taxonomía de las operaciones de ADT's no es que el hacerlas "obligatorias" redunda en una significativa mejora en la calidad de los programas. Más bien su utilidad principal se da porque, si el programador tiene una lista con todos los tipos de operaciones que puede necesitar para su ADT, le será muy fácil no implementar aquellas que no necesite, como fue el caso de TCord.Less(), y así no tendrá que invertir un gran esfuerzo intelectual en recordar las que sí debe incluir en su ADT. Es más fácil eliminar lo que sobra que aportar lo que falta.

      Una crítica que se puede hacer al uso de ADT's es que para lograr el ocultamiento de datos es necesario invocar a muchos procedimientos para hacer trabajos triviales. Por ejemplo, si el Rep de TElem es un caracter, al copiarlo hay que invocar el procedimiento Elem.Copy(x,y), cuando sería mucho más eficiente y rápido simplemente copiar el caracter "y" sobre "x" usando la asignación "x := y;". Como es necesario hacer un llamado a una subrutina para mantener la modularidad del ADT, resulta que Elem.Copy() cuesta veinte o treinta instrucciones en lenguaje de máquina por ejecución, cuando el mismo trabajo puede realizarse con dos o tres instrucciones: ¡un claro desperdicio!

      Sin embargo, si el compilador es capaz de desarrollar en línea los procedimientos, esta ineficiencia desaparece, pues aunque el código fuente del programa aparece una invocación a un procedimiento, en el código compilado lo que queda es el acceso directo al campo del objeto. Todavía Turbo Pascal no tiene esta capacidad, pero es posible que al evolucionar la obtenga, como le ha ocurrido a C++ (inline). De todas formas, la capacidad de poder definir exactamente un tipo de datos, para que pueda ser utilizado en cualquier contexto, justifica plenamente la pequeña ineficiencia en que se incurre al llamar a la subrutina que implementa cada operación del ADT; este es el precio que debe pagarse para lograr reutilizar código. Para un defensor de los ADT's es fácil afirmar que son pocos los casos en que este Sobretrabajo ("overhead" en inglés) afecta sensiblemente el rendimiento de un programa; es difícil estimar cuán cercana a la realidad está esta afirmación, pero en muchos casos es mejor que sea barato darle mantenimiento al programa, a que dure tres milisegundos menos ejecutándose. Además, si se acepta la heurística de que el 20% del programa es el que se ejecuta durante el 80% del tiempo, entonces puede también afirmarse que las "ineficiencias" producto del uso de abstracción de datos estarán muy "localizadas", por lo que será posible "optimizar" una pequeña parte del programa para lograr un programa "eficiente".

      Esta discusión es más importante de lo que a simple vista parece, pues existen programas, por ejemplo lo que trabajan en un ambiente de tiempo real, para los que es necesario ahorrar cada microsegundo que toma derreferenciar un puntero [Kri-97]. Por eso precisamente C++ cuenta con procedimientos que se desarrollan en línea (inline). De todas formas, lo importante de esta investigación es desarrollar las ideas, las que luego pueden ser trasladadas del lenguaje Pascal a C++, en caso de que no sea posible obtener toda la eficiencia que se requiere en Pascal.

      Seguramente las mejoras en los compiladores harán inatinentes estas preguntas. Lo mejor es usar inmediatamente abstracción de datos, aunque los compiladores que la soporten no estén todavía disponibles.

3.4 Contenedores

      Los programadores definen y usan objetos para crear simulaciones electrónicas de la realidad; por eso los ADT's son agregaciones de otros ADT's. Los Contenedores son ADT's que sirven para mantener una colección, o conjunto, de instancias de otros ADT's; un ADT es un contenedor si contiene varias instancias de otros ADT's. Muchas veces se dice que un contenedor es polimórfico (de muchas formas) si puede almacenar instancias de varios tipos de datos diferentes, aunque lo usual es lo contrario. La mayoría de los contenedores son abstracciones de las estructuras de datos que se necesitan en los programas.

      Después del vector, la lista es sin lugar a dudas el más importante de los ADT's contenedores. Las listas se pueden usar para implementar otros importantes contenedores como pilas, colas, grafos, y también árboles n-arios. De hecho, este trabajo es un esfuerzo que busca evitar que los programadores reprogramen el ADT lista cada vez que lo necesitan, aunque para algunos parezca fácil implementarla de nuevo. Si la técnica para reutilización de código aquí expuesta sirve sólo para evitar el gasto de reprogramar la lista, esta contribución habrá sido muy significativa.

      Como hay dos maneras diferentes de crear estructuras de datos, con punteros y agregación de campos, y como los contenedores son implementaciones de estructuras de datos, hay dos tipos bien definidos de contenedores, de acuerdo con la forma en que son implementados: usando punteros (como en la lista y el árbol), o agregando campos (como en la matriz y el arreglo). Es usual confundir las estructuras de datos con los contenedores, pero en realidad son cosas diferentes, pues la misma estructura de datos se puede usar para implementar diferentes contenedores, y también ocurre que un contenedor, por ser un ente abstracto, puede implementarse usando diferentes estructuras de datos. Para no confundir estos dos conceptos, es útil pensar que las estructuras de datos son los diagramas:

"Un diagrama para una estructura de datos dada es una representación pictórica de la estructura de datos que se construye usando un conjunto de notaciones predefinidas, y que muestra las relaciones primarias entre los componentes de la estructura de datos. [BI-87]"

      A estos diagramas la profesora Sandra Kikut los ha bautizado con el nombre de Modelos [Kik-90].

      6
     / \       
    7   5      ┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
   / \   \     │ 7 │ 1 │ 8 │ 5 │ 6 │ 0 │ 6 │ 7 │ 1 │
  1   8   4    └───┴───┴───┴───┴───┴───┴───┴───┴───┘
 / \   \         1   2   3   4   5   6   7   8   9
9   2  3

      El modelo de una estructura de datos es el dibujo que el profesor del curso hace en la pizarra para explicarles a sus pupilos por qué la estructura de datos es eficiente. El contenedor es un módulo de programación que, con base en el modelo, ofrece las operaciones que aparecen en su especificación. Por ejemplo, en la Figura 3.5 se muestra cómo implementar el contenedor árbol usando un arreglo: esta figura es un modelo que muestra cómo se ve el valor del contenedor en la memoria del computador, o sea, que muestra cómo se puede implementar el contenedor árbol usando un arreglo. La idea es poner en cada nodo una indicación de cuál es el padre del nodo. Por eso en el arreglo en su posición número 8 tiene almacenado un 7, pues el nodo padre de 8 es el nodo 7. Como el nodo 6 es la raíz del árbol, en la sexta entrada del arreglo el valor almacenado es un cero, pues en este caso el valor Tree.Null se representa como el índice "0". Los contenedores existen como módulos porque son expresión, en un lenguaje de computación, de los algoritmos que corresponden a las estructuras de datos.

      Como los contenedores son ADT's, también para ellos es necesario definir las operaciones básicas de la Figura 3.2 o de la Figura 3.3: a estas operaciones se las llama "básicas" o "elementales" pues sirven para cualquier ADT, sea este un contenedor o no. Por conveniencia, se llama ADT Elemental o ADT contenido al que está almacenado en un contenedor. Lo usual es que el ADT contenido sea simple, como un número entero (INTEGER) o una hilera (STRING), pero es perfectamente válido que un contenedor a su vez esté contenido en otro contenedor: una pila puede contener colas de árboles de listas de arreglos de matrices de personas.

TYPE
  PCpos = ^PCpos; { Localización dentro de TContainer }
  PContainer = ^TContainer;

  TContainer =  OBJECT
    PROCEDURE Init;         { ... operaciones básicas }
    { ... }
    PROCEDURE Read(     {?} VAR F : TEXT);

    FUNCTION  Empty {>>>} : BOOLEAN;
    FUNCTION  Full  {>>>} : BOOLEAN;
    FUMCTION  Count {>>>} : WORD;

    PROCEDURE Behave(   {+} b : TBehave; sw : BOOLEAN);
    FUNCTION  Behaviour({+} b : TBehave)   {>>>} : BOOLEAN;

    PROCEDURE Insert(   {+} VAR o : TElem; {+} p : PCpos);
    PROCEDURE Remove(   {?} VAR p : PCpos);

    FUNCTION  Find(     {+} VAR o : TElem) {>>>} : PCpos;

    FUNCTION  Valid(    {+}     p : PLpos) {>>>} : BOOLEAN;
    PROCEDURE Retrieve( {+}     p : PCpos) {>>>} : PElem;

    FUNCTION  First                        {>>>} : PCpos;
    FUNCTION  Next(     {+}     p : PLpos) {>>>} : PCpos;

  PRIVATE
    { Rep del contenedor }
  END;

CONST
  Null = PCpos(NIL);

      Los contenedores son objetos más complicados que los ADT's elementales, pues además de las operaciones básicas de los ADT's elementales, necesitan las operaciones de la Figura 3.6.

      Al especificar un contenedor es muy importante hacerlo de forma que pueda almacenar cualquier tipo de elemento, y no sólo uno específico; esto se logra cuando el contenedor es parametrizable. Para lograr que el contenedor sea parametrizable, en su implementación sólo se pueden usar las operaciones básicas del ADT elemental contenido, pues esas son las que cualquier contenedor necesita para manipular el elemento que contiene, aún si el elemento almacenado es a su vez otro contenedor. Es necesario que la cohesión entre el contenedor y su elemento contenido sea lo más baja posible, para aumentar la modularidad del contenedor (y la del programa), por lo que el ligamen entre los dos debe hacerse únicamente a través de las operaciones básicas del ADT elemental.

TYPE
  TStack = RECORD
    elem   : ^ARRAY[0..49] OF TElem;
    ultimo :  WORD;
  END; { TStack }

PROCEDURE Done(           { EXPORT } { Adolfo }
  {?} VAR S : TStack      { SELF }
);
VAR
  i : WORD;
BEGIN { Done }
  { sólo hay que destruir los elementos activos }
  FOR i := S.ultimo DOWNTO 0 DO BEGIN
    S.elem^[i].Done;
  END;
  System.Dispose(S.elem);
END;  { Done }

      La Figura 3.7 es una posible implementación de la operación básica Done() del ADT Pila (Stack en inglés), que muestra cómo TStack.Done() invoca a TElem.Done(), el destructor del elemento contenido en la pila. Si TElem, el tipo de elemento contenido en la pila, fuera a su vez otro contenedor, al invocar a su destructor, TElem.Done(), este también invocará los destructores de todos los campos que tiene en su Rep, o sea que la invocación original del destructor del contenedor, TStack.Done(), desencadena su destrucción completa, incluyendo la todos los ADT's que contiene. Muchas de las implementaciones de las operaciones del contenedor deben invocar a la operación homóloga de su elemento contenido; por ejemplo, TStack.Store() debe invocar a TElem.Store(), TStack.Clear() a TElem.Clear(), etc. De esta forma se logra que el mismo contenedor pueda funcionar con diferentes tipos de elemento, lo que lo convierte en un contenedor reutilizable.

      Para cada contenedor hay que proveer un tipo de datos que sirva para denotar los valores almacenados en el contenedor. A este tipo se le llama Posición en el contenedor, y se usa para indicar la parte de contenedor sobre la que se trabaja. Las posiciones sirven para desplazarse dentro del contenedor, para usar sus valores. Por ejemplo, para almacenar objetos dentro del contenedor es necesario indicar en qué parte del contenedor hacer la inserción, lo que se logra indicando la posición de inserción. Para un arreglo las posiciones son índices escalares que indican cuál de los componentes del arreglo se está usando. Para una lista es necesario definir si una inserción se hace al principio o al final de la lista, y en un árbol se puede insertar un elemento como nodo raíz o como hoja. En la Figura 3.6 (Operaciones de un ADT contenedor) la posición es el tipo "PCpos" (P = Puntero, C = Contenedor, pos = posicionamiento). También cabe definir la "Posición nula", como una posición que nunca referencia un objeto (Container.Null).

      El programador debe ser cuidadoso cuando guarda posiciones al contenedor en su programa, pues cuando cambia el valor del contenedor la posición puede dejar de denotar a un elemento en el contenedor. Por ejemplo, si el contenedor es una lista y el programador guarda la posición del último elemento, al ser ese valor removido de la lista, la posición guardada deja de ser una válida en el contenedor. (Si pensamos en una posición como un índice en un arreglo, entonces las posiciones inválidas son índices fuera del rango del arreglo).

      Algunas veces no hace falta definirle al contenedor el tipo para posicionamiento, como por ejemplo, para el ADT pila, pues los elementos de la pila entran y salen por el mismo lugar (el tope de la pila). De todas maneras, es cómodo que siempre exista el tipo PCpos.

TYPE
  PNode = ^TNode;
  TNode =  OBJECT  { nodo de una lista }
    o    :  TObj;  { valor almacenado  }
    next : ^TNode; { posición del siguiente }
  END

  TList = ^TNode;  { ADT lista }

      En la implementación de los contenedores generalmente es necesario usar tipos auxiliares para definir los componentes del contenedor. Por ejemplo, para definir una lista es necesario crear un tipo que representa los nodos de la lista. En los libros de texto de estructura de datos, la forma usual de definir listas es la que se muestra en la Figura 3.8, en la que se violan varias reglas de abstracción y en particular la del ocultamiento de datos. Para crear la lista es necesario que el elemento contenido en la lista, de tipo "TObj" en este caso, esté a la par del campo de conexión de la lista, que en este caso se llama "next". Como no se puede implementar una lista sin usar nodos, y como para insertar los elementos en la lista no hace falta que el programador cliente de la lista conozca de la existencia de nodos, entonces se puede concluir que los nodos son parte del Rep de la lista. El tipo PCpos para posicionamiento en el contenedor en muchas ocasiones es un puntero a uno de los nodos que lo forman, o, si no lo es, entonces tiene una gran relación con él. Para preservar el ocultamiento de datos es muy importante que las variables de tipo "PCpos" sean posiciones abstractas, independientemente de cómo estén implementados los nodos, las posiciones o las listas. Esto quiere decir que el programador cliente del contenedor puede usar variables que contienen posiciones, pero no puede suponer que las posiciones son punteros, ni tampoco puede derreferenciar una posición cuyo Rep es un puntero, pues estaría violando el ocultamiento de datos del contenedor.

      Como los nodos que se usan para implementar un contenedor son parte del Rep, es necesario encontrar un mecanismo para evitar que el programador cliente del ADT use los punteros a estos nodos indiscriminadamente, de forma que esté obligado a usarlos siempre como argumentos de las operaciones del contenedor. Hay dos caminos para lograrlo. Uno es definir los nodos como tipos opacos, lo que es posible en lenguajes como Modula-2 [Wir-82], pero que no funciona bien en el contexto de Turbo Pascal. La otra forma de hacerlo es definir el tipo PCpos como un puntero a sí mismo, como se hizo en la Figura 3.6:

TYPE
  PCpos = ^PCpos; { Localización dentro de TContainer }

CONST
  Null = PCpos(NIL);

      Este método obliga al programador del ADT a usar Transferencia de tipos, que es una facilidad del lenguaje que permite usar una variable de un tipo como si fuera de otro tipo. El ocultamiento de datos se preserva porque al derreferenciar una variable de tipo PCpos no se pueden accesar los campos del nodo: la expresión "p^.nodo" provoca un error de compilación si "p" es de tipo PCpos. El inconveniente de este método es que en la implementación del ADT deben usarse expresiones como "PNode(p)" [Pascal y C++], o "(PNode *) p" [C y C++]. El problema de usar transferencias de tipos es que el programador deja de usar la verificación fuerte de tipos con que el compilador le protege de muchos errores, y puede incluso llegar a escribir programas que no tienen sentido alguno. Pero como esa es la única forma de implementar el ocultamiento de datos en Turbo Pascal, no queda más que recomendarle al programador del ADT contenedor que sea "muy cuidadoso" al usar este oscuro mecanismo.

      En los casos en que se usan contenedores que manejan sus elementos contenidos usando las operaciones elementales de la Figura 3.2, el uso de transferencia de tipos no es un problema muy grande, pues sólo unas pocas personas tienen la responsabilidad de implementar los contenedores.

      La constante "Null" es la posición nula en el contenedor, que siempre referencia una posición inválida y se usa de forma análoga al NIL de punteros. La ventaja de Null es que es del tipo que corresponde al contenedor, lo que ayuda a detectar errores de lógica en tiempo de compilación. En aquellos casos en que el tipo PCpos no es un tipo puntero, la constante Null será definida de forma diferente. Por ejemplo, se puede definir Null como PCpos(51), si el Rep del contenedor es un vector de dimensiones [10..50].

      De la discusión anterior se puede concluir que al especificar un contenedor no basta con sólo especificar sus operaciones; también es necesario describir otros objetos que, aunque a primera vista no lo parezca, forman parte de la abstracción. Tal vez esta sea la razón por la que muchas bibliotecas de contenedores no están bien construidas, pues no les dan importancia a estos "condimentos" que acompañan a los tipos abstractos de datos.

      Las operaciones de los contenedores pueden agruparse en los siguientes grupos:

1. Examinadores. Estas operaciones sirven para saber si el contenedor está vacío o lleno. Por convención, los nombres para estas operaciones son Empty() y Full(). Como ocurre con los examinadores para ADT's elementales, estas operaciones nunca alteran el valor del contenedor.
2. Enumeradores. Estas operaciones sirven para averiguar cuántos elementos están almacenados en el contenedor, o en alguna de sus partes. En general, el nombre para este tipo de operación es Count(), aunque para algunos ADT's es saludable definir varios enumeradores. Por ejemplo, para el árbol conviene definir tanto Count() (cantidad de elementos del árbol) como Count_Children() (cantidad de hijos de un nodo).
3. Insertadores. Estas operaciones permiten agregar un nuevo elemento al contenedor. Muchas veces las operaciones de inserción requieren que el programador indique dónde deben realizarse.
         El nombre para estas operaciones depende mucho del tipo de contenedor. Por ejemplo, para una pila el nombre que se usa es Push(), y para una cola es En_Queue(). Aquí se les llama genéricamente Insert().
4. Borradores. Estas operaciones sirven para eliminarle elementos al contenedor. Como ocurre para las operaciones de inserción, muchas veces el programador debe indicar en qué posición realizar el borrado.
         Es usual que para cada operación de borrado en el contenedor exista una de inserción que la complementa. Por ejemplo, una pila siempre tiene a Pop(), que complementa a Push(), y la cola tiene a De_Queue(), que complementa a En_Queue(). Aquí se les llama genéricamente Remove(), aunque Delete() también es un buen nombre.
5. Posicionadores. Estas operaciones sirven para trasladarse hasta un lugar fijo del contenedor, pues siempre denotan la misma posición del ADT. Cada contenedor ofrece diferentes operaciones para este fin.
         En una lista tiene sentido posicionarse en el primer elemento mediante First(), o en el último con Last(); en un árbol se llega a la raíz con Root().
6. Recorredores. Sirven para examinar uno a uno los valores del contenedor, y para moverse a lo largo y ancho del ADT. Los recorredores siempre avanzan y retroceden en el contenedor respecto a una posición relativa actual; podría decirse que son "posicionadores relativos" (o también se puede llamar a los posicionadores "recorredores absolutos").
         Para la lista los recorredores usuales son Next() y Prev() que permiten avanzar y retroceder, y para el árbol son Father() y Child().
7. Localizadores. Estas operaciones sirven para encontrar un elemento dentro del contenedor. Cada contenedor ofrece operaciones diferentes para encontrar sus elementos de acuerdo a criterios muy diferentes.
         El nombre para estas operaciones depende mucho del tipo de contenedor. Por ejemplo, para un conjunto el nombre que se usa es Member(), pero para un Árbol de Búsqueda puede ser Find(). Aquí se les llama genéricamente Locate(). La operación Valid(C,p), que verifica que "p" sea una posición válida en el contenedor "C", también pertenece a este grupo de operaciones.
8. Accesador. Las operaciones de localización y posicionamiento del contenedor retornan posiciones (de tipo PCpos), pero el programador cliente del ADT lo que necesita es accesar el elemento que ha localizado. Para esto debe invocar la función Retrieve() que se encarga de transformar una posición del contenedor ("PCpos") en el puntero al elemento ("PElem"). Por eso en la Figura 3.6 el encabezado de esta operación es:
         PROCEDURE Retrieve( {+} p : PCpos ) {>>>} : PElem;
         Operaciones como Retrieve() contribuyen a aumentar la modularidad de los programas, pues sirven para separar al contenedor de su elemento contenido.
         Otros autores llaman a los accesadores "iteradores": en C++ un iterador es un puntero inteligente dentro de un contenedor, o sea, que en C++ un iterador es lo que aquí se llama accesador. En la sección 3.5 se describe una maquinaria completa que sirve para obtener un subconjunto de los valores almacenados en el contenedor, en un orden determinado. Por eso en este trabajo para nombrar a la abstracción de iteración se usa la palabra "iterador", y para llamar a las variables que apuntan a un elemento del contenedor se usa el término "posición".

      Es interesante definir las categorías en las que están todas las operaciones de un ADT. Sin embargo, en este trabajo se usan estos términos en pocas ocasiones, pues para parametrizar contenedores lo importante son las operaciones del elemento contenido.

      Siempre es valioso hacer clasificaciones que ayudan a entender mejor los conceptos. Si se examina su implementación, a los contenedores también se les puede clasificar en contenedores por adyacencia en contenedores enlazados. Los arreglos y matrices mantienen a todos sus elementos almacenados juntos en memoria por lo que son ejemplos de la categoría de los contenedores por adyacencia. En contraposición, las listas son contenedores enlazados, aunque puede ocurrir que una lista sea implementada como un contenedor por adyacencia. Los resultados de esta investigación se aplican mejor a los contenedores enlazados, aunque también se pueden aplicar a los otros.

3.5 Iteradores

      Como en los programas se usan contenedores, es necesario que el programador disponga de mecanismos para accesar los elementos de los contenedores. Estos mecanismos pueden implementarse básicamente de dos formas:

1. Definiendo en el ADT contenedor operaciones que permitan recorrerlo, como por ejemplo List.First() y List.Next() o Tree.Root() y Tree.Child().
2. Usando iteradores.

      Para ambos métodos el programador cliente deberá invocar el accesador Container.Retrieve() del contenedor, que es la función encargada de convertir la posición en el contenedor (PCpos), retornada por cada una de las operaciones de recorrido y por los iteradores, en un puntero al elemento del contenedor.

VAR
  p : PLpos;
  pe: PElem;
{...}
  p := List.Last(L);
  IF p <> List.Null THEN BEGIN
    REPEAT
      pe := List.Retrieve(L,p);    { procese la lista L de }
      Elem.Print(pe^);             { atrás hacia adelante  }
      p  := List.Prev(p,L);
    UNTIL p = List.Null;
  END;

      El código de la Figura 3.9 sirve para recorrer una lista hacia atrás, usando las operaciones de recorrido de la lista para moverse a lo largo de ella. Esta implementación es un poco alambicada, y puede que no sea muy eficiente. Por ejemplo, si la lista no es doblemente enlazada, el tiempo de ejecución de la operación List.Prev() es O(n); además, para comprender bien qué hace este código hay que recordar que List.Prev(L,p) retorna List.Null cuando p = List.First(L). Esta implementación es correcta, pero no es eficiente y clara; después de todo, lo más natural habría sido usar la instrucción "WHILE", y no un "REPEAT" anidado dentro de un "IF". La alternativa a esta implementación es usar la abstracción de iteración, plasmada en los iteradores, que fueron creados precisamente para simplificar el trabajo del programador que muchas veces necesita recorrer los elementos almacenados en un contenedor.

      El Iterador es uno de los módulos básicos para la construcción de programas, pues es una abstracción que sirve para recorrer en un orden predefinido los elementos que están almacenados en un contenedor. Este orden debe ser especificado de forma precisa.

      Junto al concepto de iterador también se puede definir el de "Generador". A diferencia del iterador, que generalmente es compilado aparte del contenedor, un generador generalmente es un método del contenedor que establece cómo accesar sus datos [Bis-90]. En muchas bibliotecas no se usan generadores, pues es más cómodo que un módulo aparte, el iterador, se encargue de exportar el mecanismo para obtener los valores almacenados en el contenedor. Además, esta separación de labores facilita la construcción y mantenimiento de la biblioteca.

      En la biblioteca STL de C++ [STL-95], el concepto de iterador es un poco diferente, pues los iteradores realmente son punteros inteligentes [Zig-96a]. Como en C++ un puntero se puede usar como si fuera un vector, para los programadores C++ es muy natural ver a todos los contenedores como si fueran vectores sofisticados; pero esta visión particular de un lenguaje, C++, y específica para la implementación de una biblioteca de contenedores, STL, no se ha usado en este trabajo, pues conviene lograr una implementación que pueda ser usada en muchas plataformas o lenguajes diferentes. En otras palabras, aquí "iterador" significa "Mecanismo para obtener, uno a uno, los valores de un contenedor". Como caso particular, y si el lenguaje tiene cualidades sintácticas adecuadas, este mecanismo puede implementarse usando punteros inteligentes, como en C++.

{ ORDEN
  Este iterador permite recorrer el ADT lista desde 
  adentro hacia los extremos.
  - Si L contiene (6,4,2,1,3,5,7), entonces IInOut
    la recorrerá en el orden 1-2-3-4-5-6-7.
  - Si L contiene (5,3,1,2,4,6), entonces IInOut
    la recorrerá en el orden 1-2-3-4-5-6. }

      Como se muestra en la Figura 3.10, al especificar un iterador es necesario definir el orden en que los elementos del contenedor serán recorridos. Las operaciones de un iterador siempre son las mismas, pues lo que cambia de un iterador a otro es el orden de recorrido del ADT, y no la interfaz que usa el programador, cliente del módulo. Cada orden de recorrido define a un iterador. Lo usual es que un iterador recorra todos los elementos del contenedor, pero no siempre es este el caso. Por ejemplo, puede existir un iterador que recorre sólo los elementos "pares", o que al recorrer el contenedor toque algunos elementos más de una vez. Podría darse el caso extremo de que un iterador nunca terminara de recorrer el ADT.

VAR
  L : TList;  { lista a recorrer     }
  I : IInOut; { iterador             }
  p : PLpos;  { posición en la lista }
  pe: PElem;  { puntero al elemento  }
{...}
  InOut.Init(I);                         { constructor }
  InOut.Bind(I,L);                   { I recorrerá a L }
  WHILE NOT InOut.Finished(I) DO BEGIN     { ¿terminó? }
    p  := InOut.Current(I);      { posición actual     }
    pe := List.Retrieve(L,p);    { puntero al elemento }
    Procese(pe^);                { trabajo...          }

    InOut.Next(I);               { avanza              }
  END;
  InOut.Done(I);                          { destructor }

      Los iteradores existen porque son módulos que encapsulan el acceso eficiente a los elementos de un contenedor. El ejemplo de la Figura 3.11 muestra cómo se usa un iterador y cuáles son las operaciones que se necesitan para recorrer el contenedor. En este caso se usa el iterador IInOut.pas para recorrer una instancia del ADT Lista. Si el contenedor es un árbol, los clásicos recorridos infijo, posfijo y prefijo pueden ser implementados con iteradores. Es fácil implementar un iterador que recorre únicamente las hojas del árbol, o sólo los nodos internos, etc. Lo mismo puede decirse del ADT conjunto, que es muy utilizado.

      El código de la Figura 3.9 para recorrer la lista hacia atrás es un ejemplo de las contorsiones que tiene que hacer el programador para implementar correctamente el acceso a los elementos del contenedor. Estas contorsiones no se eliminan si se usa un iterador; simplemente ocurre que bastará implementar una sola vez este código, cuando se implementa el iterador, y luego los programadores clientes del contenedor quedarán liberados de invertir esfuerzos para resolver de nuevo este mismo problema. Más aún, como muchos de los errores de programación ocurren en los casos límite, al implementar correctamente el iterador se elimina una fuente de errores, pues al iterador hay que implementarlo correctamente sólo una vez, y de ahí en adelante el programador cliente no tiene que preocuparse por los casos límite que tanto daño hacen, y que son tan tediosos de manejar. La principal razón por la que los iteradores tienen el rango de abstracción es precisamente que contribuyen a la reutilización de módulos, y así evitan la reprogramación. Por eso en la Figura 3.11 no hay un IF para tratar el caso límite "p = List.Null", como sí ocurre en la Figura 3.9.

      Como conceptualmente todos los iteradores hacen lo mismo, y lo único que cambia de uno a otro es el orden de recorrido, entonces siempre tienen las mismas operaciones, que son las siguientes:

1. Init(): Es el constructor del iterador.
2. Bind(): Es la operación del iterador que se encarga de asociarlo con el contenedor por recorrer.
3. Finished(): Regresa TRUE cuando ya el iterador ha recorrido completamente el contenedor.
4. Current(): Retorna el valor actual del iterador, o sea, la posición actual en el contenedor.
5. Next(): Avanza el iterador a la siguiente posición del contenedor.
6. Advance(n): Avanza el iterador hacia adelante o hacia atrás. Si n es un número positivo, equivale a invocar Next() n veces.
7. From(): Avanza el iterador para que la iteración comience a partir de una posición diferente del principio del contenedor.
8. Range(): Establece un rango de iteración, esto es, delimita un subconjunto de los valores del contenedor que recorrerá el iterador.
9. Done(): Es el destructor del iterador.

      Como todos los iteradores siempre tienen las mismas operaciones, todos se usan de la misma manera. Esto quiere decir que, si se cambia el iterador IInOut por otro, por ejemplo IBackL, entonces el código para accesar el ADT sería el mismo de la Figura 3.11, pero sustituyendo el nombre "IInOut" por "IBackL". Otra gran ventaja de usar iteradores es que el código de proceso para cada elemento no queda mezclado con la implementación del código para recorrer el contenedor.

PROCEDURE LRP(                            { ADH }
  {+} VAR T : TTree;       { SELF }
  {+}     p : PTpos;       { posición de T }
  {?} VAR F : TEXT
);
{ RESULTADO
  Recorre recursivamente el árbol "T" en LRP e imprime
  en el archivo "F" el valor de cada elemento.
  - El llamado inicial debe ser LRP(T, Root(T), F).
  - Para cambiar el proceso que se le hace a cada
    elemento es necesario cambiar el código que está
    marcado con <<<< y >>>>. }
BEGIN { LRP }
  IF p = Tree.Null THEN BEGIN
    EXIT;
  END;     { límite de recursión }

  { recorre y procesa los dos subárboles de "p" }
  LRP(T, Tree.Left_Child(T,p),  F);
  LRP(T, Tree.Right_Child(T,p), F);

{*********************} { CODIGO POR CAMBIAR }

  { procesa los elementos del árbol }
  Elem.Print(Tree.Retrieve(T,p)^, F);

{*********************}  { FIN DE CAMBIOS }

END;  { LRP }

      En la Figura 3.12 se destaca cómo dentro de la implementación del procedimiento LRP(), que recorre recursivamente un árbol, es necesario incluir un llamado a la función de proceso, Elem.Print() en este caso, lo que limita la facilidad de reutilizar este código: el programador cliente del ADT árbol está obligado a cambiar la implementación de LRP() si en lugar de invocar a Elem.Print() lo que necesita es aplicarles otro proceso a los valores del árbol, como Elem.Modify(), lo que claramente atenta contra la modularidad del programa.

      La principal ventaja de la abstracción de iteración es que independiza el código para recorrer el ADT contenedor de su implementación. Por eso los iteradores disminuyen la cohesión entre los módulos de los programas, lo que facilita su construcción y mantenimiento.

      Un iterador nunca cambia el valor del contenedor que recorre; esto contrasta con los iteradores de C++, que sí pueden cambiar al contenedor [Zig-96a]. Al implementar el iterador, el programador necesita estar seguro de que los valores almacenados en el contenedor tampoco cambiarán, pues, de otra manera, le será muy difícil obtener una implementación correcta y eficiente. Por ejemplo, si el iterador retorna los elementos del contenedor en orden ascendente, y si mientras el iterador está trabajando cambia el valor de algunos de los elementos del contenedor, entonces el iterador debería encontrar el siguiente elemento por retornar haciendo una búsqueda exhaustiva en todo el contenedor, lo que impide implementarla usando un método de ordenamiento eficiente. Es más, en este caso es casi imposible garantizar que todos los elementos del contenedor sean retornados, pues si algunos son insertados y luego borrados antes de que les toque el turno de ser visitados por el iterador, nunca serán recorridos. La gravedad de la falla que se produce al cambiar el valor del contenedor mientras se le recorre con un iterador depende mucho de la implementación del iterador; en algunos casos no pasará nada, y en otros puede producirse un error fatal en tiempo de ejecución.

      En la Figura 3.11 todas las operaciones del iterador están calificadas con el nombre de la unidad del iterador, "InOut" en este caso en que el iterador está implementado en el archivo InOut.pas, para evitar los errores de sintaxis que se producen cuando el compilador de Pascal no puede determinar cuál de todas las versiones de los procedimientos Init() y Done() debe usar, pues estos identificadores y algunos otros se usan en varios módulos, tanto en ADT's como en iteradores. En otros lenguajes, como Ada y C++, este problema es menos serio, pues es posible usar el mismo nombre para denotar diferentes procedimientos, usando sobrecarga de identificadores ("overload").

VAR
  L : TList;
  I : IInOut;
  p : PLpos;
  pe: PElem;
{...}
  I.Init;
  I.Bind(L);
  WHILE NOT I.Finished DO BEGIN      
    p  := I.Current;
    pe := L.Retrieve(p);
    Procese(pe^);
    I.Next;
  END;
  I.Done;

      Esta falta de expresividad de las primeras versiones de Pascal, que queda patente en el ejemplo de la Figura 3.11, obliga al programador a incluir en la invocación de todas los procedimientos el nombre de la unidad en que están implementados. Debido a esta incomodidad resulta mejor usar la notación de programación por objetos para especificar e implementar programas; en este caso el iterador se usaría como se muestra en la Figura 3.13. De nuevo, la notación de OOP hace más claro el programa, y además evita completamente la ambigüedad que se produce al usar los mismos nombres para los métodos de cada iterador. La notación de OOP es mucho más cómoda y debe ser siempre preferida.

TYPE
  IInOut = OBJECT (List.Iterator)

    CONSTRUCTOR Init;
    DESTRUCTOR  Done;              VIRTUAL;

    PROCEDURE Bind( VAR L:TList ); VIRTUAL;
    FUNCTION  Finished: BOOLEAN;   VIRTUAL;
    FUNCTION  Current : PLlink;    VIRTUAL;
    PROCEDURE Next;                VIRTUAL;

              {$IFDEF Use_PRIVATE}
  PRIVATE     {$ENDIF Use_PRIVATE}
    _dir  : BOOLEAN;              { _p  vs _q  }
    _p    : List.PLlink;          { <--p       }
    _q    : List.PLlink;          {      q-->  }
    _L    : PList;                { Contenedor }
  END;

      En la Figura 3.14 está la declaración de tipos para el iterador InOut.pas que corresponde al iterador de la Figura 3.13. En esta declaración está encapsulado tanto el Rep del iterador, como sus operaciones. Los valores "_p" y "_q" sirven para marcar la siguiente posición que debe devolverse tanto hacia la izquierda (_p) como a la derecha (_q). El campo "_dir" indica si en la siguiente iteración hay que moverse a la derecha o a la izquierda. La variable de compilación "Use_PRIVATE" sirve para mantener compatibilidad con las versiones de Pascal que no incluyen soporte para ocultamiento de datos mediante la palabra clave PRIVATE.

      Como es necesario que los iteradores sean implementados eficientemente, lo usual es que quien se encargue de programar el contenedor también implemente el iterador. Para lograr una alta eficiencia, en muchos casos es necesario accesar desde la implementación del iterador el Rep del contenedor; esto hace necesario que la implementación del iterador y la del contenedor estén íntimamente ligadas. En la terminología del lenguaje C++, los dos módulos deben ser "módulos amigos" (friend en C++).

      En Turbo Pascal se modulariza separando el programa en archivos llamados Unidades (UNIT). Es difícil lograr que dos unidades sean amigas porque, cuando se usa OOP, los campos privados de un tipo no pueden ser accesados desde otra unidad. Esto obliga al programador a simular unidades amigas creando una copia exacta del tipo en la otra unidad, para luego usar trasferencia de tipos en esa otra unidad. El problema de hacer las cosas de esta manera es que, cuando se modifica el contenedor, en muchos casos el compilador no produce mensajes de error que le recuerden al programador que debe resincronizar la implementación del iterador con la del contenedor. Este problema no sólo existe para los iteradores, sino también para todas las unidades que necesiten accesar un Rep definido en otra unidad.

UNIT Cliente;     { cliente de Biblio.pas }

INTERFACE
  USES Biblio; { importa los tipos de Biblio }

IMPLEMENTATION
{ Esta implementación accesa el Rep del contenedor.
  - Esto implica que cuando se cambia el Rep en Biblio,
    el programador es responsable de sincronizar el
    tipo Cliente.TRep para que tenga exactamente los
    mismos campos de Biblio.TRep. }
TYPE
   TRep = OBJECT ({...})
     { copia EXACTA de los campos de Biblio.TRep }
   END;
TYPE
  Check_TypeCast =  { si esto no compila, entonces los  }
                    { dos tipos son de tamaño diferente }
    ARRAY [
      SizeOf(Biblio.TRep)  .. SizeOf(Cliente.TRep),
      SizeOf(Cliente.TRep) .. SizeOf(Biblio.TRep)
    ] OF CHAR;
              { Acceso a los campos del Rep }
VAR
  o1 : Biblio.TRep;           { tipo de la otra unidad }
  x  : Cliente.TRep;          { tipo en esta unidad    }
   ...
  x.campo := Cliente.TRep(o1).campo;  { ...horrible... }

      En la Figura 3.15 se muestra cómo simular unidades amigas en Turbo Pascal. En este caso desde la unidad Cliente.pas se accesa el Rep del tipo definido en la unidad Biblio.pas. Para lograrlo hay que copiar toda la declaración de los campos del tipo Biblio.TRep en la unidad cliente, y luego usar una transferencia de tipos para accesar los campos definidos Biblio.TRep. Cuesta mucho darle mantenimiento al código que resulta.

      La semántica de la transferencia de tipos que implementa el Turbo Pascal exige que los tipos que se usen en cualquier transferencia de tipos sean del mismo tamaño. Esto implica que, si al modificar un tipo este cambia su tamaño, el compilador emitirá un error en aquellos casos en que se use transferencia de tipos. En la Figura 3.15 se usa esto para informarle al programador que ha cambiado el tamaño de sus tipos pues, si eso ocurre, el compilador emitirá un error de compilación que el programador debe interpretar como una señal para que manualmente los vuelva a sincronizar. Para esto se define una matriz cuyas dimensiones dependen del tamaño de los tipos definidos en las unidades Biblio.pas y Cliente.pas. Si alguno de estos tipos cambia de tamaño, entonces esta matriz tendrá un rango vacío, y en consecuencia el compilador señalará un error, precisamente en el lugar adonde se explica para qué ha sido creada la matriz.

UNIT Biblio;

INTERFACE


TYPE
  TObj = OBJECT
    { campos }
  PRIVATE
    a,b,c : TType;  { privados }
  END;  { TObj }

  Rep = OBJECT
  PUBLIC     { NO son privados }
    a,b,c : TType;
  END;

  Check_TObj_vs_Rep = ARRAY [
    SizeOf(TObj).. SizeOf(Rep),
    SizeOf(Rep) .. SizeOf(TObj)] 
  OF CHAR;

VAR
  O : Biblio.Rep;

   ...
  O.a := O.b; { uso directo }

UNIT Cliente;

INTERFACE
  USES Biblio;

TYPE
  TDrv = OBJECT (Biblio.TObj)
    { más campos }
  PRIVATE
    d,e,f : TType;
  END;  { TObj }

   Rep = OBJECT (Biblio.Rep)
   PUBLIC
     d,e,f : TType; { copia }
   END;

  Check_TDrv_vs_Rep = ARRAY [
    SizeOf(TDrv).. SizeOf(Rep),
    SizeOf(Rep) .. SizeOf(TDrv)] 
  OF CHAR;

VAR
  B : Biblio.TObj;
  D : Cliente.TDrv;
   ...
  Rep(B).a := Rep(B).b;
  Rep(D).a := Rep(D).b;
  D.e := D.f;

      Hay otra forma de accesar el Rep de un objeto desde otra unidad, como se muestra en la Figura 3.16. La idea es crear tanto en la unidad cliente como en la otra, una pareja de tipos llamados Rep, que están sincronizados, y que contienen exactamente los campos del tipo que se necesita accesar desde otra unidad. Por ejemplo, en la Figura 3.16 al definir el tipo TObj en la unidad Biblio.pas, también se define su tipo gemelo Biblio.Rep, que contiene exactamente sus mismos campos. En la unidad Cliente.pas, para definir el tipo Rep que corresponde al tipo Cliente.TDrv (derivado de Biblio.TObj), lo que se hace es heredar de Biblio.Rep la definición de los campos. Cuando hay que accesar los campos privados del tipo base, en la unidad Cliente.pas hay que usar una transferencia de tipos:
      VAR
        D: TDrv;
        Rep(D).a := Rep(D).b;
pero si lo que se necesita es usar los campos extra que el tipo derivado agrega al tipo base, no hace falta la transferencia de tipos:
      VAR
        D: TDrv;
        D.e := D.f;
Esta manera de hacer las cosas tiene dos ventajas: relega en el programador de la unidad base (Biblio.pas en este caso), la responsabilidad de sincronizar el tipo Rep, y permite el uso de herencia, como se muestra con la definición del tipo Cliente.TDrv (en la práctica, la definición del tipo Rep se puede poner inmediatamente después de definir el tipo base). Tiene la desventaja, muy pequeña por cierto, de que requiere que los objetos hayan sido declarados con la palabra reservada Pascal OBJECT; no funciona con registros declarados como RECORD. Por su generalidad, el método usado en este trabajo para accesar los campos desde otra unidad es el de la Figura 3.16.

      Los programas sufren modificaciones con el correr del tiempo, y lo mismo ocurre con los tipos de datos. Si es necesario reordenar los campos de un tipo, entonces el tamaño del tipo no cambiará. En este caso, el método de la Figura 3.15 no servirá para recordarle al programador que debe sincronizar de nuevo los módulos, pues el compilador Pascal sólo emite error cuando el programador trata de hacer una transferencia entre tipos de tamaño distinto. Pero si el cambio en el tipo de datos modifica su tamaño original, el compilador Pascal no aceptará la transferencia de tipos en los módulos que usan este control de compilación, lo que forzará a la recompilación de todos los módulos amigos del tipo que ha cambiado. De todas formas, como esta clase de error es muy difícil de detectar, debiera ser el sistema de compilación el que se encargue de sincronizar de nuevo los módulos amigos. Para eso C++ incluye la construcción sintáctica friend.

      Generalmente los iteradores usan estructuras de datos auxiliares para recorrer eficientemente el contenedor. Por ejemplo, si el iterador debe retornar los elementos del contenedor en orden ascendente, una forma relativamente sencilla de implementarlo es poner en el Rep del iterador un vector de punteros al contenedor (de tipo PCpos), y luego ordenarlo usando una rutina de biblioteca. En este caso, Bind() se encargaría de crear y ordenar el vector, y Next() avanzaría un contador que indique cuál es el último elemento retornado. Finished() se limitaría a comparar al contador con el número de elementos en el contenedor (en el módulo OrdVc.pas se sigue esta estrategia). Al usar la abstracción de iteración se hace posible encargar a un experto programador para que implemente el iterador de la forma más eficiente posible, y luego este trabajo se puede reutilizar una y otra vez fácilmente.

      A veces conviene que el iterador no viole el Rep del contenedor, lo que se logra si en la implementación del iterador no se usan directamente los campos del contenedor, sino sólo sus operaciones. En este caso, el mismo iterador serviría para cualquier implementación del contenedor, lo que facilita su uso. En general, es mejor que las conexiones entre módulos sean lo más delgadas posible, pues de esa manera se evita que cambios en un módulo afecten a otros módulos: siempre es saludable disminuir la cohesión de los módulos de un programa.

      Como convención, el nombre del tipo del iterador siempre comienza con la letra "I". Los nombres para los tipos que son punteros comienzan con "P" (PCpos, PElem), y los de los demás tipos con "T" (TObj; TList).

      Algunas veces al programador le queda cómodo incluirle al iterador una nueva operación Behave(order) que sirve para definir el orden que usará el iterador. Por ejemplo, el iterador OneStep.pas para la lista podría tener los dos comportamientos "Forward" y "Backward" que sirven para que el iterador avance paso a paso por la lista, de adelante hacia atrás o de atrás hacia adelante.

3.6 Herencia

      Por medio de la Herencia el programador puede extender un tipo de datos, agregándole campos nuevos al final. El efecto de la herencia puede simularse en la mayoría de los lenguajes tradicionales agregando un nuevo campo a un tipo, pero el resultado es un programa menos elegante, o conciso. Como la cualidad principal de la Programación Orientada a los Objetos es la herencia, si un lenguaje incorpora las facilidades sintácticas para hacer herencia de tipos entonces sin temor se puede afirmar que el lenguaje soporta OOP [Str-88a].

TYPE
  Punto_T = RECORD
   x,y : INTEGER
  END;

  Circulo_T = RECORD
    p : Punto_T;
    r : REAL;
  END;

PROCEDURE Traslade(VAR p: Punto_T);
VAR
  p : Punto_T;
  c : Circulo_T;
BEGIN
  p.x   := ...
  c.p.y := ...    { .p se ve feo }
  c.p.r := ...
  Traslade(p);
  Traslade(c.p);  { ¡otra vez .p! }
END;

      En la Figura 3.17 está el código que debe usarse para definir el tipo Circulo_T en términos del tipo Punto_T. Como un círculo es un punto, en el registro Circulo_T se ha agregado un campo, llamado "p", de tipo Punto_T. El procedimiento Traslade() se puede aplicar tanto al punto "p" como al círculo "c", pero en el segundo caso es necesario mencionar explícitamente el campo ".p" de la variable "c" para poder usarla como argumento de Traslade(): Traslade(c.p). Como hay que agregar un campo a cada círculo para hacer referencia a las variables del punto, el programa se ve poco elegante, por lo menos si se le compara con el programa equivalente que sí usa herencia.

TYPE                    TYPE
  TPunto = OBJECT         TCirculo = OBJECT(TPunto)
   x,y : INTEGER             r : REAL;               
  END;                    END;

PROCEDURE Traslade(VAR p: TPunto);
  VAR
    p : TPunto;
    c : TCirculo;
  BEGIN
    p.x := ...
    c.y := ...     { Uso directo de }
    c.r := ...     { los campos.   }
    Traslade(p);   { ¡¡ Bonito !!   }
    Traslade(c);   { ¡¡ SIN .p !!   }
  END;

      En la Figura 3.18 se muestra cómo definir el tipo TCirculo sin definir el campo ".p", pues al principio de cualquier instancia de tipo TCirculo están todos los campos del tipo TPunto. A TPunto se le llama el tipo base, y a todos los tipos que extienden el tipo base se les llama tipos derivados. Como el tipo extendido siempre tiene como prefijo al tipo base, cualquier rutina que utiliza una variable del tipo base puede también aplicarse al tipo extendido. Por eso en la Figura 3.18, el procedimiento Traslade() se puede aplicar a las variables "p" y "c" indistintamente, pues al ser "c" una variable de tipo TCirculo, necesariamente al principio contiene una variable de tipo TPunto, sobre la que el procedimiento Traslade() puede operar directamente.

      La propaganda sobre la gran capacidad de reutilización que tiene OOP precisamente se sustenta en la posibilidad de usar una función sobre un tipo extendido. Esto realmente no es nada nuevo, como puede verse en la Figura 3.17, en la que basta incluir un campo en un registro para obtener el mismo efecto que se logra por medio de la herencia. De todas maneras, la expresividad que se adquiere al agregar esta simple construcción sintáctica a cualquier lenguaje, compensa con creces cualquier dificultad que produzca tanto en el lenguaje como en sus compiladores. Por eso todos los lenguajes poco a poco han incorporado la herencia (inclusive Cobol y Clipper).

      El uso más importante de la herencia se encuentra en las bibliotecas para manejar la interfaz de los programas. Dado que ahora todos los programas deben presentar una interfaz gráfica, o por lo menos orientada al uso de ratón y ventanas, no es difícil entender que todos los programadores se han visto obligados a usar herencia en sus programas. De los contrario les resultaría muy difícil escribir programas para las plataformas que se usan actualmente: Windows, OS/2 Warp y X-Windows.

      La herencia es azúcar sintáctico que refuerza las facilidades de un lenguaje para expresar abstracciones de datos. La herencia es una facilidad sintáctica que complementa la abstracción de datos y, por ende, también complementa la abstracción de iteración.

3.7 Parametrización

      A cada tipo de abstracción le corresponde una técnica diferente de reutilización de código. En el caso de la abstracción de procedimientos, la reutilización de código se logra implementando bibliotecas de programas; para las abstracciones de datos y de iteración la reutilización se logra por medio de la parametrización y el polimorfismo.

      En la discusión que sigue, a los iteradores no se les menciona explícitamente porque los iteradores son datos, por lo que todo lo que se diga para los ADT's se aplica también a los iteradores: todo lo que funciona para los ADT's también funciona en iteradores.

      La Parametrización es la propiedad de un módulo, o de una construcción sintáctica del lenguaje, para utilizar datos de varios tipos. Es un mecanismo muy útil porque permite aplicar el mismo algoritmo a tipos de datos diferentes; es una facilidad que permite separar los algoritmos de los tipos de datos, aumentando de esta manera la modularidad de los programas y minimizando la duplicación de código. En Ada a la parametrización se la llama Genericidad y se logra mediante el uso de Paquetes Genéricos (generic packages), y en C++ mediante el uso de Plantillas (templates).

      Pascal tiene pocas facilidades para parametrización: primero, los procedimientos Read() y Write() de la biblioteca Pascal estándar pueden trabajar con argumentos de varios tipos. Segundo, al declarar un arreglo, el programador escoge el tipo de elemento agregándolo como un argumento al final de la declaración:

   TYPE
     TAinteger = ARRAY [15..50] OF INTEGER;
     TAreal    = ARRAY [15..50] OF REAL;

En esta declaración de tipos, la construcción sintáctica ARRAY[] tiene dos tipos de parámetros. Los primeros parámetros son los números 15 y 50, que son las constantes que definen el tamaño del arreglo declarado. Al parametrizar, el compilador necesita saber el valor de estas constantes para calcular el tamaño del arreglo. La otra clase de parámetro es el tipo INTEGER (y REAL), que define el tipo de los datos que estarán almacenados en el arreglo. Por último, los operadores aritméticos y de comparación de Pascal son parametrizables, pues el compilador usa algoritmos diferentes para realizar estas operaciones dependiendo del tipo de datos al que se aplica el operador.

      Estos parámetros difieren de los que aparecen en un programa como argumentos en las invocaciones a los procedimientos porque no son instancias de datos, -variables-, sino que son entes, -tipos y constantes-, que se usan en tiempo de compilación para producir el programa objeto. Las declaraciones de arreglos en Pascal son parametrizables, y los parámetros que se usan para definir arreglos son tipos de datos y constantes.

      Como los procedimientos también tienen parámetros, el término "parametrización" también tiene otros significados. Por ejemplo, en algunos textos se llama "Parametrización de procedimientos" al acto de invocar un procedimiento en un programa, incluyendo los argumentos que deben ser variables [LG-86]. Cuando se habla de parametrización, en general se sobreentiende que los parámetros son tipos de datos o constantes.

      Al usar parametrización, el programador puede escribir algoritmos que no dependan del tipo de los datos manipulados, lo que evita duplicar código fuente. En el contexto de los ADT's contenedores, la parametrización es el mecanismo que permite que el contenedor sea independiente de los objetos que contiene, pues con un solo módulo es posible obtener contenedores para elementos de tipos diferentes. Con base en el mismo código fuente parametrizable es posible obtener un vector de enteros, de personas, o de listas de valores booleanos. La parametrización sirve para definir un nuevo ADT contenedor en términos del ADT contenido; este último tipo de datos es el parámetro de la definición. Si Pascal fuera capaz de parametrizar contenedores directamente, sería posible escribir declaraciones como la siguiente, que define las listas de números enteros y reales "TLint" y "TLreal":

   VAR
     TLint  = TList <INTEGER>;
     TLreal = TList <REAL>;

      Pese a que no hay duplicación de código fuente cuando se usa parametrización, con frecuencia el resultado de compilar un algoritmo parametrizable produce código objeto diferente para cada uno de los algoritmos parametrizados para cada tipo de datos diferente (a veces esto se puede evitar). En el caso de las operaciones de un ADT contenedor parametrizable, algunas implementaciones logran que varias instancias del contenedor puedan compartir el código que implementa cada operación, aun si han sido parametrizados para ADT's elementales diferentes. Sin embargo, lo usual es que el compilador genere una copia completa de toda la implementación del contenedor para cada uno de los tipos parametrizados (de aquí viene el nombre "plantilla" que se usa para denotar a la capacidad de parametrización de C++).

      Es fácil compartir el código objeto si lo que cada instancia del contenedor contiene es una referencia, -puntero-, al elemento almacenado, pues lo usual es que todos los punteros tengan el mismo tamaño, independientemente del tamaño del objeto a que apuntan. Este es el enfoque que se ha usado para CLU [LG-86] o para Napier88 [MDC-91], y para los lenguajes que permiten polimorfismo uniforme, en que se usa la "Semántica de referencia". En esos lenguajes, en casi todos los casos, los objetos son punteros al lugar en la memoria en que su valor está almacenado. Cuando el contenedor almacena los objetos, y no referencias a ellos, compartir el código de las operaciones es más difícil porque los objetos diferentes tienen tamaños diferentes y requieren ser manipulados usando operaciones diferentes.

      Si se usa semántica de referencia para implementar la parametrización, no hace falta duplicar el código objeto de cada algoritmo, pero a cambio el acceso a cada dato es más lento, pues hay que derreferenciar un puntero para llegar a su valor. Además, cada dato ocupa más espacio de memoria, pues al usado para almacenar su valor hay que agregarle el que ocupa el puntero que lo referencia. Por eso en este trabajo se hacen esfuerzos por implementar la parametrización sin recurrir a la semántica de referencia.

 TYPE
   TLTreal   = TList< TTree< REAL > >; 
   TLinteger = TList< INTEGER >;

      Para el programador es muy importante que el lenguaje le permita implementar ADT's contenedores que sean parametrizables, pues de esta manera puede reutilizarse el mismo contenedor para muchos tipos de datos diferentes. Por eso algunos lenguajes (C++, Ada, Eiffel, CLU, Napier88, ML, etc.) incluyen declaraciones paramétricas análogas a las de la Figura 3.19. En el primer caso se define el tipo TLTreal, que es una lista cuyos elementos son árboles, en donde los elementos del árbol son números reales. En el segundo se define al tipo TLinteger como una lista cuyos elementos son números enteros.

TYPE
  <TSort> = ARRAY[Low<>..High<>] OF <TElem>;

PROCEDURE Sort_<TSort>(    { ADH }
  {?} VAR A :  <TSort>     { Arreglo a ordenar }
);
{ RESULTADO
  Ordena el vector "A" con el método de la burbuja. }
VAR
  j,k     : INTEGER;
  temp    : <TElem>;
  interch : BOOLEAN;
BEGIN { Sort_<TSort> }
  k := 1;
  REPEAT
    interch := FALSE;
    FOR j := Low<A> TO High<A> - k DO BEGIN

      IF (A[j+1] <= A[j]) THEN BEGIN
        interch := TRUE;

        temp   := A[j+1]; { los intercambia: }
        A[j+1] := A[j];
        A[j]   := temp;   { A[j] <==> A[j+1] }

      END;
    END;
    INC(k);
  UNTIL NOT interch;
END;  { Sort_<TSort> }

      El ejemplo clásico de parametrización de procedimientos es la rutina Sort(), que ordena un vector independientemente del tipo de datos que contenga. En la Figura 3.20 está una versión simplificada de Sort(), expresada como una plantilla escrita en pseudo-Pascal. Esta implementación parametrizable del procedimiento Sort() puede ordenar cualquier arreglo, independientemente de las cualidades del vector (tipo de elemento contenido, dimensión, cantidad de elementos, algoritmo para comparar los elementos). Los parámetros que deben ser definidos por el programador para usar la función Sort() se encuentran encerrados entre paréntesis angulares: <TSort>, <TElem>, Low<A> y High<A>. Estos dos últimos sirven para definir el rango del vector. Además, el operador "<=" también es un parámetro, pues es el que se usa para comparar cualesquiera dos elementos del vector.

TYPE
  Tarray50REAL = ARRAY[5..50] OF INTEGER;

PROCEDURE Sort_Tarray50REAL(    { ADH }
  {?} VAR A :  Tarray50REAL     { Arreglo a ordenar }
);
{ RESULTADO
  Ordena el vector "A" con el método de la burbuja. }
VAR
  j,k     : INTEGER;
  temp    : INTEGER;
  interch : BOOLEAN;
BEGIN { Sort_<TSort> }
  k := 1;
  REPEAT
    interch := FALSE;
    FOR j := 5 TO 50 - k DO BEGIN
      IF (A[j+1] <= A[j]) THEN BEGIN
        interch := TRUE;

        temp   := A[j+1]; { los intercambia: }
        A[j+1] := A[j];
        A[j]   := temp;   { A[j] <==> A[j+1] }
      END;
    END;
    INC(k);
  UNTIL NOT interch;
END;  { Sort_<TSort> }

      Cuando el lenguaje de programación no soporta la parametrización, como ocurre con Pascal, si el programador tiene acceso al código fuente de los programas, entonces puede simularla duplicando código y usando el editor de textos; a esto se le llama polimorfismo de editor de textos. Por ejemplo, para obtener a partir de la plantilla de la Figura 3.20 una función que ordene un arreglo de números enteros, el programador debe copiar el código fuente del procedimiento Sort_<TSort>() de la Figura 3.21, y luego realizar las siguientes sustituciones usando el editor de texto:

1.	Sustituya	<TSort>	por	Tarray50REAL
2.	Sustituya	Low<A>	por	5
3.	Sustituya	High<A>	por	50
4.	Sustituya	<TElem>	por	INTEGER

      Se llama Instanciación al proceso de especializar una plantilla de código parametrizable a un tipo. Para instanciar basta copiar el código de la plantilla y sustituirle las hileras por los nombres adecuados de las constantes y los tipos de datos. En el caso de los tipos, la instanciación ocurre cuando se declara la variable, y se obtiene así una instancia (en [Wil-96] se incluye una explicación muy elegante de este concepto). El término "parametrización" nace de instanciar de esta forma los tipos, que son parámetros en las plantillas de código.

      El resultado de instanciar la rutina Sort() de la Figura 3.20 se muestra en la Figura 3.21, en donde aparece la función llamada Sort_Tarray50REAL(). Como Pascal es un lenguaje que no tiene soporte directo para la parametrización, es necesario distinguir este procedimiento Sort() de otros agregándole al nombre de la rutina el nombre de los tipos instanciados (esto es lo que en C++ se conoce como la "firma" de la función).

      Si se compara el código de la Figura 3.20, con el de la Figura 3.21, se pueden identificar los siguientes problemas, que son graves limitantes cuando se parametrizan manualmente programas:

1. Es necesario que el módulo cliente del algoritmo que será parametrizado tenga acceso al código fuente de los programas. Muchas veces este es un grave inconveniente, pues muchos programadores desean proteger su esfuerzo intelectual cobrando una suma de dinero adicional cuando entregan los fuentes de sus algoritmos. Esta limitación económica tiene un severo impacto en la utilidad de usar plantillas como la de la Figura 3.20.
2. Como la plantilla de la Figura 3.20 no es código Pascal válido, al programador le costará mucho más depurar sus algoritmos. La alternativa es hacer más complicado el compilador o agregarle un preprocesador. Por eso al lenguaje C++ le incorporaron plantillas, pues de lo contrario el programador quedaba obligado a depurar complicadísimos macros del preprocesador de C [Str-89].
3. Al instanciar la plantilla, el programador debe ser muy cuidadoso al escoger los nombres de los tipos, para evitar duplicarlos, y a la vez debe usar identificadores significativos. En este caso, el identificador "Tarray50REAL" se obtuvo al seguir una convención de programación informal, que consiste simplemente en concatenar los nombres de los tipos. Esta responsabilidad del programador debería ser asumida por el compilador, para evitar que errores de programación se escabullan dentro del programa.
4. El identificador Sort_Tarray50REAL() es poco elegante, pues incluye información que necesita el compilador pero que es irrelevante para el programador, lo que desmejora el programa y lo hace más difícil de mantener; esto está directamente en contra de los objetivos de la modularización.
5. El obligar al uso de estas intrincadas convenciones para nombrar los identificadores limita la flexibilidad que tiene el programador al usar depuradores simbólicos, lo que por ende reduce la utilidad de este tipo de herramienta.
6. Como para instanciar el procedimiento Sort() de la Figura 3.20 hay que duplicar el código, el programa objeto resultante es mucho más grande de lo requerido. Aunque no siempre es posible evitar esta duplicación de código, lo cómodo para el programador es que el compilador se encargue de eliminarla cuando sea factible hacerlo.
7. La implementación de la Figura 3.20 asume que es posible invocar la operación binaria "<=" para comparar dos instancias del tipo de datos <TElem>. En el caso de Pascal, esto impide que Sort() sea utilizado para tipos de datos que no son los tipos escalares predefinidos de Pascal, pues el operador "<=" se puede usar sólo en tipos escalares. Por eso al adoptar la parametrización también es necesario permitir la sobrecarga ("overload") de los operadores del lenguaje, lo que contribuye a aumentar su complejidad.
         Este problema ha sido resuelto en el caso de los lenguajes CLU y C++ modificando el lenguaje, para que el resultado de compilar la expresión "a <= b" sea la invocación a la función LessEqual(a,b). Al modificar el lenguaje de programación es posible evitar algunos de los escollos que surgen al dotarlo de parametrización.

      Si a Pascal se le aumenta con construcciones parametrizables, el programador podría declarar listas como en la Figura 3.19, en que se definen los dos nuevos tipos "TLTreal" y "TLinteger" como instanciaciones de "TList". Esta es la forma cómoda de reutilizar los contenedores Lista y Árbol, precisamente lo que se persigue lograr en esta investigación, pero sin modificar el compilador. El efecto que la declaración de "TLinteger" debería tener es que, al crear este nuevo tipo, o sea, al instanciarlo, el compilador debería usar como plantilla la implementación de "TList", pero sustituyendo el tipo "TElem", que aparece en las operaciones que manipulan el elemento contenido en la lista, por el tipo "INTEGER".

               ANTES DE INSTANCIAR

PROCEDURE Insert(          { EXPORT }     { ADH }
  {?} VAR C : TList;       { SELF }
  {+}     p : PLpos;       { adónde insertar }
  {?} VAR o : <TElem>      { elemento a insertar }
);
          RESULTADO DE LA INSTANCIACION

PROCEDURE Insert(          { EXPORT }     { ADH }
  {?} VAR C : TList        { SELF }
  {+}     p : PLpos;       { adónde insertar }
  {?} VAR o : INTEGER      { elemento a insertar }
);

      En la Figura 3.22 aparece primero el encabezado de la operación List.Insert() según se muestra en la Figura 5.6. Esta operación sirve para ilustrar cuál es el resultado de instanciar el parámetro TList; o sea, ahí se muestra el encabezado que resulta al sustituir al tipo "TElem" por el tipo "INTEGER" en la definición de la operación List.Insert(). En este caso "INTEGER" es el tipo que se usa como parámetro para crear el nuevo tipo "TLinteger" (lista de enteros).

      Para parametrizar, el compilador debe ser capaz de instanciar módulos usando tres categorías de parámetros [DeO-94]:

• Constantes: El valor de las constantes se usa para determinar el tamaño de los objetos y así saber cuánta memoria asignar a cada variable. Por ejemplo, en el caso de los arreglos las constantes permiten determinar el número de elementos que el arreglo debe contener.
• Tipos de datos: Le sirven al compilador para crear varias versiones diferentes de los tipos parametrizados, como en el caso del tipo TList<REAL>, y para crear varias versiones de cada procedimiento u operación parametrizable, como TList<REAL>.Insert().
• Algoritmos: Permiten modificar el comportamiento del módulo parametrizado usando una rutina de proceso diferente. Por ejemplo, en el caso del procedimiento paramétrico Sort() de la Figura 3.20, si al instanciar se usa la operación ">=" (mayor que) para comparar elementos, en lugar de usar el algoritmo "<=", el orden que resulte al invocar el Sort() será descendente, y no ascendente.

      La parametrización es difícil de implementar y apoyar porque requiere de una gran inteligencia por parte del sistema de compilación de programas. Los problemas que hay que resolver para lograr una eficiente parametrización se dividen en las siguientes categorías:

• Instanciación: Para parametrizar, el compilador debe ser capaz de crear un nuevo tipo, así como todas sus operaciones. Lo usual es que la instanciación se haga sólo para los tipos que son objetos, que encapsulan sus operaciones como métodos.
        Uno de los problemas que hay que resolver al definir la semántica de un lenguaje que soporta parametrización es determinar si los tipos creados al instanciar un objeto son diferentes, iguales o parecidos. Por ejemplo, al instanciar el código de la lista de la Figura 3.19 es necesario definir si un procedimiento que acepta una variable de tipo "TList" debe aceptar indistintamente variables de tipo "TLTreal" o "TLinteger", o si, por el contrario, estos dos tipos son totalmente diferentes. Más aún, podría decirse que estos tipos son "parecidos" en el sentido de que, si en un procedimiento no se usa ninguna de las operaciones que manipulan al elemento de la lista "TElem", el compilador debe entonces permitir usar cualquiera de los dos tipos "TLTreal" o "TLinteger", pero si, por el contrario, se usa el elemento, el compilador debería emitir un error de compilación.
        Otro problema surge cuando, como resultado de la parametrización, se hace necesario definir muchos tipos, como ocurre cuando se usa meta-programación (programación con plantillas) en C++ [Pes-97].
        La instanciación automática es muy agradable para el programador de ADT's contenedores, pero desafortunadamente hace más complicado el lenguaje (¡y que lo digan quienes esperaron varios años antes de poder usar un compilador de Ada!).
• Compilación: El compilador debe ser capaz de manejar varios tipos diferentes que son realmente iguales. En particular, debe evitar duplicar el código de cada una de las rutinas que corresponden a las operaciones instanciadas para cada tipo.
        En el caso de la operación List.Insert() de la Figura 3.22, el compilador debe ser capaz de lograr que el código para la versión de List.Insert() que corresponde al tipo "TLTreal" sea el mismo que se use para el tipo "TLinteger". De lo contrario, el programa objeto que resulta sería muy grande, pues incluiría una copia de la versión de cada operación para cada tipo que se haya instanciado. Algunos compiladores de Ada y C++ tratan de eliminar código redundante, pero en general no son efectivos en esta tarea, por lo que los programas que usan la parametrización en general resultan ser bastante "gordos".
• Ligamiento: Usualmente en la mayor parte de los lenguajes no ha quedado especificada con precisión cuál es la relación entre las unidades de compilación y el ligador de eslabonamiento, por lo que, al manejar diferentes instanciaciones del mismo tipo, se pueden producir problemas de ligamiento. Una forma de resolver estos problemas es usar mecanismos engorrosos, que fuerzan al máximo el ligador de eslabonamiento, para distinguir entre las diferentes versiones de la misma rutina [Str-88c].
• Depuración: El uso de parametrización complica la construcción de herramientas de programación, las que deben incorporar las reglas para construir nuevos tipos o tipos derivados en el proceso de instanciación. En particular, esto atrasa la producción de depuradores simbólicos adecuados, lo que limita la efectividad del programador quien ve su productividad reducida cuando usa la parametrización.

      Aunque tanto Ada como C++ soportan parametrización, en general lo que el compilador hace es duplicar código a espaldas del programador, para evitarle el trabajo de hacerlo. El enfoque escogido en C++ es más engorroso, pues para parametrizar un módulo es necesario exponer su código fuente, lo que no ocurre tan abiertamente en Ada, tal vez porque C++ tiene que cargar con las complicaciones que el preprocesador de C produce cuando se instancian plantillas [All-96]. La parametrización es muy difícil de implementar eficientemente, y en muchos casos obliga a complicar el lenguaje de programación, por lo que es fácil encontrar razones para omitir de un lenguaje de programación esta construcción sintáctica. Esta dificultad es precisamente la que justifica este trabajo de investigación.

      Aunque la práctica muestra que Ada y C++ tienen suficiente expresividad como para cubrir la mayor parte de los usos más frecuentes de la parametrización, en teoría no todas las formas de polimorfismo pueden ser implementadas usando parametrización, pues con parametrización apenas alcanza para tratar a los procedimientos como objetos de segundo orden [Hos-90], sin llegar a la generalidad del polimorfismo uniforme.

      Debido a lo difícil que resulta incluir la parametrización en un lenguaje, la buena práctica de la Ingeniería indica que debe estudiarse cuáles son las aplicaciones más usuales de la parametrización para ver si es posible reducir un poco los requerimientos (del lenguaje) para obtener una solución parcial que cubra la mayor parte de las aplicaciones (de la parametrización). Las Aplicaciones más importantes de la parametrización son las siguientes:

• Bibliotecas de entrada / salida: Todos los lenguajes deben incluir construcciones sintácticas para que los programas obtengan valores del entorno, para almacenarlos en variables, y también para que el programa pueda devolver al entorno los resultados computados. Como la entrada / salida es esencial para cualquier programa, es muy importante que las rutinas de entrada / salida se puedan usar para cualquier tipo de datos, aun para aquellos definidos por el programador.
• Expresiones de constantes: Para evitarle al programador el tedio de calcular el valor de una expresión cuyos términos son todos constantes, el compilador debe permitir usar expresiones constantes en la definición de objetos.
• Arreglos de dimensión variable: Muchos lenguajes permiten usar arreglos como argumentos de procedimientos sin obligar a que el número de elementos en el arreglo sea siempre el mismo. En programas en que hay que hacer muchos cálculos numéricos también es importante que las matrices tengan dimensiones variables.
• Procedimiento Sort() genérico: En muchas ocasiones el programador necesita ordenar un arreglo de elementos. Para construir el algoritmo de ordenamiento no es necesario saber cuál es el tipo de los elementos, y mucho esfuerzo se ha concentrado en encontrar una forma de reutilizar el mismo algoritmo de ordenamiento para diferentes tipos.
• Parametrización de contenedores: La otra aplicación importante de la parametrización es la implementación de contenedores parametrizables, principalmente de los arreglos y sus derivados (como la matriz), la lista, el árbol y el grafo. Esta aplicación es la que justifica este estudio.

      Después de identificar las principales aplicaciones de la parametrización es saludable conocer cómo se le da soporte a cada una de estas aplicaciones en los lenguajes modernos:

• Bibliotecas de entrada / salida: En muchos lenguajes, como en Pascal, al definir el lenguaje se le han incluido verbos especiales para realizar entrada / salida para múltiples tipos de datos, o por lo menos para los tipos básicos: booleano, entero, punto flotante e hilera. Para este fin Pascal cuenta con los procedimientos parametrizables Read() y Write().
        En otros lenguajes, como C++, lo que se hace es usar la sobrecarga de procedimientos y operadores para obtener el mismo efecto. En el caso de Ada, la biblioteca estándar del lenguaje incluye varios paquetes genéricos que el compilador es capaz de instanciar automáticamente para obtener los procedimientos específicos para realizar la entrada / salida de diferentes tipos de datos.
• Expresiones de constantes: Como es relativamente sencillo parametrizar constantes, la mayor parte de los lenguajes actuales permite usar expresiones constantes, aunque es notable que Pascal originalmente no las permitió. Como remedio, Turbo Pascal incluye la construcción sintáctica CONST. Existen construcciones sintácticas equivalentes para C, C++ y Ada.
• Arreglos de dimensión variable: Fortran es el lenguaje que instituyó esta forma de programación, pues permite que las dimensiones de los arreglos y matrices cambien de una invocación a otra del mismo procedimiento, aunque a cambio se pierde la verificación fuerte de tipos. Esta reconfiguración dinámica es posible porque al definir el lenguaje también se define cómo se almacenan los elementos de los arreglos y matrices en memoria (en Fortran las matrices se almacenan por columnas, mientras que en casi todos los demás lenguajes se almacena por filas). En la Figura 3.23 se muestra cómo es posible definir matrices de tamaño variable en Fortran.

  SUBROUTINE Matrix(A,N,M)         REAL A(N, M)

  Figura 3.23: Una matriz Fortran parametrizable       Cabe destacar aquí que aunque una matriz Fortran puede tener un tamaño variable, ese tamaño es fijo y no puede variar dentro de cada invocación al subprograma en que está definida la matriz como argumento. Otros lenguajes permiten que los tamaños de los arreglos cambien dentro de una invocación a un subprograma, caso en el cual al arreglo se le llama Arreglo dinámico.

  FUNCTION Max_Array( { ADH } {?} VAR A : ARRAY OF REAL ) {>>>>>>>>}: REAL; { RESULTADO Retorna el valor más grande del arreglo. } VAR i,mx : INTEGER; BEGIN { Max_Array } mx := 0; FOR i := 0 TO HIGH(A) DO BEGIN IF A[mx] < A[i] THEN BEGIN mx := i; END; END; Max_Array := A[mx]; END; { Max_Array }

  Figura 3.24: Max_Array()       Tanto Modula-2 como Turbo Pascal v6.0 permiten una parametrización limitada a arreglos unidimensionales. Para esto el programador debe definir parámetros de tipo ARRAY, cuyo primer índice es siempre cero; la dimensión del arreglo se puede obtener invocando la función de biblioteca HIGH(), como se muestra en la Figura 3.24. Es relativamente simple modificar el compilador para que soporte arreglos de dimensión variable, llamados Arreglos abiertos, pues basta agregar un argumento escondido a cada invocación que use el arreglo, en el que se indique la cantidad de elementos del arreglo.

  CONST N = 25; M = (N * 3) + 4; TYPE TarrayA = ARRAY[-3*N..5, -M..M, -N..0] OF CHAR; TarrayB = ARRAY[N DIV 5..M * N DIV 15] OF BYTE;

  Figura 3.25: Uso de expresiones constantes       Una extensión a la facilidad de definición de arreglos de tamaño variable es permitirle al programador usar expresiones constantes para calcular el tamaño de las matrices, como se muestra en el código Turbo Pascal de la Figura 3.25.
• Procedimiento Sort() genérico: La forma usual de implementar un Sort() genérico es pasarle al procedimiento un puntero al arreglo y un puntero a la subrutina que debe usarse para comparar los elementos del arreglo (lo usual es intercambiar los elementos del arreglo copiándolos bit a bit, aunque esto no funciona para muchos objetos).

  void qsort( void *base, size_t nelem, size_t width, int (*fcmp) (const void *, const void *) );

  PROCEDURE QSort( VAR A : POINTER; { Puntero al arreglo } N : WORD; { Dimensión de "A" } w : WORD; { Ancho de cada elemento } FComp: POINTER { Función para comparar } );

  Figura 3.26: qsort() polimórfico       En la Figura 3.26 se muestra el encabezado similar al de la función de ordenamiento qsort() de la biblioteca estándar C. En esa misma figura está el encabezado para la misma función en Turbo Pascal. El problema de esta solución es que obliga al programador a prescindir totalmente de la verificación fuerte de tipos; por eso en la especificación de qsort() generalmente se le aconseja al programador "ser muy cuidadoso", porque para parametrizar el procedimiento es necesario anular la verificación fuerte de tipos que provee el compilador. (En [BM-93] hay una buena discusión de cómo construir el mejor qsort()).
• Parametrización de contenedores: Los métodos para parametrizar contenedores se discuten en los siguientes capítulos. De todas formas, es importante mencionar que al encontrar la forma de parametrizar contenedores, sin modificar el lenguaje, se logra cubrir todas las aplicaciones importantes de la parametrización, lo que quiere decir que se pueden obtener sus beneficios pero sin pagar el alto precio en complejidad generalmente asociada al uso de esta forma de abstracción.

      Como se verá en los capítulos posteriores, la técnica de parametrización de contenedores que se desarrolla en este trabajo busca evitar la duplicación de código objeto que usualmente resulta cuando un compilador instancia un tipo de datos pues, para parametrizar, lo que generalmente hacen los compiladores es duplicar el código objeto a espaldas del programador.

      En el contexto del lenguaje Eiffel se han dado discusiones contraponiendo la parametrización a la herencia [Mey-86], buscando mostrar que "la herencia anula la necesidad de usar parametrización" y que "la parametrización anula la necesidad de usar herencia". Por supuesto, este conflicto en realidad no existe, pues ambas formas de abstracción son complementarias, y es productivo que las dos formas de ver las cosas persistan: así aumenta el arsenal de herramientas disponible para resolver problemas.

      Si un lenguaje ofrece parametrización, con el correr del tiempo los programadores encontrarán formas de usar esta poderosa construcción sintáctica (también encontrarán maneras de abusar de ella, pero eso es harina de otro costal). Saber cómo se puede implementar la parametrización les puede ayudar a escribir mejores programas. De todas maneras les es muy útil conocer cómo implementar parametrización, aun si el lenguaje que usan no la soporta, pues entonces pueden simularla para obtener los réditos que la reutilización de componentes de programación rinde.

3.8 Polimorfismo

      De acuerdo a [MDC-91] el "Polimorfismo" en un lenguaje de programación "es la habilidad de escribir programas que son independientes de la forma de los objetos que manipulan". Es un concepto mucho más amplio que la unión de la parametrización con la herencia, pues el polimorfismo hace al lenguaje mucho más expresivo. Por eso en [CW-85] se le llama "Polimorfismo de inclusión" a la herencia y en [MDC-91] se afirma que la parametrización que ofrecen tanto Ada como C++ apenas es un método para implementar el polimorfismo, que ellos llaman "Polimorfismo textual" (pg 344). En estos dos lenguajes, la parametrización es una forma restringida del "Polimorfismo paramétrico" de [CW-85] (pg 475).

      Una muestra de que el polimorfismo es un concepto mucho más amplio que la parametrización, es el del lenguaje ML [Mil-84], o el de Miranda [Tur-86], que cuentan con "Polimorfismo uniforme", que garantiza que todos los tipos siempre compartan la misma implementación de cualquier algoritmo polimórfico. Esto se puede garantizar sólo en muy pocas ocasiones si se usan los paquetes genéricos de Ada, o las plantillas de C++, pues en estos lenguajes lo usual es que, al instanciar un procedimiento polimórfico, el compilador genere una copia del código para cada tipo (de aquí el nombre despectivo de polimorfismo de editor de textos para la genericidad [MDC-91], pg 369).

      Cuando se habla de polimorfismo surgen conceptos como la "Inferencia de tipos", que es la habilidad de un compilador de inferir el tipo de una expresión polimórfica analizando estáticamente (en tiempo de compilación) su uso. En el lenguaje Napier88 [MDC-91], los procedimientos son "Objetos de Primera Clase", pues tienen tipo (una excelente discusión de estos conceptos, y bastante concisa por cierto, se encuentra en [Hos-90]). Si el lenguaje permite definir una variable cuyo contenido es un procedimiento, entonces es interesante grabarla en memoria secundaria (disco), para ser recuperada e invocada en una corrida posterior del programa. Esta cualidad aumenta mucho la expresividad del lenguaje y, por supuesto, complica enormemente el sistema de compilación, pues cuando los módulos pueden retornar tipos diferentes en cada invocación, algunos de los cuales son procedimientos, los posibles valores por retornar crecen multiplicativamente [MDC-91].

      Tal vez la razón principal por la que los lenguajes más populares no incorporan las formas más poderosas de polimorfismo, es el costo que se paga en tiempo de ejecución por esa gran flexibilidad, la cual en pocas ocasiones sería utilizada por el programador promedio, quien seguramente tendría gran dificultad para comprender qué hacer con tanto poder expresivo. Independientemente de cuál sea la causa de este hecho, lo cierto es que las formas más abstractas de polimorfismo se implementan usando punteros, lo que aumenta tanto el tamaño de las variables como el tiempo de ejecución de los programas. Esto es inaceptable para la mayoría de los programadores C++, o para quienes necesitan producir programas eficientes (que es el auditorio al que va dirigido este trabajo).

      La mayor parte de los programas están escritos sin usar lenguajes en que los procedimientos son objetos de más alto orden; además, como queda demostrado en [Hos-90], es posible simular burdamente funciones de segundo orden usando astutamente el polimorfismo textual. En otras palabras (y torciendo un poco la lógica), podemos decir que el uso de plantillas sólo alcanza para implementar funciones de segundo orden, pues para funciones de más alto orden ya hace falta un apoyo más grande del sistema de compilación. Otra manera de ver las cosas es la siguiente: ¿para qué aspirar a usar lenguajes de altísimo nivel, si con el polimorfismo de editor de textos de Ada y C++ basta para usar funciones de segundo orden?

      Aunque en Turbo Pascal el programador puede declarar variables cuyo tipo es procedimiento o función, esto no quiere decir que Pascal tiene funciones de alto orden. Más bien el programador sabe que esas variables son punteros por medio de los que puede invocar a una rutina, por lo que ni siquiera le pasa por la mente almacenar variables de éstas en almacenamiento secundario para usar su valor en una corrida posterior del programa. El mundo del programador Pascal, o C++, está muy ligado a la implementación del compilador, y no tiene derecho a soñar con las cualidades atractivas de los lenguajes de programación más alto nivel como Napier88, Miranda o ML.

      Por lo anterior, en el contexto de un lenguaje como Pascal, de alta eficiencia aunque reducida capacidad semántica, cuando se habla de polimorfismo es porque internamente (a nivel de implementación) se usan referencias a objetos en lugar de los objetos en sí. Una forma simple de entender el polimorfismo es pensar que "polimorfismo" significa "uso de punteros". O sea que, cuando se usa polimorfismo, no se manipula al objeto, sino que se usa una referencia al objeto, que es un puntero. Por eso la parametrización que se discute en este trabajo sigue más bien las líneas de [DeO-94], y no se busca llegar al polimorfismo uniforme de otros lenguajes: más bien se trata de lograr la parametrización emulando el polimorfismo de editor de textos, como en [Gru-86]. Con frecuencia se confunde la parametrización con el polimorfismo, pues la idea de usar punteros a funciones como vehículo para implementar la parametrización no es nueva. Por ejemplo, ya en 1986 se hablaba de cómo hacerlo [CI-86], aunque la técnica usada es bastante restrictiva [Gol-86].

      En un plano más abstracto, el polimorfismo es un concepto muy similar a la parametrización. Como se sobreentiende que al usar polimorfismo internamente el compilador recurre a punteros y referencias [MDC-91], que es lo contrario de lo que generalmente ocurre al usar parametrización [Str-89], los objetos polimórficos pueden tener comportamientos mucho más variados que los que sólo están parametrizados. Por ejemplo, una lista polimórfica puede contener varios elementos, cada uno de un tipo diferente, mientras que la lista parametrizada sólo puede contener elementos de un mismo tipo (en particular, una lista polimórfica podría contener a su vez otra lista, o varios elementos de tipos diferentes).

      En [BR-95] se discute en detalle cómo extender el lenguaje C++ con el uso de "Firmas" (signatures), que sirven para usar colecciones heterogéneas, sin perder la verificación fuerte de tipos. Así se logra aumentarle la expresividad a C++, pues las firmas permiten implementar con comodidad contenedores de elementos heterogéneos, mas no lo suficiente para alcanzar la generalidad de los lenguajes que tienen polimorfismo uniforme. ¿Es necesario usar contenedores heterogéneos? Quienes refutan esta pregunta opinan que la expresividad de las firmas para C++ es un detalle interesante, aunque no sea teóricamente satisfactorio, pues no son suficientemente poderosas para lograr que las funciones C++ sean objetos de primer orden.

VAR      { Listas polimórficas: }
  Lm1 : TList = ((a,b,c), [1.2.3.4], "hilera", ("algo",1,3));
  Lm2 : TList = (a,b,c);

VAR      { Listas parametrizadas: }
  Lp1 : TList<INTEGER> = (1,2,3,4,5,6);
  Lp2 : TList<CHAR>    = (a,b,c,d,e,f);

      En la Figura 3.27 se compara la expresividad que se logra con el polimorfismo, ya que la lista "Lm1" tiene elementos que son de tipos muy variados (listas, arreglos, números, hileras), mientras que las listas parametrizadas "Lp1" y "Lp2" son homogéneas, pues todos sus elementos son del mismo tipo. Para manipular la lista "Lm1" el programador necesita que el lenguaje le provea de mecanismos para averiguar en tiempo de ejecución el tipo de cada objeto, para que pueda aplicarle las operaciones que le son válidas. Desde la perspectiva de los contenedores heterogéneos, el polimorfismo es un recurso de abstracción más general que la parametrización.

      El concepto de polimorfismo tiene dos significados. El primero ya se ha explicado, y se deriva de la práctica de usar punteros a funciones, como en el caso del procedimiento qsort() de la Figura 3.26. En este caso un programa o un módulo es polimórfico cuando usa punteros a funciones para ocultar el proceso que las rutinas realizan sobre los datos; puede verse la parametrización como un camino para llegar al polimorfismo, pues la parametrización se puede implementar usando polimorfismo.

      El segundo significado de polimorfismo se usa en el contexto de OOP, cuando se dice que un método es polimórfico si puede ser invocado indirectamente por medio de un puntero que está almacenado dentro de cada instancia del objeto; este es el polimorfismo de inclusión de [CW-85]. Usando la terminología de C++, los objetos polimórficos son los que tienen "Métodos virtuales", también llamados "Funciones virtuales". Cuando se invoca un método virtual se dice que se ha usado "ligamiento tardío" (late binding), "ligamiento dinámico" (dynamic binding) o "ligamiento en tiempo de ejecución" (run-time binding).

    TPunto       PROCEDURE TPunto.Despliegue();    VIRTUAL;
       .
     /   \
   /       \
  __      _____
 /  \    |     | PROCEDURE TCirculo.Despliegue();  VIRTUAL;
|    |   |     |
 \__/    |_____| PROCEDURE TCuadrado.Despliegue(); VIRTUAL;

TCirculo TCuadrado

VAR
  arreglo : ARRAY [1..N] OF ^TPunto;
  p : TPunto;
  c : TCirculo;
  r : TCuadrado;

BEGIN
  { ... }
  arreglo[3] := ADDR(p);
  arreglo[2] := ADDR(c);
  arreglo[1] := ADDR(r);
  { ... }
  FOR i := 1 TO N DO BEGIN
    arreglo[i]^.Despliegue;
  END;

      En la Figura 3.28 se muestra el uso del polimorfismo en el contexto de OOP. Cuando se usa herencia para extender de muchas formas un tipo de datos, puede resultar luego conveniente que el procedimiento que se use para operar sobre un dato dependa del dato en sí, aunque el programador no haya especificado exactamente cuál es ese procedimiento.

      Por ejemplo, en la Figura 3.28 se muestra una jerarquía de objetos en la que, por medio de la herencia, se extiende el tipo de datos TPunto para formar un TCirculo o a un TCuadrado. Es natural que el procedimiento para desplegar un círculo sea totalmente diferente al que puede desplegar un cuadrado. Sin embargo, ambos procedimientos tienen en común que existe un procedimiento llamado Despliegue() que permite desplegar variables de tipo TPunto, que es el tipo base para TCirculo y TCuadrado.

      El código al final de la Figura 3.28 muestra cómo es posible tener un arreglo de punteros a variables de tipo TPunto, en el que el procedimiento que se debe usar para hacer el despliegue se escoge en tiempo de ejecución. Para que la decisión de cuál es el procedimiento que debe usarse para operar sobre una variable se tome en tiempo de ejecución, se almacena en cada objeto la dirección del procedimiento que le corresponde. De esta manera, la variable "p" tendrá un puntero al procedimiento TPunto.Despliegue(), "c" a TCirculo.Despliegue(), etc.

PROCEDURE Print_Tree(           { ADH }
  {?} VAR T : TTreeB;           { qué imprimir }
  {?} VAR I : Tree.Iterator
);
{ RESULTADO
  Imprime el contenido del árbol "T" de acuerdo al
  orden definido por el iterador "I".
  - Para accesar cada elemento usa el iterador "I". }
VAR
  p : PTlink;
BEGIN { Print_Tree }
  { Usa un iterador para recorrer el árbol T }
  Write('(');
  I.BindB(T);
  WHILE NOT I.Finished DO BEGIN
    p := I.Current;
    T.Element.Print(p^,OUTPUT);
    IF NOT I.Finished THEN BEGIN
      Write(' ');
    END;
    I.Next;
  END;
  Write(')');
END; { Print_Tree }

      También es gracias a las funciones virtuales que se puede pasar un iterador como argumento a un procedimiento que accesa de forma totalmente polimórfica los elementos de un contenedor. Como cada instancia del iterador tiene punteros a sus métodos, se puede usar el mismo código para recorrer el contenedor de muchas maneras diferentes, cada una definida por el iterador, como se muestra en la Figura 3.29. A esto se le puede llamar parametrización por herencia.

      La parametrización no es una solución total al problema de la reutilización de módulos porque en muchas ocasiones es necesario que el mismo objeto esté almacenado en más de un contenedor. Por ejemplo, es usual que la misma instancia de un objeto de tipo TPerson deba estar en una lista (de elegidos) y en una cola (de espera) al mismo tiempo. Una solución parcial a este dilema es colocar copias de la instancia dentro de cada contenedor, pero entonces el programador debe agregar código en su programa para asegurarse de que, cuando una de las instancias cambia, cambien también todas las otras. Esto, además de engorroso, es inadecuado en algunas aplicaciones, principalmente aquellas en que los datos son compartidos por más de un proceso.

      La solución a este dilema es almacenar en el contenedor referencias, o sea, punteros a los objetos, en lugar de almacenar los objetos en sí, usando semántica de referencia. Para almacenar en varios contenedores la misma instancia, en cada contenedor se incluye una referencia a ella, de manera que, cuando el valor de la instancia cambie, el cambio será visible a través de todos los punteros que la referencian, y, por ende, cambiará el valor en todos los contenedores.

      Desde esta otra perspectiva se habla del polimorfismo como la capacidad de los contenedores de almacenar y compartir instancias de varios tipos de datos. Si son heterogéneos, los contenedores polimórficos pueden almacenar objetos de diferentes tipos. Por eso el polimorfismo puede verse como una manera de implementar parametrización, pero almacenando referencias a los objetos y no los objetos mismos.

      Los lenguajes que usan semántica de referencia incorporan el polimorfismo, y no la parametrización, como su mecanismo de abstracción. Entre estos lenguajes están Smalltalk, Lisp y CLU. En contraposición, los lenguajes Ada y C++ están orientados a la parametrización porque puede implementarse de manera que los programas objeto sean eficientes. Ambas tendencias, sin embargo, coinciden en que es muy importante el apoyo del compilador para lograr una fuerte verificación fuerte de tipos.

      Existe otra gran ventaja de usar referencias. Independientemente del objeto referenciado, un puntero tiene siempre el mismo tamaño (esto lo aprovecha Modula-2 para definir sus tipos "opacos" [Wir-82]). Esto implica que el compilador siempre sabe cuánta memoria reservar para las variables, que son punteros, lo que resulta en una gran flexibilidad para definir ADT's en términos de otros ADT's.

      La (más grande) desventaja del polimorfismo es que los objetos ocupan más memoria del computador, pues al espacio que usan hay que agregar todos los punteros que lo referencian, y además el acceso al objeto es menos eficiente, pues se hace indirectamente a través de un puntero. Para aquellas aplicaciones en que estas desventajas son inconvenientes imperceptibles para el usuario final del programa, se justifica totalmente usar un lenguaje que tenga semántica de referencia; para estas aplicaciones, la investigación descrita en este trabajo puede resultar irrelevante. En el caso de compiladores, sistemas operativos, y otros programas como los mencionados en la sección 1.1 (Motivación), el impacto de estas desventajas es tan grande que impide la construcción del programa.

      El uso de semántica de referencia tiene otras ventajas. Por ejemplo, para trasladar el valor de un objeto de un lugar a otro basta copiar un puntero, que es un operación que el compilador puede suplir por defecto sin mayor problema.

      Si se implementa la parametrización por medio del polimorfismo, el código de todas las operaciones del contenedor puede ser compartido entre todas las instanciaciones. Por ejemplo, si el contenedor es una lista, entonces todas las listas usarán el mismo procedimiento List.Insert() o List.Delete(), independientemente del tipo de datos contenido en la lista. La razón es la siguiente: una lista de números enteros realmente es una lista que contiene punteros de un tipo especial, o sea punteros a enteros. Pero todos los punteros son básicamente iguales, ocupan la misma cantidad de memoria, y el manipular punteros a enteros es igual que manipular punteros a personas, o listas, o a cualquier otra cosa. Para hacer una inserción o un borrado, en la implementación de TList sólo es necesario saber cómo copiar o eliminar punteros para insertar o borrar un elemento de la lista, pues lo que se inserta y borra son punteros y la implementación nunca toca los elementos en sí.

      Lo mismo ocurre con la operación List.Copy(), que se limitaría a copiar los componentes de la lista, pues en teoría nunca debería ser necesario copiar los elementos en sí. Por eso los lenguajes que usan semántica de referencia siempre proveen algún mecanismo para duplicar objetos, como una operación Clone(), de forma que puedan hacerse copias profundas de las instancias.

      Algunas operaciones básicas de los ADT's no son simples de implementar polimórficamente, como es el caso de las operaciones Load() y Store(), que no pueden limitarse a copiar punteros en almacenamiento secundario. Estas operaciones son particularmente difíciles de implementar polimórficamente, pues cuando un objeto está en más de un contenedor, y varios de esos contenedores son almacenados en almacenamiento secundario, al ser recuperados se obtendrán varias copias del mismo objeto (una diferente para cada contenedor). La única solución a este problema es crear un nuevo super-contenedor, y programarle de nuevo la complicada estructura que representa la agregación de todos los contenedores. El problema de la persistencia de los objetos ha llevado a algunos autores a crear ambientes de programación en donde algunos objetos pueden tener una vida más larga que la del programa en que han sido creados.

      Si se combinan la semántica de referencia, la herencia y el polimorfismo, es posible definir con gran facilidad un contenedor polimórfico, que contenga punteros a elementos del tipo base de la jerarquía de los tipos que pueden estar almacenados en él. Esta solución presenta no sólo los problemas que se apuntaron previamente (uso de más memoria, aumento del tiempo de ejecución, etc.), sino que además obliga a derivar de un tipo base todos los elementos que puedan eventualmente estar almacenados en un contenedor, lo que a su vez obliga a que el lenguaje permita usar herencia múltiple. Por eso hay quienes no gustan de estas complicadas construcciones sintácticas, pues todas interactúan entre sí y el resultado es un lenguaje más difícil de usar, para el cual cuesta más producir un sistema de compilación eficiente. La complejidad del lenguaje fue la causa principal por la que los programadores debieron esperar varios años antes de tener acceso a compiladores mínimamente funcionales de Ada y C++.

      En realidad, no es necesario desechar los lenguajes polimórficos aduciendo que son ineficientes, pues lenguajes como ML y Scheme son altamente expresivos y permiten escribir programas con un altísimo nivel de abstracción, sin sacrificar mucho en eficiencia de ejecución, a más de que no requieren de una gran maquinaria para la definición y verificación explícita de tipos. Por otro lado, los programadores de C++ y Ada, quienes en alguna ocasión han programado en lenguaje de máquina, no desean que su lenguaje incorpore construcciones semánticas como la semántica de referencia y los recolectores de basura, que diminuyan el rendimiento del programa, pues gustan de mantener control sobre la eficiencia. Por eso continuarán usándose tanto la parametrización como el polimorfismo en la construcción de programas, pues ambas tecnologías son complementarias, y permiten la reutilización de componentes de programación.

3.9 Excepciones

      Una excepción es un evento inesperado, generalmente con proporciones de calamidad. El buen programador desea que su programa sea robusto, de forma que ante estos eventos reaccione adecuadamente; si no es posible corregir los problemas que se producen después de una falla, es por lo menos deseable que el programa tenga una degradación suave, evitando de esta manera un estruendoso fin de ejecución. En lo posible se trata siempre de sobreponerse de la mejor manera a la catástrofe.

      Existen muchos tipos de excepciones. Por ejemplo, cuando en tiempo de ejecución se usa un índice que está fuera de rango, se produce una excepción. También sucede cuando se hace una división por cero, o cuando el resultado de una expresión es demasiado pequeño (desbordamiento y bajo rebase; overflow y underflow en inglés). Los principales tipos de excepción son los siguientes:

• Errores en tiempo de ejecución, como división por cero, sobre rebase, bajo rebase, o intentar leer de un archivo que no existe, etc.
• Excepciones generadas por las bibliotecas de programas, que aprovechan el mecanismo de excepciones para simplificar el uso de la biblioteca.
• Excepciones generadas por el programador, porque mediante la generación y manejo de excepciones es posible construir programas más robustos o retornar de invocaciones que están profundamente anidadas.

      Un ejemplo práctico del uso de excepciones es el siguiente: supóngase que se está escribiendo una hoja de cálculo, que tiene un largo y complicado proceso para recalcular el valor de todas las celdas. Se desea permitir al usuario interrumpir en cualquier momento el proceso, lo que puede implementarse de dos formas.

      La primera implementación, y más complicada, consiste en agregar una gran cantidad de parámetros de retorno a cada rutina usada para recalcular la hoja. En el momento en que se detecta la interrupción, se comenzaría una cadena de retornos de procedimientos, hasta llegar al nivel superior. En cada procedimiento debe incluirse código para retornar adecuadamente después de que se produce la interrupción, mientras realiza su trabajo.

      La otra forma es usar excepciones. Inicialmente, se establece un contexto de excepción en el nivel principal. Luego cualquier rutina (hasta las recursivas) puede retornar abruptamente a este nivel generando una excepción. De esta manera el programa no tendrá una cantidad excesiva de códigos de retorno para manejar cada situación particular.

      El retorno a un contexto de excepción difiere mucho del retorno normal de una rutina, pues generalmente al producirse la excepción no se regresa a las rutinas activas. En este ejemplo la flecha "-->" indica que una rutina invoca a otra. Entonces, si por ejemplo,
      E() --> A() --> B() --> C()
y el contexto de excepción activo está en E(), entonces si en la ejecución de C() se produce una excepción el control del programa pasará directamente a E(), saltando sobre las invocaciones de A() y B(). O sea, que el programa no retornará ni a A() ni a B().

      Con el ejemplo anterior se muestra que, cuando no se usan excepciones, el programador que desea implementar un programa muy robusto debe incluir en cada procedimiento muchos parámetros que le permitan retornar códigos de error. Además, cada procedimiento debe también incluir bastante código para tomar las acciones apropiadas, dependiendo de cada posible problema. De esta forma quedan mezcladas en el mismo módulo la lógica que resuelve un problema con la que maneja las situaciones insólitas que surgen cuando ocurren fallas. El resultado de todo esto es programas que son tan difíciles de leer como de mantener.

      Las primeras versiones del lenguaje Pascal y Modula-2 no incorporan el uso de excepciones. Sin embargo, a partir de la introducción del sistema de programación Delphi, que está basado en el Turbo Pascal v7.0, Borland definió un modelo de manejo de excepciones que es congruente con Turbo Pascal. Previo a este importante desarrollo tecnológico el autor implementó la unidad Except.pas [DiM-94j], con la que logra básicamente lo mismo que Delphi ofrece, si bien sin requerir el apoyo del compilador (aunque no con la misma flexibilidad).

      Una vez que el lenguaje Turbo Pascal, o Delphi como se le llama en su nueva presentación [BI-95], tiene excepciones, ya cuenta con prácticamente la misma expresividad de los lenguajes más complejos, Ada y C++, pues ya en este trabajo se muestra cómo parametrizar contenedores.