Tipo abstrato de dado – Wikipédia, a enciclopédia livre

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,^[1] 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”;^[2] 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;^[3] 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.^[4]

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.

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.^[5] 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.^[6]

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.

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

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

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.

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

Às vezes, um TAD é definido como se apenas uma instância dele existisse durante a execução do algoritmo e todas as operações fossem aplicadas a essa instância, o que não é explicitamente notado. Por exemplo, a pilha abstrata acima poderia ter sido definida com as operações push (x) e pop (), que operam na única pilha existente. As definições de TAD neste estilo podem ser facilmente reescritas para admitir várias instâncias coexistentes do TAD, adicionando um parâmetro de instância explícita (como S no exemplo anterior) para cada operação que usa ou modifica a instância implícita.

Por outro lado, alguns TADs não podem ser definidos de forma significativa sem assumir várias instâncias. Esse é o caso quando uma única operação leva duas instâncias distintas do TAD como parâmetros. Por exemplo, considere aumentar a definição da pilha abstrata com uma operação compare(S, T) que verifica se as pilhas S e T contêm os mesmos itens na mesma ordem.

Outra forma de definir um TAD, mais próxima do espírito da programação funcional, é considerar cada estado da estrutura como uma entidade separada. Nesta visão, qualquer operação que modifique o TAD é modelada como uma função matemática que pega o antigo estado como um argumento e retorna o novo estado como parte do resultado. Ao contrário das operações imperativas, essas funções não têm efeitos colaterais. Portanto, a ordem em que são avaliados é irrelevante e a mesma operação aplicada aos mesmos argumentos (incluindo os mesmos estados de entrada) sempre retornará os mesmos resultados (e estados de saída).

Na visão funcional, em particular, não há maneira (ou necessidade) de definir uma "variável abstrata" com a semântica de variáveis ​​imperativas (ou seja, com operações de fetch e store). Em vez de armazenar valores em variáveis, eles são passados ​​como argumentos para funções.

Por exemplo, uma definição completa de estilo funcional de uma pilha abstrata pode usar as três operações:

• push: pega um estado da pilha e um valor arbitrário, retorna o estado da pilha;
• top: pega um estado da pilha, retorna um valor;
• pop: pega um estado da pilha, retorna um estado da pilha.

Em uma definição de estilo funcional, não há necessidade de uma operação de create. Na verdade, não há noção de "instância de pilha". Os estados da pilha podem ser considerados estados potenciais de uma única estrutura de pilha, e os estados de duas pilhas que contêm os mesmos valores na mesma ordem são considerados estados idênticos. Na verdade, essa visualização reflete o comportamento de algumas implementações concretas, como listas ligadas com hash cons.

Em vez de create (), uma definição de estilo funcional de uma pilha abstrata pode assumir a existência de um estado de pilha especial, a pilha vazia, designada por um símbolo especial como Λ ou "()"; ou definir uma operação bottom () que não receba argumentos e retorne este estado de pilha especial. Observe que os axiomas implicam que

• push(Λ, x) ≠ Λ.

Em uma definição de estilo funcional de uma pilha, não é necessário um predicate vazio: em vez disso, pode-se testar se uma pilha está vazia testando se ela é igual a Λ.

Observe que esses axiomas não definem o efeito de top(s) ou pop(s), a menos que s seja um estado de pilha retornado por um push. Como o push deixa a pilha não vazia, essas duas operações são indefinidas (portanto, inválidas) quando s = Λ. Por outro lado, os axiomas (e a falta de efeitos colaterais) implicam que push (s, x) = push (t, y) se e somente se x = y e s = t.

Como em alguns outros ramos da matemática, é costume assumir também que os estados da pilha são apenas aqueles cuja existência pode ser provada a partir dos axiomas em um número finito de etapas. No exemplo de pilha abstrata acima, esta regra significa que toda pilha é uma sequência finita de valores, que se torna a pilha vazia (Λ) após um número finito de pops(desempilhar). Por si só, os axiomas acima não excluem a existência de pilhas infinitas (que podem ser desempilhadas para sempre, cada vez produzindo um estado diferente) ou pilhas circulares (que retornam ao mesmo estado após um número finito de pops(desempilhar)). Em particular, eles não excluem estados s tais que pop (s) = s ou push (s, x) = s para algum x. No entanto, uma vez que não é possível obter tais estados de pilha com as operações fornecidas, eles são considerados "não existentes".

Além do comportamento em termos de axiomas, também é possível incluir, na definição de uma operação TAD, sua complexidade algorítmica. Alexander Stepanov, designer da C ++ Standard Template Library, incluiu garantias de complexidade na especificação STL, argumentando:

"A razão para introduzir a noção de tipos de dados abstratos foi permitir módulos de software intercambiáveis. Você não pode ter módulos intercambiáveis, a menos que esses módulos compartilhem um comportamento de complexidade semelhante. Se eu substituir um módulo por outro módulo com o mesmo comportamento funcional, mas com diferentes compensações de complexidade, o usuário deste código ficará desagradavelmente surpreso. Eu poderia dizer a ele o que quiser sobre abstração de dados, e ele ainda não gostaria de usar o código. Asserções de complexidade devem fazer parte da interface.” - Alexander Stepanov

A abstração fornece uma promessa de que qualquer implementação do TAD possui certas propriedades e habilidades; saber disso é tudo o que é necessário para usar um objeto TAD.

O código que usa um objeto TAD não precisará ser editado se a implementação do TAD for alterada. Uma vez que quaisquer alterações na implementação ainda devem estar em conformidade com a interface, e como o código que usa um objeto TAD pode se referir apenas a propriedades e habilidades especificadas na interface, as alterações podem ser feitas na implementação sem exigir quaisquer alterações no código onde o TAD é usado.

Implementações diferentes do TAD, tendo todas as mesmas propriedades e habilidades, são equivalentes e podem ser usadas de forma intercambiável no código que usa o TAD. Isso oferece uma grande flexibilidade ao usar objetos TAD em diferentes situações. Por exemplo, diferentes implementações do TAD podem ser mais eficientes em diferentes situações; é possível usar cada um na situação em que são preferíveis, aumentando assim a eficiência geral.

Algumas operações que são frequentemente especificadas para TADs (possivelmente com outros nomes) são

• compare(s, t), que testa se os estados de duas instâncias são equivalentes em algum sentido;
• hash(s), que calcula alguma função hash padrão do estado da instância;
• print(s) ou show(s), que produz uma representação legível do estado da instância

Nas definições de TAD no estilo imperativo, muitas vezes também se encontra

• create(), que produz uma nova instância de TAD;
• initialize(s), que prepara uma instância recém-criada para operações posteriores ou a redefine para algum "estado inicial";
• copy(s, t), que coloca a instância s em um estado equivalente ao de t;
• clone(t), que executa s ← create (), copy (s, t) e retorna s;
• free(s) ou destroy(s), que recupera a memória e outros recursos usados ​​por s.

A operação free normalmente não é relevante ou significativo, uma vez que os TADs são entidades teóricas que não "usam memória". No entanto, pode ser necessário quando se precisa analisar o armazenamento usado por um algoritmo que usa o TAD. Nesse caso, são necessários axiomas adicionais que especificam quanta memória cada instância de TAD usa, como uma função de seu estado, e quanto dela é retornado ao pool pelo free.

Alguns TADs comuns, que se mostraram úteis em uma grande variedade de aplicações, são

• Collection (Coleção)
• Container
• List (Lista)
• Set (Conjunto)
• Multiset (Conjuntos)
• Map (Vetor associativo)
• Multimap
• Graph (Grafo)
• Tree (Árvore)
• Stack (Pilha)
• Queue
• Priority queue
• Double-ended queue
• Double-ended priority queue

Cada um desses TADs pode ser definido de muitas maneiras e variantes, não necessariamente equivalentes. Por exemplo, uma pilha abstrata pode ou não ter uma operação de contagem que informa quantos itens foram empilhados e ainda não foram desempilhados. Essa escolha faz a diferença não só para seus clientes, mas também para a implementação.

Uma extensão dos TAD para computação gráfica em 1979:^[7] um tipo de dado gráfico abstrato (TAGD). Foi apresentado por Nadia Magnenat Thalmann e Daniel Thalmann. Os TAGDs fornecem as vantagens dos TADs com recursos para construir objetos gráficos de forma estruturada.

Implementar um TAD significa fornecer um procedimento ou função para cada operação abstrata. As instâncias do TAD são representadas por alguma estrutura de dados concreta que é manipulada por esses procedimentos, de acordo com as especificações do TAD.

Normalmente, existem muitas maneiras de implementar o mesmo TAD, usando várias estruturas de dados concretas diferentes. Assim, por exemplo, uma pilha abstrata pode ser implementada por uma lista encadeada ou por um array.

Para evitar que os clientes dependam da implementação, um TAD é frequentemente empacotado como um tipo de dado opaco em um ou mais módulos, cuja interface contém apenas a assinatura (número e tipos dos parâmetros e resultados) das operações. A implementação do módulo - ou seja, os corpos dos procedimentos e a estrutura de dados concreta usada - pode então ser ocultada da maioria dos clientes do módulo. Isso permite alterar a implementação sem afetar os clientes. Se a implementação for exposta, ela será conhecida como um tipo de dados transparente.

Ao implementar um TAD, cada instância (em definições de estilo imperativo) ou cada estado (em definições de estilo funcional) é geralmente representado por um identificador de algum tipo.^[8]

Linguagens orientadas a objetos modernas, como C++ e Java, suportam uma forma de tipos de dados abstratos. Quando uma classe é usada como um tipo, é um tipo abstrato que se refere a uma representação oculta. Neste modelo, um TAD é normalmente implementado como uma classe, e cada instância do TAD é geralmente um objeto dessa classe. A interface do módulo normalmente declara os construtores como procedimentos comuns e a maioria das outras operações TAD como métodos dessa classe. No entanto, essa abordagem não encapsula facilmente várias variantes representacionais encontradas em um TAD. Também pode prejudicar a extensibilidade dos programas orientados a objetos. Em um programa puramente orientado a objetos que usa interfaces como tipos, os tipos referem-se a comportamentos, não a representações.

Como exemplo, aqui está uma implementação da pilha abstrata acima na linguagem de programação C.

Uma interface do estilo imperativo pode ser:

typedef struct stack_Rep stack_Rep;         // tipo: representação da instância da pilha (registro opaco) typedef stack_Rep* stack_T;                 // tipo: identificador de uma instância da pilha (ponteiro opaco) typedef void* stack_Item;                   // tipo: valor armazenado na instância da pilha (endereço arbitrário)  stack_T stack_create(void);                             // cria uma nova instância de pilha vazia void stack_push(stack_T s, stack_Item x);               // adiciona um item no topo da pilha stack_Item stack_pop(stack_T s);                        // remove o item do topo da pilha e o retorna bool stack_empty(stack_T s);                            // verifica se a pilha está vazia 

Essa interface pode ser usada da seguinte maneira:

#include <stack.h>                  // inclui a interface de pilha  stack_T s = stack_create();         // cria uma nova instância de pilha   vazia int x = 17; stack_push(s, &x);                  // adiciona o endereço de x no topo da pilha void* y = stack_pop(s);             // remove o endereço de x da pilha e o retorna if (stack_empty(s)) { }             // faz algo se a pilha estiver vazia 

Essa interface pode ser implementada de várias maneiras. A implementação pode ser arbitrariamente ineficiente, uma vez que a definição formal do TAD, acima, não especifica quanto espaço a pilha pode ocupar, nem quanto tempo cada operação deve ocupar. Também não especifica se o estado da pilha s continua a existir após uma chamada x ← pop (s).

Na prática, a definição formal deve especificar que o espaço é proporcional ao número de itens empilhados e ainda não desempilhados; e que cada uma das operações acima deve terminar em um período de tempo constante, independentemente desse número. Para cumprir essas especificações adicionais, a implementação pode usar uma lista vinculada ou um array (com redimensionamento dinâmico) junto com dois inteiros (um contador e o tamanho do array).

As definições de TAD de estilo funcional são mais apropriadas para linguagens de programação funcional e vice-versa. No entanto, pode-se fornecer uma interface de estilo funcional, mesmo em uma linguagem imperativa como C. Por exemplo:

typedef struct stack_Rep stack_Rep;         // tipo: representação da instância da pilha (registro opaco) typedef stack_Rep* stack_T;                 // tipo: identificador de uma instância da pilha typedef void* stack_Item;                   // tipo: valor armazenado na instância da pilha (endereço arbitrário)  stack_T stack_empty(void);                      // retorna o estado da pilha vazia stack_T stack_push(stack_T s, stack_Item x);    // adiciona um item no topo do estado da pilha e retorna o estado da pilha resultante stack_T stack_pop(stack_T s);                   // remove o item superior do estado da pilha e retorna o estado da pilha resultante stack_Item stack_top(stack_T s);                // retorna o primeiro item do estado da pilha 

Muitas linguagens de programação modernas, como C ++ e Java, vêm com bibliotecas padrão que implementam vários TADs comuns, como os listados acima.

A especificação de algumas linguagens de programação é intencionalmente vaga sobre a representação de certos tipos de dados embutidos, definindo apenas as operações que podem ser feitas neles. Portanto, esses tipos podem ser vistos como "TADs integrados". Os exemplos são os arrays em muitas linguagens de script, como Awk, Lua e Perl, que podem ser considerados como uma implementação da lista abstrata.

A abstração de informações através do TAD permitiu a melhor compreensão dos algoritmos e maior facilidade de programação, e por consequência aumentou a complexidade dos programas, tornando-se fundamental em qualquer projeto de software a modelagem prévia de seus dados.

Um dos problemas que são enfrentados no TAD é que ele é uma estrutura metafórica gerada pela modelagem. Porém, em nível de implementação, não há nenhuma segurança que as operações e regras de operação desejadas para este tipo serão respeitadas.

Posteriormente, essa metodologia foi incorporada à própria linguagem de programação para um protótipo do que é hoje a orientação a objetos (OOP - Object Oriented Programming), permitindo o controle do acesso às informações de um tipo, a herança e o polimorfismo.

• Programação estruturada
• Orientação a objetos
• Engenharia de software
• Modelagem de dados
• Representação de conhecimento

• Liskov, Barbara; Zilles, Stephen (1974). "Programming with abstract data types". Proceedings of the ACM SIGPLAN Symposium on Very High Level Languages. SIGPLAN Notices. 9. pp. 50–59.
• Dale, Nell; Walker, Henry M. (1996). Abstract Data Types: Specifications, Implementations, and Applications. Jones & Bartlett Learning.