Na ciência da computação, um Tipo Abstrato de Dados (abreviado TAD) é um modelo matemático para tipos de dados; ou seja, na programação de computadores é um código que define e implementa um novo tipo de informação ou um novo tipo de objeto utilizado na linguagem de programação orientada a objetos, que é definido pelo seu comportamento (semântico) do ponto de vista de um usuário, do dado, especificamente em termos de valores possíveis, operações possíveis no dado desse tipo, e o comportamento dessas operações. Esse modelo matemático contrasta com estrutura de dados, que são representações concretas de dado, e são o ponto de vista de um implementador, não de um usuário.
Formalmente, um TAD pode ser definido como uma “classe de objetos do qual comportamento lógico é definido por um conjunto de valores e um conjunto de operações”;Dale & Walker 1996, p. 3. isso é análogo à uma estrutura algébrica na matemática. O que significa “comportamento” varia de autor para autor, com dois principais tipos de especificações formais para comportamento sendo especificação axiomática (algébrica) e um modelo abstrato; esses correspondem à semântica axiomática e semântica operacional de uma máquina abstrata, respectivamente. Alguns autores também incluem a complexidade computacional (“custo”), ambos em termos de tempo (para computar operações) e espaço (para representar valores). Na prática, vários tipos de dados comuns não são TADs, como a abstração não é perfeita, e usuários tem que ser avisados de problemas como overflow aritmético que são causados pela representação. Por exemplo, inteiros são geralmente armazenados com valores de tamanho fixo (32-bit ou 64-bit números binários), e assim quando o valor máximo é excedido, ocorre overflow de inteiro.
TAD é um conceito teórico, na ciência da computação, usada para o design e análise de algoritmos, estrutura de dados, e sistemas de software, e não corresponde às funcionalidades específicas de linguagens de programação – Linguagens de programação convencionais não suportam diretamente TADs. Entretanto, algumas funcionalidades de linguagens correspondem à certos aspectos dos TADs, e são facilmente confundidas com os próprios TADs; isso inclui tipos abstratos, tipos de dados opacos, protocolos(interface), e programação por contrato. TADs foram propostos por Barbara Liskov e Stephen N. Zilles em 1974, como parte do desenvolvimento da linguagem CLU.
Exemplos Por exemplo, inteiros são um TAD, definido pelos valores ..., -2, -1, 0, 1, 2, ..., e pelas operações de adição, subtração, multiplicação, e divisão, juntos com maior que, menor que, etc., que se comportam de acordo com a matemática (com cuidado para divisão de inteiros), independentemente de como os inteiros são representados pelo computador. Explicitamente, “comportamento” inclui obedecer a vários axiomas (associatividade e comutatividade da adição, etc.), e precondições nas operações (não dividir por zero). Tipicamente inteiros são representados numa estrutura de dados como números binários, frequentemente como complemento de dois, mas pode ser codificação binária decimal ou em complemento de um, mas o usuário é abstraído da escolha concreta de representação, e pode simplesmente usar o dado como tipo de dado.
Um TAD consiste não apenas de operações, mas também de valores subjacentes de dados e das restrições nas operações. Uma “interface” tipicamente se refere apenas às operações, e talvez algumas das restrições nas operações, particularmente precondições e pós-condições, mas não outras restrições, como as relações entre as operações.
Por exemplo, uma pilha abstrata, que possui estrutura last-in-first-out (LIFO), pode ser definido por três operações: push(empilhar), que insere o dado na pilha; pop(desempilhar), que remove o dado da pilha; e peek ou top, que acessa o dado no topo da pilha sem desempilha-lo. Numa fila abstrata, que possui estrutura first-in-first-out (FIFO), também possui três operações: enqueue(enfileirar), que insere o dado na fila; dequeue(desenfileirar), que remove o primeiro dado da fila; e front, que acessa e apresenta o primeiro dado da fila. Não haveria forma de diferenciar esses dois tipos de dado a menos que seja introduzida uma restrição matemática que, para uma pilha, especifique que cada desempilhar("pop") sempre retornará o dado empilhado("pushed") mais recente que não foi desempilhado ainda. Ao analisar a eficiência de algoritmos que usam pilhas, pode-se também especificar que todas as operações levam o mesmo tempo, não importa quantos itens de dados foram colocados na pilha, e que a pilha usa uma quantidade constante de armazenamento para cada elemento.
Introdução Tipos abstratos de dados são entidades puramente teóricas, usadas (entre outras coisas) para simplificar a descrição de algoritmos abstratos, para classificar e avaliar estrutura de dados, e para formalmente descrever os sistemas de tipos de linguagens de programação. No entanto, um TAD pode ser implementado por um tipo específico de dado ou estrutura de dado, em várias formas e em várias linguagens de programação; ou descritos em uma linguagem formal de especificação. TADs são frequentemente implementadas como módulos: a interface do módulo declara procedimentos que correspondem à uma operação dos TADs, algumas vezes com comentários que descrevem as restrições. Essa estratégia de “information hiding” permite que a implementação dos módulos seja alterada sem perturbar os programas clientes.
O termo tipo abstrato de dado também pode ser considerado como uma abordagem generalizada de uma série de estruturas algébricas, como lattices, grupos e anéis. A noção de tipo abstrato de dado está relacionada ao conceito de abstração de dados, importante na programação orientada a objetos e metodologias de programação por contrato para o desenvolvimento de software.
Definindo um tipo abstrato de dado Um tipo abstrato de dado é definido como um modelo matemático de objetos de dados que constituem um tipo de dado, bem como as funções que operam nesses objetos. Não há padrão para defini-los. Uma ampla divisão pode ser traçada entre os estilos imperativo e funcional.
Definição de estilo imperativo Na filosofia de linguagens de programação imperativas, uma estrutura de dado abstrata é concebida como uma entidade mutável - o que significa que pode estar em estados diferentes em momentos diferentes. Algumas operações podem alterar o estado do TAD; portanto, a ordem em que as operações são avaliadas é importante, e a mesma operação nas mesmas entidades pode ter efeitos diferentes se executada em momentos diferentes - exatamente como as instruções de um computador ou os comandos e procedimentos de uma linguagem imperativa. Para enfatizar essa visão, é comum dizer que as operações são executadas ou aplicadas, ao invés de avaliadas. O estilo imperativo é frequentemente usado ao descrever algoritmos abstratos. (Ver The Art of Computer Programming de Donald Knuth para mais detalhes).
Variável abstrata As definições do estilo imperativo de TADs frequentemente depende do conceito de variável abstrata, que pode ser considerada como a TAD não trivial mais simples. Uma variável V é uma entidade mutável que admite duas operações:
store (V, x) onde x é um valor de natureza não especificada; fetch (V) que fornece um valor,
com a restrição de
fetch(V) sempre retorna o valor x usado na operação de store (V, x) mais recente na mesma variável V.
Como em muitas linguagens de programação, a operação store (V, x) é frequentemente escrita V ← x (ou outra notação similar), e fetch(V) está implícito sempre que uma variável V é usada em um contexto onde um valor é necessário. Assim, por exemplo, V ← V+1 é comumente entendido como uma abreviação de store(V, fetch(V) + 1).
Nesta definição, é implicitamente assumido que armazenar um valor em uma variável U não tem efeito sobre o estado de uma variável distinta V. Para tornar esta suposição explícita, pode-se adicionar a restrição de que
se U e V são variáveis distintas, a sequência {store (U, x); store (V,y)} é equivalente a {store (V, y); store(U, x)}.
De forma mais geral, as definições de TAD muitas vezes assumem que qualquer operação que altera o estado de uma instância do TAD não tem efeito sobre o estado de qualquer outra instância (incluindo outras instâncias do mesmo TAD) - a menos que os axiomas do TAD impliquem que as duas instâncias estão conectadas (aliased). Por exemplo, ao estender a definição de uma variável abstrata para incluir registros abstratos, a operação que seleciona um campo de uma variável de registro R deve produzir uma variável V que é conectada com aquela parte do R.
A definição de uma variável abstrata V também pode restringir os valores armazenados x para membros de um conjunto específico X, chamado de intervalo ou tipo de V. Como nas linguagens de programação, tais restrições podem simplificar a descrição e análise de algoritmos, e melhorar sua legibilidade.
Observe que esta definição não implica nada sobre o resultado da avaliação de fetch(V) quando V não é inicializado, ou seja, antes de realizar qualquer operação de armazenamento em V. Um algoritmo que faz isso geralmente é considerado inválido porque seu efeito não é definido. (No entanto, existem alguns algoritmos importantes cuja eficiência depende fortemente da suposição de que tal fetch é legal e retorna algum valor arbitrário no intervalo da variável).
Criação de instância Alguns algoritmos precisam criar novas instâncias de alguns TAD (como novas variáveis ou novas pilhas). Para descrever tais algoritmos, geralmente inclui-se na definição de TAD uma operação create() que produz uma instância de TAD, geralmente com axiomas equivalentes a
o resultado de create() é distinto de qualquer instância usada pelo algoritmo
Esse axioma pode ser reforçado para excluir também aliasing parcial com outras instâncias. Por outro lado, esse axioma ainda permite implementações do create() para produzir uma instância criada anteriormente que se tornou inacessível para o programa.
Exemplo: pilha abstrata (imperativo) Outro exemplo, uma definição de estilo imperativo de uma pilha abstrata podem especificar que o estado de uma pilha S pode ser modificado apenas pelas operações
push(S,x), onde x é um valor de natureza não especificada; pop(S), que fornece um valor como resultado,
com a restrição de
Para qualquer valor de x e uma variável abstrata V, a sequência de operações {push(S, x); V ← pop(S)} é equivalente a V ← x.
Uma vez que a atribuição V ← x, por definição, não pode alterar o estado de S, esta condição implica que V ← pop (S) restaura S ao estado que tinha antes do push(S, x). A partir desta condição e das propriedades das variáveis abstratas, segue-se, por exemplo, que a sequência
{ push(S, x); push(S, y); U ← pop(S); push(S, z); V ← pop(S); W ← pop(S) }
onde x, y e z são quaisquer valores, e U, V, W são variáveis distintas entre pares, é equivalente a
{ U ← y; V ← z; W ← x }
Aqui, é implicitamente assumido que as operações em uma instância de pilha não modificam o estado de nenhuma outra instância do TAD, incluindo outras pilhas; isso é,
Para quaisquer valores x, y e quaisquer pilhas distintas S e T, a sequência {push (S, x); push (T, y)} é equivalente a {push (T, y); push(S, x)}.
Uma definição de pilha abstrata geralmente inclui também uma função de valor booleano empty(S) e uma operação create() que retorna uma instância de pilha, com axiomas equivalentes a
create() ≠ S para qualquer pilha anterior S (uma pilha recém-criada é diferente de todas as pilhas anteriores); empty(create()) (uma pilha recém-criada está vazia); not empty(push(S, x)) (colocar algo em uma pilha torna-o não vazio).
Estilo de instância única