Tipos de Dados Abstratos e a Crise do Software

Nota: Isto faz parte da série “Composing Software” (agora um livro!) sobre a aprendizagem de programação funcional e técnicas de software composicional em JavaScriptES6+ a partir do zero. Fique atento. Há muito mais disto por vir!
Compre o Livro | Índice | < Anterior | Próximo >

Não confundir com:

Tipos de Dados Algébricos (por vezes abreviados ADT ou AlgDT). Tipos de dados algébricos referem-se a tipos complexos em linguagens de programação (por exemplo, Rust, Haskell, F#) que mostram algumas propriedades de estruturas algébricas específicas. por exemplo, tipos de soma e tipos de produto.

Estruturas algébricas. Estruturas algébricas são estudadas e aplicadas a partir de álgebra abstrata, que, como as ADTs, também são comumente especificadas em termos de descrições algébricas de axiomas, mas aplicáveis muito fora do mundo dos computadores e códigos. Uma estrutura algébrica pode existir que é impossível de ser modelada em software completamente. Por contraste, os Tipos de Dados Abstratos servem como uma especificação e guia para verificar formalmente o software de trabalho.

Um Tipo de Dados Abstratos (ADT) é um conceito abstrato definido por axiomas que representam alguns dados e operações sobre esses dados. Os ADTs não são definidos em termos de instâncias concretas e não especificam os tipos de dados concretos, estruturas ou algoritmos utilizados nas implementações. Em vez disso, os ADTs definem tipos de dados somente em termos de suas operações, e os axiomas aos quais essas operações devem aderir.

Exemplos comuns de ADTs

• Lista
• Stack
• Queue
• Set
• Map
• Stream

ADTs podem representar qualquer conjunto de operações sobre qualquer tipo de dados. Em outras palavras, a lista exaustiva de todos os ADTs possíveis é infinita pela mesma razão que a lista exaustiva de todas as frases possíveis em inglês é infinita. Os ADTs são o conceito abstrato de um conjunto de operações sobre dados não especificados, e não um conjunto específico de tipos de dados concretos. Um conceito errado comum é que os exemplos específicos de ADTs ensinados em muitos cursos universitários e manuais de estrutura de dados são o que os ADTs são. Muitos desses textos rotulam as estruturas de dados “ADTs” e depois saltam o ADT e descrevem as estruturas de dados em termos concretos, sem nunca expor o estudante a uma representação abstrata real do tipo de dados. Oops!

ADTs podem expressar muitas estruturas algébricas úteis, incluindo semigrupos, monoides, funtores, mônadas, etc. A Especificação Fantasyland é um catálogo útil de estruturas algébricas descritas por ADTs para encorajar implementações interoperáveis em JavaScript. Os construtores de bibliotecas podem verificar suas implementações usando os axiomas fornecidos.

Por que os ADTs?

Tipos de dados abstratos são úteis porque fornecem uma forma de definirmos formalmente módulos reutilizáveis de uma forma que seja matematicamente sólida, precisa e sem ambigüidade. Isso nos permite compartilhar uma linguagem comum para nos referirmos a um extenso vocabulário de blocos de construção de software úteis: Idéias que são úteis para aprender e levar conosco enquanto nos movemos entre domínios, frameworks e até mesmo linguagens de programação.

História dos ADTs

Nos anos 60 e início dos anos 70, muitos programadores e pesquisadores de informática estavam interessados na crise do software. Como Edsger Dijkstra colocou em sua palestra de premiação Turing:

“A principal causa da crise do software é que as máquinas se tornaram várias ordens de magnitude mais poderosas! Dito de uma forma bem direta: enquanto não houvesse máquinas, a programação não era problema algum; quando tínhamos alguns computadores fracos, a programação tornou-se um problema leve, e agora temos computadores gigantescos, a programação tornou-se um problema igualmente gigantesco.”

O problema a que ele se refere é que o software é muito complicado. Uma versão impressa do módulo lunar Apollo e do sistema de orientação para a NASA é sobre a altura de um gabinete de arquivamento. Isso é um monte de código. Imagine tentar ler e entender cada linha disso.

Software Moderno são ordens de magnitude mais complicadas. O Facebook tinha cerca de 62 milhões de linhas de código em 2015. Se você imprimisse 50 linhas por página, você preencheria 1,24 milhões de páginas. Se você empilhar essas páginas, você teria cerca de 1.800 páginas por pé, ou 688 pés. Isso é mais alto que a Torre Millenium de São Francisco, o prédio residencial mais alto de São Francisco na época em que foi escrito.

Gerenciar a complexidade do software é um dos principais desafios enfrentados por praticamente todos os desenvolvedores de software. Nos anos 60 e 70, eles não tinham os idiomas, padrões ou ferramentas que tomamos como garantidos hoje. Coisas como linters, intellisense e até mesmo ferramentas de análise estática ainda não foram inventadas.

Muitos engenheiros de software notaram que o hardware que construíram sobre a maioria das coisas funcionou. Mas o software, na maioria das vezes, era complexo, confuso e frágil. O software era comumente:

• Over orçamento
• Late
• Buggy
• Requisitos falhos
• Dificuldade de manutenção

Se apenas você pudesse pensar em software em peças modulares, você não precisaria entender o sistema inteiro para entender como fazer parte do sistema funcionar. Esse princípio de design de software é conhecido como localidade. Para obter a localidade, você precisa de módulos que você possa entender isoladamente do resto do sistema. Você deve ser capaz de descrever um módulo sem ambigüidade, sem especificar em demasia sua implementação. Esse é o problema que os ADTs resolvem.

Extendendo-se dos anos 60 quase até os dias atuais, avançar o estado da modularidade do software era uma preocupação central. Foi com esses problemas em mente que pessoas como Barbara Liskov (a mesma Liskov referenciada no Princípio de Substituição Liskov dos princípios de design SOLID OO), Alan Kay, Bertrand Meyer e outras lendas da ciência da computação trabalharam na descrição e especificação de várias ferramentas para permitir software modular, incluindo ADTs, programação orientada a objetos e design por contrato, respectivamente.

ADTs surgiram do trabalho de Liskov e seus alunos sobre a linguagem de programação CLU entre 1974 e 1975. Eles contribuíram significativamente para o estado da arte da especificação de módulos de software – a linguagem que usamos para descrever as interfaces que permitem a interação dos módulos de software. A conformidade formal da interface nos aproxima significativamente da modularidade e interoperabilidade do software.

Liskov recebeu o prêmio Turing por seu trabalho sobre abstração de dados, tolerância a falhas e computação distribuída em 2008. Os ADTs desempenharam um papel significativo nessa realização, e hoje, praticamente todos os cursos universitários de informática incluem ADTs no currículo.

A crise do software nunca foi totalmente resolvida, e muitos dos problemas descritos acima devem ser familiares a qualquer desenvolvedor profissional, mas aprender como usar ferramentas como objetos, módulos e ADTs certamente ajuda.

Especificações para ADTs

Critérios transversais podem ser usados para julgar a adequação de uma especificação ADT. Eu chamo estes critérios de FAMED, mas eu só inventei a mnemônica. Os critérios originais foram publicados por Liskov e Zilles em seu famoso artigo de 1975, “Specification Techniques for Data Abstractions”,

• Formal. As especificações devem ser formais. O significado de cada elemento da especificação deve ser definido com detalhes suficientes para que o público-alvo tenha uma chance razoavelmente boa de construir uma implementação compatível a partir da especificação. Deve ser possível implementar uma prova algébrica em código para cada axioma da especificação.
• Aplicável. As ADTs devem ser amplamente aplicáveis. Um ADT deve ser geralmente reutilizável para muitos casos diferentes de uso de concreto. Um ADT que descreve uma implementação particular em uma determinada linguagem em uma determinada parte do código é provavelmente sobre-especificação de coisas. Ao invés disso, os ADTs são mais adequados para descrever o comportamento de estruturas de dados comuns, componentes de biblioteca, módulos, características de linguagem de programação, etc. Por exemplo, um ADT descrevendo operações de pilha, ou um ADT descrevendo o comportamento de uma promessa.
• Minimal. As especificações do ADT devem ser mínimas. A especificação deve incluir as partes interessantes e amplamente aplicáveis do comportamento e nada mais. Cada comportamento deve ser descrito com precisão e sem ambiguidade, mas com o mínimo detalhe específico ou concreto possível. A maioria das especificações ADT devem ser prováveis usando um punhado de axiomas.
• Extensível. Os ADTs devem ser extensíveis. Uma pequena mudança em um requerimento deve levar a apenas uma pequena mudança na especificação.
• Declarativo. As especificações declarativas descrevem o quê, não como. ADTs devem ser descritos em termos do que são as coisas, e mapeamentos de relações entre entradas e saídas, não os passos para criar estruturas de dados ou os passos específicos que cada operação deve realizar.

Um bom ADT deve incluir:

• Descrição legível para humanos. Os ADTs podem ser bastante concisos se não forem acompanhados de alguma descrição legível por humanos. A descrição da linguagem natural, combinada com as definições algébricas, pode funcionar como um controle um do outro para esclarecer qualquer erro na especificação ou ambiguidade no entendimento do leitor.
• Definições. Definir claramente qualquer termo usado na especificação para evitar qualquer ambiguidade.
• Assinaturas abstratas. Descreva as entradas e saídas esperadas sem ligá-las a tipos concretos ou estruturas de dados.
• Axiomas. Algebraic definitions of the axiom invariants used to prove that an implementation has satisfied the requirements of the specification.

Stack ADT Example

A stack is a Last In, First Out (LIFO) pile of items which allows users to interact with the stack by pushing a new item to the top of the stack, or popping the most recently pushed item from the top of the stack.

Stacks are commonly used in parsing, sorting, and data collation algorithms.

Definitions

• a: Any type
• b: Any type
• item: Any type
• stack(): an empty stack
• stack(a): a stack of a
• : a pair of item and stack

Abstract Signatures

The stack operation takes any number of items and returns a stack of those items. Typically, the abstract signature for a constructor is defined in terms of itself. Please don’t confuse this with a recursive function.

• stack(...items) => stack(...items)

Stack Operations (operations which return a stack)

• push(item, stack()) => stack(item)
• pop(stack) =>

Axioms

The stack axioms deal primarily with stack and item identity, the sequence of the stack items, and the behavior of pop when the stack is empty.

Identity

Pushing and popping have no side-effects. If you push to a stack and immediately pop from the same stack, the stack should be in the state it was before you pushed.

pop(push(a, stack())) = 

• Given: push a to the stack and immediately pop from the stack
• Should: return a pair of a and stack().

Sequence

Popping from the stack should respect the sequence: Last In, First Out (LIFO).

pop(push(b, push(a, stack())) = 

• Given: push a to the stack, then push b to the stack, then pop from the stack
• Should: return a pair of b and stack(a).

Empty

Popping from an empty stack results in an undefined item value. In concrete terms, this could be defined with a Maybe(item), Nothing, or Either. In JavaScript, it’s customary to use undefined. Popping from an empty stack should not change the stack.

pop(stack()) = 

• Given: pop from an empty stack
• Should: return a pair of undefined and stack().

Concrete Implementations

An abstract data type could have many concrete implementations, in different languages, libraries, frameworks, etc. Here is one implementation of the above stack ADT, using an encapsulated object, and pure functions over that object:

const stack = (...items) => ({
push: item => stack(...items, item),
pop: () => {
// create a item list
const newItems = ; // remove the last item from the list and
// assign it to a variable
const = newItems.splice(-1); // return the pair
return ;
},
// So we can compare stacks in our assert function
toString: () => `stack(${ items.join(',') })`
});const push = (item, stack) => stack.push(item);
const pop = stack => stack.pop();

And another that implements the stack operations in terms of pure functions over JavaScript’s existing Array type:

const stack = (...elements) => ;const push = (a, stack) => stack.concat();const pop = stack => {
const newStack = stack.slice(0);
const item = newStack.pop();
return ;
};

Both versions satisfy the following axiom proofs:

// A simple assert function which will display the results
// of the axiom tests, or throw a descriptive error if an
// implementation fails to satisfy an axiom.
const assert = ({given, should, actual, expected}) => {
const stringify = value => Array.isArray(value) ?
`` :
`${ value }`;
const actualString = stringify(actual);
const expectedString = stringify(expected);
if (actualString === expectedString) {
console.log(`OK:
given: ${ given }
should: ${ should }
actual: ${ actualString }
expected: ${ expectedString }
`);
} else {
throw new Error(`NOT OK:
given ${ given }
should ${ should }
actual: ${ actualString }
expected: ${ expectedString }
`);
}
};// Concrete values to pass to the functions:
const a = 'a';
const b = 'b';// Proofs
assert({
given: 'push `a` to the stack and immediately pop from the stack',
should: 'return a pair of `a` and `stack()`',
actual: pop(push(a, stack())),
expected: 
})assert({
given: 'push `a` to the stack, then push `b` to the stack, then pop from the stack',
should: 'return a pair of `b` and `stack(a)`.',
actual: pop(push(b, push(a, stack()))),
expected: 
});assert({
given: 'pop from an empty stack',
should: 'return a pair of undefined, stack()',
actual: pop(stack()),
expected: 
});

Conclusion

• An Abstract Data Type (ADT) is an abstract concept defined by axioms which represent some data and operations on that data.
• Tipos de Dados Abstratos são focados no quê, não como (eles são enquadrados declarativamente, e não especificam algoritmos ou estruturas de dados).
• Exemplos comuns incluem listas, pilhas, conjuntos, etc.
• ADTs fornecem uma forma de definirmos formalmente módulos reutilizáveis de uma forma que seja matematicamente sólida, precisa e inequívoca.
• ADTs surgiram do trabalho de Liskov e estudantes na linguagem de programação da CLU nos anos 70.
• ADTs devem ser FAMED. Os ADTs devem incluir uma descrição legível humana, definições, assinaturas abstratas e axiomas formalmente verificáveis.

Bonus tip: Se você não tem certeza se deve ou não encapsular uma função, pergunte-se se você a incluiria em um ADT para o seu componente. Lembre-se, os ADTs devem ser mínimos, portanto, se não for essencial, não tiver coesão com as outras operações, ou se a sua especificação for susceptível de mudar, encapsule-a.

Glossary

• Axiomas são afirmações matematicamente sólidas que devem manter-se verdadeiras.
• Matematicamente sólido significa que cada termo é bem definido matematicamente para que seja possível escrever afirmações de facto inequívocas e prováveis baseadas nelas.

Passos seguintes

EricElliottJS.com apresenta muitas horas de aulas em vídeo e exercícios interactivos sobre tópicos como este. Se você gostou deste conteúdo, por favor considere juntar-se a.