2.5Sistemas com Operações Genéricas

Na seção anterior, vimos como projetar sistemas nos quais objetos de dados podem ser representados de mais de uma maneira. A ideia chave é vincular o código que especifica as operações de dados às várias representações por meio de procedimentos de interface genérica. Agora veremos como usar essa mesma ideia não apenas para definir operações que são genéricas sobre diferentes representações, mas também para definir operações que são genéricas sobre diferentes tipos de argumentos. Já vimos vários pacotes diferentes de operações aritméticas: a aritmética primitiva (+, -, *, /) embutida em nossa linguagem, a aritmética de números racionais (add-rat, sub-rat, mul-rat, div-rat) de 2.1.1, e a aritmética de números complexos que implementamos em 2.4.3. Agora usaremos técnicas dirigidas por dados para construir um pacote de operações aritméticas que incorpora todos os pacotes aritméticos que já construímos.

Figura 2.23 mostra a estrutura do sistema que construiremos. Observe as barreiras de abstração. Da perspectiva de alguém que usa "números", há um único procedimento add que opera sobre quaisquer números fornecidos. Add faz parte de uma interface genérica que permite que os pacotes separados de aritmética ordinária, aritmética racional e aritmética complexa sejam acessados uniformemente por programas que usam números. Qualquer pacote aritmético individual (como o pacote complexo) pode ser acessado por meio de procedimentos genéricos (como add-complex) que combinam pacotes projetados para diferentes representações (como retangular e polar). Além disso, a estrutura do sistema é aditiva, de modo que se pode projetar os pacotes aritméticos individuais separadamente e combiná-los para produzir um sistema aritmético genérico.

2.5.1Operações Aritméticas Genéricas

A tarefa de projetar operações aritméticas genéricas é análoga à de projetar as operações genéricas de números complexos. Gostaríamos, por exemplo, de ter um procedimento de adição genérico add que age como a adição primitiva ordinária + sobre números ordinários, como add-rat sobre números racionais e como add-complex sobre números complexos. Podemos implementar add e as outras operações aritméticas genéricas seguindo a mesma estratégia que usamos em 2.4.3 para implementar os seletores genéricos para números complexos. Anexaremos uma etiqueta de tipo a cada tipo de número e faremos com que o procedimento genérico despache para um pacote apropriado de acordo com o tipo de dados de seus argumentos.

Os procedimentos aritméticos genéricos são definidos da seguinte forma:

(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))

Começamos instalando um pacote para lidar com números ordinários, ou seja, os números primitivos de nossa linguagem. Vamos marcar esses números com o símbolo scheme-number. As operações aritméticas neste pacote são os procedimentos aritméticos primitivos (portanto, não há necessidade de definir procedimentos extras para lidar com os números não marcados). Como essas operações recebem dois argumentos, elas são instaladas na tabela com a chave (scheme-number scheme-number):

(define (install-scheme-number-package)
  (define (tag x)
    (attach-tag 'scheme-number x))
  (put 'add '(scheme-number scheme-number)
       (lambda (x y) (tag (+ x y))))
  (put 'sub '(scheme-number scheme-number)
       (lambda (x y) (tag (- x y))))
  (put 'mul '(scheme-number scheme-number)
       (lambda (x y) (tag (* x y))))
  (put 'div '(scheme-number scheme-number)
       (lambda (x y) (tag (/ x y))))
  (put 'make 'scheme-number
       (lambda (x) (tag x)))
  'done)

Os usuários do pacote Scheme-number criarão números ordinários (marcados) por meio do procedimento:

(define (make-scheme-number n)
  ((get 'make 'scheme-number) n))

Agora que a estrutura do sistema aritmético genérico está em vigor, podemos facilmente incluir novos tipos de números. Aqui está um pacote que realiza aritmética racional. Observe que, como benefício da aditividade, podemos usar sem modificação o código de números racionais de 2.1.1 como os procedimentos internos do pacote:

(define (install-rational-package)
  ;; procedimentos internos
  (define (numer x) (car x))
  (define (denom x) (cdr x))
  (define (make-rat n d)
    (let ((g (gcd n d)))
      (cons (/ n g) (/ d g))))
  (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))))
  ;; interface para o resto do sistema
  (define (tag x) (attach-tag 'rational x))
  (put 'add '(rational rational)
       (lambda (x y) (tag (add-rat x y))))
  (put 'sub '(rational rational)
       (lambda (x y) (tag (sub-rat x y))))
  (put 'mul '(rational rational)
       (lambda (x y) (tag (mul-rat x y))))
  (put 'div '(rational rational)
       (lambda (x y) (tag (div-rat x y))))
  (put 'make 'rational
       (lambda (n d) (tag (make-rat n d))))
  'done)

(define (make-rational n d)
  ((get 'make 'rational) n d))

Podemos instalar um pacote semelhante para lidar com números complexos, usando a etiqueta complex. Ao criar o pacote, extraímos da tabela as operações make-from-real-imag e make-from-mag-ang que foram definidas pelos pacotes retangular e polar. A aditividade nos permite usar, como operações internas, os mesmos procedimentos add-complex, sub-complex, mul-complex e div-complex de 2.4.1.

(define (install-complex-package)
  ;; procedimentos importados dos pacotes retangular e polar
  (define (make-from-real-imag x y)
    ((get 'make-from-real-imag 
          'rectangular) 
     x y))
  (define (make-from-mag-ang r a)
    ((get 'make-from-mag-ang 'polar) 
     r a))
  ;; procedimentos internos
  (define (add-complex z1 z2)
    (make-from-real-imag 
     (+ (real-part z1) (real-part z2))
     (+ (imag-part z1) (imag-part z2))))
  (define (sub-complex z1 z2)
    (make-from-real-imag 
     (- (real-part z1) (real-part z2))
     (- (imag-part z1) (imag-part z2))))
  (define (mul-complex z1 z2)
    (make-from-mag-ang 
     (* (magnitude z1) (magnitude z2))
     (+ (angle z1) (angle z2))))
  (define (div-complex z1 z2)
    (make-from-mag-ang 
     (/ (magnitude z1) (magnitude z2))
     (- (angle z1) (angle z2))))
  ;; interface para o resto do sistema
  (define (tag z) (attach-tag 'complex z))
  (put 'add '(complex complex)
       (lambda (z1 z2) 
         (tag (add-complex z1 z2))))
  (put 'sub '(complex complex)
       (lambda (z1 z2) 
         (tag (sub-complex z1 z2))))
  (put 'mul '(complex complex)
       (lambda (z1 z2) 
         (tag (mul-complex z1 z2))))
  (put 'div '(complex complex)
       (lambda (z1 z2) 
         (tag (div-complex z1 z2))))
  (put 'make-from-real-imag 'complex
       (lambda (x y) 
         (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'complex
       (lambda (r a) 
         (tag (make-from-mag-ang r a))))
  'done)

Programas fora do pacote de números complexos podem construir números complexos a partir de partes reais e imaginárias ou de magnitudes e ângulos. Observe como os procedimentos subjacentes, originalmente definidos nos pacotes retangular e polar, são exportados para o pacote complexo e exportados de lá para o mundo exterior.

(define (make-complex-from-real-imag x y)
  ((get 'make-from-real-imag 'complex) x y))
(define (make-complex-from-mag-ang r a)
  ((get 'make-from-mag-ang 'complex) r a))

O que temos aqui é um sistema de etiquetas de dois níveis. Um número complexo típico, como $3+4i$ na forma retangular, seria representado como mostrado na Figura 2.24. A etiqueta externa (complex) é usada para direcionar o número para o pacote complexo. Uma vez dentro do pacote complexo, a próxima etiqueta (rectangular) é usada para direcionar o número para o pacote retangular. Em um sistema grande e complicado, pode haver muitos níveis, cada um interfaciado com o próximo por meio de operações genéricas. À medida que um objeto de dados é passado "para baixo", a etiqueta externa que é usada para direcioná-lo para o pacote apropriado é removida (aplicando contents) e o próximo nível de etiqueta (se houver) se torna visível para ser usado para despacho adicional.

Nos pacotes acima, usamos add-rat, add-complex e os outros procedimentos aritméticos exatamente como foram originalmente escritos. Uma vez que essas definições são internas a diferentes procedimentos de instalação, no entanto, elas não precisam mais de nomes distintos entre si: poderíamos simplesmente nomeá-los add, sub, mul e div em ambos os pacotes.

Exercício 2.77: Louis Reasoner tenta avaliar a expressão (magnitude z) onde z é o objeto mostrado na Figura 2.24. Para sua surpresa, em vez da resposta 5, ele recebe uma mensagem de erro de apply-generic, dizendo que não há método para a operação magnitude nos tipos (complex). Ele mostra essa interação para Alyssa P. Hacker, que diz: "O problema é que os seletores de números complexos nunca foram definidos para números complex, apenas para números polar e rectangular. Tudo o que você precisa fazer para fazer isso funcionar é adicionar o seguinte ao pacote complex:"

(put 'real-part '(complex) real-part)
(put 'imag-part '(complex) imag-part)
(put 'magnitude '(complex) magnitude)
(put 'angle '(complex) angle)

Descreva em detalhes por que isso funciona. Como exemplo, trace todos os procedimentos chamados na avaliação da expressão (magnitude z) onde z é o objeto mostrado na Figura 2.24. Em particular, quantas vezes apply-generic é invocado? Qual procedimento é despachado em cada caso?

Exercício 2.78: Os procedimentos internos no pacote scheme-number são essencialmente nada mais do que chamadas para os procedimentos primitivos +, -, etc. Não foi possível usar os primitivos da linguagem diretamente porque nosso sistema de etiquetas de tipo exige que cada objeto de dados tenha um tipo anexado a ele. Na verdade, no entanto, todas as implementações de Lisp têm um sistema de tipos, que usam internamente. Predicados primitivos como symbol? e number? determinam se objetos de dados têm tipos particulares. Modifique as definições de type-tag, contents e attach-tag de 2.4.2 para que nosso sistema genérico aproveite o sistema de tipos interno do Scheme. Ou seja, o sistema deve funcionar como antes, exceto que números ordinários devem ser representados simplesmente como números do Scheme, em vez de como pares cujo car é o símbolo scheme-number.

Exercício 2.79: Defina um predicado de igualdade genérico equ? que testa a igualdade de dois números e instale-o no pacote aritmético genérico. Esta operação deve funcionar para números ordinários, números racionais e números complexos.

Exercício 2.80: Defina um predicado genérico =zero? que testa se seu argumento é zero e instale-o no pacote aritmético genérico. Esta operação deve funcionar para números ordinários, números racionais e números complexos.

2.5.2Combinando Dados de Diferentes Tipos

Vimos como definir um sistema aritmético unificado que abrange números ordinários, números complexos, números racionais e qualquer outro tipo de número que possamos decidir inventar, mas ignoramos uma questão importante. As operações que definimos até agora tratam os diferentes tipos de dados como sendo completamente independentes. Assim, há pacotes separados para adicionar, digamos, dois números ordinários ou dois números complexos. O que ainda não consideramos é o fato de que é significativo definir operações que cruzam os limites de tipo, como a adição de um número complexo a um número ordinário. Fizemos grandes esforços para introduzir barreiras entre partes de nossos programas para que possam ser desenvolvidas e entendidas separadamente. Gostaríamos de introduzir as operações entre tipos de forma cuidadosamente controlada, de modo que possamos suportá-las sem violar seriamente nossos limites de módulo.

Uma maneira de lidar com operações entre tipos é projetar um procedimento diferente para cada combinação possível de tipos para os quais a operação é válida. Por exemplo, poderíamos estender o pacote de números complexos para que ele forneça um procedimento para adicionar números complexos a números ordinários e instalar isso na tabela usando a etiqueta (complex scheme-number):¹¹⁵

(define (add-complex-to-schemenum z x)
  (make-from-real-imag (+ (real-part z) x)
                       (imag-part z)))

(put 'add 
     '(complex scheme-number)
     (lambda (z x) 
       (tag (add-complex-to-schemenum z x))))

Esta técnica funciona, mas é incômoda. Com tal sistema, o custo de introduzir um novo tipo não é apenas a construção do pacote de procedimentos para esse tipo, mas também a construção e instalação dos procedimentos que implementam as operações entre tipos. Isso pode facilmente ser muito mais código do que o necessário para definir as operações no próprio tipo. O método também mina nossa capacidade de combinar pacotes separados de forma aditiva, ou pelo menos de limitar a extensão em que os implementadores dos pacotes individuais precisam levar em conta outros pacotes. Por exemplo, no exemplo acima, parece razoável que a responsabilidade de lidar com operações mistas em números complexos e números ordinários seja do pacote de números complexos. Combinar números racionais e números complexos, no entanto, pode ser feito pelo pacote complexo, pelo pacote racional ou por algum terceiro pacote que use operações extraídas desses dois pacotes. Formular políticas coerentes sobre a divisão de responsabilidade entre pacotes pode ser uma tarefa esmagadora ao projetar sistemas com muitos pacotes e muitas operações entre tipos.

Coerção

Na situação geral de operações completamente não relacionadas agindo sobre tipos completamente não relacionados, implementar operações explícitas entre tipos, embora incômodo, é o melhor que se pode esperar. Felizmente, geralmente podemos fazer melhor aproveitando estruturas adicionais que podem estar latentes em nosso sistema de tipos. Muitas vezes, os diferentes tipos de dados não são completamente independentes, e pode haver maneiras pelas quais objetos de um tipo podem ser vistos como sendo de outro tipo. Esse processo é chamado de coerção. Por exemplo, se nos pedirem para combinar aritmeticamente um número ordinário com um número complexo, podemos ver o número ordinário como um número complexo cuja parte imaginária é zero. Isso transforma o problema em combinar dois números complexos, que pode ser tratado da maneira usual pelo pacote de aritmética complexa.

Em geral, podemos implementar essa ideia projetando procedimentos de coerção que transformam um objeto de um tipo em um objeto equivalente de outro tipo. Aqui está um procedimento de coerção típico, que transforma um número ordinário dado em um número complexo com essa parte real e parte imaginária zero:

(define (scheme-number->complex n)
  (make-complex-from-real-imag 
   (contents n) 0))

Instalamos esses procedimentos de coerção em uma tabela de coerção especial, indexada sob os nomes dos dois tipos:

(put-coercion 'scheme-number 'complex 
              scheme-number->complex)

(Assumimos que há procedimentos put-coercion e get-coercion disponíveis para manipular essa tabela.) Geralmente, alguns dos slots na tabela estarão vazios, porque não é geralmente possível coagir um objeto de dados arbitrário de cada tipo para todos os outros tipos. Por exemplo, não há como coagir um número complexo arbitrário para um número ordinário, então não haverá um procedimento geral complex->scheme-number incluído na tabela.

Uma vez que a tabela de coerção foi configurada, podemos lidar com a coerção de forma uniforme modificando o procedimento apply-generic de 2.4.3. Quando solicitado a aplicar uma operação, primeiro verificamos se a operação é definida para os tipos dos argumentos, como antes. Se for, despachamos para o procedimento encontrado na tabela de operação e tipo. Caso contrário, tentamos a coerção. Para simplificar, consideramos apenas o caso em que há dois argumentos.¹¹⁶ Verificamos a tabela de coerção para ver se objetos do primeiro tipo podem ser coagidos para o segundo tipo. Se puderem, coagimos o primeiro argumento e tentamos a operação novamente. Se objetos do primeiro tipo não puderem ser coagidos para o segundo tipo, tentamos a coerção ao contrário para ver se há uma maneira de coagir o segundo argumento para o tipo do primeiro argumento. Finalmente, se não houver uma maneira conhecida de coagir nenhum dos tipos para o outro, desistimos. Aqui está o procedimento:

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (if (= (length args) 2)
              (let ((type1 (car type-tags))
                    (type2 (cadr type-tags))
                    (a1 (car args))
                    (a2 (cadr args)))
                (let ((t1->t2 
                       (get-coercion type1
                                     type2))
                      (t2->t1 
                       (get-coercion type2 
                                     type1)))
                  (cond (t1->t2
                         (apply-generic 
                          op (t1->t2 a1) a2))
                        (t2->t1
                         (apply-generic 
                          op a1 (t2->t1 a2)))
                        (else
                         (error 
                          "No method for 
                           these types"
                          (list 
                           op 
                           type-tags))))))
              (error 
               "No method for these types"
               (list op type-tags)))))))

Este esquema de coerção tem muitas vantagens sobre o método de definir operações explícitas entre tipos, como descrito acima. Embora ainda precisemos escrever procedimentos de coerção para relacionar os tipos (possivelmente $n^2$ procedimentos para um sistema com $n$ tipos), precisamos escrever apenas um procedimento para cada par de tipos, em vez de um procedimento diferente para cada coleção de tipos e cada operação genérica.¹¹⁷ O que estamos contando aqui é o fato de que a transformação apropriada entre tipos depende apenas dos tipos em si, não da operação a ser aplicada.

Por outro lado, pode haver aplicações para as quais nosso esquema de coerção não seja suficientemente geral. Mesmo quando nenhum dos objetos a serem combinados pode ser convertido para o tipo do outro, ainda pode ser possível realizar a operação convertendo ambos os objetos para um terceiro tipo. Para lidar com essa complexidade e ainda preservar a modularidade em nossos programas, geralmente é necessário construir sistemas que aproveitem estruturas ainda mais complexas nas relações entre tipos, como discutiremos a seguir.

Hierarquias de tipos

O esquema de coerção apresentado acima dependia da existência de relações naturais entre pares de tipos. Muitas vezes, há uma estrutura mais "global" em como os diferentes tipos se relacionam entre si. Por exemplo, suponha que estamos construindo um sistema aritmético genérico para lidar com inteiros, números racionais, números reais e números complexos. Em tal sistema, é bastante natural considerar um inteiro como um tipo especial de número racional, que por sua vez é um tipo especial de número real, que por sua vez é um tipo especial de número complexo. O que realmente temos é uma chamada hierarquia de tipos, na qual, por exemplo, inteiros são um subtipo de números racionais (ou seja, qualquer operação que pode ser aplicada a um número racional pode automaticamente ser aplicada a um inteiro). Inversamente, dizemos que números racionais formam um supertipo de inteiros. A hierarquia particular que temos aqui é de um tipo muito simples, na qual cada tipo tem no máximo um supertipo e no máximo um subtipo. Tal estrutura, chamada de torre, é ilustrada na Figura 2.25.

Se tivermos uma estrutura de torre, podemos simplificar muito o problema de adicionar um novo tipo à hierarquia, pois precisamos apenas especificar como o novo tipo é incorporado ao próximo supertipo acima dele e como ele é o supertipo do tipo abaixo dele. Por exemplo, se quisermos adicionar um inteiro a um número complexo, não precisamos definir explicitamente um procedimento de coerção integer->complex. Em vez disso, definimos como um inteiro pode ser transformado em um número racional, como um número racional é transformado em um número real e como um número real é transformado em um número complexo. Em seguida, permitimos que o sistema transforme o inteiro em um número complexo por meio dessas etapas e, em seguida, adicione os dois números complexos.

Podemos redesenhar nosso procedimento apply-generic da seguinte maneira: Para cada tipo, precisamos fornecer um procedimento raise, que "eleva" objetos desse tipo um nível na torre. Então, quando o sistema é solicitado a operar sobre objetos de diferentes tipos, ele pode elevar sucessivamente os tipos inferiores até que todos os objetos estejam no mesmo nível na torre. (Exercício 2.83 e Exercício 2.84 tratam dos detalhes de implementar tal estratégia.)

Outra vantagem de uma torre é que podemos facilmente implementar a noção de que todo tipo "herda" todas as operações definidas em um supertipo. Por exemplo, se não fornecemos um procedimento especial para encontrar a parte real de um inteiro, devemos esperar que real-part seja definido para inteiros em virtude do fato de que inteiros são um subtipo de números complexos. Em uma torre, podemos organizar isso de forma uniforme modificando apply-generic. Se a operação necessária não for diretamente definida para o tipo do objeto fornecido, elevamos o objeto para seu supertipo e tentamos novamente. Assim, rastejamos pela torre, transformando nosso argumento à medida que avançamos, até encontrarmos um nível no qual a operação desejada pode ser realizada ou atingirmos o topo (caso em que desistimos).

Outra vantagem de uma torre sobre uma hierarquia mais geral é que ela nos dá uma maneira simples de "rebaixar" um objeto de dados para a representação mais simples. Por exemplo, se adicionarmos $2+3i$ a $4-<!--\; -\; -->3i$, seria bom obter a resposta como o inteiro 6 em vez de como o número complexo $6+0i$. Exercício 2.85 discute uma maneira de implementar tal operação de rebaixamento. (O truque é que precisamos de uma maneira geral de distinguir aqueles objetos que podem ser rebaixados, como $6+0i$, daqueles que não podem, como $6+2i$.)

Inadequações das hierarquias

Se os tipos de dados em nosso sistema puderem ser naturalmente organizados em uma torre, isso simplifica muito os problemas de lidar com operações genéricas em diferentes tipos, como vimos. Infelizmente, isso geralmente não é o caso. Figura 2.26 ilustra um arranjo mais complexo de tipos mistos, mostrando relações entre diferentes tipos de figuras geométricas. Vemos que, em geral, um tipo pode ter mais de um subtipo. Triângulos e quadriláteros, por exemplo, são ambos subtipos de polígonos. Além disso, um tipo pode ter mais de um supertipo. Por exemplo, um triângulo retângulo isósceles pode ser considerado tanto como um triângulo isósceles quanto como um triângulo retângulo. Essa questão de múltiplos supertipos é particularmente espinhosa, pois significa que não há uma maneira única de "elevar" um tipo na hierarquia. Encontrar o supertipo "correto" no qual aplicar uma operação a um objeto pode envolver uma busca considerável por toda a rede de tipos por parte de um procedimento como apply-generic. Como geralmente há múltiplos subtipos para um tipo, há um problema semelhante em coagir um valor "para baixo" na hierarquia de tipos. Lidar com grandes números de tipos inter-relacionados enquanto ainda preserva a modularidade no design de grandes sistemas é muito difícil e é uma área de muita pesquisa atual.¹¹⁸

Exercício 2.81: Louis Reasoner notou que apply-generic pode tentar coagir os argumentos para os tipos um do outro, mesmo que eles já tenham o mesmo tipo. Portanto, ele raciocina, precisamos colocar procedimentos na tabela de coerção para coagir argumentos de cada tipo para seu próprio tipo. Por exemplo, além da coerção scheme-number->complex mostrada acima, ele faria:

(define (scheme-number->scheme-number n) n)
(define (complex->complex z) z)

(put-coercion 'scheme-number 'scheme-number
              scheme-number->scheme-number)

(put-coercion 'complex 'complex 
              complex->complex)

1. Com os procedimentos de coerção de Louis instalados, o que acontece se apply-generic for chamado com dois argumentos do tipo scheme-number ou dois argumentos do tipo complex para uma operação que não é encontrada na tabela para esses tipos? Por exemplo, suponha que definimos uma operação genérica de exponenciação:

   (define (exp x y) 
     (apply-generic 'exp x y))

   e colocamos um procedimento para exponenciação no pacote Scheme-number, mas não em nenhum outro pacote:

   ;; seguinte adicionado ao pacote Scheme-number
   (put 'exp 
        '(scheme-number scheme-number)
        (lambda (x y) 
          (tag (expt x y)))) 
          ;; usando o primitivo expt

   O que acontece se chamarmos exp com dois números complexos como argumentos?

2. Louis está correto que algo precisava ser feito sobre coerção com argumentos do mesmo tipo, ou apply-generic funciona corretamente como está?
3. Modifique apply-generic para que ele não tente coerção se os dois argumentos tiverem o mesmo tipo.

Exercício 2.82: Mostre como generalizar apply-generic para lidar com coerção no caso geral de múltiplos argumentos. Uma estratégia é tentar coagir todos os argumentos para o tipo do primeiro argumento, depois para o tipo do segundo argumento, e assim por diante. Dê um exemplo de uma situação em que essa estratégia (e da mesma forma a versão de dois argumentos dada acima) não é suficientemente geral. (Dica: Considere o caso em que há algumas operações mistas adequadas presentes na tabela que não serão tentadas.)

Exercício 2.83: Suponha que você está projetando um sistema aritmético genérico para lidar com a torre de tipos mostrada na Figura 2.25: inteiro, racional, real, complexo. Para cada tipo (exceto complexo), projete um procedimento que eleva objetos desse tipo um nível na torre. Mostre como instalar uma operação genérica raise que funcionará para cada tipo (exceto complexo).

Exercício 2.84: Usando a operação raise do Exercício 2.83, modifique o procedimento apply-generic para que ele coage seus argumentos a terem o mesmo tipo pelo método de elevação sucessiva, como discutido nesta seção. Você precisará conceber uma maneira de testar qual dos dois tipos está mais alto na torre. Faça isso de uma maneira que seja "compatível" com o resto do sistema e não leve a problemas ao adicionar novos níveis à torre.

Exercício 2.85: Esta seção mencionou um método para "simplificar" um objeto de dados rebaixando-o na torre de tipos o máximo possível. Projete um procedimento drop que realiza isso para a torre descrita no Exercício 2.83. A chave é decidir, de alguma forma geral, se um objeto pode ser rebaixado. Por exemplo, o número complexo $1.5+0i$ pode ser rebaixado até real, o número complexo $1+0i$ pode ser rebaixado até integer, e o número complexo $2+3i$ não pode ser rebaixado. Aqui está um plano para determinar se um objeto pode ser rebaixado: Comece definindo uma operação genérica project que "empurra" um objeto para baixo na torre. Por exemplo, projetar um número complexo envolveria descartar a parte imaginária. Então, um número pode ser rebaixado se, quando o projetarmos e elevarmos o resultado de volta ao tipo que começamos, terminarmos com algo igual ao que começamos. Mostre como implementar essa ideia em detalhes, escrevendo um procedimento drop que rebaixa um objeto o máximo possível. Você precisará projetar as várias operações de projeção¹¹⁹ e instalar project como uma operação genérica no sistema. Você também precisará fazer uso de um predicado de igualdade genérico, como descrito no Exercício 2.79. Finalmente, use drop para reescrever apply-generic do Exercício 2.84 para que ele "simplifique" suas respostas.

Exercício 2.86: Suponha que queremos lidar com números complexos cujas partes reais, partes imaginárias, magnitudes e ângulos podem ser números ordinários, números racionais ou outros números que possamos desejar adicionar ao sistema. Descreva e implemente as mudanças necessárias no sistema para acomodar isso. Você terá que definir operações como sine e cosine que são genéricas sobre números ordinários e números racionais.

2.5.3Exemplo: Álgebra Simbólica

A manipulação de expressões algébricas simbólicas é um processo complexo que ilustra muitos dos problemas mais difíceis que ocorrem no design de sistemas de grande escala. Uma expressão algébrica, em geral, pode ser vista como uma estrutura hierárquica, uma árvore de operadores aplicados a operandos. Podemos construir expressões algébricas começando com um conjunto de objetos primitivos, como constantes e variáveis, e combinando-os por meio de operadores algébricos, como adição e multiplicação. Como em outras linguagens, formamos abstrações que nos permitem nos referir a objetos compostos em termos simples. Abstrações típicas em álgebra simbólica são ideias como combinação linear, polinômio, função racional ou função trigonométrica. Podemos considerar essas como "tipos" compostos, que são frequentemente úteis para direcionar o processamento de expressões. Por exemplo, poderíamos descrever a expressão $$x^2\sin <!--\; \; -->(y^2+1)+x\cos <!--\; \; -->2y+\cos <!--\; \; -->(y^3-<!--\; -\; -->2y^2)$$ como um polinômio em $x$ com coeficientes que são funções trigonométricas de polinômios em $y$ cujos coeficientes são inteiros.

Não tentaremos desenvolver um sistema completo de manipulação algébrica aqui. Tais sistemas são programas extremamente complexos, incorporando conhecimento algébrico profundo e algoritmos elegantes. O que faremos é olhar para uma parte simples, mas importante, da manipulação algébrica: a aritmética de polinômios. Ilustraremos os tipos de decisões que o designer de tal sistema enfrenta e como aplicar as ideias de dados abstratos e operações genéricas para ajudar a organizar esse esforço.

Aritmética em polinômios

Nossa primeira tarefa ao projetar um sistema para realizar aritmética em polinômios é decidir exatamente o que é um polinômio. Polinômios são normalmente definidos em relação a certas variáveis (os indeterminados do polinômio). Para simplificar, vamos nos restringir a polinômios com apenas um indeterminado (polinômios univariados). Definiremos um polinômio como uma soma de termos, cada um dos quais é um coeficiente, uma potência do indeterminado, ou um produto de um coeficiente e uma potência do indeterminado. Um coeficiente é definido como uma expressão algébrica que não depende do indeterminado do polinômio. Por exemplo,

é um polinômio simples em $x$, e

é um polinômio em $x$ cujos coeficientes são polinômios em $y$.

Já estamos lidando com algumas questões espinhosas. O primeiro desses polinômios é o mesmo que o polinômio

ou não? Uma resposta razoável pode ser "sim, se estivermos considerando um polinômio puramente como uma função matemática, mas não, se estivermos considerando um polinômio como uma forma sintática." O segundo polinômio é algebricamente equivalente a um polinômio em $y$ cujos coeficientes são polinômios em $x$. Nosso sistema deve reconhecer isso ou não? Além disso, existem outras maneiras de representar um polinômio—por exemplo, como um produto de fatores, ou (para um polinômio univariado) como o conjunto de raízes, ou como uma lista dos valores do polinômio em um conjunto especificado de pontos. Podemos contornar essas questões decidindo que, em nosso sistema de manipulação algébrica, um "polinômio" será uma forma sintática específica, e não seu significado matemático subjacente.

Agora devemos considerar como realizar aritmética em polinômios. Neste sistema simples, consideraremos apenas adição e multiplicação. Além disso, insistiremos que dois polinômios a serem combinados devem ter o mesmo indeterminado.

Vamos abordar o projeto do nosso sistema seguindo a disciplina familiar de abstração de dados. Representaremos polinômios usando uma estrutura de dados chamada poly, que consiste em uma variável e uma coleção de termos. Assumimos que temos seletores variable e term-list que extraem essas partes de um poly e um construtor make-poly que monta um poly a partir de uma variável e uma lista de termos. Uma variável será apenas um símbolo, então podemos usar o procedimento same-variable? da seção 2.3.2 para comparar variáveis. Os seguintes procedimentos definem adição e multiplicação de polys:

(define (add-poly p1 p2)
  (if (same-variable? (variable p1) 
                      (variable p2))
      (make-poly 
       (variable p1)
       (add-terms (term-list p1)
                  (term-list p2)))
      (error "Polys not in same var: 
              ADD-POLY"
             (list p1 p2))))

(define (mul-poly p1 p2)
  (if (same-variable? (variable p1) 
                      (variable p2))
      (make-poly 
       (variable p1)
       (mul-terms (term-list p1)
                  (term-list p2)))
      (error "Polys not in same var: 
              MUL-POLY"
             (list p1 p2))))

Para incorporar polinômios em nosso sistema de aritmética genérica, precisamos fornecer a eles tags de tipo. Usaremos a tag polynomial e instalaremos operações apropriadas em polinômios marcados na tabela de operações. Vamos incorporar todo o nosso código em um procedimento de instalação para o pacote de polinômios, semelhante aos da seção 2.5.1:

(define (install-polynomial-package)
  ;; procedimentos internos
  ;; representação de poly
  (define (make-poly variable term-list)
    (cons variable term-list))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  ⟨procedimentos same-variable? 
   e variable? da seção 2.3.2⟩

  ;; representação de termos e listas de termos
  ⟨procedimentos adjoin-term … coeff 
  do texto abaixo⟩

  (define (add-poly p1 p2) …)
  ⟨procedimentos usados por add-poly⟩
  (define (mul-poly p1 p2) …)
  ⟨procedimentos usados por mul-poly⟩

  ;; interface para o resto do sistema
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add '(polynomial polynomial)
       (lambda (p1 p2) 
         (tag (add-poly p1 p2))))
  (put 'mul '(polynomial polynomial)
       (lambda (p1 p2) 
         (tag (mul-poly p1 p2))))
  (put 'make 'polynomial
       (lambda (var terms) 
         (tag (make-poly var terms))))
  'done)

A adição de polinômios é realizada termo a termo. Termos da mesma ordem (ou seja, com a mesma potência do indeterminado) devem ser combinados. Isso é feito formando um novo termo da mesma ordem cujo coeficiente é a soma dos coeficientes dos termos somados. Termos em um dos polinômios para os quais não há termos da mesma ordem no outro polinômio são simplesmente acumulados no polinômio soma que está sendo construído.

Para manipular listas de termos, assumiremos que temos um construtor the-empty-termlist que retorna uma lista de termos vazia e um construtor adjoin-term que adiciona um novo termo a uma lista de termos. Também assumiremos que temos um predicado empty-termlist? que diz se uma lista de termos dada está vazia, um seletor first-term que extrai o termo de maior ordem de uma lista de termos, e um seletor rest-terms que retorna todos os termos, exceto o de maior ordem. Para manipular termos, suporemos que temos um construtor make-term que constrói um termo com uma ordem e coeficiente dados, e seletores order e coeff que retornam, respectivamente, a ordem e o coeficiente do termo. Essas operações nos permitem considerar tanto termos quanto listas de termos como abstrações de dados, cujas representações concretas podemos nos preocupar separadamente.

Aqui está o procedimento que constrói a lista de termos para a soma de dois polinômios:

(define (add-terms L1 L2)
  (cond ((empty-termlist? L1) L2)
        ((empty-termlist? L2) L1)
        (else
         (let ((t1 (first-term L1)) 
               (t2 (first-term L2)))
           (cond ((> (order t1) (order t2))
                  (adjoin-term
                   t1 
                   (add-terms (rest-terms L1) 
                              L2)))
                 ((< (order t1) (order t2))
                  (adjoin-term
                   t2 
                   (add-terms 
                    L1 
                    (rest-terms L2))))
                 (else
                  (adjoin-term
                   (make-term 
                    (order t1)
                    (add (coeff t1) 
                         (coeff t2)))
                   (add-terms 
                    (rest-terms L1)
                    (rest-terms L2))))))))

O ponto mais importante a ser observado aqui é que usamos o procedimento genérico de adição add para somar os coeficientes dos termos que estão sendo combinados. Isso tem consequências poderosas, como veremos abaixo.

Para multiplicar duas listas de termos, multiplicamos cada termo da primeira lista por todos os termos da outra lista, repetidamente usando mul-term-by-all-terms, que multiplica um termo dado por todos os termos em uma lista de termos dada. As listas de termos resultantes (uma para cada termo da primeira lista) são acumuladas em uma soma. Multiplicar dois termos forma um termo cuja ordem é a soma das ordens dos fatores e cujo coeficiente é o produto dos coeficientes dos fatores:

(define (mul-terms L1 L2)
  (if (empty-termlist? L1)
      (the-empty-termlist)
      (add-terms 
       (mul-term-by-all-terms 
        (first-term L1) L2)
       (mul-terms (rest-terms L1) L2))))

(define (mul-term-by-all-terms t1 L)
  (if (empty-termlist? L)
      (the-empty-termlist)
      (let ((t2 (first-term L)))
        (adjoin-term
         (make-term 
          (+ (order t1) (order t2))
          (mul (coeff t1) (coeff t2)))
         (mul-term-by-all-terms 
          t1 
          (rest-terms L))))))

Isso é realmente tudo o que há para adição e multiplicação de polinômios. Observe que, como operamos em termos usando os procedimentos genéricos add e mul, nosso pacote de polinômios é automaticamente capaz de lidar com qualquer tipo de coeficiente conhecido pelo pacote de aritmética genérica. Se incluirmos um mecanismo de coerção, como um dos discutidos na seção 2.5.2, então também seremos automaticamente capazes de lidar com operações em polinômios de diferentes tipos de coeficientes, como

Como instalamos os procedimentos de adição e multiplicação de polinômios add-poly e mul-poly no sistema de aritmética genérica como as operações add e mul para o tipo polynomial, nosso sistema também é automaticamente capaz de lidar com operações em polinômios como

A razão para isso é que, quando o sistema tenta combinar coeficientes, ele despachará através de add e mul. Como os coeficientes são eles mesmos polinômios (em $y$), eles serão combinados usando add-poly e mul-poly. O resultado é uma espécie de "recursão dirigida por dados" em que, por exemplo, uma chamada para mul-poly resultará em chamadas recursivas para mul-poly para multiplicar os coeficientes. Se os coeficientes dos coeficientes fossem eles mesmos polinômios (como poderia ser usado para representar polinômios em três variáveis), a direção dos dados garantiria que o sistema seguiria outro nível de chamadas recursivas, e assim por diante, através de quantos níveis a estrutura dos dados ditar.

Representando listas de termos

Finalmente, devemos enfrentar o trabalho de implementar uma boa representação para listas de termos. Uma lista de termos é, na verdade, um conjunto de coeficientes indexados pela ordem do termo. Portanto, qualquer um dos métodos para representar conjuntos, como discutido na seção 2.3.3, pode ser aplicado a essa tarefa. Por outro lado, nossos procedimentos add-terms e mul-terms sempre acessam listas de termos sequencialmente, da maior para a menor ordem. Assim, usaremos algum tipo de representação de lista ordenada.

Como devemos estruturar a lista que representa uma lista de termos? Uma consideração é a "densidade" dos polinômios que pretendemos manipular. Um polinômio é dito denso se tiver coeficientes diferentes de zero na maioria das ordens. Se tiver muitos termos zero, é dito esparso. Por exemplo,

é um polinômio denso, enquanto

é esparso.

As listas de termos de polinômios densos são mais eficientemente representadas como listas dos coeficientes. Por exemplo, $A$ acima seria bem representado como (1 2 0 3 -2 -5). A ordem de um termo nessa representação é o comprimento da sublista começando com o coeficiente desse termo, decrementado por 1. Essa seria uma representação terrível para um polinômio esparso como $B$: haveria uma lista gigante de zeros pontuada por alguns termos não nulos solitários. Uma representação mais razoável da lista de termos de um polinômio esparso é como uma lista dos termos não nulos, onde cada termo é uma lista contendo a ordem do termo e o coeficiente para essa ordem. Nesse esquema, o polinômio $B$ é eficientemente representado como ((100 1) (2 2) (0 1)). Como a maioria das manipulações de polinômios é realizada em polinômios esparsos, usaremos esse método. Assumiremos que as listas de termos são representadas como listas de termos, organizadas do termo de maior ordem para o de menor ordem. Uma vez que tomamos essa decisão, implementar os seletores e construtores para termos e listas de termos é direto:

(define (adjoin-term term term-list)
  (if (=zero? (coeff term))
      term-list
      (cons term term-list)))
(define (the-empty-termlist) '())
(define (first-term term-list) (car term-list))
(define (rest-terms term-list) (cdr term-list))
(define (empty-termlist? term-list) 
  (null? term-list))
(define (make-term order coeff) 
  (list order coeff))
(define (order term) (car term))
(define (coeff term) (cadr term))

onde =zero? é como definido no Exercício 2.80. (Veja também o Exercício 2.87 abaixo.)

Os usuários do pacote de polinômios criarão polinômios (marcados) por meio do procedimento:

(define (make-polynomial var terms)
  ((get 'make 'polynomial) var terms))

Exercício 2.87: Instale =zero? para polinômios no pacote de aritmética genérica. Isso permitirá que adjoin-term funcione para polinômios com coeficientes que são eles mesmos polinômios.

Exercício 2.88: Estenda o sistema de polinômios para incluir subtração de polinômios. (Dica: Você pode achar útil definir uma operação de negação genérica.)

Exercício 2.89: Defina procedimentos que implementem a representação de listas de termos descrita acima como apropriada para polinômios densos.

Exercício 2.90: Suponha que queremos ter um sistema de polinômios que seja eficiente tanto para polinômios esparsos quanto densos. Uma maneira de fazer isso é permitir ambos os tipos de representação de listas de termos em nosso sistema. A situação é análoga ao exemplo de números complexos da seção 2.4, onde permitimos representações retangulares e polares. Para fazer isso, devemos distinguir diferentes tipos de listas de termos e tornar as operações em listas de termos genéricas. Redesenhe o sistema de polinômios para implementar essa generalização. Este é um esforço importante, não uma mudança local.

Exercício 2.91: Um polinômio univariado pode ser dividido por outro para produzir um quociente polinomial e um resto polinomial. Por exemplo,

$$\frac{x^5-<!--\; -\; -->1}{x^2-<!--\; -\; -->1}=x^3+x,\text{resto}x-<!--\; -\; -->1.$$

A divisão pode ser realizada via divisão longa. Ou seja, divida o termo de maior ordem do dividendo pelo termo de maior ordem do divisor. O resultado é o primeiro termo do quociente. Em seguida, multiplique o resultado pelo divisor, subtraia isso do dividendo e produza o resto da resposta dividindo recursivamente a diferença pelo divisor. Pare quando a ordem do divisor exceder a ordem do dividendo e declare o dividendo como o resto. Além disso, se o dividendo se tornar zero, retorne zero como quociente e resto.

Podemos projetar um procedimento div-poly no modelo de add-poly e mul-poly. O procedimento verifica se os dois polinômios têm a mesma variável. Se sim, div-poly remove a variável e passa o problema para div-terms, que realiza a operação de divisão em listas de termos. Div-poly finalmente reanexa a variável ao resultado fornecido por div-terms. É conveniente projetar div-terms para calcular tanto o quociente quanto o resto de uma divisão. Div-terms pode receber duas listas de termos como argumentos e retornar uma lista da lista de termos do quociente e a lista de termos do resto.

Complete a seguinte definição de div-terms preenchendo as expressões ausentes. Use isso para implementar div-poly, que recebe dois polinômios como argumentos e retorna uma lista do quociente e do resto polinomial.

(define (div-terms L1 L2)
  (if (empty-termlist? L1)
      (list (the-empty-termlist) 
            (the-empty-termlist))
      (let ((t1 (first-term L1))
            (t2 (first-term L2)))
        (if (> (order t2) (order t1))
            (list (the-empty-termlist) L1)
            (let ((new-c (div (coeff t1) 
                              (coeff t2)))
                  (new-o (- (order t1) 
                            (order t2))))
              (let ((rest-of-result
                     ⟨compute rest of result 
                     recursively⟩ )))
                ⟨form complete result⟩ )))))

Hierarquias de tipos em álgebra simbólica

Nosso sistema de polinômios ilustra como objetos de um tipo (polinômios) podem, na verdade, ser objetos complexos que têm objetos de muitos tipos diferentes como partes. Isso não apresenta dificuldade real na definição de operações genéricas. Precisamos apenas instalar operações genéricas apropriadas para realizar as manipulações necessárias das partes dos tipos compostos. Na verdade, vimos que os polinômios formam uma espécie de "abstração de dados recursiva", em que partes de um polinômio podem ser elas mesmas polinômios. Nossas operações genéricas e nosso estilo de programação dirigida por dados podem lidar com essa complicação sem muitos problemas.

Por outro lado, a álgebra de polinômios é um sistema para o qual os tipos de dados não podem ser naturalmente organizados em uma torre. Por exemplo, é possível ter polinômios em $x$ cujos coeficientes são polinômios em $y$. Também é possível ter polinômios em $y$ cujos coeficientes são polinômios em $x$. Nenhum desses tipos está "acima" do outro de forma natural, mas muitas vezes é necessário somar elementos de cada conjunto. Existem várias maneiras de fazer isso. Uma possibilidade é converter um polinômio para o tipo do outro, expandindo e reorganizando os termos para que ambos os polinômios tenham a mesma variável principal. Pode-se impor uma estrutura semelhante a uma torre sobre isso, ordenando as variáveis e, assim, sempre convertendo qualquer polinômio para uma "forma canônica" com a variável de maior prioridade dominante e as variáveis de menor prioridade enterradas nos coeficientes. Essa estratégia funciona razoavelmente bem, exceto que a conversão pode expandir um polinômio desnecessariamente, tornando-o difícil de ler e talvez menos eficiente para trabalhar. A estratégia da torre certamente não é natural para este domínio ou para qualquer domínio onde o usuário possa inventar novos tipos dinamicamente usando tipos antigos em várias formas combinadas, como funções trigonométricas, séries de potências e integrais.

Não deve ser surpresa que controlar a coerção seja um problema sério no projeto de sistemas de manipulação algébrica em grande escala. Muito da complexidade de tais sistemas está preocupada com as relações entre diversos tipos. De fato, é justo dizer que ainda não entendemos completamente a coerção. Na verdade, ainda não entendemos completamente o conceito de tipo de dados. No entanto, o que sabemos nos fornece princípios poderosos de estruturação e modularidade para apoiar o projeto de grandes sistemas.

Exercício 2.92: Ao impor uma ordenação nas variáveis, estenda o pacote de polinômios para que a adição e multiplicação de polinômios funcione para polinômios em diferentes variáveis. (Isso não é fácil!)

Exercício estendido: Funções racionais

Podemos estender nosso sistema de aritmética genérica para incluir funções racionais. Estas são "frações" cujo numerador e denominador são polinômios, como

O sistema deve ser capaz de somar, subtrair, multiplicar e dividir funções racionais, e realizar cálculos como

(Aqui a soma foi simplificada removendo fatores comuns. A multiplicação cruzada comum teria produzido um polinômio de quarto grau sobre um polinômio de quinto grau.)

Se modificarmos nosso pacote de aritmética racional para usar operações genéricas, ele fará o que queremos, exceto pelo problema de reduzir frações aos termos mais baixos.

Exercício 2.93: Modifique o pacote de aritmética racional para usar operações genéricas, mas mude make-rat para que ele não tente reduzir frações aos termos mais baixos. Teste seu sistema chamando make-rational em dois polinômios para produzir uma função racional:

(define p1 (make-polynomial 'x '((2 1) (0 1))))
(define p2 (make-polynomial 'x '((3 1) (0 1))))
(define rf (make-rational p2 p1))

Agora adicione rf a si mesmo, usando add. Você observará que esse procedimento de adição não reduz frações aos termos mais baixos.

Podemos reduzir frações polinomiais aos termos mais baixos usando a mesma ideia que usamos com inteiros: modificando make-rat para dividir tanto o numerador quanto o denominador por seu maior divisor comum. A noção de "maior divisor comum" faz sentido para polinômios. De fato, podemos calcular o GCD de dois polinômios usando essencialmente o mesmo Algoritmo de Euclides que funciona para inteiros. A versão inteira é

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

Usando isso, poderíamos fazer a modificação óbvia para definir uma operação GCD que funciona em listas de termos:

(define (gcd-terms a b)
  (if (empty-termlist? b)
      a
      (gcd-terms b (remainder-terms a b))))

onde remainder-terms seleciona o componente do resto da lista retornada pela operação de divisão de listas de termos div-terms que foi implementada no Exercício 2.91.

Exercício 2.94: Usando div-terms, implemente o procedimento remainder-terms e use isso para definir gcd-terms como acima. Agora escreva um procedimento gcd-poly que calcula o GCD polinomial de dois polinômios. (O procedimento deve sinalizar um erro se os dois polinômios não estiverem na mesma variável.) Instale no sistema uma operação genérica greatest-common-divisor que reduz a gcd-poly para polinômios e a gcd comum para números comuns. Como teste, tente

(define p1 
  (make-polynomial 
   'x '((4 1) (3 -1) (2 -2) (1 2))))

(define p2 
  (make-polynomial 
   'x '((3 1) (1 -1))))

(greatest-common-divisor p1 p2)

e verifique seu resultado manualmente.

Exercício 2.95: Defina $P_1$, $P_2$ e $P_3$ como os polinômios

$$\begin{array}{rl}{P}_1:& x^2-<!--\; -\; -->2x+1,\\ P_2:& 11x^2+7,\\ P_3:& 13x+5.\end{array}$$

Agora defina $Q_1$ como o produto de $P_1$ e $P_2$, e $Q_2$ como o produto de $P_1$ e $P_3$, e use greatest-common-divisor (Exercício 2.94) para calcular o GCD de $Q_1$ e $Q_2$. Observe que a resposta não é a mesma que $P_1$. Este exemplo introduz operações não inteiras na computação, causando dificuldades com o algoritmo GCD. Para entender o que está acontecendo, tente rastrear gcd-terms enquanto calcula o GCD ou tente realizar a divisão manualmente.

Podemos resolver o problema exibido no Exercício 2.95 se usarmos a seguinte modificação do algoritmo GCD (que realmente funciona apenas no caso de polinômios com coeficientes inteiros). Antes de realizar qualquer divisão polinomial na computação do GCD, multiplicamos o dividendo por um fator constante inteiro, escolhido para garantir que nenhuma fração surja durante o processo de divisão. Nossa resposta, portanto, diferirá do GCD real por um fator constante inteiro, mas isso não importa no caso de reduzir funções racionais aos termos mais baixos; o GCD será usado para dividir tanto o numerador quanto o denominador, então o fator constante inteiro será cancelado.

Mais precisamente, se $P$ e $Q$ são polinômios, seja $O_1$ a ordem de $P$ (ou seja, a ordem do maior termo de $P$) e seja $O_2$ a ordem de $Q$. Seja $c$ o coeficiente líder de $Q$. Então, pode-se mostrar que, se multiplicarmos $P$ pelo fator de inteirização $c^{1+O_1-<!--\; -\; -->O_2}$, o polinômio resultante pode ser dividido por $Q$ usando o algoritmo div-terms sem introduzir nenhuma fração. A operação de multiplicar o dividendo por essa constante e depois dividir é às vezes chamada de pseudodivisão de $P$ por $Q$. O resto da divisão é chamado de pseudoresto.

Exercício 2.96:

1. Implemente o procedimento pseudoremainder-terms, que é como remainder-terms, exceto que ele multiplica o dividendo pelo fator de inteirização descrito acima antes de chamar div-terms. Modifique gcd-terms para usar pseudoremainder-terms e verifique que greatest-common-divisor agora produz uma resposta com coeficientes inteiros no exemplo do Exercício 2.95.
2. O GCD agora tem coeficientes inteiros, mas eles são maiores que os de $P_1$. Modifique gcd-terms para que ele remova fatores comuns dos coeficientes da resposta, dividindo todos os coeficientes por seu maior divisor comum (inteiro).

Assim, aqui está como reduzir uma função racional aos termos mais baixos:

• Calcule o GCD do numerador e do denominador, usando a versão de gcd-terms do Exercício 2.96.
• Quando você obtiver o GCD, multiplique tanto o numerador quanto o denominador pelo mesmo fator de inteirização antes de dividir pelo GCD, para que a divisão pelo GCD não introduza coeficientes não inteiros. Como fator, você pode usar o coeficiente líder do GCD elevado à potência $1+O_1-<!--\; -\; -->O_2$, onde $O_2$ é a ordem do GCD e $O_1$ é o máximo das ordens do numerador e do denominador. Isso garantirá que a divisão do numerador e do denominador pelo GCD não introduza frações.
• O resultado dessa operação será um numerador e um denominador com coeficientes inteiros. Os coeficientes normalmente serão muito grandes devido a todos os fatores de inteirização, então o último passo é remover os fatores redundantes, calculando o maior divisor comum (inteiro) de todos os coeficientes do numerador e do denominador e dividindo por esse fator.

Exercício 2.97:

1. Implemente esse algoritmo como um procedimento reduce-terms que recebe duas listas de termos n e d como argumentos e retorna uma lista nn, dd, que são n e d reduzidos aos termos mais baixos via o algoritmo dado acima. Também escreva um procedimento reduce-poly, análogo a add-poly, que verifica se os dois polinômios têm a mesma variável. Se sim, reduce-poly remove a variável e passa o problema para reduce-terms, então reanexa a variável às duas listas de termos fornecidas por reduce-terms.
2. Defina um procedimento análogo a reduce-terms que faz o que o make-rat original fazia para inteiros:

(define (reduce-integers n d)
  (let ((g (gcd n d)))
    (list (/ n g) (/ d g))))

e defina reduce como uma operação genérica que chama apply-generic para despachar para reduce-poly (para argumentos polynomial) ou reduce-integers (para argumentos scheme-number). Agora você pode facilmente fazer o pacote de aritmética racional reduzir frações aos termos mais baixos, tendo make-rat chamar reduce antes de combinar o numerador e o denominador dados para formar um número racional. O sistema agora lida com expressões racionais em inteiros ou polinômios. Para testar seu programa, tente o exemplo no início deste exercício estendido:

(define p1 
  (make-polynomial 'x '((1 1) (0 1))))
(define p2 
  (make-polynomial 'x '((3 1) (0 -1))))
(define p3 
  (make-polynomial 'x '((1 1))))
(define p4 
  (make-polynomial 'x '((2 1) (0 -1))))
(define rf1 (make-rational p1 p2))
(define rf2 (make-rational p3 p4))
(add rf1 rf2)

Veja se você obtém a resposta correta, corretamente reduzida aos termos mais baixos.

O cálculo do GCD está no coração de qualquer sistema que faz operações em funções racionais. O algoritmo usado acima, embora matematicamente direto, é extremamente lento. A lentidão se deve em parte ao grande número de operações de divisão e em parte ao enorme tamanho dos coeficientes intermediários gerados pelas pseudodivisões. Uma das áreas ativas no desenvolvimento de sistemas de manipulação algébrica é o projeto de algoritmos melhores para calcular GCDs polinomiais.

O cálculo do GCD está no coração de qualquer sistema que faz operações em funções racionais. O algoritmo usado acima, embora matematicamente direto, é extremamente lento. A lentidão se deve em parte ao grande número de operações de divisão e em parte ao enorme tamanho dos coeficientes intermediários gerados pelas pseudodivisões. Uma das áreas ativas no desenvolvimento de sistemas de manipulação algébrica é o projeto de algoritmos melhores para calcular GCDs polinomiais.