3.2O Modelo de Ambiente de Avaliação

Quando introduzimos procedimentos compostos no Capítulo 1, usamos o modelo de substituição de avaliação (1.1.5) para definir o que significa aplicar um procedimento a argumentos:

• Para aplicar um procedimento composto a argumentos, avalie o corpo do procedimento com cada parâmetro formal substituído pelo argumento correspondente.

Uma vez que admitimos a atribuição em nossa linguagem de programação, tal definição não é mais adequada. Em particular, 3.1.3 argumentou que, na presença de atribuição, uma variável não pode mais ser considerada meramente como um nome para um valor. Em vez disso, uma variável deve de alguma forma designar um "local" no qual os valores podem ser armazenados. Em nosso novo modelo de avaliação, esses locais serão mantidos em estruturas chamadas ambientes.

Um ambiente é uma sequência de frames. Cada frame é uma tabela (possivelmente vazia) de vinculações, que associam nomes de variáveis a seus valores correspondentes. (Um único frame pode conter no máximo uma vinculação para qualquer variável.) Cada frame também tem um ponteiro para seu ambiente envolvente, a menos que, para fins de discussão, o frame seja considerado como global. O valor de uma variável com respeito a um ambiente é o valor dado pela vinculação da variável no primeiro frame no ambiente que contém uma vinculação para essa variável. Se nenhum frame na sequência especificar uma vinculação para a variável, então a variável é dita não vinculada no ambiente.

Figura 3.1 mostra uma estrutura de ambiente simples consistindo de três frames, rotulados I, II e III. No diagrama, A, B, C e D são ponteiros para ambientes. C e D apontam para o mesmo ambiente. As variáveis z e x estão vinculadas no frame II, enquanto y e x estão vinculadas no frame I. O valor de x no ambiente D é 3. O valor de x em relação ao ambiente B também é 3. Isso é determinado da seguinte forma: Nós examinamos o primeiro frame na sequência (frame III) e não encontramos uma vinculação para x, então prosseguimos para o ambiente envolvente D e encontramos a vinculação no frame I. Por outro lado, o valor de x no ambiente A é 7, porque o primeiro frame na sequência (frame II) contém uma vinculação de x a 7. Em relação ao ambiente A, a vinculação de x a 7 no frame II é dita ocultar a vinculação de x a 3 no frame I.

O ambiente é crucial para o processo de avaliação, porque ele determina o contexto no qual uma expressão deve ser avaliada. De fato, pode-se dizer que expressões em uma linguagem de programação não têm, em si mesmas, qualquer significado. Em vez disso, uma expressão adquire significado apenas em relação a algum ambiente no qual ela é avaliada. Mesmo a interpretação de uma expressão tão simples quanto (+ 1 1) depende do entendimento de que se está operando em um contexto no qual + é o símbolo para adição. Assim, em nosso modelo de avaliação, sempre falaremos de avaliar uma expressão em relação a algum ambiente. Para descrever interações com o interpretador, nós suporemos que existe um ambiente global, consistindo de um único frame (sem ambiente envolvente) que inclui valores para os símbolos associados aos procedimentos primitivos. Por exemplo, a ideia de que + é o símbolo para adição é capturada ao dizer que o símbolo + está vinculado no ambiente global ao procedimento primitivo de adição.

3.2.1As Regras para Avaliação

A especificação geral de como o interpretador avalia uma combinação permanece a mesma que quando a introduzimos pela primeira vez em 1.1.3:

• Para avaliar uma combinação:

1. Avalie as subexpressões da combinação.¹⁴⁰
2. Aplique o valor da subexpressão do operador aos valores das subexpressões dos operandos.

O modelo de ambiente de avaliação substitui o modelo de substituição na especificação do que significa aplicar um procedimento composto a argumentos.

No modelo de ambiente de avaliação, um procedimento é sempre um par consistindo de algum código e um ponteiro para um ambiente. Os procedimentos são criados de uma única maneira: avaliando uma expressão λ. Isso produz um procedimento cujo código é obtido a partir do texto da expressão λ e cujo ambiente é o ambiente no qual a expressão λ foi avaliada para produzir o procedimento. Por exemplo, considere a definição de procedimento

(define (square x)
  (* x x))

avaliada no ambiente global. A sintaxe de definição de procedimento é apenas açúcar sintático para uma expressão λ subjacente implícita. Teria sido equivalente usar

(define square
  (lambda (x) (* x x)))

que avalia (lambda (x) (* x x)) e vincula square ao valor resultante, tudo no ambiente global.

Figura 3.2 mostra o resultado da avaliação dessa expressão define. O objeto de procedimento é um par cujo código especifica que o procedimento tem um parâmetro formal, nomeadamente x, e um corpo de procedimento (* x x). A parte do ambiente do procedimento é um ponteiro para o ambiente global, já que esse é o ambiente no qual a expressão λ foi avaliada para produzir o procedimento. Uma nova vinculação, que associa o objeto de procedimento ao símbolo square, foi adicionada ao frame global. Em geral, define cria definições adicionando vinculações a frames.

Agora que vimos como os procedimentos são criados, podemos descrever como os procedimentos são aplicados. O modelo de ambiente especifica: Para aplicar um procedimento a argumentos, crie um novo ambiente contendo um frame que vincula os parâmetros aos valores dos argumentos. O ambiente envolvente deste frame é o ambiente especificado pelo procedimento. Agora, dentro deste novo ambiente, avalie o corpo do procedimento.

Para mostrar como essa regra é seguida, Figura 3.3 ilustra a estrutura de ambiente criada pela avaliação da expressão (square 5) no ambiente global, onde square é o procedimento gerado em Figura 3.2. A aplicação do procedimento resulta na criação de um novo ambiente, rotulado E1 na figura, que começa com um frame no qual x, o parâmetro formal do procedimento, está vinculado ao argumento 5. O ponteiro que leva para cima a partir deste frame mostra que o ambiente envolvente do frame é o ambiente global. O ambiente global é escolhido aqui, porque este é o ambiente que é indicado como parte do objeto de procedimento square. Dentro de E1, avaliamos o corpo do procedimento, (* x x). Como o valor de x em E1 é 5, o resultado é (* 5 5), ou 25.

O modelo de ambiente de aplicação de procedimento pode ser resumido por duas regras:

• Um objeto de procedimento é aplicado a um conjunto de argumentos construindo um frame, vinculando os parâmetros formais do procedimento aos argumentos da chamada, e então avaliando o corpo do procedimento no contexto do novo ambiente construído. O novo frame tem como seu ambiente envolvente o ambiente parte do objeto de procedimento sendo aplicado.
• Um procedimento é criado avaliando uma expressão λ em relação a um dado ambiente. O objeto de procedimento resultante é um par consistindo do texto da expressão λ e um ponteiro para o ambiente no qual o procedimento foi criado.

Também especificamos que definir um símbolo usando define cria uma vinculação no frame do ambiente atual e atribui ao símbolo o valor indicado.¹⁴¹ Finalmente, nós especificamos o comportamento de set!, a operação que nos forçou a introduzir o modelo de ambiente em primeiro lugar. Avaliar a expressão (set! ⟨variável⟩ ⟨valor⟩) em algum ambiente localiza a vinculação da variável no ambiente e altera essa vinculação para indicar o novo valor. Ou seja, encontra-se o primeiro frame no ambiente que contém uma vinculação para a variável e modifica esse frame. Se a variável não estiver vinculada no ambiente, então set! sinaliza um erro.

Essas regras de avaliação, embora consideravelmente mais complexas que o modelo de substituição, ainda são razoavelmente diretas. Além disso, o modelo de avaliação, embora abstrato, fornece uma descrição correta de como o interpretador avalia expressões. Em Capítulo 4 veremos como esse modelo pode servir como um plano para implementar um interpretador funcional. As seções seguintes elaboram os detalhes do modelo analisando alguns programas ilustrativos.

3.2.2Aplicando Procedimentos Simples

Quando introduzimos o modelo de substituição em 1.1.5, mostramos como a combinação (f 5) é avaliada para 136, dadas as seguintes definições de procedimentos:

(define (square x)
  (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))
(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

Podemos analisar o mesmo exemplo usando o modelo de ambiente. Figura 3.4 mostra os três objetos de procedimento criados ao avaliar as definições de f, square e sum-of-squares no ambiente global. Cada objeto de procedimento consiste em algum código, junto com um ponteiro para o ambiente global.

Na Figura 3.5, vemos a estrutura de ambiente criada ao avaliar a expressão (f 5). A chamada para f cria um novo ambiente E1 começando com um quadro no qual a, o parâmetro formal de f, é vinculado ao argumento 5. Em E1, avaliamos o corpo de f:

(sum-of-squares (+ a 1) (* a 2))

Para avaliar essa combinação, primeiro avaliamos as subexpressões. A primeira subexpressão, sum-of-squares, tem um valor que é um objeto de procedimento. (Observe como esse valor é encontrado: primeiro procuramos no primeiro quadro de E1, que não contém uma vinculação para sum-of-squares. Em seguida, prosseguimos para o ambiente envolvente, ou seja, o ambiente global, e encontramos a vinculação mostrada na Figura 3.4.) As outras duas subexpressões são avaliadas aplicando as operações primitivas + e * para avaliar as duas combinações (+ a 1) e (* a 2) para obter 6 e 10, respectivamente.

Agora aplicamos o objeto de procedimento sum-of-squares aos argumentos 6 e 10. Isso resulta em um novo ambiente E2 no qual os parâmetros formais x e y são vinculados aos argumentos. Dentro de E2, avaliamos a combinação (+ (square x) (square y)). Isso nos leva a avaliar (square x), onde square é encontrado no quadro global e x é 6. Mais uma vez, configuramos um novo ambiente, E3, no qual x é vinculado a 6, e dentro dele avaliamos o corpo de square, que é (* x x). Também como parte da aplicação de sum-of-squares, devemos avaliar a subexpressão (square y), onde y é 10. Essa segunda chamada para square cria outro ambiente, E4, no qual x, o parâmetro formal de square, é vinculado a 10. E dentro de E4 devemos avaliar (* x x).

O ponto importante a observar é que cada chamada para square cria um novo ambiente contendo uma vinculação para x. Podemos ver aqui como os diferentes quadros servem para manter separadas as diferentes variáveis locais, todas nomeadas x. Observe que cada quadro criado por square aponta para o ambiente global, já que este é o ambiente indicado pelo objeto de procedimento square.

Após as subexpressões serem avaliadas, os resultados são retornados. Os valores gerados pelas duas chamadas para square são somados por sum-of-squares, e esse resultado é retornado por f. Como nosso foco aqui é nas estruturas de ambiente, não nos deteremos em como esses valores retornados são passados de chamada para chamada; no entanto, isso também é um aspecto importante do processo de avaliação, e retornaremos a ele em detalhes no Capítulo 5.

Exercício 3.9: Em 1.2.1, usamos o modelo de substituição para analisar dois procedimentos para calcular fatoriais, uma versão recursiva

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

e uma versão iterativa

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product 
                   counter 
                   max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

Mostre as estruturas de ambiente criadas ao avaliar (factorial 6) usando cada versão do procedimento factorial.¹⁴²

3.2.3Quadros como Repositório de Estado Local

Podemos recorrer ao modelo de ambiente para ver como procedimentos e atribuição podem ser usados para representar objetos com estado local. Como exemplo, considere o “processador de saque” de 3.1.1 criado ao chamar o procedimento

(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance amount))
               balance)
        "Insufficient funds")))

Vamos descrever a avaliação de

(define W1 (make-withdraw 100))

seguido por

(W1 50)
50

Figura 3.6 mostra o resultado de definir o procedimento make-withdraw no ambiente global. Isso produz um objeto de procedimento que contém um ponteiro para o ambiente global. Até agora, isso não é diferente dos exemplos que já vimos, exceto que o corpo do procedimento é ele mesmo uma expressão λ.

A parte interessante da computação acontece quando aplicamos o procedimento make-withdraw a um argumento:

(define W1 (make-withdraw 100))

Começamos, como de costume, configurando um ambiente E1 no qual o parâmetro formal balance é vinculado ao argumento 100. Dentro desse ambiente, avaliamos o corpo de make-withdraw, ou seja, a expressão λ. Isso constrói um novo objeto de procedimento, cujo código é o especificado pelo lambda e cujo ambiente é E1, o ambiente no qual o lambda foi avaliado para produzir o procedimento. O objeto de procedimento resultante é o valor retornado pela chamada para make-withdraw. Isso é vinculado a W1 no ambiente global, já que o próprio define está sendo avaliado no ambiente global. Figura 3.7 mostra a estrutura de ambiente resultante.

Agora podemos analisar o que acontece quando W1 é aplicado a um argumento:

(W1 50)
50

Começamos construindo um quadro no qual amount, o parâmetro formal de W1, é vinculado ao argumento 50. O ponto crucial a observar é que esse quadro tem como seu ambiente envolvente não o ambiente global, mas sim o ambiente E1, porque este é o ambiente especificado pelo objeto de procedimento W1. Dentro desse novo ambiente, avaliamos o corpo do procedimento:

(if (>= balance amount)
    (begin (set! balance 
                 (- balance amount))
           balance)
    "Insufficient funds")

A estrutura de ambiente resultante é mostrada na Figura 3.8. A expressão sendo avaliada referencia tanto amount quanto balance. Amount será encontrado no primeiro quadro do ambiente, enquanto balance será encontrado seguindo o ponteiro do ambiente envolvente para E1.

Quando o set! é executado, a vinculação de balance em E1 é alterada. Ao concluir a chamada para W1, balance é 50, e o quadro que contém balance ainda é apontado pelo objeto de procedimento W1. O quadro que vincula amount (no qual executamos o código que alterou balance) não é mais relevante, já que a chamada de procedimento que o construiu terminou, e não há ponteiros para esse quadro de outras partes do ambiente. Na próxima vez que W1 for chamado, isso construirá um novo quadro que vincula amount e cujo ambiente envolvente é E1. Vemos que E1 serve como o “local” que mantém a variável de estado local para o objeto de procedimento W1. Figura 3.9 mostra a situação após a chamada para W1.

Observe o que acontece quando criamos um segundo objeto “withdraw” fazendo outra chamada para make-withdraw:

(define W2 (make-withdraw 100))

Isso produz a estrutura de ambiente da Figura 3.10, que mostra que W2 é um objeto de procedimento, ou seja, um par com algum código e um ambiente. O ambiente E2 para W2 foi criado pela chamada para make-withdraw. Ele contém um quadro com sua própria vinculação local para balance. Por outro lado, W1 e W2 têm o mesmo código: o código especificado pela expressão λ no corpo de make-withdraw.¹⁴³ Vemos aqui por que W1 e W2 se comportam como objetos independentes. Chamadas para W1 referenciam a variável de estado balance armazenada em E1, enquanto chamadas para W2 referenciam o balance armazenado em E2. Assim, alterações no estado local de um objeto não afetam o outro objeto.

Exercício 3.10: No procedimento make-withdraw, a variável local balance é criada como um parâmetro de make-withdraw. Também poderíamos criar a variável de estado local explicitamente, usando let, da seguinte forma:

(define (make-withdraw initial-amount)
  (let ((balance initial-amount))
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance 
                       (- balance amount))
                 balance)
          "Insufficient funds"))))

Lembre-se de 1.3.2 que let é simplesmente açúcar sintático para uma chamada de procedimento:

(let ((⟨var⟩ ⟨exp⟩)) ⟨body⟩)

é interpretado como uma sintaxe alternativa para

((lambda (⟨var⟩) ⟨body⟩) ⟨exp⟩)

Use o modelo de ambiente para analisar essa versão alternativa de make-withdraw, desenhando figuras como as acima para ilustrar as interações

(define W1 (make-withdraw 100))
(W1 50)
(define W2 (make-withdraw 100))

Mostre que as duas versões de make-withdraw criam objetos com o mesmo comportamento. Como as estruturas de ambiente diferem para as duas versões?

3.2.4Definições Internas

A seção 1.1.8 introduziu a ideia de que procedimentos podem ter definições internas, levando assim a uma estrutura de bloco como no seguinte procedimento para calcular raízes quadradas:

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

Agora podemos usar o modelo de ambiente para ver por que essas definições internas se comportam como desejado. Figura 3.11 mostra o ponto na avaliação da expressão (sqrt 2) onde o procedimento interno good-enough? foi chamado pela primeira vez com guess igual a 1.

Observe a estrutura do ambiente. Sqrt é um símbolo no ambiente global que está vinculado a um objeto de procedimento cujo ambiente associado é o ambiente global. Quando sqrt foi chamado, um novo ambiente E1 foi formado, subordinado ao ambiente global, no qual o parâmetro x é vinculado a 2. O corpo de sqrt foi então avaliado em E1. Como a primeira expressão no corpo de sqrt é

(define (good-enough? guess)
    (<  (abs (- (square guess) x)) 0.001))

avaliar essa expressão definiu o procedimento good-enough? no ambiente E1. Para ser mais preciso, o símbolo good-enough? foi adicionado ao primeiro quadro de E1, vinculado a um objeto de procedimento cujo ambiente associado é E1. Da mesma forma, improve e sqrt-iter foram definidos como procedimentos em E1. Por concisão, a Figura 3.11 mostra apenas o objeto de procedimento para good-enough?.

Após os procedimentos locais serem definidos, a expressão (sqrt-iter 1.0) foi avaliada, ainda no ambiente E1. Assim, o objeto de procedimento vinculado a sqrt-iter em E1 foi chamado com 1 como argumento. Isso criou um ambiente E2 no qual guess, o parâmetro de sqrt-iter, é vinculado a 1. Sqrt-iter por sua vez chamou good-enough? com o valor de guess (de E2) como o argumento para good-enough?. Isso configurou outro ambiente, E3, no qual guess (o parâmetro de good-enough?) é vinculado a 1. Embora sqrt-iter e good-enough? tenham um parâmetro chamado guess, essas são duas variáveis locais distintas localizadas em quadros diferentes. Além disso, E2 e E3 têm E1 como seu ambiente envolvente, porque os procedimentos sqrt-iter e good-enough? têm E1 como parte de seu ambiente. Uma consequência disso é que o símbolo x que aparece no corpo de good-enough? referenciará a vinculação de x que aparece em E1, ou seja, o valor de x com o qual o procedimento sqrt original foi chamado.

O modelo de ambiente, portanto, explica as duas propriedades principais que tornam as definições de procedimentos locais uma técnica útil para modularizar programas:

• Os nomes dos procedimentos locais não interferem com nomes externos ao procedimento envolvente, porque os nomes dos procedimentos locais serão vinculados no quadro que o procedimento cria quando é executado, em vez de serem vinculados no ambiente global.
• Os procedimentos locais podem acessar os argumentos do procedimento envolvente, simplesmente usando nomes de parâmetros como variáveis livres. Isso ocorre porque o corpo do procedimento local é avaliado em um ambiente que é subordinado ao ambiente de avaliação do procedimento envolvente.

Exercício 3.11: Em 3.2.3, vimos como o modelo de ambiente descreveu o comportamento de procedimentos com estado local. Agora vimos como as definições internas funcionam. Um procedimento típico de passagem de mensagens contém ambos esses aspectos. Considere o procedimento de conta bancária de 3.1.1:

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance 
                        amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (dispatch m)
    (cond ((eq? m 'withdraw) withdraw)
          ((eq? m 'deposit) deposit)
          (else (error "Unknown request: 
                        MAKE-ACCOUNT" 
                       m))))
  dispatch)

Mostre a estrutura de ambiente gerada pela sequência de interações

(define acc (make-account 50))

((acc 'deposit) 40)
90

((acc 'withdraw) 60)
30

Onde o estado local para acc é mantido? Suponha que definamos outra conta

(define acc2 (make-account 100))

Como os estados locais para as duas contas são mantidos distintos? Quais partes da estrutura de ambiente são compartilhadas entre acc e acc2?