Tipo de datos abstracto

En el espíritu de la programación funcional , cada estado de una estructura de datos abstracta (TDA) es una entidad o valor independiente. Desde esta perspectiva, cada operación se modela como una función matemática sin efectos secundarios . Las operaciones que modifican la TDA se modelan como funciones que toman el estado anterior como argumento y devuelven el nuevo estado como parte del resultado. El orden en 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 implica que existe una noción de tiempo y que la TDA puede encontrarse en diferentes estados en distintos momentos. Las operaciones modifican el estado de la TDA a lo largo del tiempo; por lo tanto, el orden en que se evalúan las operaciones es importante, y la misma operación sobre las mismas entidades puede tener efectos diferentes si se ejecuta en momentos distintos. Esto es análogo a las instrucciones de un ordenador o a los comandos y procedimientos de un lenguaje imperativo. Para enfatizar esta perspectiva, se suele decir que las operaciones se ejecutan o aplican , en lugar de evaluarse , de forma similar al estilo imperativo que se utiliza a menudo al describir algoritmos abstractos. Las restricciones se especifican normalmente en prosa.

Las presentaciones de ADT suelen limitarse a las operaciones clave. Las presentaciones más completas suelen especificar operaciones auxiliares en los ADT, tales como:

• create(), que produce una nueva instancia del TAD;
• compare(s, t), que comprueba 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 bien show(s), que produce una representación legible para humanos del estado de la instancia.

Estos nombres son ilustrativos y pueden variar entre autores. En las definiciones de TAD de estilo imperativo, también se suele encontrar:

• initialize(s), que prepara una instancia recién creada spara operaciones posteriores, o la restablece a algún "estado inicial";
• copy(s), que coloca la instancia sen 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 usa cada instancia de TAD, en función de su estado, y cuánta de ella se devuelve al pool free.

La definición de un tipo de dato abstracto (TDA) suele restringir los valores almacenados para sus instancias a elementos de un conjunto específico X, denominado rango de dichas variables. Por ejemplo, una variable abstracta puede estar restringida a almacenar únicamente números enteros. Al igual que en los lenguajes de programación, estas restricciones pueden simplificar la descripción y el análisis de algoritmos , y mejorar su legibilidad.

En el estilo operacional, a menudo no queda claro cómo se manejan las múltiples instancias ni si la modificación de una instancia puede afectar a las demás. Un estilo común de definición de TAD consiste en escribir 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 sobre la única pila existente. Las definiciones de TAD en este estilo se pueden reescribir fácilmente para admitir múltiples instancias coexistentes del TAD, añadiendo un parámetro de instancia explícito (como S en el ejemplo de la pila que se muestra a continuación) a cada operación que utilice o modifique la instancia implícita. Algunos TAD no se pueden definir de forma 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 sobre conjuntos o una compareoperación sobre listas.

El estilo de instancias múltiples a veces se combina con un axioma de alias , a saber, que el resultado de create() es distinto de cualquier instancia que ya esté siendo utilizada por el algoritmo. Las implementaciones de TAD aún pueden reutilizar memoria y permitir que las implementaciones de create() generen una instancia creada previamente; sin embargo, definir que dicha instancia sea "reutilizada" es difícil en el formalismo de los TAD.

En términos más generales, este axioma puede reforzarse para excluir también el aliasing parcial con otras instancias, de modo que los TAD compuestos (como árboles o registros) y los TAD de estilo referencial (como punteros) pueden considerarse 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 involucran claramente a F , que es distinto de R , pero también forma parte de ella. Un axioma de aliasing parcial establecerí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 de cálculo) como de espacio (para representar valores), para facilitar el análisis de algoritmos . Por ejemplo, se puede especificar que cada operación requiere el mismo tiempo y cada valor el mismo espacio, independientemente del estado del TAD, o que existe un "tamaño" del TAD y que las operaciones son lineales, cuadráticas, etc., en función del 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 de la STL, argumentando:

La razón para introducir el concepto de tipos de datos abstractos fue permitir la intercambiabilidad de módulos de software. No se pueden tener módulos intercambiables a menos que compartan un comportamiento de complejidad similar. Si reemplazo un módulo por otro con el mismo comportamiento funcional pero con diferentes compensaciones de complejidad, el usuario de este código se llevará una desagradable sorpresa. Podría explicarle 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 formar parte de la interfaz.

Otros autores discrepan, argumentando que un tipo de dato abstracto (TDA) de pila es el mismo tanto si se implementa con una lista enlazada como con un array, a pesar de la diferencia en los costes operativos, y que la especificación de un TDA debería ser independiente de la implementación.

Una variable abstracta puede considerarse 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, dejando${\displaystyle V}$ser el tipo de la variable abstracta y${\displaystyle X}$sea ​​el tipo de su contenido, fetches una función${\displaystyle V\to X}$y storees una función de tipo${\displaystyle V\times X\to V}$. La restricción principal es que fetchsiempre devuelva el valor xstore utilizado en la operación más reciente sobre la misma variable V , es decir fetch(store(V,x)) = x. También podemos requerir que storesobrescriba el valor por completo, store(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 informalmente como que las lecturas son consistentes con las escrituras. Como en muchos lenguajes de programación, la operación store( V , x ) se suele escribir 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 asume 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:

• Si U y V son variables distintas, la secuencia { 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 sobre V. La obtención de datos antes de su almacenamiento puede estar prohibida, definida para tener un resultado determinado o quedar sin especificar. Hay algunos algoritmos cuya eficiencia depende de la suposición de que tal operación fetches válida y devuelve algún valor arbitrario dentro del rango de la variable.

Una pila abstracta es una estructura de último en entrar, primero en salir. Generalmente se define mediante tres operaciones clave: pushinsertar un elemento de datos en la pila; popeliminar un elemento de datos; y peekacceder topa 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 booleanaempty ( S ) y una createoperación () que devuelve una instancia inicial de la pila.

En la semántica axiomática, dejando${\displaystyle S}$ser el tipo de estados de pila y${\displaystyle X}$sean el tipo de valores contenidos en la pila, estos podrían tener los tipos${\displaystyle push:S\to X\to S}$,${\displaystyle pop:S\to (S,X)}$,${\displaystyle top:S\to X}$,${\displaystyle crear:S}$, y${\displaystyle empty:S\to \mathbb {B} }$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 emptypredicado de la operación se puede escribir entonces simplemente como${\displaystyle s=\Lambda }$o${\displaystyle s\neq \Lambda }$.

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 a 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 un push. Dado que pushdeja la pila no vacía, esas dos operaciones pueden definirse como invá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, es habitual suponer que los estados de la pila son solo aquellos cuya existencia puede probarse 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 (Λ) tras un número finito de iteraciones ( pops). Por sí mismos, los axiomas anteriores no excluyen la existencia de pilas infinitas (que pueden popiterarse indefinidamente, generando cada vez un estado diferente) ni de pilas circulares (que vuelven al mismo estado tras un número finito de popiteraciones). 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 tales estados de pila a partir del estado inicial con las operaciones dadas, se supone que "no existen".

En la definición operacional 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 entre sí, es equivalente a:

{ U ← y ; V ← z ; W ← x }

A diferencia de la semántica axiomática, la semántica operacional puede sufrir de aliasing. Aquí se asume 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:

• Para cualesquiera valores x , y , y cualesquiera pilas distintas S y T , la secuencia { 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 árbol binario , lista , bolsa y conjunto . ^{[ 10 ]} 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 dar 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:

Es necesario asegurarse de que la función sea invariante según las reglas pertinentes para el tipo de dato. 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 tipos de datos abstractos (TDA) comunes, que han demostrado ser útiles en una gran variedad de aplicaciones, son:

Cada uno de estos tipos de datos abstractos (TDA) puede definirse de muchas maneras y variantes, no necesariamente equivalentes. Por ejemplo, una pila abstracta puede o no tener una countoperación que indique cuántos elementos se han insertado y aún no se han extraído. Esta elección tiene repercusiones no solo para los clientes, sino también para la implementación.

Tipo de datos gráficos abstractos

En 1979 se propuso una extensión de ADT para gráficos por computadora: ^{[ 11 ]} un tipo de datos gráficos abstractos (AGDT). Fue introducido por Nadia Magnenat Thalmann y Daniel Thalmann . Los AGDT ofrecen las ventajas de los ADT con facilidades para construir objetos gráficos de manera estructurada.

Como ejemplo, aquí hay una implementación de la pila abstracta anterior en el lenguaje de programación C.

// tipo: representación de instancia de pila (registro opaco) typedef struct { // implementación aquí } Pila ;// tipo: valor almacenado en la instancia de la pila (dirección arbitraria) typedef void * Item ;// crea una nueva instancia de pila vacía Stack * stack_create ( void );// agrega un elemento en la parte superior de la pila void stack_push ( Stack * s , Item x );// elimina el elemento superior de la pila y lo devuelve Item stack_pop ( Stack * s );// Comprueba si la pila está vacía bool stack_is_empty ( Stack * s );

#include <stack.h>int main () { Stack * s = stack_create (); // crea una nueva instancia de pila vacía int x = 17 ;// agrega la dirección de x en la parte superior de la pila stack_push ( s , & x ); // elimina la dirección de x de la pila y la devuelve Item y = stack_pop ( s );if ( stack_is_empty ( s )) { // hace algo si la pila está vacía printf ( "¡La pila está vacía!" ); } }

// tipo: representación de instancia de pila (registro opaco) typedef struct { // implementación aquí } Pila ;// tipo: valor almacenado en la instancia de la pila (dirección arbitraria) typedef void * Item ;// Devuelve el estado de pila vacía Stack * stack_is_empty ( void );// agrega un elemento en la parte superior del estado de la pila y devuelve el estado de la pila resultante Stack * stack_push ( Stack * s , Item x );// elimina el elemento superior del estado de la pila y devuelve el estado de pila resultante Stack * stack_pop ( Stack * s );// devuelve el elemento superior del estado de la pila Item stack_top ( Stack * s );