3.3Modelagem com Dados Mutáveis

O Capítulo 2 tratou de dados compostos como um meio para construir objetos computacionais que têm várias partes, a fim de modelar objetos do mundo real que têm vários aspectos. Naquele capítulo, introduzimos a disciplina de abstração de dados, segundo a qual as estruturas de dados são especificadas em termos de construtores, que criam objetos de dados, e seletores, que acessam as partes de objetos de dados compostos. Mas agora sabemos que há outro aspecto dos dados que o capítulo 2 não abordou. O desejo de modelar sistemas compostos de objetos que têm estado mutável nos leva à necessidade de modificar objetos de dados compostos, além de construí-los e selecionar partes deles. Para modelar objetos compostos com estado mutável, projetaremos abstrações de dados para incluir, além de seletores e construtores, operações chamadas mutadores, que modificam objetos de dados. Por exemplo, modelar um sistema bancário exige que alteremos os saldos das contas. Assim, uma estrutura de dados para representar contas bancárias pode admitir uma operação

(set-balance! ⟨conta⟩ ⟨novo-valor⟩)

que altera o saldo da conta designada para o novo valor designado. Objetos de dados para os quais mutadores são definidos são conhecidos como objetos de dados mutáveis.

O Capítulo 2 introduziu pares como uma "cola" de propósito geral para sintetizar dados compostos. Começamos esta seção definindo mutadores básicos para pares, para que os pares possam servir como blocos de construção para objetos de dados mutáveis. Esses mutadores aumentam muito o poder de representação dos pares, permitindo-nos construir estruturas de dados além das sequências e árvores com as quais trabalhamos em 2.2. Também apresentamos alguns exemplos de simulações em que sistemas complexos são modelados como coleções de objetos com estado local.

3.3.1Estrutura de Lista Mutável

As operações básicas em pares—cons, car e cdr—podem ser usadas para construir estruturas de lista e selecionar partes de estruturas de lista, mas são incapazes de modificar estruturas de lista. O mesmo vale para as operações de lista que usamos até agora, como append e list, já que estas podem ser definidas em termos de cons, car e cdr. Para modificar estruturas de lista, precisamos de novas operações.

Os mutadores primitivos para pares são set-car! e set-cdr!. Set-car! recebe dois argumentos, o primeiro dos quais deve ser um par. Ele modifica este par, substituindo o ponteiro car por um ponteiro para o segundo argumento de set-car!.¹⁴⁴

Como exemplo, suponha que x esteja vinculado à lista ((a b) c d) e y à lista (e f), como ilustrado na Figura 3.12. Avaliar a expressão (set-car! x y) modifica o par ao qual x está vinculado, substituindo seu car pelo valor de y. O resultado da operação é mostrado na Figura 3.13. A estrutura x foi modificada e agora seria impressa como ((e f) c d). Os pares que representam a lista (a b), identificados pelo ponteiro que foi substituído, agora estão destacados da estrutura original.¹⁴⁵

Compare a Figura 3.13 com a Figura 3.14, que ilustra o resultado da execução de (define z (cons y (cdr x))) com x e y vinculados às listas originais da Figura 3.12. A variável z agora está vinculada a um novo par criado pela operação cons; a lista à qual x está vinculada não foi alterada.

A operação set-cdr! é semelhante a set-car!. A única diferença é que o ponteiro cdr do par, em vez do ponteiro car, é substituído. O efeito de executar (set-cdr! x y) nas listas da Figura 3.12 é mostrado na Figura 3.15. Aqui, o ponteiro cdr de x foi substituído pelo ponteiro para (e f). Além disso, a lista (c d), que costumava ser o cdr de x, agora está destacada da estrutura.

Cons constrói novas estruturas de lista criando novos pares, enquanto set-car! e set-cdr! modificam pares existentes. De fato, poderíamos implementar cons em termos dos dois mutadores, junto com um procedimento get-new-pair, que retorna um novo par que não faz parte de nenhuma estrutura de lista existente. Obtemos o novo par, definimos seus ponteiros car e cdr para os objetos designados e retornamos o novo par como o resultado do cons.¹⁴⁶

(define (cons x y)
  (let ((new (get-new-pair)))
    (set-car! new x)
    (set-cdr! new y)
    new))

Exercício 3.12: O seguinte procedimento para anexar listas foi introduzido em 2.2.1:

(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

Append forma uma nova lista sucessivamente consando os elementos de x em y. O procedimento append! é semelhante a append, mas é um mutador em vez de um construtor. Ele anexa as listas juntando-as, modificando o último par de x para que seu cdr seja agora y. (É um erro chamar append! com um x vazio.)

(define (append! x y)
  (set-cdr! (last-pair x) y)
  x)

Aqui, last-pair é um procedimento que retorna o último par em seu argumento:

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

Considere a interação

(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))

z
(a b c d)

(cdr x)
⟨resposta⟩

(define w (append! x y))

w
(a b c d)

(cdr x)
⟨resposta⟩

Quais são as ⟨resposta⟩s ausentes? Desenhe diagramas de caixa e ponteiro para explicar sua resposta.

Exercício 3.13: Considere o seguinte procedimento make-cycle, que usa o procedimento last-pair definido no Exercício 3.12:

(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)

Desenhe um diagrama de caixa e ponteiro que mostre a estrutura z criada por

(define z (make-cycle (list 'a 'b 'c)))

O que acontece se tentarmos calcular (last-pair z)?

Exercício 3.14: O seguinte procedimento é bastante útil, embora obscuro:

(define (mystery x)
  (define (loop x y)
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))
  (loop x '()))

Loop usa a variável "temporária" temp para manter o valor antigo do cdr de x, já que o set-cdr! na próxima linha destrói o cdr. Explique o que mystery faz em geral. Suponha que v seja definido por (define v (list 'a 'b 'c 'd)). Desenhe o diagrama de caixa e ponteiro que representa a lista à qual v está vinculada. Suponha que agora avaliamos (define w (mystery v)). Desenhe diagramas de caixa e ponteiro que mostram as estruturas v e w após avaliar esta expressão. O que seria impresso como os valores de v e w?

Compartilhamento e identidade

Mencionamos em 3.1.3 as questões teóricas de "igualdade" e "mudança" levantadas pela introdução da atribuição. Essas questões surgem na prática quando pares individuais são compartilhados entre diferentes objetos de dados. Por exemplo, considere a estrutura formada por

(define x (list 'a 'b))
(define z1 (cons x x))

Como mostrado na Figura 3.16, z1 é um par cujos car e cdr apontam para o mesmo par x. Esse compartilhamento de x pelo car e cdr de z1 é uma consequência da maneira direta em que cons é implementado. Em geral, usar cons para construir listas resultará em uma estrutura interligada de pares em que muitos pares individuais são compartilhados por muitas estruturas diferentes.

Em contraste com a Figura 3.16, a Figura 3.17 mostra a estrutura criada por

(define z2 
  (cons (list 'a 'b) (list 'a 'b)))

Nesta estrutura, os pares nas duas listas (a b) são distintos, embora os símbolos reais sejam compartilhados.¹⁴⁷

Quando pensamos como uma lista, z1 e z2 representam "a mesma" lista, ((a b) a b). Em geral, o compartilhamento é completamente indetectável se operarmos em listas usando apenas cons, car e cdr. No entanto, se permitirmos mutadores em estruturas de lista, o compartilhamento se torna significativo. Como exemplo da diferença que o compartilhamento pode fazer, considere o seguinte procedimento, que modifica o car da estrutura à qual é aplicado:

(define (set-to-wow! x)
  (set-car! (car x) 'wow)
  x)

Embora z1 e z2 sejam "a mesma" estrutura, aplicar set-to-wow! a eles produz resultados diferentes. Com z1, alterar o car também muda o cdr, porque em z1 o car e o cdr são o mesmo par. Com z2, o car e o cdr são distintos, então set-to-wow! modifica apenas o car:

z1
((a b) a b)

(set-to-wow! z1)
((wow b) wow b)

z2
((a b) a b)

(set-to-wow! z2)
((wow b) a b)

Uma maneira de detectar compartilhamento em estruturas de lista é usar o predicado eq?, que introduzimos em 2.3.1 como uma maneira de testar se dois símbolos são iguais. Mais geralmente, (eq? x y) testa se x e y são o mesmo objeto (ou seja, se x e y são iguais como ponteiros). Assim, com z1 e z2 como definidos na Figura 3.16 e Figura 3.17, (eq? (car z1) (cdr z1)) é verdadeiro e (eq? (car z2) (cdr z2)) é falso.

Como será visto nas seções seguintes, podemos explorar o compartilhamento para estender muito o repertório de estruturas de dados que podem ser representadas por pares. Por outro lado, o compartilhamento também pode ser perigoso, pois modificações feitas em estruturas também afetarão outras estruturas que compartilham as partes modificadas. As operações de mutação set-car! e set-cdr! devem ser usadas com cuidado; a menos que tenhamos um bom entendimento de como nossos objetos de dados são compartilhados, a mutação pode ter resultados imprevistos.¹⁴⁸

Exercício 3.15: Desenhe diagramas de caixa e ponteiro para explicar o efeito de set-to-wow! nas estruturas z1 e z2 acima.

Exercício 3.16: Ben Bitdiddle decide escrever um procedimento para contar o número de pares em qualquer estrutura de lista. "É fácil", ele raciocina. "O número de pares em qualquer estrutura é o número no car mais o número no cdr mais mais um para contar o par atual." Então Ben escreve o seguinte procedimento:

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

Mostre que este procedimento não está correto. Em particular, desenhe diagramas de caixa e ponteiro representando estruturas de lista compostas de exatamente três pares para as quais o procedimento de Ben retornaria 3; retornaria 4; retornaria 7; nunca retornaria.

Exercício 3.17: Projete uma versão correta do procedimento count-pairs do Exercício 3.16 que retorne o número de pares distintos em qualquer estrutura. (Dica: Percorra a estrutura, mantendo uma estrutura de dados auxiliar que é usada para rastrear quais pares já foram contados.)

Exercício 3.18: Escreva um procedimento que examine uma lista e determine se ela contém um ciclo, ou seja, se um programa que tentasse encontrar o fim da lista tomando sucessivos cdrs entraria em um loop infinito. O Exercício 3.13 construiu tais listas.

Exercício 3.19: Refazer o Exercício 3.18 usando um algoritmo que ocupa apenas uma quantidade constante de espaço. (Isso requer uma ideia muito inteligente.)

Mutação é apenas atribuição

Quando introduzimos dados compostos, observamos em 2.1.3 que pares podem ser representados puramente em termos de procedimentos:

(define (cons x y)
  (define (dispatch m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cdr) y)
          (else (error "Operação indefinida: CONS" m))))
  dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

A mesma observação é verdadeira para dados mutáveis. Podemos implementar objetos de dados mutáveis como procedimentos usando atribuição e estado local. Por exemplo, podemos estender a implementação de pares acima para lidar com set-car! e set-cdr! de maneira análoga à forma como implementamos contas bancárias usando make-account em 3.1.1:

(define (cons x y)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (dispatch m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cdr) y)
          ((eq? m 'set-car!) set-x!)
          ((eq? m 'set-cdr!) set-y!)
          (else (error "Operação indefinida: CONS" m))))
  dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

(define (set-car! z new-value)
  ((z 'set-car!) new-value)
  z)

(define (set-cdr! z new-value)
  ((z 'set-cdr!) new-value)
  z)

A atribuição é tudo o que é necessário, teoricamente, para explicar o comportamento de dados mutáveis. Assim que admitimos set! em nossa linguagem, levantamos todas as questões, não apenas de atribuição, mas de dados mutáveis em geral.¹⁴⁹

Exercício 3.20: Desenhe diagramas de ambiente para ilustrar a avaliação da sequência de expressões

(define x (cons 1 2))
(define z (cons x x))

(set-car! (cdr z) 17)

(car x)
17

usando a implementação procedural de pares dada acima. (Compare com o Exercício 3.11.)

3.3.2Representando Filas

Os mutadores set-car! e set-cdr! nos permitem usar pares para construir estruturas de dados que não podem ser construídas com cons, car e cdr sozinhos. Esta seção mostra como usar pares para representar uma estrutura de dados chamada fila. A Seção 3.3.3 mostrará como representar estruturas de dados chamadas tabelas.

Uma fila é uma sequência na qual os itens são inseridos em uma extremidade (chamada de traseira da fila) e excluídos da outra extremidade (a frente). A Figura 3.18 mostra uma fila inicialmente vazia na qual os itens a e b são inseridos. Então a é removido, c e d são inseridos e b é removido. Como os itens são sempre removidos na ordem em que são inseridos, uma fila é às vezes chamada de buffer FIFO (primeiro a entrar, primeiro a sair).

Em termos de abstração de dados, podemos considerar uma fila como definida pelo seguinte conjunto de operações:

• um construtor: (make-queue) retorna uma fila vazia (uma fila contendo nenhum item).
• dois seletores:

  (empty-queue? ⟨fila⟩)

  testa se a fila está vazia.

  (front-queue ⟨fila⟩)

  retorna o objeto na frente da fila, sinalizando um erro se a fila estiver vazia; não modifica a fila.

• dois mutadores:

  (insert-queue! ⟨fila⟩ ⟨item⟩)

  insere o item na traseira da fila e retorna a fila modificada como seu valor.

  (delete-queue! ⟨fila⟩)

  remove o item na frente da fila e retorna a fila modificada como seu valor, sinalizando um erro se a fila estiver vazia antes da exclusão.

Como uma fila é uma sequência de itens, poderíamos certamente representá-la como uma lista comum; a frente da fila seria o car da lista, inserir um item na fila equivaleria a anexar um novo elemento ao final da lista, e excluir um item da fila seria apenas tomar o cdr da lista. No entanto, essa representação é ineficiente, porque para inserir um item devemos percorrer a lista até chegarmos ao final. Como o único método que temos para percorrer uma lista é por operações sucessivas de cdr, essa varredura requer $\mathrm{\Theta }(n)$ passos para uma lista de $n$ itens. Uma modificação simples na representação da lista supera essa desvantagem, permitindo que as operações de fila sejam implementadas de forma que requeiram $\mathrm{\Theta }(1)$ passos; ou seja, o número de passos necessários é independente do comprimento da fila.

A dificuldade com a representação de lista surge da necessidade de percorrer a lista para encontrar o final. A razão pela qual precisamos percorrer é que, embora a maneira padrão de representar uma lista como uma cadeia de pares nos forneça prontamente um ponteiro para o início da lista, ela não nos dá um ponteiro facilmente acessível para o final. A modificação que evita essa desvantagem é representar a fila como uma lista, junto com um ponteiro adicional que indica o par final na lista. Dessa forma, quando formos inserir um item, podemos consultar o ponteiro traseiro e, assim, evitar percorrer a lista.

Uma fila é representada, então, como um par de ponteiros, front-ptr e rear-ptr, que indicam, respectivamente, o primeiro e o último par em uma lista comum. Como gostaríamos que a fila fosse um objeto identificável, podemos usar cons para combinar os dois ponteiros. Assim, a fila em si será o cons dos dois ponteiros. A Figura 3.19 ilustra essa representação.

Para definir as operações de fila, usamos os seguintes procedimentos, que nos permitem selecionar e modificar os ponteiros de frente e traseira de uma fila:

(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) 
  (set-car! queue item))
(define (set-rear-ptr! queue item) 
  (set-cdr! queue item))

Agora podemos implementar as operações reais da fila. Consideraremos uma fila vazia se seu ponteiro de frente for a lista vazia:

(define (empty-queue? queue) 
  (null? (front-ptr queue)))

O construtor make-queue retorna, como uma fila inicialmente vazia, um par cujo car e cdr são ambos a lista vazia:

(define (make-queue) (cons '() '()))

Para selecionar o item na frente da fila, retornamos o car do par indicado pelo ponteiro de frente:

(define (front-queue queue)
  (if (empty-queue? queue)
      (error "FRONT chamado com uma fila vazia" queue)
      (car (front-ptr queue))))

Para inserir um item em uma fila, seguimos o método cujo resultado é indicado na Figura 3.20. Primeiro criamos um novo par cujo car é o item a ser inserido e cujo cdr é a lista vazia. Se a fila estava inicialmente vazia, definimos os ponteiros de frente e traseira da fila para este novo par. Caso contrário, modificamos o par final na fila para apontar para o novo par e também definimos o ponteiro traseiro para o novo par.

(define (insert-queue! queue item)
  (let ((new-pair (cons item '())))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-pair)
           (set-rear-ptr! queue new-pair)
           queue)
          (else (set-cdr! (rear-ptr queue) 
                          new-pair)
                (set-rear-ptr! queue new-pair)
                queue))))

Para excluir o item na frente da fila, simplesmente modificamos o ponteiro de frente para que ele agora aponte para o segundo item na fila, que pode ser encontrado seguindo o ponteiro cdr do primeiro item (veja a Figura 3.21):¹⁵⁰

(define (delete-queue! queue)
  (cond ((empty-queue? queue)
         (error "DELETE! chamado com uma fila vazia" queue))
        (else (set-front-ptr! 
               queue 
               (cdr (front-ptr queue)))
              queue)))

Exercício 3.21: Ben Bitdiddle decide testar a implementação da fila descrita acima. Ele digita os procedimentos no interpretador Lisp e começa a testá-los:

(define q1 (make-queue))
        
        (insert-queue! q1 'a)
        ((a) a)
        
        (insert-queue! q1 'b)
        ((a b) b)
        
        (delete-queue! q1)
        ((b) b)
        
        (delete-queue! q1)
        (() b)

“Está tudo errado!” ele reclama. “A resposta do interpretador mostra que o último item é inserido na fila duas vezes. E quando eu deleto ambos os itens, o segundo b ainda está lá, então a fila não está vazia, mesmo que deveria estar.” Eva Lu Ator sugere que Ben entendeu mal o que está acontecendo. “Não é que os itens estão entrando na fila duas vezes,” ela explica. “É apenas que a impressora padrão do Lisp não sabe como interpretar a representação da fila. Se você quiser ver a fila impressa corretamente, você terá que definir seu próprio procedimento de impressão para filas.” Explique o que Eva Lu está falando. Em particular, mostre por que os exemplos de Ben produzem os resultados impressos que eles produzem. Defina um procedimento print-queue que recebe uma fila como entrada e imprime a sequência de itens na fila.

Exercício 3.22: Em vez de representar uma fila como um par de ponteiros, podemos construir uma fila como um procedimento com estado local. O estado local consistirá em ponteiros para o início e o fim de uma lista comum. Assim, o procedimento make-queue terá a forma:

(define (make-queue)
          (let ((front-ptr … )
                (rear-ptr … ))
            ⟨definições de procedimentos internos⟩
            (define (dispatch m) …)
            dispatch))

Complete a definição de make-queue e forneça implementações das operações de fila usando essa representação.

Exercício 3.23: Um deque (“fila de duas extremidades”) é uma sequência na qual os itens podem ser inseridos e deletados tanto na frente quanto no final. As operações em deques são o construtor make-deque, o predicado empty-deque?, os seletores front-deque e rear-deque, e os mutadores front-insert-deque!, rear-insert-deque!, front-delete-deque!, e rear-delete-deque!. Mostre como representar deques usando pares e forneça implementações das operações.¹⁵¹ Todas as operações devem ser realizadas em $\mathrm{\Theta <!--\; \Theta \; -->}(1)$ passos.

3.3.3Representando Tabelas

Quando estudamos várias maneiras de representar conjuntos no Capítulo 2, mencionamos em 2.3.3 a tarefa de manter uma tabela de registros indexados por chaves identificadoras. Na implementação de programação orientada a dados em 2.4.3, usamos extensivamente tabelas bidimensionais, nas quais as informações são armazenadas e recuperadas usando duas chaves. Aqui vemos como construir tabelas como estruturas de listas mutáveis.

Primeiro consideramos uma tabela unidimensional, na qual cada valor é armazenado sob uma única chave. Implementamos a tabela como uma lista de registros, cada um dos quais é implementado como um par consistindo de uma chave e o valor associado. Os registros são unidos para formar uma lista por pares cujos cars apontam para registros sucessivos. Esses pares de união são chamados de espinha dorsal da tabela. Para ter um lugar que possamos alterar quando adicionamos um novo registro à tabela, construímos a tabela como uma lista com cabeçalho. Uma lista com cabeçalho tem um par especial no início, que contém um registro “dummy”—neste caso, o símbolo arbitrariamente escolhido *table*. Figura 3.22 mostra o diagrama de caixas e ponteiros para a tabela:

a: 1
        b: 2
        c: 3

Para extrair informações de uma tabela, usamos o procedimento lookup, que recebe uma chave como argumento e retorna o valor associado (ou falso se não houver valor armazenado sob essa chave). Lookup é definido em termos da operação assoc, que espera uma chave e uma lista de registros como argumentos. Note que assoc nunca vê o registro dummy. Assoc retorna o registro que tem a chave dada como seu car.¹⁵² Lookup então verifica se o registro retornado por assoc não é falso e retorna o valor (o cdr) do registro.

(define (lookup key table)
          (let ((record (assoc key (cdr table))))
            (if record
                (cdr record)
                false)))
        
        (define (assoc key records)
          (cond ((null? records) false)
                ((equal? key (caar records)) 
                 (car records))
                (else (assoc key (cdr records))))

Para inserir um valor em uma tabela sob uma chave especificada, primeiro usamos assoc para ver se já existe um registro na tabela com essa chave. Se não, formamos um novo registro usando cons com a chave e o valor, e inserimos isso no início da lista de registros da tabela, após o registro dummy. Se já existe um registro com essa chave, definimos o cdr desse registro para o novo valor designado. O cabeçalho da tabela nos fornece um local fixo para modificar a fim de inserir o novo registro.¹⁵³

(define (insert! key value table)
          (let ((record (assoc key (cdr table))))
            (if record
                (set-cdr! record value)
                (set-cdr! table
                          (cons (cons key value) 
                                (cdr table)))))
          'ok)

Para construir uma nova tabela, simplesmente criamos uma lista contendo o símbolo *table*:

(define (make-table)
          (list '*table*))

Tabelas bidimensionais

Em uma tabela bidimensional, cada valor é indexado por duas chaves. Podemos construir tal tabela como uma tabela unidimensional na qual cada chave identifica uma subtabela. Figura 3.23 mostra o diagrama de caixas e ponteiros para a tabela:

math:  +: 43    letters:  a: 97
               -: 45              b: 98
               *: 42

que tem duas subtabelas. (As subtabelas não precisam de um símbolo de cabeçalho especial, pois a chave que identifica a subtabela serve para esse propósito.)

Quando procuramos um item, usamos a primeira chave para identificar a subtabela correta. Em seguida, usamos a segunda chave para identificar o registro dentro da subtabela.

(define (lookup key-1 key-2 table)
          (let ((subtable (assoc key-1 (cdr table))))
            (if subtable
                (let ((record 
                       (assoc key-2 (cdr subtable))))
                  (if record (cdr record) false))
                false)))

Para inserir um novo item sob um par de chaves, usamos assoc para ver se há uma subtabela armazenada sob a primeira chave. Se não, construímos uma nova subtabela contendo o único registro (key-2, value) e a inserimos na tabela sob a primeira chave. Se uma subtabela já existe para a primeira chave, inserimos o novo registro nessa subtabela, usando o método de inserção para tabelas unidimensionais descrito acima:

(define (insert! key-1 key-2 value table)
          (let ((subtable (assoc key-1 (cdr table))))
            (if subtable
                (let ((record 
                       (assoc key-2 (cdr subtable))))
                  (if record
                      (set-cdr! record value)
                      (set-cdr! 
                       subtable
                       (cons (cons key-2 value)
                             (cdr subtable)))))
                (set-cdr! 
                 table
                 (cons (list key-1 (cons key-2 value))
                       (cdr table)))))
          'ok)

Criando tabelas locais

As operações lookup e insert! definidas acima recebem a tabela como um argumento. Isso nos permite usar programas que acessam mais de uma tabela. Outra maneira de lidar com múltiplas tabelas é ter procedimentos lookup e insert! separados para cada tabela. Podemos fazer isso representando uma tabela proceduralmente, como um objeto que mantém uma tabela interna como parte de seu estado local. Quando enviada uma mensagem apropriada, esse “objeto de tabela” fornece o procedimento com o qual operar na tabela interna. Aqui está um gerador para tabelas bidimensionais representadas dessa forma:

(define (make-table)
          (let ((local-table (list '*table*)))
            (define (lookup key-1 key-2)
              (let ((subtable 
                     (assoc key-1 (cdr local-table))))
                (if subtable
                    (let ((record 
                           (assoc key-2 
                                  (cdr subtable))))
                      (if record (cdr record) false))
                    false)))
            (define (insert! key-1 key-2 value)
              (let ((subtable 
                     (assoc key-1 (cdr local-table))))
                (if subtable
                    (let ((record 
                           (assoc key-2 
                                  (cdr subtable))))
                      (if record
                          (set-cdr! record value)
                          (set-cdr! 
                           subtable
                           (cons (cons key-2 value)
                                 (cdr subtable)))))
                    (set-cdr! 
                     local-table
                     (cons (list key-1
                                 (cons key-2 value))
                           (cdr local-table)))))
              'ok)
            (define (dispatch m)
              (cond ((eq? m 'lookup-proc) lookup)
                    ((eq? m 'insert-proc!) insert!)
                    (else (error "Unknown operation: 
                                  TABLE" m))))
            dispatch))

Usando make-table, poderíamos implementar as operações get e put usadas em 2.4.3 para programação orientada a dados, da seguinte forma:

(define operation-table (make-table))
        (define get (operation-table 'lookup-proc))
        (define put (operation-table 'insert-proc!))

Get recebe como argumentos duas chaves, e put recebe como argumentos duas chaves e um valor. Ambas as operações acessam a mesma tabela local, que é encapsulada dentro do objeto criado pela chamada a make-table.

Exercício 3.24: Nas implementações de tabelas acima, as chaves são testadas para igualdade usando equal? (chamado por assoc). Isso nem sempre é o teste apropriado. Por exemplo, podemos ter uma tabela com chaves numéricas nas quais não precisamos de uma correspondência exata para o número que estamos procurando, mas apenas um número dentro de alguma tolerância. Projete um construtor de tabela make-table que recebe como argumento um procedimento same-key? que será usado para testar a “igualdade” das chaves. Make-table deve retornar um procedimento dispatch que pode ser usado para acessar procedimentos lookup e insert! apropriados para uma tabela local.

Exercício 3.25: Generalizando tabelas uni e bidimensionais, mostre como implementar uma tabela na qual os valores são armazenados sob um número arbitrário de chaves e diferentes valores podem ser armazenados sob diferentes números de chaves. Os procedimentos lookup e insert! devem receber como entrada uma lista de chaves usadas para acessar a tabela.

Exercício 3.26: Para pesquisar uma tabela como implementada acima, é necessário percorrer a lista de registros. Isso é basicamente a representação de lista não ordenada de 2.3.3. Para tabelas grandes, pode ser mais eficiente estruturar a tabela de uma maneira diferente. Descreva uma implementação de tabela onde os registros (chave, valor) são organizados usando uma árvore binária, assumindo que as chaves podem ser ordenadas de alguma forma (por exemplo, numericamente ou alfabeticamente). (Compare com Exercício 2.66 do Capítulo 2.)

Exercício 3.27: Memoização (também chamada de tabelamento) é uma técnica que permite a um procedimento registrar, em uma tabela local, valores que foram previamente computados. Essa técnica pode fazer uma grande diferença no desempenho de um programa. Um procedimento memoizado mantém uma tabela na qual os valores de chamadas anteriores são armazenados usando como chaves os argumentos que produziram os valores. Quando o procedimento memoizado é solicitado a computar um valor, ele primeiro verifica a tabela para ver se o valor já está lá e, se estiver, simplesmente retorna esse valor. Caso contrário, ele computa o novo valor da maneira usual e armazena isso na tabela. Como exemplo de memoização, lembre-se do processo exponencial para computar números de Fibonacci de 1.2.2:

(define (fib n)
          (cond ((= n 0) 0)
                ((= n 1) 1)
                (else (+ (fib (- n 1))
                         (fib (- n 2))))))

A versão memoizada do mesmo procedimento é:

(define memo-fib
          (memoize 
           (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else 
                    (+ (memo-fib (- n 1))
                       (memo-fib (- n 2))))))))

onde o memoizador é definido como:

(define (memoize f)
          (let ((table (make-table)))
            (lambda (x)
              (let ((previously-computed-result 
                     (lookup x table)))
                (or previously-computed-result
                    (let ((result (f x)))
                      (insert! x result table)
                      result))))))

Desenhe um diagrama de ambiente para analisar a computação de (memo-fib 3). Explique por que memo-fib computa o $n^{\text{th}}$ número de Fibonacci em um número de passos proporcional a $n$. O esquema ainda funcionaria se tivéssemos simplesmente definido memo-fib como (memoize fib)?

3.3.4Um Simulador para Circuitos Digitais

Projetar sistemas digitais complexos, como computadores, é uma atividade importante de engenharia. Sistemas digitais são construídos interconectando elementos simples. Embora o comportamento desses elementos individuais seja simples, redes deles podem ter comportamentos muito complexos. A simulação por computador de projetos de circuitos propostos é uma ferramenta importante usada por engenheiros de sistemas digitais. Nesta seção, projetamos um sistema para realizar simulações de lógica digital. Este sistema tipifica um tipo de programa chamado simulação dirigida por eventos, na qual ações (“eventos”) desencadeiam mais eventos que acontecem em um momento posterior, que por sua vez desencadeiam mais eventos, e assim por diante.

Nosso modelo computacional de um circuito será composto de objetos que correspondem aos componentes elementares dos quais o circuito é construído. Existem fios, que carregam sinais digitais. Um sinal digital pode a qualquer momento ter apenas um de dois valores possíveis, 0 e 1. Existem também vários tipos de caixas de função digitais, que conectam fios que carregam sinais de entrada a outros fios de saída. Tais caixas produzem sinais de saída computados a partir de seus sinais de entrada. O sinal de saída é atrasado por um tempo que depende do tipo da caixa de função. Por exemplo, um inversor é uma caixa de função primitiva que inverte sua entrada. Se o sinal de entrada para um inversor mudar para 0, então um atraso de inversor depois o inversor mudará seu sinal de saída para 1. Se o sinal de entrada para um inversor mudar para 1, então um atraso de inversor depois o inversor mudará seu sinal de saída para 0. Desenhamos um inversor simbolicamente como na Figura 3.24. Um porta AND, também mostrada na figura 3.24, é uma caixa de função primitiva com duas entradas e uma saída. Ela força seu sinal de saída para um valor que é o AND lógico das entradas. Ou seja, se ambas as suas entradas se tornarem 1, então um atraso de porta AND depois a porta AND forçará seu sinal de saída a ser 1; caso contrário, a saída será 0. Uma porta OR é uma caixa de função primitiva similar de duas entradas que força seu sinal de saída para um valor que é o OR lógico das entradas. Ou seja, a saída se tornará 1 se pelo menos uma das entradas for 1; caso contrário, a saída se tornará 0.

Podemos conectar funções primitivas para construir funções mais complexas. Para isso, conectamos as saídas de algumas caixas de função às entradas de outras caixas de função. Por exemplo, o circuito meio-somador mostrado na Figura 3.25 consiste em uma porta OR, duas portas AND e um inversor. Ele recebe dois sinais de entrada, A e B, e tem dois sinais de saída, S e C. S se tornará 1 sempre que exatamente um de A e B for 1, e C se tornará 1 sempre que A e B forem ambos 1. Podemos ver na figura que, devido aos atrasos envolvidos, as saídas podem ser geradas em momentos diferentes. Muitas das dificuldades no projeto de circuitos digitais surgem desse fato.

Agora construiremos um programa para modelar os circuitos de lógica digital que desejamos estudar. O programa construirá objetos computacionais modelando os fios, que “segurarão” os sinais. As caixas de função serão modeladas por procedimentos que impõem as relações corretas entre os sinais.

Um elemento básico de nossa simulação será um procedimento make-wire, que constrói fios. Por exemplo, podemos construir seis fios da seguinte forma:

(define a (make-wire))
        (define b (make-wire))
        (define c (make-wire))
        (define d (make-wire))
        (define e (make-wire))
        (define s (make-wire))

Conectamos uma caixa de função a um conjunto de fios chamando um procedimento que constrói esse tipo de caixa. Os argumentos para o procedimento construtor são os fios a serem conectados à caixa. Por exemplo, dado que podemos construir portas AND, portas OR e inversores, podemos conectar o meio-somador mostrado na Figura 3.25:

(or-gate a b d)
        ok
        
        (and-gate a b c)
        ok
        
        (inverter c e)
        ok
        
        (and-gate d e s)
        ok

Melhor ainda, podemos nomear explicitamente esta operação definindo um procedimento half-adder que constrói este circuito, dados os quatro fios externos a serem conectados ao meio-somador:

(define (half-adder a b s c)
          (let ((d (make-wire)) (e (make-wire)))
            (or-gate a b d)
            (and-gate a b c)
            (inverter c e)
            (and-gate d e s)
            'ok))

A vantagem de fazer esta definição é que podemos usar half-adder como um bloco de construção para criar circuitos mais complexos. Figura 3.26, por exemplo, mostra um somador completo composto por dois meio-somadores e uma porta OR.¹⁵⁴ Podemos construir um somador completo da seguinte forma:

(define (full-adder a b c-in sum c-out)
          (let ((c1 (make-wire)) 
                (c2 (make-wire))
                (s  (make-wire)))
            (half-adder b c-in s c1)
            (half-adder a s sum c2)
            (or-gate c1 c2 c-out)
            'ok))

Tendo definido full-adder como um procedimento, podemos agora usá-lo como um bloco de construção para criar circuitos ainda mais complexos. (Por exemplo, veja Exercício 3.30.)

Em essência, nosso simulador nos fornece as ferramentas para construir uma linguagem de circuitos. Se adotarmos a perspectiva geral sobre linguagens com a qual abordamos o estudo de Lisp em 1.1, podemos dizer que as caixas de função primitivas formam os elementos primitivos da linguagem, que a conexão de caixas fornece um meio de combinação, e que a especificação de padrões de conexão como procedimentos serve como um meio de abstração.

Caixas de função primitivas

As caixas de função primitivas implementam as “forças” pelas quais uma mudança no sinal em um fio influencia os sinais em outros fios. Para construir caixas de função, usamos as seguintes operações em fios:

• (get-signal ⟨wire⟩)

  retorna o valor atual do sinal no fio.

• (set-signal! ⟨wire⟩ ⟨new value⟩)

  altera o valor do sinal no fio para o novo valor.

• (add-action! ⟨wire⟩ ⟨procedure of no arguments⟩)

  afirma que o procedimento designado deve ser executado sempre que o sinal no fio mudar de valor. Tais procedimentos são os veículos pelos quais as mudanças no valor do sinal no fio são comunicadas a outros fios.

Além disso, usaremos um procedimento after-delay que recebe um atraso de tempo e um procedimento a ser executado e executa o procedimento dado após o atraso dado.

Usando esses procedimentos, podemos definir as funções de lógica digital primitivas. Para conectar uma entrada a uma saída através de um inversor, usamos add-action! para associar ao fio de entrada um procedimento que será executado sempre que o sinal no fio de entrada mudar de valor. O procedimento computa o logical-not do sinal de entrada e, então, após um inverter-delay, define o sinal de saída para este novo valor:

(define (inverter input output)
          (define (invert-input)
            (let ((new-value 
                   (logical-not (get-signal input))))
              (after-delay 
               inverter-delay
               (lambda ()
                 (set-signal! output new-value)))))
          (add-action! input invert-input)
          'ok)
        
        (define (logical-not s)
          (cond ((= s 0) 1)
                ((= s 1) 0)
                (else (error "Invalid signal" s))))

Uma porta AND é um pouco mais complexa. O procedimento de ação deve ser executado se qualquer uma das entradas para a porta mudar. Ele computa o logical-and (usando um procedimento análogo a logical-not) dos valores dos sinais nos fios de entrada e configura uma mudança para o novo valor para ocorrer no fio de saída após um and-gate-delay.

(define (and-gate a1 a2 output)
          (define (and-action-procedure)
            (let ((new-value
                   (logical-and (get-signal a1) 
                                (get-signal a2))))
              (after-delay 
               and-gate-delay
               (lambda ()
                 (set-signal! output new-value)))))
          (add-action! a1 and-action-procedure)
          (add-action! a2 and-action-procedure)
          'ok)

Exercício 3.28: Defina uma porta OR como uma caixa de função primitiva. Seu construtor or-gate deve ser similar ao and-gate.

Exercício 3.29: Outra maneira de construir uma porta OR é como um dispositivo de lógica digital composto, construído a partir de portas AND e inversores. Defina um procedimento or-gate que realiza isso. Qual é o tempo de atraso da porta OR em termos de and-gate-delay e inverter-delay?

Exercício 3.30: Figura 3.27 mostra um somador ripple-carry formado por encadeamento de $n$ somadores completos. Esta é a forma mais simples de somador paralelo para adicionar dois números binários de $n$ bits. As entradas $A_1$, $A_2$, $A_3$, …, $A_n$ e $B_1$, $B_2$, $B_3$, …, $B_n$ são os dois números binários a serem adicionados (cada $A_k$ e $B_k$ é um 0 ou um 1). O circuito gera $S_1$, $S_2$, $S_3$, …, $S_n$, os $n$ bits da soma, e $C$, o carry da adição. Escreva um procedimento ripple-carry-adder que gera este circuito. O procedimento deve receber como argumentos três listas de $n$ fios cada—os $A_k$, os $B_k$, e os $S_k$—e também outro fio $C$. A principal desvantagem do somador ripple-carry é a necessidade de esperar pelos sinais de carry para se propagarem. Qual é o atraso necessário para obter a saída completa de um somador ripple-carry de $n$ bits, expresso em termos dos atrasos para portas AND, portas OR e inversores?

Representando fios

Um fio em nossa simulação será um objeto computacional com duas variáveis de estado local: um signal-value (inicialmente tomado como 0) e uma coleção de action-procedures a serem executadas quando o sinal mudar de valor. Implementamos o fio, usando o estilo de passagem de mensagens, como uma coleção de procedimentos locais junto com um procedimento dispatch que seleciona a operação local apropriada, assim como fizemos com o objeto simples de conta bancária em 3.1.1:

(define (make-wire)
          (let ((signal-value 0) 
                (action-procedures '()))
            (define (set-my-signal! new-value)
              (if (not (= signal-value new-value))
                  (begin (set! signal-value new-value)
                         (call-each 
                          action-procedures))
                  'done))
            (define (accept-action-procedure! proc)
              (set! action-procedures 
                    (cons proc action-procedures))
              (proc))
            (define (dispatch m)
              (cond ((eq? m 'get-signal) 
                     signal-value)
                    ((eq? m 'set-signal!) 
                     set-my-signal!)
                    ((eq? m 'add-action!) 
                     accept-action-procedure!)
                    (else (error "Unknown operation: 
                                  WIRE" m))))
            dispatch))

O procedimento local set-my-signal! testa se o novo valor do sinal muda o sinal no fio. Se sim, ele executa cada um dos procedimentos de ação, usando o seguinte procedimento call-each, que chama cada um dos itens em uma lista de procedimentos sem argumentos:

(define (call-each procedures)
          (if (null? procedures)
              'done
              (begin ((car procedures))
                     (call-each (cdr procedures)))))

O procedimento local accept-action-procedure! adiciona o procedimento dado à lista de procedimentos a serem executados e, em seguida, executa o novo procedimento uma vez. (Veja Exercício 3.31.)

Com o procedimento local dispatch configurado conforme especificado, podemos fornecer os seguintes procedimentos para acessar as operações locais em fios:¹⁵⁵

(define (get-signal wire)
          (wire 'get-signal))
        (define (set-signal! wire new-value)
          ((wire 'set-signal!) new-value))
        (define (add-action! wire action-procedure)
          ((wire 'add-action!) action-procedure))

Fios, que têm sinais variáveis no tempo e podem ser incrementalmente conectados a dispositivos, são típicos de objetos mutáveis. Nós os modelamos como procedimentos com variáveis de estado local que são modificadas por atribuição. Quando um novo fio é criado, um novo conjunto de variáveis de estado é alocado (pela expressão let em make-wire) e um novo procedimento dispatch é construído e retornado, capturando o ambiente com as novas variáveis de estado.

Os fios são compartilhados entre os vários dispositivos que foram conectados a eles. Assim, uma mudança feita por uma interação com um dispositivo afetará todos os outros dispositivos conectados ao fio. O fio comunica a mudança aos seus vizinhos chamando os procedimentos de ação fornecidos a ele quando as conexões foram estabelecidas.

A agenda

A única coisa necessária para completar o simulador é after-delay. A ideia aqui é que mantemos uma estrutura de dados, chamada agenda, que contém um cronograma de coisas a fazer. As seguintes operações são definidas para agendas:

• (make-agenda) retorna uma nova agenda vazia.
• (empty-agenda? ⟨agenda⟩) é verdadeiro se a agenda especificada estiver vazia.
• (first-agenda-item ⟨agenda⟩) retorna o primeiro item na agenda.
• (remove-first-agenda-item! ⟨agenda⟩) modifica a agenda removendo o primeiro item.
• (add-to-agenda! ⟨time⟩ ⟨action⟩ ⟨agenda⟩) modifica a agenda adicionando o procedimento de ação dado para ser executado no tempo especificado.
• (current-time ⟨agenda⟩) retorna o tempo atual da simulação.

A agenda particular que usamos é denotada por the-agenda. O procedimento after-delay adiciona novos elementos a the-agenda:

(define (after-delay delay action)
          (add-to-agenda! 
           (+ delay (current-time the-agenda))
           action
           the-agenda))

A simulação é conduzida pelo procedimento propagate, que opera em the-agenda, executando cada procedimento na agenda em sequência. Em geral, à medida que a simulação é executada, novos itens serão adicionados à agenda, e propagate continuará a simulação enquanto houver itens na agenda:

(define (propagate)
          (if (empty-agenda? the-agenda)
              'done
              (let ((first-item 
                     (first-agenda-item the-agenda)))
                (first-item)
                (remove-first-agenda-item! the-agenda)
                (propagate))))

Uma simulação de exemplo

O seguinte procedimento, que coloca uma “sonda” em um fio, mostra o simulador em ação. A sonda diz ao fio que, sempre que seu sinal mudar de valor, ele deve imprimir o novo valor do sinal, junto com o tempo atual e um nome que identifica o fio:

(define (probe name wire)
          (add-action! 
           wire
           (lambda ()
             (newline)
             (display name)
             (display " ")
             (display (current-time the-agenda))
             (display "  New-value = ")
             (display (get-signal wire)))))

Começamos inicializando a agenda e especificando atrasos para as caixas de função primitivas:

(define the-agenda (make-agenda))
        (define inverter-delay 2)
        (define and-gate-delay 3)
        (define or-gate-delay 5)

Agora definimos quatro fios, colocando sondas em dois deles:

(define input-1 (make-wire))
        (define input-2 (make-wire))
        (define sum (make-wire))
        (define carry (make-wire))
        
        (probe 'sum sum)
        sum 0  New-value = 0
        
        (probe 'carry carry)
        carry 0  New-value = 0

Em seguida, conectamos os fios em um circuito meio-somador (como na Figura 3.25), definimos o sinal em input-1 para 1 e executamos a simulação:

(half-adder input-1 input-2 sum carry)
        ok
        
        (set-signal! input-1 1)
        done
        
        (propagate)
        sum 8  New-value = 1
        done

O sinal sum muda para 1 no tempo 8. Agora estamos oito unidades de tempo desde o início da simulação. Neste ponto, podemos definir o sinal em input-2 para 1 e permitir que os valores se propaguem:

(set-signal! input-2 1)
        done
        
        (propagate)
        carry 11  New-value = 1
        sum 16  New-value = 0
        done

O carry muda para 1 no tempo 11 e o sum muda para 0 no tempo 16.

Exercício 3.31: O procedimento interno accept-action-procedure! definido em make-wire especifica que, quando um novo procedimento de ação é adicionado a um fio, o procedimento é imediatamente executado. Explique por que essa inicialização é necessária. Em particular, percorra o exemplo do meio-somador nos parágrafos acima e diga como a resposta do sistema seria diferente se tivéssemos definido accept-action-procedure! como:

(define (accept-action-procedure! proc)
          (set! action-procedures 
                (cons proc action-procedures)))

Implementing the agenda

Finalmente, damos detalhes da estrutura de dados da agenda, que contém os procedimentos agendados para execução futura.

A agenda é composta por segmentos de tempo. Cada segmento de tempo é um par consistindo de um número (o tempo) e uma fila (veja Exercício 3.32) que contém os procedimentos agendados para serem executados durante esse segmento de tempo.

(define (make-time-segment time queue)
  (cons time queue))
(define (segment-time s) (car s))
(define (segment-queue s) (cdr s))

Operaremos nas filas dos segmentos de tempo usando as operações de fila descritas em 3.3.2.

A agenda em si é uma tabela unidimensional de segmentos de tempo. Ela difere das tabelas descritas em 3.3.3 no fato de que os segmentos serão ordenados em ordem crescente de tempo. Além disso, armazenamos o tempo atual (ou seja, o tempo da última ação processada) no início da agenda. Uma agenda recém-construída não tem segmentos de tempo e tem um tempo atual de 0:¹⁵⁶

(define (make-agenda) (list 0))
(define (current-time agenda) (car agenda))
(define (set-current-time! agenda time)
  (set-car! agenda time))
(define (segments agenda) (cdr agenda))
(define (set-segments! agenda segments)
  (set-cdr! agenda segments))
(define (first-segment agenda) 
  (car (segments agenda)))
(define (rest-segments agenda) 
  (cdr (segments agenda)))

Uma agenda está vazia se não tiver segmentos de tempo:

(define (empty-agenda? agenda)
  (null? (segments agenda)))

Para adicionar uma ação a uma agenda, primeiro verificamos se a agenda está vazia. Se estiver, criamos um segmento de tempo para a ação e o instalamos na agenda. Caso contrário, percorremos a agenda, examinando o tempo de cada segmento. Se encontrarmos um segmento para o tempo designado, adicionamos a ação à fila associada. Se chegarmos a um tempo posterior ao que estamos designando, inserimos um novo segmento de tempo na agenda logo antes dele. Se chegarmos ao final da agenda, devemos criar um novo segmento de tempo no final.

(define (add-to-agenda! time action agenda)
  (define (belongs-before? segments)
    (or (null? segments)
        (< time 
           (segment-time (car segments)))))
  (define (make-new-time-segment time action)
    (let ((q (make-queue)))
      (insert-queue! q action)
      (make-time-segment time q)))
  (define (add-to-segments! segments)
    (if (= (segment-time (car segments)) time)
        (insert-queue! 
         (segment-queue (car segments))
         action)
        (let ((rest (cdr segments)))
          (if (belongs-before? rest)
              (set-cdr!
               segments
               (cons (make-new-time-segment 
                      time 
                      action)
                     (cdr segments)))
              (add-to-segments! rest)))))
  (let ((segments (segments agenda)))
    (if (belongs-before? segments)
        (set-segments!
         agenda
         (cons (make-new-time-segment 
                time 
                action)
               segments))
        (add-to-segments! segments))))

O procedimento que remove o primeiro item da agenda deleta o item na frente da fila no primeiro segmento de tempo. Se essa deleção deixar o segmento de tempo vazio, removemos ele da lista de segmentos:¹⁵⁷

(define (remove-first-agenda-item! agenda)
  (let ((q (segment-queue 
            (first-segment agenda))))
    (delete-queue! q)
    (if (empty-queue? q)
        (set-segments! 
         agenda 
         (rest-segments agenda)))))

O primeiro item da agenda é encontrado na frente da fila no primeiro segmento de tempo. Sempre que extraímos um item, também atualizamos o tempo atual:¹⁵⁸

(define (first-agenda-item agenda)
  (if (empty-agenda? agenda)
      (error "Agenda is empty: 
              FIRST-AGENDA-ITEM")
      (let ((first-seg 
             (first-segment agenda)))
        (set-current-time! 
         agenda 
         (segment-time first-seg))
        (front-queue 
         (segment-queue first-seg)))))

Exercício 3.32: Os procedimentos a serem executados durante cada segmento de tempo da agenda são mantidos em uma fila. Assim, os procedimentos para cada segmento são chamados na ordem em que foram adicionados à agenda (primeiro a entrar, primeiro a sair). Explique por que essa ordem deve ser usada. Em particular, trace o comportamento de uma porta AND cujas entradas mudam de 0, 1 para 1, 0 no mesmo segmento e diga como o comportamento seria diferente se armazenássemos os procedimentos de um segmento em uma lista comum, adicionando e removendo procedimentos apenas na frente (último a entrar, primeiro a sair).

3.3.5Propagação de Restrições

Os programas de computador são tradicionalmente organizados como computações unidirecionais, que realizam operações em argumentos pré-especificados para produzir saídas desejadas. Por outro lado, frequentemente modelamos sistemas em termos de relações entre quantidades. Por exemplo, um modelo matemático de uma estrutura mecânica pode incluir a informação de que a deflexão $d$ de uma barra de metal está relacionada à força $F$ na barra, o comprimento $L$ da barra, a área da seção transversal $A$ e o módulo de elasticidade $E$ através da equação $$dAE=FL.$$ Tal equação não é unidirecional. Dadas quaisquer quatro das quantidades, podemos usá-la para calcular a quinta. No entanto, traduzir a equação para uma linguagem de programação tradicional nos forçaria a escolher uma das quantidades para ser calculada em termos das outras quatro. Assim, um procedimento para calcular a área $A$ não poderia ser usado para calcular a deflexão $d$, mesmo que os cálculos de $A$ e $d$ surjam da mesma equação.¹⁵⁹

Nesta seção, esboçamos o design de uma linguagem que nos permite trabalhar em termos das próprias relações. Os elementos primitivos da linguagem são restrições primitivas, que afirmam que certas relações mantêm-se entre quantidades. Por exemplo, (adder a b c) especifica que as quantidades $a$, $b$ e $c$ devem estar relacionadas pela equação $a+b=c$, (multiplier x y z) expressa a restrição $xy=z$, e (constant 3.14 x) diz que o valor de $x$ deve ser 3.14.

Nossa linguagem fornece um meio de combinar restrições primitivas para expressar relações mais complexas. Combinamos restrições construindo redes de restrições, nas quais as restrições são unidas por conectores. Um conector é um objeto que "segura" um valor que pode participar de uma ou mais restrições. Por exemplo, sabemos que a relação entre as temperaturas Fahrenheit e Celsius é $$9C=5(F-<!--\; -\; -->32).$$ Tal restrição pode ser pensada como uma rede consistindo de restrições primitivas de soma, multiplicação e constante (Figura 3.28). Na figura, vemos à esquerda uma caixa de multiplicação com três terminais, rotulados $m1$, $m2$, e $p$. Esses conectam o multiplicador ao resto da rede da seguinte forma: O terminal $m1$ está ligado a um conector $C$, que conterá a temperatura Celsius. O terminal $m2$ está ligado a um conector $w$, que também está ligado a uma caixa constante que contém 9. O terminal $p$, que a caixa de multiplicação restringe a ser o produto de $m1$ e $m2$, está ligado ao terminal $p$ de outra caixa de multiplicação, cujo $m2$ está conectado a uma constante 5 e cujo $m1$ está conectado a um dos termos em uma soma.

A computação por tal rede procede da seguinte forma: Quando um conector recebe um valor (pelo usuário ou por uma caixa de restrição à qual está ligado), ele acorda todas as suas restrições associadas (exceto a restrição que acabou de acordá-lo) para informá-las de que tem um valor. Cada caixa de restrição acordada então consulta seus conectores para ver se há informações suficientes para determinar um valor para um conector. Se houver, a caixa define esse conector, que então acorda todas as suas restrições associadas, e assim por diante. Por exemplo, na conversão entre Celsius e Fahrenheit, $w$, $x$ e $y$ são imediatamente definidos pelas caixas constantes para 9, 5 e 32, respectivamente. Os conectores acordam os multiplicadores e o somador, que determinam que não há informações suficientes para prosseguir. Se o usuário (ou alguma outra parte da rede) definir $C$ para um valor (digamos 25), o multiplicador mais à esquerda será acordado, e ele definirá $u$ para $25\cdot <!--\; \cdot \; -->9=225$. Então $u$ acorda o segundo multiplicador, que define $v$ para 45, e $v$ acorda o somador, que define $F$ para 77.

Usando o sistema de restrições

Para usar o sistema de restrições para realizar a computação de temperatura descrita acima, primeiro criamos dois conectores, C e F, chamando o construtor make-connector, e ligamos C e F em uma rede apropriada:

(define C (make-connector))
(define F (make-connector))
(celsius-fahrenheit-converter C F)
ok

O procedimento que cria a rede é definido da seguinte forma:

(define (celsius-fahrenheit-converter c f)
  (let ((u (make-connector))
        (v (make-connector))
        (w (make-connector))
        (x (make-connector))
        (y (make-connector)))
    (multiplier c w u)
    (multiplier v x u)
    (adder v y f)
    (constant 9 w)
    (constant 5 x)
    (constant 32 y)
    'ok))

Este procedimento cria os conectores internos u, v, w, x e y, e os liga como mostrado na Figura 3.28 usando os construtores de restrições primitivas adder, multiplier e constant. Assim como no simulador de circuitos digitais de 3.3.4, expressar essas combinações de elementos primitivos em termos de procedimentos fornece automaticamente à nossa linguagem um meio de abstração para objetos compostos.

Para observar a rede em ação, podemos colocar sondas nos conectores C e F, usando um procedimento probe semelhante ao que usamos para monitorar fios em 3.3.4. Colocar uma sonda em um conector fará com que uma mensagem seja impressa sempre que o conector receber um valor:

(probe "Celsius temp" C)
(probe "Fahrenheit temp" F)

Em seguida, definimos o valor de C para 25. (O terceiro argumento para set-value! diz a C que esta diretiva vem do user.)

(set-value! C 25 'user)
Probe: Celsius temp = 25
Probe: Fahrenheit temp = 77
done

A sonda em C acorda e relata o valor. C também propaga seu valor através da rede como descrito acima. Isso define F para 77, que é relatado pela sonda em F.

Agora podemos tentar definir F para um novo valor, digamos 212:

(set-value! F 212 'user)
Error! Contradiction (77 212)

O conector reclama que detectou uma contradição: Seu valor é 77, e alguém está tentando defini-lo para 212. Se realmente quisermos reutilizar a rede com novos valores, podemos dizer a C para esquecer seu valor antigo:

(forget-value! C 'user)
Probe: Celsius temp = ?
Probe: Fahrenheit temp = ?
done

C descobre que o user, que definiu seu valor originalmente, está agora retirando esse valor, então C concorda em perder seu valor, como mostrado pela sonda, e informa o resto da rede sobre esse fato. Essa informação eventualmente se propaga para F, que agora descobre que não tem mais razão para acreditar que seu próprio valor é 77. Assim, F também desiste de seu valor, como mostrado pela sonda.

Agora que F não tem valor, estamos livres para defini-lo para 212:

(set-value! F 212 'user)
Probe: Fahrenheit temp = 212
Probe: Celsius temp = 100
done

Este novo valor, quando propagado através da rede, força C a ter um valor de 100, e isso é registrado pela sonda em C. Observe que a mesma rede está sendo usada para calcular C dado F e para calcular F dado C. Essa não-direcionalidade da computação é a característica distintiva dos sistemas baseados em restrições.

Implementando o sistema de restrições

O sistema de restrições é implementado por meio de objetos procedurais com estado local, de maneira muito semelhante ao simulador de circuitos digitais de 3.3.4. Embora os objetos primitivos do sistema de restrições sejam um pouco mais complexos, o sistema geral é mais simples, já que não há preocupação com agendas e atrasos lógicos.

As operações básicas em conectores são as seguintes:

• (has-value? ⟨connector⟩) diz se o conector tem um valor.
• (get-value ⟨connector⟩) retorna o valor atual do conector.
• (set-value! ⟨connector⟩ ⟨new-value⟩ ⟨informant⟩) indica que o informante está solicitando que o conector defina seu valor para o novo valor.
• (forget-value! ⟨connector⟩ ⟨retractor⟩) diz ao conector que o retrator está solicitando que ele esqueça seu valor.
• (connect ⟨connector⟩ ⟨new-constraint⟩) diz ao conector para participar da nova restrição.

Os conectores se comunicam com as restrições por meio dos procedimentos inform-about-value, que informa à restrição dada que o conector tem um valor, e inform-about-no-value, que informa à restrição que o conector perdeu seu valor.

Adder constrói uma restrição de soma entre os conectores de soma a1 e a2 e um conector de soma sum. Um somador é implementado como um procedimento com estado local (o procedimento me abaixo):

(define (adder a1 a2 sum)
  (define (process-new-value)
    (cond ((and (has-value? a1) 
                (has-value? a2))
           (set-value! sum
                       (+ (get-value a1) 
                          (get-value a2))
                       me))
          ((and (has-value? a1) 
                (has-value? sum))
           (set-value! a2
                       (- (get-value sum) 
                          (get-value a1))
                       me))
          ((and (has-value? a2) 
                (has-value? sum))
           (set-value! a1
                       (- (get-value sum) 
                          (get-value a2))
                       me))))
  (define (process-forget-value)
    (forget-value! sum me)
    (forget-value! a1 me)
    (forget-value! a2 me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else (error "Unknown request: 
                        ADDER" request))))
  (connect a1 me)
  (connect a2 me)
  (connect sum me)
  me)

Adder conecta o novo somador aos conectores designados e o retorna como seu valor. O procedimento me, que representa o somador, age como um despachante para os procedimentos locais. As seguintes "interfaces de sintaxe" (veja Nota de rodapé 155 em 3.3.4) são usadas em conjunto com o despachante:

(define (inform-about-value constraint)
  (constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
  (constraint 'I-lost-my-value))

O procedimento local process-new-value do somador é chamado quando o somador é informado de que um de seus conectores tem um valor. O somador primeiro verifica se ambos a1 e a2 têm valores. Se tiverem, ele diz a sum para definir seu valor como a soma dos dois adendos. O argumento informant para set-value! é me, que é o próprio objeto somador. Se a1 e a2 não tiverem ambos valores, então o somador verifica se talvez a1 e sum tenham valores. Se tiverem, ele define a2 como a diferença entre esses dois. Finalmente, se a2 e sum tiverem valores, isso dá ao somador informações suficientes para definir a1. Se o somador for informado de que um de seus conectores perdeu um valor, ele solicita que todos os seus conectores agora percam seus valores. (Apenas os valores que foram definidos por este somador são realmente perdidos.) Em seguida, ele executa process-new-value. A razão para esta última etapa é que um ou mais conectores ainda podem ter um valor (ou seja, um conector pode ter tido um valor que não foi originalmente definido pelo somador), e esses valores podem precisar ser propagados de volta através do somador.

Um multiplicador é muito semelhante a um somador. Ele definirá seu product como 0 se qualquer um dos fatores for 0, mesmo que o outro fator não seja conhecido.

(define (multiplier m1 m2 product)
  (define (process-new-value)
    (cond ((or (and (has-value? m1) 
                    (= (get-value m1) 0))
               (and (has-value? m2) 
                    (= (get-value m2) 0)))
           (set-value! product 0 me))
          ((and (has-value? m1) 
                (has-value? m2))
           (set-value! product
                       (* (get-value m1) 
                          (get-value m2))
                       me))
          ((and (has-value? product) 
                (has-value? m1))
           (set-value! m2
                       (/ (get-value product) 
                          (get-value m1))
                       me))
          ((and (has-value? product) 
                (has-value? m2))
           (set-value! m1
                       (/ (get-value product) 
                          (get-value m2))
                       me))))
  (define (process-forget-value)
    (forget-value! product me)
    (forget-value! m1 me)
    (forget-value! m2 me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request: 
                   MULTIPLIER" 
                  request))))
  (connect m1 me)
  (connect m2 me)
  (connect product me)
  me)

Um construtor constant simplesmente define o valor do conector designado. Qualquer mensagem I-have-a-value ou I-lost-my-value enviada à caixa constante produzirá um erro.

(define (constant value connector)
  (define (me request)
    (error "Unknown request: CONSTANT" 
           request))
  (connect connector me)
  (set-value! connector value me)
  me)

Finalmente, uma sonda imprime uma mensagem sobre a definição ou indefinição do conector designado:

(define (probe name connector)
  (define (print-probe value)
    (newline) (display "Probe: ")
    (display name) (display " = ")
    (display value))
  (define (process-new-value)
    (print-probe (get-value connector)))
  (define (process-forget-value)
    (print-probe "?"))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else (error "Unknown request: 
                        PROBE" request))))
  (connect connector me)
  me)

Representando conectores

Um conector é representado como um objeto procedimental com variáveis de estado local value, o valor atual do conector; informant, o objeto que definiu o valor do conector; e constraints, uma lista das restrições nas quais o conector participa.

(define (make-connector)
  (let ((value false) 
        (informant false) 
        (constraints '()))
    (define (set-my-value newval setter)
      (cond ((not (has-value? me))
             (set! value newval)
             (set! informant setter)
             (for-each-except 
              setter
              inform-about-value
              constraints))
            ((not (= value newval))
             (error "Contradiction" 
                    (list value newval)))
            (else 'ignored)))
    (define (forget-my-value retractor)
      (if (eq? retractor informant)
          (begin (set! informant false)
                 (for-each-except 
                  retractor
                  inform-about-no-value
                  constraints))
          'ignored))
    (define (connect new-constraint)
      (if (not (memq new-constraint 
                     constraints))
          (set! constraints
                (cons new-constraint 
                      constraints)))
      (if (has-value? me)
          (inform-about-value new-constraint))
      'done)
    (define (me request)
      (cond ((eq? request 'has-value?)
             (if informant true false))
            ((eq? request 'value) value)
            ((eq? request 'set-value!) 
             set-my-value)
            ((eq? request 'forget) 
             forget-my-value)
            ((eq? request 'connect) connect)
            (else (error "Unknown operation: 
                          CONNECTOR"
                         request))))
    me))

O procedimento local set-my-value do conector é chamado quando há uma solicitação para definir o valor do conector. Se o conector não tiver atualmente um valor, ele definirá seu valor e lembrará como informant a restrição que solicitou que o valor fosse definido.¹⁶⁰ Então, o conector notificará todas as suas restrições participantes, exceto a restrição que solicitou que o valor fosse definido. Isso é realizado usando o seguinte iterador, que aplica um procedimento designado a todos os itens em uma lista, exceto um dado:

(define (for-each-except exception 
                         procedure 
                         list)
  (define (loop items)
    (cond ((null? items) 'done)
          ((eq? (car items) exception) 
           (loop (cdr items)))
          (else (procedure (car items))
                (loop (cdr items)))))
  (loop list))

Se um conector for solicitado a esquecer seu valor, ele executará o procedimento local forget-my-value, que primeiro verifica se a solicitação está vindo do mesmo objeto que definiu o valor originalmente. Se estiver, o conector informa suas restrições associadas sobre a perda do valor.

O procedimento local connect adiciona a nova restrição designada à lista de restrições se ela ainda não estiver nessa lista. Então, se o conector tiver um valor, ele informa a nova restrição sobre esse fato.

O procedimento me do conector serve como um despachante para os outros procedimentos internos e também representa o conector como um objeto. Os seguintes procedimentos fornecem uma interface de sintaxe para o despachante:

(define (has-value? connector)
  (connector 'has-value?))
(define (get-value connector)
  (connector 'value))
(define (set-value! connector 
                    new-value 
                    informant)
  ((connector 'set-value!) 
   new-value 
   informant))
(define (forget-value! connector retractor)
  ((connector 'forget) retractor))
(define (connect connector new-constraint)
  ((connector 'connect) new-constraint))

Exercício 3.33: Usando restrições primitivas de multiplicação, soma e constante, defina um procedimento averager que recebe três conectores a, b e c como entradas e estabelece a restrição de que o valor de c é a média dos valores de a e b.

Exercício 3.34: Louis Reasoner quer construir um quadrador, um dispositivo de restrição com dois terminais tal que o valor do conector b no segundo terminal será sempre o quadrado do valor a no primeiro terminal. Ele propõe o seguinte dispositivo simples feito de um multiplicador:

(define (squarer a b) (multiplier a a b))

Há uma falha séria nesta ideia. Explique.

Exercício 3.35: Ben Bitdiddle diz a Louis que uma maneira de evitar o problema no Exercício 3.34 é definir um quadrador como uma nova restrição primitiva. Preencha as partes ausentes no esboço de Ben para um procedimento que implementa tal restrição:

(define (squarer a b)
  (define (process-new-value)
    (if (has-value? b)
        (if (< (get-value b) 0)
            (error "square less than 0: 
                    SQUARER" 
                   (get-value b))
            ⟨alternative1⟩)
        ⟨alternative2⟩))
  (define (process-forget-value) ⟨body1⟩)
  (define (me request) ⟨body2⟩)
  ⟨rest of definition⟩
  me)

Exercício 3.36: Suponha que avaliamos a seguinte sequência de expressões no ambiente global:

(define a (make-connector))
(define b (make-connector))
(set-value! a 10 'user)

Em algum momento durante a avaliação de set-value!, a seguinte expressão do procedimento local do conector é avaliada:

(for-each-except 
  setter inform-about-value constraints)

Desenhe um diagrama de ambiente mostrando o ambiente no qual a expressão acima é avaliada.

Exercício 3.37: O procedimento celsius-fahrenheit-converter é incômodo quando comparado com um estilo de definição mais orientado a expressões, como

(define (celsius-fahrenheit-converter x)
  (c+ (c* (c/ (cv 9) (cv 5))
          x)
      (cv 32)))

(define C (make-connector))
(define F (celsius-fahrenheit-converter C))

Aqui c+, c*, etc. são as versões "restritivas" das operações aritméticas. Por exemplo, c+ recebe dois conectores como argumentos e retorna um conector que está relacionado a esses por uma restrição de soma:

(define (c+ x y)
  (let ((z (make-connector)))
    (adder x y z)
    z))

Defina procedimentos análogos c-, c*, c/ e cv (valor constante) que nos permitam definir restrições compostas como no exemplo do conversor acima.¹⁶¹

(v-sum a b temp1)
(v-sum c d temp2)
(v-prod temp1 temp2 answer)

(define answer 
  (v-prod (v-sum a b) (v-sum c d)))