2.2Dados Hierárquicos e a Propriedade de Fechamento

Como vimos, os pares fornecem uma "cola" primitiva que podemos usar para construir objetos de dados compostos. A Figura 2.2 mostra uma maneira padrão de visualizar um par — neste caso, o par formado por (cons 1 2). Nesta representação, que é chamada de notação de caixa e ponteiro, cada objeto é mostrado como um ponteiro para uma caixa. A caixa para um objeto primitivo contém uma representação do objeto. Por exemplo, a caixa para um número contém um numeral. A caixa para um par é na verdade uma caixa dupla, a parte esquerda contendo (um ponteiro para) o car do par e a parte direita contendo o cdr.

Já vimos que cons pode ser usado para combinar não apenas números, mas também pares. (Você usou esse fato, ou deveria ter usado, ao fazer os Exercício 2.2 e Exercício 2.3.) Como consequência, os pares fornecem um bloco de construção universal a partir do qual podemos construir todos os tipos de estruturas de dados. A Figura 2.3 mostra duas maneiras de usar pares para combinar os números 1, 2, 3 e 4.

A capacidade de criar pares cujos elementos são pares é a essência da importância da estrutura de listas como uma ferramenta de representação. Referimo-nos a essa capacidade como a propriedade de fechamento de cons. Em geral, uma operação para combinar objetos de dados satisfaz a propriedade de fechamento se os resultados de combinar coisas com essa operação podem ser combinados usando a mesma operação.⁷² O fechamento é a chave para o poder em qualquer meio de combinação porque nos permite criar estruturas hierárquicas — estruturas feitas de partes, que por sua vez são feitas de partes, e assim por diante.

Desde o início do Capítulo 1, usamos essencialmente o fechamento ao lidar com procedimentos, porque todos, exceto os programas mais simples, dependem do fato de que os elementos de uma combinação podem ser combinações. Nesta seção, abordamos as consequências do fechamento para dados compostos. Descrevemos algumas técnicas convencionais para usar pares para representar sequências e árvores, e exibimos uma linguagem gráfica que ilustra o fechamento de uma maneira vívida.⁷³

2.2.1Representando Sequências

Uma das estruturas úteis que podemos construir com pares é uma sequência — uma coleção ordenada de objetos de dados. Existem, é claro, muitas maneiras de representar sequências em termos de pares. Uma representação particularmente direta é ilustrada na Figura 2.4, onde a sequência 1, 2, 3, 4 é representada como uma cadeia de pares. O car de cada par é o item correspondente na cadeia, e o cdr do par é o próximo par na cadeia. O cdr do par final sinaliza o fim da sequência apontando para um valor distinguido que não é um par, representado em diagramas de caixa e ponteiro como uma linha diagonal e em programas como o valor da variável nil. A sequência inteira é construída por operações cons aninhadas:

(cons 1
          (cons 2
                (cons 3
                      (cons 4 nil))))

Essa sequência de pares, formada por cons aninhados, é chamada de lista, e Scheme fornece uma primitiva chamada list para ajudar na construção de listas.⁷⁴ A sequência acima poderia ser produzida por (list 1 2 3 4). Em geral,

(list ⟨a₁⟩ ⟨a₂⟩ … ⟨aₙ⟩)

é equivalente a

(cons ⟨a₁⟩
          (cons ⟨a₂⟩
                (cons …
                      (cons ⟨aₙ⟩
                            nil)…)))

Os sistemas Lisp convencionalmente imprimem listas imprimindo a sequência de elementos, entre parênteses. Assim, o objeto de dados na Figura 2.4 é impresso como (1 2 3 4):

(define one-through-four (list 1 2 3 4))
    
    one-through-four
    (1 2 3 4)

Cuidado para não confundir a expressão (list 1 2 3 4) com a lista (1 2 3 4), que é o resultado obtido quando a expressão é avaliada. Tentar avaliar a expressão (1 2 3 4) sinalizará um erro quando o interpretador tentar aplicar o procedimento 1 aos argumentos 2, 3, 4.

Podemos pensar em car como selecionando o primeiro item da lista, e em cdr como selecionando a sublista consistindo de todos os itens, exceto o primeiro. Aplicações aninhadas de car e cdr podem ser usadas para extrair o segundo, terceiro e itens subsequentes na lista.⁷⁵ O construtor cons faz uma lista como a original, mas com um item adicional no início.

(car one-through-four)
    1
    
    (cdr one-through-four)
    (2 3 4)
    
    (car (cdr one-through-four))
    2
    
    (cons 10 one-through-four)
    (10 1 2 3 4)
    
    (cons 5 one-through-four)
    (5 1 2 3 4)

O valor de nil, usado para terminar a cadeia de pares, pode ser pensado como uma sequência de nenhum elemento, a lista vazia. A palavra nil é uma contração da palavra latina nihil, que significa "nada".⁷⁶

Operações com Listas

O uso de pares para representar sequências de elementos como listas é acompanhado por técnicas convencionais de programação para manipular listas, "descendo" sucessivamente as listas com cdr. Por exemplo, o procedimento list-ref toma como argumentos uma lista e um número $n$ e retorna o $n^{\text{th}}$ item da lista. É costume numerar os elementos da lista começando com 0. O método para calcular list-ref é o seguinte:

• Para $n=0$, list-ref deve retornar o car da lista.
• Caso contrário, list-ref deve retornar o $(n-<!--\; -\; -->1)$-ésimo item do cdr da lista.

(define (list-ref items n)
      (if (= n 0)
          (car items)
          (list-ref (cdr items) 
                    (- n 1))))
    
    (define squares 
      (list 1 4 9 16 25))
    
    (list-ref squares 3)
    16

Muitas vezes "descemos" a lista inteira. Para ajudar nisso, Scheme inclui um predicado primitivo null?, que testa se seu argumento é a lista vazia. O procedimento length, que retorna o número de itens em uma lista, ilustra esse padrão típico de uso:

(define (length items)
      (if (null? items)
          0
          (+ 1 (length (cdr items)))))
    
    (define odds
      (list 1 3 5 7))
    
    (length odds)
    4

O procedimento length implementa um plano recursivo simples. O passo de redução é:

• O length de qualquer lista é 1 mais o length do cdr da lista.

Isso é aplicado sucessivamente até chegarmos ao caso base:

• O length da lista vazia é 0.

Também poderíamos calcular length em um estilo iterativo:

(define (length items)
      (define (length-iter a count)
        (if (null? a)
            count
            (length-iter (cdr a) 
                         (+ 1 count))))
      (length-iter items 0))

Outra técnica convencional de programação é "construir" uma lista de respostas enquanto "descemos" uma lista, como no procedimento append, que toma duas listas como argumentos e combina seus elementos para fazer uma nova lista:

(append squares odds)
    (1 4 9 16 25 1 3 5 7)
    
    (append odds squares)
    (1 3 5 7 1 4 9 16 25)

Append também é implementado usando um plano recursivo. Para append as listas list1 e list2, faça o seguinte:

• Se list1 é a lista vazia, então o resultado é apenas list2.
• Caso contrário, append o cdr de list1 e list2, e cons o car de list1 no resultado:

(define (append list1 list2)
      (if (null? list1)
          list2
          (cons (car list1) 
                (append (cdr list1) 
                        list2))))

Exercício 2.17: Defina um procedimento last-pair que retorna a lista que contém apenas o último elemento de uma lista dada (não vazia):

(last-pair (list 23 72 149 34))
    (34)

Exercício 2.18: Defina um procedimento reverse que toma uma lista como argumento e retorna uma lista dos mesmos elementos em ordem inversa:

(reverse (list 1 4 9 16 25))
    (25 16 9 4 1)

Exercício 2.19: Considere o programa de contagem de moedas de 1.2.2. Seria bom poder facilmente mudar a moeda usada pelo programa, para que pudéssemos calcular o número de maneiras de trocar uma libra britânica, por exemplo. Como o programa está escrito, o conhecimento da moeda está parcialmente no procedimento first-denomination e parcialmente no procedimento count-change (que sabe que há cinco tipos de moedas dos EUA). Seria melhor poder fornecer uma lista de moedas a serem usadas para fazer a troca.

Queremos reescrever o procedimento cc para que seu segundo argumento seja uma lista dos valores das moedas a serem usadas, em vez de um inteiro especificando quais moedas usar. Poderíamos então ter listas que definem cada tipo de moeda:

(define us-coins 
      (list 50 25 10 5 1))
    
    (define uk-coins 
      (list 100 50 20 10 5 2 1 0.5))

Poderíamos então chamar cc da seguinte forma:

(cc 100 us-coins)
    292

Para fazer isso, será necessário mudar o programa cc um pouco. Ele ainda terá a mesma forma, mas acessará seu segundo argumento de forma diferente, como segue:

(define (cc amount coin-values)
      (cond ((= amount 0) 
             1)
            ((or (< amount 0) 
                 (no-more? coin-values)) 
             0)
            (else
             (+ (cc 
                 amount
                 (except-first-denomination 
                  coin-values))
                (cc 
                 (- amount
                    (first-denomination 
                     coin-values))
                 coin-values)))))

Defina os procedimentos first-denomination, except-first-denomination e no-more? em termos de operações primitivas sobre estruturas de listas. A ordem da lista coin-values afeta a resposta produzida por cc? Por que ou por que não?

Exercício 2.20: Os procedimentos +, * e list tomam um número arbitrário de argumentos. Uma maneira de definir tais procedimentos é usar define com notação de cauda pontilhada. Em uma definição de procedimento, uma lista de parâmetros que tem um ponto antes do último nome do parâmetro indica que, quando o procedimento é chamado, os parâmetros iniciais (se houver) terão como valores os argumentos iniciais, como de costume, mas o valor do parâmetro final será uma lista de quaisquer argumentos restantes. Por exemplo, dada a definição

(define (f x y . z) ⟨body⟩)

o procedimento f pode ser chamado com dois ou mais argumentos. Se avaliarmos

(f 1 2 3 4 5 6)

então, no corpo de f, x será 1, y será 2 e z será a lista (3 4 5 6). Dada a definição

(define (g . w) ⟨body⟩)

o procedimento g pode ser chamado com zero ou mais argumentos. Se avaliarmos

(g 1 2 3 4 5 6)

então, no corpo de g, w será a lista (1 2 3 4 5 6).⁷⁷

Use essa notação para escrever um procedimento same-parity que toma um ou mais inteiros e retorna uma lista de todos os argumentos que têm a mesma paridade (par ou ímpar) que o primeiro argumento. Por exemplo,

(same-parity 1 2 3 4 5 6 7)
    (1 3 5 7)
    
    (same-parity 2 3 4 5 6 7)
    (2 4 6)

Mapeando sobre listas

Uma operação extremamente útil é aplicar alguma transformação a cada elemento em uma lista e gerar a lista de resultados. Por exemplo, o seguinte procedimento escala cada número em uma lista por um fator dado:

(define (scale-list items factor)
      (if (null? items)
          nil
          (cons (* (car items) factor)
                (scale-list (cdr items) 
                            factor))))
    
    (scale-list (list 1 2 3 4 5) 10)
    (10 20 30 40 50)

Podemos abstrair essa ideia geral e capturá-la como um padrão comum expresso como um procedimento de ordem superior, assim como em 1.3. O procedimento de ordem superior aqui é chamado map. Map toma como argumentos um procedimento de um argumento e uma lista, e retorna uma lista dos resultados produzidos pela aplicação do procedimento a cada elemento na lista:⁷⁸

(define (map proc items)
      (if (null? items)
          nil
          (cons (proc (car items))
                (map proc (cdr items)))))
    
    (map abs (list -10 2.5 -11.6 17))
    (10 2.5 11.6 17)
    
    (map (lambda (x) (* x x)) (list 1 2 3 4))
    (1 4 9 16)

Agora podemos dar uma nova definição de scale-list em termos de map:

(define (scale-list items factor)
      (map (lambda (x) (* x factor))
           items))

Map é uma construção importante, não apenas porque captura um padrão comum, mas porque estabelece um nível mais alto de abstração ao lidar com listas. Na definição original de scale-list, a estrutura recursiva do programa chama a atenção para o processamento elemento por elemento da lista. Definir scale-list em termos de map suprime esse nível de detalhe e enfatiza que a escala transforma uma lista de elementos em uma lista de resultados. A diferença entre as duas definições não é que o computador está realizando um processo diferente (não está), mas que pensamos sobre o processo de maneira diferente. Efetivamente, map ajuda a estabelecer uma barreira de abstração que isola a implementação de procedimentos que transformam listas dos detalhes de como os elementos da lista são extraídos e combinados. Como as barreiras mostradas na Figura 2.1, essa abstração nos dá a flexibilidade de mudar os detalhes de baixo nível de como as sequências são implementadas, enquanto preserva o quadro conceitual de operações que transformam sequências em sequências. A seção 2.2.3 expande esse uso de sequências como um quadro para organizar programas.

Exercício 2.21: O procedimento square-list toma uma lista de números como argumento e retorna uma lista dos quadrados desses números.

(square-list (list 1 2 3 4))
    (1 4 9 16)

Aqui estão duas definições diferentes de square-list. Complete ambas preenchendo as expressões faltantes:

(define (square-list items)
      (if (null? items)
          nil
          (cons ⟨??⟩ ⟨??⟩)))
    
    (define (square-list items)
      (map ⟨??⟩ ⟨??⟩))

Exercício 2.22: Louis Reasoner tenta reescrever o primeiro procedimento square-list do Exercício 2.21 para que ele evolua um processo iterativo:

(define (square-list items)
      (define (iter things answer)
        (if (null? things)
            answer
            (iter (cdr things)
                  (cons (square (car things))
                        answer))))
      (iter items nil))

Infelizmente, definir square-list dessa forma produz a lista de respostas na ordem inversa da desejada. Por quê?

Louis então tenta corrigir seu bug trocando os argumentos para cons:

(define (square-list items)
      (define (iter things answer)
        (if (null? things)
            answer
            (iter (cdr things)
                  (cons answer
                        (square 
                         (car things))))))
      (iter items nil))

Isso também não funciona. Explique.

Exercício 2.23: O procedimento for-each é semelhante a map. Ele toma como argumentos um procedimento e uma lista de elementos. No entanto, em vez de formar uma lista dos resultados, for-each apenas aplica o procedimento a cada um dos elementos, da esquerda para a direita. Os valores retornados pela aplicação do procedimento aos elementos não são usados — for-each é usado com procedimentos que realizam uma ação, como imprimir. Por exemplo,

(for-each 
     (lambda (x) (newline) (display x))
     (list 57 321 88))
    
    57
    321
    88

O valor retornado pela chamada a for-each (não ilustrado acima) pode ser algo arbitrário, como verdadeiro. Dê uma implementação de for-each.

2.2.2Estruturas Hierárquicas

A representação de sequências em termos de listas generaliza naturalmente para representar sequências cujos elementos podem ser sequências. Por exemplo, podemos considerar o objeto ((1 2) 3 4) construído por

(cons (list 1 2) (list 3 4))

como uma lista de três itens, o primeiro dos quais é uma lista, (1 2). De fato, isso é sugerido pela forma na qual o resultado é impresso pelo interpretador. A Figura 2.5 mostra a representação dessa estrutura em termos de pares.

Outra maneira de pensar em sequências cujos elementos são sequências é como árvores. Os elementos da sequência são os ramos da árvore, e os elementos que são eles mesmos sequências são subárvores. A Figura 2.6 mostra a estrutura na Figura 2.5 vista como uma árvore.

A recursão é uma ferramenta natural para lidar com estruturas de árvores, já que muitas vezes podemos reduzir operações em árvores a operações em seus ramos, que por sua vez se reduzem a operações nos ramos dos ramos, e assim por diante, até chegarmos às folhas da árvore. Como exemplo, compare o procedimento length de 2.2.1 com o procedimento count-leaves, que retorna o número total de folhas de uma árvore:

(define x (cons (list 1 2) (list 3 4)))

(length x)
    3

(count-leaves x)
    4
    
    (list x x)
    (((1 2) 3 4) ((1 2) 3 4))
    
    (length (list x x))
    2
    
    (count-leaves (list x x))
    8

Para implementar count-leaves, lembre-se do plano recursivo para calcular length:

• O length de uma lista x é 1 mais o length do cdr de x.
• O length da lista vazia é 0.

Count-leaves é semelhante. O valor para a lista vazia é o mesmo:

• O count-leaves da lista vazia é 0.

Mas no passo de redução, onde retiramos o car da lista, devemos levar em conta que o car pode ser uma árvore cujas folhas precisamos contar. Assim, o passo de redução apropriado é

• O count-leaves de uma árvore x é count-leaves do car de x mais count-leaves do cdr de x.

Finalmente, ao tirar cars, chegamos a folhas reais, então precisamos de outro caso base:

• O count-leaves de uma folha é 1.

Para ajudar a escrever procedimentos recursivos em árvores, Scheme fornece o predicado primitivo pair?, que testa se seu argumento é um par. Aqui está o procedimento completo:⁷⁹

(define (count-leaves x)
      (cond ((null? x) 0)
            ((not (pair? x)) 1)
            (else (+ (count-leaves (car x))
                     (count-leaves (cdr x))))))

Exercício 2.24: Suponha que avaliamos a expressão (list 1 (list 2 (list 3 4))). Dê o resultado impresso pelo interpretador, a estrutura correspondente de caixa e ponteiro, e a interpretação disso como uma árvore (como na Figura 2.6).

Exercício 2.25: Dê combinações de cars e cdrs que selecionarão 7 de cada uma das seguintes listas:

(1 3 (5 7) 9)
    ((7))
    (1 (2 (3 (4 (5 (6 7))))))

Exercício 2.26: Suponha que definimos x e y como duas listas:

(define x (list 1 2 3))
    (define y (list 4 5 6))

Qual resultado é impresso pelo interpretador em resposta à avaliação de cada uma das seguintes expressões:

(append x y)
    (cons x y)
    (list x y)

Exercício 2.27: Modifique seu procedimento reverse do Exercício 2.18 para produzir um procedimento deep-reverse que toma uma lista como argumento e retorna como seu valor a lista com seus elementos invertidos e com todas as sublistas invertidas também. Por exemplo,

(define x 
      (list (list 1 2) (list 3 4)))
    
    x
    ((1 2) (3 4))
    
    (reverse x)
    ((3 4) (1 2))
    
    (deep-reverse x)
    ((4 3) (2 1))

Exercício 2.28: Escreva um procedimento fringe que toma como argumento uma árvore (representada como uma lista) e retorna uma lista cujos elementos são todas as folhas da árvore arranjadas da esquerda para a direita. Por exemplo,

(define x 
      (list (list 1 2) (list 3 4)))
    
    (fringe x)
    (1 2 3 4)
    
    (fringe (list x x))
    (1 2 3 4 1 2 3 4)

Exercício 2.29: Um móvel binário consiste em dois ramos, um ramo esquerdo e um ramo direito. Cada ramo é uma haste de um certo comprimento, da qual pende ou um peso ou outro móvel binário. Podemos representar um móvel binário usando dados compostos, construindo-o a partir de dois ramos (por exemplo, usando list):

(define (make-mobile left right)
      (list left right))

Um ramo é construído a partir de um length (que deve ser um número) junto com uma structure, que pode ser um número (representando um peso simples) ou outro móvel:

(define (make-branch length structure)
      (list length structure))

1. Escreva os seletores correspondentes left-branch e right-branch, que retornam os ramos de um móvel, e branch-length e branch-structure, que retornam os componentes de um ramo.
2. Usando seus seletores, defina um procedimento total-weight que retorna o peso total de um móvel.
3. Um móvel é dito equilibrado se o torque aplicado por seu ramo superior esquerdo é igual ao torque aplicado por seu ramo superior direito (ou seja, se o comprimento da haste esquerda multiplicado pelo peso pendurado nessa haste é igual ao produto correspondente para o lado direito) e se cada um dos submóveis pendurados em seus ramos é equilibrado. Projete um predicado que testa se um móvel binário é equilibrado.
4. Suponha que mudamos a representação de móveis para que os construtores sejam

   (define (make-mobile left right)
         (cons left right))
       
       (define (make-branch length structure)
         (cons length structure))

   Quanto você precisa mudar seus programas para se converter para a nova representação?

Mapeando sobre árvores

Assim como map é uma abstração poderosa para lidar com sequências, map junto com recursão é uma abstração poderosa para lidar com árvores. Por exemplo, o procedimento scale-tree, análogo ao scale-list de 2.2.1, toma como argumentos um fator numérico e uma árvore cujas folhas são números. Ele retorna uma árvore da mesma forma, onde cada número é multiplicado pelo fator. O plano recursivo para scale-tree é semelhante ao de count-leaves:

(define (scale-tree tree factor)
      (cond ((null? tree) nil)
            ((not (pair? tree)) 
             (* tree factor))
            (else
             (cons (scale-tree (car tree) 
                               factor)
                   (scale-tree (cdr tree) 
                               factor)))))
    
    (scale-tree (list 1 
                      (list 2 (list 3 4) 5) 
                      (list 6 7))
                10)
    (10 (20 (30 40) 50) (60 70))

Outra maneira de implementar scale-tree é tratar a árvore como uma sequência de subárvores e usar map. Mapeamos sobre a sequência, escalando cada subárvore por sua vez, e retornamos a lista de resultados. No caso base, onde a árvore é uma folha, simplesmente multiplicamos pelo fator:

(define (scale-tree tree factor)
      (map (lambda (sub-tree)
             (if (pair? sub-tree)
                 (scale-tree sub-tree factor)
                 (* sub-tree factor)))
           tree))

Muitas operações em árvores podem ser implementadas por combinações semelhantes de operações de sequência e recursão.

Exercício 2.30: Defina um procedimento square-tree análogo ao procedimento square-list do Exercício 2.21. Ou seja, square-tree deve se comportar da seguinte forma:

(square-tree
     (list 1
           (list 2 (list 3 4) 5)
           (list 6 7)))
    (1 (4 (9 16) 25) (36 49))

Defina square-tree tanto diretamente (ou seja, sem usar nenhum procedimento de ordem superior) quanto usando map e recursão.

Exercício 2.31: Abstraia sua resposta ao Exercício 2.30 para produzir um procedimento tree-map com a propriedade de que square-tree poderia ser definido como

(define (square-tree tree) 
      (tree-map square tree))

Exercício 2.32: Podemos representar um conjunto como uma lista de elementos distintos, e podemos representar o conjunto de todos os subconjuntos do conjunto como uma lista de listas. Por exemplo, se o conjunto é (1 2 3), então o conjunto de todos os subconjuntos é (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete a seguinte definição de um procedimento que gera o conjunto de subconjuntos de um conjunto e dê uma explicação clara de por que ele funciona:

(define (subsets s)
      (if (null? s)
          (list nil)
          (let ((rest (subsets (cdr s))))
            (append rest (map ⟨??⟩ rest)))))

2.2.3Sequências como Interfaces Convencionais

No trabalho com dados compostos, enfatizamos como a abstração de dados nos permite projetar programas sem nos envolvermos nos detalhes das representações de dados, e como a abstração preserva para nós a flexibilidade de experimentar com representações alternativas. Nesta seção, introduzimos outro princípio poderoso de design para trabalhar com estruturas de dados — o uso de interfaces convencionais.

Em 1.3, vimos como abstrações de programas, implementadas como procedimentos de ordem superior, podem capturar padrões comuns em programas que lidam com dados numéricos. Nossa capacidade de formular operações análogas para trabalhar com dados compostos depende crucialmente do estilo em que manipulamos nossas estruturas de dados. Considere, por exemplo, o seguinte procedimento, análogo ao procedimento count-leaves de 2.2.2, que toma uma árvore como argumento e calcula a soma dos quadrados das folhas que são ímpares:

(define (sum-odd-squares tree)
      (cond ((null? tree) 0)
            ((not (pair? tree))
             (if (odd? tree) (square tree) 0))
            (else (+ (sum-odd-squares 
                      (car tree))
                     (sum-odd-squares 
                      (cdr tree))))))

Na superfície, este procedimento é muito diferente do seguinte, que constrói uma lista de todos os números de Fibonacci $\text{Fib}(k)$, onde $k$ é menor ou igual a um dado inteiro $n$:

(define (even-fibs n)
      (define (next k)
        (if (> k n)
            nil
            (let ((f (fib k)))
              (if (even? f)
                  (cons f (next (+ k 1)))
                  (next (+ k 1))))))
      (next 0))

Apesar do fato de que esses dois procedimentos são estruturalmente muito diferentes, uma descrição mais abstrata das duas computações revela uma grande semelhança. O primeiro programa

• enumera as folhas de uma árvore;
• filtra-as, selecionando as ímpares;
• eleva ao quadrado cada uma das selecionadas; e
• acumula os resultados usando +, começando com 0.

O segundo programa

• enumera os inteiros de 0 a $n$;
• calcula o número de Fibonacci para cada inteiro;
• filtra-os, selecionando os pares; e
• acumula os resultados usando cons, começando com a lista vazia.

Um engenheiro de processamento de sinais acharia natural conceituar esses processos em termos de sinais fluindo através de uma cascata de estágios, cada um dos quais implementa parte do plano do programa, como mostrado na Figura 2.7. No sum-odd-squares, começamos com um enumerador, que gera um "sinal" consistindo nas folhas de uma árvore dada. Esse sinal é passado por um filtro, que elimina todos os elementos exceto os ímpares. O sinal resultante é então passado por um map, que é um "transdutor" que aplica o procedimento square a cada elemento. A saída do map é então alimentada para um acumulador, que combina os elementos usando +, começando de um 0 inicial. O plano para even-fibs é análogo.

Infelizmente, as duas definições de procedimentos acima não exibem essa estrutura de fluxo de sinal. Por exemplo, se examinarmos o procedimento sum-odd-squares, descobrimos que a enumeração é implementada parcialmente pelos testes null? e pair? e parcialmente pela estrutura recursiva da árvore do procedimento. Da mesma forma, a acumulação é encontrada parcialmente nos testes e parcialmente na adição usada na recursão. Em geral, não há partes distintas de qualquer procedimento que correspondam aos elementos na descrição do fluxo de sinal. Nossos dois procedimentos decompõem as computações de uma maneira diferente, espalhando a enumeração pelo programa e misturando-a com o map, o filtro e a acumulação. Se pudéssemos organizar nossos programas para tornar a estrutura de fluxo de sinal manifesta nos procedimentos que escrevemos, isso aumentaria a clareza conceitual do código resultante.

Operações de Sequência

A chave para organizar programas de forma a refletir mais claramente a estrutura de fluxo de sinal é concentrar-se nos "sinais" que fluem de um estágio no processo para o próximo. Se representarmos esses sinais como listas, então podemos usar operações de lista para implementar o processamento em cada um dos estágios. Por exemplo, podemos implementar os estágios de mapeamento dos diagramas de fluxo de sinal usando o procedimento map de 2.2.1:

(map square (list 1 2 3 4 5))
(1 4 9 16 25)

Filtrar uma sequência para selecionar apenas os elementos que satisfazem um predicado dado é realizado por:

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate 
                       (cdr sequence))))
        (else  (filter predicate 
                       (cdr sequence)))))

Por exemplo,

(filter odd? (list 1 2 3 4 5))
(1 3 5)

Acumulações podem ser implementadas por:

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op 
                      initial 
                      (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))
15
(accumulate * 1 (list 1 2 3 4 5))
120
(accumulate cons nil (list 1 2 3 4 5))
(1 2 3 4 5)

Tudo o que resta para implementar diagramas de fluxo de sinal é enumerar a sequência de elementos a serem processados. Para even-fibs, precisamos gerar a sequência de inteiros em um determinado intervalo, o que podemos fazer da seguinte forma:

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low 
            (enumerate-interval 
             (+ low 1) 
             high))))

(enumerate-interval 2 7)
(2 3 4 5 6 7)

Para enumerar as folhas de uma árvore, podemos usar⁸⁰:

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append 
               (enumerate-tree (car tree))
               (enumerate-tree (cdr tree))))))

(enumerate-tree (list 1 (list 2 (list 3 4)) 5))
(1 2 3 4 5)

Agora podemos reformular sum-odd-squares e even-fibs como nos diagramas de fluxo de sinal. Para sum-odd-squares, enumeramos a sequência de folhas da árvore, filtramos para manter apenas os números ímpares na sequência, elevamos ao quadrado cada elemento e somamos os resultados:

(define (sum-odd-squares tree)
  (accumulate 
   +
   0
   (map square
        (filter odd?
                (enumerate-tree tree)))))

Para even-fibs, enumeramos os inteiros de 0 a $n$, geramos o número de Fibonacci para cada um desses inteiros, filtramos a sequência resultante para manter apenas os elementos pares e acumulamos os resultados em uma lista:

(define (even-fibs n)
  (accumulate 
   cons
   nil
   (filter even?
           (map fib
                (enumerate-interval 0 n)))))

O valor de expressar programas como operações de sequência é que isso nos ajuda a fazer designs de programas que são modulares, ou seja, designs que são construídos combinando peças relativamente independentes. Podemos incentivar o design modular fornecendo uma biblioteca de componentes padrão junto com uma interface convencional para conectar os componentes de maneiras flexíveis.

A construção modular é uma estratégia poderosa para controlar a complexidade no design de engenharia. Em aplicações reais de processamento de sinais, por exemplo, os designers regularmente constroem sistemas por cascateamento de elementos selecionados de famílias padronizadas de filtros e transdutores. Da mesma forma, as operações de sequência fornecem uma biblioteca de elementos de programa padrão que podemos misturar e combinar. Por exemplo, podemos reutilizar peças dos procedimentos sum-odd-squares e even-fibs em um programa que constrói uma lista dos quadrados dos primeiros $n+1$ números de Fibonacci:

(define (list-fib-squares n)
  (accumulate 
   cons
   nil
   (map square
        (map fib
             (enumerate-interval 0 n)))))

(list-fib-squares 10)
(0 1 1 4 9 25 64 169 441 1156 3025)

Podemos rearranjar as peças e usá-las para calcular o produto dos quadrados dos inteiros ímpares em uma sequência:

(define 
  (product-of-squares-of-odd-elements
   sequence)
  (accumulate 
   *
   1
   (map square (filter odd? sequence))))

(product-of-squares-of-odd-elements 
 (list 1 2 3 4 5))
225

Também podemos formular aplicações convencionais de processamento de dados em termos de operações de sequência. Suponha que temos uma sequência de registros de pessoal e queremos encontrar o salário do programador mais bem pago. Suponha que temos um seletor salary que retorna o salário de um registro, e um predicado programmer? que testa se um registro é para um programador. Então podemos escrever:

(define 
  (salary-of-highest-paid-programmer
   records)
  (accumulate 
   max
   0
   (map salary
        (filter programmer? records))))

Esses exemplos dão apenas uma ideia da vasta gama de operações que podem ser expressas como operações de sequência.⁸¹

Sequências, implementadas aqui como listas, servem como uma interface convencional que nos permite combinar módulos de processamento. Além disso, quando representamos estruturas uniformemente como sequências, temos localizado as dependências de estrutura de dados em nossos programas para um pequeno número de operações de sequência. Ao mudar essas, podemos experimentar com representações alternativas de sequências, enquanto deixamos o design geral de nossos programas intacto. Vamos explorar essa capacidade em 3.5, quando generalizarmos o paradigma de processamento de sequências para admitir sequências infinitas.

Exercício 2.33: Preencha as expressões faltantes para completar as seguintes definições de algumas operações básicas de manipulação de listas como acumulações:

(define (map p sequence)
  (accumulate (lambda (x y) ⟨??⟩) 
              nil sequence))

(define (append seq1 seq2)
  (accumulate cons ⟨??⟩ ⟨??⟩))

(define (length sequence)
  (accumulate ⟨??⟩ 0 sequence))

Exercício 2.34: Avaliar um polinômio em $x$ em um dado valor de $x$ pode ser formulado como uma acumulação. Avaliamos o polinômio $$a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$$ usando um algoritmo bem conhecido chamado Regra de Horner, que estrutura a computação como $$(\dots (a_{n}x+a_{n-1})x+\cdots +a_1)x+a_0.$$ Em outras palavras, começamos com $a_n$, multiplicamos por $x$, adicionamos $a_{n-1}$, multiplicamos por $x$, e assim por diante, até chegarmos a $a_0$.⁸²

Preencha o seguinte modelo para produzir um procedimento que avalia um polinômio usando a Regra de Horner. Suponha que os coeficientes do polinômio estão arranjados em uma sequência, de $a_0$ até $a_n$.

(define 
  (horner-eval x coefficient-sequence)
  (accumulate 
   (lambda (this-coeff higher-terms)
     ⟨??⟩)
   0
   coefficient-sequence))

Por exemplo, para calcular $1+3x+5x^3+x^5$ em $x=2$ você avaliaria:

(horner-eval 2 (list 1 3 0 5 0 1))

Exercício 2.35: Redefina count-leaves de 2.2.2 como uma acumulação:

(define (count-leaves t)
  (accumulate ⟨??⟩ ⟨??⟩ (map ⟨??⟩ ⟨??⟩)))

Exercício 2.36: O procedimento accumulate-n é similar a accumulate, exceto que ele toma como seu terceiro argumento uma sequência de sequências, que são todas assumidas como tendo o mesmo número de elementos. Ele aplica o procedimento de acumulação designado para combinar todos os primeiros elementos das sequências, todos os segundos elementos das sequências, e assim por diante, e retorna uma sequência dos resultados. Por exemplo, se s é uma sequência contendo quatro sequências, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), então o valor de (accumulate-n + 0 s) deve ser a sequência (22 26 30). Preencha as expressões faltantes na seguinte definição de accumulate-n:

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init ⟨??⟩)
            (accumulate-n op init ⟨??⟩))))

Exercício 2.37: Suponha que representamos vetores v = $(v_i)$ como sequências de números, e matrizes m = $(m_{ij})$ como sequências de vetores (as linhas da matriz). Por exemplo, a matriz $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 5& 6& 6\\ 6& 7& 8& 9\end{array}\right)$$ é representada como a sequência ((1 2 3 4) (4 5 6 6) (6 7 8 9)). Com essa representação, podemos usar operações de sequência para expressar de forma concisa as operações básicas de matriz e vetor. Essas operações (que são descritas em qualquer livro de álgebra linear) são as seguintes:

$$\begin{array}{rl}\text{(dot-product v w)}& \text{retorna a soma}{\mathrm{\Sigma }}_i{v}_i{w}_i;\\ \text{(matrix-*-vector m v)}& \text{retorna o vetor}\mathbf{t},\\ & \text{onde}{t}_i={\mathrm{\Sigma }}_j{m}_{ij}{v}_j;\\ \text{(matrix-*-matrix m n)}& \text{retorna a matriz}\mathbf{p},\\ & \text{onde}{p}_{ij}={\mathrm{\Sigma }}_k{m}_{ik}{n}_{kj};\\ \text{(transpose m)}& \text{retorna a matriz}\mathbf{n},\\ & \text{onde}{n}_{ij}=m_{ji}.\end{array}$$

Podemos definir o produto escalar como⁸³:

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

Preencha as expressões faltantes nos seguintes procedimentos para computar as outras operações de matriz. (O procedimento accumulate-n é definido em Exercício 2.36.)

(define (matrix-*-vector m v)
  (map ⟨??⟩ m))

(define (transpose mat)
  (accumulate-n ⟨??⟩ ⟨??⟩ mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map ⟨??⟩ m)))

Exercício 2.38: O procedimento accumulate também é conhecido como fold-right, porque combina o primeiro elemento da sequência com o resultado de combinar todos os elementos à direita. Há também um fold-left, que é similar ao fold-right, exceto que ele combina elementos trabalhando na direção oposta:

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

Quais são os valores de:

(fold-right / 1 (list 1 2 3))
(fold-left  / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left  list nil (list 1 2 3))

Dê uma propriedade que op deve satisfazer para garantir que fold-right e fold-left produzirão os mesmos valores para qualquer sequência.

Exercício 2.39: Complete as seguintes definições de reverse (Exercício 2.18) em termos de fold-right e fold-left de Exercício 2.38:

(define (reverse sequence)
  (fold-right 
   (lambda (x y) ⟨??⟩) nil sequence))

(define (reverse sequence)
  (fold-left 
   (lambda (x y) ⟨??⟩) nil sequence))

Mapeamentos Aninhados

Podemos estender o paradigma de sequência para incluir muitas computações que são comumente expressas usando loops aninhados.⁸⁴ Considere este problema: Dado um inteiro positivo $n$, encontre todos os pares ordenados de inteiros positivos distintos $i$ e $j$, onde $1\le j<i\le n$, tal que $i+j$ é primo. Por exemplo, se $n$ é 6, então os pares são os seguintes:

Uma maneira natural de organizar essa computação é gerar a sequência de todos os pares ordenados de inteiros positivos menores ou iguais a $n$, filtrar para selecionar aqueles pares cuja soma é prima, e então, para cada par $(i,j)$ que passa pelo filtro, produzir o triplo $(i,j,i+j)$.

Aqui está uma maneira de gerar a sequência de pares: Para cada inteiro $i\le n$, enumeramos os inteiros $j<i$, e para cada $i$ e $j$ geramos o par $(i,j)$. Em termos de operações de sequência, mapeamos ao longo da sequência (enumerate-interval 1 n). Para cada $i$ nessa sequência, mapeamos ao longo da sequência (enumerate-interval 1 (- i 1)). Para cada $j$ nessa última sequência, geramos o par (list i j). Isso nos dá uma sequência de pares para cada $i$. Combinando todas as sequências para todos os $i$ (por acumulação com append) produz a sequência necessária de pares:⁸⁵

(accumulate 
 append
 nil
 (map (lambda (i)
        (map (lambda (j) 
               (list i j))
             (enumerate-interval 
              1 
              (- i 1))))
      (enumerate-interval 1 n)))

A combinação de mapeamento e acumulação com append é tão comum nesse tipo de programa que vamos isolá-la como um procedimento separado:

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

Agora filtre essa sequência de pares para encontrar aqueles cuja soma é prima. O predicado do filtro é chamado para cada elemento da sequência; seu argumento é um par e ele deve extrair os inteiros do par. Assim, o predicado para aplicar a cada elemento na sequência é:

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

Finalmente, gere a sequência de resultados mapeando sobre os pares filtrados usando o seguinte procedimento, que constrói um triplo consistindo dos dois elementos do par junto com sua soma:

(define (make-pair-sum pair)
  (list (car pair) 
        (cadr pair) 
        (+ (car pair) (cadr pair))))

Combinando todos esses passos, obtemos o procedimento completo:

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter 
        prime-sum?
        (flatmap
         (lambda (i)
           (map (lambda (j) 
                  (list i j))
                (enumerate-interval 
                 1 
                 (- i 1))))
         (enumerate-interval 1 n)))))

Mapeamentos aninhados também são úteis para sequências que não enumeram intervalos. Suponha que desejamos gerar todas as permutações de um conjunto $S;$ isto é, todas as maneiras de ordenar os itens no conjunto. Por exemplo, as permutações de $\{1,2,3\}$ são $\{1,2,3\}$, $\{1,3,2\}$, $\{2,1,3\}$, $\{2,3,1\}$, $\{3,1,2\}$, e $\{3,2,1\}$. Aqui está um plano para gerar as permutações de $S$: Para cada item $x$ em $S$, gere recursivamente a sequência de permutações de $S-x$,⁸⁶ e adicione $x$ à frente de cada uma. Isso produz, para cada $x$ em $S$, a sequência de permutações de $S$ que começam com $x$. Combinando essas sequências para todos os $x$ dá todas as permutações de $S$:⁸⁷

(define (permutations s)
  (if (null? s)   ; conjunto vazio?
      (list nil)  ; sequência contendo o conjunto vazio
      (flatmap (lambda (x)
                 (map (lambda (p) 
                        (cons x p))
                      (permutations 
                       (remove x s))))
               s)))

Observe como essa estratégia reduz o problema de gerar permutações de $S$ ao problema de gerar as permutações de conjuntos com menos elementos que $S$. No caso terminal, trabalhamos até a lista vazia, que representa um conjunto sem elementos. Para isso, geramos (list nil), que é uma sequência com um item, ou seja, o conjunto sem elementos. O procedimento remove usado em permutations retorna todos os itens em uma sequência dada, exceto um item dado. Isso pode ser expresso como um simples filtro:

(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

Exercício 2.40: Defina um procedimento unique-pairs que, dado um inteiro $n$, gera a sequência de pares $(i,j)$ com $1\le j<i\le n$. Use unique-pairs para simplificar a definição de prime-sum-pairs dada acima.

Exercício 2.41: Escreva um procedimento para encontrar todos os triplos ordenados de inteiros positivos distintos $i$, $j$, e $k$ menores ou iguais a um dado inteiro $n$ que somam a um dado inteiro $s$.

Exercício 2.42: O "quebra-cabeça das oito rainhas" pergunta como colocar oito rainhas em um tabuleiro de xadrez de forma que nenhuma rainha esteja em cheque de qualquer outra (ou seja, nenhuma duas rainhas estão na mesma linha, coluna ou diagonal). Uma solução possível é mostrada na Figura 2.8. Uma maneira de resolver o quebra-cabeça é trabalhar através do tabuleiro, colocando uma rainha em cada coluna. Uma vez que colocamos $k-1$ rainhas, devemos colocar a $k^{\text{th}}$ rainha em uma posição onde ela não esteja em cheque de nenhuma das rainhas já no tabuleiro. Podemos formular essa abordagem recursivamente: Assuma que já geramos a sequência de todas as maneiras possíveis de colocar $k-1$ rainhas nas primeiras $k-1$ colunas do tabuleiro. Para cada uma dessas maneiras, gere um conjunto estendido de posições colocando uma rainha em cada linha da $k^{\text{th}}$ coluna. Agora filtre essas, mantendo apenas as posições para as quais a rainha na $k^{\text{th}}$ coluna está segura em relação às outras rainhas. Isso produz a sequência de todas as maneiras de colocar $k$ rainhas nas primeiras $k$ colunas. Continuando esse processo, produziremos não apenas uma solução, mas todas as soluções para o quebra-cabeça.

Implementamos essa solução como um procedimento queens, que retorna uma sequência de todas as soluções para o problema de colocar $n$ rainhas em um tabuleiro de xadrez $n\times n$. Queens tem um procedimento interno queen-cols que retorna a sequência de todas as maneiras de colocar rainhas nas primeiras $k$ colunas do tabuleiro.

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) 
           (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position 
                    new-row 
                    k 
                    rest-of-queens))
                 (enumerate-interval 
                  1 
                  board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

Neste procedimento, rest-of-queens é uma maneira de colocar $k-1$ rainhas nas primeiras $k-1$ colunas, e new-row é uma linha proposta na qual colocar a rainha para a $k^{\text{th}}$ coluna. Complete o programa implementando a representação para conjuntos de posições do tabuleiro, incluindo o procedimento adjoin-position, que adiciona uma nova posição de linha-coluna a um conjunto de posições, e empty-board, que representa um conjunto vazio de posições. Você também deve escrever o procedimento safe?, que determina, para um conjunto de posições, se a rainha na $k^{\text{th}}$ coluna está segura em relação às outras. (Note que precisamos apenas verificar se a nova rainha está segura—as outras rainhas já estão garantidamente seguras em relação umas às outras.)

Exercício 2.43: Louis Reasoner está tendo um tempo terrível fazendo Exercício 2.42. Seu procedimento queens parece funcionar, mas roda extremamente devagar. (Louis nunca consegue esperar o suficiente para resolver até mesmo o caso $6\times 6$.) Quando Louis pede ajuda a Eva Lu Ator, ela aponta que ele trocou a ordem dos mapeamentos aninhados no flatmap, escrevendo-o como:

(flatmap
 (lambda (new-row)
   (map (lambda (rest-of-queens)
          (adjoin-position 
           new-row k rest-of-queens))
        (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))

Explique por que essa troca faz o programa rodar devagar. Estime quanto tempo o programa de Louis levará para resolver o quebra-cabeça das oito rainhas, assumindo que o programa em Exercício 2.42 resolve o quebra-cabeça em tempo $T$.

2.2.4Exemplo: Uma Linguagem de Imagens

Esta seção apresenta uma linguagem simples para desenhar imagens que ilustra o poder da abstração de dados e do fechamento, e também explora procedimentos de ordem superior de maneira essencial. A linguagem é projetada para facilitar a experimentação com padrões como os da Figura 2.9, que são compostos de elementos repetidos que são deslocados e escalados.⁸⁸ Nessa linguagem, os objetos de dados sendo combinados são representados como procedimentos em vez de estruturas de lista. Assim como cons, que satisfaz a propriedade de fechamento, nos permitiu construir facilmente estruturas de lista arbitrariamente complicadas, as operações nessa linguagem, que também satisfazem a propriedade de fechamento, nos permitem construir facilmente padrões arbitrariamente complicados.

A linguagem de imagens

Quando começamos nosso estudo de programação em 1.1, enfatizamos a importância de descrever uma linguagem focando nos primitivos da linguagem, seus meios de combinação e seus meios de abstração. Vamos seguir esse framework aqui.

Parte da elegância dessa linguagem de imagens é que há apenas um tipo de elemento, chamado de pintor. Um pintor desenha uma imagem que é deslocada e escalada para caber dentro de um quadro em forma de paralelogramo designado. Por exemplo, há um pintor primitivo que chamaremos de wave que faz um desenho rudimentar, como mostrado na Figura 2.10. A forma real do desenho depende do quadro—todas as quatro imagens na figura 2.10 são produzidas pelo mesmo pintor wave, mas com respeito a quatro quadros diferentes. Pintores podem ser mais elaborados que isso: O pintor primitivo chamado rogers pinta uma imagem do fundador do MIT, William Barton Rogers, como mostrado na Figura 2.11.⁸⁹ As quatro imagens na figura 2.11 são desenhadas com respeito aos mesmos quatro quadros que as imagens wave na figura 2.10.

Para combinar imagens, usamos várias operações que constroem novos pintores a partir de pintores dados. Por exemplo, a operação beside toma dois pintores e produz um novo pintor composto que desenha a imagem do primeiro pintor na metade esquerda do quadro e a imagem do segundo pintor na metade direita do quadro. Da mesma forma, below toma dois pintores e produz um pintor composto que desenha a imagem do primeiro pintor abaixo da imagem do segundo pintor. Algumas operações transformam um único pintor para produzir um novo pintor. Por exemplo, flip-vert toma um pintor e produz um pintor que desenha sua imagem de cabeça para baixo, e flip-horiz produz um pintor que desenha a imagem original do pintor invertida da esquerda para a direita.

Figura 2.12 mostra o desenho de um pintor chamado wave4 que é construído em dois estágios a partir de wave:

(define wave2 (beside wave (flip-vert wave)))
(define wave4 (below wave2 wave2))

Ao construir uma imagem complexa dessa maneira, estamos explorando o fato de que os pintores são fechados sob os meios de combinação da linguagem. O beside ou below de dois pintores é ele mesmo um pintor; portanto, podemos usá-lo como um elemento para fazer pintores mais complexos. Assim como construir estruturas de lista usando cons, o fechamento de nossos dados sob os meios de combinação é crucial para a capacidade de criar estruturas complexas enquanto usa apenas algumas operações.

Uma vez que podemos combinar pintores, gostaríamos de ser capazes de abstrair padrões típicos de combinação de pintores. Vamos implementar as operações de pintor como procedimentos Scheme. Isso significa que não precisamos de um mecanismo especial de abstração na linguagem de imagens: Como os meios de combinação são procedimentos Scheme comuns, temos automaticamente a capacidade de fazer qualquer coisa com operações de pintor que podemos fazer com procedimentos. Por exemplo, podemos abstrair o padrão em wave4 como:

(define (flipped-pairs painter)
  (let ((painter2 
         (beside painter 
                 (flip-vert painter))))
    (below painter2 painter2)))

e definir wave4 como uma instância desse padrão:

(define wave4 (flipped-pairs wave))

Também podemos definir operações recursivas. Aqui está uma que faz pintores se dividirem e ramificarem para a direita, como mostrado na Figura 2.13 e Figura 2.14:

(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter 
                                  (- n 1))))
        (beside painter 
                (below smaller smaller)))))

Podemos produzir padrões balanceados ramificando para cima, bem como para a direita (veja Exercício 2.44, Figura 2.13 e Figura 2.14):

(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-split painter (- n 1)))
            (right (right-split painter 
                                (- n 1))))
        (let ((top-left (beside up up))
              (bottom-right (below right 
                                   right))
              (corner (corner-split painter 
                                    (- n 1))))
          (beside (below painter top-left)
                  (below bottom-right 
                         corner))))))

Ao colocar quatro cópias de um corner-split apropriadamente, obtemos um padrão chamado square-limit, cuja aplicação a wave e rogers é mostrada na Figura 2.9:

(define (square-limit painter n)
  (let ((quarter (corner-split painter n)))
    (let ((half (beside (flip-horiz quarter) 
                        quarter)))
      (below (flip-vert half) half))))

Exercício 2.44: Defina o procedimento up-split usado por corner-split. Ele é similar ao right-split, exceto que ele troca os papéis de below e beside.

Operações de ordem superior

Além de abstrair padrões de combinação de pintores, podemos trabalhar em um nível mais alto, abstraindo padrões de combinação de operações de pintores. Ou seja, podemos ver as operações de pintores como elementos a serem manipulados e podemos escrever meios de combinação para esses elementos — procedimentos que recebem operações de pintores como argumentos e criam novas operações de pintores.

Por exemplo, flipped-pairs e square-limit cada um organiza quatro cópias da imagem de um pintor em um padrão quadrado; eles diferem apenas na forma como orientam as cópias. Uma maneira de abstrair esse padrão de combinação de pintores é com o seguinte procedimento, que recebe quatro operações de pintores de um argumento e produz uma operação de pintor que transforma um pintor dado com essas quatro operações e organiza os resultados em um quadrado. Tl, tr, bl e br são as transformações a serem aplicadas à cópia superior esquerda, à cópia superior direita, à cópia inferior esquerda e à cópia inferior direita, respectivamente.

(define (square-of-four tl tr bl br)
  (lambda (painter)
    (let ((top (beside (tl painter) 
                       (tr painter)))
          (bottom (beside (bl painter) 
                          (br painter))))
      (below bottom top))))

Então, flipped-pairs pode ser definido em termos de square-of-four da seguinte forma:⁹⁰

(define (flipped-pairs painter)
  (let ((combine4 
         (square-of-four identity 
                         flip-vert
                         identity 
                         flip-vert)))
    (combine4 painter)))

e square-limit pode ser expresso como⁹¹

(define (square-limit painter n)
  (let ((combine4 
         (square-of-four flip-horiz 
                         identity
                         rotate180 
                         flip-vert)))
    (combine4 (corner-split painter n))))

Exercício 2.45: Right-split e up-split podem ser expressos como instâncias de uma operação de divisão geral. Defina um procedimento split com a propriedade de que avaliar

(define right-split (split beside below))
(define up-split (split below beside))

produz procedimentos right-split e up-split com os mesmos comportamentos dos já definidos.

Quadros

Antes de podermos mostrar como implementar pintores e seus meios de combinação, devemos primeiro considerar quadros. Um quadro pode ser descrito por três vetores — um vetor de origem e dois vetores de borda. O vetor de origem especifica o deslocamento da origem do quadro em relação a alguma origem absoluta no plano, e os vetores de borda especificam os deslocamentos dos cantos do quadro em relação à sua origem. Se as bordas forem perpendiculares, o quadro será retangular. Caso contrário, o quadro será um paralelogramo mais geral.

Figura 2.15 mostra um quadro e seus vetores associados. De acordo com a abstração de dados, não precisamos ser específicos ainda sobre como os quadros são representados, exceto para dizer que há um construtor make-frame, que recebe três vetores e produz um quadro, e três seletores correspondentes origin-frame, edge1-frame e edge2-frame (veja Exercício 2.47).

Usaremos coordenadas no quadrado unitário $(0\le <!--\; \le \; -->x,y\le <!--\; \le \; -->1)$ para especificar imagens. Com cada quadro, associamos um mapa de coordenadas do quadro, que será usado para deslocar e escalar imagens para caber no quadro. O mapa transforma o quadrado unitário no quadro mapeando o vetor $\mathbf{v}=(x,y)$ para a soma vetorial $$\text{Origin(Frame)}+x\cdot <!--\; \cdot \; -->{\text{Edge}}_1\text{(Frame)}+y\cdot <!--\; \cdot \; -->{\text{Edge}}_2\text{(Frame)}.$$ Por exemplo, (0, 0) é mapeado para a origem do quadro, (1, 1) para o vértice diagonalmente oposto à origem, e (0.5, 0.5) para o centro do quadro. Podemos criar o mapa de coordenadas de um quadro com o seguinte procedimento:⁹²

(define (frame-coord-map frame)
  (lambda (v)
    (add-vect
     (origin-frame frame)
     (add-vect 
      (scale-vect (xcor-vect v)
                  (edge1-frame frame))
      (scale-vect (ycor-vect v)
                  (edge2-frame frame))))))

Observe que aplicar frame-coord-map a um quadro retorna um procedimento que, dado um vetor, retorna um vetor. Se o vetor de argumento estiver no quadrado unitário, o vetor resultante estará no quadro. Por exemplo,

((frame-coord-map a-frame) (make-vect 0 0))

retorna o mesmo vetor que

(origin-frame a-frame)

Exercício 2.46: Um vetor bidimensional $\mathbf{v}$ que vai da origem a um ponto pode ser representado como um par consistindo de uma coordenada $x$ e uma coordenada $y$. Implemente uma abstração de dados para vetores fornecendo um construtor make-vect e seletores correspondentes xcor-vect e ycor-vect. Em termos de seus seletores e construtor, implemente procedimentos add-vect, sub-vect e scale-vect que realizam as operações de adição de vetores, subtração de vetores e multiplicação de um vetor por um escalar: $$\begin{array}{rcl}(x_1,y_1)+(x_2,y_2)& =& (x_1+x_2,y_1+y_2),\\ (x_1,y_1)-<!--\; -\; -->(x_2,y_2)& =& (x_1-<!--\; -\; -->x_2,y_1-<!--\; -\; -->y_2),\\ s\cdot <!--\; \cdot \; -->(x,y)& =& (sx,sy).\end{array}$$

Exercício 2.47: Aqui estão dois possíveis construtores para quadros:

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

Para cada construtor, forneça os seletores apropriados para produzir uma implementação para quadros.

Pintores

Um pintor é representado como um procedimento que, dado um quadro como argumento, desenha uma imagem específica deslocada e escalada para caber no quadro. Ou seja, se p é um pintor e f é um quadro, então produzimos a imagem de p em f chamando p com f como argumento.

Os detalhes de como os pintores primitivos são implementados dependem das características particulares do sistema gráfico e do tipo de imagem a ser desenhada. Por exemplo, suponha que temos um procedimento draw-line que desenha uma linha na tela entre dois pontos especificados. Então podemos criar pintores para desenhos de linhas, como o pintor wave na Figura 2.10, a partir de listas de segmentos de linha da seguinte forma:⁹³

(define (segments->painter segment-list)
  (lambda (frame)
    (for-each
     (lambda (segment)
       (draw-line
        ((frame-coord-map frame) 
         (start-segment segment))
        ((frame-coord-map frame) 
         (end-segment segment))))
     segment-list)))

Os segmentos são dados usando coordenadas com respeito ao quadrado unitário. Para cada segmento na lista, o pintor transforma os pontos finais do segmento com o mapa de coordenadas do quadro e desenha uma linha entre os pontos transformados.

Representar pintores como procedimentos ergue uma poderosa barreira de abstração na linguagem de imagens. Podemos criar e misturar todos os tipos de pintores primitivos, baseados em uma variedade de capacidades gráficas. Os detalhes de sua implementação não importam. Qualquer procedimento pode servir como um pintor, desde que receba um quadro como argumento e desenhe algo escalado para caber no quadro.⁹⁴

Exercício 2.48: Um segmento de linha direcionado no plano pode ser representado como um par de vetores — o vetor que vai da origem ao ponto inicial do segmento, e o vetor que vai da origem ao ponto final do segmento. Use sua representação de vetor do Exercício 2.46 para definir uma representação para segmentos com um construtor make-segment e seletores start-segment e end-segment.

Exercício 2.49: Use segments->painter para definir os seguintes pintores primitivos:

1. O pintor que desenha o contorno do quadro designado.
2. O pintor que desenha um “X” conectando os cantos opostos do quadro.
3. O pintor que desenha uma forma de diamante conectando os pontos médios dos lados do quadro.
4. O pintor wave.

Transformando e combinando pintores

Uma operação em pintores (como flip-vert ou beside) funciona criando um pintor que invoca os pintores originais com respeito a quadros derivados do quadro de argumento. Assim, por exemplo, flip-vert não precisa saber como um pintor funciona para invertê-lo — ele só precisa saber como virar um quadro de cabeça para baixo: O pintor invertido simplesmente usa o pintor original, mas no quadro invertido.

As operações de pintores são baseadas no procedimento transform-painter, que recebe como argumentos um pintor e informações sobre como transformar um quadro e produz um novo pintor. O pintor transformado, quando chamado em um quadro, transforma o quadro e chama o pintor original no quadro transformado. Os argumentos para transform-painter são pontos (representados como vetores) que especificam os cantos do novo quadro: Quando mapeados no quadro, o primeiro ponto especifica a origem do novo quadro e os outros dois especificam as extremidades de seus vetores de borda. Assim, argumentos dentro do quadrado unitário especificam um quadro contido dentro do quadro original.

(define (transform-painter 
         painter origin corner1 corner2)
  (lambda (frame)
    (let ((m (frame-coord-map frame)))
      (let ((new-origin (m origin)))
        (painter (make-frame new-origin
                  (sub-vect (m corner1) 
                            new-origin)
                  (sub-vect (m corner2)
                            new-origin))))))

Aqui está como inverter as imagens do pintor verticalmente:

(define (flip-vert painter)
  (transform-painter 
   painter
   (make-vect 0.0 1.0)   ; nova origem
   (make-vect 1.0 1.0)   ; novo fim de edge1
   (make-vect 0.0 0.0))) ; novo fim de edge2

Usando transform-painter, podemos facilmente definir novas transformações. Por exemplo, podemos definir um pintor que encolhe sua imagem para o quarto superior direito do quadro que lhe é dado:

(define (shrink-to-upper-right painter)
  (transform-painter painter
                     (make-vect 0.5 0.5)
                     (make-vect 1.0 0.5)
                     (make-vect 0.5 1.0)))

Outras transformações giram as imagens no sentido anti-horário em 90 graus⁹⁵

(define (rotate90 painter)
  (transform-painter painter
                     (make-vect 1.0 0.0)
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 0.0)))

ou esmagam as imagens em direção ao centro do quadro:⁹⁶

(define (squash-inwards painter)
  (transform-painter painter
                     (make-vect 0.0 0.0)
                     (make-vect 0.65 0.35)
                     (make-vect 0.35 0.65)))

A transformação de quadros também é a chave para definir meios de combinar dois ou mais pintores. O procedimento beside, por exemplo, recebe dois pintores, transforma-os para pintar nas metades esquerda e direita de um quadro de argumento, respectivamente, e produz um novo pintor composto. Quando o pintor composto recebe um quadro, ele chama o primeiro pintor transformado para pintar na metade esquerda do quadro e chama o segundo pintor transformado para pintar na metade direita do quadro:

(define (beside painter1 painter2)
  (let ((split-point (make-vect 0.5 0.0)))
    (let ((paint-left  (transform-painter 
                        painter1
                        (make-vect 0.0 0.0)
                        split-point
                        (make-vect 0.0 1.0)))
          (paint-right (transform-painter
                        painter2
                        split-point
                        (make-vect 1.0 0.0)
                        (make-vect 0.5 1.0))))
      (lambda (frame)
        (paint-left frame)
        (paint-right frame)))))

Observe como a abstração de dados do pintor, e em particular a representação de pintores como procedimentos, torna beside fácil de implementar. O procedimento beside não precisa saber nada sobre os detalhes dos pintores componentes, exceto que cada pintor desenhará algo em seu quadro designado.

Exercício 2.50: Defina a transformação flip-horiz, que inverte os pintores horizontalmente, e transformações que giram os pintores no sentido anti-horário em 180 graus e 270 graus.

Exercício 2.51: Defina a operação below para pintores. Below recebe dois pintores como argumentos. O pintor resultante, dado um quadro, desenha com o primeiro pintor na parte inferior do quadro e com o segundo pintor na parte superior. Defina below de duas maneiras diferentes — primeiro escrevendo um procedimento que é análogo ao procedimento beside dado acima, e novamente em termos de beside e operações de rotação adequadas (do Exercício 2.50).

Níveis de linguagem para design robusto

A linguagem de imagens exercita algumas das ideias críticas que introduzimos sobre abstração com procedimentos e dados. As abstrações de dados fundamentais, pintores, são implementadas usando representações procedurais, o que permite que a linguagem lide com diferentes capacidades básicas de desenho de maneira uniforme. Os meios de combinação satisfazem a propriedade de fechamento, o que nos permite facilmente construir designs complexos. Finalmente, todas as ferramentas para abstrair procedimentos estão disponíveis para nós para abstrair meios de combinação para pintores.

Também obtivemos um vislumbre de outra ideia crucial sobre linguagens e design de programas. Esta é a abordagem de design estratificado, a noção de que um sistema complexo deve ser estruturado como uma sequência de níveis que são descritos usando uma sequência de linguagens. Cada nível é construído combinando partes que são consideradas primitivas naquele nível, e as partes construídas em cada nível são usadas como primitivas no próximo nível. A linguagem usada em cada nível de um design estratificado tem primitivas, meios de combinação e meios de abstração apropriados para aquele nível de detalhe.

O design estratificado permeia a engenharia de sistemas complexos. Por exemplo, na engenharia de computadores, resistores e transistores são combinados (e descritos usando uma linguagem de circuitos analógicos) para produzir partes como portas AND e portas OR, que formam as primitivas de uma linguagem para design de circuitos digitais.⁹⁷ Essas partes são combinadas para construir processadores, estruturas de barramento e sistemas de memória, que por sua vez são combinados para formar computadores, usando linguagens apropriadas para arquitetura de computadores. Computadores são combinados para formar sistemas distribuídos, usando linguagens apropriadas para descrever interconexões de rede, e assim por diante.

Como um pequeno exemplo de estratificação, nossa linguagem de imagens usa elementos primitivos (pintores primitivos) que são criados usando uma linguagem que especifica pontos e linhas para fornecer as listas de segmentos de linha para segments->painter, ou os detalhes de sombreamento para um pintor como rogers. A maior parte de nossa descrição da linguagem de imagens focou em combinar esses primitivos, usando combinadores geométricos como beside e below. Também trabalhamos em um nível mais alto, considerando beside e below como primitivos a serem manipulados em uma linguagem cujas operações, como square-of-four, capturam padrões comuns de combinação de combinadores geométricos.

O design estratificado ajuda a tornar os programas robustos, ou seja, torna provável que pequenas mudanças em uma especificação exijam mudanças correspondentemente pequenas no programa. Por exemplo, suponha que quiséssemos mudar a imagem baseada em wave mostrada na Figura 2.9. Poderíamos trabalhar no nível mais baixo para mudar a aparência detalhada do elemento wave; poderíamos trabalhar no nível médio para mudar a forma como corner-split replica o wave; poderíamos trabalhar no nível mais alto para mudar como square-limit organiza as quatro cópias do canto. Em geral, cada nível de um design estratificado fornece um vocabulário diferente para expressar as características do sistema, e um tipo diferente de capacidade para mudá-lo.

Exercício 2.52: Faça mudanças no limite quadrado de wave mostrado na Figura 2.9 trabalhando em cada um dos níveis descritos acima. Em particular:

1. Adicione alguns segmentos ao pintor primitivo wave do Exercício 2.49 (para adicionar um sorriso, por exemplo).
2. Mude o padrão construído por corner-split (por exemplo, usando apenas uma cópia das imagens up-split e right-split em vez de duas).
3. Modifique a versão de square-limit que usa square-of-four para montar os cantos em um padrão diferente. (Por exemplo, você pode fazer o grande Sr. Rogers olhar para fora de cada canto do quadrado.)

(cadr ⟨arg⟩) = (car (cdr ⟨arg⟩))

(define f (lambda (x y . z) ⟨body⟩))
(define g (lambda w ⟨body⟩))

(map + 
     (list 1 2 3) 
     (list 40 50 60) 
     (list 700 800 900))
(741 852 963)

(map (lambda (x y) (+ x (* 2 y)))
     (list 1 2 3)
     (list 4 5 6))
(9 12 15)

(define flipped-pairs
  (square-of-four 
   identity flip-vert identity flip-vert))