En informática , un tipo de datos abstracto ( ADT ) es un modelo matemático para 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 posibles valores, posibles operaciones 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 puede implementar concretamente 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í no se recuperan de los conjuntos, sino que se prueba la pertenencia de un valor para obtener un valor booleano "dentro" o "no dentro".
Los ADT 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 ADT. Sin embargo, varias características del lenguaje corresponden a ciertos aspectos de la implementación de ADT y se confunden fácilmente con las ADT propiamente dichas; estos incluyen tipos abstractos , tipos de datos opacos , protocolos y diseño por contrato . Por ejemplo, en programación modular , el módulo declara procedimientos que corresponden a las operaciones de ADT, a menudo con comentarios que describen las restricciones. Esta estrategia de ocultación de información permite cambiar la implementación del módulo sin perturbar los programas cliente , pero el módulo solo define informalmente un ADT. 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 en metodologías de diseño por contrato para la ingeniería de software . [ cita necesaria ]
Los ADT fueron propuestos por primera vez por Barbara Liskov y Stephen N. Zilles en 1974, como parte del desarrollo del lenguaje CLU . [1] 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. [2] Tiene un fundamento matemático en el álgebra universal . [3]
Formalmente, una ADT es análoga a una estructura algebraica en matemáticas, [4] que consta de un dominio, una colección de operaciones y un conjunto de restricciones que las operaciones deben satisfacer. [5] El dominio a menudo se define implícitamente, por ejemplo, el objeto libre sobre el conjunto de operaciones ADT. La interfaz del ADT normalmente se refiere sólo al dominio y las operaciones, y quizás a algunas de las restricciones de las operaciones, como condiciones previas y posteriores; pero no a otras restricciones, como las relaciones entre las operaciones, que se consideran comportamiento. Hay dos estilos principales de especificaciones formales de comportamiento, la semántica axiomática y la semántica operativa . [6]
A pesar de no ser parte de la interfaz, las restricciones siguen siendo importantes para la definición del ADT; por ejemplo, una pila y una cola tienen interfaces similares para agregar y quitar elementos, pero son las restricciones las que distinguen el comportamiento de último en entrar, primero en salir del primero en entrar, primero en salir. Las restricciones no consisten sólo 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 separado. En esta vista, cada operación se modela como una función matemática sin efectos secundarios . Las operaciones que modifican el ADT 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 mutable , lo que significa que existe una noción de tiempo y el ADT puede estar en diferentes estados en diferentes momentos. Luego, las operaciones cambian el estado del ADT con el 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 efectos diferentes si se ejecuta en momentos diferentes. Esto es análogo a las instrucciones de una computadora o a los comandos y procedimientos de un lenguaje imperativo. Para subrayar esta visión, se acostumbra decir que las operaciones se ejecutan o aplican , en lugar de evaluarse , similar al estilo imperativo que se utiliza a menudo al describir algoritmos abstractos. Las restricciones suelen especificarse en prosa.
Las presentaciones de las ADT a menudo tienen un alcance limitado a operaciones clave. Las presentaciones más completas suelen especificar operaciones auxiliares en los ADT, 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 ADT de estilo imperativo, a menudo se encuentra también:
initialize( s ), que prepara una instancia s recién creada para operaciones posteriores, o la restablece a algún "estado inicial";copy( s , t ), que pone 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 TDA son entidades teóricas que no "utilizan memoria". Sin embargo, puede ser necesario cuando se necesita analizar el almacenamiento utilizado por un algoritmo que utiliza el ADT. En ese caso, se necesitan axiomas adicionales que especifiquen cuánta memoria utiliza cada instancia de ADT, en función de su estado, y cuánta memoria devuelve al grupo free.
La definición de un ADT a menudo restringe los valores almacenados para sus instancias a miembros de un conjunto específico X llamado rango de esas variables. Por ejemplo, una variable abstracta puede estar restringida para almacenar únicamente números enteros. Al igual que en los lenguajes de programación, tales restricciones pueden simplificar la descripción y el análisis de los algoritmos y mejorar su legibilidad.
En el estilo operativo, 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 ADT escribe las operaciones como si solo existiera una instancia durante la ejecución del algoritmo y todas las operaciones se aplicaran a esa instancia. Por ejemplo, una pila puede tener operaciones push( x ) y pop(), que operan en la única pila existente. Las definiciones de ADT en este estilo se pueden reescribir fácilmente para admitir múltiples instancias coexistentes de ADT, agregando un parámetro de instancia explícito (como S en el ejemplo de pila a continuación) a cada operación que use o modifique la instancia implícita. Algunas ADT no se pueden definir de manera significativa sin permitir múltiples instancias, por ejemplo, cuando una sola operación toma dos instancias distintas de la ADT como parámetros, como una unionoperación en conjuntos o una compareoperación en listas.
El estilo de instancia múltiple a veces se combina con un axioma de aliascreate , es decir, que el resultado de () es distinto de cualquier instancia que el algoritmo ya esté utilizando. Las implementaciones de ADT aún pueden reutilizar la memoria y permitir que las implementaciones de create() produzcan una instancia creada previamente; sin embargo, definir que tal instancia incluso se "reutiliza" es difícil en el formalismo ADT.
De manera más general, este axioma puede reforzarse para excluir también el alias parcial con otras instancias, de modo que se pueda suponer que las ADT compuestas (como árboles o registros) y las ADT de estilo de referencia (como punteros) son completamente independientes. Por ejemplo, cuando se extiende 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 alias 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 operaciones informáticas) como de espacio (para representar valores), para ayudar en el análisis de algoritmos . Por ejemplo, se puede especificar que cada operación toma el mismo tiempo y cada valor ocupa el mismo espacio independientemente del estado del ADT, o que hay un "tamaño" del ADT y las operaciones son lineales, cuadráticas, etc. el tamaño del TDA. Alexander Stepanov , diseñador de la biblioteca de plantillas estándar de C++ , incluyó garantías de complejidad en la especificación STL, argumentando:
La razón para introducir la noción de tipos de datos abstractos fue permitir módulos de software intercambiables. No puede tener módulos intercambiables a menos que estos módulos compartan un comportamiento de complejidad similar. Si reemplazo un módulo con otro módulo con el mismo comportamiento funcional pero con diferentes compensaciones de complejidad, el usuario de este código se sorprenderá desagradablemente. 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 deben ser parte de la interfaz.
— Alejandro Stepanov [7]
Otros autores no están de acuerdo, argumentando que un ADT de pila es el mismo ya sea que se implemente 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 debe ser independiente de la implementación.
Una variable abstracta puede considerarse como el TDA no trivial más simple, con la semántica de una variable imperativa. Admite dos operaciones, fetchy store. Las definiciones operativas suelen escribirse en términos de variables abstractas. En la semántica axiomática, dejar ser el tipo de la variable abstracta y ser el tipo de su contenido, es una función y es una función de tipo . La principal restricción es que siempre devuelve el valor x utilizado en la operación más reciente en la misma variable V , es decir . También podemos requerir que se sobrescriba el valor por completo .fetchstorefetchstorefetch(store(V,x)) = xstorestore(store(V,x1),x2) = store(V,x2)
En la semántica operativa, 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 informalmente ya 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ícita 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 siempre son distintos: almacenar un valor en una variable U no tiene ningún 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 recuperación antes de almacenar puede no estar permitida, definirse para que tenga un resultado determinado o dejarse sin especificar. Hay algunos algoritmos cuya eficiencia depende de la suposición de que tal fetches legal y devuelve algún 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; y peeko top, que accede a un elemento de datos en la parte superior de la pila sin eliminarlo. Una definición de pila abstracta completa 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 estados de estado y el tipo de 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 operación puede entonces escribirse simplemente como o . empty
Las restricciones son entonces pop(push(S,v))=(S,v), top(push(S,v))=v, [8] empty ( create) = T (una pila recién creada está vacía), empty( push( S , x )) = F (empujar algo dentro de una pila hace que no esté 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 pushque la pila no está vacía, se puede definir que esas dos operaciones no son válidas cuando s = Λ. De estos axiomas (y la falta de efectos secundarios), se puede deducir 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, se acostumbra suponer también que los estados de la 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 finita de valores, que se convierte en la pila vacía (Λ) después de un número finito de pops. Por sí mismos, los axiomas anteriores no excluyen la existencia de pilas infinitas (que se pueden popejecutar para siempre, produciendo cada vez un estado diferente) o pilas circulares (que regresan 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 alguna x . Sin embargo, dado que no se pueden obtener dichos estados de la pila a partir del estado inicial de la pila con las operaciones dadas, se supone que "no existen".
En la definición operativa de una pila abstracta, push( S , x ) no devuelve 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 deduce, 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 , W son variables distintas por pares, es equivalente a:
A diferencia de la semántica axiomática, la semántica operativa 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 ADT, incluidas otras pilas; eso es:
push( S , x ); push( T , y ) } es equivalente a { push( T , y ); push( S , x ) }.Un ejemplo más complicado es la jerarquía Boom de los tipos de datos abstractos árbol binario , lista , bolsa y conjunto . [9] Todos estos tipos de datos se pueden declarar mediante tres operaciones: null , que construye el contenedor vacío, single , que construye un contenedor a partir de un solo elemento y append , que combina dos contenedores del mismo tipo. La especificación completa para los cuatro tipos de datos se puede obtener agregando 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 para garantizar que la función sea invariante según las reglas relevantes para el tipo de datos. Dentro de cada una de las clases de equivalencia implícitas en 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 TDA puede definirse de muchas formas y variantes, no necesariamente equivalentes. Por ejemplo, una pila abstracta puede tener o no una countoperación que indique cuántos elementos se han enviado y aún no se han sacado. Esta elección marca la diferencia no sólo para sus clientes sino también para la implementación.
En 1979 se propuso una extensión de ADT para gráficos por computadora: [10] un tipo de datos gráficos abstractos (AGDT). Fue presentado por Nadia Magnenat Thalmann y Daniel Thalmann . Los AGDT ofrecen las ventajas de los ADT con funciones para construir objetos gráficos de forma 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 lenguajes de programación. Sin embargo, se puede implementar un ADT . Esto significa que cada instancia o estado de ADT 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 de ADT hasta algún estándar. En la práctica, la implementación no es perfecta y los usuarios deben ser conscientes de los problemas debidos a las limitaciones de la representación y los procedimientos implementados.
Por ejemplo, los números enteros pueden especificarse como un TDA, definido por los valores distinguidos 0 y 1, las operaciones de suma, resta, multiplicación, división (con cuidado con la división por cero), comparación, etc., comportándose de acuerdo con el conocido sistema matemático. axiomas 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 o 64 bits . Los usuarios deben tener en cuenta los problemas con esta representación, como el desbordamiento aritmético , donde el ADT especifica un resultado válido pero la representación no puede acomodar este valor. Sin embargo, 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, hay muchas formas de implementar el mismo ADT, utilizando varias estructuras de datos concretas diferentes. Así, por ejemplo, una pila abstracta se puede implementar mediante una lista enlazada o mediante una matriz . Diferentes implementaciones de ADT, que tienen las mismas propiedades y capacidades, pueden considerarse semánticamente equivalentes y pueden usarse de manera algo intercambiable en el código que usa ADT. Esto proporciona una forma de abstracción o encapsulación y brinda una gran flexibilidad al usar objetos ADT en diferentes situaciones. Por ejemplo, diferentes implementaciones del ADT pueden ser más eficientes en diferentes situaciones; es posible utilizar cada uno en la situación en la que sean preferibles, aumentando así la eficiencia general. El código que utiliza una implementación de ADT según su interfaz seguirá funcionando incluso si se cambia la implementación de ADT.
Para evitar que los clientes dependan de la implementación, un ADT a menudo se empaqueta como un tipo de datos opaco o identificador de algún tipo, [11] en uno o más módulos , cuya interfaz contiene solo la firma (número y tipos de 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 la conoce como tipo de datos transparente.
Los lenguajes modernos orientados a objetos, como C++ y Java , admiten una forma de tipos de datos abstractos. Cuando una clase se usa como tipo, es un tipo abstracto que hace referencia a una representación oculta. En este modelo, un ADT normalmente se implementa como una clase y cada instancia del ADT 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 ADT como métodos de esa clase. Muchos lenguajes de programación modernos, como C++ y Java, vienen con bibliotecas estándar que implementan numerosos ADT en este estilo. Sin embargo, este enfoque no encapsula fácilmente múltiples variantes de representación que se encuentran en un ADT. También puede socavar la extensibilidad de los programas orientados a objetos. En un programa puramente orientado a objetos que utiliza interfaces como tipos, los tipos se refieren 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 solo las operaciones que se pueden realizar con ellos. Por lo tanto, esos tipos pueden verse como "ADT 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 , las ADT se pueden definir axiomáticamente y el lenguaje permite manipular los valores de estas ADT, proporcionando así una implementación sencilla e inmediata. La familia de lenguajes de programación OBJ, por ejemplo, permite definir ecuaciones para su especificación y reescribirlas para ejecutarlas. Sin embargo, estas implementaciones automáticas no suelen ser tan eficientes como las implementaciones dedicadas.
Como ejemplo, aquí hay una implementación de la pila abstracta anterior en el lenguaje de programación C.
Una interfaz de estilo imperativo podría ser:
typedef estructura stack_Rep stack_Rep ; // tipo: representación de instancia de pila (registro opaco) typedef stack_Rep * stack_T ; // tipo: identificador de una instancia de pila (puntero opaco) typedef void * stack_Item ; // tipo: valor almacenado en la instancia de la pila (dirección arbitraria) stack_T stack_create ( vacío ); // crea una nueva instancia de pila vacía void stack_push ( stack_T s , stack_Item x ); // agrega un elemento en la parte superior de la pila stack_Item stack_pop ( stack_T s ); // elimina el elemento superior de la pila y lo devuelve bool stack_empty ( stack_T s ); // comprueba si la pila está vacía Esta interfaz podría usarse de la siguiente manera:
#include <stack.h> // incluye la interfaz de la pila pila_T s = pila_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 de ADT anterior no especifica cuánto espacio puede usar la pila ni cuánto tiempo debe tomar 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 empujados y aún no sacados; 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 usar una lista vinculada o una matriz (con cambio de tamaño 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 estructura stack_Rep stack_Rep ; // tipo: representación del estado de la pila (registro opaco) typedef stack_Rep * stack_T ; // tipo: maneja un estado de pila (puntero opaco) typedef void * stack_Item ; // tipo: valor de un estado de pila (dirección arbitraria) stack_T stack_empty ( vacío ); // devuelve el estado de la pila vacía stack_T stack_push ( stack_T s , stack_Item x ); // agrega un elemento en la parte superior del estado de la pila y devuelve el estado de la pila resultante stack_T stack_pop ( stack_T s ); // elimina el elemento superior del estado de la pila y devuelve el estado de la pila resultante stack_Item stack_top ( stack_T s ); // devuelve el elemento superior del estado de la pila 
Medios relacionados con tipos de datos abstractos en Wikimedia Commons