4.2Variações em um Esquema — Avaliação Preguiçosa

Agora que temos um avaliador expresso como um programa Lisp, podemos experimentar com escolhas alternativas no design da linguagem simplesmente modificando o avaliador. De fato, novas linguagens são frequentemente inventadas primeiro escrevendo um avaliador que incorpora a nova linguagem dentro de uma linguagem de alto nível existente. Por exemplo, se quisermos discutir algum aspecto de uma modificação proposta ao Lisp com outro membro da comunidade Lisp, podemos fornecer um avaliador que incorpora a mudança. O destinatário pode então experimentar o novo avaliador e enviar comentários como modificações adicionais. Não apenas a base de implementação de alto nível facilita o teste e a depuração do avaliador; além disso, a incorporação permite que o designer aproveite características da linguagem subjacente, assim como nosso avaliador Lisp incorporado usa primitivas e estrutura de controle da linguagem Lisp subjacente. Somente mais tarde (se for o caso) o designer precisará se preocupar em construir uma implementação completa em uma linguagem de baixo nível ou em hardware. Nesta seção e na próxima, exploraremos algumas variações no Scheme que fornecem poder expressivo adicional significativo.

4.2.1Ordem Normal e Ordem Aplicativa

Em 1.1, onde começamos nossa discussão sobre modelos de avaliação, nós observamos que o Scheme é uma linguagem de ordem aplicativa, ou seja, todos os argumentos para procedimentos do Scheme são avaliados quando o procedimento é aplicado. Em contraste, linguagens de ordem normal atrasam a avaliação dos argumentos do procedimento até que os valores reais dos argumentos sejam necessários. Atrasar a avaliação dos argumentos do procedimento até o último momento possível (por exemplo, até que sejam exigidos por uma operação primitiva) é chamado de avaliação preguiçosa.²³⁶ Considere o procedimento

(define (try a b)
  (if (= a 0) 1 b))

Avaliar (try 0 (/ 1 0)) gera um erro no Scheme. Com avaliação preguiçosa, não haveria erro. Avaliar a expressão retornaria 1, porque o argumento (/ 1 0) nunca seria avaliado.

Um exemplo que explora a avaliação preguiçosa é a definição de um procedimento unless

(define (unless condition 
                usual-value 
                exceptional-value)
  (if condition 
      exceptional-value 
      usual-value))

que pode ser usado em expressões como

(unless (= b 0)
        (/ a b)
        (begin 
          (display "exception: returning 0")
          0))

Isso não funcionará em uma linguagem de ordem aplicativa porque tanto o valor usual quanto o valor excepcional serão avaliados antes que unless seja chamado (compare Exercício 1.6). Uma vantagem da avaliação preguiçosa é que alguns procedimentos, como unless, podem realizar computações úteis mesmo que a avaliação de alguns de seus argumentos produza erros ou não termine.

Se o corpo de um procedimento é executado antes que um argumento tenha sido avaliado, dizemos que o procedimento é não estrito em relação a esse argumento. Se o argumento é avaliado antes que o corpo do procedimento seja executado, dizemos que o procedimento é estrito em relação a esse argumento.²³⁷ Em uma linguagem puramente de ordem aplicativa, todos os procedimentos são estritos em cada argumento. Em uma linguagem puramente de ordem normal, todos os procedimentos compostos são não estritos em cada argumento, e procedimentos primitivos podem ser estritos ou não estritos. Há também linguagens (veja Exercício 4.31) que dão aos programadores controle detalhado sobre a estrita dos procedimentos que eles definem.

Um exemplo marcante de um procedimento que pode ser útilmente tornado não estrito é cons (ou, em geral, quase qualquer construtor para estruturas de dados). Pode-se realizar computações úteis, combinando elementos para formar estruturas de dados e operando nas estruturas de dados resultantes, mesmo que os valores dos elementos não sejam conhecidos. Faz todo o sentido, por exemplo, calcular o comprimento de uma lista sem conhecer os valores dos elementos individuais na lista. Nós exploraremos essa ideia em 4.2.3 para implementar os fluxos de Capítulo 3 como listas formadas por pares cons não estritos.

Exercício 4.25: Suponha que (no Scheme de ordem aplicativa comum) definimos unless como mostrado acima e então definimos factorial em termos de unless como

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

O que acontece se tentarmos avaliar (factorial 5)? Nossas definições funcionariam em uma linguagem de ordem normal?

Exercício 4.26: Ben Bitdiddle e Alyssa P. Hacker discordam sobre a importância da avaliação preguiçosa para implementar coisas como unless. Ben aponta que é possível implementar unless em ordem aplicativa como uma forma especial. Alyssa contra-argumenta que, se alguém fizesse isso, unless seria meramente sintaxe, não um procedimento que poderia ser usado em conjunto com procedimentos de ordem superior. Preencha os detalhes de ambos os lados do argumento. Mostre como implementar unless como uma expressão derivada (como cond ou let), e dê um exemplo de uma situação onde seria útil ter unless disponível como um procedimento, em vez de como uma forma especial.

4.2.2Um Interpretador com Avaliação Preguiçosa

Nesta seção, implementaremos uma linguagem de ordem normal que é a mesma que o Scheme, exceto que os procedimentos compostos são não estritos em cada argumento. Procedimentos primitivos ainda serão estritos. Não é difícil modificar o avaliador de 4.1.1 para que a linguagem que ele interpreta se comporte dessa maneira. Quase todas as mudanças necessárias giram em torno da aplicação de procedimentos.

A ideia básica é que, ao aplicar um procedimento, o interpretador deve determinar quais argumentos devem ser avaliados e quais devem ser atrasados. Os argumentos atrasados não são avaliados; em vez disso, são transformados em objetos chamados thunks.²³⁸ O thunk deve conter as informações necessárias para produzir o valor do argumento quando ele for necessário, como se tivesse sido avaliado no momento da aplicação. Assim, o thunk deve conter a expressão do argumento e o ambiente em que a aplicação do procedimento está sendo avaliada.

O processo de avaliar a expressão em um thunk é chamado de forçamento.²³⁹ Em geral, um thunk será forçado apenas quando seu valor for necessário: quando ele for passado para um procedimento primitivo que usará o valor do thunk; quando ele for o valor de um predicado de uma condicional; e quando ele for o valor de um operador que está prestes a ser aplicado como um procedimento. Uma escolha de design que temos disponível é se devemos ou não memorizar thunks, como fizemos com objetos atrasados em 3.5.1. Com memorização, a primeira vez que um thunk é forçado, ele armazena o valor que é calculado. Forçamentos subsequentes simplesmente retornam o valor armazenado sem repetir a computação. Faremos nosso interpretador memorizar, porque isso é mais eficiente para muitas aplicações. No entanto, há considerações complicadas aqui.²⁴⁰

Modificando o avaliador

A principal diferença entre o avaliador preguiçoso e o de 4.1 está no tratamento de aplicações de procedimentos em eval e apply.

A cláusula application? de eval se torna

((application? exp)
 (apply (actual-value (operator exp) env)
        (operands exp)
        env))

Isso é quase o mesmo que a cláusula application? de eval em 4.1.1. Para avaliação preguiçosa, no entanto, chamamos apply com as expressões dos operandos, em vez dos argumentos produzidos por sua avaliação. Como precisaremos do ambiente para construir thunks se os argumentos forem atrasados, devemos passá-lo também. Ainda avaliamos o operador, porque apply precisa do procedimento real a ser aplicado para despachar em seu tipo (primitivo versus composto) e aplicá-lo.

Sempre que precisamos do valor real de uma expressão, usamos

(define (actual-value exp env)
  (force-it (eval exp env)))

em vez de apenas eval, para que, se o valor da expressão for um thunk, ele seja forçado.

Nossa nova versão de apply também é quase a mesma que a versão em 4.1.1. A diferença é que eval passou expressões de operandos não avaliadas: Para procedimentos primitivos (que são estritos), avaliamos todos os argumentos antes de aplicar o primitivo; para procedimentos compostos (que são não estritos), atrasamos todos os argumentos antes de aplicar o procedimento.

(define (apply procedure arguments env)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure
          procedure
          (list-of-arg-values 
           arguments 
           env)))  ; changed
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (extend-environment
           (procedure-parameters procedure)
           (list-of-delayed-args 
            arguments 
            env)   ; changed
           (procedure-environment procedure))))
        (else (error "Unknown procedure 
                      type: APPLY" 
                     procedure))))

Os procedimentos que processam os argumentos são como list-of-values de 4.1.1, exceto que list-of-delayed-args atrasa os argumentos em vez de avaliá-los, e list-of-arg-values usa actual-value em vez de eval:

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

(define (list-of-delayed-args exps env)
  (if (no-operands? exps)
      '()
      (cons (delay-it 
             (first-operand exps) 
             env)
            (list-of-delayed-args 
             (rest-operands exps)
             env))))

O outro lugar onde devemos mudar o avaliador é no tratamento de if, onde devemos usar actual-value em vez de eval para obter o valor da expressão do predicado antes de testar se é verdadeiro ou falso:

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

Finalmente, devemos mudar o procedimento driver-loop (4.1.4) para usar actual-value em vez de eval, para que, se um valor atrasado for propagado de volta ao loop de leitura-avaliação-impressão, ele será forçado antes de ser impresso. Também mudamos os prompts para indicar que este é o avaliador preguiçoso:

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

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

Com essas mudanças feitas, podemos iniciar o avaliador e testá-lo. A avaliação bem-sucedida da expressão try discutida em 4.2.1 indica que o interpretador está realizando avaliação preguiçosa:

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

(driver-loop)

;;; L-Eval input:
(define (try a b) (if (= a 0) 1 b))

;;; L-Eval value:
ok

;;; L-Eval input:
(try 0 (/ 1 0))

;;; L-Eval value:
1

Representando thunks

Nosso avaliador deve organizar a criação de thunks quando procedimentos são aplicados a argumentos e forçar esses thunks posteriormente. Um thunk deve empacotar uma expressão junto com o ambiente, para que o argumento possa ser produzido mais tarde. Para forçar o thunk, simplesmente extraímos a expressão e o ambiente do thunk e avaliamos a expressão no ambiente. Usamos actual-value em vez de eval para que, caso o valor da expressão seja ele mesmo um thunk, nós o forcemos, e assim por diante, até chegarmos a algo que não seja um thunk:

(define (force-it obj)
  (if (thunk? obj)
      (actual-value (thunk-exp obj) 
                    (thunk-env obj))
      obj))

Uma maneira fácil de empacotar uma expressão com um ambiente é fazer uma lista contendo a expressão e o ambiente. Assim, criamos um thunk da seguinte forma:

(define (delay-it exp env)
  (list 'thunk exp env))
(define (thunk? obj) (tagged-list? obj 'thunk))
(define (thunk-exp thunk) (cadr thunk))
(define (thunk-env thunk) (caddr thunk))

Na verdade, o que queremos para nosso interpretador não é exatamente isso, mas sim thunks que foram memorizados. Quando um thunk é forçado, nós o transformamos em um thunk avaliado, substituindo a expressão armazenada por seu valor e mudando a tag thunk para que ele possa ser reconhecido como já avaliado.²⁴¹

(define (evaluated-thunk? obj)
  (tagged-list? obj 'evaluated-thunk))

(define (thunk-value evaluated-thunk) 
  (cadr evaluated-thunk))

(define (force-it obj)
  (cond ((thunk? obj)
         (let ((result
                (actual-value 
                 (thunk-exp obj)
                 (thunk-env obj))))
           (set-car! obj 'evaluated-thunk)
           ;; replace exp with its value:
           (set-car! (cdr obj) result) 
           ;; forget unneeded env:
           (set-cdr! (cdr obj) '()) 
           result))
        ((evaluated-thunk? obj)
         (thunk-value obj))
        (else obj)))

Observe que o mesmo procedimento delay-it funciona tanto com quanto sem memorização.

Exercício 4.27: Suponha que digitamos as seguintes definições no avaliador preguiçoso:

(define count 0)
(define (id x) (set! count (+ count 1)) x)

Forneça os valores ausentes na seguinte sequência de interações e explique suas respostas.²⁴²

(define w (id (id 10)))

;;; L-Eval input:
count

;;; L-Eval value:
⟨response⟩

;;; L-Eval input:
w

;;; L-Eval value:
⟨response⟩

;;; L-Eval input:
count

;;; L-Eval value:
⟨response⟩

Exercício 4.28: Eval usa actual-value em vez de eval para avaliar o operador antes de passá-lo para apply, a fim de forçar o valor do operador. Dê um exemplo que demonstre a necessidade desse forçamento.

Exercício 4.29: Exiba um programa que você esperaria que rodasse muito mais lentamente sem memorização do que com memorização. Além disso, considere a seguinte interação, onde o procedimento id é definido como em Exercício 4.27 e count começa em 0:

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

;;; L-Eval input:
(square (id 10))

;;; L-Eval value:
⟨response⟩

;;; L-Eval input:
count

;;; L-Eval value:
⟨response⟩

Forneça as respostas tanto quando o avaliador memoriza quanto quando não memoriza.

Exercício 4.30: Cy D. Fect, um programador C reformado, está preocupado que alguns efeitos colaterais possam nunca ocorrer, porque o avaliador preguiçoso não força as expressões em uma sequência. Como o valor de uma expressão em uma sequência, exceto a última, não é usado (a expressão está lá apenas para seu efeito, como atribuir a uma variável ou imprimir), não pode haver uso subsequente desse valor (por exemplo, como argumento para um procedimento primitivo) que o forçará. Cy, portanto, pensa que, ao avaliar sequências, devemos forçar todas as expressões na sequência, exceto a final. Ele propõe modificar eval-sequence de 4.1.1 para usar actual-value em vez de eval:

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

1. Ben Bitdiddle acha que Cy está errado. Ele mostra a Cy o procedimento for-each descrito em Exercício 2.23, que dá um exemplo importante de uma sequência com efeitos colaterais:

   (define (for-each proc items)
     (if (null? items)
         'done
         (begin (proc (car items))
                (for-each proc 
                          (cdr items)))))

   Ele afirma que o avaliador no texto (com o eval-sequence original) lida com isso corretamente:

   ;;; L-Eval input:
   (for-each
    (lambda (x) (newline) (display x))
    (list 57 321 88))
   57
   321
   88
   
   ;;; L-Eval value:
   done

   Explique por que Ben está certo sobre o comportamento de for-each.

2. Cy concorda que Ben está certo sobre o exemplo for-each, mas diz que esse não é o tipo de programa que ele estava pensando quando propôs sua mudança para eval-sequence. Ele define os seguintes dois procedimentos no avaliador preguiçoso:

   (define (p1 x)
     (set! x (cons x '(2))) x)
   
   (define (p2 x)
     (define (p e) e x)
     (p (set! x (cons x '(2)))))

   Quais são os valores de (p1 1) e (p2 1) com o eval-sequence original? Quais seriam os valores com a mudança proposta por Cy para eval-sequence?

3. Cy também aponta que mudar eval-sequence como ele propõe não afeta o comportamento do exemplo na parte a. Explique por que isso é verdade.
4. Como você acha que as sequências devem ser tratadas no avaliador preguiçoso? Você gosta da abordagem de Cy, da abordagem no texto ou de alguma outra abordagem?

Exercício 4.31: A abordagem tomada nesta seção é um tanto desagradável, porque faz uma mudança incompatível com o Scheme. Seria mais agradável implementar a avaliação preguiçosa como uma extensão compatível, ou seja, de modo que programas comuns do Scheme funcionem como antes. Podemos fazer isso estendendo a sintaxe de declarações de procedimentos para permitir que o usuário controle se os argumentos devem ser atrasados. Enquanto estamos nisso, também podemos dar ao usuário a escolha entre atrasar com ou sem memorização. Por exemplo, a definição

(define (f a (b lazy) c (d lazy-memo))
  …)

definiria f como um procedimento de quatro argumentos, onde o primeiro e o terceiro argumentos são avaliados quando o procedimento é chamado, o segundo argumento é atrasado, e o quarto argumento é atrasado e memorizado. Assim, definições comuns de procedimentos produzirão o mesmo comportamento que o Scheme comum, enquanto adicionar a declaração lazy-memo a cada parâmetro de cada procedimento composto produzirá o comportamento do avaliador preguiçoso definido nesta seção. Projete e implemente as mudanças necessárias para produzir tal extensão ao Scheme. Você terá que implementar novos procedimentos de sintaxe para lidar com a nova sintaxe para define. Você também deve arranjar para que eval ou apply determinem quando os argumentos devem ser atrasados, e forçar ou atrasar argumentos conforme apropriado, e você deve arranjar para que o forçamento memorize ou não, conforme apropriado.

4.2.3Fluxos como Listas Preguiçosas

Em 3.5.1, mostramos como implementar fluxos como listas atrasadas. Introduzimos formas especiais delay e cons-stream, que permitiram construir uma “promessa” para calcular o cdr de um fluxo, sem realmente cumprir essa promessa até mais tarde. Poderíamos usar essa técnica geral de introduzir formas especiais sempre que precisamos de mais controle sobre o processo de avaliação, mas isso é incômodo. Por um lado, uma forma especial não é um objeto de primeira classe como um procedimento, então não podemos usá-la junto com procedimentos de ordem superior.²⁴³ Além disso, fomos forçados a criar fluxos como um novo tipo de objeto de dados semelhante, mas não idêntico a listas, e isso nos obrigou a reimplementar muitas operações comuns de listas (map, append, e assim por diante) para uso com fluxos.

Com avaliação preguiçosa, fluxos e listas podem ser idênticos, então não há necessidade de formas especiais ou de operações separadas de listas e fluxos. Tudo o que precisamos fazer é arranjar as coisas para que cons seja não estrito. Uma maneira de conseguir isso é estender o avaliador preguiçoso para permitir primitivas não estritas, e implementar cons como uma delas. Uma maneira mais fácil é lembrar (2.1.3) que não há necessidade fundamental de implementar cons como uma primitiva. Em vez disso, podemos representar pares como procedimentos:²⁴⁴

(define (cons x y) (lambda (m) (m x y)))
(define (car z) (z (lambda (p q) p)))
(define (cdr z) (z (lambda (p q) q)))

Em termos dessas operações básicas, as definições padrão das operações de listas funcionarão com listas infinitas (fluxos) assim como com listas finitas, e as operações de fluxos podem ser implementadas como operações de listas. Aqui estão alguns exemplos:

(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))

(define (map proc items)
  (if (null? items)
      '()
      (cons (proc (car items))
            (map proc (cdr items)))))

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

(define (add-lists list1 list2)
  (cond ((null? list1) list2)
        ((null? list2) list1)
        (else (cons (+ (car list1) 
                       (car list2))
                    (add-lists
                     (cdr list1) 
                     (cdr list2))))))

(define ones (cons 1 ones))

(define integers 
  (cons 1 (add-lists ones integers)))

;;; L-Eval input:
(list-ref integers 17)

;;; L-Eval value:
18

Observe que essas listas preguiçosas são ainda mais preguiçosas que os fluxos de Capítulo 3: O car da lista, assim como o cdr, é atrasado.²⁴⁵ De fato, até mesmo acessar o car ou cdr de um par preguiçoso não precisa forçar o valor de um elemento da lista. O valor será forçado apenas quando for realmente necessário—por exemplo, para uso como argumento de uma primitiva, ou para ser impresso como uma resposta.

Pares preguiçosos também ajudam com o problema que surgiu com fluxos em 3.5.4, onde descobrimos que formular modelos de fluxos de sistemas com loops pode exigir que espalhemos nossos programas com operações explícitas de delay, além das fornecidas por cons-stream. Com avaliação preguiçosa, todos os argumentos para procedimentos são atrasados uniformemente. Por exemplo, podemos implementar procedimentos para integrar listas e resolver equações diferenciais como originalmente pretendíamos em 3.5.4:

(define (integral integrand initial-value dt)
  (define int
    (cons initial-value
          (add-lists (scale-list integrand dt) 
                     int)))
  int)

(define (solve f y0 dt)
  (define y (integral dy y0 dt))
  (define dy (map f y))
  y)

;;; L-Eval input:
(list-ref (solve (lambda (x) x) 1 0.001) 1000)

;;; L-Eval value:
2.716924

Exercício 4.32: Dê alguns exemplos que ilustram a diferença entre os fluxos de Capítulo 3 e as listas preguiçosas “mais preguiçosas” descritas nesta seção. Como você pode tirar vantagem dessa preguiça extra?

Exercício 4.33: Ben Bitdiddle testa a implementação de listas preguiçosas dada acima avaliando a expressão

(car '(a b c))

Para sua surpresa, isso produz um erro. Depois de pensar um pouco, ele percebe que as “listas” obtidas ao ler expressões entre aspas são diferentes das listas manipuladas pelas novas definições de cons, car, e cdr. Modifique o tratamento de expressões entre aspas pelo avaliador para que listas entre aspas digitadas no loop de driver produzam listas preguiçosas verdadeiras.

Exercício 4.34: Modifique o loop de driver para o avaliador para que pares e listas preguiçosas sejam impressos de alguma maneira razoável. (O que você vai fazer sobre listas infinitas?) Você também pode precisar modificar a representação de pares preguiçosos para que o avaliador possa identificá-los a fim de imprimi-los.