5.4O Avaliador de Controle Explícito

Em 5.1, vimos como transformar programas simples em Scheme em descrições de máquinas de registradores. Agora realizaremos essa transformação em um programa mais complexo, o avaliador metacircular de 4.1.1–4.1.4, que mostra como o comportamento de um interpretador Scheme pode ser descrito em termos dos procedimentos eval e apply. O avaliador de controle explícito que desenvolvemos nesta seção mostra como os mecanismos subjacentes de chamada de procedimentos e passagem de argumentos usados no processo de avaliação podem ser descritos em termos de operações em registradores e pilhas. Além disso, o avaliador de controle explícito pode servir como uma implementação de um interpretador Scheme, escrito em uma linguagem muito semelhante à linguagem de máquina nativa de computadores convencionais. O avaliador pode ser executado pelo simulador de máquina de registradores de 5.2. Alternativamente, ele pode ser usado como ponto de partida para construir uma implementação em linguagem de máquina de um avaliador Scheme, ou até mesmo uma máquina de propósito específico para avaliar expressões Scheme. Figura 5.16 mostra uma implementação em hardware: um chip de silício que age como um avaliador para Scheme. Os designers do chip começaram com as especificações de caminho de dados e controlador para uma máquina de registradores semelhante ao avaliador descrito nesta seção e usaram programas de automação de design para construir o layout do circuito integrado.³⁰⁴

Registradores e operações

No projeto do avaliador de controle explícito, devemos especificar as operações a serem usadas em nossa máquina de registradores. Descrevemos o avaliador metacircular em termos de sintaxe abstrata, usando procedimentos como quoted? e make-procedure. Na implementação da máquina de registradores, poderíamos expandir esses procedimentos em sequências de operações elementares de memória de estrutura de lista e implementar essas operações em nossa máquina de registradores. No entanto, isso tornaria nosso avaliador muito longo, obscurecendo a estrutura básica com detalhes. Para esclarecer a apresentação, incluiremos como operações primitivas da máquina de registradores os procedimentos de sintaxe dados em 4.1.2 e os procedimentos para representar ambientes e outros dados de tempo de execução dados nas seções 4.1.3 e 4.1.4. Para especificar completamente um avaliador que possa ser programado em uma linguagem de máquina de baixo nível ou implementado em hardware, substituiríamos essas operações por operações mais elementares, usando a implementação de estrutura de lista que descrevemos em 5.3.

Nossa máquina de registradores do avaliador Scheme inclui uma pilha e sete registradores: exp, env, val, continue, proc, argl e unev. Exp é usado para manter a expressão a ser avaliada, e env contém o ambiente no qual a avaliação deve ser realizada. No final de uma avaliação, val contém o valor obtido ao avaliar a expressão no ambiente designado. O registrador continue é usado para implementar recursão, como explicado em 5.1.4. (O avaliador precisa chamar a si mesmo recursivamente, pois avaliar uma expressão requer avaliar suas subexpressões.) Os registradores proc, argl e unev são usados na avaliação de combinações.

Não forneceremos um diagrama de caminho de dados para mostrar como os registradores e operações do avaliador estão conectados, nem daremos a lista completa de operações da máquina. Esses são implícitos no controlador do avaliador, que será apresentado em detalhes.

5.4.1O Núcleo do Avaliador de Controle Explícito

O elemento central no avaliador é a sequência de instruções que começa em eval-dispatch. Isso corresponde ao procedimento eval do avaliador metacircular descrito em 4.1.1. Quando o controlador começa em eval-dispatch, ele avalia a expressão especificada por exp no ambiente especificado por env. Quando a avaliação é concluída, o controlador irá para o ponto de entrada armazenado em continue, e o registrador val conterá o valor da expressão. Assim como no eval metacircular, a estrutura de eval-dispatch é uma análise de caso no tipo sintático da expressão a ser avaliada.³⁰⁵

eval-dispatch
  (test (op self-evaluating?) (reg exp))
  (branch (label ev-self-eval))
  (test (op variable?) (reg exp))
  (branch (label ev-variable))
  (test (op quoted?) (reg exp))
  (branch (label ev-quoted))
  (test (op assignment?) (reg exp))
  (branch (label ev-assignment))
  (test (op definition?) (reg exp))
  (branch (label ev-definition))
  (test (op if?) (reg exp))
  (branch (label ev-if))
  (test (op lambda?) (reg exp))
  (branch (label ev-lambda))
  (test (op begin?) (reg exp))
  (branch (label ev-begin))
  (test (op application?) (reg exp))
  (branch (label ev-application))
  (goto (label unknown-expression-type))

Avaliando expressões simples

Números e strings (que são autoavaliados), variáveis, citações e expressões lambda não têm subexpressões a serem avaliadas. Para essas, o avaliador simplesmente coloca o valor correto no registrador val e continua a execução no ponto de entrada especificado por continue. A avaliação de expressões simples é realizada pelo seguinte código do controlador:

ev-self-eval
  (assign val (reg exp))
  (goto (reg continue))
ev-variable
  (assign val
          (op lookup-variable-value)
          (reg exp)
          (reg env))
  (goto (reg continue))
ev-quoted
  (assign val
          (op text-of-quotation)
          (reg exp))
  (goto (reg continue))
ev-lambda
  (assign unev
          (op lambda-parameters)
          (reg exp))
  (assign exp 
          (op lambda-body)
          (reg exp))
  (assign val 
          (op make-procedure)
          (reg unev)
          (reg exp)
          (reg env))
  (goto (reg continue))

Observe como ev-lambda usa os registradores unev e exp para manter os parâmetros e o corpo da expressão lambda, para que possam ser passados para a operação make-procedure, junto com o ambiente em env.

Avaliando aplicações de procedimentos

Uma aplicação de procedimento é especificada por uma combinação contendo um operador e operandos. O operador é uma subexpressão cujo valor é um procedimento, e os operandos são subexpressões cujos valores são os argumentos aos quais o procedimento deve ser aplicado. O eval metacircular lida com aplicações chamando a si mesmo recursivamente para avaliar cada elemento da combinação e, em seguida, passando os resultados para apply, que realiza a aplicação real do procedimento. O avaliador de controle explícito faz a mesma coisa; essas chamadas recursivas são implementadas por instruções goto, juntamente com o uso da pilha para salvar registradores que serão restaurados após o retorno da chamada recursiva. Antes de cada chamada, teremos o cuidado de identificar quais registradores devem ser salvos (porque seus valores serão necessários posteriormente).³⁰⁶

Começamos a avaliação de uma aplicação avaliando o operador para produzir um procedimento, que será aplicado posteriormente aos operandos avaliados. Para avaliar o operador, movemos ele para o registrador exp e vamos para eval-dispatch. O ambiente no registrador env já é o correto para avaliar o operador. No entanto, salvamos env porque precisaremos dele mais tarde para avaliar os operandos. Também extraímos os operandos em unev e salvamos isso na pilha. Configuramos continue para que eval-dispatch retome em ev-appl-did-operator após o operador ter sido avaliado. Primeiro, no entanto, salvamos o valor antigo de continue, que diz ao controlador onde continuar após a aplicação.

ev-application
  (save continue)
  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))
  (assign continue (label ev-appl-did-operator))
  (goto (label eval-dispatch))

Ao retornar da avaliação da subexpressão do operador, prosseguimos para avaliar os operandos da combinação e acumular os argumentos resultantes em uma lista, mantida em argl. Primeiro, restauramos os operandos não avaliados e o ambiente. Inicializamos argl como uma lista vazia. Em seguida, atribuímos ao registrador proc o procedimento que foi produzido pela avaliação do operador. Se não houver operandos, vamos diretamente para apply-dispatch. Caso contrário, salvamos proc na pilha e iniciamos o loop de avaliação de argumentos:³⁰⁷

ev-appl-did-operator
  (restore unev)             ; os operandos
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))    ; o operador
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))
  (save proc)

Cada ciclo do loop de avaliação de argumentos avalia um operando da lista em unev e acumula o resultado em argl. Para avaliar um operando, colocamos ele no registrador exp e vamos para eval-dispatch, após configurar continue para que a execução retome com a fase de acumulação de argumentos. Mas primeiro salvamos os argumentos acumulados até agora (mantidos em argl), o ambiente (mantido em env) e os operandos restantes a serem avaliados (mantidos em unev). Um caso especial é feito para a avaliação do último operando, que é tratado em ev-appl-last-arg.

ev-appl-operand-loop
  (save argl)
  (assign exp
          (op first-operand)
          (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)
  (assign continue 
          (label ev-appl-accumulate-arg))
  (goto (label eval-dispatch))

Quando um operando foi avaliado, o valor é acumulado na lista mantida em argl. O operando é então removido da lista de operandos não avaliados em unev, e a avaliação de argumentos continua.

ev-appl-accumulate-arg
  (restore unev)
  (restore env)
  (restore argl)
  (assign argl 
          (op adjoin-arg)
          (reg val)
          (reg argl))
  (assign unev
          (op rest-operands)
          (reg unev))
  (goto (label ev-appl-operand-loop))

A avaliação do último argumento é tratada de forma diferente. Não há necessidade de salvar o ambiente ou a lista de operandos não avaliados antes de ir para eval-dispatch, pois eles não serão necessários após o último operando ser avaliado. Assim, retornamos da avaliação para um ponto de entrada especial ev-appl-accum-last-arg, que restaura a lista de argumentos, acumula o novo argumento, restaura o procedimento salvo e vai para realizar a aplicação.³⁰⁸

ev-appl-last-arg
  (assign continue 
          (label ev-appl-accum-last-arg))
  (goto (label eval-dispatch))
ev-appl-accum-last-arg
  (restore argl)
  (assign argl 
          (op adjoin-arg)
          (reg val)
          (reg argl))
  (restore proc)
  (goto (label apply-dispatch))

Os detalhes do loop de avaliação de argumentos determinam a ordem em que o interpretador avalia os operandos de uma combinação (por exemplo, da esquerda para a direita ou da direita para a esquerda—veja Exercício 3.8). Essa ordem não é determinada pelo avaliador metacircular, que herda sua estrutura de controle do Scheme subjacente no qual é implementado.³⁰⁹ Como o seletor first-operand (usado em ev-appl-operand-loop para extrair operandos sucessivos de unev) é implementado como car e o seletor rest-operands é implementado como cdr, o avaliador de controle explícito avaliará os operandos de uma combinação na ordem da esquerda para a direita.

Aplicação de procedimentos

O ponto de entrada apply-dispatch corresponde ao procedimento apply do avaliador metacircular. Quando chegamos a apply-dispatch, o registrador proc contém o procedimento a ser aplicado e argl contém a lista de argumentos avaliados aos quais ele deve ser aplicado. O valor salvo de continue (originalmente passado para eval-dispatch e salvo em ev-application), que diz onde retornar com o resultado da aplicação do procedimento, está na pilha. Quando a aplicação é concluída, o controlador transfere para o ponto de entrada especificado pelo continue salvo, com o resultado da aplicação em val. Assim como no apply metacircular, há dois casos a considerar. Ou o procedimento a ser aplicado é primitivo ou é um procedimento composto.

apply-dispatch
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-apply))
  (test (op compound-procedure?) (reg proc))
  (branch (label compound-apply))
  (goto (label unknown-procedure-type))

Assumimos que cada primitiva é implementada de forma a obter seus argumentos de argl e colocar seu resultado em val. Para especificar como a máquina lida com as primitivas, teríamos que fornecer uma sequência de instruções do controlador para implementar cada primitiva e organizar para que primitive-apply despache para as instruções da primitiva identificada pelo conteúdo de proc. Como estamos interessados na estrutura do processo de avaliação, em vez dos detalhes das primitivas, usaremos uma operação apply-primitive-procedure que aplica o procedimento em proc aos argumentos em argl. Para o propósito de simular o avaliador com o simulador de 5.2, usamos o procedimento apply-primitive-procedure, que chama o sistema Scheme subjacente para realizar a aplicação, assim como fizemos para o avaliador metacircular em 4.1.4. Após calcular o valor da aplicação primitiva, restauramos continue e vamos para o ponto de entrada designado.

primitive-apply
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
  (restore continue)
  (goto (reg continue))

Para aplicar um procedimento composto, procedemos exatamente como no avaliador metacircular. Construímos um quadro que vincula os parâmetros do procedimento aos argumentos, usamos esse quadro para estender o ambiente carregado pelo procedimento e avaliamos nesse ambiente estendido a sequência de expressões que forma o corpo do procedimento. Ev-sequence, descrito abaixo em 5.4.2, lida com a avaliação da sequência.

compound-apply
  (assign unev 
          (op procedure-parameters)
          (reg proc))
  (assign env
          (op procedure-environment)
          (reg proc))
  (assign env
          (op extend-environment)
          (reg unev)
          (reg argl)
          (reg env))
  (assign unev
          (op procedure-body)
          (reg proc))
  (goto (label ev-sequence))

Compound-apply é o único lugar no interpretador onde o registrador env recebe um novo valor. Assim como no avaliador metacircular, o novo ambiente é construído a partir do ambiente carregado pelo procedimento, juntamente com a lista de argumentos e a lista correspondente de variáveis a serem vinculadas.

5.4.2Avaliação de Sequência e Recursão em Cauda

A parte do avaliador de controle explícito em ev-sequence é análoga ao procedimento eval-sequence do avaliador metacircular. Ele lida com sequências de expressões em corpos de procedimentos ou em expressões begin explícitas.

Expressões begin explícitas são avaliadas colocando a sequência de expressões a serem avaliadas em unev, salvando continue na pilha e pulando para ev-sequence.

ev-begin
  (assign unev
          (op begin-actions)
          (reg exp))
  (save continue)
  (goto (label ev-sequence))

As sequências implícitas em corpos de procedimentos são tratadas pulando para ev-sequence a partir de compound-apply, momento em que continue já está na pilha, tendo sido salvo em ev-application.

As entradas em ev-sequence e ev-sequence-continue formam um loop que avalia sucessivamente cada expressão em uma sequência. A lista de expressões não avaliadas é mantida em unev. Antes de avaliar cada expressão, verificamos se há mais expressões a serem avaliadas na sequência. Se houver, salvamos o restante das expressões não avaliadas (mantidas em unev) e o ambiente no qual elas devem ser avaliadas (mantido em env) e chamamos eval-dispatch para avaliar a expressão. Os dois registradores salvos são restaurados ao retornar dessa avaliação, em ev-sequence-continue.

A expressão final na sequência é tratada de forma diferente, no ponto de entrada ev-sequence-last-exp. Como não há mais expressões a serem avaliadas após esta, não precisamos salvar unev ou env antes de ir para eval-dispatch. O valor de toda a sequência é o valor da última expressão, então após a avaliação da última expressão, não há mais nada a fazer, exceto continuar no ponto de entrada atualmente mantido na pilha (que foi salvo por ev-application ou ev-begin). Em vez de configurar continue para arranjar que eval-dispatch retorne aqui e então restaurar continue da pilha e continuar nesse ponto de entrada, restauramos continue da pilha antes de ir para eval-dispatch, para que eval-dispatch continue nesse ponto de entrada após avaliar a expressão.

ev-sequence
  (assign exp (op first-exp) (reg unev))
  (test (op last-exp?) (reg unev))
  (branch (label ev-sequence-last-exp))
  (save unev)
  (save env)
  (assign continue
          (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev
          (op rest-exps)
          (reg unev))
  (goto (label ev-sequence))
ev-sequence-last-exp
  (restore continue)
  (goto (label eval-dispatch))

Recursão em cauda

Em Capítulo 1, dissemos que o processo descrito por um procedimento como

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x))

é um processo iterativo. Embora o procedimento seja sintaticamente recursivo (definido em termos de si mesmo), não é logicamente necessário que um avaliador salve informações ao passar de uma chamada para sqrt-iter para a próxima.³¹⁰ Um avaliador que pode executar um procedimento como sqrt-iter sem exigir armazenamento crescente à medida que o procedimento continua a chamar a si mesmo é chamado de avaliador de recursão em cauda. A implementação metacircular do avaliador em Capítulo 4 não especifica se o avaliador é de recursão em cauda, porque esse avaliador herda seu mecanismo para salvar estado do Scheme subjacente. Com o avaliador de controle explícito, no entanto, podemos rastrear o processo de avaliação para ver quando as chamadas de procedimento causam um acúmulo líquido de informações na pilha.

Nosso avaliador é de recursão em cauda, porque, para avaliar a expressão final de uma sequência, transferimos diretamente para eval-dispatch sem salvar nenhuma informação na pilha. Portanto, avaliar a expressão final em uma sequência—mesmo que seja uma chamada de procedimento (como em sqrt-iter, onde a expressão if, que é a última expressão no corpo do procedimento, reduz-se a uma chamada para sqrt-iter)—não causará nenhum acúmulo de informações na pilha.³¹¹

Se não pensássemos em aproveitar o fato de que não era necessário salvar informações nesse caso, poderíamos ter implementado eval-sequence tratando todas as expressões em uma sequência da mesma forma—salvando os registradores, avaliando a expressão, retornando para restaurar os registradores e repetindo isso até que todas as expressões tenham sido avaliadas:³¹²

ev-sequence
  (test (op no-more-exps?) (reg unev))
  (branch (label ev-sequence-end))
  (assign exp (op first-exp) (reg unev))
  (save unev)
  (save env)
  (assign continue
          (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-end
  (restore continue)
  (goto (reg continue))

Isso pode parecer uma pequena mudança em relação ao nosso código anterior para avaliação de uma sequência: a única diferença é que passamos pelo ciclo de salvar-restaurar para a última expressão em uma sequência, assim como para as outras. O interpretador ainda dará o mesmo valor para qualquer expressão. Mas essa mudança é fatal para a implementação de recursão em cauda, porque agora devemos retornar após avaliar a expressão final em uma sequência para desfazer os salvamentos (inúteis) de registradores. Esses salvamentos extras se acumularão durante uma aninhamento de chamadas de procedimentos. Consequentemente, processos como sqrt-iter exigirão espaço proporcional ao número de iterações, em vez de exigir espaço constante. Essa diferença pode ser significativa. Por exemplo, com recursão em cauda, um loop infinito pode ser expresso usando apenas o mecanismo de chamada de procedimento:

(define (count n)
  (newline)
  (display n)
  (count (+ n 1)))

Sem recursão em cauda, tal procedimento eventualmente ficaria sem espaço na pilha, e expressar uma verdadeira iteração exigiria algum mecanismo de controle diferente de chamada de procedimento.

5.4.3Condicionais, Atribuições e Definições

Assim como no avaliador metacircular, formas especiais são tratadas avaliando seletivamente fragmentos da expressão. Para uma expressão if, devemos avaliar o predicado e decidir, com base no valor do predicado, se avaliamos o consequente ou a alternativa.

Antes de avaliar o predicado, salvamos a expressão if em si para que possamos extrair posteriormente o consequente ou a alternativa. Também salvamos o ambiente, que precisaremos mais tarde para avaliar o consequente ou a alternativa, e salvamos continue, que precisaremos mais tarde para retornar à avaliação da expressão que está esperando o valor do if.

ev-if
  (save exp)   ; salvar a expressão para depois
  (save env)
  (save continue)
  (assign continue (label ev-if-decide))
  (assign exp (op if-predicate) (reg exp))
  ; avaliar o predicado:
  (goto (label eval-dispatch))

Quando retornamos da avaliação do predicado, testamos se ele era verdadeiro ou falso e, dependendo do resultado, colocamos o consequente ou a alternativa em exp antes de ir para eval-dispatch. Observe que restaurar env e continue aqui configura eval-dispatch para ter o ambiente correto e continuar no lugar certo para receber o valor da expressão if.

ev-if-decide
  (restore continue)
  (restore env)
  (restore exp)
  (test (op true?) (reg val))
  (branch (label ev-if-consequent))
ev-if-alternative
  (assign exp (op if-alternative) (reg exp))
  (goto (label eval-dispatch))
ev-if-consequent
  (assign exp (op if-consequent) (reg exp))
  (goto (label eval-dispatch))

Atribuições e definições

Atribuições são tratadas por ev-assignment, que é alcançado a partir de eval-dispatch com a expressão de atribuição em exp. O código em ev-assignment primeiro avalia a parte do valor da expressão e, em seguida, instala o novo valor no ambiente. Set-variable-value! é assumido como uma operação de máquina disponível.

ev-assignment
  (assign unev 
          (op assignment-variable)
          (reg exp))
  (save unev)   ; salvar a variável para depois
  (assign exp
          (op assignment-value)
          (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-assignment-1))
  ; avaliar o valor da atribuição:
  (goto (label eval-dispatch))  
ev-assignment-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform (op set-variable-value!)
           (reg unev)
           (reg val)
           (reg env))
  (assign val (const ok))
  (goto (reg continue))

Definições são tratadas de forma semelhante:

ev-definition
  (assign unev 
          (op definition-variable)
          (reg exp))
  (save unev)   ; salvar a variável para depois
  (assign exp 
          (op definition-value)
          (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-definition-1))
  ; avaliar o valor da definição:
  (goto (label eval-dispatch))  
ev-definition-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform (op define-variable!)
           (reg unev)
           (reg val)
           (reg env))
  (assign val (const ok))
  (goto (reg continue))

Exercício 5.23: Estenda o avaliador para lidar com expressões derivadas como cond, let e assim por diante (4.1.2). Você pode “trapacear” e assumir que os transformadores de sintaxe como cond->if estão disponíveis como operações de máquina.³¹³

Exercício 5.24: Implemente cond como uma nova forma especial básica sem reduzi-la a if. Você terá que construir um loop que testa os predicados de cláusulas cond sucessivas até encontrar uma que seja verdadeira e, em seguida, usar ev-sequence para avaliar as ações da cláusula.

Exercício 5.25: Modifique o avaliador para que ele use avaliação em ordem normal, baseada no avaliador preguiçoso de 4.2.

5.4.4Executando o Avaliador

Com a implementação do avaliador de controle explícito, chegamos ao final de um desenvolvimento, iniciado em Capítulo 1, no qual exploramos modelos sucessivamente mais precisos do processo de avaliação. Começamos com o modelo de substituição relativamente informal, depois estendemos isso em Capítulo 3 para o modelo de ambiente, que nos permitiu lidar com estado e mudança. No avaliador metacircular de Capítulo 4, usamos o próprio Scheme como uma linguagem para tornar mais explícita a estrutura de ambiente construída durante a avaliação de uma expressão. Agora, com máquinas de registradores, demos uma olhada mais de perto nos mecanismos do avaliador para gerenciamento de armazenamento, passagem de argumentos e controle. Em cada novo nível de descrição, tivemos que levantar questões e resolver ambiguidades que não eram aparentes no tratamento anterior, menos preciso, da avaliação. Para entender o comportamento do avaliador de controle explícito, podemos simulá-lo e monitorar seu desempenho.

Instalaremos um loop de driver em nossa máquina do avaliador. Isso desempenha o papel do procedimento driver-loop de 4.1.4. O avaliador imprimirá repetidamente um prompt, lerá uma expressão, avaliará a expressão indo para eval-dispatch e imprimirá o resultado. As seguintes instruções formam o início da sequência do controlador do avaliador de controle explícito:³¹⁴

read-eval-print-loop
  (perform (op initialize-stack))
  (perform (op prompt-for-input)
           (const ";;; EC-Eval input:"))
  (assign exp (op read))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (label eval-dispatch))
print-result
  (perform (op announce-output)
           (const ";;; EC-Eval value:"))
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

Quando encontramos um erro em um procedimento (como o erro “tipo de procedimento desconhecido” indicado em apply-dispatch), imprimimos uma mensagem de erro e retornamos ao loop do driver.³¹⁵

unknown-expression-type
  (assign val (const unknown-expression-type-error))
  (goto (label signal-error))
unknown-procedure-type
  ; limpar a pilha (de apply-dispatch):
  (restore continue)    
  (assign val (const unknown-procedure-type-error))
  (goto (label signal-error))
signal-error
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

Para os propósitos da simulação, inicializamos a pilha cada vez que passamos pelo loop do driver, pois ela pode não estar vazia após um erro (como uma variável indefinida) interromper uma avaliação.³¹⁶

Se combinarmos todos os fragmentos de código apresentados em 5.4.1–5.4.4, podemos criar um modelo de máquina do avaliador que pode ser executado usando o simulador de máquina de registradores de 5.2.

(define eceval
  (make-machine
   '(exp env val proc argl continue unev)
   eceval-operations
   '(read-eval-print-loop
     ⟨entire machine controller 
      as given above⟩)))

Devemos definir procedimentos Scheme para simular as operações usadas como primitivas pelo avaliador. Esses são os mesmos procedimentos que usamos para o avaliador metacircular em 4.1, juntamente com os poucos adicionais definidos em notas de rodapé ao longo de 5.4.

(define eceval-operations
  (list (list 'self-evaluating? 
              self-evaluating)
        ⟨complete list of operations 
         for eceval machine⟩))

Finalmente, podemos inicializar o ambiente global e executar o avaliador:

(define the-global-environment
  (setup-environment))

(start eceval)

;;; EC-Eval input:
(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(append '(a b c) '(d e f))

;;; EC-Eval value:
(a b c d e f)

Claro, avaliar expressões dessa maneira levará muito mais tempo do que se as tivéssemos digitado diretamente no Scheme, devido aos múltiplos níveis de simulação envolvidos. Nossas expressões são avaliadas pela máquina do avaliador de controle explícito, que está sendo simulada por um programa Scheme, que por sua vez está sendo avaliado pelo interpretador Scheme.

Monitorando o desempenho do avaliador

A simulação pode ser uma ferramenta poderosa para orientar a implementação de avaliadores. As simulações facilitam não apenas explorar variações do design da máquina de registradores, mas também monitorar o desempenho do avaliador simulado. Por exemplo, um fator importante no desempenho é a eficiência com que o avaliador usa a pilha. Podemos observar o número de operações de pilha necessárias para avaliar várias expressões definindo a máquina do avaliador com a versão do simulador que coleta estatísticas sobre o uso da pilha (5.2.4), e adicionando uma instrução no ponto de entrada print-result do avaliador para imprimir as estatísticas:

print-result
  ; instrução adicionada:
  (perform (op print-stack-statistics))
  (perform (op announce-output)
           (const ";;; EC-Eval value:"))
  … ; mesmo que antes

As interações com o avaliador agora se parecem com isso:

;;; EC-Eval input:
(define (factorial n)
  (if (= n 1) 1 (* (factorial (- n 1)) n))
(total-pushes = 3, maximum-depth = 3)

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)
(total-pushes = 144, maximum-depth = 28)

;;; EC-Eval value:
120

Observe que o loop do driver do avaliador reinicializa a pilha no início de cada interação, de modo que as estatísticas impressas se referirão apenas às operações de pilha usadas para avaliar a expressão anterior.

Exercício 5.26: Use a pilha monitorada para explorar a propriedade de recursão em cauda do avaliador (5.4.2). Inicie o avaliador e defina o procedimento iterativo factorial de 1.2.1:

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

Execute o procedimento com alguns valores pequenos de $n$. Registre a profundidade máxima da pilha e o número de empilhamentos necessários para calcular $n!$ para cada um desses valores.

1. Você descobrirá que a profundidade máxima necessária para avaliar $n!$ é independente de $n$. Qual é essa profundidade?
2. Determine a partir de seus dados uma fórmula em termos de $n$ para o número total de operações de empilhamento usadas na avaliação de $n!$ para qualquer $n\ge 1$. Observe que o número de operações usadas é uma função linear de $n$ e, portanto, é determinado por duas constantes.

Exercício 5.27: Para comparação com o Exercício 5.26, explore o comportamento do seguinte procedimento para calcular fatoriais recursivamente:

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

Ao executar esse procedimento com a pilha monitorada, determine, como uma função de $n$, a profundidade máxima da pilha e o número total de empilhamentos usados na avaliação de $n!$ para $n\ge 1$. (Novamente, essas funções serão lineares.) Resuma seus experimentos preenchendo a seguinte tabela com as expressões apropriadas em termos de $n$:

$$\begin{array}{lll}& \text{Máximo}& \text{Número de}\\ & \text{profundidade}& \text{empilhamentos}\\ \text{Recursivo}& & \\ \text{factorial}& & \\ \text{Iterativo}& & \\ \text{factorial}& & \end{array}$$

A profundidade máxima é uma medida da quantidade de espaço usado pelo avaliador ao realizar a computação, e o número de empilhamentos correlaciona-se bem com o tempo necessário.

Exercício 5.28: Modifique a definição do avaliador alterando eval-sequence como descrito em 5.4.2 para que o avaliador não seja mais de recursão em cauda. Refaça seus experimentos de Exercício 5.26 e Exercício 5.27 para demonstrar que ambas as versões do procedimento factorial agora exigem espaço que cresce linearmente com sua entrada.

Exercício 5.29: Monitore as operações de pilha na computação recursiva em árvore de Fibonacci:

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

1. Dê uma fórmula em termos de $n$ para a profundidade máxima da pilha necessária para calcular $\text{Fib}(n)$ para $n\ge 2$. Dica: Em 1.2.2, argumentamos que o espaço usado por esse processo cresce linearmente com $n$.
2. Dê uma fórmula para o número total de empilhamentos usados para calcular $\text{Fib}(n)$ para $n\ge 2$. Você deve descobrir que o número de empilhamentos (que se correlaciona bem com o tempo usado) cresce exponencialmente com $n$. Dica: Seja $S(n)$ o número de empilhamentos usados na computação de $\text{Fib}(n)$. Você deve ser capaz de argumentar que há uma fórmula que expressa $S(n)$ em termos de $S(n-1)$, $S(n-2)$ e alguma constante fixa “overhead” $k$ que é independente de $n$. Dê a fórmula e diga o que $k$ é. Em seguida, mostre que $S(n)$ pode ser expresso como $a\cdot \text{Fib}(n+1)+b$ e dê os valores de $a$ e $b$.

Exercício 5.30: Nosso avaliador atualmente captura e sinaliza apenas dois tipos de erros—tipos de expressão desconhecidos e tipos de procedimento desconhecidos. Outros erros nos tirarão do loop de leitura-avaliação-impressão do avaliador. Quando executamos o avaliador usando o simulador de máquina de registradores, esses erros são capturados pelo sistema Scheme subjacente. Isso é análogo ao computador travar quando um programa de usuário comete um erro.³¹⁷ É um grande projeto fazer um sistema de erros real funcionar, mas vale a pena entender o que está envolvido aqui.

1. Erros que ocorrem no processo de avaliação, como uma tentativa de acessar uma variável não vinculada, poderiam ser capturados alterando a operação de pesquisa para fazê-la retornar um código de condição distinto, que não pode ser um valor possível de qualquer variável de usuário. O avaliador pode testar esse código de condição e então fazer o necessário para ir para signal-error. Encontre todos os lugares no avaliador onde tal mudança é necessária e corrija-os. Isso é muito trabalho.
2. Muito pior é o problema de lidar com erros que são sinalizados pela aplicação de procedimentos primitivos, como uma tentativa de dividir por zero ou uma tentativa de extrair o car de um símbolo. Em um sistema de alta qualidade escrito profissionalmente, cada aplicação primitiva é verificada quanto à segurança como parte da primitiva. Por exemplo, cada chamada para car poderia primeiro verificar que o argumento é um par. Se o argumento não for um par, a aplicação retornaria um código de condição distinto para o avaliador, que então relataria a falha. Poderíamos arranjar isso em nosso simulador de máquina de registradores fazendo cada procedimento primitivo verificar a aplicabilidade e retornar um código de condição apropriado em caso de falha. Então o código primitive-apply no avaliador pode verificar o código de condição e ir para signal-error se necessário. Construa essa estrutura e faça-a funcionar. Este é um projeto importante.

(define (empty-arglist) '())
(define (adjoin-arg arg arglist)
  (append arglist (list arg)))

(define (last-operand? ops) (null? (cdr ops)))

(define (no-more-exps? seq) (null? seq))

(define the-global-environment
  (setup-environment))

(define (get-global-environment)
  the-global-environment)