2Construindo Abstrações com Dados

Agora chegamos 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 precisar olhar para as coisas que eles representam.

—Hermann Weyl, O Caminho Matemático do Pensamento

No Capítulo 1, nos concentramos em processos computacionais e no papel dos procedimentos no design de programas. Vimos como usar dados primitivos (números) e operações primitivas (operações aritméticas), como combinar procedimentos para formar procedimentos compostos por meio de composição, condicionais e o uso de parâmetros, e como abstrair procedimentos usando define. Vimos que um procedimento pode ser visto como um padrão para a evolução local de um processo, e classificamos, raciocinamos e realizamos análises algorítmicas simples de alguns padrões comuns para processos incorporados em procedimentos. Também vimos que procedimentos de ordem superior aumentam o poder de nossa linguagem, permitindo-nos manipular e, assim, 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. Todos os procedimentos 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 muitas vezes é necessário construir objetos computacionais que tenham várias partes para modelar fenômenos do mundo real que têm vários aspectos. Assim, enquanto nosso foco no Capítulo 1 foi em construir abstrações combinando procedimentos para formar procedimentos compostos, neste capítulo nos voltamos para outro aspecto fundamental 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 procedimentos compostos: para elevar o nível conceitual em que podemos projetar nossos programas, para aumentar a modularidade de nossos designs e para aumentar o poder expressivo de nossa linguagem. Assim como a capacidade de definir procedimentos 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 dois procedimentos (um produzindo o numerador da soma e outro produzindo o denominador). Mas isso seria incômodo, porque precisaríamos explicitamente rastrear quais numeradores correspondem a quais denominadores. Em um sistema destinado a realizar muitas operações em muitos números racionais, esses detalhes de contabilidade bagunçariam substancialmente os programas, para não mencionar o que fariam com nossas mentes. Seria muito melhor se pudéssemos "colar" um numerador e um denominador para formar um par—um objeto de dados composto—que nossos programas pudessem manipular de uma maneira consistente com o tratamento de 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 em si mesmos, podemos separar a parte de nosso programa que lida com números racionais per se 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 poderosa metodologia de design 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 gostar de escrever um procedimento que aceitasse $a$, $b$, $x$ e $y$ como argumentos e retornasse o valor de $ax+by$. Isso não apresenta dificuldade se os argumentos forem números, porque podemos facilmente definir o procedimento:

(define (linear-combination a b x y)
                (+ (* a x) (* b y)))

Mas suponha que não estejamos preocupados apenas com números. Suponha que gostaríamos de expressar, em termos procedimentais, a ideia de que se pode formar combinações lineares sempre que a adição e a multiplicação são definidas—para números racionais, números complexos, polinômios ou qualquer coisa. Poderíamos expressar isso como um procedimento da forma:

(define (linear-combination a b x y)
                (add (mul a x) (mul b y)))

onde add e mul não são os procedimentos primitivos + e *, mas coisas mais complexas que realizarão as operações apropriadas para quaisquer tipos de dados que passarmos como argumentos a, b, x e y. O ponto-chave é que a única coisa que linear-combination precisa saber sobre a, b, x e y é que os procedimentos add e mul realizarão as manipulações apropriadas. Da perspectiva do procedimento linear-combination, é irrelevante o que a, b, x e y são e ainda mais irrelevante como eles podem ser representados em termos de dados mais primitivos. Esse 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á como um procedimento 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 procedimentos compostos, 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 operações especiais de "dados", apenas procedimentos. Isso desfocará ainda mais a distinção entre "procedimento" 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 fechamento—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 programas de maneiras mix-and-match. Ilustraremos algumas dessas ideias apresentando uma linguagem gráfica simples que explora o fechamento.

Em seguida, 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. Exploraremos várias alternativas para representar conjuntos de objetos. Descobriremos que, assim como uma determinada função numérica pode ser computada por muitos processos computacionais diferentes, há muitas maneiras de representar uma determinada estrutura de dados em termos de objetos mais simples, e a escolha da representação pode ter um 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, representação de conjuntos e codificação de informação.

Em seguida, abordaremos o problema de trabalhar com dados que podem ser representados de maneira 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 as que podem ser erguidas com a simples abstração de dados. Em particular, introduzimos programação dirigida por 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 para o design de sistemas, fechamos o capítulo aplicando o que aprendemos à implementação de um pacote para realizar aritmética simbólica em polinômios, nos quais os coeficientes dos polinômios podem ser inteiros, números racionais, números complexos e até mesmo outros polinômios.