2 Construindo Abstrações com Dados

Chegamos agora ao passo decisivo da abstração matemática: esquecemos o que os símbolos representam. [...] [O matemático] não precisa ficar ocioso; há muitas operações que ele pode realizar com esses símbolos, sem nunca ter que olhar para as coisas que eles representam. — Hermann Weyl, The Mathematical Way of Thinking

Nos concentramos no capítulo 1 em processos computacionais e no papel das funções no design de programas. Vimos como usar dados primitivos (números) e operações primitivas (operações aritméticas), como combinar funções para formar funções compostas através de composição, condicionais e o uso de parâmetros, e como abstrair processos usando declarações de funções. Vimos que uma função pode ser considerada como um padrão para a evolução local de um processo, e classificamos, raciocinamos sobre e realizamos análises algorítmicas simples de alguns padrões comuns para processos incorporados em funções. Também vimos que funções de ordem superior aumentam o poder de nossa linguagem ao nos permitir manipular e, portanto, raciocinar em termos de métodos gerais de computação. Isso é muito da essência da programação.

Neste capítulo, vamos olhar para dados mais complexos. Todas as funções do capítulo 1 operam em dados numéricos simples, e dados simples não são suficientes para muitos dos problemas que desejamos abordar usando computação. Programas são tipicamente projetados para modelar fenômenos complexos, e mais frequentemente do que não, deve-se construir objetos computacionais que têm várias partes para modelar fenômenos do mundo real que têm vários aspectos. Assim, enquanto nosso foco no capítulo 1 estava em construir abstrações combinando funções para formar funções compostas, voltamos neste capítulo para outro aspecto chave de qualquer linguagem de programação: os meios que ela fornece para construir abstrações combinando objetos de dados para formar dados compostos.

Por que queremos dados compostos em uma linguagem de programação? Pelas mesmas razões que queremos funções compostas: para elevar o nível conceitual no qual podemos projetar nossos programas, para aumentar a modularidade de nossos designs e para melhorar o poder expressivo de nossa linguagem. Assim como a capacidade de declarar funções nos permite lidar com processos em um nível conceitual mais alto do que o das operações primitivas da linguagem, a capacidade de construir objetos de dados compostos nos permite lidar com dados em um nível conceitual mais alto do que o dos objetos de dados primitivos da linguagem.

Considere a tarefa de projetar um sistema para realizar aritmética com números racionais. Poderíamos imaginar uma operação add_rat que recebe dois números racionais e produz sua soma. Em termos de dados simples, um número racional pode ser pensado como dois inteiros: um numerador e um denominador. Assim, poderíamos projetar um programa no qual cada número racional seria representado por dois inteiros (um numerador e um denominador) e onde add_rat seria implementado por duas funções (uma produzindo o numerador da soma e uma produzindo o denominador). Mas isso seria desajeitado, porque então precisaríamos explicitamente manter o controle de quais numeradores correspondiam a quais denominadores. Em um sistema destinado a realizar muitas operações em muitos números racionais, tais detalhes de contabilidade sobrecarregariam os programas substancialmente, sem mencionar o que fariam com nossas mentes. Seria muito melhor se pudéssemos "colar juntos" um numerador e denominador para formar um par—um objeto de dados composto—que nossos programas pudessem manipular de uma maneira que seria consistente com considerar um número racional como uma única unidade conceitual.

O uso de dados compostos também nos permite aumentar a modularidade de nossos programas. Se pudermos manipular números racionais diretamente como objetos por si mesmos, então podemos separar a parte de nosso programa que lida com números racionais em si dos detalhes de como os números racionais podem ser representados como pares de inteiros. A técnica geral de isolar as partes de um programa que lidam com como os objetos de dados são representados das partes de um programa que lidam com como os objetos de dados são usados é uma metodologia de design poderosa chamada abstração de dados. Veremos como a abstração de dados torna os programas muito mais fáceis de projetar, manter e modificar.

O uso de dados compostos leva a um aumento real no poder expressivo de nossa linguagem de programação. Considere a ideia de formar uma "combinação linear" ax+by. Poderíamos querer escrever uma função que aceitaria a, b, x e y como argumentos e retornaria o valor de ax+by. Isso não apresenta nenhuma dificuldade se os argumentos devem ser números, porque podemos facilmente declarar a função

function linear_combination(a, b, x, y) {
    return a * x + b * y;
}

Mas suponha que não estamos preocupados apenas com números. Suponha que gostaríamos de descrever um processo que forma combinações lineares sempre que adição e multiplicação são definidas—para números racionais, números complexos, polinômios ou o que quer que seja. Poderíamos expressar isso como uma função da forma

function linear_combination(a, b, x, y) {
    return add(mul(a, x), mul(b, y));
}

onde add e mul não são as funções primitivas + e *, mas sim coisas mais complexas que executarão as operações apropriadas para quaisquer tipos de dados que passarmos como os argumentos a, b, x e y. O ponto chave é que a única coisa que linear_combination deveria precisar saber sobre a, b, x e y é que as funções add e mul realizarão as manipulações apropriadas. Da perspectiva da função linear_combination, é irrelevante o que a, b, x e y são e ainda mais irrelevante como eles podem estar representados em termos de dados mais primitivos. Este mesmo exemplo mostra por que é importante que nossa linguagem de programação forneça a capacidade de manipular objetos compostos diretamente: Sem isso, não há maneira de uma função como linear_combination passar seus argumentos para add e mul sem ter que conhecer sua estrutura detalhada.

Começamos este capítulo implementando o sistema de aritmética de números racionais mencionado acima. Isso formará o pano de fundo para nossa discussão sobre dados compostos e abstração de dados. Assim como com funções compostas, a principal questão a ser abordada é a da abstração como uma técnica para lidar com a complexidade, e veremos como a abstração de dados nos permite erguer barreiras de abstração adequadas entre diferentes partes de um programa.

Veremos que a chave para formar dados compostos é que uma linguagem de programação deve fornecer algum tipo de "cola" para que objetos de dados possam ser combinados para formar objetos de dados mais complexos. Há muitos tipos possíveis de cola. De fato, descobriremos como formar dados compostos sem usar nenhuma operação especial de "dados", apenas funções. Isso desfocará ainda mais a distinção entre "função" e "dados", que já estava se tornando tênue no final do capítulo 1. Também exploraremos algumas técnicas convencionais para representar sequências e árvores. Uma ideia chave ao lidar com dados compostos é a noção de closure—que a cola que usamos para combinar objetos de dados deve nos permitir combinar não apenas objetos de dados primitivos, mas também objetos de dados compostos. Outra ideia chave é que objetos de dados compostos podem servir como interfaces convencionais para combinar módulos de programa de maneiras mix-and-match. Ilustramos algumas dessas ideias apresentando uma linguagem gráfica simples que explora closure.

Então aumentaremos o poder representacional de nossa linguagem introduzindo expressões simbólicas—dados cujas partes elementares podem ser símbolos arbitrários em vez de apenas números. Exploramos várias alternativas para representar conjuntos de objetos. Descobriremos que, assim como uma dada função numérica pode ser computada por muitos processos computacionais diferentes, há muitas maneiras pelas quais uma dada estrutura de dados pode ser representada em termos de objetos mais simples, e a escolha da representação pode ter impacto significativo nos requisitos de tempo e espaço dos processos que manipulam os dados. Investigaremos essas ideias no contexto de diferenciação simbólica, a representação de conjuntos e a codificação de informações.

Em seguida, abordaremos o problema de trabalhar com dados que podem ser representados de forma diferente por diferentes partes de um programa. Isso leva à necessidade de implementar operações genéricas, que devem lidar com muitos tipos diferentes de dados. Manter a modularidade na presença de operações genéricas requer barreiras de abstração mais poderosas do que podem ser erguidas com simples abstração de dados sozinha. Em particular, introduzimos a programação orientada a dados como uma técnica que permite que representações de dados individuais sejam projetadas isoladamente e depois combinadas aditivamente (ou seja, sem modificação). Para ilustrar o poder dessa abordagem de design de sistema, fechamos o capítulo aplicando o que aprendemos à implementação de um pacote para realizar aritmética simbólica em polinômios, no qual os coeficientes dos polinômios podem ser inteiros, números racionais, números complexos e até outros polinômios.