Programación II - Abstract Data Types (I)

Copyright (c) Gabriel Pimentel, 2009

All rights reserved. Without limiting the rights under copyright reserved above, no part of this publication may be reproduced,
stored or introduced into a retrieval system, or transmitted, in any form or by any means (electronic, mechanical, photocopying,
recording or otherwise), without the prior written permission of the copyright owner.
 Tipos de Datos Abstractos (I)
Gabriel Pimentel

Introducción
La década del 70’s fue verdaderamente significativa en términos del desarrollo de conceptos y
herramientas para soportar la construcción de software de alta calidad. Frecuentemente utilizamos la
frase Abstract Data Type, para dar cuenta de la confluencia de ideas en el campo de la especificación y
verificación de programas, metodologías de la programación, semánticas formales y lenguajes de
programación.

Es la sinergia de los desarrollos en estas áreas, y no simplemente la manifestación de estos en

una metodología o lenguaje de programación lo significativo. Si bien esta confluencia es mas evidente en
los lenguajes de programación, detrás de cada lenguaje es posible identificar las contribuciones de las
otras áreas.

Aquí abordaremos una metodología para el desarrollo de sistemas de software que tiene por
objetivo asistir el desarrollo de sistemas de calidad que sean correctos, robustos, eficientes y
razonablemente fáciles de entender, reusar y extender.

Antecedentes
Es difícil conocer dónde se origino el concepto de Abstract Data Type, pero sin duda uno de estos
puntos puede ser la debacle de los grandes sistemas de los años 60’s. La experiencia con estos sistemas
llevo a reconocer que el desarrollo de software es mucho más difícil de lo que se había imaginado hasta
ese momento, tal como quedo expresado en las dos NATO Software Engineering Conferences.

Como consecuencia directa de la experiencia con esos sistema, se comenzó a apreciar la

dificultad intelectual de la programación. Más aun, se comenzó a apreciar que la raíz de la dificultad se
centraba en nuestra incapacidad de tratar con la complejidad de estos sistemas. Esto a su vez levo a
reconocer que ciertas formas de organizar los programas, cierta estructura, era más intelectualmente
tratable que otras.

Durante los finales de los 60’s y al principio de los 70’s mucho del trabajo de diferentes grupos de
investigación se abocó a resolver esta crisis (“software crisis”, un termino aun hoy significativo). De
especial interés resulta dar cuenta del trabajo realizado en algunas áreas:

Programación Estructurada
Promovida por el famoso articulo de Dijkstra “Goto Statement Considered Harmful”,
donde ciertas estructuras de control fueron identificadas como una de las fuentes de
complejidad intelectual, y el infame “goto” que fue identificado como un mecanismo de
los lenguajes que podría ser usado para construir programas intelectualmente
intratables.
Esto a su vez llevo a investigar por un lado estructuras de control alternativas y a la
clase de metodología de programación (Structured Programming. Dijkstra, Dahl, Hoare)
caracterizadas por refinamientos sucesivos (“stepwise refinement”, Program
Development by Stepwise Refinement. Niklaus Wirth).

Ciclo 2020 © Gabriel Pimentel Página 2 de 8

 Estos enfoque sugieren comenzar con una descripción general, de alto nivel, abstracta y
evidentemente correcta (lógica de Hoare), refinando a través de una secuencia de
sucesivos programas más concretos, hasta concluir en una versión final.

Descomposición Jerárquica
Mucho del trabajo realizado (Dijsktra, Brooks, Simon) concluyo que entre las estructuras
de programas mas manejables están aquellas que son jerárquicas, esto es, una en la
cual la relación entre los componentes del sistema pueden ser vista como un “lattice”.
Sistemas tales como THE (sistema operativo desarrollado por Dijsktra) fueron
construidos utilizando una descomposición jerárquica como principio guía y demostró
que este tipo de descomposición encapsulaba alguna de las propiedades deseadas.
Posteriormente, por supuesto, se observo que generalmente hay mas de una forma de
relación entre los componentes de un sistema, donde, idealmente un numero bajo de
componentes se relacionan de pocas y especificas manera.

Descomposición Modular
En los sistemas de los 60’-70’, el termino modulo simplemente se asociaba, en la
mayoría de los casos, a unidad de compilación. Frecuentemente, un modulo era una
unidad funcional, los datos pasaban de modulo a modulo, con cada modulo ejecutando
alguna tarea especifica sobre estos datos.
En una serie de publicaciones, David Parnas cambia la visión acerca de un modulo en al
menos tres aspectos. Primero, un modulo es ahora una abstracción de datos más que
una abstracción funcional. Segunda, en lugar de una interfaz extensa y compleja
involucrando detalles acerca del formato de los datos, un modulo tiene, principalmente,
una interfaz procedural que admite una especificación formal y que es invariante en
relación a los cambios de implementación. Tercero los detalles de implementación de un
modulo están ocultos de sus usuarios de modo que estos pueden estar aislados de
detalles irrelevantes. El trabajo de Parnas fue principalmente metodológico, no obstante
esta visión acerca de la descomposición de un programa es el antecedente mas directo
de las facilidades para la abstracción de datos de los lenguajes de programación
modernos y es clave a la especificación y verificación formal de programas.

Semántica, Verificación y Especificación

Cada una de estas áreas son importantes per ser, pero ellas tienen mucho en común. Si
bien estas lineas de investigación comenzaron al mismo tiempo que las otras, aun
subsisten algunos problemas teóricos. Si bien se ha avanzado al punto de poder
especificar la semántica completa de un lenguaje y el comportamiento de programas no
triviales, son pocos aun los lenguajes de programación que soporten la especificación y
verificación a nivel del código y su control en tiempo de ejecución (un caso interesante
es el entorno de desarrollo Eiffel).

Lenguajes
Con “software crisis” o no, la investigación en el área de los lenguajes de programación
ha sido y es una de alta dinámica. Los lenguajes de programación, constituyen el
principal vehículo de expresión de nuestra disciplina y como tal es siempre un área de
interés.
La investigación en este campo fue guiada por nuestra compresión del rol de la
complejidad. Primero, hubo un giro de lo complejo a lo simple en los lenguajes mismos,
y lenguajes tales como Pascal aparecieron. Segundo, si bien el trabajo en lenguajes
extensibles en sentido estricto disminuyo, en parte a ciertos problemas técnicos de difícil
solución, mucho de los conceptos de planteados en estas lineas sobrevivieron en los

Ciclo 2020 © Gabriel Pimentel Página 3 de 8

 lenguajes con soporte para la abstracción de datos. Sin embargo, lo más importante de
estos trabajos fue el reconocimiento de que la simple extension sintáctica no resuelve
por sí las cuestiones esenciales de la complejidad.

Ninguna de estos trabajos tomados aisladamente, por supuesto, resolvió la “software crisis” (aun
presente, mas allá de lo que se sugiera). Tal vez la consecuencia más significativa de la confluencia de los
resultados de estas áreas de investigación fue el creciente numero de investigaciones que pueden ser
categorizadas como “Abstract Data Types”, y esta serie de trabajos encierra aspectos de todos ellos.

Abstracción y Descomposición
Un sistema pequeño, alrededor de varios miles de lineas, puede ser implementado como un solo
bloque, o monolíticamente sin que esto implique necesariamente consecuencias severas a futuro. A
medida que el tamaño de los sistemas se incrementa, una estructura monolítica ya no resulta razonable,
entre otras razones porque resulta difícil de comprender. Estos sistemas, en cambio, deben ser
descompuestos en un numero, idealmente pequeño e independiente, de entidades genéricamente
llamados módulos, que sistemicamente provean el abanico de características requeridas.

El interés esta puesto en el proceso de descomposición (estructura), esto es: que criterio debe
guiar la descomposición, que tipo de entidades (piezas resultantes de aplicar el criterio de
descomposición) son de mayor utilidad y que técnicas incrementan las chances de que estas piezas
puedan ser combinadas para resolver el problema original u otros.

Realizar una descomposición apropiada es más importante a medida que la complejidad de las
aplicaciones se incrementa, debido a un sinnúmero de razones, alguna de las cuales ya hemos tratado en
otros espacios, no obstante esto repasemos algunas.

En primer lugar, muchos desarrolladores están involucrados en el desarrollo de sistemas de gran

tamaño. Si solo pocas personas están trabajando sobre un programa, la interacción entre estas puede
darse regularmente lo que reduce la posibilidad de confusiones o mal entendidos acerca de qué esta
haciendo cada uno y las consecuencias de estos mal entendidos. Por el contrario, cuando el tamaño del
grupo de desarrollo crece la posibilidad de comunicarse regularmente disminuye, fundamentalmente
porque consume demasiado tiempo, en estos contextos el sistema debe ser particionado de una manera
tal que facilite su desarrollo de manera independiente con un mínimo de contacto interpersonal.

La vida útil de una aplicación comienza cuando es liberado a sus usuarios, la labor de desarrollo
no continua mas allá de este punto. Sin embargo, el código probablemente contenga errores residuales
que requerirán ser atendidos con rapidez, también es bastante probable que se requiera introducir
modificaciones que hagan que la funcionalidad previstas se ajusten mejor a las necesidades de los
usuarios. La mayoría de las aplicaciones tienen un ciclo de vida largo y los desarrolladores, muy
frecuentemente, tienen que tratar con programas en los que ellos no participaron. En general las
actividades de mantenimiento o extension son hechas por personas que no estuvieron involucradas en el
desarrollo.

Todos estos factores hacen necesario que los programas sean estructurados de manera tal que
ellos puedan ser desarrollados independientemente, entendidos con facilidad y permitan su modificación
y extension a bajo costo (económico, intelectual).

El principio básico con el que abordamos la resolución de aquello problemas que consideramos
“grandes” o complejos, ha sido clara a lo largo del tiempo y es transversal a la mayoría de las disciplinas,
en estas situaciones nosotros “dividimos” para “gobernar”. Desafortunadamente simplemente seguir esta

Ciclo 2020 © Gabriel Pimentel Página 4 de 8

máxima nos deja aun lejos de resolver el problema. Decidir cómo exactamente dividir el problema es
realmente lo significativo para llegar a la solución del problema.

Nuestro objetivo al descomponer un programa es crear o desarrollar entidades, que interactúen

entre sí de una manera simple y bien definida. Si logramos este objetivo seremos capaces de trabajar
sobre diferentes entidades independientemente, sin necesidad de mucha comunicación entre sí.

Cuando nosotros descomponemos un problema, tratamos de hacerlo de modo tal que:

• cada subproblema este al mismo nivel de detalle,
• cada subproblema pueda ser resuelto independientemente y
• las soluciones a los subproblemas puedan ser combinadas para resolver el problema
original y eventualmente otros problemas.

La descomposición ha probado ser, a lo largo del tiempo, una técnica útil para la resolución de
problemas. Específicamente, en nuestro campo, desde los tiempos de Babbage hasta ahora, se ha
reconocido la utilidad de cosas como las macros y subrutinas como artefactos resultantes de la aplicación
de esta técnica por parte de los programadores. Es importante reconocer, no obstante, que la
descomposición no es una panacea y cuando es usada sin un criterio apropiado sus efectos pueden aun
ser peores que sí no se hubiera llevado adelante ninguna descomposición. El problema más común es
obtener componentes que resuelven el subproblema pero no pueden ser combinados para resolver el
problema original. Este problema citado por algunos autores como la complejidad de lograr una “partición
inteligente del espacio del problema” es una de las principales razones por las que resulta tan difícil la
integración de sistemas.

Como hemos planteado en diversas oportunidades, cuando formulamos abstracciones elegimos

no considerar ciertos aspectos de la situación problemática en un esfuerzo para construir una versión
simplificada de la anterior. El proceso de abstracción puede ser visto como la aplicación de un mapeo
muchos a uno.

Si admitimos que nosotros suprimimos ciertos contenidos de información para tratar cosas
disimiles como si ellas fueran lo mismo con el interés de simplificar nuestro análisis al separar aquello
que es relevante de lo que no lo es (la relevancia depende del contexto), en este sentido también es la
abstracción una manera de descomponer de manera apropiada al cambiar el nivel de detalle que
consideramos.

Abstract Data Types

Entre los enfoques discutidos a lo largo del tiempo en torno a la la abstracción, la abstracción de
datos surge como uno de los mas importante. La abstracción de datos nos permite abstraernos de los
detalles de implementación de las entidades para concentrarnos en cómo estas se comportan. Como
planteara John Guttag:

“La mayor parte del tiempo uno solo esta ocupado con las características de comportamiento de
un objeto, que puede hacerse con él, no con como las operaciones sobre el son implementadas.
Usare el término Abstract Data Type (ADT) para referirme a una clase de objetos definidos por
una especificación independiente de la representación… Una noción simple, un conjunto de
objetos y las operaciones sobre esos objetos …”

La especificación de esas operaciones define una interfaz entre el tipo de dato abstracto y el resto
del programa. La especificación define el comportamiento de las operaciones que hacen, no cómo lo
hacen. La especificación aísla al resto del programa de las estructuras de datos, algoritmos y código
involucrado al proveer una realización de la abstracción.

Ciclo 2020 © Gabriel Pimentel Página 5 de 8

 Mas aun como Barbara Liskov, planteara:

“La abstracción de datos nos permite abstraernos de la manera en que las estructuras son
implementadas y concentrarnos en como se comportan … permiten que la representación de los
datos cambien localmente sin afectar a los programas que los usan … también simplifican la
estructura de los programas que las usan porque estas abstracciones presentan una interfaz de
alto nivel ….
El propósito de la abstracción en la programación es separar comportamiento de
implementación. Una abstracción es definida por especificación e implementada por un modulo.
La especificación describe que hace la abstracción pero omite como es implementada. Al omitir
tales detalles permite que diferentes implementaciones de la misma abstracción puedan, en
principio, ser sustituidas libremente..”

El verdadero arte de la programación es encontrar una noción relevante a ambos, el constructor

de la abstracción y al usuario de la abstracción. Un conjunto fijo de abstracciones no es suficiente para
modelar la complejidad inherente de un dominio particular, de donde, se requiere contar con
herramientas que permitan crear abstracciones específicas al dominio, idealmente estas capturan
conceptos relevantes a través del ciclo de vida de la aplicación, y proveen una descomposición
conveniente.

Es en este marco que analizaremos el aporte de los Tipos de Datos Abstractos (Abstract Data
Types) y como veremos estos nos permite no solo: manejar la complejidad inherente al software (vía
estructura y abstracción) sino también, extender el lenguaje de programación (mas precisamente el
sistema de tipos del lenguaje).

Estos nuevos tipos incorporan abstracción por parametrizacion y por especificación. La

abstracción por parametrizacion se logra de la misma manera que en los procedimientos o funciones,
como ya hemos visto. La abstracción por especificación implica hacer las operaciones parte del tipo. Esto
cambia la noción mantenida con anterioridad a la emergencia de los Tipos de Datos Abstractos, que
consideraba los tipos como conjuntos.

Para entender las implicaciones de este cambio, cuando pensamos en un tipo como un conjunto,
básicamente todo lo que se requiere es elegir una representación para los valores del tipo. Hecho esto
todos los programas son desarrollados en términos de esa representación. Si la representación cambia, o
aun si su interpretación cambia, todos los programas que usan el tipo deben cambiar, no hay manera de
limitar el impacto del cambio.

Por otra parte si incluimos las operaciones en el tipo tal como sugiere la siguiente formula:

Abstract Data Type = <objects, operations>

(en esta formula el termino objeto hace referencia a una zona de almacenamiento con ciertas
características, principalmente un valor.)

Obviamente, las operaciones del tipo son implementadas en términos del esquema de
representación elegido por la naturaleza y extension de los valores del tipo. Resulta lógico
reimplementarlas si cambiamos la representación, sin embargo, los programas que utilizan la abstracción
no deben ser cambiados puesto que ya no usan la representación, sino que dependen de una interfaz
abstracta, y por tanto mas estable, provista por la especificación de la operación.

Si un numero (idealmente mínimo) de operaciones se proveen para un tipo, la imposibilidad de

acceder a la representación no debería generar ningún inconveniente, en términos generales cualquier

Ciclo 2020 © Gabriel Pimentel Página 6 de 8

requerimiento debería poder ser satisfecho eficientemente al invocar estas operaciones (idealmente
completa).

Obviamente, los usuarios pueden aumentar el conjunto de operaciones definidas para el tipo al
definir otras abstracciones de datos o procedurales, pero tales extensiones no deberían tener acceso (ser
dependientes) a la representación del tipo. Lamentablemente son pocos los lenguajes (objecive-c y varios
de los lenguajes considerados post-modenos) que soportan mecanismos para extender tanto aquellas
abstracciones primitivas como aquellas introducidas como resultado de este proceso de descomposición y
abstracción.

En la visión planteada por este enfoque, los tipos ya no son considerados conjuntos sino mas bien
algebras heterogéneas, es por esto que varios autores, independientemente de algunas sutiles
diferencias, se refieren a los Tipos de Datos Abstractos como una Especificación Algebraica de Tipo.

Especificación para un Tipo de Dato Abstracto

Al igual que en el caso de las abstracciones por parametrizacion (procedimientos) , el significado
de un tipo no estaría dado por ninguna de sus implementaciones. En lugar de esto, una especificación
debería definir su comportamiento y dado que las instancias de un tipo son solo utilizadas a través de sus
operaciones, resulta lógico plantear, en principio, que esta especificación consista de una explicación
acerca de que hace la operación.

En general la especificación de un tipo debe establecer las propiedades que lo definen. La

especificación de un tipo debe ser precisa, general, legible y no ambigua, debe cubrir totalmente el
comportamiento del tipo y debe poder verificarse a condición que el lenguaje en la que se escriba provea
una semántica clara.

La especificación de un tipo consiste en establecer las propiedades que lo definen. Esta

especificación ha de ser precisa, general, legible y no ambigua. La especificación debe definir totalmente
el comportamiento del tipo, es decir completa y debe poder verificarse a condición que el lenguaje en la
que se escriba provea una semántica clara.

En el marco de este espacio, utilizaremos una versión aumentada (lógica de Hoare, excepciones)
de la notación propuesta por John Guttag. En términos generales la especificación de un tipo tiene tres
partes: una cabecera, una sección donde se especifica la sintaxis del tipo y por ultimo una sección donde
se especifica la semántica del tipo (axiomas).

La cabecera introduce el nombre de la abstracción, posiblemente una breve descripción (en

términos de conceptos bien entendidos) y las relaciones entre esta abstracción y otras previamente
definidas, puede (formalmente debe) ser aumentada con el invariante del tipo.

La sintaxis, suministra una lista de las operaciones que definen el tipo, básicamente presenta el
formato de las operaciones (prototipos) indicando el nombre de la operación, una lista de los tipos de los
argumentos y el tipo del resultado de la operación. Esta especificación puede (formalmente debe) ser
aumentada mediante la especificación de pre-condiciones (require) , post-condiciones (effects) y en el
caso de corresponder su invariante.

Las operaciones de un tipo pueden clasificarse de varias maneras, nosotros elegiremos

clasificarlas, de la siguiente manera: constructoras, productoras, modificadoras, inspectoras o
evaluadoras. Las operaciones constructoras crean una nueva instancia del tipo, estas operaciones pueden
tomar uno o mas argumentos. Las operaciones productoras, crean una nueva instancia a partir de uno o
más instancias per-existentes del tipo. Las operaciones modificadoras cambian, en el caso de que el tipo

Ciclo 2020 © Gabriel Pimentel Página 7 de 8

sea mutable, las instancias del tipo. Las operaciones inspectoras, en general toman una instancia del tipo
y devuelven una instancia de otro tipo. Ciertas operaciones pueden no definirse en particular aquellas que
puedan considerarse un formalismo dentro del dominio del cual se formula la abstracción.

La semántica, describe el significado de las operaciones definidas sobre el tipo expresado como
un conjunto de axiomas. Estos axiomas se escriben usando las operaciones definidas en la sintaxis,
estableciendo lo que es siempre verdadero acerca del comportamiento de las instancias del tipo. Es
posible especificar en la semántica del tipo expresiones condicionales, referencias a la misma u otra
abstracción, condiciones de error y condiciones excepcionales.

Una regla general para escribir la semántica es establecer los axiomas para las operaciones
constructoras y productoras, y luego escribir un axioma para cada operación evaluada, modificadora
sobre cada constructor/productor.

Existe la creencia generalizada que es posible introducir la especificación de un tipo a través de

algún constructor particular de un lenguaje de programación, en general el constructor “class”. Resulta
obvio señalar qué tal creencia es una contradicción en sí misma, de hacerse a través de algún lenguaje
de programación particular la especificación dejaría de ser abstracta y por tanto de valor.

Como ejemplo, consideremos una versión simplificada de una coordenada en plano X,Y, como se
muestra a continuación.

Coord
use integer, boolean

Sintaxis

create( integer, integer ) -> Coord

X( none ) -> integer

Y( none ) -> integer

equal( Coord, Coord ) -> boolean

Semantic

X( create( x, y ) ) -> x

Y( create( x, y ) ) -> y

equal( create( x, y ), create( r, q ) ) -> true, if x == r && y == q

Ciclo 2020 © Gabriel Pimentel Página 8 de 8