Usuario:Santhy/Tipo de dato abstracto

Un tipo de dato abstracto (TDA, también abreviado TDA por su nombre en inglés) o tipo abstracto de datos (TAD) es un modelo matemático para tipos de datos en los que el tipo de dato se define por su comportamiento desde el punto de vista de un usuario de los datos, concretamente respecto a los posibles valores, operaciones en el tipo de dato, y el comportamiento de estas operaciones. Desde el punto de vista del implementador de la estructura, su contraparte son las estructuras de datos, que funcionan como realizaciones concretas de uno o más tipos de datos abstractos (que serían las interfaces de las estructuras de datos), y que son implementables en una o más arquitecturas reales.

Formalmente, un TAD podría definirse como una clase de objetos cuyo comportamiento lógico es definido por un conjunto de valores y otro de operaciones;​ lo que es análogo a una estructura algebraica en matemáticas. Sin embargo, distintos autores ofrecen visiones paralelas respecto a lo que dan a entender por comportamiento, siendo las especificaciones axiomáticas (algebraicas) y los modelos abstractos las dos clases principales de especificación formal para referir el comportamiento.​ Éstas se corresponden respectivamente con la semántica axiomática y la semántica operacional de la máquina abstracta. Algunos autores también incluye el coste computacional, en términos del tiempo y espacio necesarios para realizar las operaciones y para representar los valores.

En la práctica mchos tipos de datos comunes no son genuinos TDAs, ya que la abstracción no es perfecta, y los usuarios han de estar al corriente de detalles como un posible desbordamiento aritmético debido a la representación subyacente utilizada en la implementación del tipo de dato. Por ejemplo, los números enteros se suelen almacenar como valores de ancho fijo (generalmente números binarios de 32 o 64 bits), y por tanto experimentan desbordamiento al exceder el valor máximo o mínimo del tipo de dato.

Los TDAs son un concepto teórico en ciencias de la computación, utilizados para el diseño y análisis de algoritmos, estructuras de datos, y sistemas software, y no se corresponden con características específicas de ningún lenguaje de programación (la mayoría de lenguajes ampliamente usados no soportan utilizar TDAs especificados formalmente). Sin embargo, diversas características de lenguajes suelen tener una correspondencia con aspectos de los TDAs, y son fácilmente confundidos con los TDAs mismos. Entre estas características se incluyen los tipos abstractos, los tipos opacos de datos, los protocolos en orientación a objetos, y el diseño por contrato. Los TDAs fueron propuestos por primera vez por Barbara Liskov y Stephen N. Zilles en 1974, como parte del desarrollo del lenguaje CLU.​

Ejemplos

Los números enteros son un tipo de dato abstracto, definido como los valores $\ldots ,-2,-1,0,1,2,\ldots$, y por las operaciones aritméticas de suma, resta, multiplicación y división, y las operaciones lógicas de mayor y menor que., que se comportan como es usual en matemáticas (teniendo en cuenta la división entera), independientemente de como se representan los enteros en el ordenador. El comportamiento de este tipo de dato incluiría respetar ciertos axiomas (como la asociatividad y la conmutatividad de la suma), y precondiciones en operaciones (como la división por cero). En general los enteros se representarán en una estructura de dtos como números binarios, típicamente en complemento a dos, pero podrían ser decimales codificados en binario o en complemento a uno. En cualquier caso, el programador puede utilizar los datos simplemente como enteros, sin preocuparse de cuál ha sido la elección para la implementación subyacente.

Un TDA no solo consiste en operaciones, sino también en los propios valores de los datos subyacentes al tipo y de las restricciones que estas operaciones puedan tener. En general una "interfaz" solamente se refiere a las operaciones, y ocasionalmente a alguna restricción sobre estas —normalmente precondiciones y postcondiciones, pero no otras clases de restricciones, como las relaciones entre las operaciones.

Esto puede entenderse con el siguiente ejemplo:

Una pila abstracta, que es una estructura LIFO (es decir, lo primero que entra es lo último en salir), podría ser definida por tres operaciones:

• apilar (push) para insertar un elemento en la parte superior de la pila,
• desapilar (pop) para eliminar el elemento superior de la pila, y
• peek o superior (peek o top) para acceder al elemento superior de la pila sin eliminarlo.

Una cola abstracta, que es una estructura FIFO, sin embargo, también tendría tres operaciones

• encolar (enqueue) para insertar un elemento al final de la cola,
• desencolar (dequeue) para eliminar el primer elemento de la cola, y
• primero (front), que devuelva el primer elemento de la cola sin eliminarlo.

Estos dos tipos de datos serían indistinguibles entre sí, si no se incluyese en la definición la restricción formal de que en una pila cada desapilamiento siempre devuelve el elemento más reciente que no se haya desapilado todavía, y que en una cola cada desencolado ha de devolver el elemento más antiguo que aún se halle encolado. Al analizar la eficiencia de los algoritmos que utilizan pilas puede ser también relevante especificar que en una pila todas las operaciones han de llevar el mismo tiempo computacional sin importar cuántos datos hayan sido apilados, y que la pila utiliza, además, una cantidad constante de espacio para cada elemento.

Introducción

Los tipos de datos abstractos son elementos puramente teóricos, utilizados (entre otras cosas) para simplificar la descripción de algoritmos abstractos, clasificar y evaluar estructuras de datos, y para describir formalmente los sistemas de tipos de los lenguajes de programación. A la hora de ser utilizados, un TDA puede ser implementado por tipos de datos específicos o estructuras de datos, de muchas formas y por diversos lenguajes de programación; o descritos en un lenguaje de especificación formal.

Los TDAs son implementados a menudo como módulos: ofreciendo al usuario únicamente una interfaz en la que se declaran funciones las funciones que correspondan con las operaciones del TDA, utilizando comentarios para describir las restricciones. Esta ocultación de información permite que se cambie la implementación del módulo sin que ningún programa cliente pueda verse afectado.

El término tipo de dato abstracto también puede verse como una generalización de ciertos tipos de estructuras algebraicas, tales como redes, grupos y anillos.​ El concepto de los tipos de datos abstractos está relacionado con la abstracción de datos, importante en las metodologías de programación orientada a objetos y de diseño por contrato para desarrollo software.

Definición de un tipo de dato abstracto

Como se ha dicho arriba, un tipo de dato abstracto puede definirse como un modelo abstracto, en función de la semántica operacional de la máquina abstracta, o bien como una especificación axiomática, en función de la semántica axiomática de la máquina abstracta. Debido a que el énfasis del uso de los tipos de dato abstractos cobran gran importancia a la hora del desarrollo software, en este contexto es habitual denotarlos por su semántica operacional, más cercana a la interpretación máquina de la ejecución.

Así, en función del paradigma con el que trabajemos, podemos realizar una distinción dual en dos tipos de definiciones: las definiciones imperativas y las funcionales.

Definición imperativa

En los lenguajes de programación imperativos una estructura de datos abstracta puede verse como una entidad mutable (es decir, que puede cambiar de estado con el tiempo). Algunas operaciones pueden modificar el estado del TDA y, por tanto, el orden en el que se evalúan las operaciones es importante, y la misma operación en las mismas entidades puede tener efectos diferentes si se ejecuta en momentos diferentes (salvo que sea idempotente), tal y como ocurre con las instrucciones máquina o los comandos y procedimientos del paradigma imperativo. Este estilo suele ser el utilizado para describir algoritmos abstractos, tal y como describe Donald Knuth en The Art of Computer Programming.

Ejemplo de variable abstracta

Las definiciones imperativas de los TDAs suelen depender del concepto de variable abstracta, que podría verse como el TDA no trivial más sencillo. Una variable abstracta V es una entidad mutable que admite dos operaciones:

• almacenar(V, x), donde x es un valor de algún tipo no especificado;
• recuperar(V), que devuelve un valor,

con la restricción de que

• recuperar(V) siempre devuelve el valor x utilizado en la operación recuperar(V, x) más reciente realizada sobre esa misma variable V.

Ya que la variable abstracta es un concepto tan ubicuo, suele utilizarse la notación V ← x (u otra similar) en pseudocódigo para referirse a la acción de almacenar(V, x) y cada vez que se utilice la variable V en un contexto en el que se requiere un valor, se supone que se está realizando la operación de recuperar(V). Por lo tanto, por ejemplo, V ← V + 1 se entiende que significa almacenar(V, recuperar(V) + 1).

Según esta definición, se asume implícitamente que guardar un valor en una variable U no tiene efecto sobre el estado de ninguna otra variable diferente V. Este razonamiento puede hacerse explícito añadiendo la restricción de que

• si U y V son variables distintas, la secuencia de operaciones almacenar(U, x); almacenar(V, y) es equivalente a la secuencia almacenar(V, y); almacenar(U, x).

En general, las definiciones de TDAs asumen implícitamente que ninguna operación que cambie el estado de un TDA pueda tener efecto en el estado de ninguna otra instancia (incluyendo otras instancias del mismo TDA), salvo que de algún modo en la definición del TDA se implique que las dos instancias estén relacionadas de ese modo. Por ejemplo, al generalizar la definición de la variable abstracta para incluir registros, la operación que selecciona un campo de una variable registro R ha de devolver una variable V que está relacionada con una parte de R.

La definición de una variable abstacta V puede restringir los valores almacenables x a elementos de un conjunto específico X, denominado rango o tipo de V. Al igual que en los lenguajes de programación, tales restricciones pueden simplificar la descripción y análisis de algoritmos, así como mejorar la legibilidad.

Téngase en cuenta que la definición dada no determina el comportamiento de evaluar recuperar(V) mientras V esté sin inicializar, esto es, antes de realizar ninguna operación de almacenar en V. Si un algoritmo realizase una operación de recuperar en ese caso podría considerarse que es formalmente incorrecto, ya que el efecto de esa operación todavía no está definido.

Definición funcional

Otro modo de definir un TDA, más cercano a la metodología funcional de programación es considerar cada estado de la estructura como una entidad independiente. Bajo este punto de vista cualquier operación que modifica el TDA se modela como una función matemática (acorde al paradigma) que toma el estado anterior como argumento, y cuyo resultado de evaluación incluye el nuevo estado de la estructura. En contraposición con las operaciones bajo el paradigma imperativo, estas funciones son funciones puras y por tanto no ocasionan efectos colaterales. Por lo tanto, el orden de evaluación no es importante, y la misma operación aplicada a los mismos argumentos (incluyendo los estados como argumento) siempre devolverá los mismos resultados (y estados de salida).

Ejemplo de variable abstracta

Desde un punto de vista puramente funcional no es posible definir una variable abstracta con la semántica precisa de las variables imperativas. Aún así, el paradigma puede reconciliar el concepto de variable abstracta dentro de una superestructura que permita representar el estado como puede ser una mónada.

Recuérdese que una mónada es una estructura para representar computaciones como una secuencia de pasos. Esto establece un orden definido en las operaciones de almacenar y recuperar sobre la variable abstracta, junto con el paso del estado necesario entre las operaciones monádicas. En este caso, seguiríamos teniendo las operaciones de almacenar y recuperar, pero que recibirían y devolverían los siguientes tipos de datos:

• almacenar :: Variable x → x → Estado s ()
• recuperar :: Variable x → Estado s x

donde Variable x representa un dato de tipo Variable de x para algún tipo de dato x, y Estado s x es la Mónada Estado con un estado interno s (incluyendo el estado actual del parámetro de entrada Variable x) y un valor de salida del tipo de x.

Respecto a la inclusión de la complejidad algorítmica en la definición

Además del comportamiento en términos axiomáticos u operacionales, es frecuente incluir en la definición de un TDA su complejidad algorítmica esperada. Esto sigue la doctrina establecida por Alexander Stepanov, diseñador de la Standard Template Library de C++, en la que incluyó garantías respecto a la complejidad computacional, ya que si en la práctica el uso de los tipos de dato abstractos lo que permiten es intercambiar módulos software para ofrecer la misma funcionalidad, no es esperable poder intercambiar un módulo por otro salvo que sus operaciones sigan compartiendo un comportamiento similar en ejecución, pues en otro caso los programas usuarios de este código podrían verse gravemente afectados de modos inanticipables.​

Ventajas del tipado abstracto de datos

Encapsulación

La abstracción proporciona una promesa de que cualquier implementación del tipo abstracto tendrá ciertas propiedades y comportamientos; y conocer éstas es lo único necesario para hacer uso del tipo de dato abstracto. El usuario no necesita conocer cómo está implementado el tipo internamente para poder utilizarlo. De este modo, e independientemente de la complejidad de una implementación particular del tipo de dato es abstraida en una interfaz consistente y sencilla en su uso.

Ubicación de los cambios

El código programado utilizando tipos de dato abstractos no necesitan ser editados si cambia la implementación del TDA. Debido a que cualquier cambio en la implementación ha de satisfacer la interfaz, y a que el código que utiliza el TDA tan solo puede referirse a propiedades y operaciones especificadas en la interfaz, pueden realizarse cambios en la implementación sin necesidad de ningún cambio en el código en el que se use el TDA.

Flexibilidad

Diferentes implementaciones del TDA que tengan las mismas propiedades y operaciones son equivalentes y pueden utilizarse indistintamente en código que dependa de ese TDA. Esto permite un mayor grado de flexibilidad al utilizar TDAs en diversas situaciones. Por ejemplo, distintas implementaciones de un TDA pueden ser más eficientes en función de qué situaciones, y es posible utilizar la más eficiente en cada una, si son conocidas las condiciones a priori, lo que puede aumentar la eficiencia global.

Razonamiento formal

Un tipo de dato abstracto puede ser útil en un conjunto de programas, tal vez elaborados utilizando distintas tecnologías. En el caso de manejar tipos de dato abstracto complejos, o de propósito específico, pueden elaborarse pruebas formales o derivar propiedades formalmente sobre los mismos. Una vez elaboradas estas pruebas o demostradas las propiedades, los efectos de las mismas pueden ser experimentados en cualquier lenguaje o plataforma, e implementados de cualquier modo específico con garantías de respetar lo probado formalmente en cualquiera de las implementaciones.

Ejemplos

Algunos TDAs comunes, que se emplean en multitud de aplicaciones son:

• Contenedor
• Lista
• Conjunto
• Multiconjunto (una generalización del concepto de conjunto que permite elementos duplicados)
• Vector asociativo
• Multimap (una generalización del ector asociativo en el que se puede devolver más de un valor para la misma clave)
• Grafo
• Pila
• Cola
• Cola de prioridades
• Cola doblemente terminada
• Cola de prioridades doblemente terminada

Cada uno de estos TDAs pueden definirse de varias formas y variantes, no necesariamente equivalentes. Por ejemplo, una pila abstracta puede tener, o no, una operación de contar para saber cuantos elementos han sido apilados y que todavía estén sin desapilar. Estos detalles no solo afectan a los clientes de la interfaz, sino que también pueden ser significativos para elegir una implementación.

Ver también

• Método formal
• Principio de sustitución de Liskov
• Tipo de dato
• Teoría de tipos