Tipo de datos abstracto - Abstract data type

No confundir con el tipo de datos algebraicos .

En informática , un tipo de datos abstracto ( ADT ) es un modelo matemático para tipos de datos . Un tipo de datos abstracto se define 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.

Formalmente, un ADT puede definirse como una "clase de objetos cuyo comportamiento lógico está definido por un conjunto de valores y un conjunto de operaciones"; esto es análogo a una estructura algebraica en matemáticas. Lo que se entiende por "comportamiento" varía según el autor, siendo los dos tipos principales de especificaciones formales para el comportamiento la especificación axiomática (algebraica) y un modelo abstracto; estos corresponden a la semántica axiomática y la semántica operacional de una máquina abstracta , respectivamente. Algunos autores también incluyen la complejidad computacional ("costo"), tanto en términos de tiempo (para operaciones de computación) como de espacio (para representar valores). En la práctica, muchos tipos de datos comunes no son ADT, ya que la abstracción no es perfecta y los usuarios deben ser conscientes de problemas como el desbordamiento aritmético que se deben a la representación. Por ejemplo, los enteros a menudo se almacenan como valores de ancho fijo (números binarios de 32 bits o 64 bits) y, por lo tanto, experimentan un desbordamiento de enteros si se excede el valor máximo.

Los ADT son un concepto teórico, en informática, que se utiliza en el diseño y análisis de algoritmos , estructuras de datos y sistemas de software, y no corresponden a características específicas de los lenguajes informáticos; los lenguajes informáticos principales no admiten directamente los ADT especificados formalmente. Sin embargo, varias características del lenguaje corresponden a ciertos aspectos de los ADT y se confunden fácilmente con los ADT propiamente dichos; estos incluyen tipos abstractos , tipos de datos opacos , protocolos y diseño por contrato . Los ADT fueron propuestos por primera vez por Barbara Liskov y Stephen N. Zilles en 1974, como parte del desarrollo del lenguaje CLU .

Ejemplos de

Por ejemplo, los enteros son un ADT, definido como los valores ..., −2, −1, 0, 1, 2, ..., y por las operaciones de suma, resta, multiplicación y división, junto con mayor que , menos que, etc., que se comportan de acuerdo con las matemáticas familiares (con cuidado de la división de enteros ), independientemente de cómo los números enteros sean representados por la computadora. Explícitamente, "comportamiento" incluye obedecer a varios axiomas (asociatividad y conmutatividad de la adición, etc.) y condiciones previas a las operaciones (no se puede dividir por cero). Normalmente, los enteros se representan en una estructura de datos como números binarios , la mayoría de las veces como complemento a dos , pero pueden ser decimales codificados en binario o en complemento a unos , pero el usuario se abstrae de la elección concreta de representación y simplemente puede usar los datos como tipos de datos.

Un ADT consta no solo de operaciones, sino también de valores de los datos subyacentes y de restricciones sobre las operaciones. Una "interfaz" se refiere típicamente sólo a las operaciones, y quizás a algunas de las limitaciones de las operaciones, en particular condiciones previas y posteriores, pero no a otras limitaciones, como las relaciones entre las operaciones.

Por ejemplo, una pila abstracta , que es una estructura de último en entrar, primero en salir, podría definirse mediante tres operaciones:, pushque inserta un elemento de datos en la pila; pop, que elimina un elemento de datos de él; y peeko top, que accede a un elemento de datos en la parte superior de la pila sin quitarlo. Una cola abstracta , que es una estructura de primero en entrar enqueue, primero en salir, también tendría tres operaciones:, que inserta un elemento de datos en la cola; dequeue, que elimina el primer elemento de datos; y frontque accede y sirve el primer elemento de datos en la cola. No habría forma de diferenciar estos dos tipos de datos a menos que se introduzca una restricción matemática que, para una pila, especifique que cada elemento emergente siempre devuelve el elemento enviado más recientemente que aún no se ha publicado. Al analizar la eficiencia de los algoritmos que usan pilas, también se puede especificar que todas las operaciones toman el mismo tiempo sin importar cuántos elementos de datos se hayan introducido en la pila, y que la pila usa una cantidad constante de almacenamiento para cada elemento.

Introducción

Los tipos de datos abstractos son entidades puramente 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, un ADT puede implementarse mediante tipos de datos o estructuras de datos específicos , de muchas formas y en muchos lenguajes de programación; o descrito en un lenguaje de especificación formal . Los ADT a menudo se implementan como módulos : la interfaz del módulo declara procedimientos que corresponden a las operaciones de ADT, a veces 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 del cliente .

El término tipo de datos abstractos también se puede considerar como un enfoque generalizado de una serie de estructuras algebraicas , como retículas, grupos y anillos. 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 el diseño por metodologías de contrato para el desarrollo de software .

Definición de un tipo de datos abstracto

Un tipo de datos abstracto se define como un modelo matemático de los objetos de datos que componen un tipo de datos, así como las funciones que operan en estos objetos. No existen convenciones estándar para definirlos. Puede trazarse una amplia división entre estilos de definición "imperativos" y "funcionales".

Definición de estilo imperativo

En la filosofía de los lenguajes de programación imperativos , una estructura de datos abstracta se concibe como una entidad que es mutable, lo que significa que puede estar en diferentes estados en diferentes momentos. Algunas operaciones pueden cambiar el estado del ADT; 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, al igual que 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 aplican , en lugar de evaluarse . El estilo imperativo se usa a menudo cuando se describen algoritmos abstractos. (Consulte El arte de la programación informática de Donald Knuth para obtener más detalles)

Variable abstracta

Las definiciones de estilo imperativo de ADT a menudo dependen del concepto de una variable abstracta , que puede considerarse como la ADT no trivial más simple. Una variable abstracta V es una entidad mutable que admite dos operaciones:

  • store( V , x ) donde x es un valor de naturaleza no especificada;
  • fetch( V ), que arroja un valor,

con la restricción de que

  • fetch( V ) siempre devuelve el valor x utiliza en la más reciente store( V , x ) operación en la misma variable V .

Como en tantos 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 el almacenamiento de un valor en una variable T 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

  • si U y V son variables distintas, la secuencia { store( U , x ); store( V , y )} es equivalente a { store( V , y ); store( U , x )}.

De manera más general, las definiciones de ADT a menudo asumen que cualquier operación que cambia el estado de una instancia de ADT no tiene ningún efecto sobre el estado de cualquier otra instancia (incluidas otras instancias del mismo ADT), a menos que los axiomas de ADT impliquen que las dos instancias están conectadas ( alias ) en ese sentido. Por ejemplo, cuando se extiende la definición de una variable abstracta para incluir abstractos registros , la operación que selecciona un campo de una variable de registro R deben ceder una variable V que se alias a la parte de R .

La definición de una variable abstracta V también puede restringir los valores almacenados x a los miembros de un conjunto específico X , llamado el rango o tipo de V . 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.

Tenga en cuenta que esta definición no implica nada sobre el resultado de la evaluación fetch( V ) cuando V es no inicializado , es decir, antes de realizar cualquier storeoperación en V . Un algoritmo que lo hace generalmente se considera inválido porque su efecto no está definido. (Sin embargo, existen algunos algoritmos importantes cuya eficiencia depende en gran medida de la suposición de que tal fetches legal y devuelve algún valor arbitrario en el rango de la variable).

Creación de instancias

Algunos algoritmos necesitan crear nuevas instancias de algunos ADT (como nuevas variables o nuevas pilas). Para describir tales algoritmos, generalmente se incluye en la definición de ADT una createoperación () que produce una instancia de ADT, generalmente con axiomas equivalentes a

  • el resultado de create() es distinto de cualquier instancia utilizada por el algoritmo.

Este axioma puede reforzarse para excluir también el alias parcial con otros casos. Por otro lado, este axioma todavía permite que las implementaciones de create() produzcan una instancia creada previamente que se ha vuelto inaccesible para el programa.

Ejemplo: pila abstracta (imperativo)

Como otro ejemplo, una definición de estilo imperativo de una pila abstracta podría especificar que el estado de una pila S sólo puede ser modificado por las operaciones

  • push( S , x ), donde x es algún valor de naturaleza no especificada;
  • pop( S ), que arroja un valor como resultado,

con 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 , z son valores cualesquiera, y U , V , W son variables distintas por pares, es equivalente a

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

Aquí se asume implícitamente que las operaciones en una instancia de pila no modifican el estado de ninguna otra instancia de ADT, incluidas otras pilas; es decir,

  • Para cualquier valor x , y , y cualquier pila distinta S y T , la secuencia { push( S , x ); push( T , y )} es equivalente a { push( T , y ); push( S , x )}.

Una definición de pila abstracta generalmente incluye también una función de valor booleanoempty ( S ) y una createoperación () que devuelve una instancia de pila, con axiomas equivalentes a

  • create() ≠ S para cualquier pila anterior S (una pila recién creada es distinta de todas las pilas anteriores);
  • empty( create()) (una pila recién creada está vacía);
  • not empty( push( S , x )) (empujar algo en una pila hace que no esté vacío).

Estilo de instancia única

A veces, un ADT se define como si solo existiera una instancia de él durante la ejecución del algoritmo, y todas las operaciones se aplicaron a esa instancia, que no se anota explícitamente. Por ejemplo, la pila abstracta anterior podría haberse definido con las 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 anterior) a cada operación que usa o modifica la instancia implícita.

Por otro lado, algunos ADT no se pueden definir de manera significativa sin asumir múltiples instancias. Este es el caso cuando una sola operación toma dos instancias distintas del ADT como parámetros. Por ejemplo, considere aumentar la definición de la pila abstracta con una operación compare( S , T ) que verifica si las pilas S y T contienen los mismos elementos en el mismo orden.

Definición de estilo funcional

Otra forma de definir un ADT, más cercano al espíritu de la programación funcional , es considerar cada estado de la estructura como una entidad separada. En esta vista, cualquier operación que modifique el ADT se modela como una función matemática que toma el estado anterior como argumento y devuelve el nuevo estado como parte del resultado. A diferencia de las operaciones imperativas, estas funciones no tienen efectos secundarios . Por lo tanto, el orden en el que se evalúan 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).

En la vista funcional, en particular, no hay forma (o necesidad) de definir una "variable abstracta" con la semántica de variables imperativas (es decir, con fetchy storeoperaciones). En lugar de almacenar valores en variables, uno los pasa como argumentos a funciones.

Ejemplo: pila abstracta (funcional)

Por ejemplo, una definición completa de estilo funcional de una pila abstracta podría usar las tres operaciones:

  • push: toma un estado de pila y un valor arbitrario, devuelve un estado de pila;
  • top: toma un estado de pila, devuelve un valor;
  • pop: toma un estado de pila, devuelve un estado de pila.

En una definición de estilo funcional no hay necesidad de una createoperación. De hecho, no existe la noción de "instancia de pila". Los estados de la pila se pueden considerar como estados potenciales de una estructura de pila única, y los estados de dos pilas que contienen los mismos valores en el mismo orden se consideran estados idénticos. Esta vista en realidad refleja el comportamiento de algunas implementaciones concretas, como listas enlazadas con contras de hash .

En lugar de create(), una definición de estilo funcional de una pila abstracta puede asumir la existencia de un estado de pila especial, la pila vacía , designada por un símbolo especial como Λ o "()"; o defina una bottomoperación () que no tome argumentos y devuelva este estado de pila especial. Tenga en cuenta que los axiomas implican que

  • push(Λ, x ) ≠ Λ.

En una definición de estilo funcional de una pila, no se necesita un emptypredicado: en su lugar, se puede probar si una pila está vacía probando si es igual a Λ.

Tenga en cuenta que 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 no están definidas (por lo tanto, no son válidas) cuando s = Λ. Por otro lado, los axiomas (y la ausencia de efectos secundarios) implican que push( s , x ) = push( t , y ) si y solo si x = y y s = t .

Como en algunas otras ramas de las matemáticas, se acostumbra suponer también que los estados de la pila son solo aquellos cuya existencia puede demostrarse a partir de los axiomas en un número finito de pasos. En el ejemplo de pila abstracta anterior, esta regla 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 popeditar para siempre, cada vez produciendo un estado diferente) o pilas circulares (que regresan al mismo estado después de un número finito de pops). En particular, no excluyen los estados s tal que pop( s ) = s o push( s , x ) = s por alguna x . Sin embargo, dado que no se pueden obtener tales estados de pila con las operaciones dadas, se supone que "no existen".

Ya sea para incluir complejidad

Aparte del comportamiento en términos de axiomas, también es posible incluir, en la definición de una operación ADT, su complejidad algorítmica . 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 aún así no querría usar el código. Las afirmaciones de complejidad deben formar parte de la interfaz.

-  Alexander Stepanov

Ventajas de la mecanografía de datos abstractos

Encapsulamiento

Abstraction ofrece la promesa de que cualquier implementación del ADT tiene ciertas propiedades y habilidades; saber esto es todo lo que se requiere para hacer uso de un objeto ADT.

Localización del cambio

No será necesario editar el código que utiliza un objeto ADT si se cambia la implementación de ADT. Dado que cualquier cambio en la implementación debe cumplir con la interfaz, y dado que el código que usa un objeto ADT solo puede hacer referencia a las propiedades y habilidades especificadas en la interfaz, se pueden realizar cambios en la implementación sin requerir ningún cambio en el código donde se usa el ADT .

Flexibilidad

Las diferentes implementaciones del ADT, que tienen todas las mismas propiedades y habilidades, son equivalentes y pueden usarse de manera intercambiable en el código que usa el ADT. Esto proporciona una gran flexibilidad al utilizar 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 sea preferible, aumentando así la eficiencia general.

Operaciones típicas

Algunas operaciones que a menudo se especifican para ADT (posiblemente con otros nombres) son

  • 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.

En las definiciones de TDA de estilo imperativo, a menudo se encuentra también

  • create(), que produce una nueva instancia de ADT;
  • 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 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 recuperan la memoria y otros recursos utilizados por s .

La freeoperación normalmente no es relevante o significativa, ya que los ADT son entidades teóricas que no "usan 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 de ella se devuelve al grupo free.

Ejemplos de

Algunos ADT comunes, que han demostrado su utilidad en una gran variedad de aplicaciones, son

Cada uno de estos ADT 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 insertado y aún no se han revelado. Esta elección marca la diferencia no solo para sus 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: un tipo de datos gráficos abstractos (AGDT). Fue presentado por Nadia Magnenat Thalmann y Daniel Thalmann . Los AGDT brindan las ventajas de los ADT con facilidades para construir objetos gráficos de manera estructurada.

Implementación

Más información: tipo de datos opaco

Implementar un ADT significa proporcionar un procedimiento o función para cada operación abstracta. Las instancias de ADT están representadas por una estructura de datos concreta que es manipulada por esos procedimientos, de acuerdo con las especificaciones de ADT.

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 .

Para evitar que los clientes dependan de la implementación, un ADT a menudo se empaqueta como un tipo de datos opaco 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 permite 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.

Al implementar un ADT, cada instancia (en definiciones de estilo imperativo) o cada estado (en definiciones de estilo funcional) generalmente se representa mediante un identificador de algún tipo.

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 se refiere a una representación oculta. En este modelo, un ADT se implementa normalmente 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 otras operaciones de ADT como métodos de esa clase. Sin embargo, tal enfoque no encapsula fácilmente múltiples variantes representativas que se encuentran en un ADT. También puede socavar la extensibilidad de los programas orientados a objetos. En un programa orientado a objetos puro que usa interfaces como tipos, los tipos se refieren a comportamientos, no a representaciones.

Ejemplo: implementación de la pila abstracta

A modo de ejemplo, aquí es una implementación de la pila abstracta anteriormente en el lenguaje de programación C .

Interfaz de estilo imperativo

Una interfaz de estilo imperativo podría ser: 

typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;               // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                 // type: value stored in stack instance (arbitrary address)

stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty

Esta interfaz se puede utilizar de la siguiente manera: 

#include <stack.h>          // includes the stack interface

stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);     // removes the address of x from the stack and returns it
if (stack_empty(s)) { }     // does something if stack is empty

Esta interfaz se puede implementar de muchas formas. La implementación puede ser arbitrariamente ineficiente, ya que la definición formal del ADT, arriba, no especifica cuánto espacio puede usar la pila, ni cuánto tiempo debe tomar cada operación. También no especifica si el estado de la pila s sigue 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 revelados; y que cada una de las operaciones anteriores debe terminar en un período de 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).

Interfaz de estilo funcional

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;          // type: stack state representation (opaque record)
typedef stack_Rep* stack_T;                  // type: handle to a stack state (opaque pointer)
typedef void* stack_Item;                    // type: value of a stack state (arbitrary address)

stack_T stack_empty(void);                   // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s);                // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s);             // returns the top item of the stack state

Bibliotecas ADT

Muchos lenguajes de programación modernos, como C ++ y Java, vienen con bibliotecas estándar que implementan varios ADT comunes, como los enumerados anteriormente.

Tipos de datos abstractos integrados

La especificación de algunos lenguajes de programación es intencionalmente vaga sobre la representación de ciertos tipos de datos integrados, definiendo solo las operaciones que se pueden realizar en ellos. Por lo tanto, esos tipos pueden verse como "ADT incorporados". Algunos ejemplos son las matrices en muchos lenguajes de secuencias de comandos, como Awk , Lua y Perl , que se pueden considerar como una implementación de la lista abstracta.

Ver también

Notas

Citas

Referencias

Otras lecturas

enlaces externos