En informática , un tipo abstracto de datos ( ADT ) es un modelo matemático para los tipos de datos , definido por su comportamiento ( semántica ) desde el punto de vista de un usuario de los datos, específicamente en términos de valores posibles, operaciones posibles sobre datos de este tipo y el comportamiento de estas operaciones. Este modelo matemático contrasta con las estructuras de datos , que son representaciones concretas de datos y son el punto de vista de un implementador, no de un usuario. Por ejemplo, una pila tiene operaciones push/pop que siguen una regla de último en entrar, primero en salir, y se pueden implementar de manera concreta utilizando una lista o una matriz. Otro ejemplo es un conjunto que almacena valores, sin ningún orden particular , y sin valores repetidos. Los valores en sí mismos no se recuperan de los conjuntos; en cambio, se prueba un valor para determinar su pertenencia para obtener un booleano "en" o "no en".
Los TAD son un concepto teórico, utilizado en semántica formal y verificación de programas y, de manera menos estricta, en el diseño y análisis de algoritmos , estructuras de datos y sistemas de software . La mayoría de los lenguajes informáticos convencionales no admiten directamente la especificación formal de TAD. Sin embargo, varias características del lenguaje corresponden a ciertos aspectos de la implementación de TAD y se confunden fácilmente con los TAD propiamente dichos; estos incluyen tipos abstractos , tipos de datos opacos , protocolos y diseño por contrato . Por ejemplo, en la programación modular , el módulo declara procedimientos que corresponden a las operaciones del TAD, a menudo con comentarios que describen las restricciones. Esta estrategia de ocultamiento de información permite cambiar la implementación del módulo sin perturbar los programas cliente , pero el módulo solo define informalmente un TAD. La noción de tipos de datos abstractos está relacionada con el concepto de abstracción de datos , importante en la programación orientada a objetos y las metodologías de diseño por contrato para la ingeniería de software . [1]
Los ADT fueron propuestos por primera vez por Barbara Liskov y Stephen N. Zilles en 1974, como parte del desarrollo del lenguaje CLU . [2] La especificación algebraica fue un tema importante de investigación en informática alrededor de 1980 y casi un sinónimo de tipos de datos abstractos en ese momento. [3] Tiene una base matemática en el álgebra universal . [4]
Formalmente, un TAD es análogo a una estructura algebraica en matemáticas, [5] que consiste en un dominio, una colección de operaciones y un conjunto de restricciones que las operaciones deben satisfacer. [6] El dominio a menudo se define implícitamente, por ejemplo, el objeto libre sobre el conjunto de operaciones del TAD. La interfaz del TAD normalmente se refiere solo al dominio y las operaciones, y quizás algunas de las restricciones sobre las operaciones, como precondiciones y postcondiciones; pero no a otras restricciones, como las relaciones entre las operaciones, que se consideran comportamiento. Hay dos estilos principales de especificaciones formales para el comportamiento, la semántica axiomática y la semántica operacional . [7]
A pesar de no ser parte de la interfaz, las restricciones son importantes para la definición del TAD; por ejemplo, una pila y una cola tienen interfaces similares para agregar/quitar elementos, pero son las restricciones las que distinguen el comportamiento de último en entrar, primero en salir del de primero en entrar, primero en salir. Las restricciones no consisten solo en ecuaciones como , fetch(store(S,v))=vsino también en fórmulas lógicas .
En el espíritu de la programación funcional , cada estado de una estructura de datos abstracta es una entidad o valor independiente. En esta perspectiva, cada operación se modela como una función matemática sin efectos secundarios . Las operaciones que modifican el TAD se modelan como funciones que toman el estado anterior como argumento y devuelven el nuevo estado como parte del resultado. El orden en el que se evalúan las operaciones es irrelevante, y la misma operación aplicada a los mismos argumentos (incluidos los mismos estados de entrada) siempre devolverá los mismos resultados (y estados de salida). Las restricciones se especifican como axiomas o leyes algebraicas que las operaciones deben satisfacer.
En el espíritu de la programación imperativa , una estructura de datos abstracta se concibe como una entidad que es mutable , lo que significa que existe una noción de tiempo y que el TAD puede estar en diferentes estados en diferentes momentos. Las operaciones cambian entonces el estado del TAD a lo largo del tiempo; por lo tanto, el orden en el que se evalúan las operaciones es importante, y la misma operación en las mismas entidades puede tener diferentes efectos si se ejecuta en diferentes momentos. Esto es análogo a las instrucciones de una computadora o los comandos y procedimientos de un lenguaje imperativo. Para subrayar este punto de vista, se acostumbra decir que las operaciones se ejecutan o se aplican , en lugar de evaluarse , de manera similar al estilo imperativo que se suele utilizar al describir algoritmos abstractos. Las restricciones se especifican normalmente en prosa.
Las presentaciones de los TAD suelen limitarse a las operaciones clave. Las presentaciones más detalladas suelen especificar las operaciones auxiliares de los TAD, como por ejemplo:
create(), que produce una nueva instancia del ADT;compare( s , t ), que prueba si los estados de dos instancias son equivalentes en algún sentido;hash( s ), que calcula alguna función hash estándar a partir del estado de la instancia;print( s ) o show( s ), que produce una representación legible por humanos del estado de la instancia.Estos nombres son ilustrativos y pueden variar entre autores. En las definiciones del TAD en estilo imperativo, también se suele encontrar:
initialize( s ), que prepara una instancia recién creada s para operaciones posteriores, o la restablece a algún "estado inicial";copy( s , t ), que pone a la instancia s en un estado equivalente al de t ;clone( t ), que realiza s ← create(), copy( s , t ), y devuelve s ;free( s ) o destroy( s ), que recupera la memoria y otros recursos utilizados por s .La freeoperación normalmente no es relevante ni significativa, ya que los TAD son entidades teóricas que no "usan memoria". Sin embargo, puede ser necesaria cuando se necesita analizar el almacenamiento utilizado por un algoritmo que utiliza el TAD. En ese caso, se necesitan axiomas adicionales que especifiquen cuánta memoria utiliza cada instancia del TAD, como una función de su estado, y qué cantidad de ella es devuelta al pool por free.
La definición de un TAD suele restringir los valores almacenados para sus instancias a los miembros de un conjunto específico X llamado rango de esas variables. Por ejemplo, una variable abstracta puede estar restringida a almacenar únicamente números enteros. Como en los lenguajes de programación, dichas restricciones pueden simplificar la descripción y el análisis de algoritmos y mejorar su legibilidad.
En el estilo operacional, a menudo no está claro cómo se manejan múltiples instancias y si la modificación de una instancia puede afectar a otras. Un estilo común de definición de TAD escribe las operaciones como si solo existiera una instancia durante la ejecución del algoritmo, y todas las operaciones se aplican a esa instancia. Por ejemplo, una pila puede tener operaciones push( x ) y pop(), que operan en la única pila existente. Las definiciones de TAD en este estilo se pueden reescribir fácilmente para admitir múltiples instancias coexistentes del TAD, agregando un parámetro de instancia explícito (como S en el ejemplo de pila a continuación) a cada operación que usa o modifica la instancia implícita. Algunos TAD no se pueden definir de manera significativa sin permitir múltiples instancias, por ejemplo, cuando una sola operación toma dos instancias distintas del TAD como parámetros, como una unionoperación en conjuntos o una compareoperación en listas.
El estilo de instancias múltiples a veces se combina con un axioma de aliascreate , es decir, que el resultado de () es distinto de cualquier instancia que ya esté en uso por el algoritmo. Las implementaciones de TAD aún pueden reutilizar la memoria y permitir que las implementaciones de create() produzcan una instancia creada previamente; sin embargo, definir que una instancia de este tipo incluso se "reutiliza" es difícil en el formalismo de TAD.
En términos más generales, este axioma puede reforzarse para excluir también el aliasing parcial con otras instancias, de modo que se pueda suponer que los TAD compuestos (como árboles o registros) y los TAD de estilo de referencia (como punteros) son completamente disjuntos. Por ejemplo, al extender la definición de una variable abstracta para incluir registros abstractos , las operaciones sobre un campo F de una variable de registro R claramente involucran a F , que es distinta de R , pero también parte de ella . Un axioma de aliasing parcial afirmaría que cambiar un campo de una variable de registro no afecta a ningún otro registro.
Algunos autores también incluyen la complejidad computacional ("costo") de cada operación, tanto en términos de tiempo (para las operaciones de cálculo) como de espacio (para la representación de valores), para ayudar en el análisis de algoritmos . Por ejemplo, se puede especificar que cada operación tome el mismo tiempo y cada valor tome el mismo espacio independientemente del estado del TAD, o que exista un "tamaño" del TAD y que las operaciones sean lineales, cuadráticas, etc. en el tamaño del TAD. Alexander Stepanov , diseñador de la Biblioteca de plantillas estándar de C++ , incluyó garantías de complejidad en la especificación STL, argumentando:
El motivo de introducir la noción de tipos de datos abstractos fue permitir módulos de software intercambiables. No se pueden tener módulos intercambiables a menos que estos módulos compartan un comportamiento de complejidad similar. Si reemplazo un módulo por otro módulo con el mismo comportamiento funcional pero con diferentes compensaciones de complejidad, el usuario de este código se llevará una sorpresa desagradable. Podría decirle todo lo que quisiera sobre la abstracción de datos y, aun así, no querría usar el código. Las afirmaciones de complejidad tienen que ser parte de la interfaz.
— Aleksandr Stepanov [8]
Otros autores no están de acuerdo y argumentan que un ADT de pila es el mismo independientemente de si se implementa con una lista enlazada o una matriz, a pesar de la diferencia en los costos de operación, y que una especificación de ADT debería ser independiente de la implementación.
Una variable abstracta puede considerarse como el TAD no trivial más simple, con la semántica de una variable imperativa. Admite dos operaciones, fetchy store. Las definiciones operacionales a menudo se escriben en términos de variables abstractas. En la semántica axiomática, siendo el tipo de la variable abstracta y el tipo de su contenido, es una función y es una función de tipo . La restricción principal es que siempre devuelve el valor x utilizado en la operación más reciente sobre la misma variable V , es decir . También podemos requerir que sobrescriba el valor por completo, .fetchstorefetchstorefetch(store(V,x)) = xstorestore(store(V,x1),x2) = store(V,x2)
En la semántica operacional, fetch( V ) es un procedimiento que devuelve el valor actual en la ubicación V , y store( V , x ) es un procedimiento con voidtipo de retorno que almacena el valor x en la ubicación V . Las restricciones se describen de manera informal como que las lecturas son consistentes con las escrituras. Como en muchos lenguajes de programación, la operación store( V , x ) a menudo se escribe V ← x (o alguna notación similar), y fetch( V ) está implícito siempre que se usa una variable V en un contexto donde se requiere un valor. Así, por ejemplo, V ← V + 1 se entiende comúnmente como una abreviatura de store( V , fetch( V ) + 1).
En esta definición, se supone implícitamente que los nombres son siempre distintos: almacenar un valor en una variable U no tiene efecto sobre el estado de una variable distinta V. Para hacer explícita esta suposición, se podría agregar la restricción de que:
store( U , x ); store( V , y ) } es equivalente a { store( V , y ); store( U , x ) }.Esta definición no dice nada sobre el resultado de evaluar fetch( V ) cuando V no está inicializado , es decir, antes de realizar cualquier storeoperación en V . La obtención antes del almacenamiento puede no estar permitida, puede definirse para tener un resultado determinado o puede dejarse sin especificar. Hay algunos algoritmos cuya eficiencia depende de la suposición de que tal a fetches legal y devuelve un valor arbitrario en el rango de la variable.
Una pila abstracta es una estructura de último en entrar, primero en salir. Generalmente se define mediante tres operaciones clave: push, que inserta un elemento de datos en la pila; pop, que elimina un elemento de datos de ella; y peeko top, que accede a un elemento de datos en la parte superior de la pila sin eliminarlo. Una definición completa de pila abstracta incluye también una función con valor booleanoempty ( S ) y una createoperación () que devuelve una instancia de pila inicial.
En la semántica axiomática, siendo el tipo de los estados de la pila y el tipo de los valores contenidos en la pila, estos podrían tener los tipos , , , y . En la semántica axiomática, crear la pila inicial es una operación "trivial" y siempre devuelve el mismo estado distinguido. Por lo tanto, a menudo se designa con un símbolo especial como Λ o "()". El predicado de la operación puede entonces escribirse simplemente como o . empty
Las restricciones son entonces pop(push(S,v))=(S,v), top(push(S,v))=v, [9] empty ( create) = T (una pila recién creada está vacía), empty( push( S , x )) = F (empujar algo dentro de una pila la hace no vacía). Estos axiomas no definen el efecto de top( s ) o pop( s ), a menos que s sea un estado de pila devuelto por a push. Dado que pushdeja la pila no vacía, esas dos operaciones pueden definirse como inválidas cuando s = Λ. A partir de estos axiomas (y la falta de efectos secundarios), puede deducirse que push(Λ, x ) ≠ Λ. Además, push( s , x ) = push( t , y ) si y solo si x = y y s = t .
Como en otras ramas de las matemáticas, es habitual suponer también que los estados de pila son sólo aquellos cuya existencia puede demostrarse a partir de los axiomas en un número finito de pasos. En este caso, significa que cada pila es una secuencia finitapop de valores, que se convierte en la pila vacía (Λ) después de un número finito de s. Por sí mismos, los axiomas anteriores no excluyen la existencia de pilas infinitas (que pueden repetirse popindefinidamente, produciendo cada vez un estado diferente) o pilas circulares (que vuelven al mismo estado después de un número finito de pops). En particular, no excluyen estados s tales que pop( s ) = s o push( s , x ) = s para algún x . Sin embargo, dado que no se pueden obtener dichos estados de pila a partir del estado de pila inicial con las operaciones dadas, se supone que "no existen".
En la definición operacional de una pila abstracta, push( S , x ) no retorna nada y pop( S ) produce el valor como resultado pero no el nuevo estado de la pila. Existe entonces la restricción de que, para cualquier valor x y cualquier variable abstracta V , la secuencia de operaciones { push( S , x ); V ← pop( S ) } es equivalente a V ← x . Dado que la asignación V ← x , por definición, no puede cambiar el estado de S , esta condición implica que V ← pop( S ) restaura S al estado que tenía antes de push( S , x ). De esta condición y de las propiedades de las variables abstractas, se sigue, por ejemplo, que la secuencia:
push( S , x ); push( S , y ); U ← pop( S ); push( S , z ); V ← pop( S ); W ← pop( S ) }donde x , y y z son valores cualesquiera, y U , V y W son variables distintas por pares, es equivalente a:
A diferencia de la semántica axiomática, la semántica operacional puede sufrir aliasing. Aquí se supone implícitamente que las operaciones en una instancia de pila no modifican el estado de ninguna otra instancia de TAD, incluidas otras pilas; es decir:
push( S , x ); push( T , y ) } es equivalente a { push( T , y ); push( S , x ) }.Un ejemplo más complejo es la jerarquía Boom de los tipos de datos abstractos de árbol binario , lista , bolsa y conjunto . [10] Todos estos tipos de datos pueden declararse mediante tres operaciones: null , que construye el contenedor vacío, single , que construye un contenedor a partir de un único elemento y append , que combina dos contenedores del mismo tipo. La especificación completa para los cuatro tipos de datos puede entonces darse añadiendo sucesivamente las siguientes reglas sobre estas operaciones:
El acceso a los datos se puede especificar mediante la coincidencia de patrones en las tres operaciones, por ejemplo, una función miembro para estos contenedores mediante:
Se debe tener cuidado de garantizar que la función sea invariante según las reglas pertinentes para el tipo de datos. Dentro de cada una de las clases de equivalencia implicadas por el subconjunto de ecuaciones elegido, debe producir el mismo resultado para todos sus miembros.
Algunos ADT comunes, que han demostrado ser útiles en una gran variedad de aplicaciones, son
Cada uno de estos ADT puede definirse de muchas maneras y variantes, no necesariamente equivalentes. Por ejemplo, una pila abstracta puede tener o no una countoperación que indique cuántos elementos se han insertado y cuántos no se han extraído. Esta elección marca una diferencia no solo para sus clientes sino también para la implementación.
En 1979 se propuso una extensión del TAD para gráficos de computadora: [11] un tipo de datos gráficos abstractos (AGDT). Fue introducido por Nadia Magnenat Thalmann y Daniel Thalmann . Los AGDT brindan las ventajas de los TAD con facilidades para construir objetos gráficos de manera estructurada.
Los tipos de datos abstractos son entidades teóricas que se utilizan (entre otras cosas) para simplificar la descripción de algoritmos abstractos, clasificar y evaluar estructuras de datos y describir formalmente los sistemas de tipos de los lenguajes de programación. Sin embargo, un TAD puede implementarse . Esto significa que cada instancia o estado del TAD está representado por algún tipo de datos o estructura de datos concretos , y para cada operación abstracta hay un procedimiento o función correspondiente , y estos procedimientos implementados satisfacen las especificaciones y axiomas del TAD hasta cierto estándar. En la práctica, la implementación no es perfecta y los usuarios deben ser conscientes de los problemas debido a las limitaciones de la representación y los procedimientos implementados.
Por ejemplo, los números enteros pueden especificarse como un TAD, definido por los valores distinguidos 0 y 1, las operaciones de suma, resta, multiplicación, división (con cuidado de la división por cero), comparación, etc., comportándose de acuerdo con los axiomas matemáticos familiares en álgebra abstracta como asociatividad, conmutatividad, etc. Sin embargo, en una computadora, los números enteros se representan más comúnmente como números binarios de ancho fijo de 32 bits o 64 bits . Los usuarios deben ser conscientes de los problemas con esta representación, como el desbordamiento aritmético , donde el TAD especifica un resultado válido pero la representación no puede acomodar este valor. No obstante, para muchos propósitos, el usuario puede ignorar estas infidelidades y simplemente usar la implementación como si fuera el tipo de datos abstracto.
Por lo general, existen muchas formas de implementar el mismo TAD, utilizando varias estructuras de datos concretas diferentes. Así, por ejemplo, una pila abstracta puede implementarse mediante una lista enlazada o mediante una matriz . Diferentes implementaciones del TAD, que tienen todas las mismas propiedades y capacidades, pueden considerarse semánticamente equivalentes y pueden usarse de manera algo intercambiable en el código que utiliza el TAD. Esto proporciona una forma de abstracción o encapsulación, y da una gran flexibilidad al usar objetos del TAD en diferentes situaciones. Por ejemplo, diferentes implementaciones del TAD pueden ser más eficientes en diferentes situaciones; es posible usar cada una en la situación en la que sean preferibles, aumentando así la eficiencia general. El código que utiliza una implementación del TAD según su interfaz seguirá funcionando incluso si se cambia la implementación del TAD.
Para evitar que los clientes dependan de la implementación, un ADT se empaqueta a menudo como un tipo de datos opaco o un identificador de algún tipo, [12] en uno o más módulos , cuya interfaz contiene solo la firma (número y tipos de los parámetros y resultados) de las operaciones. La implementación del módulo, es decir, los cuerpos de los procedimientos y la estructura de datos concreta utilizada, se puede ocultar a la mayoría de los clientes del módulo. Esto hace posible cambiar la implementación sin afectar a los clientes. Si la implementación está expuesta, se conoce en cambio como un tipo de datos transparente.
Los lenguajes orientados a objetos modernos, como C++ y Java , admiten una forma de tipos de datos abstractos. Cuando se utiliza una clase como tipo, se trata de un tipo abstracto que hace referencia a una representación oculta. En este modelo, un TAD se implementa normalmente como una clase y cada instancia del TAD suele ser un objeto de esa clase. La interfaz del módulo normalmente declara los constructores como procedimientos ordinarios y la mayoría de las demás operaciones del TAD como métodos de esa clase. Muchos lenguajes de programación modernos, como C++ y Java, vienen con bibliotecas estándar que implementan numerosos TAD en este estilo. Sin embargo, este enfoque no encapsula fácilmente las múltiples variantes de representación que se encuentran en un TAD. También puede socavar la extensibilidad de los programas orientados a objetos. En un programa orientado a objetos puro que utiliza interfaces como tipos, los tipos hacen referencia a comportamientos, no a representaciones.
La especificación de algunos lenguajes de programación es intencionalmente vaga en cuanto a la representación de ciertos tipos de datos integrados, definiendo únicamente las operaciones que se pueden realizar con ellos. Por lo tanto, esos tipos pueden considerarse como "TDA integrados". Algunos ejemplos son las matrices en muchos lenguajes de programación, como Awk , Lua y Perl , que pueden considerarse como una implementación de la lista abstracta.
En un lenguaje de especificación formal , los TAD pueden definirse axiomáticamente y el lenguaje permite manipular los valores de estos TAD, lo que proporciona una implementación directa e inmediata. La familia de lenguajes de programación OBJ , por ejemplo, permite definir ecuaciones para la especificación y reescribirlas para ejecutarlas. Sin embargo, estas implementaciones automáticas no suelen ser tan eficientes como las implementaciones dedicadas.
A modo de ejemplo, aquí se muestra una implementación de la pila abstracta anterior en el lenguaje de programación C.
Una interfaz de estilo imperativo podría ser:
typedef struct stack_Rep stack_Rep ; // tipo: representación de la instancia de la pila (registro opaco) typedef stack_Rep * stack_T ; // tipo: identificador de una instancia de la pila (puntero opaco) typedef void * stack_Item ; // tipo: valor almacenado en la instancia de la pila (dirección arbitraria) stack_T stack_create ( void ); // crea una nueva instancia de pila vacía void stack_push ( stack_Ts , stack_Itemx ); // agrega un elemento en la parte superior de la pila stack_Item stack_pop ( stack_Ts ) ; // elimina el elemento superior de la pila y lo devuelve bool stack_empty ( stack_Ts ); // verifica si la pila está vacía Esta interfaz se podría utilizar de la siguiente manera:
#include <stack.h> // incluye la interfaz de la pila stack_T s = stack_create (); // crea una nueva instancia de pila vacía int x = 17 ; stack_push ( s , & x ); // agrega la dirección de x en la parte superior de la pila void * y = stack_pop ( s ); // elimina la dirección de x de la pila y la devuelve if ( stack_empty ( s )) { } // hace algo si la pila está vacía Esta interfaz se puede implementar de muchas maneras. La implementación puede ser arbitrariamente ineficiente, ya que la definición formal del TAD, antes mencionada, no especifica cuánto espacio puede utilizar la pila ni cuánto tiempo debe durar cada operación. Tampoco especifica si el estado de la pila s continúa existiendo después de una llamada x ← pop( s ).
En la práctica, la definición formal debería especificar que el espacio es proporcional al número de elementos introducidos y no extraídos aún, y que cada una de las operaciones anteriores debe finalizar en un tiempo constante, independientemente de ese número. Para cumplir con estas especificaciones adicionales, la implementación podría utilizar una lista enlazada o una matriz (con redimensionamiento dinámico) junto con dos números enteros (un recuento de elementos y el tamaño de la matriz).
Las definiciones de ADT de estilo funcional son más apropiadas para lenguajes de programación funcionales y viceversa. Sin embargo, se puede proporcionar una interfaz de estilo funcional incluso en un lenguaje imperativo como C. Por ejemplo:
typedef struct stack_Rep stack_Rep ; // tipo: representación del estado de la pila (registro opaco) typedef stack_Rep * stack_T ; // tipo: identificador de un estado de la pila (puntero opaco) typedef void * stack_Item ; // tipo: valor de un estado de la pila (dirección arbitraria) stack_T stack_empty ( void ); // devuelve el estado de pila vacío stack_T stack_push ( stack_Ts , stack_Itemx ); // agrega un elemento en la parte superior del estado de pila y devuelve el estado de pila resultante stack_T stack_pop ( stack_Ts ) ; // elimina el elemento superior del estado de pila y devuelve el estado de pila resultante stack_Item stack_top ( stack_Ts ) ; // devuelve el elemento superior del estado de pila 
Medios relacionados con Tipos de datos abstractos en Wikimedia Commons