RECURSIVIDAD EN PROGRAMACION

Introducción a los tipos abstractos de datos

Con la aparición de los lenguajes de programación estructurados en la década de los 60, surge el concepto de tipo de datos (ing., data type), definido como un conjunto de valores que sirve de dominio de ciertas operaciones. En estos lenguajes (C, Pascal y similares, derivados todos ellos -de forma más o menos directa- de Algol), los tipos de datos sirven sobre todo para clasificar los objetos de los programas (variables, parámetros y constantes) y determinar qué valores pueden tomar y qué operaciones se les pueden aplicar.

Esta noción, no obstante, se reveló insuficiente en el desarrollo de software a gran escala, dado que el uso de los datos dentro de los programas no conocía más restricciones que las impuestas por el compilador, lo cual era muy inconveniente en los nuevos tipos de datos definidos por el usuario, sobre todo porque no se restringía de ninguna manera su ámbito de manipulación. Para solucionar esta carencia, resumida por J.B. Morris en "Types are not Sets" (Proceedings ACM POPL, 1973), diversos investigadores (citemos como pioneros a S.N. Zilles, a J.V. Guttag y al grupo ADJ, formado por J.A. Goguen, J.W. Thatcher, E.G. Wagner y J.B. Wright [ADJ78]) introdujeron a mediados de la década de los 70 el concepto de tipo abstracto de datos (ing., abstract data type; abreviadamente, TAD), que considera un tipo de datos no sólo como el conjunto de valores que lo caracteriza sino también como las operaciones que sobre él se pueden aplicar, juntamente con las diversas propiedades que determinan inequívocamente su comportamiento. Todos estos autores coincidieron en la necesidad de emplear una notación formal para describir el comportamiento de las operaciones, no sólo para impedir cualquier interpretación ambigua sino para identificar claramente el modelo matemático denotado por el TAD.

En realidad, el concepto de TAD ya existe en los lenguajes de programación estructurados bajo la forma de los tipos predefinidos, que se pueden considerar como tipos abstractos con poco esfuerzo adicional. Por ejemplo, consideremos el tipo de datos de los enteros que of rece el lenguaje Pascal; la definición del TAD correspondiente consiste en determinar:

- cuáles son sus valores: los números enteros dentro del intérvalo [minint, maxint];

- cuáles son sus operaciones: la suma, la resta, el producto, y el cociente y el resto de la división, y

- cuáles son las propiedades que cumplen estas operaciones: hay muchas; por ejemplo: a+b = b+a, a*Q = Q, etc.

Resumiendo, se puede definir un tipo abstracto de datos como un conjunto de valores sobre los que se aplica un conjunto dado de operaciones que cumplen determinadas propiedades. ¿Por qué "abstracto"? Éste es un punto clave en la metodología que se presentará. El calificativo "abstracto" no significa "surrealista" sino que proviene de "abstracción", y responde al hecho de que los valores de un tipo pueden ser manipulados mediante sus operaciones si se saben las propiedades que éstas cumplen, sin que sea necesario ningún conocimiento ulterior sobre el tipo; en concreto, su implementación en la máquina es absolutamente irrelevante. En el caso de los enteros de Pascal, cualquier programa escrito en este lenguaje puede efectuar la operación x+y (siendo x e y dos variables enteras) con la certeza de que siempre calculará la suma de los enteros x e y, independientemente de su representación interna en la máquina que está ejecutando el programa (complemento a 2, signo y magnitud, etc.) porque, sea ésta cual sea, la definición de los enteros de Pascal asegura que la suma se comporta de una manera determinada. En otras palabras, la manipulación de los objetos de un tipo sólo depende del comportamiento descrito en su especificación (ing., specification) y es independiente de su implementación (ing., implementation):

- La especificación de un TAD consiste en establecer las propiedades que lo definen. Para que sea útil, una especificación ha de ser precisa (sólo tiene que decir aquello realmente imprescindible), general (adaptable a diferentes contextos), legible (que sirva como instrumento de comunicación entre el especificador y los usuarios del tipo, por un lado, y entre el especificador y el implementador, por el otro) y no ambigua (que evite posteriores problemas de interpretación). La especificación del tipo, que es única, define totalmente su comportamiento a cualquier usuario que lo necesite. Según su grado de formalismo, será más o menos fácil de escribir y de leer y más o menos propensa a ser ambigua o incompleta.

- La implementación de un TAD consiste en determinar una representación para los valores del tipo y en codificar sus operaciones a partir de esta representación, todo ello usando un lenguaje de programación convencional. Para que sea útil, una implementación ha de ser estructurada (para facilitar su desarrollo), eficiente (para optimizar el uso de recursos del computador) y legible (para facilitar su modificación y mantenimiento). Una implementación del TAD (puede haber muchas, cada una de ellas pensada para un contexto de uso diferente) es totalmente transparente a los usuarios del tipo y no se puede escribir hasta haber determinado claramente su especificación; el cambio de una implementación por otra que respete el comportamiento deseado del tipo no ha de cambiar en absoluto la especificación ni, por consiguiente, la visión que de él tienen sus usuarios, que se limitarán a recompilar la aplicación correspondiente.

La verdadera utilidad de los TAD aparece en el diseño de nuevos tipos de datos. Imaginemos que se quiere construir un programa Pascal que calcule la suma de una secuencia de números complejos introducida por el terminal, acabada por el valor 0 + 0i (para simplificar la escritura de algunos detalles irrelevantes, supondremos que tanto la parte real como la parte imaginaria de los números complejos son enteros en vez de reales), escribiendo el resultado en la pantalla. Fieles a la metodología que acabamos de esbozar, enfocamos el caso como un ejercicio resoluble a partir de la especificación de un TAD para los números complejos, definible de la siguiente forma:

- cuáles son sus valores: todos aquellos números complejos de partes real e imaginaria enteras y dentro del intérvalo [minint, maxint];

- cuáles son sus operaciones: como mínimo, y dada la funcionalidad del programa, se necesita una operación para sumar complejos, otra para crear un complejo a partir de dos enteros y dos más para obtener las partes real e imaginaria, y- cuáles son las propiedades que cumplen las operaciones: las típicas de los complejos.

Una vez definido el TAD para los complejos es posible utilizarlo desde un programa Pascal: se pueden declarar variables

...