Abstracción de Datos en Pascal por Adolfo Di Mare Reporte Técnico PIBDC-03-91 Proyecto 326-89-019 Revisión 2.0 Resumen: ======= El principal objetivo de este trabajo es presentar un conjunto de convenciones que permitan usar abstracción de datos en el ámbito del lenguaje Pascal (para aquellas implementaciones que incluyen compilación separada por medio de unidades). Múltiples ejemplos ilustran los alcances de esta técnica. Este trabajo está orientado al compilador Turbo Pascal v5.0, aunque la misma técnica también puede usarse para Modula-2 o en otras versiones de Pascal. Las convenciones aquí elaboradas permiten que las instancias de los objetos, aun de los que son contenedores, tengan asignada memoria en la pila de ejecución del programa. A diferencia de otras propuestas, no obligan a usar punteros a las instancias de los objetos en memoria dinámica, con lo que se logra una significativa mejora en la eficiencia de programas que usan abstracción de datos. Abstract: ======== We explain a set of conventions that allow data abstraction for the Pascal language (for those implementations that support separate compilation through units). Complete examples illustrate the applicability of this technique. This work is oriented to Turbo Pascal v5.0, even though these ideas can be used with Modula-2 or with other versions of Pascal. These conventions allow object instances, even those that are containers, to use stack memory. As other proposals require the use of pointers and dynamic memory, the use of these conventions can mean a significant improvement in the efficiency of programs that use data abstraction. Esta investigación se realizó dentro del proyecto de investigación 326-89-019 "Estudios en la tecnología de programación por objetos y C++" inscrito ante la Vicerrectoría de Investigación de la Universidad de Costa Rica. La Escuela de Ciencias de la Computación e Informática también ha aportado fondos para realizar este trabajo. Abstracción de Datos en Pascal ============================== La ingeniería de sistemas de información ha progresado gracias a la introducción de nuevas técnicas para construir programas. El primer gran avance lo constituye la programación modular, complementada con la programación estructurada. Otros logros lo constituyen los llamados lenguajes de cuarta generación, que permiten desarrollar sistemas en un lenguaje muy especializado. Pero conforme avanza la tecnología de computadores es necesario crear programas cada vez más sofisticados. En la última década ha tomado gran auge el uso de la programación por objetos, que tiene como requisito la abstracción de datos, y que implica una nueva manera de diseñar programas. El lenguaje Smalltalk [Goldberg-83] ha causado gran revuelo, hasta tal punto que existen compiladores para lenguajes como C++ [Stroustrup-86a], que han sacado la programación por objetos de los laboratorios de investigación, para ser utilizados en el quehacer diario de las empresas. (Una excelente discusión de los alcances de la programación por objetos puede encontrarse en [Stroustrup-88]). El lenguaje Pascal fue definido por el profesor Niklaus Wirth a principios de los 70s. Tuvo gran aceptación, pues incorpora la mayor parte de las construcciones sintácticas necesarias para la programación estructurada, y como Pascal es un lenguaje simple y elegante, es posible escribir compiladores muy rápidos y eficientes para él. En el contexto de las micro computadoras, la implementación de Phillipe Kahn del lenguaje Pascal, conocido como Turbo Pascal [Borland-88], ha literalmente revolucionado el desarrollo de programas. Su aceptación y uso en nuestras universidades junto con la falta de difusión de las técnicas de abstracción de datos en nuestro medio, hacen necesario este artículo. Aquí se discuten primero los conceptos generales de tipos abstractos de datos (ADTs) y luego se explican los "trucos" usados para implementar ADTs en Turbo Pascal 5.0 o en Modula-2. Finalmente se incluyen algunos ejemplos de implementaciones. En todo el artículo se siguen las convenciones de programación descritas en [Di Mare-88], que son ampliadas en este trabajo. 1. Abstracción de procedimientos ================================ Fundamentalmente, la programación modular es abstracción de procedimientos. La idea meter un conjunto de instrucciones en un módulo, que tiene una interfaz claramente definida. Mediante la abstracción de procedimientos el programador separa claramente el cómo del qué: una subrutina contiene la lógica necesaria para ejecutar una tarea, y sus parámetros definen los objetos sobre los que trabaja. 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. La "documentación" era labor de funcionarios de poco sueldo, y 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. Se introdujo la verificación de tipos en tiempo de compilación, en los argumentos de cada rutina, como una herramienta para reducir el tiempo de desarrollo de un programa, con gran éxito. Sin embargo, todavía no se reconocían las grandes ventajas de especificar procedimientos. ================================================================== PROCEDURE Lea_Arbol_Menu( { EXPORT } { Adolfo Di Mare } {+} VAR f : TEXT; { archivo de lineas de menú } {+} mprin : Linea_P; { linea leída por el llamador } {-} VAR ultLn : Linea_P { 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 ítems del menú mprin. } Figura 1 ================================================================== La Figura 1 es un ejemplo de la especificación de un procedimiento, escrito de acuerdo a las convenciones de programación definidas en [Di Mare-88]. 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: la mayoría de los programadores no se molestarían en escribir tanto para una "escuálida" subrutina. 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. Las bibliotecas de programas están formadas por procedimientos como éste. 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 Linea_P (o sea, un puntero a una Linea_T). Es cierto que los identificadores son significativos, pero eso no es suficiente para lograr incorporar este procedimiento en un programa real. Hace falta mucho más información. Las bibliotecas de programas comerciales generalmente proveen información adicional al programador, en la que se describe el contexto de uso de cada procedimiento. 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 partir 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 [Kernighan- 86], el lenguaje usado en el sistema operativo UNIX [Kernighan- 87], 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 no basta con describir lo que el subprograma hace para que sea posible utilizarlo. También es necesario describir los datos con que trabaja cada procedimiento. Esto se logra mediante la abstracción de datos. 2. Abstracción de datos ======================= La programación que utiliza abstracción de datos (data hiding) se basa en el hecho de que en un programa se deben integrar y combinar los tipos básicos de datos, como números y caracteres, para formar estructuras de datos 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. Esto último es muy importante para separar el programa en partes independientes, o módulos, evitando así 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. El objetivo perseguido al usar abstracción de datos es lograr aislar todas estas dependencias, de forma que los cambios puedan ser hechos con un mínimo de esfuerzo y en una forma localizada. En nada ayuda tener que buscar por todo el programa en qué lugar deben hacerse los cambios. También es importante especificar qué es cada estructura de datos, mediante la abstracción de datos. Una lista, por ejemplo, es una estructura de datos que tiene un comportamiento muy bien definido: pueden insertársele nuevos elementos, recorrérsela, encontrar el primer y último elemento, etc. Al usar abstracción de datos, el programador decide cuáles procedimientos se necesitan para manipular una lista, y define su interrelación. Un usuario del tipo de datos "lista" no necesitará entonces conocer cómo se interrelacionan (a nivel de implementación) los datos ni los procedimientos que manipulan listas. Para usar una lista, un programador no necesita descubrir de nuevo el concepto de lista: simplemente lo puede importar de una biblioteca. Al usar abstracción de datos el programador define cómo puede comportarse cada una de las variables de su programa. O sea que además de usar abstracción de procedimientos para construir el programa modularmente, deben especificarse las operaciones válidas sobre los datos. El objetivo es programar un módulo que defina un nuevo tipo de datos, y además que incluya varios procedimientos que permitan manipularlo. Este dúo procedimiento-dato es un Tipo Abstracto de Datos, o Abstract Data Type en Inglés (ADT). El programador-usuario del ADT podrá manipular las variables del tipo de datos únicamente por medio de sus procedimientos asociados. En un sólo módulo se "encapsula" el nuevo tipo de datos junto con sus procedimientos. Entonces, para implementar un ADT deben definirse dos cosas: primero, los campos que se necesitan para almacenar los valores del dato, y segundo los procedimientos que permiten utilizarlo. El asociar un tipo de datos con sus procedimientos en un módulo se conoce como encapsulamiento. En Pascal el encapsulamiento se simula mediante unidades, y en Modula-2 usando módulos. En otros lenguajes, como Smalltalk, Simula y C++, el lenguaje incluye construcciones sintácticas que permiten encapsular un tipo de datos, también llamado una clase, con sus procedimientos. En este caso, los procedimientos se conocen por los nombres "operación", "procedimiento miembro" o "método". ================================================================== Tabla de sinónimos ================== Encapsulación Procedimiento Tipo de Dato Mensaje Abstracción Subrutina Objeto Parámetro Especificación Rutina Clase Argumento Diseño Método ADT Ocultamiento Operación Tipo Abstracto de Datos Figura 2 ================================================================== Desgraciadamente los computólogos tenemos la costumbre de crear muchos nuevos términos para viejos conceptos. Los términos estructura de datos, tipo de datos, tipo abstracto de datos, objeto, clase y variable son muy similares. Todos sirven básicamente para lo mismo: definir variables en un programa, o sea, instancias del tipo de datos (aunque tiene más prestigio hablar de "objetos" o de ADTs, que de simples tipos). La Figura 2 es una lista de los términos usados para referirse a los mismos conceptos (aunque no todos son sinónimos exactos). Sin embargo, el contexto del discurso es muy importante: al hablar de ADTs en Smalltalk necesariamente debe suponerse que el concepto incluye cualidades como herencia y funciones virtuales. Las mismas palabras dichas en el contexto de Pascal o Modula-2 no pueden significar más que abstracción de datos. Entonces, una operación es una rutina que está asociada a un tipo de datos, y que permite manipularlo, examinarlo y cambiarlo. El término "método" es sinónimo de operación y, aunque es bastante confuso, es el utilizado en ambientes Smalltalk (aunque sí existe una buena razón para usar ese término, no la discutiremos). Intrínsecamente ligado al concepto de encapsulamiento y abstracción está el concepto de ocultamiento de datos. Al ocultar datos, básicamente lo que se persigue es evitar que la representación usada para un ADT sea accesible a un programador- usuario. Por ejemplo, al implementar el ADT pila puede usarse una lista de nodos con punteros, o un arreglo. Si la representación del ADT es privada, entonces al usar una pila el programador no podría saber si la implementación que usa es una o la otra. El ocultamiento de datos es muy importante para lograr una mejor modularización, pues garantiza que el programador descuidado tenga acceso controlado a las campos que conforman una instancia de un ADT, evitando así que destruya inadvertidamente alguna relación necesaria entre esos campos. Paradójicamente, Smalltalk y Simula son lenguajes que soportan abstracción y encapsulamiento de datos, pero que no soportan ocultamiento de datos. Es evidente que los diseñadores de esos lenguajes no consideraron necesario el ocultamiento de datos, lo que amerita su defensa. Tal vez pueda pensarse que los programadores, por antonomasia, no son "descuidados". Sin embargo, el ser "cuidadoso" requiere de un esfuerzo mental grande, a veces enorme, principalmente cuando se trabaja en grandes proyectos de programación. Si el compilador, la máquina computacional, el robot automático puede verificar que se sigan procedimientos adecuados, ¿para qué cargar entonces al programador con esta innecesaria responsabilidad? Como se ha mencionado anteriormente, gran parte del éxito de Pascal como lenguaje radica en su capacidad de verificar tipos, que en realidad es una de esas actividades que podría hacerse manualmente. Al ser ésto responsabilidad de la máquina, se obtiene una significativa reducción del esfuerzo requerido para construir un programa, lo que decrece su costo y tiempo de programación. El lector debe saber que la programación que usa abstracción de datos requiere de un mayor esfuerzo en el diseño de los programas, pues no basta simplemente con partir en subproblemas el problema a resolver, tal y como se hace al descomponer el código y el diseño del programa de arriba hacia abajo (top-down). Cuando se programa de arriba hacia abajo el programador deja para después decisiones de diseño, pues cada nueva incógnita representa un nuevo procedimiento, en el que se oculta la respuesta correcta. Al final del diseño lo que queda es un árbol de dependencias de procedimientos. Desgraciadamente, en muchos casos la partición así definida no es la más adecuada para alcanzar los objetivos del programa. Algunos autores han escrito muchos artículos en los que exponen el diseño de arriba hacia abajo claramente, y han logrado convencer a los teóricos de la programación de que es posible llegar a un excelente programa con sólo partirlo de arriba hacia abajo. La verdad es que el proceso de programación es iterativo, y requiere de muchas revisiones en todos los niveles de un programa. La abstracción de datos permite descomponer más adecuadamente un problema, a partir de los objetos que usa. (Esto último es lo que esta nueva tecnología promete: todavía debe usarse mucho antes de decidir si la anterior afirmación es cierta, o si no lo es, bajo qué condiciones sí puede serlo). En este artículo no se busca desprestigiar a las metodologías de diseño de arriba hacia abajo. Más bien se busca complementarlas, pues el proceso de programación es una actividad intelectual muy difícil, en la que los pocos avances tecnológicos que se han alcanzado todavía no son suficientes para satisfacer las crecientes demandas de sistemas computacionales. Es simplemente ilusorio olvidar una técnica que en muchos contextos ha dado muy buenos resultados, para sustituirla por otra que todavía no está bien difundida. Pero como con el uso disciplinado de abstracción de datos se han obtenido muchos éxitos, es el deber de todo profesional o académico conocer esta novel técnica. Al usar abstracción de datos es necesario diseñar mejor el programa, con lo que se logra una mayor modularidad, que es una de las medidas de calidad en programación. El programa queda mejor modularizado que si hubiera sido hecho simplemente usando abstracción de procedimientos, pero el precio de este beneficio es que el programador puede tardar más en terminar su programa (más aún si no sabe bien lo que es un ADT). Un programa escrito sin usar abstracción de datos es más difícil de mantener, pues su estructura está oscurecida por la maraña de procedimientos que lo componen. Por eso al usar abstracción de datos se logra escribir programas más modulares. La alta modularización alcanzada al usar ADTs permite que el mantenimiento del programa sea mucho más simple. Sin embargo, en un ambiente de desarrollo de programas es difícil que esta nueva tecnología sea aceptada, pues un administrador miope va a preferir que sus sistemas sean programados muy rápidamente, aunque el posterior mantenimiento sea más difícil. Con el correr del tiempo el mercado aprenderá a apreciar la calidad de los programas, lo que obligará a los programadores a usar tecnologías nuevas que les permitan crear mejores productos a un precio más bajo. Una de las ventajas más importantes de usar ADTs es que un programador especializado puede dedicarse a depurar totalmente los procedimientos de un ADT 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 un programador-usuario del ADT tiene acceso a rutinas de alta calidad y confiabilidad. Se evita así reprogramar los "trucos" que permiten implementar, eficientemente, una estructura de datos cada vez que se la necesite. ================================================================== UNIT Stack_T; INTERFACE USES Elem_T; CONST SSize = 20000; { capacidad de la pila } TYPE Rep_Stack = RECORD { representación privada del ADT } elem : ARRAY [1..SSize] OF Elem_ADT; ultimo : INTEGER; END; Stack_P = ^Stack_ADT; Stack_ADT = RECORD Rep : Rep_Stack; END; { PARAMETERS (Stack_T Stack_ADT Stack_P SSize) (Elem_T Elem_ADT) } PROCEDURE Init ( {-} VAR s : Stack_ADT); PROCEDURE Clear ( {?} VAR s : Stack_ADT); PROCEDURE Done ( {?} VAR s : Stack_ADT); FUNCTION OK ( {+} VAR s : Stack_ADT) {>>>>>>>} : BOOLEAN; PROCEDURE Copy ( {?} VAR x : Stack_ADT; {+} VAR y : Stack_ADT); PROCEDURE Move ( {?} VAR x : Stack_ADT; {?} VAR y : Stack_ADT); FUNCTION Equal ( {+} VAR x, y: Stack_ADT) {>>>>>} : BOOLEAN; PROCEDURE Load ( {?} VAR s : Stack_ADT; {+} VAR F : FILE); PROCEDURE Store ( {+} VAR s : Stack_ADT; {?} VAR F : FILE); FUNCTION Empty ( {+} VAR s : Stack_ADT) {>>>>>>>} : BOOLEAN; FUNCTION Full ( {+} VAR s : Stack_ADT) {>>>>>>>} : BOOLEAN; PROCEDURE Push ( {?} VAR s : Stack_ADT; {+} VAR e : Elem_ADT); PROCEDURE Pop ( {?} VAR s : Stack_ADT; {-} VAR e : Elem_ADT); IMPLEMENTATION {...} END. Figura 3 ================================================================== Para entender todos estos nuevos conceptos es conveniente enmarcarlos en un ejemplo específico. Para esto es útil usar la especificación del ADT pila, que es el ejemplo usualmente presentado al principiante. Una pila es un tipo de datos de los llamados contenedores, en el que el último dato en entrar a la pila es el primero que sale: el programador necesita que ese orden de entrada-salida sea el comportamiento de una variable de tipo pila. Los ADTs cuya función es contener a otros datos se llaman contenedores. La Figura 3 es un extracto de la especificación del ADT pila, usando una unidad Turbo Pascal. Es muy conveniente usar convenciones para programar un ADT: el nombre de la unidad que contiene las declaraciones de tipos y el código de las operaciones del ADT deben tener el sufijo "_T", que indica que contiene un ADT. Además, el nombre del tipo del ADT es igual al de la unidad en que está contenido, pero se usa el sufijo "_ADT". El usar una unidad Pascal para implementar un ADT es muy cómodo, pues en ella es posible incluir no sólo las operaciones del ADT, sino también las declaraciones de tipos necesarias para definir los campos que permiten almacenar una instancia del ADT. Los trucos de este artículo pueden usarse en las versiones de Pascal que no soporten el uso de unidades (que desgraciadamente son la mayoría), pero es entonces necesario simular su efecto, a costa de un mayor esfuerzo por parte del programador. ================================================================== VAR s : Stack_ADT; { pila para invertir t } ch : CHAR; { temporal } t : STRING; { tira a invertir } i : INTEGER; { contador } BEGIN Init(s); { inicializa s } ReadLn(t); FOR i:= 1 TO Length(t) DO BEGIN Push(s,t[i]); END; WHILE NOT Empty(s) DO BEGIN Pop(s,ch); Write(ch); END; Done(s); { libera s } END; Figura 4 ================================================================== Las operaciones de la unidad Stack_T tienen argumentos de tipo Stack_ADT: cuando el programador quiere declarar una variable que sea una pila, o sea, cuando necesita usar una instancia del objeto pila, lo que hace es declarar la variable de tipo Stack_ADT, como se hace con la variable "s" en la Figura 4. Para manipular una variable de tipo Stack_ADT, el programador-usuario puede únicamente usar los procedimientos exportados por la unidad Stack_T. Por ejemplo, el código de la Figura 4 lee una tira de caracteres, y la invierte usando una pila. Nótese que bastan los procedimientos de la pila para lograr el objetivo deseado. (En este ejemplo se supone que el tipo de datos Elem_ADT a almacenar en la pila es CHAR). 3. Implementación de ADTs en Pascal =================================== ================================================================== VAR e : Elem_ADT; s : Stack_ADT; { "s" es la pila que usará el programador. } r : Rep_Stack ; { debe cualificarse el nombre, pues cada ADT } {...} { posee su propio tipo Rep_Stack. } BEGIN s := r; { error de compilación: tipos incompatibles } r := s.Rep; { OK: son del mismo tipo } s := Stack_ADT(r); { OK, usado muy pocas veces } Push(s, e); { OK } Pop (s, e); { OK } Push(r, e); { error: r no es de tipo Stack_ADT } Pop (r, e); { error: r no es de tipo Stack_ADT } IF NOT Empty(s) THEN BEGIN { OK } {...} END; Figura 5 ================================================================== A primera vista la definición del tipo Stack_ADT en la Figura 5 parece muy extraña: ¿para qué se necesita el registro Rep_Stack y un registro que únicamente contiene un campo llamado Rep? El tipo Rep_Stack define cuáles son los campos, registros o arreglos que se necesitan para implementar la pila, esto es, la parte interna o privada del ADT. Por otro lado, el tipo Stack_ADT contiene un único campo que se llama Rep (Rep_resentación), que es el campo que contiene la representación interna del ADT. La palabra "Rep" se ha tomado del lenguaje CLU, en donde esta palabra no es, como en Pascal, un identificador más, sino que forma parte del lenguaje. Coloquialmente se dice "metérsele al Rep" al acto de accesar los campos privados que componen un ADT. Un programador usuario del ADT no necesita el tipo Rep_Stack en absoluto, pues su interés debe centrarse en manipular las variables de tipo Stack_ADT por medio de las operaciones Init, Clear, Done, OK, Copy, Move, Equal, Empty, Full, Load, Store, Push, Pop, y nada más. Si un programador define una variable de tipo Stack_T.Rep_Stack (lo que es válido), no podrá usarla como argumento en ninguno de los procedimientos del ADT pila. Con esto se logra evitar que el programador, inadvertidamente, cambie los valores privados de una pila. Si lo hiciera, entonces el compilador respondería con "error de tipo de datos", pues una variable de tipo "Rep_Stack" no es compatible con una de tipo "Stack_ADT". De esta forma se simula en Pascal el ocultamiento de datos, pues con este truco se logra que el compilador, por medio de la verificación de tipos, resguarde la parte interna del ADT. El usar el tipo Rep_Stack para construir Stack_ADT es una manera elegante de lograr ocultamiento de datos. Una variable de tipo Stack_ADT tiene exactamente el mismo tamaño que una de tipo Rep_Stack. En la implementación de Stack_ADT será necesario usaaaar muchas sentencias que usen el campo Rep del registro Stack_ADT, que es válido. Pero si un programador-usuario del la unidad Stack_T usa ese campo, su programa quedará plagado de referencias a "Rep", las que son muy fáciles de detectar por medio del programa GREP. Este programa busca todas las líneas en un archivo de texto que contienen un patrón de caracteres, por lo que al ejecutar el comando: GREP Rep PROGRAMA.PAS Si al ejecutar GREP éste despliega alguna línea, entonces el programador-usuario del ADT Stack sabrá que está violando las partes privadas del ADT. Lo mismo sucedería si usara transferencia de tipos desde Stack_ADT a Rep_Stack. La transferencia de tipos es una facilidad de muchos lenguajes, como es el caso de Modula-2, Turbo Pascal y C. De esta manera el usuario del ADT está forzado a no ver la representación interna de la pila; si quiere "metérsele al Rep" deberá entonces usar la palabra Rep al referirse a alguno de los campos de una variable de tipo Stack_ADT. La Figura 5 ilustra la reacción del compilador al uso del Rep para implementar un ADT. En el ejemplo de la Figura 5 la variable "s" es la pila que el programador podrá usar, depositando y recuperando objetos de tipo Elem_ADT. El tipo Rep_Stack es la representación, interna y privada, del ADT. Es posible definir variables de tipo Stack_T.Rep_Stack, como es el caso de la variable r, pero lo usual es hacerlo únicamente al escribir el código que implementa cada una de las operaciones de un ADT. En un lenguaje como C++, que tiene un mejor soporte para ocultamiento de datos, sería posible impedir que el programador usuario del Stack_ADT tuviera acceso a la representación interna del tipo de datos abstracto pila. Como Pascal no fue diseñado para implementar ADTs, no es posible hacer ésto. Debe confiarse en que el programador no abusará del ADT, metiéndosele al Rep. (La versión 6.0 de Turbo Pascal permite definir campos privados, pues éste compilador ya tiene un soporte bastante adecuado para programación por objetos). Cuando se usa abstracción de datos sin ocultamiento de datos, es muy común que el novicio con frecuencia se le mete al Rep por pereza de definir y usar las respectivas operaciones. Es más cómodo violentar el ADT, que usar sus operaciones. La tentación es más fuerte cuando es el mismo programador quien ha definido un ADT y, para ahorrar tiempo al digitar su programa, simplemente usa la parte interna del tipo de datos. En general, es difícil no usar cada campo "directamente". Pero el no usar ocultamiento de datos es contraproducente, pues entonces el compilador podrá hacer menos trabajo para el programador. Además, si la implementación del ADT cambia, un programa que lo use deberá también modificarse. Pero si un programa únicamente usa las operaciones del ADT, siguiendo las reglas de su especificación, y nunca se le mete al Rep, al cambiar la implementación del ADT bastará recompilar el programa junto al nuevo ADT. De esta manera se logra mejorar o cambiar la implementación de un ADT, sin modificar los programas que lo usan. Esta es, en mayor cuenta, la modularización adicional que se deriva del uso de abstracción de datos respecto del uso de programación estructurada. Para implementar las operaciones del ADT el programador deberá usar mucho la transferencia de tipos. En el caso del ADT pila, deberá transformar variables del tipo Stack_ADT en variables tipo Rep_Stack. Cada operación del ADT contendrá muchas instrucciones en que aparecerá Rep_Stack, o simplemente Rep. A primera vista incomoda un poco ver Rep tantas veces, pero es fácil aceptar este hecho al reconocer que cada vez que se usa Rep es porque se tiene acceso a la parte interna del ADT. Visto desde este sesgado punto de vista, el uso de Rep ayuda a documentar el código del programa, en lugar de opacar su claridad. En la experience del autor, para aceptar el uso de la palabra Rep en los programas se requiere de tres semanas, en las que se produce un serio conflicto personal en contra de Rep. Al principio los programas se ven feos, y llenos de garabatos que estorban la vista. Pero al llegar la cuarta semana, el cerebro se acostumbra a ver lo que debe ser, y la palabra Rep pasa a ser una molestia necesaria y aceptable. Como es costoso usar cada una de las operaciones del ADT, pues hay que hacer un llamado de subrutina, se objeta el uso de ocultamiento de datos por esta pérdida de eficiencia. Esto mueve a muchos programadores a no usar el truco del Rep por "eficiencia". Lo cierto es que un programa debe estar correcto antes de ser eficiente. El sobretrabajo que implica usar las operaciones del ADT en muy pocos casos justifica romper la modularidad de un sistema. Además, pronto comenzaremos a ver versiones de Pascal que permitan desarrollar el código de una subrutina en línea (inline), que es un proceso por el cual se sustituye la invocación a una rutina por el cuerpo que la implementa, como si fuera una "macro". Con esto se lograría que el acceso a los componentes del ADT sea tan eficiente como usar directamente los campos de la representación privada del dato, lo que daría al traste con esta objeción. Esto es el curso seguido al definir C++. El truco del Rep le permite a cualquier programador tener acceso a la parte interna del ADT, si así lo desea. Para lograrlo deberá usar la palabra Rep, ya sea al declarar una variable (como es el caso al declarar r en el ejemplo), o al hacer una transferencia de tipos, que es el caso de la asignación a la variable r en la Figura 5. Al mencionar explícitamente la palabra Rep, el programador de hecho reconoce que está irrumpiendo en las partes privadas del ADT, y que es consciente de sus actos. Muchas veces sucede que dos o más ADTs están muy relacionados; en esos casos se puede acceso a cada una de sus partes internas desde el otro sin mayor problema, usando la cualificación de identificadores para los tipos Rep respectivos. Por ejemplo, si se definen juntos los tipos Matriz_ADT y Vector_ADT, es de suponer que cada uno de ellos uno pueda tener acceso a la representación interna del otro, en aras de mejorar la eficiencia de la implementación. En este caso, dentro de la unidad Matriz_T se puede usar el Rep del Vector_ADT simplemente declarando y usando variables de tipo Vector_T.Rep_Vector. Otro ejemplo lo constituyen los iteradores, que se discuten más adelante. Usando el truco del Rep es posible implementar el concepto de "tipos amigos" de C++. Un tipo es amigo de otro, si sus operaciones tienen acceso a las partes privadas del otro. En general, la "amistad" no es un relación simétrica. No es tan usual encontrar tipos amigos en programas Pascal como lo es en programas C++, debido a sus limitaciones como lenguaje de computación. 4. ADTs elementales y ADTs contenedores ======================================= El ADT pila es un tipo especial de dato, pues su función primordial es contener a otros datos. No puede concebirse una pila que no contenga elementos (que no es lo mismo que una pila que está, en cierto momento, vacía). Los ADTs cuya función es contener a otros datos se llaman "contenedores". En este artículo se usa mucho el término "ADT contenedor", del que la pila es un ejemplo, o "ADT contenido", que en la mayoría de los casos es un ADT elemental. Ambos términos son necesarios para diferenciar bien el papel de cada ADT. En general, en todo programa se usan muchos ADTs elementales y contenedores. Por ejemplo, si se escribe un programa que permita simular las vías de la ciudad capital, con el fin de determinar el tiempo que una persona debe invertir para viajar de un punto a otro, entonces deberán definirse varios ADTs elementales: Persona_ADT, Lugar_ADT, Hora_ADT, etc. Además, deben usarse muchos tipos de ADTs contenedores, como Bus_ADT, Auto_ADT, Moto_ADT, Calle_ADT, Ruta_ADT, etc. Cada uno de estos últimos contiene a otro ADT: el auto, el bus y la moto contienen personas, la ruta contiene varias calles y la calle contiene buses, autos y motos. De este ejemplo se desprende que algunos contenedores, como el Bus_ADT, también pueden ser el elemento contenido en otro ADT. En general, un programa consta de sus ADTs, y de procedimientos que los manipulan para obtener el resultado esperado. Estos procedimientos son la "goma" que pega a los ADTs, y son los que contienen la "lógica" que implementa un sistema. Existen varios tipos importantes de ADTs contenedores, entre los que se destacan la pila, la cola, el arreglo, la lista, el árbol, el grafo y el conjunto. Algunos de estos ADTs forman parte intrínseca del lenguaje Pascal, que es el caso de los arreglos y los conjuntos de escalares, mientras que otros deben programarse en una unidad aparte, como en el caso de la lista o la pila. Estos ADTs contenedores son sumamente importantes, hasta el punto de que se han escrito muchos libros para describirlos y estudiarlos, pues prácticamente todas las estructuras de datos interesantes son trucos para implementar ADTs contenedores, o son mezclas de ellos. Por ejemplo, una multilista es un ADT en que cada objeto pertenece a varias listas. Entonces el mundo de los tipos de datos está dividido en dos grandes clases: los contenedores y los elementales. A veces un contenedor contiene a otro. Por ejemplo, puede hacerse una pila que contenga colas de árboles de listas de arreglos de matrices de personas. La gran ventaja de usar ADTs es que esta maraña puede definirse de una forma relativamente mecánica, usando cada ADT como un elemento contenido en otro ADT contenedor. 5. Implementación de Elem_T =========================== Es natural que los ADTs elementales tengan propiedades más simples que los contenedores, por lo que deben estudiarse primero. Para esto lo más simple es referirse a una implementación específica, que se presenta en los Listados 1 y 2. Estos listados contienen dos posibles implementaciones para la unidad Elem_T, que se usa para describir los datos contenidos en una pila. Esta última tiene su implementación en la unidad Stack_T, que se discute más adelante. Las operaciones de la unidad Elem_T son muy simples: inicializar un dato, almacenarle el valor correspondiente a un número entero, imprimirlo, copiar valores de y a variables de tipo Elem_ADT, escribirlo o leerlo de un archivo, etc. Estas operaciones son comunes a todos los tipos de datos, por lo que esta unidad puede usarse como plantilla para definir cualquier tipo abstracto de datos simple. ================================================================== Operaciones de un ADT Elemental PROCEDURE Init (VAR {-} e : Elem_ADT); PROCEDURE Clear (VAR {?} e : Elem_ADT); PROCEDURE Done (VAR {?} e : Elem_ADT); FUNCTION OK (VAR {+} e : Elem_ADT) {>>>>} : BOOLEAN; PROCEDURE Copy (VAR {?} x : Elem_ADT; VAR {+} y : Elem_ADT); PROCEDURE Move (VAR {?} x : Elem_ADT; VAR {?} y : Elem_ADT); FUNCTION Equal (VAR {+} x, y : Elem_ADT) {>>>>} : BOOLEAN; PROCEDURE Load (VAR {?} e : Elem_ADT; VAR {+} F: FILE); PROCEDURE Store (VAR {+} e : Elem_ADT; VAR {?} F: FILE); PROCEDURE Get (VAR {+} e : Elem_ADT; VAR {+} .......); PROCEDURE Put (VAR {?} e : Elem_ADT; VAR {+} .......); PROCEDURE Print (VAR {+} e : Elem_ADT); Figura 6 ================================================================== Es importante que cualquier ADT tenga, al menos, las operaciones definidas en la Figura 6 [Realmente este es un defecto del enfoque presentado en este artículo, pero removerlo requiere del uso de una gran cantidad de trucos que serán discutidos en un otro escrito]. De esta manera, ese ADT puede ser usado como el elemento contenido en cualquier ADT contenedor. Además, al incluir todas estas operaciones básicas se logra definir al ADT mejor, y se evita que la implementación quede incompleta. Por ejemplo, para definir Person_ADT pueden seguirse los siguientes pasos: Primero, copiar el archivo "Elem_T.pas" a "Person_T.pas", usando un comando del sistema operativo. Después basta sustituir (por medio del editor de texto) la palabra "Elem_" por "Person_" en toda la unidad Person_T. El siguiente paso es incluir en el registro llamado Rep_Person los campos relevantes a una variable de tipo Person_ADT (que podrían ser nombre, edad, sexo, etc.). Por último, el programador debe reprogramar las operaciones Copy, Move, etc., adecuadamente, en los casos que sea necesario. Con este artículo se incluyen dos posibles implementaciones para Elem_ADT: la del Listado 1 usa caracteres y la del Listado 2 usa números enteros. Las dos implementaciones de Elem_T son muy similares, pero no todas las implementaciones de operaciones son iguales: como los Reps son diferentes, las operaciones Get y el Put difieren notablemente. En una unidad que implemente un ADT contenedor los objetos de tipo Elem_ADT se obtienen únicamente por medio de las operaciones de la Figura 6. Esto permite reutilizar el código Pascal que implementa el ADT contenedor, pues como sólo usa esas operaciones de Elem_T, entonces el código fuente del ADT contenedor es independiente del código del ADT contenido, por lo que es muy fácil crear una nueva versión del ADT contenedor para un nuevo tipo de datos contenido. O sea, es posible crear una unidad, Stack_T por ejemplo, que implementa el ADT pila, y luego usar esa unidad como plantilla para obtener una pila de números reales, enteros, Person_ADTs, o de "pilas de colas de árboles de listas de arreglos de matrices de personas". Las operaciones de la Figura 6 son las que se necesitan para manipular los elementos contenidos en un ADT contenedor. Como una de las más importantes razones que justifican el uso de tipos abstractos de datos es el reutilizar componentes de programas, es muy importante que estas operaciones básicas de los ADTs elementales estén claramente especificadas y que formen parte de cualquier implementación de un ADT. De esta manera es posible reutilizar el código que implementa los diferentes ADTs contenedores, que son la base de todas las estructuras de datos que se usan en computación. Así se logra abaratar el proceso de programación, logrando al mismo tiempo una mejor calidad del producto obtenido. Las operaciones de Elem_T implican cierto sobretrabajo, pues como Pascal no cuenta con procedimientos que se desarrollen en línea, en ocasiones será más eficiente no usar una subrutina para implementar las operaciones del ADT. Por ejemplo, si Elem_ADT es un caracter, al copiarlo hay que invocar el procedimiento Elem_T.Copy(x,y), cuando sería mucho más rápido simplemente copiar el caracter "y" sobre "x" usando la asignación "x := y;". Esta operación Copy puede implementarse muy eficientemente, pues requiere tal vez de dos o tres instrucciones en lenguaje de máquina, y los consiguientes accesos a la memoria principal, pero como es necesario hacer un llamado a una subrutina para mantener la modularidad del ADT, el resultado es que Copy cuesta veinte o treinta instrucciones de máquina por ejecución. Por eso para incrementar la eficiencia es importante que el compilador pueda desarrollar en código en línea. La capacidad de poder definir exactamente un tipo de datos 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. Es este el precio que debe pagarse para lograr reutilizar código. Para un defensor de los ADTs es fácil afirmar que son pocos los casos en que este sobretrabajo afecta sensiblemente el rendimiento de un programa; es difícil estimar qué tan cercana a la realidad está esta afirmación. Pero si se acepta la heurística de que el 20% del programa es el que se ejecuta 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". Estas afirmaciones son producto de la intuición, que no ha sido verificada científicamente por el autor: seguramente las mejoras en los compiladores harán inatinentes estas preguntas. Lo mejor es usar desde ya abstracción de datos, aunque los compiladores que la soporten no estén todavía disponibles. Los lenguajes que tienen amplio soporte para ocultamiento de datos, como CLU [Liskov-86], ADA [Ichbiah-79] y Pascal Plus [Bustard-88], automáticamente generan algunos de las operaciones que se mencionan en Elem_T (con lo que también pueden evitar el sobretrabajo que significa el llamar a la subrutina que implementa cada operación). En C++, el uso de código que se expande en línea, que tiene el mismo efecto de los macros en C, elimina totalmente esta ineficiencia. En Pascal, si se necesita expander una subrutina en línea, por razones de eficiencia, el programador tiene que hacerlo manualmente. En general, para cualquier tipo de datos es necesario contar con todas las operaciones definidas en la Figura 6, salvo tal vez la operación Print y, en en casos muy calificados, Load y Store. A continuación se discuten en detalle cada una de estas operaciones. Cabe destacar que los nombres utilizados son los que Borland usa en sus ejemplos (e ir contra Borland, en estos momentos, es ir contra corriente...). Init(e): inicializa la variable "e", posiblemente usando memoria dinámica o dando valores a los campos del Rep del ADT. Muchos ADTs se implementan usando punteros que deben tener el valor apropiado antes de que puedan ser utilizados. La regla general, y casi absoluta, es que es vital que el programador inicialice todos los objetos o variables que usa. "Init" y "Done" son tan importantes que hasta tienen su propio nombre: son conocidos como constructores y destructores. La operación Init(e) puede implicar desde poner en "0" el Rep(e) hasta crear una complicada estructura de datos bajo "e". Debe hacerse exactamente un llamado a esta operación, preferiblemente al principio del procedimiento en que "e" esté definida. Además, si el espacio para "e" fue obtenido mediante la operación NEW, entonces inmediatamente después de esa invocación debe estar el llamado a Init. Init deja a su argumento en un estado inicial válido, listo para utilizarlo en cualquier operación. En el caso de objetos simples, como punteros o números, el Init puede limitarse a asignar a "e" un valor nulo, como NIL o cero. Pero si el Elem_ADT es una estructura complicada, el Init tiene la misión de dejar al objeto en un estado que le permita funcionar. Por ejemplo, puede que se asigne cierta memoria adicional a la variable "e" antes de que pueda ser utilizada, o que ciertos de sus campos tengan algunos valores especiales. Todas las operaciones de un ADT trabajan sobre objetos que han sido adecuadamente inicializados mediante Init. Todos los programadores conocen tan bien esta regla que lo usual es no mencionarla siquiera. No inicializar un ADT es un pecado mortal, hasta el punto de que el inicializar correctamente las variables es una de las primeras reglas que aprende cada programador. Como todo el mundo "sabe" esto, lo usual es no repetirlo en cada cláusula REQUIERE. Done(e): destructor para "e". Generalmente esta operación devuelve al sistema la memoria (dinámica) que ha sido asignada a "e". Done es el inverso de Init. Es una función totalmente terminante, pues deja completamente inservible el objeto "e", hasta el punto de que para volver a utilizarlo es necesario inicializarlo con Init. Init y Done son muy importantes principalmente para ADTs contenedores, aunque también deben incluirse estas operaciones para cualquier ADT elemental. Para toda variable debe hacerse exactamente una invocación a Done. Si la variable "e" está definida en un procedimiento, dentro del bloque de definición VAR, entonces debe haber un llamado a Done(e) al final del procedimiento. Si fue definida usando NEW, entonces el llamado a Done debe preceder inmediatamente al llamado a DISPOSE correspondiente. En algunos casos un programador diestro puede retardar el uso de Init, o adelantar el de Done: pero esto debe hacerse con sumo cuidado. La corrección de errores de programación que se derivan de usar objetos inadecuadamente inicializados es muy compleja, sólo secundaria en dificultad a la depuración de programas que utilizan procesos concurrentes (en [Bustard-88] esto se discute "grosso modo"). Desgraciadamente, en Pascal el programador debe ser muy disciplinado, hacendoso y organizado al inicializar y destruir cada instancia de un ADT, de tal modo que siempre incluya exactamente un llamado a Init y otro a Done para cada instancia de un ADT. De lo contrario el uso del ADT ocasionaría serios problemas. En C++ y Pascal Plus este problema no existe, pues el compilador se encarga de insertar en el código generado el llamado a Init (y Done) para cada variable. Un error muy común es usar una variable no inicializada, o devolver varias veces al sistema la misma localización de memoria. Stroustrup dice que C++ "soporta" la abstracción de datos, mientras que Pascal simplemente la "permite", pues en Pascal el programador debe ser "cuidadoso" y no olvidar invocar a los constructores y destructores, mientras que en C++ el compilador tiene la responsabilidad de hacer los llamados a Init y Done para cada variable que lo requiera. Clear(e): reinicializa la variable "e". El valor anterior de "e" se pierde, y su valor actual pasa a ser exactamente el que tenía después de que se ejecutó Init(e). O sea, que Clear es un Done suave, pues no inutiliza totalmente a "e", aunque si "borra" su anterior contenido. En muchos casos las tres operaciones Init, Clear y Done hacen exactamente lo mismo. Pero cuando el Elem_ADT es un poco complejo, puede que el ejecutar un Clear sea mucho más barato (en términos de tiempo de ejecución) que ejecutar un Done. Para evitar problemas, al programar un ADT debe usarse Done y Init sólo una vez en cada variable, y el Clear se debe utilizar cuando es necesario limpiar un objeto. Conceptualmente, el efecto de Clear es equivalente a un Done seguido inmediatamente de un Init. OK(e): esta operación verifica que la invariante del ADT se cumpla, sin cambiar el valor de la instancia. La invariante es un predicado, a veces expresado en forma matemática, que siempre se cumple para una instancia del ADT. Por ejemplo, en una lista la invariante puede ser que a cado nodo siguiente el apunta el anterior, y que la lista nula se representa como NIL. En este ejemplo, OK(L) será verdadero siempre que la lista L esté correctamente construida, y que también lo estén sus elementos. La operación OK es en general muy difícil de implementar, pues lo natural es que funcione aun cuando la instancia del ADT esté quebrada. La experiencia del autor es que arreglar un ADT roto es muy difícil, por lo que es mejor definir el OK como una operación que siempre retorna TRUE cuando la instancia del ADT cumple con su invariante, y cuando no es así hace "lo posible" por retornar el valor FALSE. Pero en este último caso puede ser que OK simplemente no pueda sobreponerse a la destrucción de la instancia del ADT, y el resultado sea un programa incorrecto o interminable. El autor ha tenido la tentación de definir una operación llamada FIX, que se encarge de des-quebrar una instancia de ADT que está quebrada. Pero parece que es conceptualmente impropio darle a un programador herramientas que le permitan ser descuidado al programar; mejor es exigir calidad en los programas. Sin embargo, existen muchas aplicaciones en que sería más fácil implementar programas robuztos si se cuenta con una operación como FIX. Copy(X,Y): este procedimiento retorna en X un duplicado del objeto Y. Al copiar objetos el programador desea que al modificar el objeto X no se modifique ni Y ni alguno de sus componentes. Esto significa que no hay memoria compartida por X y Y, pues estos dos objetos deben ocupar un espacio diferente en la memoria del computador. Lo primero que casi todas las implementaciones de Copy hacen es limpiar X invocando a Clear(X). Siempre que el programador escribe "X := Y;" en Pascal, el código generado por el compilador es duplicar, bit por bit, todo el contenido de la variable "Y" sobre la variable "X". Aunque no es el caso de las implementaciones de Elem_T en este artículo, muchas veces no es suficiente simplemente copiar bits, como lo hace una asignación de Pascal, para copiar un objeto. Por eso es muy importante que la unidad Elem_T contenga la operación Copy, que permite copiar un Elem_ADT sobre otro. Cuando se trabaja con objetos complejos, lo usual es que una parte de ellos esté en memoria dinámica. En estos casos hacer una copia superficial bit por bit de un objeto a otro no es suficiente. Para copiar estos objetos complejos, que son los más "interesantes", es necesario copiar no sólo las posiciones de memoria de una variable, sino todas las que están conectadas con ella, pero que aparecen en otra parte de la memoria. Por ejemplo, si el objeto por copiar es un árbol con una complicada estructura de punteros, al copiarlo habría que recorrerlo todo y reproducir cada uno de sus nodos y cada una de sus conexiones. Al copiar el árbol no basta sólo copiar la raíz, pues es necesario también copiar todos los nodos a ella conectados. Si para hacer el duplicado se usara la instrucción de asignación Pascal "X := Y;", se copiaría únicamente el nodo raíz, y el resultado sería dos nodos raíz que apuntan al mismo conjunto de nodos. No se obtendria en X una copia del arbol Y, sino dos raíces apuntando a los mismos descendientes, que no es lo que se quiere. Como la operación Copy no es trivial de programar, el programador debe ser cuidadoso al implementarla. Un error usual es implementar un Copy que no copia, pues no crea una instancia totalmente nueva de cada objeto. En estos casos puede que el programa funcione bien por mucho tiempo, hasta que llegue a una parte en que el no usar una copia produzca una falla. Lo malo es que estos errores son muy difíciles de detectar, pues la falla puede ocurrir mucho después de que la copia de un objeto se ha hecho. A veces hay que evitar copiar objetos, por el costo en uso de memoria y tiempo de ejecución que Copy implica. En el caso del árbol muchos veces no es necesario copiarlo completo, pues basta con trasladarlo de una variable a otra. En estos casos, tiene sentido usar el Move en lugar del Copy. Move(X,Y): Esta operación permite trasladar el objeto Y para que quede almacenado en la variable X. Los valores previos de X y Y se pierden irremisiblemente. El nuevo valor de X será el que Y tenía. El valor de Y será el de una variable que ha sido recién inicializada con Clear. De hecho, aparecen llamados a Clear(X) y Clear(Y) en casi todas las implementaciones de Move. En el caso de tipos de datos muy simples esta operación se implementa con una simple asignación (Copy). Pero la ventaja que tiene el Move sobre el Copy es que el primero puede tomar mucho menos tiempo para objetos muy grandes y de estructura muy complicada. Piense el lector en el caso del árbol mencionado anteriormente: trasladar el objeto de Y a X puede lograrse copiando únicamente el nodo raíz Y sobre X, y tal vez actualizando algunos punteros que antes apuntaban hacia Y para que apunten a X. El trabajo total sería mucho menor que el necesario para hacer un Copy completo. Además, muchas veces no se quieren tener varias copias del mismo objeto, sino que el objeto aparezca sólo una vez en la memoria. El Move puede verse como un truco de programación, que permite pasar un objeto de un lugar a otro de una manera rápida ("eficiente"). Es útil si se desea meter rápidamente dentro de un ADT contenedor un objeto, invalidando la copia original (posiblemente porque no se necesita más). Equal(X,Y): Retorna el valor TRUE cuando el objeto X es igual a Y. Existen al menos dos definiciones de igualdad. La más común es que dos objetos sean iguales cuando tienen el mismo valor: si X y Y son dos variables que contienen el número 3, entonces Equal(X,Y) será verdadero. Si Elem_ADT es un árbol o cualquier otra estructura de similar complejidad, entonces el procedimiento que determina igualdad podría exigir únicamente que los nodos de los árboles X y Y fueran "isomórficos", o que tuvieran cualquier propiedad por el estilo. En general es importante que la implementación de Equal sea "razonable", de forma que el programador usuario del ADT no necesite ver la implementación para adivinar si el concepto de igualdad implementado con Equal es el que él espera. Es posible ser más exigentes para definir igualdad. En Lisp existen dos funciones bien definidas a este efecto: (Eq X Y) es verdadero sólo cuando X y Y son punteros a la misma localización de memoria; (Equal X Y) es verdadero si los valores de X y Y son iguales. En la mayoría de las ocasiones la definición de igualdad que el programador necesita es la segunda. Load(X,F) y Store(X,F): Estas operaciones permiten almacenar en y recuperar de un archivo al objeto X. Necesariamente el programador usuario debe haber abierto el archivo F. De esta manera es posible escribir y restaurar X, lo que le brinda al programador usuario una gran flexibilidad para programar. En muchas ocasiones un programador necesita guardar el estado actual de una variable, pero su estructura de datos es tan complicada que opta por reconstruirla. Precisamente es ésta la razón que justifica programar estas dos importantes operaciones. Además, esta facilidad permite enviar, de una máquina a otra, copias de objetos, lo que es muy apreciado cuando se construyen programas realmente grandes. A primera vista parece que el implementar estas operaciones es tarea fácil. Este es el caso para ADTs simples, como enteros o números reales. Pero si el ADT tiene una intrincada estructura, como es el caso de un árbol o un grafo, entonces el programador deberá ser muy cuidadoso al almacenar las partes de X en F, pues debe asegurarse de que sea posible reconstruirlo adecuadamente. En el caso del compilador Turbo Pascal, necesariamente F debe ser un archivo sin tipo, pues el tamaño y forma del objeto X no puede determinarse de antemano. En estas implementaciones es prácticamente obligatorio el uso de los procedimientos BlockRead y BlockWrite de la biblioteca Turbo Pascal, como puede verse en los Listados 4 y 5. Para Modula-2 debe utilizarse la biblioteca respectiva, que depende de cada compilador. Las operaciones Load y Store de un ADT le permiten al programador usuario archivar en memoria permanente una instancia de un objeto. Pero no es razonable esperar que quien implementa un ADT también defina un sofisticado sistema de archivo para almacenar instancias del ADT, por lo que el programador usuario deberá hacerlo cuando así lo necesite (que posiblemente sea en muy pocas ocasiones). Por lo anterior, el programador usuario no debe esperar que F sea algo más que un archivo secuencial. Get(X,...) y Put(X,...): en general, estas dos operaciones permiten leer y cambiar los campos o componentes del ADT. En muchos casos se tienen muchas operaciones a este efecto, y lo usual es que un ADT contenedor nunca use estas operaciones del ADT contenido. Estas dos operaciones son las mejores candidatas para ser implementados en línea, pues generalmente lo que hacen es leer o cambiar un campo del Rep del ADT. Si un ADT tiene muchos campos, entonces necesitará muchas operaciones Get y Put: una pareja para cada campo. Como puede resultar tedioso definir tantos procedimientos, a veces se agrupa en uno sólo el acceso a varios campos, aunque esto implique una leve pérdida de eficiencia. Print(X): esta operación permite imprimir el objeto X. En los listados adjuntos se incluye, aunque en la práctica es mejor no incluir esta operación para el ADT, principalmente porque un objeto puede imprimirse de muchísimas formas diferentes. En general es difícil definir cómo debe imprimirse un ADT elemental. Una alternativa es que el programador usario use el Get para sacar cada campo relevante, y que luego lo imprima con Write y WriteLn. Otra es definir una unidad amiga del ADT, que contenga varias opciones diferentes de impresión para el ADT. Aún otra es definir una operación que transforme X en una tira de caracteres, o en un arreglo de tiras, que pueda luego ser desplegado cómodamente usando WriteLn. Es muy importante destacar que los ADTs contenedores generalmente usan todas las operaciones de la Figura 6 para manipular el ADT contenido, salvo Get, Put y Print. Es muy importante que todo ADT tenga definidas estas operaciones, pues de lo contrario, en algunos casos no podrá ser el elemento contenido en un ADT contenedor. Una sana regla para definir las operaciones de un ADT es incluir todas las mencionadas en esta sección, y otras que completen la implementación. Esto quiere decir que no debe dejarse por fuera una operación que luego obligue a un programador usuario del ADT a implementarla. Por ejemplo, si se implementa la unidad BCD_T, de números decimales, entonces sería un error dejar por fuera la función de comparación Less(X,Y), o alguna similar. Por la misma razón, es necesario que se implementen únicamente aquellas operaciones que puedan ser ejecutadas eficientemente, pues de lo contrario el programador usuario tendrá problemas con el rendimiento de su programa si usa el ADT. 6. Operaciones básicas de un ADT contenedor =========================================== ================================================================== Operaciones de un ADT contenedor PROCEDURE Init ( VAR {-} C : Cont_ADT); PROCEDURE Clear ( VAR {?} e : Cont_ADT); PROCEDURE Done ( VAR {?} C : Cont_ADT); FUNCTION OK ( VAR {+} e Cont_ADT ) {>>>>>} : BOOLEAN; PROCEDURE Copy ( VAR {?} x : Cont_ADT; VAR {+} y : Cont_ADT ); PROCEDURE Move ( VAR {?} x : Cont_ADT; VAR {?} y : Cont_ADT ); FUNCTION Equal ( VAR {+} x, y : Cont_ADT ) {>>>>>} : BOOLEAN; PROCEDURE Load ( VAR {?} C : Cont_ADT; VAR {+} F : FILE ); PROCEDURE Store ( VAR {+} C : Cont_ADT; VAR {?} F : FILE ); FUNCTION Empty ( VAR {+} C : Cont_ADT) {>>>} : BOOLEAN; FUNCTION Full ( VAR {+} C : Cont_ADT) {>>>} : BOOLEAN; PROCEDURE Insert ( VAR {?} C : Cont_ADT; VAR {+} e : Elem_ADT ); PROCEDURE Delete ( VAR {?} C : Cont_ADT; VAR {?} p : Pos_T ); PROCEDURE Retrieve ( VAR {+} C : Cont_ADT; {+} p : Pos_T ) {>>>>>} : Elem_P; FUNCTION Locate ( VAR {+} C : Cont_ADT; VAR {+} e : Elem_ADT ) {>>>>>} : Pos_T; PROCEDURE Print ( VAR {+} C : Cont_ADT ); Figura 7 ================================================================== Después de examinar las operaciones básicas de un ADT elemental, es interesante conocer las operaciones de los ADTs contenedores, que se muestran en la Figura 7. Obviamente, el ADT contenedor debe tener al menos las operaciones básicas de un ADT elemental, más otras operaciones para meter y sacar elementos del ADT, como son el Push y Pop en el caso de la pila, el En_Queue y De_Queue en la cola, o el Insert y Delete en el conjunto. Init y Done ya han sido discutidos ampliamente. Clear tiene más aplicación en el contexto de contenedores que de ADTs simples, pues en las implementaciones de los primeros con frecuencia es necesario mover elementos de un lugar a otro usando Move, por lo que debe usarse Clear con frecuencia. Como el tipo de datos por almacenar en un ADT contenedor no puede determinarse de antemano, el programador del ADT debe ser muy cuidadoso al programar las operaciones Init, Clear y Done, pues es relativamente difícil probar cada operación adecuadamente. ================================================================== PROCEDURE Clear( { EXPORT } { Adolfo } {-} VAR S : Stack_ADT ); VAR p,q : Rep_Stack; { PILA DE PUNTEROS } BEGIN { Clear } {==================} p := S.Rep; WHILE p <> NIL DO BEGIN q := p^.next; Elem_T.Done(p^.elem); DISPOSE(p); p := q; { evita usar p } END; S.Rep := NIL; END; { Clear } Figura 8 ================================================================== En la Figura 8 se muestra la implementación del Clear del ADT pila implementado por punteros. Antes de destruir un nodo de la lista de nodos, debe destruirse el elemento contenido. Si el elemento contenido fuera, a su vez, un ADT contenedor, entonces el Clear de la pila estaría iniciando una cadena de llamados para los destructores de los ADTs contenidos, lo que es necesario para recuperar toda la memoria asignada a ellos. Pero cabe destacar que en la implementación de una pila por medio de arreglos no se usa Elem_T.Done(), pues se limpia cada entrada de la pila con Elem_T.Clear(), como se muestra en la Figura 9. En este segundo caso el programador puede escoger entre dejar la pila en "estado Clear" o en "estado Done"; pero para la implementación por medio de punteros sólo cabe usar el "estado Done". ================================================================== PROCEDURE Clear( { EXPORT } { Adolfo } {-} VAR S : Stack_ADT { Pila a limpiar. } ); VAR i : INTEGER; { PILA DE VECTORES } BEGIN { Clear } {==================} FOR i := S.Rep.ultimo-1 DOWNTO 0 DO BEGIN Elem_T.Clear(S.Rep.elem[i]); END; S.Rep.ultimo := 0; END; { Clear } Figura 9 ================================================================== La implementación de la Figura 9 evita destruir y recrear cada elem[i] cuando se hace un Push o un Pop, pues mantiene toda la pila inicializada con todos los elem[i]'s en su estado vacío (Clear). El mantener los elem[i]'s inicializados puede requerir más memoria que si se mantuvieran en un estado no inicializado (que es el estado en que los dejaría Done). Pero de esta manera se evitaría llamar a Elem_T.Init para cada Push, y a Elem_T.Done en cada Pop, con lo que se cambia espacio por tiempo, para aquellos Elem_ADTs en que el estado Clear ocupe más espacio que el estado Done. El manejo de memoria dinámica tiene, en general, un costo significativo, por lo menos al compararlo con el uso de memoria en la pila de ejecución del programa. Esto es así porque el administrador de memoria dinámica (heap manager) debe mantener listas de espacio libre y espacio ocupado, las que deben ser recorridas para asignar o desasignar memoria. En una prueba informal hecha por estudiantes, se encontró que este tiempo es significativo en el caso del ADT pila, cuando deben efectuarse muchas operaciones Push y Pop. En esa evaluación informal, se generaron 20,000 operaciones Push y Pop, alternadas con otros operaciones de asignación de memoria dinámica, y el tiempo de corrida del programa que usó la implementación con punteros fue hasta dos veces mayor que el utilizado por el que usó la implementación de vectores. Si hay que hacer tanto malabarismo con constructores y destructores, ¿valdrá la pena el esfuerzo de aprender tantos detalles para usar ADTs? La razón primordial de usar ADTs es lograr una alta modularización, que permita reutilizar código. Para esto se necesita lograr que cada ADT sea independiente de los demás módulos que conforman un programa, lo que tiene por requisito el definir bien el papel de cada una de las operaciones básicas del ADT. El programador bisoño puede encontrar difícil digerir esta técnica (pues es difícil), aunque para él será difícil lo nuevo. El programar, definitivamente, no es para colegiales. Es una tarea difícil, reservada para profesionales. Al insertar un elemento en un ADT contenedor es necesario decidir si se usa el Elem_T.Copy o el Elem_T.Move. ¿Qué criterio debe usarse para escoger uno u otro? Obviamente la respuesta depende del contexto de programación, y es el programador usuario del ADT contenedor quien debe decidir cuál de las dos operaciones usar. En principio, el programador-usuario de un ADT contenedor debería poder escoger entre las dos alternativas, aunque el costo de implementar tanto flexibilidad puede ser prohibitivo. Lo perfecto, es, enemigo de lo bueno. Como puede verse en la implementación del la unidad Stack_T, en los Listados 4 y 5, en la implementación de la operación Push se usa el vocable "Elem_T.Copy{_Move}": entre llaves de comentario está la alternativa de usar Move por Copy para insertar un nuevo elemento en la pila. Si el programador usuario necesita usar el Move, basta que reemplace (usando un editor de texto) la tira "Copy{_Move}" por "Move{_Copy}", en todo el archivo Stack_T.pas, que contiene el código fuente del ADT pila. Load(X,F) y Store(X,F): La implementación del Load y Store en un contenedor necesariamente debe hacer uso de las operaciones Elem_T.Load() y Elem_T.Store(). Tal vez el mayor problema al grabar en F un contenedor es incluir ciertas marcas que permitan reconstruir el objeto salvado. Por ejemplo, en la implementación del Store de la pila se incluye un número de secuencia que permite determinar cuando se ha llegado al último elemento de la pila. Empty y Full son operaciones booleanas que permiten determinar si el contenedor está lleno o vacío. El siguiente grupo de operaciones permite insertar y borrar elementos del contenedor. La operación Retrieve recibe como entrada una posición, que es un indicador dentro del ADT contenedor, y que apunta a uno de sus elementos. Devuelve, no un objeto, sino más bien un puntero al objeto contenido en el ADT (pues el tipo regresado tiene el sufijo "_P"), para evitar hacer una copia del mismo. Para sacar un elemento del contenedor, debe usarse primero el Retrieve, luego el Copy o el Move, y por último el Delete (el valor de p después de la invocación queda indefinido). En algunos contextos pueden ser más elegante definir Retrieve como un procedimiento, y no como una función (que es el caso del Pop en Stack_T). El clásico ejemplo de un ADT contenedor es la lista, de la que se incluye un extracto de su especificación en el Listado 6. 7. Implementación del programa UsaPila ====================================== En esta sección se discute el código del programa UsaPila, que es el Listado 3. Este programa lee una tira y la invierte usando una pila. Lo importante en este ejemplo es demostrar la separación que existe entre la interfaz del Stack_T y su implementación. En UsaPila el mismo código corre tanto con la implementación de la pila por medio de arreglos, como con la de punteros. El lector puede hacer la prueba, sustituyendo una implementación por la otra. Lo único que cambia al trocar una implementación por la otra es la cantidad de tiempo de ejecución y de espacio requerido por el programa. El programa UsaPila está basado en el código para invertir una tira (Figura 4), pero no se supone que el tipo Elem_ADT es CHAR. Necesita que exista una unidad adicional, llamada Elem_T, en donde se define el ADT contenido en la pila, y en el que el Rep de Elem_ADT es CHAR. Lo importante es que el mismo código de la unidad Stack_T pueda ser usada para implementar el ADT pila con diferentes tipos de datos, mediante la recompilación las unidades Stack_T y Elem_T. Por ejemplo, para hacer una pila que almacene variables de tipo Person_ADT, basta que en el tipo Rep_Stack, el tipo Elem_ADT sea sustituido por Person_ADT. Lo más importante es que el código fuente que implementa la pila no sea modificado, aunque la nueva unidad si debe ser recompilada. Con esto se logra parametrizar el tipo de datos pila, pues la misma implementación de Stack_T sirve para diferentes tipos de datos. En la implementación de la unidad Stack_T, ya sea en la versión de punteros o vectores, se usa la operaciones Elem_T.Copy y Elem_T.Move para insertar un nuevo elemento dentro de la pila. 8. Instanciación de Stack_T =========================== ¿Cómo logra un programador obtener una pila, ya no de enteros o caracteres, sino de matrices, o vectores? ¿Cómo obtener una pila de pilas de personas (o sea, una en la que los elementos contenidos sean a su vez pilas de personas)? Lo único que el programador debe hacer para esto es instanciar dos copias del archivo Stack_T.pas, que contiene el código que implementa el ADT pila, para el nuevo tipo de dato contenido. Para obtener un nuevo tipo de datos de contenedor, el programador debe copiar uno o varios archivos, y sustituir unos identificadores. Este proceso se conoce como instanciar un ADT, y es un proceso automático en lenguajes como CLU, ADA y Pascal Plus (el término instanciación también se utiliza cuando se crea una variable en memoria dinámica: indica obtener una nueva instancia de un tipo de datos). En Turbo Pascal el programador debe instanciar manualmente sus ADTs. La instanciación del archivo Stack_T.pas se logra copiando el código de "Stack_T.pas" a dos nuevos archivos: "SS_Per_T.pas" (pila de pilas de personas), y "S_Per_T.pas" (pila de personas). En el archivo "SS_Per_T.pas" es necesario sustituir, por medio del editor, la tira de caracteres "Stack_" por "SS_Per_", y "Elem_" por "S_Per_". En el archivo "S_Per.pas" debe sustituirse "Stack_" por "S_Per_" y "Elem_" por "Person_". Como "Elem_T.pas" es una plantilla para cualquier ADT elemental, para obtener el Person_ADT basta copiar el archivo "Elem_T.pas" a otro, llamado "Person_T.pas", sustituir "Elem_" por "Person_", y luego reprogramar todas las operaciones básicas de un ADT elemental, si fuera necesario. ================================================================== Instanciación de un contenedor usando el editor { PARAMETERS (Stack_T Stack_ADT Stack_P [SSize]) (Elem_T Elem_ADT) } PLANTILLA Pila de Pilas Pila de Personas Stack_T.pas: SS_Per_T.pas S_Per_T.pas Stack_ ----> SS_Per_ Stack_ ----> S_Per_ Elem_ ----> S_Per_ Elem_ ----> Person_ ElemT.pas: Person_T.pas Elem_ ----> Person_ Figura 10 ================================================================== La Figura 10 es un diagrama de las sustituciones que se necesitan hacer en el archivo Stack_T.pas y Elem_T.pas. Estos archivos son plantillas que permiten utilizar el ADT que implementan, por medio de la instanciación de identificadores. Los identificadores a sustituir manualmente mediante el editor en un archivo que contiene la implementación de un ADT contenedor son los que aparecen baja el encabezado PARAMETERS, como se muestra en las Figuras 3 y 10. En el párrafo anterior se mencionan las sustituciones más importantes para instanciar el Stack_T, pues deben sustituirse todos los identificadores listados bajo PARAMETERS. Si en el ejemplo de la pila de pilas de personas se usa la implementación del Listado 4, que usa vectores, también será necesario darle un valor a la constante SSize, que no aparece del todo en el Listado 5 (pila con punteros). Como el proceso de instanciar un ADT contenedor es manual, el programador debe, de nuevo, ser "cuidadoso" al hacerlo, para evitar errores. La ventaja es que éste es un procedimiento muy simple, que no requiere pensar mucho, por lo que la costumbre de hacerlo evitará que se cometen errores. (Aunque ya los compiladores de ADA lo hacen automáticamente por medio de tipos genéricos, es difícil que llegue el día en que estas facilidades sean ampliamente disponibles para Pascal). Como en la implementación de Stack_T se usa el procedimiento Copy del ADT contenido, y no el ":=" del compilador de Pascal, entonces cada vez que es necesario copiar elementos se hace de la forma correcta usando S_Per_T.Copy o SS_Per_T.Copy: cada uno de estos Copys "sabe" copiar adecuadamente (pues de hecho llaman al Copy del elemento contenido). Lo mismo puede decirse de todas las demás operaciones que manipulan al elemento contenido. Es por esto que el mismo código programado en Stack_T.pas puede utilizarse para implementar pilas de cualquier tipo de datos, aun cuando el ADT contenido sea una estructuras de datos altamente complicada. Si se necesita una pila de enteros, basta usar, en lugar de la unidad Elem_T, una en que el Rep sea un entero. Si se necesita una pila de "pilas de personas", entonces el Rep en el sustituo de Elem_T deberá ser "pilas de personas": S_Per_T. En los Listados 4 y 5 se incluye el código Pascal que implementa el tipo abstracto de datos pila usando arreglos y punteros, que son las dos formas clásicas de hacerlo. Como es lógico, cada implementación de Stack_T se programa diferente (NEW sólo se usa en la implementación con punteros), pero la interfaz de ambas implementaciones es exactamente la misma. Esto quiere decir que el programador usuario del ADT puede utilizar cualquiera de las dos implementaciones en su programa, con el objetivo de que use aquella que lo haga más eficiente. Lo importante es que este afinamiento de la eficiencia del programa se hace en un sólo módulo, que es la unidad Stack_T. Esto quiere decir que efectivamente se está logrando que cada ADT sea una barrera protectora para un tipo de datos, lo que ayuda a que el programa producido sea más robusto y que sea más fácil darle mantenimiento. UsaPila ha sido diseñado para que pueda utilizar cualquiera de las versiones de Elem_T de los Listados 1 y 2, para lo que utiliza el procedimiento Elem_T.Put. El lector puede comprobar que si cambia una versión de Stack_T por la otra, o de Elem_T por lo otra, UsaPila continúa haciendo exactamente lo mismo. Lo que este ejercicio muestra es que los tres módulos Elem_T+Stack_T+UsaPila son realmente independientes, pues de hecho UsaPila puede implementarse de cuatro formas diferentes. Las diferencias entre las dos implementaciones de Elem_T son muy pequeñas. Las variaciones se dan únicamente dentro la unidad Elem_T, por lo que no afectan a la unidad Stack_T (haga el lector la prueba, cambiando una versión de Elem_T por la otra: el resultado obtenido es el mismo). Precisamente 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 de datos da dividendos cuando se le da mantenimiento a los programas. 9. Polimorfismo: uso de referencias a objetos ============================================= Una pila es un tipo abstracto de datos que contiene elementos de otro tipo. Por ejemplo, en un programa puede usarse una pila que contiene números enteros, y otra de caracteres. Este segundo tipo puede verse como un parámetro necesario para definir el tipo de datos pila. En la Figura 3 se incluye la cláusula PARAMETERS que sirve, precisamente, para indicarle al programador cuáles son los identificadores, dentro de la unidad Stack_T, que debe utilizar para definir el tipo de datos contenido en la pila. Cabe destacar que es muy usual que un ADT sea definido en término de otro u otros: lo natural al hacer programación por objetos es crear una red de ADTs y procedimientos que conforman juntos el programa. En la Figura 3 la declaración del los procedimientos Push y Pop, y también la del tipo Rep, necesitan que el programador haya definido una unidad llamada Elem_T que contenga un ADT llamado Elem_ADT. Elem_T contiene la declaración de los tipos de objeto que el programador desea almacenar en su Stack_ADT. Esta parametrización del tipo Elem_ADT evita amarrar el Stack_T a un tipo de datos, pues la misma implementación de Stack_T sirve para cualquier tipo de datos Elem_ADT. Al parametrizar el tipo Elem_ADT en la definición de Rep se logra que la misma unidad, Stack_T en este caso, sirva para producir varios tipos de pila. Por ejemplo, si Elem_ADT es un número real, el resultado de compilar Stack_T será una pila de números reales; si es un entero, lo será de enteros. Lo interesante es que basta copiar y recompilar la unidad Stack_T para obtener una pila de uno y otro tipo. A diferencia del lenguaje ADA, que tiene un amplio soporte para parametrización de módulos por medio de los paquetes genéricos, en Pascal el programador debe hacer uso de un editor de texto para producir, con base en una unidad que implementa un ADT parametrizado, una instanciación del ADT para el tipo abstracto de datos. El proceso es relativamente simple, pero no es automático, y tiene la desventaja que se obtiene una nueva unidad, que contiene una copia completa del código de la unidad. Por ejemplo, sería muy cómodo que en Pascal el programador pudiera declarar una pila con capacidad de 350 números enteros de la siguiente manera: VAR s_int : Stack_ADT. Esto implicaría que el tipo Elem_ADT sería INTEGER, y que el valor de la constante SSize debe ser 350, y no 20000 como aparece en la Figura 3. Si el programador necesitara, en el mismo programa, una pila de números reales con capacidad de 50 número, la declararía así: VAR s_real : Stack_ADT. En ADA el compilador se encarga de sustituir en cada caso el identificador Elem_ADT por INTEGER o REAL; en Pascal el programador debe hacerlo usando un editor de texto. Más aún, en Pascal el programador deberá hacer dos copias de la unidad Stack_T, llamadas, por ejemplo, StackI_T y STackR_T, en las que luego sustituya el identificador Elem_ADT por INTEGER en el primero caso, y REAL en el segundo. Así obtendrá dos copias de la unidad, una para cada tipo de datos. El programador también debe producir dos unidades llamadas ElemI_T y ElemR_T, que contengan las operaciones que las unidades StackI_T y STackR_T necesitan: el proceso es simple, tedioso, y requiere que el programador sepa lo que está haciendo. Esta duplicación innecesaria de código es una limitación del truco de programación expuesto en este artículo para usar abstracción de datos en Pascal. Pero no es el unico. La técnica del Rep permite definir un ADT en términos de otro. Pero tiene la gran desventaja de que un objeto no puede estar en más de un contenedor. Por ejemplo, si Elem_ADT corresponde a un registro de Person_ADT, entonces esa persona no puede estar en más de una lista. Lo que puede hacerse es tener, en varias instancias del ADT lista, copias del mismo registro de la persona, pero no es posible que el mismo registro se encuentre en todas las listas. La solución a estos dos problemas es usar punteros. En CLU se habla de semántica de referencia para decir que 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. Usando punteros es posible meter en varios contenedores el mismo objeto, y si se le cambia de alguna manera, entonces el cambio será visible desde todos los punteros que lo referencian. Existe otra gran ventaja al usar punteros. Independientemente del objeto referenciado, un puntero tiene siempre el mismo tamaño. Esta ventaja la aprovecha Modula-2 para definir sus tipos "opacos". Esto implica que el compilador no tiene problemas al asignar memoria para una variable que es un puntero, lo que resulta en una gran flexibilidad para definir ADTs en términos de otros ADTs. Además, la operación Move se implementa simplemente como una asignación de puntero. Las convenciones expuestas en este artículo se basan en que los objetos de tipo Rep_Stack y Stack_ADT tiene exactamente el mismo tamaño, lo que permite usar la transferencia de tipos, pues el compilador debe saber cuánta memoria reservar para una instancia de cada ADT. La capacidad de definir un tipo abstracto de datos en término de otro, o de varios otros, se conoce en el ámbito de la programación por objetos como parametrización. La idea principal es que el tipo del ADT contenedor sea independiente del tipo del ADT contenido, hasta el punto de que varias instancias del contenedor puedan hacer uso del mismo código que implementa cada operación. En este sentido, el ADT contenido es un parámetro que sirve para definir al ADT contenedor. Como se verá más adelante, ésto es más difícil de hacer si el objeto en sí, y no una variable que le apunta, es lo que está almacenado en la instancia del tipo contenedor, básicamente porque objetos diferentes tienen tamaños y operaciones diferentes. Si se implementa la parametrización usando punteros a los objetos contenidos en el ADT, entonces el código de las operaciones del ADT contenedor puede ser compartido por todos las instancias del tipo contenedor. Por ejemplo, si el contenedor es una lista, entonces todas las listas usarán el mismo procedimiento Insert o 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 lo que sea. En la implementación de List_T no haría falta saber el tipo de Elem_ADT, pues para insertar o borrar en la lista bastaría insertar o borrar un puntero. Por lo mismo no sería necesario usar procedimientos de Copy y Move especiales para cada tipo contenido: basta copiar punteros para lograr el efecto de insertar o borrar un objeto contenido en el ADT parametrizado. Se llama polimórfico al tipo abstracto de datos contenedor en que todas sus instancias comparten el código que implementa cada una de las operaciones del ADT, independientemente del ADT contenido. El concepto de parametrización es más general que el término polimorfismo, pues al usar el segundo en general se sobreentiende que la implementación del ADT contenedor usa punteros a los objetos contenidos. En cambio, si un lenguaje realmente soporta parametrización de tipos, como es el caso con ADA y CLU, entonces la implementación del ADT no necesariamente usará punteros. En el caso específico de ADA es posible crear tipos de datos contenedores que no usan punteros a sus objetos mediante el uso de paquetes genéricos; en estos casos el compilador se encarga de crear varias copias del código necesario para implementar cada operación, en aquellos casos en que es necesario hacerlo. Si un ADT es polimórfico, entonces todas las operaciones del ADT pueden usarse en cualquiera que sea el objeto contenido, pues se implementan moviendo y copiando punteros. O sea que en mucho polimorfismo significa implementar parametrización usando punteros. Parametrización implica el definir una ADT en términos de otro. Estos dos conceptos están muy ligados a la forma en que pueden ser implementados: el polimorfismo permite compartir código, y la parametrización permite definir módulos que usan tipos como si fueran argumentos. Los dos conceptos son complementarios pues permiten la reutilización de componentes de programas. El precio que tiene la flexibilidad de usar polimorfismo es que debe agregarse a la memoria usada por cada objeto el espacio usado para almacenar su puntero. Además, para accesarlo debe hacerse una indirección adicional. Pero cuando el mismo objeto debe aparecer en varios contenedores, lo que es usual en muchos programas, no queda más que usar punteros, lo que además cubre el costo de usar polimorfismo. Otro problema con el polimorfismo es que las operaciones Load y Save deben implementarse de manera diferente, pues de nada vale almacenar en disco una cadena de punteros a objetos contenidos en memoria real. Esto se resuelve fácilmente, almacenando los objetos y no sus punteros. Pero si un objeto está en más de un contenedor, y varios contenedores son almacenados en el disco, cuando sean recuperados se obtendrán varias copias del mismo objeto (una diferente para cada contenedor). Este problema no tiene solución, pero pocas veces necesita el programador guardar tan complicadas estructuras. (Una manera ruda de solucionar este programar, es almacenar en el disco todo el contenido de la memoria). Pero ahora surge otra dificultad al usar polimorfismo en el ámbito de Turbo Pascal: el programador debe invalidar la verificación de tipos al usar las operaciones del ADT, que contendrá punteros genéricos, compatibles con cualquier tipo de puntero. O sea que el compilador no verificará, por ejemplo, que en una pila de enteros se metan punteros a números reales. Es efectivamente posible escribir un programa que meta en una pila polimórfica tanto enteros como caracteres. Si no hay verificación de tipos, el programador debe ser muy cuidados al usar ADTs polimórficos. Si se mezclan diferentes tipos de punteros en la misma pila polimórfica, es necesario que en todo momento el programa "sepa" que tipo de dato esperar. Para esto lo usual es incluir un campo en el Rep de Elem_ADT que indique el tipo del objeto contenido. No es usual mezclar en el mismo contendor tipos "muy" disímiles. Cuando se hace programación por objetos, es usual usar listas que tienen varios objetos que difieren poco unos de otros. Por ejemplo, un programa puede manipular una la lista de figuras geométricas, en que sus partes internas difieran poco unas de otras. Lo malo es que para lograr esto cómodamente es necesario usar dos técnicas que son muy difíciles de simular en Pascal: herencia y funciones virtuales. La programación por objetos es, básicamente, usar ADTs polimóricos para accesar contenedores de elementos similares que se han obtenido unos de otros mediante de herencia de tipos. En [Stroustrup-88] se discute en detalle ésto. ================================================================== UNIT StackI_T; { Interfaz de enteros para la pila genérica } INTERFACE TYPE INTEGER_P = INTEGER; { Puntero a enteros } {...} IMPLEMENTATION USES Stack_T; { Pila Polimórfica } {...} PROCEDURE Push_INTEGER( { EXPORT } { Adolfo } {?} VAR s : Stack_ADT; { Pila a procesar } {+} e : INTEGER_P { Puntero a un entero } ); { RESULTADO Mete el entero apuntado por e en la pila s } BEGIN { Push_INTEGER } Stack_T.Push(s, POINTER(e)); END; { Push_INTEGER } {...} END. Figura 11 ================================================================== Si se desea evitar perder el chequeo de tipos al usar polimorfismo en Pascal, entonces basta definir una unidad que haga la transformación de punteros para cada tipo contenido en el ADT. En la Figura 11 se muestra la operación Push_INTEGER, que recibe un puntero, y lo transforma a un puntero a enteros antes de llamar al procedimiento genérico Push del ADT Stack_T. El problema ahora estriba en que para ejecutar la operación Push de la pila se necesitan dos llamados... Si Pascal, como C++, permitiera la sobrecarga de identificadores y procedimientos que se desarrollen en línea, este sobretrabajo prodría evitarse. Casi que dan ganas de escribir un preprocesador de Pascal que elimine este sobretrabajo, como ya ha sido hecho en el caso de C++. 10. Parametrización: objetos de tamaños diferentes ================================================== Después de discutir el concepto de polimorfismo, es posible discutir más a fondo la parametrización de tipos sin usar punteros. Para esto hay que estudiar la Figura 12, en que se presentan dos instancias del ADT pila, una de enteros y la otra de caracteres. En este ejemplo se presentan dos instanciaciones diferentes de la "misma" pila con objetos de diferentes tipo. Como en el Rep de la pila se menciona a Elem_ADT, entonces los tamaños de cada pila son diferentes. Más aún, ya se ha visto que el copiar objetos de tipo Elem_ADT puede no ser trivial, por lo que el programador usuario del ADT pila debe haber definido en Elem_T operaciones que permitan copiar instancias del tipo Elem_ADT. Estas operaciones se usan para insertar en la pila copias de los objetos a almacenar. Por ejemplo, en el caso del ADT pila cuya implementación aparece en los Listado 4 y 5, las operaciones Push, Pop, etc., usan el Copy o Move definido en Elem_T. Como contraste, la implementación polimórfica del ADT pila no necesitaría hacer referencia a esos procedimientos. ================================================================== S1 S2 +------------------+ +----------------------+ | | | | | +---+---+ +---+ | | +---+---+ +---+---+ | | | 3 | | A | | | | 2 | | 3245 | | | +---+---+ +---+ | | +---+---+ +---+---+ | | | | B | | | \----->| 7880 | | | | +---+ | | +---+---+ | | \----->| D | | | | | | | +---+ | | +---+---+ | +------------------+ +----------------------+ StackC_T [CHAR] StackI_T [INTEGER] 2 + 3*1 = 5 Bytes 2 + 3*2 = 8 Bytes ElmCHR_T.pas ElmINT_T.pas Figura 12 ================================================================== La Figura 12 muestra como se ve la memoria si se implementa, por medio de un arreglo, una pila de caracteres versus una de enteros. La disposición de los elementos en la memoria es, básicamente, la misma. Pero una variable de tipo StackC_ADT (pila de caracteres) ocupa 5 bytes, mientras que una de tipo StackI_ADT (pila de enteros) necesita 8. El código generado por el compilador para un tipo de pila no sirve para manipular el otro tipo. Es por esto que si el programador necesita usar dos tipos de pila en su programa, deberá entonces usar dos unidades que diferirán únicamente el en tipo de datos que usan: una usará enteros y la otra caracteres. Sin embargo, la lógica plasmada en la implementación de ambas unidades será exactamente la misma. El polimorfismo es muy utilizado precisamente porque al usarlo se puede evitar esta proliferación innecesaria de copias del mismo código. Las diferencias entre StackC_T y StackI_T son realmente muy pequeñas, y sus operaciones son prácticamente iguales. Pero como StackC_ADT y StackI_ADT tienen tamaño diferente, el compilador debe tratarlas diferente. Es posible que ambos tipos puedan utilizar las mismas operaciones, pero efectivamente lograr esto es difícil. Requiere usar punteros a procedimientos para ejecutar las operaciones del ADT contenido. Por ejemplo, debe haber un procedimiento Copy para enteros y otro para caracteres, de forma que cuando se invoque a Copy se haga de forma indirecta a través de ese puntero. Cada instancia del Stack_T debería mantener una tabla con los punteros a los procedimientos necesarios para manipular el ADT contenido. En ADA se puede usar paquetes genéricos para implementar el ADT pila. En ese caso, el compilador de ADA sabe que un tipo parametrizado necesita definir objetos que tienen diferente tamaño, y diferentes operaciones. Quiere esto decir que el mismo código para un tipo de datos se podría usar para diferentes tipos de Elem_ADTs. El compilador de ADA es quien se encarga de hacer la copia de un módulo, si es necesario, y de coordinar el acceso a los Elem_ADTs por medio de sus operaciones. En Pascal, que es un lenguaje que no soporta paquetes genéricos, el programador debe hacer la copia "a pie". El lector astuto puede ahora ver que es posible implementar en Pascal un ADT parametrizado que no sea polimórfico. Para crear el tipo abstracto de datos pila que permita almacenar objetos de diferente tamaño, es necesario que el programador usuario del ADT provea, al usar la operación Init de la pila, direcciones a los procedimientos que implementen todas las operaciones básicas del ADT contenido, como Copy y Move del Elem_ADT, y también el tamaño del Elem_ADT (SizeOf(Rep)) como se muestra en la Figura 13. S_chr es una pila de caracteres, y S_int de enteros. Ambas variables son del mismo tipo: Stack_ADT. La diferencia estriba en los procedimientos mencionados en el Init. Dentro de Stack_T.Rep debe haber espacio para guardar las direcciones de las del operaciones del Elem_ADT almacenado en la pila. ================================================================== TYPE CONST SSize = 500; { tamaño de la pila } Rep_Stack = RECORD ult, size : INTEGER; { ultimo byte usado, SizeOf(Elem_ADT) } elem : ARRAY[1..SSize] OF BYTE; { contenido de la pila } { Punteros a las operaciones de Elem_ADT } P_Init, P_Clear, P_Done : PROCEDURE(VAR e); P_Copy, P_Move : PROCEDURE(VAR x; VAR y); P_Equal : FUNCTION (VAR x; VAR y) : BOOLEAN; END; { Rep } Stack_ADT = RECORD Rep : Rep_Stack; END; VAR S_chr, S_int : Stack_ADT; BEGIN Init(S_chr, SizeOf(INTEGER), Int_Copy, Int_Move, {.....}); Init(S_int, SizeOf(CHAR), Chr_Copy, Chr_Move, {.....}); END; Figura 13 ================================================================== La implementación del Stack_T mencinado en la Figura 13 es necesariamente mucho más complicada que la de los Listados 4 y 5, pues es necesario manejar, a nivel de byte, la memoria asignada. ================================================================== PROCEDURE Push( { EXPORT } { ADOLFO } {?} VAR S : Stack_ADT; { Pila polimórfica } {+} VAR e { argumento SIN tipo } ); { RESULTADO Agrega a la pila S el elemento e. } { REQUIERE Que S no este llena ( Full(S)=FALSE ) Todos los elementos "e" deben ser del mismo tamaño: Rep(S).size. } BEGIN { Push } IF (S.Rep.sultimo+S.Rep.size) < SizeOf(Rep) THEN BEGIN S.Rep.P_Copy{_Move}(S.Rep.elem[S.Rep.ultimo], e); S.Rep.ultimo := S.Rep.ultimo + S.Rep.size; END; END; { Push } Figura 14 ================================================================== Por ejemplo, al hacer un Push en S_chr, por el valor del argumento SizeOf(Chr_T.Rep_Chr) se sabe que debe incrementarse en uno el puntero al último byte usado, y luego se procedería a insertar el caracter en la pila usando el procedimiento P_Copy (esta variable es un puntero al procedimiento que "sabe" cómo copiar caracteres). En el caso de S_int, el incremento se haría de dos en dos. Como es lógico, caben más caracteres que enteros en el mismo espacio, por lo que la capacidad de S_chr será la mitad de S_int, dado que ambas variables tienen diferente tamaño. La Figura 14 muestra un extracto de la operación Push de esta pila, que es polimórfica (pues se usa el mismo código para implementar todas las operaciones de cualquiera de las instancias de la pila) pero que no almacena punteros a los objetos que contiene. La mayoría de los lenguajes que permiten parametrización la implementan por medio de punteros (o sea, que realmente lo que hacen es polimorfismo pero sin abandonar la verificación de tipos). Uno de los factores que han contribuido significativamente a para que no existan muchos compiladores de ADA es que permite módulos genéricos. Como se ha demostrado aquí, en Pascal es posible implementar tipos genéricos, pero el peso del trabajo recae sobre el programador. En ADA, el compilador debe ser muy complejo para evitarle todas estas molestias al programador. El uso de estas sofisticadas técnicas de polimorfismo, requiere de un alto dominio de la técnica aquí expuesta. El programador bisoño no debe usarlas, y si lo hace debe ser muy cuidadoso. Si algo es muy difícil de hacer, es más probable que no resulte correcto. Existen entonces varios niveles de parametrización: la mayor flexibilidad se obtiene un tipo contenedor puede contener diferentes tipos de datos. Un ejemplo de esto sería una una instancia del ADT lista que pueda contener tanto números enteros como caracteres, personas e inclusive otras listas. El siguiente nivel de flexibilidad se da usando polimorfismo y el último nivel se alcanza cuando la implementación del ADT contiene los objetos, y no punteros a ellos. Recapitulando, la parametrización es la flexibilidad de usar el mismo tipo abstracto de datos para diferentes tipos de datos. Es una facilidad de un lenguaje que permite que la definición de un tipo reciba como parámetro a otro tipo. La más cómoda implementación de parametrización se logra por medio de polimorfismo, en que se logra compartir código almacenando punteros a objetos. El polimorfismo es la base de los lenguajes que soportan programación por objetos. 11. Anidamiento de ADTs ======================= El anidar un ADT dentro de otro es muy importante, pues permite definir un ADT en términos de otro. Todos los contenedores tienen un ADT anidado. Pero al anidar ADTs en Turbo Pascal se debe resolver un serio problema de referencia circular de unidades. Para la exposición es conveniente utilizar un ejemplo. Al implementar el ADT árbol, en donde cada nodo tiene una lista de sus hijos, se encuentra el siguiente problema. - El árbol necesita usar a la lista, pues los punteros a sus nodos hijos deben estar almacenados en una lista. - La lista necesita usar al árbol, pues la lista de cada nodo contiene los punteros a los nodos hijos, que son árboles. ================================================================== UNIT Tree_T; UNIT Tlist_T; USES Tlist_T, Elem_T USES Tree_T; TYPE TYPE Rep_Tree = RECORD Rep_Tlist = RECORD e : Elem_ADT; n : INTEGER; h : Tlist_ADT; {<<**>>} e : ARRAY [1..LSize] OF Tree_ADT; END; END; Tree_ADT = RECORD Tlist_ADT = RECORD Rep : Rep_Tree; Rep : Rep_Tlist; END; END; Figura 15 ================================================================== Como se muestra en la Figura 15, lo que sucede entonces es que hay una referencia circular entre las unidades Tree_T y Tlist_T, que puede resolverse de varias maneras: - Usar polimorfismo: El campo de tipo Tree_ADT en el Rep de Tlist_ADT puede definirse como POINTER, de forma que la unidad Tlist_T no necesite usar a Tree_T, pues ya "sabe" que el Rep en Tree_T es un puntero. - Se puede sacar la definición de Tree_T.Rep a un archivo especial, Tree_T.Rep, e incluirlo (usando {$INCLUDE Tree_T.Rep}) tanto en Tree_T.pas como en Tlist_T.pas. Esta segunda solución es fea, pues todo el código que implementa el ADT árbol deja de estar contenido en un sólo archivo. La primera solución parece más elegante, y ha sido utilizada por el autor para implementar Tree_T con base a List_T: el chequeo de tipos en este caso es un impedimento para lograr la modularidad del programa. Como Pascal realmente no soporta ADTs, el programador debe estar pendiente de todo lo que hace, so pena de terminar con una maraña realmente complicada. 12. Convenciones para implementar ADTs con unidades =================================================== Las convenciones que se deben usar para implementar ADTs, que han sido básicamente expuestas en los ejemplos, son las siguientes: - Cada ADT estará contenido en una unidad. Es válido que un ADT haga uso de otro. - En la parte de interfaz de la unidad deben listarse la declaración del tipo del ADT y sus operaciones. Para esto debe incluirse únicamente el nombre de cada procedimiento y sus argumentos, sin copiar las cláusulas REQUIERE o RESULTADO que forman parte de la especificación. - Debe incluirse en la sección de PARAMETERS una indicación de los identificadores que deben usarse para obtener una instancia del ADT, si es necesario. El programdor usuario luego puede sustituir esos identificadores por los que necesita al instanciar el ADT. La idea es que cada ADT sea un plantilla base para el programador usuario. - El nombre de la unidad que implementa un ADT debe terminar en "_T" (por tipo), y el nombre del ADT tendrá la terminación "_ADT". Por ejemplo, para una pila el nombre de la unidad es Stack_T y el del tipo de datos es Stack_ADT. - La representación interna del ADT debe definirse usando el identificador Rep. En los ejemplos que se incluyen en este escrito se resaltan en un cuadro los campos del Rep. - Cada procedimiento que sea una operación del ADT tendrá la anotación EXPORT, que así lo indica, y también el nombre del programador que lo escribió. - El primer argumento de todas las operaciones de un ADT debe ser la instancia sobre la que se opera. Todas estas variables debe pasarse como parámetros de referencia (VAR). - Para definir una instancia del ADT, el programador usuario debe utilizar el identificador cuyo sufijo es "_ADT". - Es conveniente incluir en la sección de implementación de la unidad una explicación detallada de cómo se interrelacionan todos los datos y campos que forman el ADT. El uso de dibujos puede ayudar mucho en esta documentación. - Como es usual que cada ADT tenga operaciones llamadas Init y Done, que sirven para inicializar y destruir cada instancia del ADT, es importante que al usar el ADT estos identificadores estén cualificados con el nombre de la unidad a la que pertenecen, no vaya a ser que el compilador tome un nombre por otro. Esto es difícil que ocurra, pues generalmente estas operaciones tiene parámetros diferentes. - Si una operación puede implementarse de forma simple con base en otras, es mejor eliminarla de la implementación. Sin embargo, debe incluirse todas las operaciones necesarias para manipular adecuadamente las instancias del ADT. Las operaciones del ADT deben estar completas. - Deben incluirse todas las operaciones básicas para el ADT, de forma que el programador usuario no se vea obligado a cambiar el ADT para usarlo. El lector ya debe haber notado que no todos los argumentos para las operaciones de un ADT son siempre necesarios. Por ejemplo, en algunas implementaciones de la lista usando punteros Insert(e,L) no necesita usar la variable L. Pero en la implementación de listas usando vectores es necesario usar L. Para lograr consistencia al implementar ADTs, es necesario siempre incluir como argumento el objeto sobre el que actúa la operación. El omitir estos argumentos "innecesarios" es contraproducente, pues hace la interfaz del módulo dependiente de la implementación. Todas estas reglas pueden entenderse bien en el contexto de un ejemplo completo. Para eso se incluyen dos implementaciones diferentes del ADT pila en los Listados 4 y 5: la primera implementa la pila con vectores, y la segunda usando punteros. 13. Iteradores en Pascal ======================== Como en la mayoría de los programas se usan muchos ADTs contenedores, surge entonces la necesidad de establecer un mecanismo para accesar a todos esos elementos. Este mecanismo puede implementarse básicamente de dos formas: definiendo en el ADT contenedor operaciones que permitan recorrerlo, o por medio de iteradores. ================================================================== p := Endl(L); WHILE p <> First(L) DO BEGIN p := Prev(p,L); Procese(p); END; Figura 16 ================================================================== El Listado 6 es un extracto de la definición del ADT lista de [Aho-85]. Se incluyen operaciones que permiten recorrer la lista, como Next(p,L), First(L) o Prev(p,L). El código de la Figura 16 recorre una lista hacia atrás, usando esas operaciones. Esto es válido hacerlo, y es lo que procede en muchos casos. El lector suspicaz puede ver de este ejemplo que, dependiendo de la implementación de la lista, es posible que su recorrido sea muy ineficiente. Por ejemplo, si la lista está implementada con nodos enlazados por punteros hacia adelante, entonces encontrar el predecesor de cada nodo requiere recorrer toda la lista desde el principio. Esto es ineficiente; en otras implementaciones no existiría este problema ([Aho-85] incluye una buena discusión sobre ésto). La idea al definir un iterador es lograr encapsular una forma de acceso eficiente a todos los elementos de un ADT contenedor. Para esto el iterador debe proveer al usuario programador de un tipo de datos y varias operaciones para recorrer el ADT. Como convención, el tipo del iterador debe terminar en "_ITR", y debe estar en una unidad Pascal aparte cuyo nombre termina en "_I". La Figura 17 es el extracto de la especificación de un iterador que recorre hacia atrás una lista. En [Liskov-86] se discute en detalle el uso de iteradores; la convención descrita en esta sección sigue las sugerencias de ese texto. Es obvio que un iterador accesa la representación interna del ADT. En general, el programador que crea un ADT también debe crear iteradores para recorrerlo. Luego los programadores usuarios del ADT los pueden usar para construir sus programas. Los iteradores deben implementarse como tipos amigos del ADT, usando la terminología de C++. Cualquier iterador consta de cinco operaciones, que siempre tienen los mismo parámetros. Las operaciones Init y Done tienen el mismo uso que en ADTs. Clear inicializa el iterador para recorrer un ADT. En el caso de una lista implementada con punteros hacia adelante, el Init podría consistir en crear en memoria dinámica un vector de punteros en orden inverso a la lista original. El Clear inicializaría adecuadamente el vector de punteros, y finalmente el Done devolvería la memoria dinámica usada para almacenar el vector de punteros. En el caso de una lista implementada por medio de vectores, el iterador podría limitarse a llevar un contador de la última posición accesada en la lista. Más aún, el iterador se podría programar independientemente de List_T.Rep, usando las operaciones Next y Prev. La operación Finished retorna un valor booleano que indica si faltan de procesar elementos del ADT. Esta operación puede invocarse cuantas veces sea necesario, pues no modifica el valor del iterador. ================================================================== UNIT BackL_I; USES List_T, Elem_T; CONST Max = 20000; {[])====================================================([]} {[]) IMPLEMENTATION: ([]} {[])====================================================([]} {[]} TYPE {[]} {[]} BackL_ITR = RECORD {[]} {[]} Rep : ARRAY[1..Max] OF Lpos_T; {[]} {[]} END; {[]} {[])====================================================([]} {[])====================================================([]} {[]) PARAMETERS: LISTA USANDO PUNTEROS ([]} {[])====================================================([]} {[]) BackL_T ( nombre de la unidad ) ([]} {[]) BackL_ITR ( nombre del iterador ) ([]} {[]) List_T ( nombre de unidad ) ([]} {[]) List_ADT ( nombre del ADT ) ([]} {[]) Elem_T ( nombre de unidad ) ([]} {[]) Max ( tamaño del iterador ) ([]} {[])====================================================([]} PROCEDURE Init( {-} VAR I : BackL_ITR); PROCEDURE Clear( {?} VAR I : BackL_ITR; {+} VAR L : List_ADT); PROCEDURE Done( {?} VAR I : BackL_ITR); FUNCTION Next( {?} VAR I : BackL_ITR; {+} VAR L : List_ADT); {>>>>>>>} : Elem_P; FUNCTION Finished( {+} VAR I : BackL_ITR; {+} VAR L : List_ADT); {>>>>>>>} : BOOLEAN; Figura 17 ================================================================== La operación Next avanza el iterador, y retorna un puntero hacia el siguiente elemento contenido en el ADT. Es necesario que en la unidad Elem_T, en donde se define el tipo básico contenido en el ADT que el iterador recorre, se defina Elem_P = Elem_ADT. La Figura 18 contiene el código para recorrer hacia atrás una lista, usando el iterador definido en la Figura 17. ================================================================== BackL_I.Init(I); { ... } BackL_I.Clear(I,L); WHILE NOT BackL_I.Finished(I,L) DO BEGIN p := BackL_I.Next(I,L); Procese(p); END; { ... } BackL_I.Done(I); Figura 18 ================================================================== En la Figura 18 todas las operaciones del iterador están calificadas con el nombre de la unidad que contiene el iterador. Esto debe ser así porque los nombres usados para denotar las operaciones de un iterador son muy comunes y se usan en muchos ADTs. Además, como cada iterador siempre usa estos mismos nombres, es necesario calificarlos para evitar errores de sintaxis. En otros lenguajes sería posible usar el mismo nombre para denotar diferentes procedimientos, usando sobrecarga de nombres. Como el soporte de Pascal para ocultamiento de datos no es muy completo, entonces no es posible sobrecargar los nombres de las operaciones. El Rep del iterador de la Figura 17 debe ser una estructura de datos que permita recorrer todos los elementos del ADT contenedor de una manera eficiente. Esta estructura de datos dependerá de la forma en que el ADT esté implementado, aunque no es necesario que esto sea así. Por ejemplo, el iterador BackL_I puede implementarse usando las operaciones Endl y Prev del ADT Lista, aunque no resulte ésto en la más eficiente implementación. Es el programador del ADT quien debe decidir, al escribir la implementación del iterador, cuál técnica debe utilizar. El programador usuario debe evitar cambiar un ADT mientras lo recorre usando un iterador. Si lo cambia, en el mejor de los casos, el estado del iterador será indefinido. En el caso peor se podría producir una falla fatal. Un iterador permite examinar los elementos contenidos en un ADT contenedor. Es válido cambiar un elemento contenido, pero no lo es cambiar al contenedor. Los iteradores tiene muchas aplicaciones. Por ejemplo, puede definirse uno para números enteros que retorne el siguiente número primo en cada llamado. Si el ADT utilizado es un árbol, los clásicos recorridos infijo, posfijo y prefijo pueden ser implementados cómodamente con un iterador. 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. 14. Transferencia de tipos ========================== Puede que al novicio le preocupe que al hacer una transferencia de tipos se incurra en algún sobretrabajo innecesario, pero lo cierto es que esto no es así. La transferencia de tipos no tiene costo alguno. En la Figura 5 están las siguientes asignaciones: r := Rep_Stack(s); { Bien: transferencia de tipos } s := Stack_ADT(r); { Bien } En ambos casos el código generado se limita a copiar SizeOf(Rep) bytes de un lugar de memoria a otro. Desde el punto de vista del compilador, lo importante al definir un nuevo tipo de datos es saber cuánta memoria se necesita para almacenarlo. Es esa información la que le proporcionamos al decirle cuánta memoria debe reservar para una variable de tipo Stack_ADT: exactamente la misma que ocuparía una variable de tipo Rep_Stack. En la implementación de la operación Push puede encontrarse la instrucción: Inc(S.Rep.ultimo); { Incrementa el tope de la pila } El código generado por el compilador en este caso se limita a accesar el campo .ultimo en la variable s. Exactamente el mismo código hubiera sido generado si el identificador Rep no fuera necesario: Inc(S.ultimo); { Incrementa el tope de la pila } En este último caso, no se estaría usando ocultamiento de datos. El único sobretrabajo real que existe al usar ADTs en Pascal es el llamado a cada procedimiento que implementa una operación del ADT. 15. Comparación con otros métodos para implementar ADTs ======================================================= En [Liskov-86; cap. 7] se describe extensamente otro truco para implementar ADTs en Pascal que requiere, al igual que los tipos opacos de Modula-2, definir un puntero para cada instancia del ADT. Lo malo de esa propuesta es que está orientada a que todos los objetos manipulados por un programa sean accesados por medio de punteros. Este excecivo uso de punteros resulta en programas innecesariamente ineficientes, que deben pagar un sobretrabajo significativo para cada instancia de un objeto, pues se necesita un puntero que lo referencie. La ventaja principal de las convenciones descritas en este artículo es que se logra que el mecanismo de chequeo de tipos ayude al programador a construir abstracciones de datos. En contraposición, la técnica de Liskov y Guttag no protege la parte interna del ADT. Otro inconveniente de las convenciones de [Liskov-86] es que el código de un ADT se ve plagado de "chimbolitos" de puntero: por todo lado aparecen expresiones como s.campo que no significan nada para el programador. Si se usan las convenciones de este artículo, en la implementación del ADT aparecen expresiones como Rep(s).campo, que indican claramente que el programador está accesando la parte interna del ADT. Desgraciadamente el método de Liskov, y el aquí propuesto, incurren en la ineficiencia producida por el sobretrabajo de llamar a las operaciones del ADT. La ventaja principal de la técnica aquí discutida es que ésta es la única penalización que debe pagarse. Un gran inconveniente de esta manera de implementar ADTs es que el programador usuario necesita, en general, acceso al código fuente que implementa el ADT. Esto implica que será difícil que compañías especializadas desarrollen ADTs, pues deberán también ceder el código fuente. Esta debe haber sido la razón principal que motivó el que ADA tenga paquetes genéricos. Estas convenciones requieren de un compilador de Pascal que permita: - Uso de unidades - Uso de transferencia de tipos - Uso de cualificadores para los identificadores de una unidad Para una implementación de Pascal que no soporte unidades, se pueden utilizar las convenciones aquí descritas sustituyendo la calificación de procedimientos por medio de la unidad en que aparecen, por un prefijo. Por ejemplo, en lugar de escribir: Stack_T.Push(S,e); el programador escribiría Stack_T_Push(S,e). Todas las operaciones deberían estar adecuadamente calificadas. Además, en lugar de usar unidades sería necesario usar directivas de compilador {$INCLUDE Stack_T.inc}. El método ya no es tan elegante como para Turbo Pascal o Modula-2, pero funciona. 16. Conclusiones Usando estas convenciones el programador puede implementar tipos abstractos de datos cómodamente, aún cuando el compilador de Pascal usado no posea unidades. A diferencia de las convenciones de [Liskov-86], éstas permiten que la memoria usada por las instancias del ADT esté en la pila de ejecución del programa, y no en memoria dinámica, con lo que se logra una gran eficiencia al usar ADTs. El uso de esta técnica permitirá al programador comenzar a utilizar ADTs en su quehacer diario. Específicamente en el caso del compilador Turbo Pascal 5.0, es válido decir que las cualidades que presenta para usar abstracción de datos no sólo igualan a las de Modula-2, sino que le sobrepasan. En opinión del autor, al usar estas convenciones no existe razón alguna para usar Modula-2 para programación de aplicaciones, al menos en computadores para los que existe una versión del Turbo Pascal 5.0. El lector interesado debe comprender que el lenguaje Pascal no soporta programación por objetos en la forma que la soportan C++ y Smalltalk. Pero, de hecho, ¡casi que está al mismo nivel que ADA! (Sólo falta automatizar la instanciación de unidades). Estas convenciones están orientadas a que el programador use parametrización para sus ADTs, no polimorfismo. Si se implementan ADTs contenedores usando punteros a los objetos, el programador debe tomar muy en cuenta que puede ser necesario invalidar la verificación de tipos del compilador, por lo que el compilador no le podrá ayudar a encontrar errores en tiempo de compilación. Este trabajo ha sido inspirado en gran parte en el libro de Liskov y Guttag. Se ha explicado cómo implementar en Pascal la mayoría de las cualidades de CLU, en el contexto de un lenguaje de amplio uso, y sin sacrificar eficiencia en espacio y tiempo de ejecución. Mientras CLU es un lenguaje usado en pocas universidades (en Costa Rica es inasequible), Pascal es usado por muchos programadores profesionales. Estas técnicas les permitirán obtener todas las ventajas del uso de abstracción, pagando un precio muy pequeño en eficiencia del programa. Aunque usar ADTs es más difícil que no hacerlo, pues en algunos casos se dura el doble programando, vale la pena el esfuerzo, pues la calidad de los programas producidos es mucho más alta. Ojalá los programadores acepten este mensaje. BIBLIOGRAFIA [Aho-84] Aho, Alfred V. et al: "Data Structures and Algorithms" Addisson Wesley Publishing Co. U.S.A. 1984. [Borland-88] Borland International: "Turbo Pascal Reference Manual"; Borland International. California, U.S.A. 1988. [Bustard-88] Bustard, David; Elder, John; Welsh, Jim: "Concurrent Program Structures; Prentice-Hall; 1988. [Di Mare-88] Di Mare, Adolfo: "Convenciones de Programación para Pascal"; Reporte técnico ECCI-01-88. [Goldberg-83] Goldberg, Adele; Robson, David: Smalltalk-80, the Language and its Implementation; Addison-Wesley, 1983. [Ichbiah-79] Ichbiah, J.D et al: "Rationale for the Design of the ADA Programming Language"; SigPlan Notices, Vol 14; No. 6, Junio 1979. [Kernighan-86] Kernighan, Brian: "El lenguaje de programación C"; Prentice Hall; 1986. [Kernighan-87] Kernighan, B.; Pike, Rob: "El entorno de programación UNIX"; Prentice Hall; 1987. [Liskov-86] Liskov, Barbara; Guttag, John: "Abstraction and Specification in Program Development"; McGraw-Hill; 1986. [Stroustrup-86a] Stroustrup, Bjarne: "The C++ Programming Language"; Addison-Wesley; 1986. [Stroustrup-86b] Stroustrup, Bjarne: "An Overview of C++"; Sigplan notices; Octubre 1986. [Stroustrup-88] Stroustrup, Bjarne: "What is Object-Oriented Programming"; IEEE Transactions on Software Engineering; Mayo 1988. [Wiener-88] Wiener, Richard S.; Pinson, Lewis J.: "An Introduction to Object-Oriented Programming and C++"; Addison-Wesley, 1988. [Wirth-82] Wirth, Niklaus: "Programming in Modula-2, Second Edition"; R.R. Donnelley & Sons, Harrisonburg; Virginia, U.S.A. 1982. L I S T A D O S D E P R O G R A M A S ========================================= Por razones de espacio, no se incluyen todos los listados completos, sino aquellas partes más representativas de cada implementación. Si desea obtener todos los programas aquí mencionados, puede enviar un sobre con porte de correo pagado y con un diskette preformateado IBM/pc del 5 1/4" a la siguiente dirección: Prof Adolfo Di Mare Escuela de Ciencias de la Computación e Informática Universidad de Costa Rica ADTs en Pascal Listado 1 [ElemC.pas]: Interfaz del Elem_ADT de caracteres Listado 2 [ElemI_T.pas]: Interfaz del Elem_ADT de enteros Listado 3 [UsaPila.pas]: Programa que usa el ADT pila Listado 4 [StackV_T.pas]: Implementación del ADT pila con vectores Listado 5 [StackP_T.pas]: Implementación del ADT pila con punteros Listado 6 [ListC.pas]: Interfaz del ADT lista http://www.di-mare.com/adolfo/p/src/adts-91.zip