Estrutura e Interpretação de Programas de Computador, 2ª edição: 5.1

⇡

5.1Projetando Máquinas de Registro

Para projetar uma máquina de registro, devemos projetar seus caminhos de dados (registros e operações) e o controlador que sequencia essas operações. Para ilustrar o projeto de uma máquina de registro simples, vamos examinar o Algoritmo de Euclides, que é usado para calcular o máximo divisor comum (MDC) de dois inteiros. Como vimos em 1.2.5, o Algoritmo de Euclides pode ser realizado por um processo iterativo, conforme especificado pelo seguinte procedimento:

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

Uma máquina para realizar esse algoritmo deve acompanhar dois números, $a$ e $b$ , então vamos assumir que esses números são armazenados em dois registros com esses nomes. As operações básicas necessárias são testar se o conteúdo do registro b é zero e calcular o resto da divisão do conteúdo do registro a pelo conteúdo do registro b. A operação de resto é um processo complexo, mas vamos assumir por enquanto que temos um dispositivo primitivo que calcula restos. Em cada ciclo do algoritmo MDC, o conteúdo do registro a deve ser substituído pelo conteúdo do registro b, e o conteúdo de b deve ser substituído pelo resto da divisão do conteúdo antigo de a pelo conteúdo antigo de b. Seria conveniente se essas substituições pudessem ser feitas simultaneamente, mas em nosso modelo de máquinas de registro, assumiremos que apenas um registro pode receber um novo valor a cada passo. Para realizar as substituições, nossa máquina usará um terceiro registro "temporário", que chamaremos de t. (Primeiro, o resto será colocado em t, depois o conteúdo de b será colocado em a, e finalmente o resto armazenado em t será colocado em b.)

Podemos ilustrar os registros e operações necessárias para essa máquina usando o diagrama de caminhos de dados mostrado na Figura 5.1. Neste diagrama, os registros (a, b e t) são representados por retângulos. Cada maneira de atribuir um valor a um registro é indicada por uma seta com um X atrás da cabeça, apontando da fonte de dados para o registro. Podemos pensar no X como um botão que, quando pressionado, permite que o valor na fonte "flua" para o registro designado. O rótulo ao lado de cada botão é o nome que usaremos para nos referir ao botão. Os nomes são arbitrários e podem ser escolhidos para ter valor mnemônico (por exemplo, a<-b denota pressionar o botão que atribui o conteúdo do registro b ao registro a). A fonte de dados para um registro pode ser outro registro (como na atribuição a<-b), o resultado de uma operação (como na atribuição t<-r) ou uma constante (um valor embutido que não pode ser alterado, representado em um diagrama de caminhos de dados por um triângulo contendo a constante).

Figura 5.1: Caminhos de dados para uma máquina MDC.

Uma operação que calcula um valor a partir de constantes e do conteúdo de registros é representada em um diagrama de caminhos de dados por um trapézio contendo um nome para a operação. Por exemplo, a caixa marcada como rem na Figura 5.1 representa uma operação que calcula o resto da divisão do conteúdo dos registros a e b aos quais está conectada. Setas (sem botões) apontam dos registros de entrada e constantes para a caixa, e setas conectam o valor de saída da operação aos registros. Um teste é representado por um círculo contendo um nome para o teste. Por exemplo, nossa máquina MDC tem uma operação que testa se o conteúdo do registro b é zero. Um teste também tem setas de seus registros de entrada e constantes, mas não tem setas de saída; seu valor é usado pelo controlador em vez dos caminhos de dados. No geral, o diagrama de caminhos de dados mostra os registros e operações necessários para a máquina e como eles devem ser conectados. Se visualizarmos as setas como fios e os botões X como interruptores, o diagrama de caminhos de dados é muito semelhante ao diagrama de fiação de uma máquina que poderia ser construída a partir de componentes elétricos.

Para que os caminhos de dados realmente calculem MDCs, os botões devem ser pressionados na sequência correta. Descreveremos essa sequência em termos de um diagrama de controlador, conforme ilustrado na Figura 5.2. Os elementos do diagrama do controlador indicam como os componentes dos caminhos de dados devem ser operados. As caixas retangulares no diagrama do controlador identificam os botões dos caminhos de dados que devem ser pressionados, e as setas descrevem a sequência de um passo para o próximo. O losango no diagrama representa uma decisão. Uma das duas setas de sequência será seguida, dependendo do valor do teste dos caminhos de dados identificado no losango. Podemos interpretar o controlador em termos de uma analogia física: pense no diagrama como um labirinto no qual uma bola está rolando. Quando a bola rola para uma caixa, ela pressiona o botão dos caminhos de dados que é nomeado pela caixa. Quando a bola rola para um nó de decisão (como o teste para b = 0), ela deixa o nó no caminho determinado pelo resultado do teste indicado. Juntos, os caminhos de dados e o controlador descrevem completamente uma máquina para calcular MDCs. Iniciamos o controlador (a bola rolante) no lugar marcado como start, após colocar números nos registros a e b. Quando o controlador atinge done, encontraremos o valor do MDC no registro a.

Figura 5.2: Controlador para uma máquina MDC.

Exercício 5.1: Projete uma máquina de registro para calcular fatoriais usando o algoritmo iterativo especificado pelo seguinte procedimento. Desenhe diagramas de caminhos de dados e controlador para essa máquina.
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

5.1.1Uma Linguagem para Descrever Máquinas de Registro

Diagramas de caminhos de dados e controlador são adequados para representar máquinas simples, como a de MDC, mas são difíceis de usar para descrever máquinas grandes, como um interpretador Lisp. Para possibilitar o trabalho com máquinas complexas, criaremos uma linguagem que apresenta, em forma textual, todas as informações fornecidas pelos diagramas de caminhos de dados e controlador. Começaremos com uma notação que espelha diretamente os diagramas.

Definimos os caminhos de dados de uma máquina descrevendo os registros e as operações. Para descrever um registro, damos a ele um nome e especificamos os botões que controlam a atribuição a ele. Damos a cada um desses botões um nome e especificamos a fonte dos dados que entram no registro sob o controle do botão. (A fonte é um registro, uma constante ou uma operação.) Para descrever uma operação, damos a ela um nome e especificamos suas entradas (registros ou constantes).

Definimos o controlador de uma máquina como uma sequência de instruções junto com rótulos que identificam pontos de entrada na sequência. Uma instrução é uma das seguintes:

O nome de um botão dos caminhos de dados para pressionar e atribuir um valor a um registro. (Isso corresponde a uma caixa no diagrama do controlador.)
Uma instrução test, que realiza um teste especificado.
Um desvio condicional (branch) para um local indicado por um rótulo do controlador, com base no resultado do teste anterior. (O teste e o desvio juntos correspondem a um losango no diagrama do controlador.) Se o teste for falso, o controlador deve continuar com a próxima instrução na sequência. Caso contrário, o controlador deve continuar com a instrução após o rótulo.
Um desvio incondicional (goto) nomeando um rótulo do controlador para continuar a execução.

A máquina começa no início da sequência de instruções do controlador e para quando a execução atinge o final da sequência. Exceto quando um desvio muda o fluxo de controle, as instruções são executadas na ordem em que são listadas.

A Figura 5.3 mostra a máquina MDC descrita dessa forma. Este exemplo apenas sugere a generalidade dessas descrições, já que a máquina MDC é um caso muito simples: cada registro tem apenas um botão, e cada botão e teste é usado apenas uma vez no controlador.

Figura 5.3: $↓$ Uma especificação da máquina MDC.

(data-paths
 (registers
  ((name a)
   (buttons ((name a<-b) 
             (source (register b)))))
  ((name b)
   (buttons ((name b<-t)
             (source (register t)))))
  ((name t)
   (buttons ((name t<-r)
             (source (operation rem))))))
 (operations
  ((name rem)
   (inputs (register a) (register b)))
  ((name =)
   (inputs (register b) (constant 0)))))

(controller
 test-b                ; rótulo
   (test =)            ; teste
   (branch 
    (label gcd-done))  ; desvio condicional
   (t<-r)              ; pressionar botão
   (a<-b)              ; pressionar botão
   (b<-t)              ; pressionar botão
   (goto 
    (label test-b))    ; desvio incondicional
 gcd-done)             ; rótulo

Infelizmente, é difícil ler uma descrição como essa. Para entender as instruções do controlador, devemos constantemente nos referir às definições dos nomes dos botões e das operações, e para entender o que os botões fazem, podemos ter que nos referir às definições dos nomes das operações. Portanto, transformaremos nossa notação para combinar as informações das descrições dos caminhos de dados e do controlador, de modo que possamos ver tudo junto.

Para obter essa forma de descrição, substituiremos os nomes arbitrários dos botões e operações pelas definições de seu comportamento. Ou seja, em vez de dizer (no controlador) "Pressione o botão t<-r" e separadamente dizer (nos caminhos de dados) "O botão t<-r atribui o valor da operação rem ao registro t" e "As entradas da operação rem são os conteúdos dos registros a e b", diremos (no controlador) "Pressione o botão que atribui ao registro t o valor da operação rem sobre os conteúdos dos registros a e b". Da mesma forma, em vez de dizer (no controlador) "Realize o teste =" e separadamente dizer (nos caminhos de dados) "O teste = opera sobre o conteúdo do registro b e a constante 0", diremos "Realize o teste = sobre o conteúdo do registro b e a constante 0". Omitiremos a descrição dos caminhos de dados, deixando apenas a sequência do controlador. Assim, a máquina MDC é descrita da seguinte forma:

(controller
 test-b
   (test (op =) (reg b) (const 0))
   (branch (label gcd-done))
   (assign t (op rem) (reg a) (reg b))
   (assign a (reg b))
   (assign b (reg t))
   (goto (label test-b))
 gcd-done)

Essa forma de descrição é mais fácil de ler do que a ilustrada na Figura 5.3, mas também tem desvantagens:

É mais verbosa para máquinas grandes, porque descrições completas dos elementos dos caminhos de dados são repetidas sempre que os elementos são mencionados na sequência de instruções do controlador. (Isso não é um problema no exemplo do MDC, porque cada operação e botão é usado apenas uma vez.) Além disso, repetir as descrições dos caminhos de dados obscurece a estrutura real dos caminhos de dados da máquina; não é óbvio para uma máquina grande quantos registros, operações e botões existem e como eles estão interconectados.
Como as instruções do controlador em uma definição de máquina se parecem com expressões Lisp, é fácil esquecer que elas não são expressões Lisp arbitrárias. Elas só podem notar operações legais da máquina. Por exemplo, as operações só podem operar diretamente sobre constantes e os conteúdos dos registros, não sobre os resultados de outras operações.

Apesar dessas desvantagens, usaremos essa linguagem de máquina de registro ao longo deste capítulo, porque estaremos mais preocupados em entender os controladores do que em entender os elementos e conexões nos caminhos de dados. Devemos manter em mente, no entanto, que o projeto dos caminhos de dados é crucial no projeto de máquinas reais.

Exercício 5.2: Use a linguagem de máquina de registro para descrever a máquina de fatorial iterativa do Exercício 5.1.

Ações

Vamos modificar a máquina MDC para que possamos digitar os números cujo MDC queremos e obter a resposta impressa no nosso terminal. Não discutiremos como fazer uma máquina que possa ler e imprimir, mas assumiremos (como fazemos quando usamos read e display em Scheme) que elas estão disponíveis como operações primitivas.²⁸⁶

Read é como as operações que temos usado, pois produz um valor que pode ser armazenado em um registro. Mas read não recebe entradas de nenhum registro; seu valor depende de algo que acontece fora das partes da máquina que estamos projetando. Permitiremos que as operações da nossa máquina tenham esse comportamento e, portanto, desenharemos e notaremos o uso de read como fazemos com qualquer outra operação que calcula um valor.

Print, por outro lado, difere das operações que temos usado de uma maneira fundamental: ele não produz um valor de saída para ser armazenado em um registro. Embora tenha um efeito, esse efeito não é sobre uma parte da máquina que estamos projetando. Chamaremos esse tipo de operação de ação. Representaremos uma ação em um diagrama de caminhos de dados da mesma forma que representamos uma operação que calcula um valor—como um trapézio que contém o nome da ação. Setas apontam para a caixa da ação de quaisquer entradas (registros ou constantes). Também associamos um botão à ação. Pressionar o botão faz a ação acontecer. Para fazer o controlador pressionar um botão de ação, usamos um novo tipo de instrução chamado perform. Assim, a ação de imprimir o conteúdo do registro a é representada em uma sequência de controlador pela instrução

(perform (op print) (reg a))

A Figura 5.4 mostra os caminhos de dados e o controlador para a nova máquina MDC. Em vez de fazer a máquina parar após imprimir a resposta, fizemos com que ela recomece, de modo que ela repetidamente lê um par de números, calcula seu MDC e imprime o resultado. Essa estrutura é semelhante aos loops de driver que usamos nos interpretadores do Capítulo 4.

Figura 5.4: Uma máquina MDC que lê entradas e imprime resultados.

5.1.2Abstração no Projeto de Máquinas

Frequentemente definiremos uma máquina para incluir operações "primitivas" que são, na verdade, muito complexas. Por exemplo, em 5.4 e 5.5, trataremos as manipulações de ambiente do Scheme como primitivas. Essa abstração é valiosa porque nos permite ignorar os detalhes de partes de uma máquina para que possamos nos concentrar em outros aspectos do projeto. O fato de termos escondido muita complexidade, no entanto, não significa que o projeto de uma máquina seja irrealista. Sempre podemos substituir as "primitivas" complexas por operações primitivas mais simples.

Considere a máquina MDC. A máquina tem uma instrução que calcula o resto da divisão dos conteúdos dos registros a e b e atribui o resultado ao registro t. Se quisermos construir a máquina MDC sem usar uma operação primitiva de resto, devemos especificar como calcular restos em termos de operações mais simples, como subtração. De fato, podemos escrever um procedimento Scheme que encontra restos dessa forma:

(define (remainder n d)
  (if (< n d)
      n
      (remainder (- n d) d)))

Podemos, portanto, substituir a operação de resto nos caminhos de dados da máquina MDC por uma operação de subtração e um teste de comparação. A Figura 5.5 mostra os caminhos de dados e o controlador para a máquina elaborada. A instrução

(assign t (op rem) (reg a) (reg b))

na definição do controlador do MDC é substituída por uma sequência de instruções que contém um loop, como mostrado na Figura 5.6.

Figura 5.5: Caminhos de dados e controlador para a máquina MDC elaborada.

Figura 5.6: $↓$ Sequência de instruções do controlador para a máquina MDC na Figura 5.5.

(controller
 test-b
   (test (op =) (reg b) (const 0))
   (branch (label gcd-done))
   (assign t (reg a))
 rem-loop
   (test (op <) (reg t) (reg b))
   (branch (label rem-done))
   (assign t (op -) (reg t) (reg b))
   (goto (label rem-loop))
 rem-done
   (assign a (reg b))
   (assign b (reg t))
   (goto (label test-b))
 gcd-done)

Exercício 5.3: Projete uma máquina para calcular raízes quadradas usando o método de Newton, conforme descrito em 1.1.7:
(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))
Comece assumindo que as operações good-enough? e improve estão disponíveis como primitivas. Em seguida, mostre como expandir essas operações em termos de operações aritméticas. Descreva cada versão do projeto da máquina sqrt desenhando um diagrama de caminhos de dados e escrevendo uma definição de controlador na linguagem de máquina de registro.

5.1.3Sub-rotinas

Ao projetar uma máquina para realizar uma computação, muitas vezes preferimos organizar os componentes para que sejam compartilhados por diferentes partes da computação, em vez de duplicar os componentes. Considere uma máquina que inclui duas computações de MDC—uma que encontra o MDC dos conteúdos dos registros a e b e outra que encontra o MDC dos conteúdos dos registros c e d. Podemos começar assumindo que temos uma operação primitiva gcd, então expandir as duas instâncias de gcd em termos de operações mais primitivas. A Figura 5.7 mostra apenas as partes dos caminhos de dados da máquina resultante relacionadas ao MDC, sem mostrar como elas se conectam ao resto da máquina. A figura também mostra as partes correspondentes da sequência de controlador da máquina.

Figura 5.7: Partes dos caminhos de dados e sequência de controlador para uma máquina com duas computações de MDC.

Essa máquina tem duas caixas de operação de resto e duas caixas para testar igualdade. Se os componentes duplicados forem complicados, como a caixa de resto, essa não será uma maneira econômica de construir a máquina. Podemos evitar duplicar os componentes dos caminhos de dados usando os mesmos componentes para ambas as computações de MDC, desde que isso não afete o restante da computação da máquina maior. Se os valores nos registros a e b não forem necessários quando o controlador chegar a gcd-2 (ou se esses valores puderem ser movidos para outros registros para segurança), podemos mudar a máquina para que ela use os registros a e b, em vez dos registros c e d, para calcular o segundo MDC além do primeiro. Se fizermos isso, obteremos a sequência de controlador mostrada na Figura 5.8.

Figura 5.8: $↓$ Partes da sequência de controlador para uma máquina que usa os mesmos componentes dos caminhos de dados para duas computações de MDC diferentes.
gcd-1
 (test (op =) (reg b) (const 0))
 (branch (label after-gcd-1))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd-1))
after-gcd-1
  …
gcd-2
 (test (op =) (reg b) (const 0))
 (branch (label after-gcd-2))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd-2))
after-gcd-2

Removemos os componentes duplicados dos caminhos de dados (de modo que os caminhos de dados são novamente como na Figura 5.1), mas o controlador agora tem duas sequências de MDC que diferem apenas em seus rótulos de ponto de entrada. Seria melhor substituir essas duas sequências por desvios para uma única sequência—uma gcd sub-rotina—no final da qual desviamos de volta para o lugar correto na sequência de instruções principal. Podemos realizar isso da seguinte forma: Antes de desviar para gcd, colocamos um valor distinto (como 0 ou 1) em um registro especial, continue. No final da sub-rotina gcd, retornamos para after-gcd-1 ou after-gcd-2, dependendo do valor do registro continue. A Figura 5.9 mostra a parte relevante da sequência de controlador resultante, que inclui apenas uma cópia das instruções gcd.

Figura 5.9: $↓$ Usando um registro continue para evitar a sequência de controlador duplicada na Figura 5.8.

gcd
 (test (op =) (reg b) (const 0))
 (branch (label gcd-done))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd))
gcd-done
 (test (op =) (reg continue) (const 0))
 (branch (label after-gcd-1))
 (goto (label after-gcd-2))
  …
;; Antes de desviar para gcd do primeiro lugar onde é necessário,
;; colocamos 0 no registro continue
 (assign continue (const 0))
 (goto (label gcd))
after-gcd-1
  …
;; Antes do segundo uso de gcd,
;; colocamos 1 no registro continue
 (assign continue (const 1))
 (goto (label gcd))
after-gcd-2

Essa é uma abordagem razoável para lidar com problemas pequenos, mas seria incômoda se houvesse muitas instâncias de computações de MDC na sequência de controlador. Para decidir onde continuar a execução após a sub-rotina gcd, precisaríamos de testes nos caminhos de dados e instruções de desvio no controlador para todos os lugares que usam gcd. Um método mais poderoso para implementar sub-rotinas é fazer com que o registro continue mantenha o rótulo do ponto de entrada na sequência de controlador onde a execução deve continuar quando a sub-rotina terminar. Implementar essa estratégia requer um novo tipo de conexão entre os caminhos de dados e o controlador de uma máquina de registro: Deve haver uma maneira de atribuir a um registro um rótulo na sequência de controlador de forma que esse valor possa ser recuperado do registro e usado para continuar a execução no ponto de entrada designado.

Para refletir essa capacidade, estenderemos a instrução assign da linguagem de máquina de registro para permitir que um registro seja atribuído como valor um rótulo da sequência de controlador (como um tipo especial de constante). Também estenderemos a instrução goto para permitir que a execução continue no ponto de entrada descrito pelo conteúdo de um registro, em vez de apenas em um ponto de entrada descrito por um rótulo constante. Usando esses novos construtos, podemos terminar a sub-rotina gcd com um desvio para o local armazenado no registro continue. Isso leva à sequência de controlador mostrada na Figura 5.10.

Figura 5.10: $↓$ Atribuir rótulos ao registro continue simplifica e generaliza a estratégia mostrada na Figura 5.9.

gcd
 (test (op =) (reg b) (const 0))
 (branch (label gcd-done))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd))
gcd-done
 (goto (reg continue))
  …
;; Antes de chamar gcd,
;; atribuímos ao continue o rótulo
;; para o qual gcd deve retornar.
 (assign continue (label after-gcd-1))
 (goto (label gcd))
after-gcd-1
  …
;; Aqui está a segunda chamada para gcd,
;; com uma continuação diferente.
 (assign continue (label after-gcd-2))
 (goto (label gcd))
after-gcd-2

Uma máquina com mais de uma sub-rotina poderia usar múltiplos registros de continuação (por exemplo, gcd-continue, factorial-continue) ou poderíamos ter todas as sub-rotinas compartilhando um único registro continue. Compartilhar é mais econômico, mas devemos ter cuidado se tivermos uma sub-rotina (sub1) que chama outra sub-rotina (sub2). A menos que sub1 salve o conteúdo de continue em algum outro registro antes de configurar continue para a chamada a sub2, sub1 não saberá para onde ir quando terminar. O mecanismo desenvolvido na próxima seção para lidar com recursão também fornece uma solução melhor para esse problema de chamadas de sub-rotinas aninhadas.

5.1.4Usando uma Pilha para Implementar Recursão

Com as ideias ilustradas até agora, podemos implementar qualquer processo iterativo especificando uma máquina de registro que tenha um registro correspondente a cada variável de estado do processo. A máquina executa repetidamente um loop de controlador, alterando o conteúdo dos registros, até que alguma condição de término seja satisfeita. Em cada ponto da sequência de controlador, o estado da máquina (representando o estado do processo iterativo) é completamente determinado pelo conteúdo dos registros (os valores das variáveis de estado).

Implementar processos recursivos, no entanto, requer um mecanismo adicional. Considere o seguinte método recursivo para calcular fatoriais, que examinamos pela primeira vez em 1.2.1:

(define (factorial n)
  (if (= n 1) 
      1
      (* (factorial (- n 1)) n)))

Como vemos no procedimento, calcular $n!$ requer calcular $(n - 1)!$ . Nossa máquina MDC, modelada no procedimento

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

da mesma forma teve que calcular outro MDC. Mas há uma diferença importante entre o procedimento gcd, que reduz a computação original a uma nova computação de MDC, e factorial, que requer calcular outro fatorial como um subproblema. Em MDC, a resposta para a nova computação de MDC é a resposta para o problema original. Para calcular o próximo MDC, simplesmente colocamos os novos argumentos nos registros de entrada da máquina MDC e reutilizamos os caminhos de dados da máquina executando a mesma sequência de controlador. Quando a máquina termina de resolver o problema final de MDC, ela concluiu toda a computação.

No caso de fatorial (ou qualquer processo recursivo), a resposta para o novo subproblema de fatorial não é a resposta para o problema original. O valor obtido para $(n - 1)!$ deve ser multiplicado por $n$ para obter a resposta final. Se tentarmos imitar o projeto do MDC e resolver o subproblema de fatorial decrementando o registro n e reexecutando a máquina de fatorial, não teremos mais disponível o valor antigo de n pelo qual multiplicar o resultado. Precisamos, portanto, de uma segunda máquina de fatorial para trabalhar no subproblema. Essa segunda computação de fatorial tem, por sua vez, um subproblema de fatorial, que requer uma terceira máquina de fatorial, e assim por diante. Como cada máquina de fatorial contém outra máquina de fatorial dentro dela, a máquina total contém um ninho infinito de máquinas semelhantes e, portanto, não pode ser construída a partir de um número fixo e finito de partes.

No entanto, podemos implementar o processo de fatorial como uma máquina de registro se pudermos organizar para usar os mesmos componentes para cada instância aninhada da máquina. Especificamente, a máquina que calcula $n!$ deve usar os mesmos componentes para trabalhar no subproblema de calcular $(n - 1)!$ , no subproblema para $(n - 2)!$ , e assim por diante. Isso é plausível porque, embora o processo de fatorial exija que um número ilimitado de cópias da mesma máquina sejam necessárias para realizar uma computação, apenas uma dessas cópias precisa estar ativa a qualquer momento. Quando a máquina encontra um subproblema recursivo, ela pode suspender o trabalho no problema principal, reutilizar as mesmas partes físicas para trabalhar no subproblema e, em seguida, continuar a computação suspensa.

No subproblema, o conteúdo dos registros será diferente do que era no problema principal. (Nesse caso, o registro n é decrementado.) Para poder continuar a computação suspensa, a máquina deve salvar o conteúdo de quaisquer registros que serão necessários após o subproblema ser resolvido, para que esses valores possam ser restaurados para continuar a computação suspensa. No caso de fatorial, salvaremos o valor antigo de n, para ser restaurado quando terminarmos de calcular o fatorial do registro n decrementado.²⁸⁷

Como não há limite a priori para a profundidade de chamadas recursivas aninhadas, podemos precisar salvar um número arbitrário de valores de registros. Esses valores devem ser restaurados na ordem inversa àquela em que foram salvos, já que em um ninho de recursões o último subproblema a ser entrado é o primeiro a ser concluído. Isso dita o uso de uma pilha, ou estrutura de dados "último a entrar, primeiro a sair", para salvar os valores dos registros. Podemos estender a linguagem de máquina de registro para incluir uma pilha adicionando dois tipos de instruções: Valores são colocados na pilha usando uma instrução save e restaurados da pilha usando uma instrução restore. Após uma sequência de valores ter sido saved na pilha, uma sequência de restores recuperará esses valores na ordem inversa.²⁸⁸

Com a ajuda da pilha, podemos reutilizar uma única cópia dos caminhos de dados da máquina de fatorial para cada subproblema de fatorial. Há uma questão de projeto semelhante na reutilização da sequência de controlador que opera os caminhos de dados. Para reexecutar a computação de fatorial, o controlador não pode simplesmente voltar ao início, como em um processo iterativo, porque após resolver o subproblema de $(n - 1)!$ , a máquina ainda deve multiplicar o resultado por $n$ . O controlador deve suspender sua computação de $n!$ , resolver o subproblema de $(n - 1)!$ , e então continuar sua computação de $n!$ . Essa visão da computação de fatorial sugere o uso do mecanismo de sub-rotina descrito em 5.1.3, que faz o controlador usar um registro continue para transferir para a parte da sequência que resolve um subproblema e, em seguida, continuar de onde parou no problema principal. Podemos, portanto, fazer uma sub-rotina de fatorial que retorna ao ponto de entrada armazenado no registro continue. Em torno de cada chamada de sub-rotina, salvamos e restauramos continue assim como fazemos com o registro n, já que cada "nível" da computação de fatorial usará o mesmo registro continue. Ou seja, a sub-rotina de fatorial deve colocar um novo valor em continue quando chama a si mesma para um subproblema, mas precisará do valor antigo para retornar ao lugar que a chamou para resolver um subproblema.

A Figura 5.11 mostra os caminhos de dados e o controlador para uma máquina que implementa o procedimento recursivo factorial. A máquina tem uma pilha e três registros, chamados n, val e continue. Para simplificar o diagrama de caminhos de dados, não nomeamos os botões de atribuição de registros, apenas os botões de operação de pilha (sc e sn para salvar registros, rc e rn para restaurar registros). Para operar a máquina, colocamos no registro n o número cujo fatorial desejamos calcular e iniciamos a máquina. Quando a máquina atinge fact-done, a computação é concluída e a resposta será encontrada no registro val. Na sequência de controlador, n e continue são salvos antes de cada chamada recursiva e restaurados após o retorno da chamada. O retorno de uma chamada é realizado desviando para o local armazenado em continue. Continue é inicializado quando a máquina é iniciada para que o último retorno vá para fact-done. O registro val, que contém o resultado da computação de fatorial, não é salvo antes da chamada recursiva, porque o conteúdo antigo de val não é útil após o retorno da sub-rotina. Apenas o novo valor, que é o valor produzido pela subcomputação, é necessário.

Figura 5.11: Uma máquina de fatorial recursiva.

Embora, em princípio, a computação de fatorial exija uma máquina infinita, a máquina na Figura 5.11 é, na verdade, finita, exceto pela pilha, que é potencialmente ilimitada. Qualquer implementação física de uma pilha, no entanto, terá um tamanho finito, e isso limitará a profundidade de chamadas recursivas que podem ser tratadas pela máquina. Essa implementação de fatorial ilustra a estratégia geral para realizar algoritmos recursivos como máquinas de registro comuns aumentadas por pilhas. Quando um subproblema recursivo é encontrado, salvamos na pilha os registros cujos valores atuais serão necessários após o subproblema ser resolvido, resolvemos o subproblema recursivo e, em seguida, restauramos os registros salvos e continuamos a execução no problema principal. O registro continue deve sempre ser salvo. Se há outros registros que precisam ser salvos depende da máquina específica, já que nem todas as computações recursivas precisam dos valores originais dos registros que são modificados durante a solução do subproblema (veja Exercício 5.4).

Uma dupla recursão

Vamos examinar um processo recursivo mais complexo, a computação recursiva em árvore dos números de Fibonacci, que introduzimos em 1.2.2:

(define (fib n)
  (if (< n 2) 
      n 
      (+ (fib (- n 1)) (fib (- n 2)))))

Assim como com fatorial, podemos implementar a computação recursiva de Fibonacci como uma máquina de registro com registros n, val e continue. A máquina é mais complexa que a de fatorial, porque há dois lugares na sequência de controlador onde precisamos realizar chamadas recursivas—uma para calcular $Fib (n - 1)$ e outra para calcular $Fib (n - 2)$ . Para configurar cada uma dessas chamadas, salvamos os registros cujos valores serão necessários posteriormente, definimos o registro n para o número cujo Fib precisamos calcular recursivamente ( $n - 1$ ou $n - 2$ ), e atribuímos ao continue o ponto de entrada na sequência principal para o qual retornar (afterfib-n-1 ou afterfib-n-2, respectivamente). Em seguida, vamos para fib-loop. Quando retornamos da chamada recursiva, a resposta está em val. A Figura 5.12 mostra a sequência de controlador para essa máquina.

Figura 5.12: $↓$ Controlador para uma máquina que calcula números de Fibonacci.

(controller
   (assign continue (label fib-done))
 fib-loop
   (test (op <) (reg n) (const 2))
   (branch (label immediate-answer))
   ;; configurar para calcular Fib(n − 1)
   (save continue)
   (assign continue (label afterfib-n-1))
   (save n)           ; salvar o valor antigo de n
   (assign n 
           (op -)
           (reg n)
           (const 1)) ; sobrescrever n para n-1
   (goto 
    (label fib-loop)) ; realizar chamada recursiva
 afterfib-n-1 ; ao retornar, val contém Fib(n − 1)
   (restore n)
   (restore continue)
   ;; configurar para calcular Fib(n − 2)
   (assign n (op -) (reg n) (const 2))
   (save continue)
   (assign continue (label afterfib-n-2))
   (save val)         ; salvar Fib(n − 1)
   (goto (label fib-loop))
 afterfib-n-2 ; ao retornar, val contém Fib(n − 2)
   (assign n 
           (reg val)) ; n agora contém Fib(n − 2)
   (restore val)      ; val agora contém Fib(n − 1)
   (restore continue)
   (assign val        ; Fib(n − 1) + Fib(n − 2)
           (op +) 
           (reg val)
           (reg n))
   (goto              ; retornar ao chamador,
    (reg continue))   ; a resposta está em val
 immediate-answer
   (assign val 
           (reg n))   ; caso base: Fib(n) = n
   (goto (reg continue))
 fib-done)

Exercício 5.4: Especifique máquinas de registro que implementem cada um dos seguintes procedimentos. Para cada máquina, escreva uma sequência de instruções de controlador e desenhe um diagrama mostrando os caminhos de dados.
Exponenciação recursiva:
(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))
Exponenciação iterativa:
(define (expt b n)
  (define (expt-iter counter product)
    (if (= counter 0)
        product
        (expt-iter (- counter 1)
                   (* b product))))
  (expt-iter n 1))

Exercício 5.5: Simule manualmente as máquinas de fatorial e Fibonacci, usando alguma entrada não trivial (exigindo a execução de pelo menos uma chamada recursiva). Mostre o conteúdo da pilha em cada ponto significativo da execução.

Exercício 5.6: Ben Bitdiddle observa que a sequência de controlador da máquina de Fibonacci tem um save e um restore extras, que podem ser removidos para fazer uma máquina mais rápida. Onde estão essas instruções?

5.1.5Resumo das Instruções

Uma instrução de controlador em nossa linguagem de máquina de registro tem uma das seguintes formas, onde cada $⟨ i n p u t_{i} ⟩$ é (reg ⟨nome-do-registro⟩) ou (const ⟨valor-constante⟩). Essas instruções foram introduzidas em 5.1.1:

(assign ⟨nome-do-registro⟩ (reg ⟨nome-do-registro⟩))
(assign ⟨nome-do-registro⟩ 
        (const ⟨valor-constante⟩))
(assign ⟨nome-do-registro⟩ 
        (op ⟨nome-da-operação⟩) 
        ⟨input₁⟩ … ⟨inputₙ⟩)
(perform (op ⟨nome-da-operação⟩) 
         ⟨input₁⟩ 
         … 
         ⟨inputₙ⟩)
(test (op ⟨nome-da-operação⟩) 
      ⟨input₁⟩ 
      … 
      ⟨inputₙ⟩)
(branch (label ⟨nome-do-rótulo⟩))
(goto (label ⟨nome-do-rótulo⟩))

O uso de registros para armazenar rótulos foi introduzido em 5.1.3:

(assign ⟨nome-do-registro⟩ (label ⟨nome-do-rótulo⟩))
(goto (reg ⟨nome-do-registro⟩))

As instruções para usar a pilha foram introduzidas em 5.1.4:

(save ⟨nome-do-registro⟩)
(restore ⟨nome-do-registro⟩)

O único tipo de ⟨valor-constante⟩ que vimos até agora é um número, mas mais tarde usaremos strings, símbolos e listas. Por exemplo,
(const "abc") é a string "abc",
(const abc) é o símbolo abc,
(const (a b c)) é a lista (a b c),
e (const ()) é a lista vazia.

Notas de rodapé

²⁸⁶ Essa suposição ignora uma grande quantidade de complexidade. Normalmente, uma grande parte da implementação de um sistema Lisp é dedicada a fazer a leitura e impressão funcionarem.

²⁸⁷ Pode-se argumentar que não precisamos salvar o valor antigo de n; após decrementá-lo e resolver o subproblema, poderíamos simplesmente incrementá-lo para recuperar o valor antigo. Embora essa estratégia funcione para fatorial, ela não pode funcionar em geral, já que o valor antigo de um registro nem sempre pode ser calculado a partir do novo.

²⁸⁸ Em 5.3 veremos como implementar uma pilha em termos de operações mais primitivas.