2.1Introdução à Abstração de Dados

Em 1.1.8, observamos que um procedimento usado como um elemento na criação de um procedimento mais complexo poderia ser considerado não apenas como uma coleção de operações específicas, mas também como uma abstração procedural. Ou seja, os detalhes de como o procedimento foi implementado poderiam ser suprimidos, e o próprio procedimento poderia ser substituído por qualquer outro procedimento com o mesmo comportamento geral. Em outras palavras, poderíamos fazer uma abstração que separaria a maneira como o procedimento seria usado dos detalhes de como o procedimento seria implementado em termos de procedimentos mais primitivos. A noção análoga para dados compostos é chamada de abstração de dados. A abstração de dados é uma metodologia que nos permite isolar como um objeto de dados composto é usado dos detalhes de como ele é construído a partir de objetos de dados mais primitivos.

A ideia básica da abstração de dados é estruturar os programas que usam objetos de dados compostos para que operem em "dados abstratos". Ou seja, nossos programas devem usar dados de forma a não fazer suposições sobre os dados que não sejam estritamente necessárias para realizar a tarefa em questão. Ao mesmo tempo, uma representação de dados "concreta" é definida independentemente dos programas que usam os dados. A interface entre essas duas partes do nosso sistema será um conjunto de procedimentos, chamados seletores e construtores, que implementam os dados abstratos em termos da representação concreta. Para ilustrar essa técnica, consideraremos como projetar um conjunto de procedimentos para manipular números racionais.

2.1.1Exemplo: Operações Aritméticas para Números Racionais

Suponha que queremos fazer aritmética com números racionais. Queremos ser capazes de somar, subtrair, multiplicar e dividir eles e testar se dois números racionais são iguais.

Vamos começar assumindo que já temos uma maneira de construir um número racional a partir de um numerador e um denominador. Também assumimos que, dado um número racional, temos uma maneira de extrair (ou selecionar) seu numerador e seu denominador. Vamos ainda assumir que o construtor e os seletores estão disponíveis como procedimentos:

• (make-rat ⟨n⟩ ⟨d⟩) retorna o número racional cujo numerador é o inteiro ⟨n⟩ e cujo denominador é o inteiro ⟨d⟩.
• (numer ⟨x⟩) retorna o numerador do número racional ⟨x⟩.
• (denom ⟨x⟩) retorna o denominador do número racional ⟨x⟩.

Estamos usando aqui uma poderosa estratégia de síntese: pensamento desejoso. Ainda não dissemos como um número racional é representado, ou como os procedimentos numer, denom e make-rat devem ser implementados. Mesmo assim, se tivéssemos esses três procedimentos, poderíamos então somar, subtrair, multiplicar, dividir e testar a igualdade usando as seguintes relações:

Podemos expressar essas regras como procedimentos:

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

Agora temos as operações sobre números racionais definidas em termos dos procedimentos seletor e construtor numer, denom e make-rat. Mas ainda não definimos esses procedimentos. O que precisamos é de alguma maneira de unir um numerador e um denominador para formar um número racional.

Pares

Para nos permitir implementar o nível concreto de nossa abstração de dados, nossa linguagem fornece uma estrutura composta chamada par, que pode ser construída com o procedimento primitivo cons. Este procedimento recebe dois argumentos e retorna um objeto de dados composto que contém os dois argumentos como partes. Dado um par, podemos extrair as partes usando os procedimentos primitivos car e cdr.⁶⁸ Assim, podemos usar cons, car e cdr da seguinte forma:

(define x (cons 1 2))

(car x)
1

(cdr x)
2

Observe que um par é um objeto de dados que pode ser nomeado e manipulado, assim como um objeto de dados primitivo. Além disso, cons pode ser usado para formar pares cujos elementos são pares, e assim por diante:

(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))

(car (car z))
1

(car (cdr z))
3

Em 2.2 veremos como essa capacidade de combinar pares significa que pares podem ser usados como blocos de construção de propósito geral para criar todos os tipos de estruturas de dados complexas. O único primitivo de dados compostos par, implementado pelos procedimentos cons, car e cdr, é a única cola que precisamos. Objetos de dados construídos a partir de pares são chamados de dados estruturados em listas.

Representando números racionais

Pares oferecem uma maneira natural de completar o sistema de números racionais. Simplesmente representamos um número racional como um par de dois inteiros: um numerador e um denominador. Então make-rat, numer e denom são facilmente implementados da seguinte forma:⁶⁹

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

Além disso, para exibir os resultados de nossas computações, podemos imprimir números racionais imprimindo o numerador, uma barra e o denominador:⁷⁰

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

Agora podemos testar nossos procedimentos de números racionais:

(define one-half (make-rat 1 2))
(print-rat one-half)
1/2

(define one-third (make-rat 1 3))
(print-rat
 (add-rat one-half one-third))
5/6

(print-rat
 (mul-rat one-half one-third))
1/6

(print-rat
 (add-rat one-third one-third))
6/9

Como o exemplo final mostra, nossa implementação de números racionais não reduz números racionais aos termos mais baixos. Podemos remediar isso mudando make-rat. Se tivermos um procedimento gcd como o de 1.2.5 que produz o maior divisor comum de dois inteiros, podemos usar gcd para reduzir o numerador e o denominador aos termos mais baixos antes de construir o par:

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) 
          (/ d g))))

Agora temos

(print-rat 
 (add-rat one-third one-third))
2/3

como desejado. Essa modificação foi realizada mudando o construtor make-rat sem alterar nenhum dos procedimentos (como add-rat e mul-rat) que implementam as operações reais.

Exercício 2.1: Defina uma versão melhor de make-rat que lida com argumentos positivos e negativos. Make-rat deve normalizar o sinal de forma que, se o número racional for positivo, tanto o numerador quanto o denominador sejam positivos, e se o número racional for negativo, apenas o numerador seja negativo.

2.1.2Barreiras de Abstração

Antes de continuar com mais exemplos de dados compostos e abstração de dados, vamos considerar algumas das questões levantadas pelo exemplo dos números racionais. Definimos as operações de números racionais em termos de um construtor make-rat e seletores numer e denom. Em geral, a ideia subjacente da abstração de dados é identificar para cada tipo de objeto de dados um conjunto básico de operações em termos das quais todas as manipulações de objetos de dados desse tipo serão expressas, e então usar apenas essas operações na manipulação dos dados.

Podemos visualizar a estrutura do sistema de números racionais como mostrado na Figura 2.1. As linhas horizontais representam barreiras de abstração que isolam diferentes "níveis" do sistema. Em cada nível, a barreira separa os programas (acima) que usam a abstração de dados dos programas (abaixo) que implementam a abstração de dados. Programas que usam números racionais os manipulam apenas em termos dos procedimentos fornecidos "para uso público" pelo pacote de números racionais: add-rat, sub-rat, mul-rat, div-rat e equal-rat?. Estes, por sua vez, são implementados apenas em termos do construtor e dos seletores make-rat, numer e denom, que por sua vez são implementados em termos de pares. Os detalhes de como os pares são implementados são irrelevantes para o restante do pacote de números racionais, desde que os pares possam ser manipulados pelo uso de cons, car e cdr. Na prática, os procedimentos em cada nível são as interfaces que definem as barreiras de abstração e conectam os diferentes níveis.

Essa ideia simples tem muitas vantagens. Uma vantagem é que torna os programas muito mais fáceis de manter e modificar. Qualquer estrutura de dados complexa pode ser representada de várias maneiras com as estruturas de dados primitivas fornecidas por uma linguagem de programação. É claro que a escolha da representação influencia os programas que operam nela; assim, se a representação fosse alterada em algum momento posterior, todos esses programas poderiam ter que ser modificados de acordo. Essa tarefa poderia ser demorada e cara no caso de programas grandes, a menos que a dependência da representação fosse confinada por design a muito poucos módulos de programa.

Por exemplo, uma maneira alternativa de abordar o problema de reduzir números racionais aos termos mais baixos é realizar a redução sempre que acessamos as partes de um número racional, em vez de quando o construímos. Isso leva a diferentes procedimentos construtores e seletores:

(define (make-rat n d)
  (cons n d))

(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))

(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))

A diferença entre essa implementação e a anterior está em quando calculamos o gcd. Se, em nosso uso típico de números racionais, acessarmos os numeradores e denominadores dos mesmos números racionais muitas vezes, seria preferível calcular o gcd quando os números racionais são construídos. Caso contrário, pode ser melhor esperar até o momento do acesso para calcular o gcd. Em qualquer caso, quando mudamos de uma representação para a outra, os procedimentos add-rat, sub-rat e assim por diante não precisam ser modificados.

Restringir a dependência da representação a alguns poucos procedimentos de interface nos ajuda a projetar programas, bem como a modificá-los, porque nos permite manter a flexibilidade de considerar implementações alternativas. Para continuar com nosso exemplo simples, suponha que estamos projetando um pacote de números racionais e não podemos decidir inicialmente se devemos realizar o gcd no momento da construção ou no momento da seleção. A metodologia de abstração de dados nos dá uma maneira de adiar essa decisão sem perder a capacidade de progredir no restante do sistema.

Exercício 2.2: Considere o problema de representar segmentos de linha em um plano. Cada segmento é representado como um par de pontos: um ponto inicial e um ponto final. Defina um construtor make-segment e seletores start-segment e end-segment que definem a representação de segmentos em termos de pontos. Além disso, um ponto pode ser representado como um par de números: a coordenada $x$ e a coordenada $y$. Assim, especifique um construtor make-point e seletores x-point e y-point que definem essa representação. Finalmente, usando seus seletores e construtores, defina um procedimento midpoint-segment que recebe um segmento de linha como argumento e retorna seu ponto médio (o ponto cujas coordenadas são a média das coordenadas dos pontos finais). Para testar seus procedimentos, você precisará de uma maneira de imprimir pontos:

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

Exercício 2.3: Implemente uma representação para retângulos em um plano. (Dica: Você pode querer fazer uso do Exercício 2.2.) Em termos de seus construtores e seletores, crie procedimentos que calculem o perímetro e a área de um retângulo dado. Agora implemente uma representação diferente para retângulos. Você pode projetar seu sistema com barreiras de abstração adequadas, de modo que os mesmos procedimentos de perímetro e área funcionem usando qualquer representação?

2.1.3O Que Se Entende por Dados?

Começamos a implementação de números racionais em 2.1.1 implementando as operações de números racionais add-rat, sub-rat e assim por diante em termos de três procedimentos não especificados: 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 era especificado por esses três procedimentos.

Mas o que exatamente se entende por dados? Não basta dizer "o que quer que seja implementado pelos seletores e construtores dados". Claramente, nem todo conjunto arbitrário de três procedimentos pode servir como 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 nulo d, se x for (make-rat n d), então $$\frac{\text{(numer x)}}{\text{(denom x)}}=\frac{\text{n}}{\text{d}}.$$ Na verdade, essa é a única condição que make-rat, numer e denom devem cumprir para formar uma base adequada para uma representação de números racionais. Em geral, podemos pensar em dados como definidos por alguma coleção de seletores e construtores, juntamente com condições especificadas que esses procedimentos devem cumprir para ser uma representação válida.⁷¹

Esse 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 par, que usamos para definir nossos números racionais. Nunca dissemos o que era um par, apenas que a linguagem fornecia procedimentos cons, car e cdr para operar em pares. Mas a única coisa que precisamos saber sobre essas três operações é que, se colarmos dois objetos usando cons, podemos recuperar os objetos usando car e cdr. Ou seja, as operações satisfazem a condição de que, para quaisquer objetos x e y, se z for (cons x y), então (car z) é x e (cdr z) é y. De fato, mencionamos que esses três procedimentos são incluídos como primitivos em nossa linguagem. No entanto, qualquer tripla de procedimentos que satisfaça a condição acima pode ser usada como base para implementar pares. Esse ponto é ilustrado de forma impressionante pelo fato de que poderíamos implementar cons, car e cdr sem usar nenhuma estrutura de dados, mas apenas usando procedimentos. Aqui estão as definições:

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else 
           (error "Argument not 0 or 1:
                   CONS" m))))
  dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))

Esse uso de procedimentos não corresponde a nada parecido com nossa noção intuitiva do que dados deveriam ser. No entanto, tudo o que precisamos fazer para mostrar que essa é uma maneira válida de representar pares é verificar que esses procedimentos satisfazem a condição dada acima.

O ponto sutil a ser notado é que o valor retornado por (cons x y) é um procedimento — ou seja, o procedimento internamente definido dispatch, que recebe um argumento e retorna x ou y dependendo de se o argumento é 0 ou 1. Correspondentemente, (car z) é definido para aplicar z a 0. Portanto, se z for o procedimento formado por (cons x y), então z aplicado a 0 retornará x. Assim, mostramos que (car (cons x y)) retorna x, como desejado. Da mesma forma, (cdr (cons x y)) aplica o procedimento retornado por (cons x y) a 1, que retorna y. Portanto, essa implementação procedural de pares é uma implementação válida, e se acessarmos pares usando apenas cons, car e cdr, não podemos distinguir essa implementação de uma que usa estruturas de dados "reais".

O ponto de exibir a representação procedural de pares não é que nossa linguagem funcione dessa maneira (Scheme, e sistemas Lisp em geral, implementam pares diretamente, por razões de eficiência), mas que poderia funcionar dessa maneira. A representação procedural, embora obscura, é uma maneira perfeitamente adequada de representar pares, já que cumpre as únicas condições que os pares precisam cumprir. Esse exemplo também demonstra que a capacidade de manipular procedimentos como objetos automaticamente fornece a capacidade de representar dados compostos. Isso pode parecer uma curiosidade agora, mas as representações procedurais de dados desempenharão um papel central em nosso repertório de programação. Esse estilo de programação é frequentemente chamado de 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 procedural alternativa de pares. Para essa representação, verifique que (car (cons x y)) retorna x para quaisquer objetos x e y.

(define (cons x y) 
  (lambda (m) (m x y)))

(define (car z) 
  (z (lambda (p q) p)))

Qual é a definição correspondente de cdr? (Dica: Para verificar que isso funciona, use o modelo de substituição de 1.1.5.)

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 dos procedimentos cons, car e cdr.

Exercício 2.6: No caso de representar pares como procedimentos não ser suficientemente surpreendente, considere que, em uma linguagem que pode manipular procedimentos, podemos nos virar sem números (pelo menos no que diz respeito a inteiros não negativos) implementando 0 e a operação de adicionar 1 como

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

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

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 do procedimento de adição + (não em termos de aplicação repetida de add-1).

2.1.4Exercício Estendido: Aritmética de Intervalos

Alyssa P. Hacker está projetando um sistema para ajudar as pessoas a resolver problemas de engenharia. Uma das funcionalidades que ela deseja fornecer em seu sistema é a capacidade de manipular quantidades inexatas (como parâmetros medidos de dispositivos físicos) com precisão conhecida, de modo que, quando os cálculos são feitos com essas quantidades aproximadas, os resultados sejam números de precisão conhecida.

Engenheiros elétricos estarão usando o sistema de Alyssa para calcular quantidades elétricas. Às vezes, é necessário para eles calcular o valor de uma resistência equivalente em paralelo $R_p$ de dois resistores $R_1$ e $R_2$ usando a fórmula $$R_p=\frac{1}{1/R_1+1/R_2}.$$ Os valores de resistência geralmente são conhecidos apenas até alguma tolerância garantida pelo fabricante do resistor. Por exemplo, se você comprar um resistor rotulado como "6,8 ohms com 10% de tolerância", você só pode ter certeza de que o resistor tem uma resistência entre 6,8 $-<!--\; -\; -->$ 0,68 = 6,12 e 6,8 + 0,68 = 7,48 ohms. Assim, se você tiver um resistor de 6,8 ohms com 10% de tolerância em paralelo com um resistor de 4,7 ohms com 5% de tolerância, a resistência da combinação pode variar de cerca de 2,58 ohms (se os dois resistores estiverem nos limites inferiores) a cerca de 2,97 ohms (se os dois resistores estiverem nos limites superiores).

A ideia de Alyssa é implementar "aritmética de intervalos" como um conjunto de operações aritméticas para combinar "intervalos" (objetos que representam a faixa de valores possíveis de uma quantidade inexata). O resultado de somar, subtrair, multiplicar ou dividir dois intervalos é ele mesmo um intervalo, representando a faixa do resultado.

Alyssa postula a existência de um objeto abstrato chamado "intervalo" que tem dois pontos finais: um limite inferior e um limite superior. Ela também presume que, dados os pontos finais de um intervalo, ela pode construir o intervalo usando o construtor de dados make-interval. Alyssa primeiro escreve um procedimento para somar dois intervalos. Ela raciocina que o valor mínimo que a soma poderia ser é a soma dos dois limites inferiores e o valor máximo que poderia ser é a soma dos dois limites superiores:

(define (add-interval x y)
  (make-interval (+ (lower-bound x) 
                    (lower-bound y))
                 (+ (upper-bound x) 
                    (upper-bound y))))

Alyssa também trabalha no produto de dois intervalos encontrando o mínimo e o máximo dos produtos dos limites e usando-os como os limites do intervalo resultante. (Min e max são primitivas que encontram o mínimo ou o máximo de qualquer número de argumentos.)

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) 
               (lower-bound y)))
        (p2 (* (lower-bound x) 
               (upper-bound y)))
        (p3 (* (upper-bound x) 
               (lower-bound y)))
        (p4 (* (upper-bound x) 
               (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

Para dividir dois intervalos, Alyssa multiplica o primeiro pelo inverso do segundo. Observe que os limites do intervalo inverso são o inverso do limite superior e o inverso do limite inferior, nessa ordem.

(define (div-interval x y)
  (mul-interval x 
                (make-interval 
                 (/ 1.0 (upper-bound y)) 
                 (/ 1.0 (lower-bound y)))))

Exercício 2.7: O programa de Alyssa está incompleto porque ela não especificou a implementação da abstração de intervalo. Aqui está uma definição do construtor de intervalo:

(define (make-interval a b) (cons a b))

Defina seletores upper-bound e lower-bound para completar a implementação.

Exercício 2.8: Usando raciocínio análogo ao de Alyssa, descreva como a diferença de dois intervalos pode ser calculada. Defina um procedimento de subtração correspondente, chamado sub-interval.

Exercício 2.9: A largura de um intervalo é metade da diferença entre seus limites superior e inferior. A largura é uma medida da incerteza do número especificado pelo intervalo. Para algumas operações aritméticas, a largura do resultado da combinação de dois intervalos é uma função apenas das larguras dos intervalos de argumento, enquanto para outras a largura da combinação não é uma função das larguras dos intervalos de argumento. Mostre que a largura da soma (ou diferença) de dois intervalos é uma função apenas das larguras dos intervalos sendo somados (ou subtraídos). Dê exemplos para mostrar que isso não é verdade para multiplicação ou divisão.

Exercício 2.10: Ben Bitdiddle, um programador de sistemas especialista, olha por cima do ombro de Alyssa e comenta que não está claro o que significa dividir por um intervalo que abrange zero. Modifique o código de Alyssa para verificar essa condição e sinalizar um erro se ela ocorrer.

Exercício 2.11: De passagem, Ben também comenta de forma críptica: "Ao testar os sinais dos pontos finais dos intervalos, é possível dividir mul-interval em nove casos, apenas um dos quais requer mais de duas multiplicações." Reescreva esse procedimento usando a sugestão de Ben.

Depois de depurar seu programa, Alyssa o mostra a um usuário potencial, que reclama que seu programa resolve o problema errado. Ele quer um programa que possa lidar com números representados como um valor central e uma tolerância aditiva; por exemplo, ele quer trabalhar com intervalos como 3,5 $\pm <!--\; \pm \; -->$ 0,15 em vez de [3,35, 3,65]. Alyssa volta para sua mesa e corrige esse problema fornecendo um construtor alternativo e seletores alternativos:

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))

(define (center i)
  (/ (+ (lower-bound i) 
        (upper-bound i)) 
     2))

(define (width i)
  (/ (- (upper-bound i) 
        (lower-bound i)) 
     2))

Infelizmente, a maioria dos usuários de Alyssa são engenheiros. Situações reais de engenharia geralmente envolvem medições com apenas uma pequena incerteza, medida como a razão entre a largura do intervalo e o ponto médio do intervalo. Engenheiros geralmente especificam tolerâncias percentuais nos parâmetros de dispositivos, como nas especificações de resistores dadas anteriormente.

Exercício 2.12: Defina um construtor make-center-percent que recebe um centro e uma tolerância percentual e produz o intervalo desejado. Você também deve definir um seletor percent que produz a tolerância percentual para um intervalo dado. O seletor center é o mesmo mostrado acima.

Exercício 2.13: Mostre que, sob a suposição de pequenas tolerâncias percentuais, há uma fórmula simples para a tolerância percentual aproximada do produto de dois intervalos em termos das tolerâncias dos fatores. Você pode simplificar o problema assumindo que todos os números são positivos.

Após um trabalho considerável, Alyssa P. Hacker entrega seu sistema finalizado. Vários anos depois, depois que ela esqueceu tudo sobre isso, ela recebe uma ligação frenética de um usuário irritado, Lem E. Tweakit. Parece que Lem notou que a fórmula para resistores em paralelo pode ser escrita de duas maneiras algebricamente equivalentes: $$\frac{R_1{R}_2}{R_1+R_2}$$ e $$\frac{1}{1/R_1+1/R_2}.$$ Ele escreveu os dois programas a seguir, cada um dos quais calcula a fórmula de resistores em paralelo de maneira diferente:

(define (par1 r1 r2)
  (div-interval 
   (mul-interval r1 r2)
   (add-interval r1 r2)))

(define (par2 r1 r2)
  (let ((one (make-interval 1 1)))
    (div-interval 
     one
     (add-interval 
      (div-interval one r1) 
      (div-interval one r2)))))

Lem reclama que o programa de Alyssa dá respostas diferentes para as duas maneiras de calcular. Essa é uma reclamação séria.

Exercício 2.14: Demonstre que Lem está certo. Investigue o comportamento do sistema em uma variedade de expressões aritméticas. Crie alguns intervalos $A$ e $B$, e use-os para calcular as expressões $A/A$ e $A/B$. Você obterá mais insights usando intervalos cuja largura é uma pequena porcentagem do valor central. Examine os resultados da computação na forma de centro e porcentagem (veja Exercício 2.12).

Exercício 2.15: Eva Lu Ator, outra usuária, também notou os diferentes intervalos computados por expressões algebricamente equivalentes. Ela diz que uma fórmula para computar com intervalos usando o sistema de Alyssa produzirá limites de erro mais apertados se puder ser escrita de forma que nenhuma variável que represente um número incerto seja repetida. Assim, ela diz, par2 é um programa "melhor" para resistências em paralelo do que par1. Ela está certa? Por quê?

Exercício 2.16: Explique, em geral, por que expressões algébricas equivalentes podem levar a respostas diferentes. Você pode criar um pacote de aritmética de intervalos que não tenha essa deficiência, ou essa tarefa é impossível? (Aviso: Este problema é muito difícil.)

(define make-rat cons)
(define numer car)
(define denom cdr)