4.1O Avaliador Metacircular

Nosso avaliador para Lisp será implementado como um programa Lisp. Pode parecer circular pensar em avaliar programas Lisp usando um avaliador que é ele mesmo implementado em Lisp. No entanto, a avaliação é um processo, então é apropriado descrever o processo de avaliação usando Lisp, que, afinal, é nossa ferramenta para descrever processos.²⁰⁷ Um avaliador que é escrito na mesma linguagem que ele avalia é chamado de metacircular.

O avaliador metacircular é essencialmente uma formulação em Scheme do modelo de avaliação de ambiente descrito em 3.2. Lembre-se de que o modelo tem duas partes básicas:

1. Para avaliar uma combinação (uma expressão composta que não seja uma forma especial), avalie as subexpressões e então aplique o valor da subexpressão do operador aos valores das subexpressões dos operandos.
2. Para aplicar um procedimento composto a um conjunto de argumentos, avalie o corpo do procedimento em um novo ambiente. Para construir esse ambiente, estenda a parte do ambiente do objeto de procedimento por um quadro no qual os parâmetros formais do procedimento são vinculados aos argumentos aos quais o procedimento é aplicado.

Essas duas regras descrevem a essência do processo de avaliação, um ciclo básico no qual expressões a serem avaliadas em ambientes são reduzidas a procedimentos a serem aplicados a argumentos, que por sua vez são reduzidos a novas expressões a serem avaliadas em novos ambientes, e assim por diante, até chegarmos a símbolos, cujos valores são procurados no ambiente, e a procedimentos primitivos, que são aplicados diretamente (veja Figura 4.1).²⁰⁸ Este ciclo de avaliação será incorporado pela interação entre os dois procedimentos críticos no avaliador, eval e apply, que são descritos em 4.1.1 (veja Figura 4.1).

A implementação do avaliador dependerá de procedimentos que definem a sintaxe das expressões a serem avaliadas. Usaremos abstração de dados para tornar o avaliador independente da representação da linguagem. Por exemplo, em vez de nos comprometermos com a escolha de que uma atribuição seja representada por uma lista começando com o símbolo set!, usamos um predicado abstrato assignment? para testar uma atribuição, e usamos seletores abstratos assignment-variable e assignment-value para acessar as partes de uma atribuição. A implementação de expressões será descrita em detalhes em 4.1.2. Há também operações, descritas em 4.1.3, que especificam a representação de procedimentos e ambientes. Por exemplo, make-procedure constrói procedimentos compostos, lookup-variable-value acessa os valores das variáveis, e apply-primitive-procedure aplica um procedimento primitivo a uma dada lista de argumentos.

4.1.1O Núcleo do Avaliador

O processo de avaliação pode ser descrito como a interação entre dois procedimentos: eval e apply.

Eval

Eval recebe como argumentos uma expressão e um ambiente. Ele classifica a expressão e direciona sua avaliação. Eval é estruturado como uma análise de caso do tipo sintático da expressão a ser avaliada. Para manter o procedimento geral, expressamos a determinação do tipo de uma expressão de forma abstrata, sem nos comprometermos com nenhuma representação particular para os vários tipos de expressões. Cada tipo de expressão tem um predicado que testa por ele e um meio abstrato para selecionar suas partes. Esta sintaxe abstrata facilita ver como podemos mudar a sintaxe da linguagem usando o mesmo avaliador, mas com uma coleção diferente de procedimentos de sintaxe.

Expressões primitivas

• Para expressões autoavaliáveis, como números, eval retorna a própria expressão.
• Eval deve procurar variáveis no ambiente para encontrar seus valores.

Formas especiais

• Para expressões citadas, eval retorna a expressão que foi citada.
• Uma atribuição a (ou uma definição de) uma variável deve chamar recursivamente eval para calcular o novo valor a ser associado à variável. O ambiente deve ser modificado para alterar (ou criar) a vinculação da variável.
• Uma expressão if requer processamento especial de suas partes, de modo a avaliar o consequente se o predicado for verdadeiro, e caso contrário, avaliar a alternativa.
• Uma expressão lambda deve ser transformada em um procedimento aplicável, empacotando os parâmetros e o corpo especificados pela expressão lambda com o ambiente da avaliação.
• Uma expressão begin requer a avaliação de sua sequência de expressões na ordem em que aparecem.
• Uma análise de caso (cond) é transformada em um ninho de expressões if e então avaliada.

Combinações

• Para uma aplicação de procedimento, eval deve avaliar recursivamente a parte do operador e os operandos da combinação. O procedimento resultante e os argumentos são passados para apply, que lida com a aplicação real do procedimento.

Aqui está a definição de eval:

(define (eval exp env)
  (cond ((self-evaluating? exp) 
         exp)
        ((variable? exp) 
         (lookup-variable-value exp env))
        ((quoted? exp) 
         (text-of-quotation exp))
        ((assignment? exp) 
         (eval-assignment exp env))
        ((definition? exp) 
         (eval-definition exp env))
        ((if? exp) 
         (eval-if exp env))
        ((lambda? exp)
         (make-procedure 
          (lambda-parameters exp)
          (lambda-body exp)
          env))
        ((begin? exp)
         (eval-sequence 
          (begin-actions exp) 
          env))
        ((cond? exp) 
         (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values 
                 (operands exp) 
                 env)))
        (else
         (error "Unknown expression 
                 type: EVAL" exp))))

Para clareza, eval foi implementado como uma análise de caso usando cond. A desvantagem disso é que nosso procedimento lida apenas com alguns tipos distinguíveis de expressões, e nenhum novo pode ser definido sem editar a definição de eval. Na maioria das implementações de Lisp, a despacho sobre o tipo de uma expressão é feito de forma dirigida por dados. Isso permite que um usuário adicione novos tipos de expressões que eval pode distinguir, sem modificar a definição de eval em si. (Veja Exercício 4.3.)

Apply

Apply recebe dois argumentos, um procedimento e uma lista de argumentos aos quais o procedimento deve ser aplicado. Apply classifica procedimentos em dois tipos: Ele chama apply-primitive-procedure para aplicar primitivas; ele aplica procedimentos compostos avaliando sequencialmente as expressões que compõem o corpo do procedimento. O ambiente para a avaliação do corpo de um procedimento composto é construído estendendo o ambiente base carregado pelo procedimento para incluir um quadro que vincula os parâmetros do procedimento aos argumentos aos quais o procedimento é aplicado. Aqui está a definição de apply:

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure 
          procedure 
          arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters 
              procedure)
             arguments
             (procedure-environment 
              procedure))))
        (else
         (error "Unknown procedure 
                 type: APPLY" 
                procedure))))

Argumentos de procedimento

Quando eval processa uma aplicação de procedimento, ele usa list-of-values para produzir a lista de argumentos aos quais o procedimento deve ser aplicado. List-of-values recebe como argumento os operandos da combinação. Ele avalia cada operando e retorna uma lista dos valores correspondentes:²⁰⁹

(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values 
             (rest-operands exps) 
             env))))

Condicionais

Eval-if avalia a parte do predicado de uma expressão if no ambiente dado. Se o resultado for verdadeiro, eval-if avalia o consequente, caso contrário, avalia a alternativa:

(define (eval-if exp env)
  (if (true? (eval (if-predicate exp) env))
      (eval (if-consequent exp) env)
      (eval (if-alternative exp) env)))

O uso de true? em eval-if destaca a questão da conexão entre uma linguagem implementada e uma linguagem de implementação. O if-predicate é avaliado na linguagem sendo implementada e, portanto, produz um valor nessa linguagem. O predicado do interpretador true? traduz esse valor em um valor que pode ser testado pelo if na linguagem de implementação: A representação metacircular da verdade pode não ser a mesma que a do Scheme subjacente.²¹⁰

Sequências

Eval-sequence é usado por apply para avaliar a sequência de expressões no corpo de um procedimento e por eval para avaliar a sequência de expressões em uma expressão begin. Ele recebe como argumentos uma sequência de expressões e um ambiente, e avalia as expressões na ordem em que ocorrem. O valor retornado é o valor da expressão final.

(define (eval-sequence exps env)
  (cond ((last-exp? exps) 
         (eval (first-exp exps) env))
        (else 
         (eval (first-exp exps) env)
         (eval-sequence (rest-exps exps) 
                        env))))

Atribuições e definições

O seguinte procedimento lida com atribuições a variáveis. Ele chama eval para encontrar o valor a ser atribuído e transmite a variável e o valor resultante para set-variable-value! para ser instalado no ambiente designado.

(define (eval-assignment exp env)
  (set-variable-value! 
   (assignment-variable exp)
   (eval (assignment-value exp) env)
   env)
  'ok)

As definições de variáveis são tratadas de maneira semelhante.²¹¹

(define (eval-definition exp env)
  (define-variable! 
    (definition-variable exp)
    (eval (definition-value exp) env)
    env)
  'ok)

Escolhemos aqui retornar o símbolo ok como o valor de uma atribuição ou uma definição.²¹²

Exercício 4.1: Observe que não podemos dizer se o avaliador metacircular avalia operandos da esquerda para a direita ou da direita para a esquerda. Sua ordem de avaliação é herdada do Lisp subjacente: Se os argumentos para cons em list-of-values são avaliados da esquerda para a direita, então list-of-values avaliará operandos da esquerda para a direita; e se os argumentos para cons são avaliados da direita para a esquerda, então list-of-values avaliará operandos da direita para a esquerda.

Escreva uma versão de list-of-values que avalia operandos da esquerda para a direita, independentemente da ordem de avaliação no Lisp subjacente. Também escreva uma versão de list-of-values que avalia operandos da direita para a esquerda.

4.1.2Representando Expressões

O avaliador é reminiscente do programa de diferenciação simbólica discutido em 2.3.2. Ambos os programas operam em expressões simbólicas. Em ambos os programas, o resultado de operar em uma expressão composta é determinado operando recursivamente nas partes da expressão e combinando os resultados de uma forma que depende do tipo da expressão. Em ambos os programas, usamos abstração de dados para desacoplar as regras gerais de operação dos detalhes de como as expressões são representadas. No programa de diferenciação, isso significava que o mesmo procedimento de diferenciação poderia lidar com expressões algébricas em forma de prefixo, em forma de infixo ou em alguma outra forma. Para o avaliador, isso significa que a sintaxe da linguagem sendo avaliada é determinada unicamente pelos procedimentos que classificam e extraem partes das expressões.

Aqui está a especificação da sintaxe da nossa linguagem:

• Os únicos itens autoavaliáveis são números e strings:

  (define (self-evaluating? exp)
    (cond ((number? exp) true)
          ((string? exp) true)
          (else false)))

• Variáveis são representadas por símbolos:

  (define (variable? exp) (symbol? exp))

• Citações têm a forma (quote ⟨text-of-quotation⟩):²¹³

  (define (quoted? exp)
    (tagged-list? exp 'quote))
  
  (define (text-of-quotation exp)
    (cadr exp))

  Quoted? é definido em termos do procedimento tagged-list?, que identifica listas começando com um símbolo designado:

  (define (tagged-list? exp tag)
    (if (pair? exp)
        (eq? (car exp) tag)
        false))

• Atribuições têm a forma (set! ⟨var⟩ ⟨value⟩):

  (define (assignment? exp)
    (tagged-list? exp 'set!))
  
  (define (assignment-variable exp) 
    (cadr exp))
  
  (define (assignment-value exp) (caddr exp))

• Definições têm a forma

  (define ⟨var⟩ ⟨value⟩)

  ou a forma

  (define (⟨var⟩ ⟨param₁⟩ … ⟨paramₙ⟩)
    ⟨body⟩)

  A última forma (definição padrão de procedimento) é açúcar sintático para

  (define ⟨var⟩
    (lambda (⟨param₁⟩ … ⟨paramₙ⟩)
      ⟨body⟩))

  Os procedimentos de sintaxe correspondentes são os seguintes:

  (define (definition? exp)
    (tagged-list? exp 'define))
  
  (define (definition-variable exp)
    (if (symbol? (cadr exp))
        (cadr exp)
        (caadr exp)))
  
  (define (definition-value exp)
    (if (symbol? (cadr exp))
        (caddr exp)
        (make-lambda 
         (cdadr exp)   ; parâmetros formais
         (cddr exp)))) ; corpo

• Expressões lambda são listas que começam com o símbolo lambda:

  (define (lambda? exp) 
    (tagged-list? exp 'lambda))
  (define (lambda-parameters exp) (cadr exp))
  (define (lambda-body exp) (cddr exp))

  Também fornecemos um construtor para expressões lambda, que é usado por definition-value, acima:

  (define (make-lambda parameters body)
    (cons 'lambda (cons parameters body)))

• Condicionais começam com if e têm um predicado, um consequente e uma alternativa (opcional). Se a expressão não tiver parte alternativa, fornecemos false como alternativa.²¹⁴

  (define (if? exp) (tagged-list? exp 'if))
  (define (if-predicate exp) (cadr exp))
  (define (if-consequent exp) (caddr exp))
  (define (if-alternative exp)
    (if (not (null? (cdddr exp)))
        (cadddr exp)
        'false))

  Também fornecemos um construtor para expressões if, a ser usado por cond->if para transformar expressões cond em expressões if:

  (define (make-if predicate 
                   consequent 
                   alternative)
    (list 'if 
          predicate 
          consequent 
          alternative))

• Begin empacota uma sequência de expressões em uma única expressão. Incluímos operações de sintaxe em expressões begin para extrair a sequência real da expressão begin, bem como seletores que retornam a primeira expressão e o restante das expressões na sequência.²¹⁵

  (define (begin? exp) 
    (tagged-list? exp 'begin))
  (define (begin-actions exp) (cdr exp))
  (define (last-exp? seq) (null? (cdr seq)))
  (define (first-exp seq) (car seq))
  (define (rest-exps seq) (cdr seq))

  Também incluímos um construtor sequence->exp (para uso por cond->if) que transforma uma sequência em uma única expressão, usando begin se necessário:

  (define (sequence->exp seq)
    (cond ((null? seq) seq)
          ((last-exp? seq) (first-exp seq))
          (else (make-begin seq))))
  
  (define (make-begin seq) (cons 'begin seq))

• Uma aplicação de procedimento é qualquer expressão composta que não seja um dos tipos de expressão acima. O car da expressão é o operador, e o cdr é a lista de operandos:

  (define (application? exp) (pair? exp))
  (define (operator exp) (car exp))
  (define (operands exp) (cdr exp))
  (define (no-operands? ops) (null? ops))
  (define (first-operand ops) (car ops))
  (define (rest-operands ops) (cdr ops))

Expressões derivadas

Algumas formas especiais em nossa linguagem podem ser definidas em termos de expressões envolvendo outras formas especiais, em vez de serem implementadas diretamente. Um exemplo é cond, que pode ser implementado como um ninho de expressões if. Por exemplo, podemos reduzir o problema de avaliar a expressão

(cond ((> x 0) x)
      ((= x 0) (display 'zero) 0)
      (else (- x)))

ao problema de avaliar a seguinte expressão envolvendo if e begin:

(if (> x 0)
    x
    (if (= x 0)
        (begin (display 'zero) 0)
        (- x)))

Implementar a avaliação de cond dessa forma simplifica o avaliador porque reduz o número de formas especiais para as quais o processo de avaliação deve ser explicitamente especificado.

Incluímos procedimentos de sintaxe que extraem as partes de uma expressão cond, e um procedimento cond->if que transforma expressões cond em expressões if. Uma análise de caso começa com cond e tem uma lista de cláusulas predicado-ação. Uma cláusula é uma cláusula else se seu predicado for o símbolo else.²¹⁶

(define (cond? exp) 
  (tagged-list? exp 'cond))
(define (cond-clauses exp) (cdr exp))
(define (cond-else-clause? clause)
  (eq? (cond-predicate clause) 'else))
(define (cond-predicate clause) 
  (car clause))
(define (cond-actions clause) 
  (cdr clause))
(define (cond->if exp)
  (expand-clauses (cond-clauses exp)))
(define (expand-clauses clauses)
  (if (null? clauses)
      'false     ; sem cláusula else
      (let ((first (car clauses))
            (rest (cdr clauses)))
        (if (cond-else-clause? first)
            (if (null? rest)
                (sequence->exp 
                 (cond-actions first))
                (error "ELSE clause isn't 
                        last: COND->IF"
                       clauses))
            (make-if (cond-predicate first)
                     (sequence->exp 
                      (cond-actions first))
                     (expand-clauses 
                      rest))))))

Expressões (como cond) que escolhemos implementar como transformações sintáticas são chamadas de expressões derivadas. Expressões let também são expressões derivadas (veja Exercício 4.6).²¹⁷

Exercício 4.2: Louis Reasoner planeja reordenar as cláusulas cond em eval para que a cláusula para aplicações de procedimento apareça antes da cláusula para atribuições. Ele argumenta que isso tornará o interpretador mais eficiente: Como os programas geralmente contêm mais aplicações do que atribuições, definições e assim por diante, seu eval modificado geralmente verificará menos cláusulas do que o eval original antes de identificar o tipo de uma expressão.

1. O que há de errado com o plano de Louis? (Dica: O que o avaliador de Louis fará com a expressão (define x 3)?)
2. Louis está chateado que seu plano não funcionou. Ele está disposto a fazer qualquer coisa para fazer seu avaliador reconhecer aplicações de procedimento antes de verificar a maioria dos outros tipos de expressões. Ajude-o mudando a sintaxe da linguagem avaliada para que as aplicações de procedimento comecem com call. Por exemplo, em vez de (factorial 3) agora teremos que escrever (call factorial 3) e em vez de (+ 1 2) teremos que escrever (call + 1 2).

Exercício 4.3: Reescreva eval para que o despacho seja feito de forma dirigida por dados. Compare isso com o procedimento de diferenciação dirigido por dados de Exercício 2.73. (Você pode usar o car de uma expressão composta como o tipo da expressão, como é apropriado para a sintaxe implementada nesta seção.)

Exercício 4.4: Lembre-se das definições das formas especiais and e or do Capítulo 1:

• and: As expressões são avaliadas da esquerda para a direita. Se qualquer expressão avaliar para falso, falso é retornado; quaisquer expressões restantes não são avaliadas. Se todas as expressões avaliarem para valores verdadeiros, o valor da última expressão é retornado. Se não houver expressões, então verdadeiro é retornado.
• or: As expressões são avaliadas da esquerda para a direita. Se qualquer expressão avaliar para um valor verdadeiro, esse valor é retornado; quaisquer expressões restantes não são avaliadas. Se todas as expressões avaliarem para falso, ou se não houver expressões, então falso é retornado.

Instale and e or como novas formas especiais para o avaliador, definindo procedimentos de sintaxe apropriados e procedimentos de avaliação eval-and e eval-or. Alternativamente, mostre como implementar and e or como expressões derivadas.

Exercício 4.5: Scheme permite uma sintaxe adicional para cláusulas cond, (⟨test⟩ => ⟨recipient⟩). Se ⟨test⟩ avaliar para um valor verdadeiro, então ⟨recipient⟩ é avaliado. Seu valor deve ser um procedimento de um argumento; este procedimento é então invocado com o valor de ⟨test⟩, e o resultado é retornado como o valor da expressão cond. Por exemplo

(cond ((assoc 'b '((a 1) (b 2))) => cadr)
      (else false))

retorna 2. Modifique o tratamento de cond para que ele suporte essa sintaxe estendida.

Exercício 4.6: Expressões let são expressões derivadas, porque

(let ((⟨var₁⟩ ⟨exp₁⟩) … (⟨varₙ⟩ ⟨expₙ⟩))
  ⟨body⟩)

é equivalente a

((lambda (⟨var₁⟩ … ⟨varₙ⟩)
   ⟨body⟩)
 ⟨exp₁⟩
 …
 ⟨expₙ⟩)

Implemente uma transformação sintática let->combination que reduza a avaliação de expressões let à avaliação de combinações do tipo mostrado acima, e adicione a cláusula apropriada a eval para lidar com expressões let.

Exercício 4.7: Let* é semelhante a let, exceto que as ligações das variáveis do let* são realizadas sequencialmente da esquerda para a direita, e cada ligação é feita em um ambiente no qual todas as ligações anteriores são visíveis. Por exemplo

(let* ((x 3)
       (y (+ x 2))
       (z (+ x y 5)))
  (* x z))

retorna 39. Explique como uma expressão let* pode ser reescrita como um conjunto de expressões let aninhadas, e escreva um procedimento let*->nested-lets que realize essa transformação. Se já implementamos let (Exercício 4.6) e queremos estender o avaliador para lidar com let*, é suficiente adicionar uma cláusula a eval cuja ação é

(eval (let*->nested-lets exp) env)

ou devemos expandir explicitamente let* em termos de expressões não derivadas?

Exercício 4.8: “Named let” é uma variante de let que tem a forma

(let ⟨var⟩ ⟨bindings⟩ ⟨body⟩)

As ⟨bindings⟩ e ⟨body⟩ são como no let comum, exceto que ⟨var⟩ é ligado dentro de ⟨body⟩ a um procedimento cujo corpo é ⟨body⟩ e cujos parâmetros são as variáveis nas ⟨bindings⟩. Assim, pode-se executar repetidamente o ⟨body⟩ invocando o procedimento nomeado ⟨var⟩. Por exemplo, o procedimento iterativo de Fibonacci (1.2.2) pode ser reescrito usando named let da seguinte forma:

(define (fib n)
  (let fib-iter ((a 1) (b 0) (count n))
    (if (= count 0)
        b
        (fib-iter (+ a b) 
                  a 
                  (- count 1)))))

Modifique let->combination do Exercício 4.6 para também suportar named let.

Exercício 4.9: Muitas linguagens suportam uma variedade de construções de iteração, como do, for, while e until. Em Scheme, processos iterativos podem ser expressos em termos de chamadas de procedimentos comuns, então construções de iteração especiais não fornecem ganho essencial em poder computacional. Por outro lado, tais construções são frequentemente convenientes. Projete algumas construções de iteração, dê exemplos de seu uso e mostre como implementá-las como expressões derivadas.

Exercício 4.10: Ao usar abstração de dados, pudemos escrever um procedimento eval que é independente da sintaxe específica da linguagem a ser avaliada. Para ilustrar isso, projete e implemente uma nova sintaxe para Scheme modificando os procedimentos nesta seção, sem alterar eval ou apply.

4.1.3Estruturas de Dados do Avaliador

Além de definir a sintaxe externa das expressões, a implementação do avaliador também deve definir as estruturas de dados que o avaliador manipula internamente, como parte da execução de um programa, como a representação de procedimentos e ambientes e a representação de verdadeiro e falso.

Teste de predicados

Para condicionais, aceitamos como verdadeiro qualquer coisa que não seja o objeto explícito false.

(define (true? x)
  (not (eq? x false)))

(define (false? x)
  (eq? x false))

Representação de procedimentos

Para lidar com primitivas, assumimos que temos disponíveis os seguintes procedimentos:

• (apply-primitive-procedure ⟨proc⟩ ⟨args⟩)

  aplica a primitiva dada aos valores dos argumentos na lista ⟨args⟩ e retorna o resultado da aplicação.

• (primitive-procedure? ⟨proc⟩)

  testa se ⟨proc⟩ é uma primitiva.

Esses mecanismos para lidar com primitivas são descritos mais detalhadamente em 4.1.4.

Procedimentos compostos são construídos a partir de parâmetros, corpos de procedimentos e ambientes usando o construtor make-procedure:

(define (make-procedure parameters body env)
  (list 'procedure parameters body env))
(define (compound-procedure? p)
  (tagged-list? p 'procedure))
(define (procedure-parameters p) (cadr p))
(define (procedure-body p) (caddr p))
(define (procedure-environment p) (cadddr p))

Operações sobre Ambientes

O avaliador precisa de operações para manipular ambientes. Como explicado em 3.2, um ambiente é uma sequência de quadros, onde cada quadro é uma tabela de ligações que associam variáveis a seus valores correspondentes. Usamos as seguintes operações para manipular ambientes:

• (lookup-variable-value ⟨var⟩ ⟨env⟩)

  retorna o valor que está ligado ao símbolo ⟨var⟩ no ambiente ⟨env⟩, ou sinaliza um erro se a variável não estiver ligada.

• (extend-environment ⟨variables⟩ ⟨values⟩ ⟨base-env⟩)

  retorna um novo ambiente, consistindo de um novo quadro no qual os símbolos na lista ⟨variables⟩ são ligados aos elementos correspondentes na lista ⟨values⟩, onde o ambiente envolvente é o ambiente ⟨base-env⟩.

• (define-variable! ⟨var⟩ ⟨value⟩ ⟨env⟩)

  adiciona ao primeiro quadro no ambiente ⟨env⟩ uma nova ligação que associa a variável ⟨var⟩ ao valor ⟨value⟩.

• (set-variable-value! ⟨var⟩ ⟨value⟩ ⟨env⟩)

  altera a ligação da variável ⟨var⟩ no ambiente ⟨env⟩ para que a variável agora esteja ligada ao valor ⟨value⟩, ou sinaliza um erro se a variável não estiver ligada.

Para implementar essas operações, representamos um ambiente como uma lista de quadros. O ambiente envolvente de um ambiente é o cdr da lista. O ambiente vazio é simplesmente a lista vazia.

(define (enclosing-environment env) (cdr env))
(define (first-frame env) (car env))
(define the-empty-environment '())

Cada quadro de um ambiente é representado como um par de listas: uma lista das variáveis ligadas naquele quadro e uma lista dos valores associados.²¹⁸

(define (make-frame variables values)
  (cons variables values))
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
(define (add-binding-to-frame! var val frame)
  (set-car! frame (cons var (car frame)))
  (set-cdr! frame (cons val (cdr frame))))

Para estender um ambiente por um novo quadro que associa variáveis a valores, fazemos um quadro consistindo da lista de variáveis e da lista de valores, e o adicionamos ao ambiente. Sinalizamos um erro se o número de variáveis não corresponder ao número de valores.

(define (extend-environment vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" 
                 vars 
                 vals)
          (error "Too few arguments supplied" 
                 vars 
                 vals))))

Para procurar uma variável em um ambiente, escaneamos a lista de variáveis no primeiro quadro. Se encontrarmos a variável desejada, retornamos o elemento correspondente na lista de valores. Se não encontrarmos a variável no quadro atual, procuramos no ambiente envolvente, e assim por diante. Se alcançarmos o ambiente vazio, sinalizamos um erro de “variável não ligada”.

(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop 
              (enclosing-environment env)))
            ((eq? var (car vars))
             (car vals))
            (else (scan (cdr vars) 
                        (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

Para definir uma variável para um novo valor em um ambiente especificado, procuramos pela variável, assim como em lookup-variable-value, e alteramos o valor correspondente quando a encontramos.

(define (set-variable-value! var val env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop 
              (enclosing-environment env)))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) 
                        (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable: SET!" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

Para definir uma variável, procuramos no primeiro quadro por uma ligação para a variável e alteramos a ligação se ela existir (assim como em set-variable-value!). Se tal ligação não existir, adicionamos uma ao primeiro quadro.

(define (define-variable! var val env)
  (let ((frame (first-frame env)))
    (define (scan vars vals)
      (cond ((null? vars)
             (add-binding-to-frame! 
              var val frame))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) 
                        (cdr vals)))))
    (scan (frame-variables frame)
          (frame-values frame))))

O método descrito aqui é apenas uma das muitas maneiras plausíveis de representar ambientes. Como usamos abstração de dados para isolar o restante do avaliador da escolha detalhada de representação, poderíamos mudar a representação do ambiente se quiséssemos. (Veja Exercício 4.11.) Em um sistema Lisp de qualidade de produção, a velocidade das operações de ambiente do avaliador—especialmente a de busca de variáveis—tem um grande impacto no desempenho do sistema. A representação descrita aqui, embora conceitualmente simples, não é eficiente e não seria normalmente usada em um sistema de produção.²¹⁹

Exercício 4.11: Em vez de representar um quadro como um par de listas, podemos representar um quadro como uma lista de ligações, onde cada ligação é um par nome-valor. Reescreva as operações de ambiente para usar essa representação alternativa.

Exercício 4.12: Os procedimentos define-variable!, set-variable-value! e lookup-variable-value podem ser expressos em termos de procedimentos mais abstratos para percorrer a estrutura do ambiente. Defina abstrações que capturem os padrões comuns e redefina os três procedimentos em termos dessas abstrações.

Exercício 4.13: Scheme nos permite criar novas ligações para variáveis por meio de define, mas não fornece uma maneira de se livrar das ligações. Implemente para o avaliador uma forma especial make-unbound! que remove a ligação de um determinado símbolo do ambiente no qual a expressão make-unbound! é avaliada. Este problema não está completamente especificado. Por exemplo, devemos remover apenas a ligação no primeiro quadro do ambiente? Complete a especificação e justifique quaisquer escolhas que fizer.

4.1.4Executando o Avaliador como um Programa

Dado o avaliador, temos em mãos uma descrição (expressa em Lisp) do processo pelo qual as expressões Lisp são avaliadas. Uma vantagem de expressar o avaliador como um programa é que podemos executar o programa. Isso nos dá, rodando dentro do Lisp, um modelo funcional de como o próprio Lisp avalia expressões. Isso pode servir como uma estrutura para experimentar com regras de avaliação, como faremos mais adiante neste capítulo.

Nosso programa avaliador reduz expressões, em última análise, à aplicação de procedimentos primitivos. Portanto, tudo o que precisamos para executar o avaliador é criar um mecanismo que chame o sistema Lisp subjacente para modelar a aplicação de procedimentos primitivos.

Deve haver uma ligação para cada nome de procedimento primitivo, de modo que quando eval avalia o operador de uma aplicação de uma primitiva, ele encontrará um objeto para passar para apply. Assim, configuramos um ambiente global que associa objetos únicos aos nomes dos procedimentos primitivos que podem aparecer nas expressões que serão avaliadas. O ambiente global também inclui ligações para os símbolos true e false, para que possam ser usados como variáveis em expressões a serem avaliadas.

(define (setup-environment)
  (let ((initial-env
         (extend-environment 
          (primitive-procedure-names)
          (primitive-procedure-objects)
          the-empty-environment)))
    (define-variable! 'true true initial-env)
    (define-variable! 'false false initial-env)
    initial-env))

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

Não importa como representamos os objetos de procedimento primitivo, desde que apply possa identificá-los e aplicá-los usando os procedimentos primitive-procedure? e apply-primitive-procedure. Escolhemos representar um procedimento primitivo como uma lista começando com o símbolo primitive e contendo um procedimento no Lisp subjacente que implementa essa primitiva.

(define (primitive-procedure? proc)
  (tagged-list? proc 'primitive))

(define (primitive-implementation proc) 
  (cadr proc))

Setup-environment obterá os nomes e procedimentos de implementação das primitivas de uma lista:²²⁰

(define primitive-procedures
  (list (list 'car car)
        (list 'cdr cdr)
        (list 'cons cons)
        (list 'null? null?)
        ⟨more primitives⟩ ))

(define (primitive-procedure-names)
  (map car primitive-procedures))

(define (primitive-procedure-objects)
  (map (lambda (proc) 
         (list 'primitive (cadr proc)))
       primitive-procedures))

Para aplicar um procedimento primitivo, simplesmente aplicamos o procedimento de implementação aos argumentos, usando o sistema Lisp subjacente:²²¹

(define (apply-primitive-procedure proc args)
  (apply-in-underlying-scheme
   (primitive-implementation proc) args))

Para conveniência em executar o avaliador metacircular, fornecemos um loop de driver que modela o loop de leitura-avaliação-impressão do sistema Lisp subjacente. Ele imprime um prompt, lê uma expressão de entrada, avalia essa expressão no ambiente global e imprime o resultado. Precedemos cada resultado impresso por um prompt de saída para distinguir o valor da expressão de outras saídas que podem ser impressas.²²²

(define input-prompt  ";;; M-Eval input:")
(define output-prompt ";;; M-Eval value:")

(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output 
           (eval input 
                 the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))

(define (prompt-for-input string)
  (newline) (newline) 
  (display string) (newline))

(define (announce-output string)
  (newline) (display string) (newline))

Usamos um procedimento de impressão especial, user-print, para evitar imprimir a parte do ambiente de um procedimento composto, que pode ser uma lista muito longa (ou pode até conter ciclos).

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

Agora, tudo o que precisamos fazer para executar o avaliador é inicializar o ambiente global e iniciar o loop de driver. Aqui está uma interação de exemplo:

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

(driver-loop)

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

;;; M-Eval value:
ok

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

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

Exercício 4.14: Eva Lu Ator e Louis Reasoner estão cada um experimentando com o avaliador metacircular. Eva digita a definição de map e executa alguns programas de teste que a usam. Eles funcionam bem. Louis, por outro lado, instalou a versão do sistema de map como uma primitiva para o avaliador metacircular. Quando ele tenta, as coisas dão terrivelmente errado. Explique por que o map de Louis falha, embora o de Eva funcione.

4.1.5Dados como Programas

Ao pensar em um programa Lisp que avalia expressões Lisp, uma analogia pode ser útil. Uma visão operacional do significado de um programa é que um programa é uma descrição de uma máquina abstrata (talvez infinitamente grande). Por exemplo, considere o programa familiar para calcular fatoriais:

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

Podemos considerar este programa como a descrição de uma máquina contendo partes que decrementam, multiplicam e testam igualdade, junto com um interruptor de duas posições e outra máquina fatorial. (A máquina fatorial é infinita porque contém outra máquina fatorial dentro dela.) Figura 4.2 é um diagrama de fluxo para a máquina fatorial, mostrando como as partes são conectadas.

De maneira semelhante, podemos considerar o avaliador como uma máquina muito especial que recebe como entrada uma descrição de uma máquina. Dada essa entrada, o avaliador se configura para emular a máquina descrita. Por exemplo, se alimentarmos nosso avaliador com a definição de factorial, como mostrado em Figura 4.3, o avaliador será capaz de calcular fatoriais.

Dessa perspectiva, nosso avaliador é visto como uma máquina universal. Ele imita outras máquinas quando estas são descritas como programas Lisp.²²³ Isso é impressionante. Tente imaginar um avaliador análogo para circuitos elétricos. Isso seria um circuito que recebe como entrada um sinal codificando os planos para algum outro circuito, como um filtro. Dada essa entrada, o avaliador de circuitos se comportaria como um filtro com a mesma descrição. Tal circuito elétrico universal é quase inimaginavelmente complexo. É notável que o programa avaliador seja um programa bastante simples.²²⁴

Outro aspecto impressionante do avaliador é que ele age como uma ponte entre os objetos de dados que são manipulados por nossa linguagem de programação e a própria linguagem de programação. Imagine que o programa avaliador (implementado em Lisp) está rodando, e que um usuário está digitando expressões para o avaliador e observando os resultados. Da perspectiva do usuário, uma expressão de entrada como (* x x) é uma expressão na linguagem de programação, que o avaliador deve executar. Da perspectiva do avaliador, no entanto, a expressão é simplesmente uma lista (neste caso, uma lista de três símbolos: *, x e x) que deve ser manipulada de acordo com um conjunto bem definido de regras.

Que os programas do usuário sejam os dados do avaliador não precisa ser uma fonte de confusão. Na verdade, às vezes é conveniente ignorar essa distinção e dar ao usuário a capacidade de avaliar explicitamente um objeto de dados como uma expressão Lisp, disponibilizando eval para uso em programas. Muitos dialetos Lisp fornecem um procedimento primitivo eval que recebe como argumentos uma expressão e um ambiente e avalia a expressão em relação ao ambiente.²²⁵ Assim,

(eval '(* 5 5) user-initial-environment)

e

(eval (cons '* (list 5 5)) 
      user-initial-environment)

ambos retornarão 25.²²⁶

(define apply-in-underlying-scheme apply)