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

⇡

5.5Compilação

O avaliador de controle explícito de 5.4 é uma máquina de registros cujo controlador interpreta programas em Scheme. Nesta seção, veremos como executar programas em Scheme em uma máquina de registros cujo controlador não é um interpretador de Scheme.

A máquina do avaliador de controle explícito é universal—ela pode realizar qualquer processo computacional que pode ser descrito em Scheme. O controlador do avaliador orquestra o uso de seus caminhos de dados para realizar a computação desejada. Assim, os caminhos de dados do avaliador são universais: Eles são suficientes para realizar qualquer computação que desejarmos, dado um controlador apropriado.³¹⁸

Computadores comerciais de propósito geral são máquinas de registros organizadas em torno de uma coleção de registros e operações que constituem um conjunto universal de caminhos de dados eficiente e conveniente. O controlador para uma máquina de propósito geral é um interpretador para uma linguagem de máquina de registros como a que temos usado. Essa linguagem é chamada de linguagem nativa da máquina, ou simplesmente linguagem de máquina. Programas escritos em linguagem de máquina são sequências de instruções que usam os caminhos de dados da máquina. Por exemplo, a sequência de instruções do avaliador de controle explícito pode ser pensada como um programa em linguagem de máquina para um computador de propósito geral, em vez de como o controlador para uma máquina de interpretação especializada.

Existem duas estratégias comuns para preencher a lacuna entre linguagens de alto nível e linguagens de máquina de registros. O avaliador de controle explícito ilustra a estratégia de interpretação. Um interpretador escrito na linguagem nativa de uma máquina configura a máquina para executar programas escritos em uma linguagem (chamada de linguagem fonte) que pode diferir da linguagem nativa da máquina que realiza a avaliação. Os procedimentos primitivos da linguagem fonte são implementados como uma biblioteca de sub-rotinas escritas na linguagem nativa da máquina dada. Um programa a ser interpretado (chamado de programa fonte) é representado como uma estrutura de dados. O interpretador percorre essa estrutura de dados, analisando o programa fonte. Ao fazer isso, ele simula o comportamento pretendido do programa fonte chamando sub-rotinas primitivas apropriadas da biblioteca.

Nesta seção, exploraremos a estratégia alternativa de compilação. Um compilador para uma determinada linguagem fonte e máquina traduz um programa fonte em um programa equivalente (chamado de programa objeto) escrito na linguagem nativa da máquina. O compilador que implementaremos nesta seção traduz programas escritos em Scheme em sequências de instruções a serem executadas usando os caminhos de dados da máquina do avaliador de controle explícito.³¹⁹

Comparada com a interpretação, a compilação pode proporcionar um grande aumento na eficiência da execução de programas, como explicaremos abaixo na visão geral do compilador. Por outro lado, um interpretador fornece um ambiente mais poderoso para o desenvolvimento e depuração interativa de programas, porque o programa fonte sendo executado está disponível em tempo de execução para ser examinado e modificado. Além disso, como toda a biblioteca de primitivas está presente, novos programas podem ser construídos e adicionados ao sistema durante a depuração.

Diante das vantagens complementares da compilação e interpretação, os ambientes modernos de desenvolvimento de programas adotam uma estratégia mista. Interpretadores Lisp são geralmente organizados de forma que procedimentos interpretados e compilados possam se chamar mutuamente. Isso permite que um programador compile as partes de um programa que são consideradas depuradas, obtendo assim a vantagem de eficiência da compilação, enquanto mantém o modo interpretativo de execução para as partes do programa que estão em fluxo durante o desenvolvimento e depuração interativa. Em 5.5.7, após implementarmos o compilador, mostraremos como interfacá-lo com nosso interpretador para produzir um sistema integrado de desenvolvimento interpretador-compilador.

Uma visão geral do compilador

Nosso compilador é muito parecido com nosso interpretador, tanto em sua estrutura quanto na função que desempenha. Consequentemente, os mecanismos usados pelo compilador para analisar expressões serão semelhantes aos usados pelo interpretador. Além disso, para facilitar a interface entre código compilado e interpretado, projetaremos o compilador para gerar código que obedece às mesmas convenções de uso de registros que o interpretador: O ambiente será mantido no registro env, listas de argumentos serão acumuladas em argl, um procedimento a ser aplicado estará em proc, procedimentos retornarão suas respostas em val, e o local para o qual um procedimento deve retornar será mantido em continue. Em geral, o compilador traduz um programa fonte em um programa objeto que realiza essencialmente as mesmas operações de registros que o interpretador faria ao avaliar o mesmo programa fonte.

Essa descrição sugere uma estratégia para implementar um compilador rudimentar: Percorremos a expressão da mesma forma que o interpretador faz. Quando encontramos uma instrução de registro que o interpretador realizaria ao avaliar a expressão, não executamos a instrução, mas a acumulamos em uma sequência. A sequência resultante de instruções será o código objeto. Observe a vantagem de eficiência da compilação sobre a interpretação. Cada vez que o interpretador avalia uma expressão—por exemplo, (f 84 96)—ele realiza o trabalho de classificar a expressão (descobrindo que se trata de uma aplicação de procedimento) e testar o fim da lista de operandos (descobrindo que há dois operandos). Com um compilador, a expressão é analisada apenas uma vez, quando a sequência de instruções é gerada em tempo de compilação. O código objeto produzido pelo compilador contém apenas as instruções que avaliam o operador e os dois operandos, montam a lista de argumentos e aplicam o procedimento (em proc) aos argumentos (em argl).

Esse é o mesmo tipo de otimização que implementamos no avaliador analisador de 4.1.7. Mas há mais oportunidades para ganhar eficiência no código compilado. Conforme o interpretador é executado, ele segue um processo que deve ser aplicável a qualquer expressão na linguagem. Em contraste, um determinado segmento de código compilado é destinado a executar alguma expressão específica. Isso pode fazer uma grande diferença, por exemplo, no uso da pilha para salvar registros. Quando o interpretador avalia uma expressão, ele deve estar preparado para qualquer contingência. Antes de avaliar uma subexpressão, o interpretador salva todos os registros que serão necessários posteriormente, porque a subexpressão pode exigir uma avaliação arbitrária. Um compilador, por outro lado, pode explorar a estrutura da expressão específica que está processando para gerar código que evita operações desnecessárias na pilha.

Como exemplo, considere a combinação (f 84 96). Antes que o interpretador avalie o operador da combinação, ele se prepara para essa avaliação salvando os registros contendo os operandos e o ambiente, cujos valores serão necessários posteriormente. O interpretador então avalia o operador para obter o resultado em val, restaura os registros salvos e finalmente move o resultado de val para proc. No entanto, na expressão específica com a qual estamos lidando, o operador é o símbolo f, cuja avaliação é realizada pela operação da máquina lookup-variable-value, que não altera nenhum registro. O compilador que implementaremos nesta seção aproveitará esse fato e gerará código que avalia o operador usando a instrução

(assign proc 
        (op lookup-variable-value)
        (const f)
        (reg env))

Esse código não apenas evita os salvamentos e restaurações desnecessários, mas também atribui o valor da pesquisa diretamente a proc, enquanto o interpretador obteria o resultado em val e então moveria isso para proc.

Um compilador também pode otimizar o acesso ao ambiente. Tendo analisado o código, o compilador pode, em muitos casos, saber em qual quadro uma variável específica estará localizada e acessar esse quadro diretamente, em vez de realizar a busca lookup-variable-value. Discutiremos como implementar tal acesso a variáveis em 5.5.6. Até lá, no entanto, nos concentraremos no tipo de otimizações de registros e pilha descritas acima. Há muitas outras otimizações que podem ser realizadas por um compilador, como codificar operações primitivas "em linha" em vez de usar um mecanismo geral de apply (veja Exercício 5.38); mas não enfatizaremos isso aqui. Nosso principal objetivo nesta seção é ilustrar o processo de compilação em um contexto simplificado (mas ainda interessante).

5.5.1Estrutura do Compilador

Em 4.1.7, modificamos nosso interpretador metacircular original para separar a análise da execução. Analisamos cada expressão para produzir um procedimento de execução que tomava um ambiente como argumento e realizava as operações necessárias. Em nosso compilador, faremos essencialmente a mesma análise. Em vez de produzir procedimentos de execução, no entanto, geraremos sequências de instruções a serem executadas por nossa máquina de registros.

O procedimento compile é o despacho de alto nível no compilador. Ele corresponde ao procedimento eval de 4.1.1, ao procedimento analyze de 4.1.7 e ao ponto de entrada eval-dispatch do avaliador de controle explícito em 5.4.1. O compilador, como os interpretadores, usa os procedimentos de sintaxe de expressão definidos em 4.1.2.³²⁰ Compile realiza uma análise de caso no tipo sintático da expressão a ser compilada. Para cada tipo de expressão, ele despacha para um gerador de código especializado:

(define (compile exp target linkage)
  (cond ((self-evaluating? exp)
         (compile-self-evaluating 
          exp target linkage))
        ((quoted? exp) 
         (compile-quoted exp target linkage))
        ((variable? exp)
         (compile-variable 
          exp target linkage))
        ((assignment? exp)
         (compile-assignment
          exp target linkage))
        ((definition? exp)
         (compile-definition
          exp target linkage))
        ((if? exp)
         (compile-if exp target linkage))
        ((lambda? exp)
         (compile-lambda exp target linkage))
        ((begin? exp)
         (compile-sequence 
          (begin-actions exp) target linkage))
        ((cond? exp) 
         (compile 
          (cond->if exp) target linkage))
        ((application? exp)
         (compile-application 
          exp target linkage))
        (else
         (error "Unknown expression type: 
                 COMPILE" 
                exp))))

Destinos e ligações

Compile e os geradores de código que ele chama recebem dois argumentos além da expressão a ser compilada. Há um destino, que especifica o registro no qual o código compilado deve retornar o valor da expressão. Há também um descritor de ligação, que descreve como o código resultante da compilação da expressão deve prosseguir quando terminar sua execução. O descritor de ligação pode exigir que o código faça uma das três coisas a seguir:

continuar na próxima instrução na sequência (isso é especificado pelo descritor de ligação next),
retornar do procedimento que está sendo compilado (isso é especificado pelo descritor de ligação return), ou
pular para um ponto de entrada nomeado (isso é especificado usando o rótulo designado como descritor de ligação).

Por exemplo, compilar a expressão 5 (que é autoavaliada) com um destino no registro val e uma ligação next deve produzir a instrução

(assign val (const 5))

Compilar a mesma expressão com uma ligação return deve produzir as instruções

(assign val (const 5))
(goto (reg continue))

No primeiro caso, a execução continuará com a próxima instrução na sequência. No segundo caso, retornaremos de uma chamada de procedimento. Em ambos os casos, o valor da expressão será colocado no registro de destino val.

Sequências de instruções e uso da pilha

Cada gerador de código retorna uma sequência de instruções contendo o código objeto que ele gerou para a expressão. A geração de código para uma expressão composta é realizada combinando a saída de geradores de código mais simples para expressões componentes, assim como a avaliação de uma expressão composta é realizada avaliando as expressões componentes.

O método mais simples para combinar sequências de instruções é um procedimento chamado append-instruction-sequences. Ele recebe como argumentos qualquer número de sequências de instruções que devem ser executadas sequencialmente; ele as concatena e retorna a sequência combinada. Ou seja, se $⟨ s e q_{1} ⟩$ e $⟨ s e q_{2} ⟩$ são sequências de instruções, então avaliar

(append-instruction-sequences ⟨seq₁⟩ ⟨seq₂⟩)

produz a sequência

⟨seq₁⟩
⟨seq₂⟩

Sempre que os registros precisarem ser salvos, os geradores de código do compilador usam preserving, que é um método mais sutil para combinar sequências de instruções. Preserving recebe três argumentos: um conjunto de registros e duas sequências de instruções que devem ser executadas sequencialmente. Ele concatena as sequências de forma que o conteúdo de cada registro no conjunto seja preservado sobre a execução da primeira sequência, se isso for necessário para a execução da segunda sequência. Ou seja, se a primeira sequência modificar o registro e a segunda sequência realmente precisar do conteúdo original do registro, então preserving envolve um save e um restore do registro em torno da primeira sequência antes de concatenar as sequências. Caso contrário, preserving simplesmente retorna as sequências de instruções concatenadas. Assim, por exemplo, (preserving (list ⟨reg₁⟩ ⟨reg₂⟩) ⟨seg₁⟩ ⟨seg₂⟩) produz uma das seguintes quatro sequências de instruções, dependendo de como $⟨ s e q_{1} ⟩$ e $⟨ s e q_{2} ⟩$ usam $⟨ r e g_{1} ⟩$ e $⟨ r e g_{2} ⟩$ : $\begin{array}{llll} ⟨ s e q_{1} ⟩ & (save & (save & (save ⟨ r e g_{2} ⟩) \\ ⟨ s e q_{2} ⟩ & ⟨ r e g_{1} ⟩) & ⟨ r e g_{2} ⟩) & (save ⟨ r e g_{1} ⟩) \\ ⟨ s e q_{1} ⟩ & ⟨ s e q_{1} ⟩ & ⟨ s e q_{1} ⟩ \\ (restore & (restore & (restore ⟨ r e g_{1} ⟩) \\ ⟨ r e g_{1} ⟩) & ⟨ r e g_{2} ⟩) & (restore ⟨ r e g_{2} ⟩) \\ ⟨ s e q_{2} ⟩ & ⟨ s e q_{2} ⟩ & ⟨ s e q_{2} ⟩ \end{array}$

Ao usar preserving para combinar sequências de instruções, o compilador evita operações desnecessárias na pilha. Isso também isola os detalhes de se gerar ou não instruções save e restore dentro do procedimento preserving, separando-os das preocupações que surgem ao escrever cada um dos geradores de código individuais. Na verdade, nenhuma instrução save ou restore é explicitamente produzida pelos geradores de código.

Em princípio, poderíamos representar uma sequência de instruções simplesmente como uma lista de instruções. Append-instruction-sequences poderia então combinar sequências de instruções realizando um append de lista comum. No entanto, preserving seria então uma operação complexa, porque teria que analisar cada sequência de instruções para determinar como a sequência usa seus registros. Preserving seria ineficiente e complexo, porque teria que analisar cada um de seus argumentos de sequência de instruções, mesmo que essas sequências pudessem ter sido construídas por chamadas a preserving, caso em que suas partes já teriam sido analisadas. Para evitar essa análise repetitiva, associaremos a cada sequência de instruções algumas informações sobre seu uso de registros. Quando construímos uma sequência de instruções básica, forneceremos essas informações explicitamente, e os procedimentos que combinam sequências de instruções derivarão informações de uso de registros para a sequência combinada a partir das informações associadas às sequências componentes.

Uma sequência de instruções conterá três partes de informação:

o conjunto de registros que devem ser inicializados antes que as instruções na sequência sejam executadas (esses registros são ditos necessários pela sequência),
o conjunto de registros cujos valores são modificados pelas instruções na sequência, e
as instruções reais (também chamadas de declarações) na sequência.

Representaremos uma sequência de instruções como uma lista de suas três partes. O construtor para sequências de instruções é, portanto,

(define (make-instruction-sequence 
         needs modifies statements)
  (list needs modifies statements))

Por exemplo, a sequência de duas instruções que procura o valor da variável x no ambiente atual, atribui o resultado a val e então retorna, requer que os registros env e continue tenham sido inicializados e modifica o registro val. Essa sequência seria, portanto, construída como

(make-instruction-sequence
 '(env continue)
 '(val)
 '((assign val
           (op lookup-variable-value)
           (const x)
           (reg env))
   (goto (reg continue))))

Às vezes, precisamos construir uma sequência de instruções sem declarações:

(define (empty-instruction-sequence)
  (make-instruction-sequence '() '() '()))

Os procedimentos para combinar sequências de instruções são mostrados em 5.5.4.

Exercício 5.31: Na avaliação de uma aplicação de procedimento, o avaliador de controle explícito sempre salva e restaura o registro env em torno da avaliação do operador, salva e restaura env em torno da avaliação de cada operando (exceto o último), salva e restaura argl em torno da avaliação de cada operando e salva e restaura proc em torno da avaliação da sequência de operandos. Para cada uma das seguintes combinações, diga quais dessas operações de save e restore são supérfluas e, portanto, poderiam ser eliminadas pelo mecanismo preserving do compilador:
(f 'x 'y)
((f) 'x 'y)
(f (g 'x) y)
(f (g 'x) 'y)

Exercício 5.32: Usando o mecanismo preserving, o compilador evitará salvar e restaurar env em torno da avaliação do operador de uma combinação no caso em que o operador é um símbolo. Poderíamos também construir tais otimizações no avaliador. De fato, o avaliador de controle explícito de 5.4 já realiza uma otimização semelhante, tratando combinações sem operandos como um caso especial.

Estenda o avaliador de controle explícito para reconhecer como uma classe separada de expressões combinações cujo operador é um símbolo e para tirar vantagem desse fato na avaliação de tais expressões.

Alyssa P. Hacker sugere que, ao estender o avaliador para reconhecer mais e mais casos especiais, poderíamos incorporar todas as otimizações do compilador e que isso eliminaria a vantagem da compilação. O que você acha dessa ideia?

5.5.2Compilando Expressões

Nesta seção e na próxima, implementamos os geradores de código para os quais o procedimento compile despacha.

Compilando código de ligação

Em geral, a saída de cada gerador de código terminará com instruções—geradas pelo procedimento compile-linkage—que implementam a ligação necessária. Se a ligação for return, então devemos gerar a instrução (goto (reg continue)). Isso precisa do registro continue e não modifica nenhum registro. Se a ligação for next, então não precisamos incluir nenhuma instrução adicional. Caso contrário, a ligação é um rótulo, e geramos um goto para esse rótulo, uma instrução que não precisa ou modifica nenhum registro.³²¹

(define (compile-linkage linkage)
  (cond ((eq? linkage 'return)
         (make-instruction-sequence 
          '(continue)
          '()
          '((goto (reg continue)))))
        ((eq? linkage 'next)
         (empty-instruction-sequence))
        (else
         (make-instruction-sequence '() '()
          `((goto (label ,linkage))))))

O código de ligação é anexado a uma sequência de instruções preservando o registro continue, já que uma ligação return exigirá o registro continue: Se a sequência de instruções dada modificar continue e o código de ligação precisar dele, continue será salvo e restaurado.

(define (end-with-linkage 
         linkage instruction-sequence)
  (preserving '(continue)
   instruction-sequence
   (compile-linkage linkage)))

Compilando expressões simples

Os geradores de código para expressões autoavaliadas, citações e variáveis constroem sequências de instruções que atribuem o valor necessário ao registro de destino e então prosseguem conforme especificado pelo descritor de ligação.

(define (compile-self-evaluating 
         exp target linkage)
  (end-with-linkage
   linkage (make-instruction-sequence 
            '()
            (list target)
            `((assign ,target (const ,exp))))))

(define (compile-quoted exp target linkage)
  (end-with-linkage
   linkage
   (make-instruction-sequence
    '()
    (list target)
    `((assign 
       ,target
       (const ,(text-of-quotation exp))))))

(define (compile-variable
         exp target linkage)
  (end-with-linkage 
   linkage
   (make-instruction-sequence 
    '(env)
    (list target)
    `((assign ,target
              (op lookup-variable-value)
              (const ,exp)
              (reg env)))))

Todas essas instruções de atribuição modificam o registro de destino, e a que procura uma variável precisa do registro env.

Atribuições e definições são tratadas de forma semelhante ao que são no interpretador. Geramos recursivamente código que calcula o valor a ser atribuído à variável e anexamos a ele uma sequência de duas instruções que realmente define ou define a variável e atribui o valor da expressão inteira (o símbolo ok) ao registro de destino. A compilação recursiva tem destino val e ligação next para que o código coloque seu resultado em val e continue com o código que é anexado após ele. A anexação é feita preservando env, já que o ambiente é necessário para definir ou definir a variável e o código para o valor da variável pode ser a compilação de uma expressão complexa que pode modificar os registros de forma arbitrária.

(define (compile-assignment 
         exp target linkage)
  (let ((var (assignment-variable exp))
        (get-value-code
         (compile (assignment-value exp) 
                  'val'
                  'next')))
    (end-with-linkage 
     linkage
     (preserving 
      '(env)
      get-value-code
      (make-instruction-sequence
       '(env val)
       (list target)
       `((perform (op set-variable-value!)
                  (const ,var)
                  (reg val)
                  (reg env))
         (assign ,target (const ok)))))))

(define (compile-definition 
         exp target linkage)
  (let ((var (definition-variable exp))
        (get-value-code
         (compile (definition-value exp)
                  'val'
                  'next')))
    (end-with-linkage
     linkage
     (preserving 
      '(env)
      get-value-code
      (make-instruction-sequence
       '(env val)
       (list target)
       `((perform (op define-variable!)
                  (const ,var)
                  (reg val)
                  (reg env))
         (assign ,target (const ok)))))))

A sequência de duas instruções anexada requer env e val e modifica o destino. Observe que, embora preservemos env para essa sequência, não preservamos val, porque o get-value-code é projetado para colocar explicitamente seu resultado em val para uso por essa sequência. (Na verdade, se preservássemos val, teríamos um bug, porque isso faria com que o conteúdo anterior de val fosse restaurado logo após a execução do get-value-code.)

Compilando expressões condicionais

O código para uma expressão if compilada com um destino e uma ligação dados tem a forma

⟨compilation of predicate, 
 target val, linkage next⟩
 (test (op false?) (reg val))
 (branch (label false-branch))
true-branch
 ⟨compilation of consequent with given 
  target and given linkage or after-if⟩
false-branch
 ⟨compilation of alternative 
  with given target and linkage⟩
after-if

Para gerar esse código, compilamos o predicado, o consequente e a alternativa, e combinamos o código resultante com instruções para testar o resultado do predicado e com rótulos recém-gerados para marcar os ramos verdadeiro e falso e o fim do condicional.³²² Nesse arranjo de código, devemos pular o ramo verdadeiro se o teste for falso. A única complicação leve é em como a ligação para o ramo verdadeiro deve ser tratada. Se a ligação para o condicional for return ou um rótulo, então os ramos verdadeiro e falso usarão essa mesma ligação. Se a ligação for next, o ramo verdadeiro termina com um salto ao redor do código para o ramo falso para o rótulo no fim do condicional.

(define (compile-if exp target linkage)
  (let ((t-branch (make-label 'true-branch))
        (f-branch (make-label 'false-branch))
        (after-if (make-label 'after-if)))
    (let ((consequent-linkage
           (if (eq? linkage 'next) 
               after-if
               linkage)))
      (let ((p-code 
             (compile (if-predicate exp)
                      'val'
                      'next'))
            (c-code
             (compile (if-consequent exp) 
                      target 
                      consequent-linkage))
            (a-code
             (compile (if-alternative exp)
                      target
                      linkage)))
        (preserving 
         '(env continue)
         p-code
         (append-instruction-sequences
          (make-instruction-sequence 
           '(val) 
           '()
           `((test (op false?) (reg val))
             (branch (label ,f-branch))))
          (parallel-instruction-sequences
           (append-instruction-sequences 
            t-branch c-code)
           (append-instruction-sequences
            f-branch a-code))
          after-if))))))

Env é preservado em torno do código do predicado porque ele pode ser necessário pelos ramos verdadeiro e falso, e continue é preservado porque pode ser necessário pelo código de ligação nesses ramos. O código para os ramos verdadeiro e falso (que não são executados sequencialmente) é anexado usando um combinador especial parallel-instruction-sequences descrito em 5.5.4.

Observe que cond é uma expressão derivada, então tudo que o compilador precisa fazer para lidar com ela é aplicar o transformador cond->if (de 4.1.2) e compilar a expressão if resultante.

Compilando sequências

A compilação de sequências (de corpos de procedimentos ou expressões begin explícitas) é paralela à sua avaliação. Cada expressão da sequência é compilada—a última expressão com a ligação especificada para a sequência, e as outras expressões com ligação next (para executar o resto da sequência). As sequências de instruções para as expressões individuais são anexadas para formar uma única sequência de instruções, de forma que env (necessário para o resto da sequência) e continue (possivelmente necessário para a ligação no fim da sequência) sejam preservados.

(define (compile-sequence seq target linkage)
  (if (last-exp? seq)
      (compile (first-exp seq) target linkage)
      (preserving '(env continue)
       (compile (first-exp seq) target 'next')
       (compile-sequence (rest-exps seq)
                         target
                         linkage))))

Compilando expressões `lambda`

Expressões lambda constroem procedimentos. O código objeto para uma expressão lambda deve ter a forma

⟨construct procedure object 
 and assign it to target register⟩
⟨linkage⟩

Quando compilamos a expressão lambda, também geramos o código para o corpo do procedimento. Embora o corpo não seja executado no momento da construção do procedimento, é conveniente inseri-lo no código objeto logo após o código para o lambda. Se a ligação para a expressão lambda for um rótulo ou return, isso é bom. Mas se a ligação for next, precisaremos pular o código para o corpo do procedimento usando uma ligação que salta para um rótulo que é inserido após o corpo. O código objeto tem, portanto, a forma

⟨construct procedure object 
 and assign it to target register⟩
 ⟨code for given linkage⟩ or 
  (goto (label after-lambda))
 ⟨compilation of procedure body⟩
after-lambda

Compile-lambda gera o código para construir o objeto de procedimento seguido pelo código para o corpo do procedimento. O objeto de procedimento será construído em tempo de execução combinando o ambiente atual (o ambiente no ponto de definição) com o ponto de entrada para o corpo do procedimento compilado (um rótulo recém-gerado).³²³

(define (compile-lambda exp target linkage)
  (let ((proc-entry 
         (make-label 'entry))
        (after-lambda 
         (make-label 'after-lambda)))
    (let ((lambda-linkage
           (if (eq? linkage 'next)
               after-lambda
               linkage)))
      (append-instruction-sequences
       (tack-on-instruction-sequence
        (end-with-linkage 
         lambda-linkage
         (make-instruction-sequence 
          '(env)
          (list target)
          `((assign 
             ,target
             (op make-compiled-procedure)
             (label ,proc-entry)
             (reg env)))))
        (compile-lambda-body exp proc-entry))
       after-lambda))))

Compile-lambda usa o combinador especial tack-on-instruction-sequence em vez de append-instruction-sequences (5.5.4) para anexar o corpo do procedimento ao código da expressão lambda, porque o corpo não faz parte da sequência de instruções que será executada quando a sequência combinada for inserida; em vez disso, ele está na sequência apenas porque esse foi um local conveniente para colocá-lo.

Compile-lambda-body constrói o código para o corpo do procedimento. Esse código começa com um rótulo para o ponto de entrada. Em seguida, vêm instruções que farão com que o ambiente de avaliação em tempo de execução mude para o ambiente correto para avaliar o corpo do procedimento—ou seja, o ambiente de definição do procedimento, estendido para incluir as ligações dos parâmetros formais aos argumentos com os quais o procedimento é chamado. Depois disso, vem o código para a sequência de expressões que compõem o corpo do procedimento. A sequência é compilada com ligação return e destino val para que termine retornando do procedimento com o resultado do procedimento em val.

(define (compile-lambda-body exp proc-entry)
  (let ((formals (lambda-parameters exp)))
    (append-instruction-sequences
     (make-instruction-sequence 
      '(env proc argl)
      '(env)
      `(,proc-entry
        (assign env 
                (op compiled-procedure-env)
                (reg proc))
        (assign env
                (op extend-environment)
                (const ,formals)
                (reg argl)
                (reg env))))
     (compile-sequence (lambda-body exp)
                       'val'
                       'return'))))

5.5.3Compilando Combinações

A essência do processo de compilação é a compilação de aplicações de procedimentos. O código para uma combinação compilada com um destino e uma ligação dados tem a forma

⟨compilation of operator, 
 target proc, linkage next⟩
⟨evaluate operands and construct 
 argument list in argl⟩
⟨compilation of procedure call 
 with given target and linkage⟩

Os registros env, proc e argl podem precisar ser salvos e restaurados durante a avaliação do operador e dos operandos. Observe que este é o único lugar no compilador onde um destino diferente de val é especificado.

O código necessário é gerado por compile-application. Isso compila recursivamente o operador, para produzir código que coloca o procedimento a ser aplicado em proc, e compila os operandos, para produzir código que avalia os operandos individuais da aplicação. As sequências de instruções para os operandos são combinadas (por construct-arglist) com código que constrói a lista de argumentos em argl, e o código resultante da lista de argumentos é combinado com o código do procedimento e o código que realiza a chamada do procedimento (produzido por compile-procedure-call). Ao anexar as sequências de código, o registro env deve ser preservado em torno da avaliação do operador (já que a avaliação do operador pode modificar env, que será necessário para avaliar os operandos), e o registro proc deve ser preservado em torno da construção da lista de argumentos (já que a avaliação dos operandos pode modificar proc, que será necessário para a aplicação real do procedimento). Continue também deve ser preservado durante todo o processo, já que é necessário para a ligação na chamada do procedimento.

(define (compile-application 
         exp target linkage)
  (let ((proc-code 
         (compile (operator exp) 'proc' 'next'))
        (operand-codes
         (map (lambda (operand)
                (compile operand 'val' 'next'))
              (operands exp))))
    (preserving 
     '(env continue)
     proc-code
     (preserving 
      '(proc continue)
      (construct-arglist operand-codes)
      (compile-procedure-call 
       target
       linkage)))))

O código para construir a lista de argumentos avaliará cada operando em val e então cons esse valor na lista de argumentos sendo acumulada em argl. Como cons os argumentos em argl em sequência, devemos começar com o último argumento e terminar com o primeiro, para que os argumentos apareçam em ordem do primeiro ao último na lista resultante. Em vez de desperdiçar uma instrução inicializando argl para a lista vazia para configurar essa sequência de avaliações, fazemos com que a primeira sequência de código construa o argl inicial. A forma geral da construção da lista de argumentos é, portanto, a seguinte:

⟨compilation of last operand, targeted to val⟩
(assign argl (op list) (reg val))
⟨compilation of next operand, targeted to val⟩
(assign argl (op cons) (reg val) (reg argl))
…
⟨compilation of first operand, targeted to val⟩
(assign argl (op cons) (reg val) (reg argl))

Argl deve ser preservado em torno de cada avaliação de operando, exceto a primeira (para que os argumentos acumulados até então não sejam perdidos), e env deve ser preservado em torno de cada avaliação de operando, exceto a última (para uso por avaliações subsequentes de operandos).

Compilar esse código de argumentos é um pouco complicado, devido ao tratamento especial do primeiro operando a ser avaliado e à necessidade de preservar argl e env em lugares diferentes. O procedimento construct-arglist recebe como argumentos o código que avalia os operandos individuais. Se não houver operandos, ele simplesmente emite a instrução

(assign argl (const ()))

Caso contrário, construct-arglist cria código que inicializa argl com o último argumento e anexa código que avalia o resto dos argumentos e os adiciona a argl em sucessão. Para processar os argumentos do último ao primeiro, devemos inverter a lista de sequências de código de operandos da ordem fornecida por compile-application.

(define (construct-arglist operand-codes)
  (let ((operand-codes 
         (reverse operand-codes)))
    (if (null? operand-codes)
        (make-instruction-sequence 
         '() 
         '(argl)
         '((assign argl (const ()))))
        (let ((code-to-get-last-arg
               (append-instruction-sequences
                (car operand-codes)
                (make-instruction-sequence 
                 '(val)
                 '(argl)
                 '((assign argl
                           (op list)
                           (reg val))))))
          (if (null? (cdr operand-codes))
              code-to-get-last-arg
              (preserving 
               '(env)
               code-to-get-last-arg
               (code-to-get-rest-args
                (cdr operand-codes)))))))

(define (code-to-get-rest-args operand-codes)
  (let ((code-for-next-arg
         (preserving 
          '(argl)
          (car operand-codes)
          (make-instruction-sequence 
           '(val argl)
           '(argl)
           '((assign argl
                     (op cons)
                     (reg val)
                     (reg argl))))))
    (if (null? (cdr operand-codes))
        code-for-next-arg
        (preserving 
         '(env)
         code-for-next-arg
         (code-to-get-rest-args 
          (cdr operand-codes))))))

Aplicando procedimentos

Após avaliar os elementos de uma combinação, o código compilado deve aplicar o procedimento em proc aos argumentos em argl. O código realiza essencialmente a mesma despacho que o procedimento apply no avaliador metacircular de 4.1.1 ou o ponto de entrada apply-dispatch no avaliador de controle explícito de 5.4.1. Ele verifica se o procedimento a ser aplicado é um procedimento primitivo ou um procedimento compilado. Para um procedimento primitivo, ele usa apply-primitive-procedure; veremos em breve como ele lida com procedimentos compilados. O código de aplicação de procedimento tem a seguinte forma:

(test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch))
compiled-branch
 ⟨código para aplicar o procedimento compilado
  com o alvo dado e a ligação apropriada⟩
primitive-branch
 (assign ⟨alvo⟩
         (op apply-primitive-procedure)
         (reg proc)
         (reg argl))
 ⟨ligação⟩
after-call

Observe que o ramo compilado deve pular ao redor do ramo primitivo. Portanto, se a ligação para a chamada de procedimento original fosse next, o ramo composto deve usar uma ligação que salte para um rótulo inserido após o ramo primitivo. (Isso é semelhante à ligação usada para o ramo verdadeiro em compile-if.)

(define (compile-procedure-call
         target linkage)
  (let ((primitive-branch 
         (make-label 'primitive-branch))
        (compiled-branch 
         (make-label 'compiled-branch))
        (after-call
         (make-label 'after-call)))
    (let ((compiled-linkage
           (if (eq? linkage 'next)
               after-call
               linkage)))
      (append-instruction-sequences
       (make-instruction-sequence 
        '(proc)
        '()
        `((test 
           (op primitive-procedure?)
           (reg proc))
          (branch 
           (label ,primitive-branch))))
       (parallel-instruction-sequences
        (append-instruction-sequences
         compiled-branch
         (compile-proc-appl 
          target
          compiled-linkage))
        (append-instruction-sequences
         primitive-branch
         (end-with-linkage
          linkage
          (make-instruction-sequence
           '(proc argl)
           (list target)
           `((assign 
              ,target
              (op apply-primitive-procedure)
              (reg proc)
              (reg argl)))))))
       after-call))))

Os ramos primitivo e composto, como os ramos verdadeiro e falso em compile-if, são anexados usando parallel-instruction-sequences em vez do append-instruction-sequences comum, porque eles não serão executados sequencialmente.

Aplicando procedimentos compilados

O código que lida com a aplicação de procedimentos é a parte mais sutil do compilador, mesmo que as sequências de instruções que ele gera sejam muito curtas. Um procedimento compilado (como construído por compile-lambda) tem um ponto de entrada, que é um rótulo que designa onde o código para o procedimento começa. O código neste ponto de entrada calcula um resultado em val e retorna executando a instrução (goto (reg continue)). Assim, nós poderíamos esperar que o código para uma aplicação de procedimento compilado (a ser gerado por compile-proc-appl) com um alvo e ligação dados se pareça com isso se a ligação for um rótulo

(assign continue 
        (label proc-return))
 (assign val
         (op compiled-procedure-entry)
         (reg proc))
 (goto (reg val))
proc-return
 (assign ⟨alvo⟩ 
         (reg val))   ; incluído se o alvo não for val
 (goto (label ⟨ligação⟩))   ; código de ligação

ou assim se a ligação for return.

(save continue))
 (assign continue 
         (label proc-return))
 (assign val 
         (op compiled-procedure-entry)
         (reg proc))
 (goto (reg val))
proc-return
 (assign ⟨alvo⟩
         (reg val))   ; incluído se o alvo não for val
 (restore continue))
 (goto (reg continue))   ; código de ligação

Este código configura continue para que o procedimento retorne a um rótulo proc-return e salta para o ponto de entrada do procedimento. O código em proc-return transfere o resultado do procedimento de val para o registrador de destino (se necessário) e então salta para o local especificado pela ligação. (A ligação é sempre return ou um rótulo, porque compile-procedure-call substitui uma ligação next para o ramo de procedimento composto por um rótulo after-call.)

Na verdade, se o alvo não for val, esse é exatamente o código que nosso compilador gerará.³²⁴ Geralmente, no entanto, o alvo é val (a única vez que o compilador especifica um registrador diferente é quando o alvo é a avaliação de um operador para proc), então o resultado do procedimento é colocado diretamente no registrador de destino e não há necessidade de retornar a um local especial que o copie. Em vez disso, simplificamos o código configurando continue para que o procedimento "retorne" diretamente para o local especificado pela ligação do chamador:

⟨configurar continue para a ligação⟩
(assign val 
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Se a ligação for um rótulo, configuramos continue para que o procedimento retorne para esse rótulo. (Ou seja, o (goto (reg continue)) com o qual o procedimento termina se torna equivalente ao (goto (label ⟨ligação⟩)) em proc-return acima.)

(assign continue 
        (label ⟨ligação⟩))
(assign val
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Se a ligação for return, não precisamos configurar continue: Ele já contém o local desejado. (Ou seja, o (goto (reg continue)) com o qual o procedimento termina vai diretamente para o local onde o (goto (reg continue)) em proc-return teria ido.)

(assign val
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Com esta implementação da ligação return, o compilador gera código recursivo em cauda. Chamar um procedimento como o passo final em um corpo de procedimento faz uma transferência direta, sem salvar qualquer informação na pilha.

Suponha que, em vez disso, tivéssemos tratado o caso de uma chamada de procedimento com uma ligação de return e um alvo de val como mostrado acima para um alvo não val. Isso destruiria a recursão em cauda. Nosso sistema ainda daria o mesmo valor para qualquer expressão. Mas cada vez que chamássemos um procedimento, salvaríamos continue e retornaríamos após a chamada para desfazer o (inútil) salvamento. Esses salvamentos extras se acumulariam durante um aninhamento de chamadas de procedimento.³²⁵

Compile-proc-appl gera o código de aplicação de procedimento acima considerando quatro casos, dependendo se o alvo para a chamada é val e se a ligação é return. Observe que as sequências de instruções são declaradas para modificar todos os registradores, já que executar o corpo do procedimento pode alterar os registradores de maneiras arbitrárias.³²⁶ Também note que a sequência de código para o caso com alvo val e ligação return é declarada para precisar de continue: Mesmo que continue não seja explicitamente usado na sequência de duas instruções, devemos ter certeza de que continue terá o valor correto quando entrarmos no procedimento compilado.

(define (compile-proc-appl target linkage)
  (cond ((and (eq? target 'val)
              (not (eq? linkage 'return)))
         (make-instruction-sequence 
          '(proc)
          all-regs
          `((assign continue (label ,linkage))
            (assign 
             val 
             (op compiled-procedure-entry)
             (reg proc))
            (goto (reg val)))))
        ((and (not (eq? target 'val))
              (not (eq? linkage 'return)))
         (let ((proc-return 
                (make-label 'proc-return)))
           (make-instruction-sequence 
            '(proc)
            all-regs
            `((assign continue 
                      (label ,proc-return))
              (assign 
               val 
               (op compiled-procedure-entry)
               (reg proc))
              (goto (reg val))
              ,proc-return
              (assign ,target (reg val))
              (goto (label ,linkage))))))
        ((and (eq? target 'val)
              (eq? linkage 'return))
         (make-instruction-sequence 
          '(proc continue) 
          all-regs
          '((assign 
             val 
             (op compiled-procedure-entry)
             (reg proc))
            (goto (reg val)))))
        ((and (not (eq? target 'val))
              (eq? linkage 'return))
         (error "return linkage, 
                 target not val: COMPILE"
                target))))

5.5.4Combinando Sequências de Instruções

Esta seção descreve os detalhes sobre como as sequências de instruções são representadas e combinadas. Lembre-se de 5.5.1 que uma sequência de instruções é representada como uma lista dos registradores necessários, os registradores modificados e as instruções reais. Também consideraremos um rótulo (símbolo) como um caso degenerado de uma sequência de instruções, que não precisa ou modifica nenhum registrador. Então, para determinar os registradores necessários e modificados por sequências de instruções, usamos os seletores

(define (registers-needed s)
  (if (symbol? s) '() (car s)))
(define (registers-modified s)
  (if (symbol? s) '() (cadr s)))
(define (statements s)
  (if (symbol? s) (list s) (caddr s)))

e para determinar se uma determinada sequência precisa ou modifica um determinado registrador, usamos os predicados

(define (needs-register? seq reg)
  (memq reg (registers-needed seq)))
(define (modifies-register? seq reg)
  (memq reg (registers-modified seq)))

Em termos desses predicados e seletores, podemos implementar os vários combinadores de sequências de instruções usados ao longo do compilador.

O combinador básico é append-instruction-sequences. Ele recebe como argumentos um número arbitrário de sequências de instruções que devem ser executadas sequencialmente e retorna uma sequência de instruções cujas instruções são as instruções de todas as sequências anexadas juntas. O ponto sutil é determinar os registradores que são necessários e modificados pela sequência resultante. Ele modifica aqueles registradores que são modificados por qualquer uma das sequências; ele precisa daqueles registradores que devem ser inicializados antes que a primeira sequência possa ser executada (os registradores necessários para a primeira sequência), juntamente com aqueles registradores necessários para qualquer uma das outras sequências que não são inicializados (modificados) por sequências anteriores.

As sequências são anexadas duas de cada vez por append-2-sequences. Este recebe duas sequências de instruções seq1 e seq2 e retorna a sequência de instruções cujas instruções são as instruções de seq1 seguidas pelas instruções de seq2, cujos registradores modificados são aqueles registradores que são modificados por seq1 ou seq2, e cujos registradores necessários são os registradores necessários para seq1 juntamente com aqueles registradores necessários para seq2 que não são modificados por seq1. (Em termos de operações de conjuntos, o novo conjunto de registradores necessários é a união do conjunto de registradores necessários para seq1 com a diferença de conjuntos dos registradores necessários para seq2 e os registradores modificados por seq1.) Assim, append-instruction-sequences é implementado da seguinte forma:

(define (append-instruction-sequences . seqs)
  (define (append-2-sequences seq1 seq2)
    (make-instruction-sequence
     (list-union 
      (registers-needed seq1))
      (list-difference 
       (registers-needed seq2))
       (registers-modified seq1))))
     (list-union
      (registers-modified seq1))
      (registers-modified seq2)))
     (append (statements seq1))
             (statements seq2)))))
  (define (append-seq-list seqs)
    (if (null? seqs))
        (empty-instruction-sequence)
        (append-2-sequences 
         (car seqs))
         (append-seq-list (cdr seqs)))))
  (append-seq-list seqs))

Este procedimento usa algumas operações simples para manipular conjuntos representados como listas, semelhantes à representação de conjuntos (não ordenados) descrita em 2.3.3:

(define (list-union s1 s2)
  (cond ((null? s1)) s2)
        ((memq (car s1)) s2)
         (list-union (cdr s1)) s2))
        (else
         (cons (car s1))
               (list-union (cdr s1)) s2)))))

(define (list-difference s1 s2)
  (cond ((null? s1)) '())
        ((memq (car s1)) s2)
         (list-difference (cdr s1)) s2))
        (else 
         (cons (car s1))
               (list-difference (cdr s1))
                                s2)))))

Preserving, o segundo principal combinador de sequências de instruções, recebe uma lista de registradores regs e duas sequências de instruções seq1 e seq2 que devem ser executadas sequencialmente. Ele retorna uma sequência de instruções cujas instruções são as instruções de seq1 seguidas pelas instruções de seq2, com as instruções save e restore apropriadas ao redor de seq1 para proteger os registradores em regs que são modificados por seq1 mas necessários para seq2. Para realizar isso, preserving primeiro cria uma sequência que tem os saves necessários seguidos pelas instruções de seq1 seguidos pelos restores necessários. Esta sequência precisa dos registradores sendo salvos e restaurados em adição aos registradores necessários para seq1, e modifica os registradores modificados por seq1 exceto pelos que estão sendo salvos e restaurados. Esta sequência aumentada e seq2 são então anexadas da maneira usual. O seguinte procedimento implementa essa estratégia recursivamente, percorrendo a lista de registradores a serem preservados:³²⁷

(define (preserving regs seq1 seq2)
  (if (null? regs))
      (append-instruction-sequences seq1 seq2)
      (let ((first-reg (car regs)))
        (if (and 
             (needs-register? seq2 first-reg)
             (modifies-register? seq1 
                                 first-reg))
            (preserving 
             (cdr regs)
             (make-instruction-sequence
              (list-union 
               (list first-reg))
               (registers-needed seq1)))
              (list-difference
               (registers-modified seq1))
               (list first-reg)))
              (append `((save ,first-reg))
                      (statements seq1))
                      `((restore ,first-reg)))))
             seq2)
            (preserving 
             (cdr regs)
             seq1
             seq2)))))

Outro combinador de sequências, tack-on-instruction-sequence, é usado por compile-lambda para anexar um corpo de procedimento a outra sequência. Porque o corpo do procedimento não está "em linha" para ser executado como parte da sequência combinada, seu uso de registradores não tem impacto no uso de registradores da sequência em que está embutido. Assim, ignoramos os conjuntos de registradores necessários e modificados pelo corpo do procedimento quando o anexamos à outra sequência.

(define (tack-on-instruction-sequence 
         seq body-seq)
  (make-instruction-sequence
   (registers-needed seq))
   (registers-modified seq))
   (append (statements seq))
           (statements body-seq))))

Compile-if e compile-procedure-call usam um combinador especial chamado parallel-instruction-sequences para anexar os dois ramos alternativos que seguem um teste. Os dois ramos nunca serão executados sequencialmente; para qualquer avaliação particular do teste, um ramo ou o outro será executado. Por causa disso, os registradores necessários para o segundo ramo ainda são necessários para a sequência combinada, mesmo que esses sejam modificados por o primeiro ramo.

(define (parallel-instruction-sequences 
         seq1 seq2)
  (make-instruction-sequence
   (list-union (registers-needed seq1))
               (registers-needed seq2)))
   (list-union (registers-modified seq1))
               (registers-modified seq2)))
   (append (statements seq1))
           (statements seq2))))

5.5.5Um Exemplo de Código Compilado

Agora que vimos todos os elementos do compilador, vamos examinar um exemplo de código compilado para ver como as coisas se encaixam. Vamos compilar a definição de um procedimento recursivo factorial chamando compile:

(compile
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))
 'val
 'next)

Especificamos que o valor da expressão define deve ser colocado no registrador val. Não nos importamos com o que o código compilado faz após executar o define, então nossa escolha de next como o descritor de ligação é arbitrária.

Compile determina que a expressão é uma definição, então ele chama compile-definition para compilar o código para calcular o valor a ser atribuído (destinado a val), seguido pelo código para instalar a definição, seguido pelo código para colocar o valor do define (que é o símbolo ok) no registrador de destino, seguido finalmente pelo código de ligação. Env é preservado ao redor do cálculo do valor, porque ele é necessário para instalar a definição. Como a ligação é next, não há código de ligação neste caso. O esqueleto do código compilado é assim

⟨salvar env se modificado pelo código para calcular o valor⟩
  ⟨compilação do valor da definição, 
   alvo val, ligação next⟩
  ⟨restaurar env se salvo acima⟩
  (perform (op define-variable!)
           (const factorial)
           (reg val)
           (reg env))
  (assign val (const ok))

A expressão que deve ser compilada para produzir o valor para a variável factorial é uma expressão lambda cujo valor é o procedimento que calcula fatoriais. Compile lida com isso chamando compile-lambda, que compila o corpo do procedimento, rotula-o como um novo ponto de entrada e gera a instrução que combinará o corpo do procedimento no novo ponto de entrada com o ambiente de execução e atribuirá o resultado a val. A sequência então salta ao redor do código do procedimento compilado, que é inserido neste ponto. O código do procedimento começa estendendo o ambiente de definição do procedimento por um quadro que vincula o parâmetro formal n ao argumento do procedimento. Então vem o corpo do procedimento. Como este código para o valor da variável não modifica o registrador env, o save e restore opcionais mostrados acima não são gerados. (O código do procedimento em entry2 não é executado neste ponto, então seu uso de env é irrelevante.) Portanto, o esqueleto para o código compilado se torna

  (assign val (op make-compiled-procedure)
              (label entry2)
              (reg env))
  (goto (label after-lambda1))
entry2
  (assign env (op compiled-procedure-env)
              (reg proc))
  (assign env (op extend-environment)
              (const (n))
              (reg argl)
              (reg env))
  ⟨compilação do corpo do procedimento⟩
after-lambda1
  (perform (op define-variable!)
           (const factorial)
           (reg val)
           (reg env))
  (assign val (const ok))

O corpo de um procedimento é sempre compilado (por compile-lambda-body) como uma sequência com alvo val e ligação return. A sequência neste caso consiste em uma única expressão if:

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

Compile-if gera código que primeiro calcula o predicado (destinado a val), então verifica o resultado e salta ao redor do ramo verdadeiro se o predicado for falso. Env e continue são preservados ao redor do código do predicado, já que eles podem ser necessários para o restante da expressão if. Como a expressão if é a expressão final (e única) na sequência que compõe o corpo do procedimento, seu alvo é val e sua ligação é return, então os ramos verdadeiro e falso são compilados com alvo val e ligação return. (Ou seja, o valor do condicional, que é o valor calculado por qualquer um de seus ramos, é o valor do procedimento.)

⟨salvar continue, env se modificado pelo 
 predicado e necessário pelos ramos⟩
  ⟨compilação do predicado, 
   alvo val, ligação next⟩
  ⟨restaurar continue, env se salvo acima⟩
  (test (op false?) (reg val))
  (branch (label false-branch4))
true-branch5
  ⟨compilação do ramo verdadeiro, 
   alvo val, ligação return⟩
false-branch4
  ⟨compilação do ramo falso, 
   alvo val, ligação return⟩
after-if3

O predicado (= n 1) é uma chamada de procedimento. Isso procura o operador (o símbolo =) e coloca esse valor em proc. Ele então monta os argumentos 1 e o valor de n em argl. Então ele testa se proc contém um procedimento primitivo ou composto, e despacha para um ramo primitivo ou composto de acordo. Ambos os ramos retomam no rótulo after-call. Os requisitos para preservar registradores ao redor da avaliação do operador e operandos não resultam em nenhum salvamento de registradores, porque neste caso essas avaliações não modificam os registradores em questão.

  (assign proc (op lookup-variable-value)
               (const =) 
               (reg env))
  (assign val (const 1))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value)
              (const n)
              (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch17))
compiled-branch16
  (assign continue (label after-call15))
  (assign val (op compiled-procedure-entry)
              (reg proc))
  (goto (reg val))
primitive-branch17
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
after-call15

O ramo verdadeiro, que é a constante 1, compila (com alvo val e ligação return) para

(assign val (const 1))
(goto (reg continue))

O código para o ramo falso é outra chamada de procedimento, onde o procedimento é o valor do símbolo *, e os argumentos são n e o resultado de outra chamada de procedimento (uma chamada para factorial). Cada uma dessas chamadas configura proc e argl e seus próprios ramos primitivos e compostos. Figura 5.17 mostra a compilação completa da definição do procedimento factorial. Observe que o possível save e restore de continue e env ao redor do predicado, mostrado acima, são de fato gerados, porque esses registradores são modificados pela chamada de procedimento no predicado e necessários para a chamada de procedimento e a ligação return nos ramos.

Figura 5.17: $↓$ Compilação da definição do procedimento factorial.

;; constrói o procedimento e salta sobre o código
;; para o corpo do procedimento
  (assign val
          (op make-compiled-procedure) 
          (label entry2) 
          (reg env))
  (goto (label after-lambda1))
entry2     ; chamadas para factorial entrarão aqui
  (assign env 
          (op compiled-procedure-env)
          (reg proc))
  (assign env
          (op extend-environment) 
          (const (n)) 
          (reg argl) 
          (reg env))
;; começa o corpo real do procedimento
  (save continue)
  (save env)
;; computa (= n 1)
  (assign proc 
          (op lookup-variable-value) 
          (const =) 
          (reg env))
  (assign val (const 1))
  (assign argl (op list) (reg val))
  (assign val 
          (op lookup-variable-value) 
          (const n) 
          (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch17))
compiled-branch16
  (assign continue (label after-call15))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch17
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))
after-call15   ; val agora contém o resultado de (= n 1)
  (restore env)
  (restore continue)
  (test (op false?) (reg val))
  (branch (label false-branch4))
true-branch5  ; retorna 1
  (assign val (const 1))
  (goto (reg continue))

false-branch4
;; computa e retorna (* (factorial (- n 1)) n)
  (assign proc 
          (op lookup-variable-value) 
          (const *) 
          (reg env))
  (save continue)
  (save proc)   ; salva o procedimento *
  (assign val 
          (op lookup-variable-value) 
          (const n) 
          (reg env))
  (assign argl (op list) (reg val))
  (save argl)   ; salva a lista parcial de argumentos para *
;; computa (factorial (- n 1)), que é o outro argumento para *
  (assign proc
          (op lookup-variable-value) 
          (const factorial) 
          (reg env))
  (save proc)  ; salva o procedimento factorial
;; computa (- n 1), que é o argumento para factorial
  (assign proc 
          (op lookup-variable-value)
          (const -) 
          (reg env))
  (assign val (const 1))
  (assign argl (op list) (reg val))
  (assign val 
          (op lookup-variable-value) 
          (const n) 
          (reg env))
  (assign argl (op cons) (reg val) (reg argl))
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch8))
compiled-branch7
  (assign continue (label after-call6))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch8
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))

after-call6   ; val agora contém o resultado de (- n 1)
  (assign argl (op list) (reg val))
  (restore proc) ; restaura factorial
;; aplica factorial
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch11))
compiled-branch10
  (assign continue (label after-call9))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch11
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))
after-call9      ; val agora contém o resultado
                 ; de (factorial (- n 1))
  (restore argl) ; restaura a lista parcial de argumentos para *
  (assign argl (op cons) (reg val) (reg argl))
  (restore proc) ; restaura *
  (restore continue)
;; aplica * e retorna seu valor
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch14))
compiled-branch13
;; note que um procedimento composto aqui
;; é chamado recursivamente em cauda
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch14
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))
  (goto (reg continue))
after-call12
after-if3
after-lambda1
;; atribui o procedimento à variável factorial
  (perform (op define-variable!) 
           (const factorial) 
           (reg val) 
           (reg env))
  (assign val (const ok))

Exercício 5.33: Considere a seguinte definição de um procedimento fatorial, que é ligeiramente diferente da dada acima:
(define (factorial-alt n)
  (if (= n 1)
      1
      (* n (factorial-alt (- n 1)))))
Compile este procedimento e compare o código resultante com o produzido para factorial. Explique quaisquer diferenças que você encontrar. Algum dos programas executa mais eficientemente que o outro?

Exercício 5.34: Compile o fatorial iterativo
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))
Anote o código resultante, mostrando a diferença essencial entre o código para as versões iterativa e recursiva de factorial que faz um processo acumular espaço na pilha e o outro rodar em espaço constante na pilha.

Exercício 5.35: Qual expressão foi compilada para produzir o código mostrado em Figura 5.18?

Figura 5.18: $↓$ Um exemplo de saída do compilador. Veja Exercício 5.35.

(assign val (op make-compiled-procedure) 
            (label entry16) 
            (reg env))
  (goto (label after-lambda15))
entry16
  (assign env (op compiled-procedure-env)
              (reg proc))
  (assign env (op extend-environment) 
              (const (x)) 
              (reg argl) 
              (reg env))
  (assign proc (op lookup-variable-value) 
               (const +) 
               (reg env))
  (save continue) (save proc) (save env)
  (assign proc (op lookup-variable-value) 
               (const g) 
               (reg env))
  (save proc)
  (assign proc (op lookup-variable-value) 
               (const +) 
               (reg env))
  (assign val (const 2))
  (assign argl (op list) (reg val))
  (assign val (op lookup-variable-value)
              (const x) 
              (reg env))
  (assign argl (op cons)
               (reg val)
               (reg argl))
  (test (op primitive-procedure?)
        (reg proc))
  (branch (label primitive-branch19))
compiled-branch18
  (assign continue (label after-call17))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch19
  (assign val
          (op apply-primitive-procedure)
          (reg proc) 
          (reg argl))
after-call17
  (assign argl (op list) (reg val))
  (restore proc)
  (test (op primitive-procedure?)
        (reg proc))
  (branch (label primitive-branch22))
compiled-branch21
  (assign continue (label after-call20))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch22
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))
after-call20
  (assign argl (op list) (reg val))
  (restore env)
  (assign val
          (op lookup-variable-value) 
          (const x) 
          (reg env))
  (assign argl
          (op cons)
          (reg val)
          (reg argl))
  (restore proc)
  (restore continue)
  (test (op primitive-procedure?)
        (reg proc))
  (branch (label primitive-branch25))
compiled-branch24
  (assign val (op compiled-procedure-entry)
              (reg proc))
  (goto (reg val))
primitive-branch25
  (assign val 
          (op apply-primitive-procedure)
          (reg proc) 
          (reg argl))
  (goto (reg continue))
after-call23
after-lambda15
  (perform (op define-variable!) 
           (const f) 
           (reg val) 
           (reg env))
  (assign val (const ok))

Exercício 5.36: Qual ordem de avaliação nosso compilador produz para os operandos de uma combinação? É da esquerda para a direita, da direita para a esquerda, ou alguma outra ordem? Onde no compilador essa ordem é determinada? Modifique o compilador para que ele produza alguma outra ordem de avaliação. (Veja a discussão sobre ordem de avaliação para o avaliador de controle explícito em 5.4.1.) Como mudar a ordem de avaliação dos operandos afeta a eficiência do código que constrói a lista de argumentos?

Exercício 5.37: Uma maneira de entender o mecanismo preserving do compilador para otimizar o uso da pilha é ver quais operações extras seriam geradas se não usássemos essa ideia. Modifique preserving para que ele sempre gere as operações save e restore. Compile algumas expressões simples e identifique as operações desnecessárias na pilha que são geradas. Compare o código com o gerado com o mecanismo preserving intacto.

Exercício 5.38: Nosso compilador é inteligente sobre evitar operações desnecessárias na pilha, mas não é nada inteligente quando se trata de compilar chamadas para os procedimentos primitivos da linguagem em termos das operações primitivas fornecidas pela máquina. Por exemplo, considere quanto código é compilado para calcular (+ a 1): O código configura uma lista de argumentos em argl, coloca o procedimento de adição primitiva (que ele encontra procurando o símbolo + no ambiente) em proc, e testa se o procedimento é primitivo ou composto. O compilador sempre gera código para realizar o teste, bem como código para os ramos primitivo e composto (apenas um dos quais será executado). Não mostramos a parte do controlador que implementa primitivas, mas presumimos que essas instruções fazem uso de operações aritméticas primitivas nos caminhos de dados da máquina. Considere quanto menos código seria gerado se o compilador pudesse abrir o código de primitivas—ou seja, se ele pudesse gerar código para diretamente usar essas operações primitivas da máquina. A expressão (+ a 1) poderia ser compilada em algo tão simples quanto³²⁸
(assign val (op lookup-variable-value) 
            (const a) 
            (reg env))
(assign val (op +)
            (reg val)
            (const 1))
Neste exercício, estenderemos nosso compilador para suportar a abertura de código de primitivas selecionadas. Código especializado será gerado para chamadas a esses procedimentos primitivos em vez do código geral de aplicação de procedimento. Para suportar isso, aumentaremos nossa máquina com registradores de argumentos especiais arg1 e arg2. As operações aritméticas primitivas da máquina receberão suas entradas de arg1 e arg2. Os resultados podem ser colocados em val, arg1 ou arg2.

O compilador deve ser capaz de reconhecer a aplicação de uma primitiva de código aberto no programa fonte. Aumentaremos a despacho no procedimento compile para reconhecer os nomes dessas primitivas em adição às palavras reservadas (as formas especiais) que ele atualmente reconhece.³²⁹ Para cada forma especial, nosso compilador tem um gerador de código. Neste exercício, construiremos uma família de geradores de código para as primitivas de código aberto.

As primitivas de código aberto, ao contrário das formas especiais, precisam que seus operandos sejam avaliados. Escreva um gerador de código spread-arguments para uso por todos os geradores de código de código aberto. Spread-arguments deve receber uma lista de operandos e compilar os operandos dados destinados a registradores de argumentos sucessivos. Note que um operando pode conter uma chamada para uma primitiva de código aberto, então os registradores de argumentos terão que ser preservados durante a avaliação do operando.

Para cada um dos procedimentos primitivos =, *, -, e +, escreva um gerador de código que receba uma combinação com esse operador, junto com um alvo e um descritor de ligação, e produza código para espalhar os argumentos nos registradores e então realizar a operação destinada ao alvo dado com a ligação dada. Você só precisa lidar com expressões com dois operandos. Faça compile despachar para esses geradores de código.

Teste seu novo compilador no exemplo factorial. Compare o código resultante com o resultado produzido sem código aberto.

Estenda seus geradores de código para + e * para que eles possam lidar com expressões com um número arbitrário de operandos. Uma expressão com mais de dois operandos terá que ser compilada em uma sequência de operações, cada uma com apenas duas entradas.

5.5.6Endereçamento Léxico

Uma das otimizações mais comuns realizadas por compiladores é a otimização da busca de variáveis. Nosso compilador, como o implementamos até agora, gera código que usa a operação lookup-variable-value da máquina do avaliador. Essa operação busca uma variável comparando-a com cada variável que está atualmente vinculada, percorrendo os frames do ambiente de execução, um por um. Essa busca pode ser custosa se os frames estiverem profundamente aninhados ou se houver muitas variáveis. Por exemplo, considere o problema de buscar o valor de x ao avaliar a expressão (* x y z) em uma aplicação do procedimento retornado por:

(let ((x 3) (y 4))
  (lambda (a b c d e)
    (let ((y (* a b x))
          (z (+ c d x)))
      (* x y z))))

Como uma expressão let é apenas açúcar sintático para uma combinação lambda, essa expressão é equivalente a:

((lambda (x y)
   (lambda (a b c d e)
     ((lambda (y z) (* x y z))
      (* a b x)
      (+ c d x)))
 3
 4)

Cada vez que lookup-variable-value busca por x, ele deve determinar que o símbolo x não é eq? a y ou z (no primeiro frame), nem a a, b, c, d ou e (no segundo frame). Assumiremos, por enquanto, que nossos programas não usam define—que as variáveis são vinculadas apenas com lambda. Como nossa linguagem tem escopo léxico, o ambiente de execução para qualquer expressão terá uma estrutura que reflete a estrutura léxica do programa em que a expressão aparece.³³⁰ Assim, o compilador pode saber, ao analisar a expressão acima, que cada vez que o procedimento é aplicado, a variável x em (* x y z) será encontrada dois frames acima do frame atual e será a primeira variável naquele frame.

Podemos explorar esse fato inventando um novo tipo de operação de busca de variável, lexical-address-lookup, que recebe como argumentos um ambiente e um endereço léxico que consiste em dois números: um número do frame, que especifica quantos frames devem ser pulados, e um número de deslocamento, que especifica quantas variáveis devem ser puladas naquele frame. Lexical-address-lookup produzirá o valor da variável armazenada naquele endereço léxico em relação ao ambiente atual. Se adicionarmos a operação lexical-address-lookup à nossa máquina, podemos fazer o compilador gerar código que referencia variáveis usando essa operação, em vez de lookup-variable-value. Da mesma forma, nosso código compilado pode usar uma nova operação lexical-address-set! em vez de set-variable-value!.

Para gerar tal código, o compilador deve ser capaz de determinar o endereço léxico de uma variável para a qual está prestes a compilar uma referência. O endereço léxico de uma variável em um programa depende de onde se está no código. Por exemplo, no seguinte programa, o endereço de x na expressão ⟨e1⟩ é (2, 0)—dois frames atrás e a primeira variável no frame. Nesse ponto, y está no endereço (0, 0) e c está no endereço (1, 2). Na expressão ⟨e2⟩, x está em (1, 0), y está em (1, 1) e c está em (0, 2).

((lambda (x y)
   (lambda (a b c d e)
     ((lambda (y z) ⟨e1⟩)
      ⟨e2⟩
      (+ c d x))))
 3
 4)

Uma maneira de o compilador produzir código que usa endereçamento léxico é manter uma estrutura de dados chamada ambiente de tempo de compilação. Essa estrutura mantém o controle de quais variáveis estarão em quais posições em quais frames no ambiente de execução quando uma operação de acesso a variável for executada. O ambiente de tempo de compilação é uma lista de frames, cada um contendo uma lista de variáveis. (É claro que não haverá valores vinculados às variáveis, já que os valores não são computados em tempo de compilação.) O ambiente de tempo de compilação torna-se um argumento adicional para compile e é passado adiante para cada gerador de código. A chamada de nível superior para compile usa um ambiente de tempo de compilação vazio. Quando o corpo de um lambda é compilado, compile-lambda-body estende o ambiente de tempo de compilação com um frame contendo os parâmetros do procedimento, de modo que a sequência que compõe o corpo é compilada com esse ambiente estendido. Em cada ponto da compilação, compile-variable e compile-assignment usam o ambiente de tempo de compilação para gerar os endereços léxicos apropriados.

Exercício 5.39 até Exercício 5.43 descrevem como completar esse esboço da estratégia de endereçamento léxico para incorporar a busca léxica ao compilador. Exercício 5.44 descreve outro uso para o ambiente de tempo de compilação.

Exercício 5.39: Escreva um procedimento lexical-address-lookup que implemente a nova operação de busca. Ele deve receber dois argumentos—um endereço léxico e um ambiente de execução—e retornar o valor da variável armazenada no endereço léxico especificado. Lexical-address-lookup deve sinalizar um erro se o valor da variável for o símbolo *unassigned*.³³¹ Escreva também um procedimento lexical-address-set! que implemente a operação que altera o valor da variável em um endereço léxico especificado.

Exercício 5.40: Modifique o compilador para manter o ambiente de tempo de compilação conforme descrito acima. Ou seja, adicione um argumento de ambiente de tempo de compilação para compile e os vários geradores de código, e estenda-o em compile-lambda-body.

Exercício 5.41: Escreva um procedimento find-variable que receba como argumentos uma variável e um ambiente de tempo de compilação e retorne o endereço léxico da variável em relação a esse ambiente. Por exemplo, no fragmento de programa mostrado acima, o ambiente de tempo de compilação durante a compilação da expressão ⟨e1⟩ é ((y z) (a b c d e) (x y)). Find-variable deve produzir
(find-variable 
 'c '((y z) (a b c d e) (x y)))
(1 2)

(find-variable 
 'x '((y z) (a b c d e) (x y)))
(2 0)

(find-variable 
 'w '((y z) (a b c d e) (x y)))
not-found

Exercício 5.42: Usando find-variable do Exercício 5.41, reescreva compile-variable e compile-assignment para gerar instruções de endereçamento léxico. Nos casos em que find-variable retornar not-found (ou seja, quando a variável não estiver no ambiente de tempo de compilação), você deve fazer com que os geradores de código usem as operações do avaliador, como antes, para buscar a vinculação. (O único lugar onde uma variável que não é encontrada em tempo de compilação pode estar é no ambiente global, que faz parte do ambiente de execução, mas não faz parte do ambiente de tempo de compilação.³³² Assim, se você quiser, pode fazer com que as operações do avaliador busquem diretamente no ambiente global, que pode ser obtido com a operação (op get-global-environment), em vez de fazer com que elas busquem em todo o ambiente de execução encontrado em env.) Teste o compilador modificado em alguns casos simples, como a combinação de lambda aninhada no início desta seção.

Exercício 5.43: Argumentamos em 4.1.6 que as definições internas para estrutura de blocos não devem ser consideradas "verdadeiras" defines. Em vez disso, o corpo de um procedimento deve ser interpretado como se as variáveis internas sendo definidas fossem instaladas como variáveis comuns de lambda inicializadas com seus valores corretos usando set!. 4.1.6 e Exercício 4.16 mostraram como modificar o interpretador metacircular para realizar isso, escaneando as definições internas. Modifique o compilador para realizar a mesma transformação antes de compilar o corpo de um procedimento.

Exercício 5.44: Nesta seção, focamos no uso do ambiente de tempo de compilação para produzir endereços léxicos. Mas existem outros usos para ambientes de tempo de compilação. Por exemplo, em Exercício 5.38, aumentamos a eficiência do código compilado ao abrir o código de procedimentos primitivos. Nossa implementação tratou os nomes dos procedimentos de código aberto como palavras reservadas. Se um programa redefinisse tal nome, o mecanismo descrito em Exercício 5.38 ainda abriria o código como um primitivo, ignorando a nova vinculação. Por exemplo, considere o procedimento
(lambda (+ * a b x y)
  (+ (* a x) (* b y)))
que calcula uma combinação linear de x e y. Poderíamos chamá-lo com argumentos +matrix, *matrix e quatro matrizes, mas o compilador de código aberto ainda abriria o código de + e * em (+ (* a x) (* b y)) como os primitivos + e *. Modifique o compilador de código aberto para consultar o ambiente de tempo de compilação a fim de compilar o código correto para expressões envolvendo os nomes de procedimentos primitivos. (O código funcionará corretamente desde que o programa não define ou set! esses nomes.)

5.5.7Interconectando Código Compilado ao Avaliador

Ainda não explicamos como carregar código compilado na máquina do avaliador ou como executá-lo. Assumiremos que a máquina do avaliador de controle explícito foi definida como em 5.4.4, com as operações adicionais especificadas em Nota de rodapé 323. Implementaremos um procedimento compile-and-go que compila uma expressão Scheme, carrega o código objeto resultante na máquina do avaliador e faz com que a máquina execute o código no ambiente global do avaliador, imprima o resultado e entre no loop de leitura-avaliação-impressão do avaliador. Também modificaremos o avaliador para que expressões interpretadas possam chamar procedimentos compilados, além de interpretados. Podemos então colocar um procedimento compilado na máquina e usar o avaliador para chamá-lo:

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)

;;; EC-Eval value:
120

Para permitir que o avaliador lide com procedimentos compilados (por exemplo, para avaliar a chamada a factorial acima), precisamos mudar o código em apply-dispatch (5.4.1) para que ele reconheça procedimentos compilados (distintos de procedimentos compostos ou primitivos) e transfira o controle diretamente para o ponto de entrada do código compilado:³³³

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

compiled-apply
  (restore continue)
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))

Observe a restauração de continue em compiled-apply. Lembre-se de que o avaliador foi organizado de modo que, em apply-dispatch, a continuação estaria no topo da pilha. O ponto de entrada do código compilado, por outro lado, espera que a continuação esteja em continue, então continue deve ser restaurado antes que o código compilado seja executado.

Para nos permitir executar algum código compilado quando iniciarmos a máquina do avaliador, adicionamos uma instrução branch no início da máquina do avaliador, que faz com que a máquina vá para um novo ponto de entrada se o registrador flag estiver setado.³³⁴

;; branches if flag is set:
(branch (label external-entry)) 
read-eval-print-loop
  (perform (op initialize-stack))
  …

External-entry assume que a máquina é iniciada com val contendo a localização de uma sequência de instruções que coloca um resultado em val e termina com (goto (reg continue)). Começar nesse ponto de entrada salta para a localização designada por val, mas primeiro atribui continue para que a execução retorne a print-result, que imprime o valor em val e então vai para o início do loop de leitura-avaliação-impressão do avaliador.³³⁵

external-entry
  (perform (op initialize-stack))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (reg val))

Agora podemos usar o seguinte procedimento para compilar uma definição de procedimento, executar o código compilado e executar o loop de leitura-avaliação-impressão para que possamos testar o procedimento. Como queremos que o código compilado retorne para a localização em continue com seu resultado em val, compilamos a expressão com um alvo de val e um linkage de return. Para transformar o código objeto produzido pelo compilador em instruções executáveis para a máquina de registradores do avaliador, usamos o procedimento assemble do simulador de máquina de registradores (5.2.2). Em seguida, inicializamos o registrador val para apontar para a lista de instruções, setamos o flag para que o avaliador vá para external-entry e iniciamos o avaliador.

(define (compile-and-go expression)
  (let ((instructions
         (assemble 
          (statements
           (compile 
            expression 'val 'return))
          eceval)))
    (set! the-global-environment
          (setup-environment))
    (set-register-contents! 
     eceval 'val instructions)
    (set-register-contents! 
     eceval 'flag true)
    (start eceval)))

Se tivermos configurado o monitoramento da pilha, como no final de 5.4.4, podemos examinar o uso da pilha pelo código compilado:

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))
(total-pushes = 0, maximum-depth = 0)

;;; EC-Eval value:
ok

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

;;; EC-Eval value:
120

Compare este exemplo com a avaliação de (factorial 5) usando a versão interpretada do mesmo procedimento, mostrada no final de 5.4.4. A versão interpretada exigiu 144 pushes e uma profundidade máxima de pilha de 28. Isso ilustra a otimização resultante de nossa estratégia de compilação.

Interpretação e Compilação

Com os programas nesta seção, podemos agora experimentar com as estratégias alternativas de execução de interpretação e compilação.³³⁶ Um interpretador eleva a máquina ao nível do programa do usuário; um compilador reduz o programa do usuário ao nível da linguagem de máquina. Podemos considerar a linguagem Scheme (ou qualquer linguagem de programação) como uma família coerente de abstrações erguidas sobre a linguagem de máquina. Interpretadores são bons para o desenvolvimento e depuração interativa de programas porque os passos da execução do programa são organizados em termos dessas abstrações, e são, portanto, mais inteligíveis para o programador. O código compilado pode executar mais rápido, porque os passos da execução do programa são organizados em termos da linguagem de máquina, e o compilador é livre para fazer otimizações que cortam através das abstrações de nível superior.³³⁷

As alternativas de interpretação e compilação também levam a diferentes estratégias para portar linguagens para novos computadores. Suponha que desejamos implementar Lisp para uma nova máquina. Uma estratégia é começar com o avaliador de controle explícito de 5.4 e traduzir suas instruções para instruções da nova máquina. Uma estratégia diferente é começar com o compilador e mudar os geradores de código para que eles gerem código para a nova máquina. A segunda estratégia nos permite executar qualquer programa Lisp na nova máquina, primeiro compilando-o com o compilador rodando em nosso sistema Lisp original e, em seguida, vinculando-o a uma versão compilada da biblioteca de tempo de execução.³³⁸ Melhor ainda, podemos compilar o próprio compilador e rodá-lo na nova máquina para compilar outros programas Lisp.³³⁹ Ou podemos compilar um dos interpretadores de 4.1 para produzir um interpretador que roda na nova máquina.

Exercício 5.45: Comparando as operações de pilha usadas pelo código compilado com as operações de pilha usadas pelo avaliador para o mesmo cálculo, podemos determinar até que ponto o compilador otimiza o uso da pilha, tanto em velocidade (reduzindo o número total de operações de pilha) quanto em espaço (reduzindo a profundidade máxima da pilha). Comparando esse uso otimizado da pilha com o desempenho de uma máquina de propósito especial para o mesmo cálculo, obtemos alguma indicação da qualidade do compilador.

Exercício 5.27 pediu que você determinasse, como uma função de $n$ , o número de pushes e a profundidade máxima da pilha necessária pelo avaliador para calcular $n!$ usando o procedimento fatorial recursivo dado acima. Exercício 5.14 pediu que você fizesse as mesmas medições para a máquina de fatorial de propósito especial mostrada em Figura 5.11. Agora, realize a mesma análise usando o procedimento factorial compilado.
Calcule a razão entre o número de pushes na versão compilada e o número de pushes na versão interpretada, e faça o mesmo para a profundidade máxima da pilha. Como o número de operações e a profundidade da pilha usada para calcular $n!$ são lineares em $n$ , essas razões devem se aproximar de constantes à medida que $n$ se torna grande. Quais são essas constantes? Da mesma forma, encontre as razões do uso da pilha na máquina de propósito especial para o uso na versão interpretada.

Compare as razões para a máquina de propósito especial versus o código interpretado com as razões para o código compilado versus o código interpretado. Você deve descobrir que a máquina de propósito especial se sai muito melhor que o código compilado, já que o código do controlador feito à mão deve ser muito melhor que o produzido por nosso compilador rudimentar de propósito geral.

Você pode sugerir melhorias para o compilador que o ajudariam a gerar código que se aproximasse mais em desempenho da versão feita à mão?

Exercício 5.46: Realize uma análise como a em Exercício 5.45 para determinar a eficácia de compilar o procedimento Fibonacci recursivo em árvore
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))
comparado à eficácia de usar a máquina de Fibonacci de propósito especial de Figura 5.12. (Para medição do desempenho interpretado, veja Exercício 5.29.) Para Fibonacci, o recurso de tempo usado não é linear em $n;$ portanto, as razões das operações de pilha não se aproximarão de um valor limite que seja independente de $n$ .

Exercício 5.47: Esta seção descreveu como modificar o avaliador de controle explícito para que o código interpretado possa chamar procedimentos compilados. Mostre como modificar o compilador para que procedimentos compilados possam chamar não apenas procedimentos primitivos e compilados, mas também procedimentos interpretados. Isso requer modificar compile-procedure-call para lidar com o caso de procedimentos compostos (interpretados). Certifique-se de lidar com todas as mesmas combinações de target e linkage como em compile-proc-appl. Para fazer a aplicação real do procedimento, o código precisa pular para o ponto de entrada compound-apply do avaliador. Esse rótulo não pode ser referenciado diretamente no código objeto (já que o montador exige que todos os rótulos referenciados pelo código que está montando sejam definidos lá), então adicionaremos um registrador chamado compapp à máquina do avaliador para manter esse ponto de entrada e adicionaremos uma instrução para inicializá-lo:
  (assign compapp (label compound-apply))
  ;; branches if flag is set:
  (branch (label external-entry))
read-eval-print-loop …
Para testar seu código, comece definindo um procedimento f que chama um procedimento g. Use compile-and-go para compilar a definição de f e iniciar o avaliador. Agora, digitando no avaliador, defina g e tente chamar f.

Exercício 5.48: A interface compile-and-go implementada nesta seção é desajeitada, já que o compilador só pode ser chamado uma vez (quando a máquina do avaliador é iniciada). Aumente a interface compilador-interpretador fornecendo um primitivo compile-and-run que pode ser chamado de dentro do avaliador de controle explícito da seguinte forma:
;;; EC-Eval input:
(compile-and-run
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)

;;; EC-Eval value:
120

Exercício 5.49: Como uma alternativa ao uso do loop de leitura-avaliação-impressão do avaliador de controle explícito, projete uma máquina de registradores que execute um loop de leitura-compilação-execução-impressão. Ou seja, a máquina deve executar um loop que lê uma expressão, a compila, monta e executa o código resultante e imprime o resultado. Isso é fácil de rodar em nossa configuração simulada, já que podemos organizar para chamar os procedimentos compile e assemble como "operações de máquina de registradores."

Exercício 5.50: Use o compilador para compilar o avaliador metacircular de 4.1 e execute este programa usando o simulador de máquina de registradores. (Para compilar mais de uma definição de cada vez, você pode empacotar as definições em um begin.) O interpretador resultante rodará muito lentamente devido aos múltiplos níveis de interpretação, mas fazer todos os detalhes funcionarem é um exercício instrutivo.

Exercício 5.51: Desenvolva uma implementação rudimentar de Scheme em C (ou alguma outra linguagem de baixo nível de sua escolha) traduzindo o avaliador de controle explícito de 5.4 para C. Para rodar esse código, você também precisará fornecer rotinas apropriadas de alocação de armazenamento e outros suportes de tempo de execução.

Exercício 5.52: Como um contraponto a Exercício 5.51, modifique o compilador para que ele compile procedimentos Scheme em sequências de instruções C. Compile o avaliador metacircular de 4.1 para produzir um interpretador Scheme escrito em C.

Notas de Rodapé

³¹⁸ Esta é uma afirmação teórica. Não estamos afirmando que os caminhos de dados do avaliador sejam um conjunto particularmente conveniente ou eficiente de caminhos de dados para um computador de propósito geral. Por exemplo, eles não são muito bons para implementar cálculos de ponto flutuante de alta performance ou cálculos que manipulam intensivamente vetores de bits.

³¹⁹ Na verdade, a máquina que executa código compilado pode ser mais simples que a máquina do interpretador, porque não usaremos os registradores exp e unev. O interpretador usou esses registradores para manter partes de expressões não avaliadas. Com o compilador, no entanto, essas expressões são incorporadas ao código compilado que a máquina de registradores executará. Pela mesma razão, não precisamos das operações da máquina que lidam com a sintaxe das expressões. Mas o código compilado usará algumas operações adicionais da máquina (para representar objetos de procedimentos compilados) que não apareceram na máquina do avaliador de controle explícito.

³²⁰ Observe, no entanto, que nosso compilador é um programa Scheme, e os procedimentos de sintaxe que ele usa para manipular expressões são os procedimentos reais do Scheme usados com o avaliador metacircular. Para o avaliador de controle explícito, em contraste, assumimos que operações de sintaxe equivalentes estavam disponíveis como operações para a máquina de registradores. (É claro que, quando simulamos a máquina de registradores em Scheme, usamos os procedimentos reais do Scheme em nossa simulação da máquina de registradores.)

³²¹ Este procedimento usa um recurso do Lisp chamado backquote (ou quasiquote) que é útil para construir listas. Preceder uma lista com um símbolo de backquote é muito parecido com citá-la, exceto que qualquer coisa na lista que estiver marcado com uma vírgula é avaliado.

Por exemplo, se o valor de linkage for o símbolo branch25, então a expressão

`((goto (label ,linkage)))

avalia para a lista

((goto (label branch25)))

Da mesma forma, se o valor de x for a lista (a b c), então

`(1 2 ,(car x))

avalia para a lista

(1 2 a)

³²² Não podemos simplesmente usar os rótulos true-branch, false-branch e after-if como mostrado acima, porque pode haver mais de um if no programa. O compilador usa o procedimento make-label para gerar rótulos. Make-label recebe um símbolo como argumento e retorna um novo símbolo que começa com o símbolo dado. Por exemplo, chamadas sucessivas a (make-label 'a) retornariam a1, a2, e assim por diante. Make-label pode ser implementado de forma semelhante à geração de nomes de variáveis únicos na linguagem de consulta, como segue:

(define label-counter 0)

(define (new-label-number)
  (set! label-counter (+ 1 label-counter))
  label-counter)

(define (make-label name)
  (string->symbol
   (string-append 
    (symbol->string name)
    (number->string (new-label-number)))))

³²³ Precisamos de operações da máquina para implementar uma estrutura de dados para representar procedimentos compilados, análoga à estrutura para procedimentos compostos descrita em 4.1.3:

(define (make-compiled-procedure entry env)
  (list 'compiled-procedure entry env))
(define (compiled-procedure? proc)
  (tagged-list? proc 'compiled-procedure))
(define (compiled-procedure-entry c-proc) 
  (cadr c-proc))
(define (compiled-procedure-env c-proc)
  (caddr c-proc))

³²⁴ Na verdade, sinalizamos um erro quando o alvo não é val e o linkage é return, já que o único lugar onde solicitamos linkages return é na compilação de procedimentos, e nossa convenção é que procedimentos retornam seus valores em val.

³²⁵ Fazer um compilador gerar código recursivo em cauda pode parecer uma ideia simples. Mas a maioria dos compiladores para linguagens comuns, incluindo C e Pascal, não faz isso, e portanto essas linguagens não podem representar processos iterativos em termos de chamada de procedimento apenas. A dificuldade com recursão em cauda nessas linguagens é que suas implementações usam a pilha para armazenar argumentos de procedimento e variáveis locais, bem como endereços de retorno. As implementações do Scheme descritas neste livro armazenam argumentos e variáveis em memória para serem coletados como lixo. A razão para usar a pilha para variáveis e argumentos é que isso evita a necessidade de coleta de lixo em linguagens que não a exigiriam de outra forma, e geralmente se acredita ser mais eficiente. Compiladores Lisp sofisticados podem, de fato, usar a pilha para argumentos sem destruir a recursão em cauda. (Veja Hanson 1990 para uma descrição.) Há também algum debate sobre se a alocação em pilha é realmente mais eficiente que a coleta de lixo em primeiro lugar, mas os detalhes parecem depender de pontos finos da arquitetura do computador. (Veja Appel 1987 e Miller e Rozas 1994 para visões opostas sobre essa questão.)

³²⁶ A variável all-regs é vinculada à lista de nomes de todos os registradores:

(define all-regs '(env proc val argl continue))

³²⁷ Note que preserving chama append com três argumentos. Embora a definição de append mostrada neste livro aceite apenas dois argumentos, o Scheme normalmente fornece um procedimento append que aceita um número arbitrário de argumentos.

³²⁸ Usamos o mesmo símbolo + aqui para denotar tanto o procedimento da linguagem fonte quanto a operação da máquina. Em geral, não haverá uma correspondência um-para-um entre primitivas da linguagem fonte e primitivas da máquina.

³²⁹ Tornar as primitivas em palavras reservadas é, em geral, uma má ideia, já que um usuário não pode então redefinir esses nomes para diferentes procedimentos. Além disso, se adicionarmos palavras reservadas a um compilador que está em uso, programas existentes que definem procedimentos com esses nomes pararão de funcionar. Veja Exercício 5.44 para ideias sobre como evitar esse problema.

³³⁰ Isso não é verdade se permitirmos definições internas, a menos que as escaneemos. Veja Exercício 5.43.

³³¹ Esta é a modificação necessária para a busca de variáveis se implementarmos o método de escaneamento para eliminar definições internas (Exercício 5.43). Precisaremos eliminar essas definições para que o endereçamento léxico funcione.

³³² Endereços léxicos não podem ser usados para acessar variáveis no ambiente global, porque esses nomes podem ser definidos e redefinidos interativamente a qualquer momento. Com definições internas escaneadas, como em Exercício 5.43, as únicas definições que o compilador vê são aquelas no nível superior, que atuam no ambiente global. A compilação de uma definição não faz com que o nome definido seja inserido no ambiente de tempo de compilação.

³³³ É claro que, procedimentos compilados, assim como procedimentos interpretados, são compostos (não primitivos). Para compatibilidade com a terminologia usada no avaliador de controle explícito, nesta seção usaremos "composto" para significar interpretado (em oposição a compilado).

³³⁴ Agora que a máquina do avaliador começa com um branch, devemos sempre inicializar o registrador flag antes de iniciar a máquina do avaliador. Para iniciar a máquina em seu loop comum de leitura-avaliação-impressão, poderíamos usar

(define (start-eceval)
  (set! the-global-environment
        (setup-environment))
  (set-register-contents! eceval 'flag false)
  (start eceval))

³³⁵ Como um procedimento compilado é um objeto que o sistema pode tentar imprimir, também modificamos a operação de impressão do sistema user-print (de 4.1.4) para que ele não tente imprimir os componentes de um procedimento compilado:

(define (user-print object)
  (cond ((compound-procedure? object)
         (display 
          (list 'compound-procedure
                (procedure-parameters object)
                (procedure-body object)
                '<procedure-env>)))
        ((compiled-procedure? object)
         (display '<compiled-procedure>))
        (else (display object))))

³³⁶ Podemos fazer ainda melhor estendendo o compilador para permitir que código compilado chame procedimentos interpretados. Veja Exercício 5.47.

³³⁷ Independentemente da estratégia de execução, incorremos em uma sobrecarga significativa se insistirmos que erros encontrados na execução de um programa do usuário sejam detectados e sinalizados, em vez de serem permitidos matar o sistema ou produzir respostas erradas. Por exemplo, uma referência fora dos limites de um array pode ser detectada verificando a validade da referência antes de realizá-la. A sobrecarga de verificação, no entanto, pode ser muitas vezes o custo da referência ao array em si, e um programador deve ponderar velocidade contra segurança ao determinar se tal verificação é desejável. Um bom compilador deve ser capaz de produzir código com tais verificações, deve evitar verificações redundantes e deve permitir que programadores controlem a extensão e o tipo de verificação de erros no código compilado.

Compiladores para linguagens populares, como C e C++, colocam poucas operações de verificação de erros no código em execução, para que as coisas rodem o mais rápido possível. Como resultado, cabe aos programadores fornecer explicitamente verificações de erros. Infelizmente, as pessoas frequentemente negligenciam isso, mesmo em aplicações críticas onde a velocidade não é uma restrição. Seus programas levam vidas rápidas e perigosas. Por exemplo, o notório "Worm" que paralisou a Internet em 1988 explorou a falha do sistema operacional UNIX(tm) em verificar se o buffer de entrada transbordou no daemon finger. (Veja Spafford 1989.)

³³⁸ É claro que, com qualquer uma das estratégias de interpretação ou compilação, também devemos implementar para a nova máquina alocação de armazenamento, entrada e saída, e todas as várias operações que tomamos como "primitivas" em nossa discussão do avaliador e do compilador. Uma estratégia para minimizar o trabalho aqui é escrever o maior número possível dessas operações em Lisp e então compilá-las para a nova máquina. No final, tudo se reduz a um pequeno kernel (como coleta de lixo e o mecanismo para aplicar primitivas reais da máquina) que é codificado à mão para a nova máquina.

³³⁹ Essa estratégia leva a testes divertidos de correção do compilador, como verificar se a compilação de um programa na nova máquina, usando o compilador compilado, é idêntica à compilação do programa no sistema Lisp original. Rastrear a fonte das diferenças é divertido, mas muitas vezes frustrante, porque os resultados são extremamente sensíveis a detalhes minúsculos.