2.1.3 O Que Se Entende por Dados?

Começamos a implementação de números racionais na seção 2.1.1 implementando as operações de números racionais add_rat, sub_rat e assim por diante em termos de três funções não especificadas: make_rat, numer e denom. Naquele ponto, poderíamos pensar nas operações como sendo definidas em termos de objetos de dados—numeradores, denominadores e números racionais—cujo comportamento foi especificado pelas três funções posteriores.

Mas o que exatamente se entende por dados? Não é suficiente dizer "o que quer que seja implementado pelos seletores e construtores dados". Claramente, nem todo conjunto arbitrário de três funções pode servir como uma base apropriada para a implementação de números racionais. Precisamos garantir que, se construirmos um número racional x a partir de um par de inteiros n e d, então extrair o numer e o denom de x e dividi-los deve produzir o mesmo resultado que dividir n por d. Em outras palavras, make_rat, numer e denom devem satisfazer a condição de que, para qualquer inteiro n e qualquer inteiro não-zero d, se x é make_rat(n, d), então

$$\dfrac{\texttt{numer}(\texttt{x})}{\texttt{denom}(\texttt{x})} = \dfrac{\texttt{n}}{\texttt{d}}$$

Na verdade, esta é a única condição que make_rat, numer e denom devem cumprir para formar uma base adequada para uma representação de número racional. Em geral, podemos pensar em dados como definidos por alguma coleção de seletores e construtores, juntamente com condições especificadas que essas funções devem cumprir para serem uma representação válida.

Este ponto de vista pode servir para definir não apenas objetos de dados de "alto nível", como números racionais, mas também objetos de nível mais baixo. Considere a noção de um par, que usamos para definir nossos números racionais. Nunca dissemos realmente o que era um par, apenas que a linguagem fornecia funções pair, head e tail para operar em pares. Mas a única coisa que precisamos saber sobre essas três operações é que, se colarmos dois objetos juntos usando pair, podemos recuperar os objetos usando head e tail. Ou seja, as operações satisfazem a condição de que, para quaisquer objetos x e y, se z é pair(x, y), então head(z) é x e tail(z) é y. De fato, mencionamos que essas três funções estão incluídas como primitivas em nossa linguagem. No entanto, qualquer trio de funções que satisfaça a condição acima pode ser usado como base para implementar pares. Este ponto é ilustrado de forma marcante pelo fato de que poderíamos implementar pair, head e tail sem usar nenhuma estrutura de dados, mas apenas usando funções. Aqui estão as definições:

Carregando playground de código...

Este uso de funções corresponde a nada parecido com nossa noção intuitiva do que os dados deveriam ser. No entanto, tudo o que precisamos fazer para mostrar que esta é uma maneira válida de representar pares é verificar que essas funções satisfazem a condição dada acima.

O ponto sutil a notar é que o valor retornado por pair(x, y) é uma função—a saber, a função dispatch definida internamente, que recebe um argumento e retorna x ou y dependendo se o argumento é 0 ou 1. Correspondentemente, head(z) é definido para aplicar z a 0. Portanto, se z é a função formada por pair(x, y), então z aplicado a 0 produzirá x. Assim, mostramos que head(pair(x, y)) produz x, como desejado. Similarmente, tail(pair(x, y)) aplica a função retornada por pair(x, y) a 1, que retorna y. Portanto, esta implementação funcional de pares é uma implementação válida, e se acessarmos pares usando apenas pair, head e tail, não podemos distinguir esta implementação de uma que usa estruturas de dados "reais".

O ponto de exibir a representação funcional de pares não é que nossa linguagem funcione dessa maneira (uma implementação eficiente de pares pode usar a estrutura de dados nativa vector do JavaScript), mas que ela poderia funcionar dessa maneira. A representação funcional, embora obscura, é uma maneira perfeitamente adequada de representar pares, pois cumpre as únicas condições que os pares precisam cumprir. Este exemplo também demonstra que a capacidade de manipular funções como objetos fornece automaticamente a capacidade de representar dados compostos. Isso pode parecer uma curiosidade agora, mas as representações funcionais de dados desempenharão um papel central em nosso repertório de programação. Este estilo de programação é frequentemente chamado de message passing (passagem de mensagens), e o usaremos como uma ferramenta básica no capítulo 3 quando abordarmos as questões de modelagem e simulação.

Exercício 2.4

Aqui está uma representação funcional alternativa de pares. Para esta representação, verifique que head(pair(x, y)) produz x para quaisquer objetos x e y.

Carregando playground de código...

Qual é a definição correspondente de tail? (Dica: Para verificar que isso funciona, faça uso do modelo de substituição da seção 1.1.5.)

Carregando playground de código...

Exercício 2.5

Mostre que podemos representar pares de inteiros não-negativos usando apenas números e operações aritméticas se representarmos o par a e b como o inteiro que é o produto 2^a 3^b. Dê as definições correspondentes das funções pair, head e tail.

Carregando playground de código...

Exercício 2.6

Caso representar pares como funções (exercício 2.4) não tenha sido suficientemente alucinante, considere que, em uma linguagem que pode manipular funções, podemos nos virar sem números (pelo menos no que diz respeito aos inteiros não-negativos) implementando 0 e a operação de adicionar 1 como:

Carregando playground de código...

Esta representação é conhecida como numerais de Church, em homenagem ao seu inventor, Alonzo Church, o lógico que inventou o cálculo lambda.

Defina one e two diretamente (não em termos de zero e add_1). (Dica: Use substituição para avaliar add_1(zero)). Dê uma definição direta da função de adição plus (não em termos de aplicação repetida de add_1).

Carregando playground de código...

📝 Encontrou algo errado nesta página?

Sua ajuda é muito importante para melhorar a qualidade da tradução!

🐛 Encontrou um erro?

Se você encontrou:

• Erro de tradução (palavra incorreta, termo técnico errado)
• Erro de ortografia ou gramática
• Link quebrado
• Código de exemplo que não funciona
• Problema de formatação

Reporte um bug →

❓ Tem uma dúvida?

Se você tem:

• Dúvida sobre o conteúdo desta seção
• Pergunta sobre um conceito do SICP
• Dificuldade em entender algum exemplo
• Questão sobre a tradução de algum termo

Inicie uma discussão →

💡 Tem uma sugestão de melhoria?

Se você quer sugerir:

• Melhoria na explicação
• Exemplo adicional
• Recurso visual (diagrama, ilustração)
• Qualquer outra ideia

Sugira uma melhoria →

🌍 Quer discutir a tradução?

Se você quer debater:

• Escolha de tradução de algum termo
• Consistência de terminologia
• Nuances do português

Discussão de tradução →

Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨