2.4Múltiplas Representações para Dados Abstratos

Introduzimos a abstração de dados, uma metodologia para estruturar sistemas de forma que grande parte de um programa possa ser especificada independentemente das escolhas envolvidas na implementação dos objetos de dados que o programa manipula. Por exemplo, vimos em 2.1.1 como separar a tarefa de projetar um programa que usa números racionais da tarefa de implementar números racionais em termos dos mecanismos primitivos da linguagem de computador para construir dados compostos. A ideia principal foi erguer uma barreira de abstração – neste caso, os seletores e construtores para números racionais (make-rat, numer, denom) – que isola a forma como os números racionais são usados de sua representação subjacente em termos de estrutura de lista. Uma barreira de abstração semelhante isola os detalhes dos procedimentos que realizam aritmética racional (add-rat, sub-rat, mul-rat e div-rat) dos procedimentos de "nível superior" que usam números racionais. O programa resultante tem a estrutura mostrada em Figura 2.1.

Essas barreiras de abstração de dados são ferramentas poderosas para controlar a complexidade. Ao isolar as representações subjacentes dos objetos de dados, podemos dividir a tarefa de projetar um grande programa em tarefas menores que podem ser realizadas separadamente. Mas esse tipo de abstração de dados ainda não é poderoso o suficiente, porque nem sempre faz sentido falar de "a representação subjacente" para um objeto de dados.

Por um lado, pode haver mais de uma representação útil para um objeto de dados, e podemos querer projetar sistemas que possam lidar com múltiplas representações. Para dar um exemplo simples, números complexos podem ser representados de duas formas quase equivalentes: na forma retangular (partes real e imaginária) e na forma polar (magnitude e ângulo). Às vezes, a forma retangular é mais apropriada e, às vezes, a forma polar é mais apropriada. De fato, é perfeitamente plausível imaginar um sistema em que os números complexos são representados de ambas as formas, e em que os procedimentos para manipular números complexos funcionam com qualquer representação.

Mais importante, os sistemas de programação são frequentemente projetados por muitas pessoas trabalhando por longos períodos de tempo, sujeitos a requisitos que mudam com o tempo. Em tal ambiente, simplesmente não é possível que todos concordem antecipadamente sobre as escolhas de representação de dados. Portanto, além das barreiras de abstração de dados que isolam a representação do uso, precisamos de barreiras de abstração que isolem diferentes escolhas de design umas das outras e permitam que diferentes escolhas coexistam em um único programa. Além disso, como grandes programas são frequentemente criados combinando módulos pré-existentes que foram projetados isoladamente, precisamos de convenções que permitam aos programadores incorporar módulos em sistemas maiores aditivamente, ou seja, sem precisar redesenhar ou reimplementar esses módulos.

Nesta seção, aprenderemos como lidar com dados que podem ser representados de diferentes maneiras por diferentes partes de um programa. Isso requer a construção de procedimentos genéricos – procedimentos que podem operar em dados que podem ser representados de mais de uma maneira. Nossa principal técnica para construir procedimentos genéricos será trabalhar em termos de objetos de dados que possuem etiquetas de tipo, ou seja, objetos de dados que incluem informações explícitas sobre como devem ser processados. Também discutiremos programação orientada a dados, uma estratégia de implementação poderosa e conveniente para montar sistemas aditivamente com operações genéricas.

Começamos com o exemplo simples de números complexos. Veremos como as etiquetas de tipo e o estilo orientado a dados nos permitem projetar representações retangulares e polares separadas para números complexos, mantendo a noção de um objeto de dados abstrato "número complexo". Conseguiremos isso definindo procedimentos aritméticos para números complexos (add-complex, sub-complex, mul-complex e div-complex) em termos de seletores genéricos que acessam partes de um número complexo independentemente de como o número é representado. O sistema de números complexos resultante, como mostrado em Figura 2.19, contém dois tipos diferentes de barreiras de abstração. As barreiras de abstração "horizontais" desempenham o mesmo papel que as da Figura 2.1. Elas isolam operações de "nível superior" de representações de "nível inferior". Além disso, há uma barreira "vertical" que nos dá a capacidade de projetar e instalar representações alternativas separadamente.

Em 2.5, mostraremos como usar etiquetas de tipo e o estilo orientado a dados para desenvolver um pacote aritmético genérico. Isso fornece procedimentos (add, mul, e assim por diante) que podem ser usados para manipular todos os tipos de "números" e podem ser facilmente estendidos quando um novo tipo de número é necessário. Em 2.5.3, mostraremos como usar aritmética genérica em um sistema que realiza álgebra simbólica.

2.4.1Representações para Números Complexos

Desenvolveremos um sistema que realiza operações aritméticas em números complexos como um exemplo simples, mas irrealista, de um programa que usa operações genéricas. Começamos discutindo duas representações plausíveis para números complexos como pares ordenados: a forma retangular (parte real e parte imaginária) e a forma polar (magnitude e ângulo).¹⁰⁹ A seção 2.4.2 mostrará como ambas as representações podem coexistir em um único sistema por meio do uso de etiquetas de tipo e operações genéricas.

Assim como os números racionais, os números complexos são naturalmente representados como pares ordenados. O conjunto de números complexos pode ser pensado como um espaço bidimensional com dois eixos ortogonais, o eixo "real" e o eixo "imaginário". (Veja Figura 2.20.) Desse ponto de vista, o número complexo $z=x+iy$ (onde $i^2=\text{−1}$) pode ser pensado como o ponto no plano cuja coordenada real é $x$ e cuja coordenada imaginária é $y$. A adição de números complexos reduz-se, nesta representação, à adição de coordenadas: $$\begin{array}{rcl}\text{Parte Real}(z_1+z_2)& =& \text{Parte Real}(z_1)+\\ & & \text{Parte Real}(z_2),\\ \text{Parte Imaginária}(z_1+z_2)& =& \text{Parte Imaginária}(z_1)+\\ & & \text{Parte Imaginária}(z_2).\end{array}$$

Ao multiplicar números complexos, é mais natural pensar em termos de representar um número complexo na forma polar, como uma magnitude e um ângulo ($r$ e $A$ na Figura 2.20). O produto de dois números complexos é o vetor obtido esticando um número complexo pelo comprimento do outro e depois girando-o pelo ângulo do outro: $$\begin{array}{rcl}\text{Magnitude}(z_1\cdot <!--\; \cdot \; -->z_2)& =& \text{Magnitude}(z_1)\cdot <!--\; \cdot \; -->\text{Magnitude}(z_2),\\ \text{Ângulo}(z_1\cdot <!--\; \cdot \; -->z_2)& =& \text{Ângulo}(z_1)+\text{Ângulo}(z_2).\end{array}$$

Assim, existem duas representações diferentes para números complexos, que são apropriadas para diferentes operações. No entanto, do ponto de vista de alguém escrevendo um programa que usa números complexos, o princípio da abstração de dados sugere que todas as operações para manipular números complexos devem estar disponíveis, independentemente de qual representação é usada pelo computador. Por exemplo, muitas vezes é útil poder encontrar a magnitude de um número complexo especificado por coordenadas retangulares. Da mesma forma, muitas vezes é útil determinar a parte real de um número complexo especificado por coordenadas polares.

Para projetar tal sistema, podemos seguir a mesma estratégia de abstração de dados que seguimos ao projetar o pacote de números racionais em 2.1.1. Suponha que as operações em números complexos sejam implementadas em termos de quatro seletores: real-part, imag-part, magnitude e angle. Também suponha que temos dois procedimentos para construir números complexos: make-from-real-imag retorna um número complexo com partes real e imaginária especificadas, e make-from-mag-ang retorna um número complexo com magnitude e ângulo especificados. Esses procedimentos têm a propriedade de que, para qualquer número complexo z, ambos

(make-from-real-imag (real-part z) 
                     (imag-part z))

e

(make-from-mag-ang (magnitude z) 
                   (angle z))

produzem números complexos que são iguais a z.

Usando esses construtores e seletores, podemos implementar aritmética em números complexos usando os "dados abstratos" especificados pelos construtores e seletores, assim como fizemos para números racionais em 2.1.1. Como mostrado nas fórmulas acima, podemos adicionar e subtrair números complexos em termos de partes real e imaginária, enquanto multiplicamos e dividimos números complexos em termos de magnitudes e ângulos:

(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))))

Para completar o pacote de números complexos, devemos escolher uma representação e implementar os construtores e seletores em termos de números primitivos e estrutura de lista primitiva. Há duas maneiras óbvias de fazer isso: podemos representar um número complexo na "forma retangular" como um par (parte real, parte imaginária) ou na "forma polar" como um par (magnitude, ângulo). Qual devemos escolher?

Para tornar as diferentes escolhas concretas, imagine que há dois programadores, Ben Bitdiddle e Alyssa P. Hacker, que estão projetando independentemente representações para o sistema de números complexos. Ben escolhe representar números complexos na forma retangular. Com essa escolha, selecionar as partes real e imaginária de um número complexo é direto, assim como construir um número complexo com partes real e imaginária dadas. Para encontrar a magnitude e o ângulo, ou para construir um número complexo com uma magnitude e ângulo dados, ele usa as relações trigonométricas

que relacionam as partes real e imaginária $(x,y)$ à magnitude e ao ângulo $(r,A)$.¹¹⁰ A representação de Ben é, portanto, dada pelos seguintes seletores e construtores:

(define (real-part z) (car z))
(define (imag-part z) (cdr z))

(define (magnitude z)
  (sqrt (+ (square (real-part z)) 
           (square (imag-part z)))))

(define (angle z)
  (atan (imag-part z) (real-part z)))

(define (make-from-real-imag x y) 
  (cons x y))

(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))

Alyssa, em contraste, escolhe representar números complexos na forma polar. Para ela, selecionar a magnitude e o ângulo é direto, mas ela precisa usar as relações trigonométricas para obter as partes real e imaginária. A representação de Alyssa é:

(define (real-part z)
  (* (magnitude z) (cos (angle z))))

(define (imag-part z)
  (* (magnitude z) (sin (angle z))))

(define (magnitude z) (car z))
(define (angle z) (cdr z))

(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))

(define (make-from-mag-ang r a) 
  (cons r a))

A disciplina de abstração de dados garante que a mesma implementação de add-complex, sub-complex, mul-complex e div-complex funcionará com a representação de Ben ou a de Alyssa.

2.4.2Dados Etiquetados

Uma maneira de ver a abstração de dados é como uma aplicação do "princípio do menor compromisso". Na implementação do sistema de números complexos em 2.4.1, podemos usar a representação retangular de Ben ou a representação polar de Alyssa. A barreira de abstração formada pelos seletores e construtores nos permite adiar até o último momento possível a escolha de uma representação concreta para nossos objetos de dados e, assim, manter a máxima flexibilidade no design do nosso sistema.

O princípio do menor compromisso pode ser levado a extremos ainda maiores. Se desejarmos, podemos manter a ambiguidade de representação mesmo depois de termos projetado os seletores e construtores, e optar por usar tanto a representação de Ben quanto a de Alyssa. Se ambas as representações estiverem incluídas em um único sistema, no entanto, precisaremos de alguma maneira de distinguir dados na forma polar de dados na forma retangular. Caso contrário, se nos pedissem, por exemplo, para encontrar a magnitude do par (3, 4), não saberíamos se responder 5 (interpretando o número na forma retangular) ou 3 (interpretando o número na forma polar). Uma maneira direta de realizar essa distinção é incluir uma etiqueta de tipo – o símbolo rectangular ou polar – como parte de cada número complexo. Então, quando precisarmos manipular um número complexo, podemos usar a etiqueta para decidir qual seletor aplicar.

Para manipular dados etiquetados, assumiremos que temos procedimentos type-tag e contents que extraem de um objeto de dados a etiqueta e o conteúdo real (as coordenadas polares ou retangulares, no caso de um número complexo). Também postularemos um procedimento attach-tag que recebe uma etiqueta e um conteúdo e produz um objeto de dados etiquetado. Uma maneira direta de implementar isso é usar a estrutura de lista comum:

(define (attach-tag type-tag contents)
  (cons type-tag contents))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum: 
              TYPE-TAG" datum)))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum: 
              CONTENTS" datum)))

Usando esses procedimentos, podemos definir predicados rectangular? e polar?, que reconhecem números retangulares e polares, respectivamente:

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))

(define (polar? z)
  (eq? (type-tag z) 'polar))

Com as etiquetas de tipo, Ben e Alyssa podem agora modificar seu código para que suas duas representações diferentes possam coexistir no mesmo sistema. Sempre que Ben constrói um número complexo, ele o etiqueta como retangular. Sempre que Alyssa constrói um número complexo, ela o etiqueta como polar. Além disso, Ben e Alyssa devem garantir que os nomes de seus procedimentos não entrem em conflito. Uma maneira de fazer isso é Ben anexar o sufixo rectangular ao nome de cada um de seus procedimentos de representação e Alyssa anexar polar aos nomes dos dela. Aqui está a representação retangular revisada de Ben de 2.4.1:

(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))

(define (magnitude-rectangular z)
  (sqrt (+ (square (real-part-rectangular z))
           (square (imag-part-rectangular z)))))

(define (angle-rectangular z)
  (atan (imag-part-rectangular z)
        (real-part-rectangular z)))

(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))

(define (make-from-mag-ang-rectangular r a)
  (attach-tag 
   'rectangular
   (cons (* r (cos a)) (* r (sin a)))))

e aqui está a representação polar revisada de Alyssa:

(define (real-part-polar z)
  (* (magnitude-polar z) 
     (cos (angle-polar z))))

(define (imag-part-polar z)
  (* (magnitude-polar z) 
     (sin (angle-polar z))))

(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))

(define (make-from-real-imag-polar x y)
  (attach-tag 
   'polar
   (cons (sqrt (+ (square x) (square y)))
         (atan y x))))

(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))

Cada seletor genérico é implementado como um procedimento que verifica a etiqueta de seu argumento e chama o procedimento apropriado para lidar com dados desse tipo. Por exemplo, para obter a parte real de um número complexo, real-part examina a etiqueta para determinar se deve usar o real-part-rectangular de Ben ou o real-part-polar de Alyssa. Em ambos os casos, usamos contents para extrair o dado bruto, sem etiqueta, e enviá-lo ao procedimento retangular ou polar conforme necessário:

(define (real-part z)
  (cond ((rectangular? z)
         (real-part-rectangular (contents z)))
        ((polar? z)
         (real-part-polar (contents z)))
        (else
         (error "Unknown type: 
               REAL-PART" z))))

(define (imag-part z)
  (cond ((rectangular? z)
         (imag-part-rectangular (contents z)))
        ((polar? z)
         (imag-part-polar (contents z)))
        (else
         (error "Unknown type: 
               IMAG-PART" z))))

(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular (contents z)))
        ((polar? z)
         (magnitude-polar (contents z)))
        (else
         (error "Unknown type: 
               MAGNITUDE" z))))

(define (angle z)
  (cond ((rectangular? z)
         (angle-rectangular (contents z)))
        ((polar? z)
         (angle-polar (contents z)))
        (else
         (error "Unknown type: 
               ANGLE" z))))

Para implementar as operações aritméticas de números complexos, podemos usar os mesmos procedimentos add-complex, sub-complex, mul-complex e div-complex de 2.4.1, porque os seletores que eles chamam são genéricos e, portanto, funcionarão com qualquer representação. Por exemplo, o procedimento add-complex ainda é

(define (add-complex z1 z2)
  (make-from-real-imag 
   (+ (real-part z1) (real-part z2))
   (+ (imag-part z1) (imag-part z2))))

Finalmente, devemos escolher se construímos números complexos usando a representação de Ben ou a de Alyssa. Uma escolha razoável é construir números retangulares sempre que tivermos partes real e imaginária e construir números polares sempre que tivermos magnitudes e ângulos:

(define (make-from-real-imag x y)
  (make-from-real-imag-rectangular x y))

(define (make-from-mag-ang r a)
  (make-from-mag-ang-polar r a))

O sistema de números complexos resultante tem a estrutura mostrada na Figura 2.21. O sistema foi decomposto em três partes relativamente independentes: as operações aritméticas de números complexos, a implementação polar de Alyssa e a implementação retangular de Ben. As implementações polar e retangular poderiam ter sido escritas por Ben e Alyssa trabalhando separadamente, e ambas podem ser usadas como representações subjacentes por um terceiro programador implementando os procedimentos aritméticos complexos em termos da interface abstrata de construtores/seletores.

Como cada objeto de dados é etiquetado com seu tipo, os seletores operam nos dados de maneira genérica. Ou seja, cada seletor é definido para ter um comportamento que depende do tipo específico de dados ao qual é aplicado. Observe o mecanismo geral para interfacear as representações separadas: Dentro de uma determinada implementação de representação (digamos, o pacote polar de Alyssa), um número complexo é um par sem tipo (magnitude, ângulo). Quando um seletor genérico opera em um número do tipo polar, ele remove a etiqueta e passa o conteúdo para o código de Alyssa. Por outro lado, quando Alyssa constrói um número para uso geral, ela o etiqueta com um tipo para que ele possa ser reconhecido apropriadamente pelos procedimentos de nível superior. Essa disciplina de remover e anexar etiquetas à medida que os objetos de dados são passados de nível para nível pode ser uma estratégia organizacional importante, como veremos em 2.5.

2.4.3Programação Orientada a Dados e Aditividade

A estratégia geral de verificar o tipo de um dado e chamar um procedimento apropriado é chamada de despacho por tipo. Essa é uma estratégia poderosa para obter modularidade no design de sistemas. Por outro lado, implementar o despacho como em 2.4.2 tem duas fraquezas significativas. Uma fraqueza é que os procedimentos de interface genérica (real-part, imag-part, magnitude e angle) devem conhecer todas as diferentes representações. Por exemplo, suponha que quiséssemos incorporar uma nova representação para números complexos em nosso sistema de números complexos. Precisaríamos identificar essa nova representação com um tipo e, em seguida, adicionar uma cláusula a cada um dos procedimentos de interface genérica para verificar o novo tipo e aplicar o seletor apropriado para essa representação.

Outra fraqueza da técnica é que, embora as representações individuais possam ser projetadas separadamente, devemos garantir que nenhum dois procedimentos em todo o sistema tenham o mesmo nome. É por isso que Ben e Alyssa tiveram que mudar os nomes de seus procedimentos originais de 2.4.1.

A questão subjacente a ambas essas fraquezas é que a técnica para implementar interfaces genéricas não é aditiva. A pessoa que implementa os procedimentos de seletores genéricos deve modificar esses procedimentos cada vez que uma nova representação é instalada, e as pessoas que interfaceiam as representações individuais devem modificar seu código para evitar conflitos de nomes. Em cada um desses casos, as mudanças que devem ser feitas no código são diretas, mas devem ser feitas mesmo assim, e isso é uma fonte de inconveniência e erro. Isso não é um grande problema para o sistema de números complexos como ele está, mas suponha que houvesse não duas, mas centenas de diferentes representações para números complexos. E suponha que houvesse muitos seletores genéricos para serem mantidos na interface de dados abstratos. Suponha, de fato, que nenhum programador conhecesse todos os procedimentos de interface ou todas as representações. O problema é real e deve ser abordado em programas como sistemas de gerenciamento de banco de dados em grande escala.

O que precisamos é de um meio para modularizar ainda mais o design do sistema. Isso é fornecido pela técnica de programação conhecida como programação orientada a dados. Para entender como a programação orientada a dados funciona, comece com a observação de que sempre que lidamos com um conjunto de operações genéricas que são comuns a um conjunto de diferentes tipos, estamos, de fato, lidando com uma tabela bidimensional que contém as operações possíveis em um eixo e os tipos possíveis no outro eixo. As entradas na tabela são os procedimentos que implementam cada operação para cada tipo de argumento apresentado. No sistema de números complexos desenvolvido na seção anterior, a correspondência entre o nome da operação, o tipo de dados e o procedimento real foi espalhada entre as várias cláusulas condicionais nos procedimentos de interface genérica. Mas a mesma informação poderia ter sido organizada em uma tabela, como mostrado na Figura 2.22.

A programação orientada a dados é a técnica de projetar programas para trabalhar diretamente com essa tabela. Anteriormente, implementamos o mecanismo que interfaceia o código de aritmética complexa com os dois pacotes de representação como um conjunto de procedimentos que cada um realiza um despacho explícito por tipo. Aqui, implementaremos a interface como um único procedimento que procura a combinação do nome da operação e do tipo do argumento na tabela para encontrar o procedimento correto a ser aplicado e, em seguida, aplica-o ao conteúdo do argumento. Se fizermos isso, então, para adicionar um novo pacote de representação ao sistema, não precisamos mudar nenhum procedimento existente; precisamos apenas adicionar novas entradas à tabela.

Para implementar esse plano, assuma que temos dois procedimentos, put e get, para manipular a tabela de operações e tipos:

• (put ⟨op⟩ ⟨type⟩ ⟨item⟩) instala o ⟨item⟩ na tabela, indexado pelo ⟨op⟩ e o ⟨type⟩.
• (get ⟨op⟩ ⟨type⟩) procura a entrada ⟨op⟩, ⟨type⟩ na tabela e retorna o item encontrado lá. Se nenhum item for encontrado, get retorna falso.

Por enquanto, podemos assumir que put e get estão incluídos em nossa linguagem. Em Capítulo 3 (3.3.3), veremos como implementar essas e outras operações para manipular tabelas.

Aqui está como a programação orientada a dados pode ser usada no sistema de números complexos. Ben, que desenvolveu a representação retangular, implementa seu código exatamente como fez originalmente. Ele define uma coleção de procedimentos, ou um pacote, e interfaceia esses procedimentos com o resto do sistema adicionando entradas à tabela que dizem ao sistema como operar em números retangulares. Isso é realizado chamando o seguinte procedimento:

(define (install-rectangular-package)
  ;; procedimentos internos
  (define (real-part z) (car z))
  (define (imag-part z) (cdr z))
  (define (make-from-real-imag x y) 
    (cons x y))
  (define (magnitude z)
    (sqrt (+ (square (real-part z))
             (square (imag-part z)))))
  (define (angle z)
    (atan (imag-part z) (real-part z)))
  (define (make-from-mag-ang r a)
    (cons (* r (cos a)) (* r (sin a))))
  ;; interface com o resto do sistema
  (define (tag x) 
    (attach-tag 'rectangular x))
  (put 'real-part '(rectangular) real-part)
  (put 'imag-part '(rectangular) imag-part)
  (put 'magnitude '(rectangular) magnitude)
  (put 'angle '(rectangular) angle)
  (put 'make-from-real-imag 'rectangular
       (lambda (x y) 
         (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'rectangular
       (lambda (r a) 
         (tag (make-from-mag-ang r a))))
  'done)

Observe que os procedimentos internos aqui são os mesmos procedimentos de 2.4.1 que Ben escreveu quando estava trabalhando isoladamente. Nenhuma mudança é necessária para interfaceá-los com o resto do sistema. Além disso, como essas definições de procedimentos são internas ao procedimento de instalação, Ben não precisa se preocupar com conflitos de nomes com outros procedimentos fora do pacote retangular. Para interfacear esses procedimentos com o resto do sistema, Ben instala seu procedimento real-part sob o nome de operação real-part e o tipo (rectangular), e da mesma forma para os outros seletores.¹¹¹ A interface também define os construtores a serem usados pelo sistema externo.¹¹² Esses são idênticos aos construtores definidos internamente por Ben, exceto que eles anexam a etiqueta.

O pacote polar de Alyssa é análogo:

(define (install-polar-package)
  ;; procedimentos internos
  (define (magnitude z) (car z))
  (define (angle z) (cdr z))
  (define (make-from-mag-ang r a) (cons r a))
  (define (real-part z)
    (* (magnitude z) (cos (angle z))))
  (define (imag-part z)
    (* (magnitude z) (sin (angle z))))
  (define (make-from-real-imag x y)
    (cons (sqrt (+ (square x) (square y)))
          (atan y x)))
  ;; interface com o resto do sistema
  (define (tag x) (attach-tag 'polar x))
  (put 'real-part '(polar) real-part)
  (put 'imag-part '(polar) imag-part)
  (put 'magnitude '(polar) magnitude)
  (put 'angle '(polar) angle)
  (put 'make-from-real-imag 'polar
       (lambda (x y) 
         (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'polar
       (lambda (r a) 
         (tag (make-from-mag-ang r a))))
  'done)

Mesmo que Ben e Alyssa ainda usem seus procedimentos originais definidos com os mesmos nomes que os do outro (por exemplo, real-part), essas definições agora são internas a diferentes procedimentos (veja 1.1.8), então não há conflito de nomes.

Os seletores de aritmética complexa acessam a tabela por meio de um procedimento geral de "operação" chamado apply-generic, que aplica uma operação genérica a alguns argumentos. Apply-generic procura na tabela sob o nome da operação e os tipos dos argumentos e aplica o procedimento resultante, se um estiver presente:¹¹³

(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))
          (error
            "No method for these types: 
             APPLY-GENERIC"
            (list op type-tags))))))

Usando apply-generic, podemos definir nossos seletores genéricos da seguinte forma:

(define (real-part z) 
  (apply-generic 'real-part z))
(define (imag-part z) 
  (apply-generic 'imag-part z))
(define (magnitude z) 
  (apply-generic 'magnitude z))
(define (angle z) 
  (apply-generic 'angle z))

Observe que esses procedimentos não mudam em nada se uma nova representação for adicionada ao sistema.

Também podemos extrair da tabela os construtores a serem usados pelos programas externos aos pacotes para fazer números complexos a partir de partes real e imaginária e de magnitudes e ângulos. Como em 2.4.2, construímos números retangulares sempre que temos partes real e imaginária, e números polares sempre que temos magnitudes e ângulos:

(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))

Exercício 2.73: 2.3.2 descreveu um programa que realiza diferenciação simbólica:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) 
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product 
            (multiplier exp)
            (deriv (multiplicand exp) var))
           (make-product 
            (deriv (multiplier exp) var)
            (multiplicand exp))))
        ⟨mais regras podem ser adicionadas aqui⟩
        (else
         (error "unknown expression type:
                      DERIV" exp))))

Podemos considerar esse programa como realizando um despacho no tipo da expressão a ser diferenciada. Nessa situação, a "etiqueta de tipo" do dado é o símbolo do operador algébrico (como +) e a operação sendo realizada é deriv. Podemos transformar esse programa em estilo orientado a dados reescrevendo o procedimento básico de derivada como

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) 
           (if (same-variable? exp var) 
               1 
               0))
         (else
          ((get 'deriv (operator exp)) 
           (operands exp) 
           var))))

(define (operator exp) (car exp))
(define (operands exp) (cdr exp))

1. Explique o que foi feito acima. Por que não podemos assimilar os predicados number? e variable? no despacho orientado a dados?
2. Escreva os procedimentos para derivadas de somas e produtos, e o código auxiliar necessário para instalá-los na tabela usada pelo programa acima.
3. Escolha qualquer regra de diferenciação adicional que você goste, como a de expoentes (Exercício 2.56), e instale-a nesse sistema orientado a dados.
4. Neste simples manipulador algébrico, o tipo de uma expressão é o operador algébrico que a une. Suponha, no entanto, que indexássemos os procedimentos de maneira oposta, de modo que a linha de despacho em deriv parecesse

   ((get (operator exp) 'deriv) 
    (operands exp) var)

   Quais mudanças correspondentes no sistema de derivadas são necessárias?

Exercício 2.74: Insatiable Enterprises, Inc., é uma empresa altamente descentralizada, consistindo em um grande número de divisões independentes localizadas em todo o mundo. As instalações de computação da empresa acabaram de ser interconectadas por meio de um esquema inteligente de interface de rede que faz com que toda a rede pareça, para qualquer usuário, ser um único computador. A presidente da Insatiable, em sua primeira tentativa de explorar a capacidade da rede de extrair informações administrativas dos arquivos das divisões, fica desapontada ao descobrir que, embora todos os arquivos das divisões tenham sido implementados como estruturas de dados em Scheme, a estrutura de dados específica usada varia de divisão para divisão. Uma reunião dos gerentes das divisões é convocada às pressas para buscar uma estratégia para integrar os arquivos que atenda às necessidades da sede, preservando a autonomia existente das divisões.

Mostre como tal estratégia pode ser implementada com programação orientada a dados. Como exemplo, suponha que os registros de pessoal de cada divisão consistam em um único arquivo, que contém um conjunto de registros indexados pelos nomes dos funcionários. A estrutura do conjunto varia de divisão para divisão. Além disso, o registro de cada funcionário é, ele mesmo, um conjunto (estruturado de forma diferente de divisão para divisão) que contém informações indexadas por identificadores como address e salary. Em particular:

1. Implemente para a sede um procedimento get-record que recupera o registro de um funcionário especificado de um arquivo de pessoal especificado. O procedimento deve ser aplicável a qualquer arquivo de divisão. Explique como os arquivos individuais das divisões devem ser estruturados. Em particular, que informações de tipo devem ser fornecidas?
2. Implemente para a sede um procedimento get-salary que retorna as informações de salário de um determinado registro de funcionário de qualquer arquivo de pessoal de divisão. Como o registro deve ser estruturado para que essa operação funcione?
3. Implemente para a sede um procedimento find-employee-record. Isso deve pesquisar todos os arquivos das divisões pelo registro de um determinado funcionário e retornar o registro. Suponha que esse procedimento receba como argumentos o nome de um funcionário e uma lista de todos os arquivos das divisões.
4. Quando a Insatiable assume uma nova empresa, quais mudanças devem ser feitas para incorporar as novas informações de pessoal ao sistema central?

Passagem de Mensagens

A ideia principal da programação orientada a dados é lidar com operações genéricas em programas, lidando explicitamente com tabelas de operações e tipos, como a tabela na Figura 2.22. O estilo de programação que usamos em 2.4.2 organizou o despacho necessário por tipo, fazendo com que cada operação cuidasse de seu próprio despacho. Na prática, isso decompõe a tabela de operações e tipos em linhas, com cada procedimento de operação genérica representando uma linha da tabela.

Uma estratégia de implementação alternativa é decompor a tabela em colunas e, em vez de usar "operações inteligentes" que despacham em tipos de dados, trabalhar com "objetos de dados inteligentes" que despacham em nomes de operações. Podemos fazer isso organizando as coisas de forma que um objeto de dados, como um número retangular, seja representado como um procedimento que recebe como entrada o nome da operação necessária e realiza a operação indicada. Nessa disciplina, make-from-real-imag poderia ser escrito como

(define (make-from-real-imag x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'imag-part) y)
          ((eq? op 'magnitude)
           (sqrt (+ (square x) (square y))))
          ((eq? op 'angle) (atan y x))
          (else
           (error "Unknown op: 
            MAKE-FROM-REAL-IMAG" op))))
  dispatch)

O procedimento apply-generic correspondente, que aplica uma operação genérica a um argumento, agora simplesmente alimenta o nome da operação para o objeto de dados e deixa o objeto fazer o trabalho:¹¹⁴

(define (apply-generic op arg) (arg op))

Observe que o valor retornado por make-from-real-imag é um procedimento – o procedimento interno dispatch. Esse é o procedimento que é invocado quando apply-generic solicita que uma operação seja realizada.

Esse estilo de programação é chamado de passagem de mensagens. O nome vem da imagem de que um objeto de dados é uma entidade que recebe o nome da operação solicitada como uma "mensagem". Já vimos um exemplo de passagem de mensagens em 2.1.3, onde vimos como cons, car e cdr poderiam ser definidos sem objetos de dados, mas apenas com procedimentos. Aqui vemos que a passagem de mensagens não é um truque matemático, mas uma técnica útil para organizar sistemas com operações genéricas. No restante deste capítulo, continuaremos a usar programação orientada a dados, em vez de passagem de mensagens, para discutir operações aritméticas genéricas. Em Capítulo 3, retornaremos à passagem de mensagens e veremos que ela pode ser uma ferramenta poderosa para estruturar programas de simulação.

Exercício 2.75: Implemente o construtor make-from-mag-ang no estilo de passagem de mensagens. Esse procedimento deve ser análogo ao procedimento make-from-real-imag dado acima.

Exercício 2.76: À medida que um grande sistema com operações genéricas evolui, novos tipos de objetos de dados ou novas operações podem ser necessários. Para cada uma das três estratégias – operações genéricas com despacho explícito, estilo orientado a dados e estilo de passagem de mensagens – descreva as mudanças que devem ser feitas em um sistema para adicionar novos tipos ou novas operações. Qual organização seria mais apropriada para um sistema em que novos tipos devem ser frequentemente adicionados? Qual seria mais apropriada para um sistema em que novas operações devem ser frequentemente adicionadas?

(apply + (list 1 2 3 4))