-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-27.html
270 lines (213 loc) · 39.2 KB
/
book-Z-H-27.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:ops="http://www.idpf.org/2007/ops">
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta http-equiv="Content-Type: text/html; charset=utf-8"/>
<title>Estrutura e Interpretação de Programas de Computador</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title="default"/>
</head>
<body>
<a name="%_sec_4.2" id="%_sec_4.2"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_4.2">4.2 Variações em um Scheme – avaliação preguiçosa</a></h2><p>
<a name="%_idx_4666" id="%_idx_4666"/><a name="%_idx_4668" id="%_idx_4668"/>
<a name="%_idx_4670" id="%_idx_4670"/><a name="%_idx_4672" id="%_idx_4672"/>Agora que temos um avaliador expresso como um programa Lisp, podemos experimentar opções alternativas no projeto da linguagem simplesmente modificando o avaliador. De fato, novas linguagens são frequentemente inventadas ao escrever primeiro um avaliador que incorpora a nova linguagens em uma linguagem de alto nível existente. Por exemplo, se desejamos discutir algum aspecto de uma modificação proposta no Lisp com outro membro da comunidade Lisp, podemos fornecer um avaliador que incorpore a mudança. O destinatário pode então experimentar o novo avaliador e enviar comentários como modificações adicionais. A base de implementação de alto nível não apenas facilita o teste e a depuração do avaliador; Além disso, a incorporação permite que o projetista usar <a name="call_footnote_Temp_575" href="#footnote_Temp_575" id="call_footnote_Temp_575"><sup><small>31</small></sup></a> recursos da linguagem subjacente, assim como nosso avaliador Lisp incorporado usa primitivas e estrutura de controle do Lisp subjacente. Somente mais tarde (se houver) o projetista precisa se dar ao trabalho de criar 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.</p><p>
<a name="%_sec_4.2.1" id="%_sec_4.2.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.1">4.2.1 Ordem normal e ordem de aplicação</a></h3><p>
</p><p>
<a name="%_idx_4680" id="%_idx_4680"/><a name="%_idx_4682" id="%_idx_4682"/>Na seção <a href="book-Z-H-10.html#%_sec_1.1">1.1</a>, onde começamos nossa discussão sobre modelos de avaliação, observamos que Scheme é uma linguagem de <em>ordem aplicativa</em>, em que todos os argumentos para os procedimentos do Scheme são avaliados quando o procedimento é aplicado. Em contraste, linguagens de <em>ordem normal</em> atrasam a avaliação dos argumentos do procedimento até que os valores reais do argumento 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 <a name="%_idx_4684" id="%_idx_4684"/><em>avaliação preguiçosa</em>.<a name="call_footnote_Temp_576" href="#footnote_Temp_576" id="call_footnote_Temp_576"><sup><small>32</small></sup></a> Considere o procedimento</p><p>
</p><p/><p><tt>(define (try a b)<br/>
(if (= a 0) 1 b))<br/></tt></p><p/><p>Avaliando <tt>(try 0 (/1 0))</tt> gera um erro no Scheme. Com uma avaliação preguiçosa, não haveria erro. Avaliar a expressão retornaria 1, pois o argumento <tt>(/1 0)</tt> nunca seria avaliado.</p><p>Um exemplo que explora a avaliação preguiçosa é a definição de um procedimento <tt>unless</tt></p><p>
</p><p/><p><tt>(define (unless condition usual-value exceptional-value)<br/>
(if condition exceptional-value usual-value))<br/></tt></p><p/><p>que pode ser usado em expressões como</p><p>
</p><p/><p><tt>(unless (= b 0)<br/>
(/ a b)<br/>
(begin (display "exception: returning 0")<br/>
0))<br/></tt></p><p/><p>Isso não funcionará em uma linguagem de ordem aplicativa, pois o valor usual e o valor excepcional serão avaliados antes de <tt>unless</tt> ser chamado (compare o exercício <a href="book-Z-H-10.html#%_thm_1.6">1.6</a>) Uma vantagem da avaliação preguiçosa é que alguns procedimentos, como <tt>unless</tt>, podem fazer cálculos úteis, mesmo que a avaliação de alguns de seus argumentos produza erros ou não termine.</p><p>Se o corpo de um procedimento for inserido antes de um argumento ser avaliado, dizemos que o procedimento é <a name="%_idx_4686" id="%_idx_4686"/><em>não rigoroso</em> nesse argumento. Se o argumento for avaliado antes da inserção do corpo do procedimento, dizemos que o procedimento é <a name="%_idx_4688" id="%_idx_4688"/><em>estrito</em> nesse argumento.<a name="call_footnote_Temp_577" href="#footnote_Temp_577" id="call_footnote_Temp_577"><sup><small>33</small></sup></a> Em uma linguagem de ordem puramente aplicativa, todos os procedimentos são estritos em cada argumento. Em uma linguagem de ordem puramente normal, todos os procedimentos compostos são não-estritos em cada argumento, e os procedimentos primitivos podem ser estritos ou não-estritos. Existem também linguagens (ver exercício <a href="#%_thm_4.31">4.31</a>) que fornecem aos programadores controle detalhado sobre os procedimentos estritos que eles definem.</p><p>Um exemplo impressionante de um procedimento que pode ser utilmente não estrito é <tt>cons</tt> (ou, em geral, quase qualquer construtor para estruturas de dados). Pode-se fazer cálculos ú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 tamanho de uma lista sem conhecer os valores dos elementos individuais da lista. Exploraremos essa ideia na seção <a href="#%_sec_4.2.3">4.2.3</a> para implementar os fluxos do capítulo 3 como listas formadas de pares de <tt>cons</tt> não estritos.</p><p>
</p><p><a name="%_thm_4.25" id="%_thm_4.25"/>
<b>Exercício 4.25.</b> Suponha que (no Scheme ordinário de ordem aplicativa) definimos <tt>unless</tt> como mostrado acima e depois defina <tt>factorial</tt> em termos de <tt>unless</tt> como</p><p>
</p><p/><p><tt>(define (factorial n)<br/>
(unless (= n 1)<br/>
(* n (factorial (- n 1)))<br/>
1))<br/></tt></p><p/><p>O que acontece se tentarmos avaliar <tt>(factorial 5)</tt>? Nossas definições funcionarão em uma linguagem de ordem normal?</p><p/><p>
</p><p><a name="%_thm_4.26" id="%_thm_4.26"/>
<b>Exercício 4.26.</b> <a name="%_idx_4692" id="%_idx_4692"/><a name="%_idx_4694" id="%_idx_4694"/>Ben Bitdiddle e Alyssa P. Hacker discordam sobre a importância da avaliação preguiçosa para implementar algo como <tt>unless</tt>. Ben ressalta que é possível implementar <tt>unless</tt> em ordem aplicativa como uma forma especial. Alyssa rebate que, se alguém fizer isso, <tt>unless</tt> seria apenas sintaxe, não um procedimento que poderia ser usado em conjunto com procedimentos de ordem superior. Preencha os detalhes nos dois lados do argumento. Mostre como implementar <tt>unless</tt> como uma expressão derivada (como <tt>cond</tt> ou <tt>let</tt>) e dê um exemplo de uma situação em que pode ser útil ter <tt>unless</tt> disponível como um procedimento, e não como uma forma especial.</p><p/><p>
<a name="%_sec_4.2.2" id="%_sec_4.2.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.2">4.2.2 Um interpretador com avaliação preguiçosa</a></h3><p>Nesta seção, implementaremos uma linguagem de ordem normal que é a mesma do Scheme, exceto que os procedimentos compostos não são rigorosos em cada argumento. Os procedimentos primitivos ainda serão estritos. Não é difícil modificar o avaliador da seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> para que a linguagem que ela interpreta se comporte dessa maneira. Quase todas as alterações necessárias estão centradas na aplicação do procedimento.</p><p>A ideia básica é que, ao aplicar um procedimento, o interpretador deve determinar quais argumentos devem ser avaliados e quais devem ser adiados. Os argumentos atrasados não são avaliados; em vez disso, eles são transformados em objetos chamados <a name="%_idx_4696" id="%_idx_4696"/><em>thunk</em> s.<a name="call_footnote_Temp_580" href="#footnote_Temp_580" id="call_footnote_Temp_580"><sup><small>34</small></sup></a> A conversão deve conter as informações necessárias para produzir o valor do argumento quando necessário, como se tivesse sido avaliado no momento da aplicação. Portanto, o thunk deve conter a expressão do argumento e o ambiente em que a aplicação de procedimento é avaliado.</p><p>
<a name="%_idx_4704" id="%_idx_4704"/><a name="%_idx_4706" id="%_idx_4706"/>O processo de avaliar a expressão em uma conversão é chamado <em>forçamento</em>.<a name="call_footnote_Temp_581" href="#footnote_Temp_581" id="call_footnote_Temp_581"><sup><small>35</small></sup></a> Em geral, um thunk será forçado apenas quando seu valor for necessário: quando for passado para um procedimento primitivo que usará o valor do thunk; quando é o valor de um predicado de uma condicional; e quando é o valor de um operador que está prestes a ser aplicado como um procedimento. Uma opção de projeto que temos disponível é se deve ou não <a name="%_idx_4710" id="%_idx_4710"/><em>memoizar</em> thunks, como fizemos com objetos atrasados na seção <a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a>. Com a memoização, na primeira vez em que uma conversão é forçada, ela armazena o valor calculado. Forçamentos subsequentes simplesmente retornam o valor armazenado sem repetir o cálculo. Tornaremos nosso interpretador memoizado, pois isso é mais eficiente para muitas aplicações. Existem considerações complicadas aqui, no entanto.<a name="call_footnote_Temp_582" href="#footnote_Temp_582" id="call_footnote_Temp_582"><sup><small>36</small></sup></a></p><p>
<a name="%_sec_Temp_583" id="%_sec_Temp_583"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_583">Modificando o avaliador</a></h4><p>A principal diferença entre o avaliador preguiçoso e o da seção <a href="book-Z-H-26.html#%_sec_4.1">4.1</a> está no manuseio de aplicações de procedimento em <tt>eval</tt> e <tt>apply</tt>.</p><p>
<a name="%_idx_4720" id="%_idx_4720"/>A cláusula <tt>application?</tt> de <tt>eval</tt> torna-se</p><p>
</p><p/><p><tt>((application? exp)<br/>
(apply (actual-value (operator exp) env)<br/>
(operands exp)<br/>
env))<br/></tt></p><p/><p>Isso é quase o mesmo que a cláusula <tt>application?</tt> de <tt>eval</tt> na seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>. Para avaliação preguiçosa, no entanto, chamamos <tt>apply</tt> com as expressões do operando, em vez dos argumentos produzidos pela avaliação deles. Como precisaremos que o ambiente construa thunks para que os argumentos sejam adiados, precisamos passar isso também. Ainda avaliamos o operador, pois <tt>apply</tt> precisa que o procedimento real seja aplicado para despachar seu tipo (primitivo versus composto) e aplicá-lo.</p><p>Sempre que precisamos do valor real de uma expressão, usamos</p><p/><p><tt><a name="%_idx_4722" id="%_idx_4722"/>(define (actual-value exp env)<br/>
(force-it (eval exp env)))<br/></tt></p><p/><p>em vez de apenas <tt>eval</tt>, para que, se o valor da expressão for um thunk, ele será forçado.</p><p>Nossa nova versão do <tt>apply</tt> também é quase o mesmo que a versão na seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>. A diferença é que <tt>eval</tt> passou em expressões não avaliadas de operando: Para procedimentos primitivos (que são estritos), avaliamos todos os argumentos antes de aplicar a primitiva; para procedimentos compostos (que não são rigorosos), atrasamos todos os argumentos antes de aplicar o procedimento.</p><p>
</p><p/><p><tt><a name="%_idx_4724" id="%_idx_4724"/>(define (apply procedure arguments env)<br/>
(cond ((primitive-procedure? procedure)<br/>
(apply-primitive-procedure<br/>
procedure<br/>
(list-of-arg-values arguments env))) <em>; changed</em><br/>
((compound-procedure? procedure)<br/>
(eval-sequence<br/>
(procedure-body procedure)<br/>
(extend-environment<br/>
(procedure-parameters procedure)<br/>
(list-of-delayed-args arguments env) <em>; changed</em><br/>
(procedure-environment procedure))))<br/>
(else<br/>
(error<br/>
"Unknown procedure type -- APPLY" procedure))))<br/></tt></p><p/><p>Os procedimentos que processam os argumentos são como <tt>list-of-values</tt> da seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>, exceto que <tt>list-of-delayed-args</tt> atrasa os argumentos em vez de avaliá-los, e <tt>list-of-arg-values</tt> usa <tt>actual-value</tt> em vez de <tt>eval</tt>:</p><p>
</p><p/><p><tt><a name="%_idx_4726" id="%_idx_4726"/>(define (list-of-arg-values exps env)<br/>
(if (no-operands? exps)<br/>
'()<br/>
(cons (actual-value (first-operand exps) env)<br/>
(list-of-arg-values (rest-operands exps)<br/>
env))))<br/><a name="%_idx_4728" id="%_idx_4728"/>(define (list-of-delayed-args exps env)<br/>
(if (no-operands? exps)<br/>
'()<br/>
(cons (delay-it (first-operand exps) env)<br/>
(list-of-delayed-args (rest-operands exps)<br/>
env))))<br/></tt></p><p/><p/><p>O outro lugar em que devemos mudar o avaliador está no manuseio de <tt>if</tt>, onde devemos usar <tt>actual-value</tt> em vez de <tt>eval</tt> para obter o valor da expressão de predicado antes de testar se é verdadeiro ou falso:</p><p>
</p><p/><p><tt><a name="%_idx_4730" id="%_idx_4730"/>(define (eval-if exp env)<br/>
(if (true? (actual-value (if-predicate exp) env))<br/>
(eval (if-consequent exp) env)<br/>
(eval (if-alternative exp) env)))<br/></tt></p><p/><p/><p>
<a name="%_idx_4732" id="%_idx_4732"/>Finalmente, devemos mudar o procedimento <tt>driver-loop</tt> (seção <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>) usar <tt>actual-value</tt> em vez de <tt>eval</tt>, para que, se um valor atrasado for propagado de volta para o laço de leitura-avaliação-impressão, ele será forçado antes de ser impresso. Também alteramos as solicitações para indicar que este é o avaliador preguiçoso:</p><p>
</p><p/><p><tt><a name="%_idx_4734" id="%_idx_4734"/>(define input-prompt ";;; L-Eval input:")<br/>
(define output-prompt ";;; L-Eval value:")<br/><a name="%_idx_4736" id="%_idx_4736"/>(define (driver-loop)<br/>
(prompt-for-input input-prompt)<br/>
(let ((input (read)))<br/>
(let ((output<br/>
(actual-value input the-global-environment)))<br/>
(announce-output output-prompt)<br/>
(user-print output)))<br/>
(driver-loop))<br/></tt></p><p/><p/><p>Com essas alterações, podemos iniciar o avaliador e testá-lo. A avaliação bem-sucedida da expressão <tt>try</tt> discutida na seção <a href="#%_sec_4.2.1">4.2.1</a> indica que o interpretador realiza uma avaliação preguiçosa:</p><p>
</p><p/><p><tt>(define the-global-environment (setup-environment))<br/>
(driver-loop)<br/><i>;;; L-Eval input:</i><br/>
(define (try a b)<br/>
(if (= a 0) 1 b))<br/><i>;;; L-Eval value:</i><br/><i>ok</i><br/><i>;;; L-Eval input:</i><br/>
(try 0 (/ 1 0))<br/><i>;;; L-Eval value:</i><br/><i>1</i><br/></tt></p><p/><p/><p>
<a name="%_sec_Temp_584" id="%_sec_Temp_584"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_584">Representando thunks</a></h4><p>
<a name="%_idx_4738" id="%_idx_4738"/>Nosso avaliador deve organizar a criação de thunks quando os procedimentos são aplicados aos argumentos e forçá-los posteriormente. Um thunk deve empacotar uma expressão junto com o ambiente, para que o argumento possa ser produzido posteriormente. Para forçar o thunk, simplesmente extraímos a expressão e o ambiente do thunk e avaliamos a expressão no ambiente. Usamos <tt>actual-value</tt> em vez de <tt>eval</tt> de modo que, se o valor da expressão for um thunk, forçaremos isso, e assim por diante, até chegarmos a algo que não é thunk:</p><p>
</p><p/><p><tt><a name="%_idx_4740" id="%_idx_4740"/>(define (force-it obj)<br/>
(if (thunk? obj)<br/>
(actual-value (thunk-exp obj) (thunk-env obj))<br/>
obj))<br/></tt></p><p/><p/><p>Uma maneira fácil de compactar uma expressão com um ambiente é fazer uma lista contendo a expressão e o ambiente. Assim, criamos uma conversão da seguinte maneira:</p><p>
</p><p/><p><tt><a name="%_idx_4742" id="%_idx_4742"/>(define (delay-it exp env)<br/>
(list 'thunk exp env))<br/><br/>
(define (thunk? obj)<br/>
(tagged-list? obj 'thunk))<br/><br/>
(define (thunk-exp thunk) (cadr thunk))<br/><br/>
(define (thunk-env thunk) (caddr thunk))<br/></tt></p><p/><p/><p>Na verdade, o que queremos para o nosso interpretador não é exatamente isso, mas sim thunks que foram memoizados. Quando um thunk é forçado, vamos transformá-lo em um thunk avaliado, substituindo a expressão armazenada por seu valor e alterando o <tt>thunk</tt> para que possa ser reconhecido como já avaliado.<a name="call_footnote_Temp_585" href="#footnote_Temp_585" id="call_footnote_Temp_585"><sup><small>37</small></sup></a></p><p>
</p><p/><p><tt>(define (evaluated-thunk? obj)<br/>
(tagged-list? obj 'evaluated-thunk))<br/><br/>
(define (thunk-value evaluated-thunk) (cadr evaluated-thunk))<br/><a name="%_idx_4748" id="%_idx_4748"/>(define (force-it obj)<br/>
(cond ((thunk? obj)<br/>
(let ((result (actual-value<br/>
(thunk-exp obj)<br/>
(thunk-env obj))))<br/>
(set-car! obj 'evaluated-thunk)<br/>
(set-car! (cdr obj) result) <em>; replace <tt>exp</tt> with its value</em><br/>
(set-cdr! (cdr obj) '()) <em>; forget unneeded <tt>env</tt></em><br/>
result))<br/>
((evaluated-thunk? obj)<br/>
(thunk-value obj))<br/>
(else obj)))<br/></tt></p><p/><p>Observe que o procedimento <tt>delay-it</tt> funciona com e sem memoização.</p><p>
</p><p><a name="%_thm_4.27" id="%_thm_4.27"/>
<b>Exercício 4.27.</b> Suponha que digitemos as seguintes definições para o avaliador preguiçoso:</p><p/><p><tt>(define count 0)<br/>
(define (id x)<br/>
(set! count (+ count 1))<br/>
x)<br/></tt></p><p/><p>Dê os valores ausentes na seguinte sequência de interações e explique suas respostas.<a name="call_footnote_Temp_587" href="#footnote_Temp_587" id="call_footnote_Temp_587"><sup><small>38</small></sup></a>
</p><p/><p><tt>(define w (id (id 10)))<br/><i>;;; L-Eval input:</i><br/>
count<br/><i>;;; L-Eval value:</i><br/>
<<em>response</em>><br/><i>;;; L-Eval input:</i><br/>
w<br/><i>;;; L-Eval value:</i><br/>
<<em>response</em>><br/><i>;;; L-Eval input:</i><br/>
count<br/><i>;;; L-Eval value:</i><br/>
<<em>response</em>><br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_4.28" id="%_thm_4.28"/>
<b>Exercício 4.28.</b> <tt>Eval</tt> usa <tt>actual-value</tt> em vez de <tt>eval</tt> para avaliar o operador antes de passá-lo para <tt>apply</tt>, para forçar o valor do operador. Dê um exemplo que demonstre a necessidade desse forçamento.</p><p/><p>
</p><p><a name="%_thm_4.29" id="%_thm_4.29"/>
<b>Exercício 4.29.</b> Mostre um programa que você esperaria executar muito mais lentamente sem memoização do que com memoização. Além disso, considere a seguinte interação, em que o procedimento <tt>id</tt> é definido como no exercício <a href="#%_thm_4.27">4.27</a> e <tt>count</tt> começa em 0:</p><p/><p><tt>(define (square x)<br/>
(* x x))<br/><i>;;; L-Eval input:</i><br/>
(square (id 10))<br/><i>;;; L-Eval value:</i><br/>
<<em>response</em>><br/><i>;;; L-Eval input:</i><br/>
count<br/><i>;;; L-Eval value:</i><br/>
<<em>response</em>><br/></tt></p><p/><p>Dê as respostas quando o avaliador memoizar e quando não o fizer.</p><p/><p>
</p><p><a name="%_thm_4.30" id="%_thm_4.30"/>
<b>Exercício 4.30.</b> Cy D. Fect, um programador C reformado, teme que alguns efeitos colaterais nunca ocorram, pois 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 diferente da última não é usada (a expressão existe apenas para seu efeito, como atribuir a uma variável ou imprimir), não pode haver uso subsequente desse valor (por exemplo, como um argumento para um procedimento primitivo) que fará com que seja forçado. Cy acha que, ao avaliar sequências, devemos forçar todas as expressões na sequência, exceto a final. Ele propõe modificar <tt>eval-sequence</tt> da seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> para usar <tt>actual-value</tt> em vez de <tt>eval</tt>:</p><p>
</p><p/><p><tt>(define (eval-sequence exps env)<br/>
(cond ((last-exp? exps) (eval (first-exp exps) env))<br/>
(else (actual-value (first-exp exps) env)<br/>
(eval-sequence (rest-exps exps) env))))<br/></tt></p><p/><p/><p>
</p><p/><p>a. Ben Bitdiddle acha que Cy está errado. Ele mostra Cy o procedimento <tt>for-each</tt> descrito no exercício <a href="book-Z-H-15.html#%_thm_2.23">2.23</a>, que fornece um exemplo importante de uma sequência com efeitos colaterais:</p><p>
</p><p/><p><tt><a name="%_idx_4750" id="%_idx_4750"/>(define (for-each proc items)<br/>
(if (null? items)<br/>
'done<br/>
(begin (proc (car items))<br/>
(for-each proc (cdr items)))))<br/></tt></p><p/><p>Ele afirma que o avaliador no texto (com o <tt>eval-sequence</tt> original) lida com isso corretamente:</p><p>
</p><p/><p><tt><i>;;; L-Eval input:</i><br/>
(for-each (lambda (x) (newline) (display x))<br/>
(list 57 321 88))<br/><i>57</i><br/><i>321</i><br/><i>88</i><br/><i>;;; L-Eval value:</i><br/><i>done</i><br/></tt></p><p/><p>Explique por que Ben está certo sobre o comportamento de <tt>for-each</tt>.</p><p>
</p><p/><p>b. Cy concorda que Ben está certo sobre o <tt>for-each</tt> exemplo, mas diz que esse não é o tipo de programa em que ele pensava quando propôs sua mudança para <tt>eval-sequence</tt>. Ele define os dois procedimentos a seguir no avaliador preguiçoso:</p><p>
</p><p/><p><tt>(define (p1 x)<br/>
(set! x (cons x '(2)))<br/>
x)<br/><br/>
(define (p2 x)<br/>
(define (p e)<br/>
e<br/>
x)<br/>
(p (set! x (cons x '(2)))))<br/></tt></p><p/><p>Quais são os valores de <tt>(p1 1)</tt> e <tt>(p2 1)</tt> com o original <tt>eval-sequence</tt>? Quais seriam os valores com a mudança proposta por Cy para <tt>eval-sequence</tt>?</p><p>
</p><p/><p>c. Cy também aponta que mudar <tt>eval-sequence</tt> como ele propõe, não afeta o comportamento do exemplo na parte a. Explique por que isso é verdade.</p><p>
</p><p/><p>d. 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?</p><p/><p>
</p><p><a name="%_thm_4.31" id="%_thm_4.31"/>
<b>Exercício 4.31.</b> <a name="%_idx_4752" id="%_idx_4752"/>A abordagem adotada nesta seção é um pouco desagradável, pois faz uma alteração incompatível no Scheme. Pode ser mais agradável implementar uma avaliação preguiçosa como uma <em>extensão com compatibilidade futura</em>, ou seja, para que os programas comuns do Scheme funcionem como antes. Podemos fazer isso estendendo a sintaxe das declarações de procedimento para permitir que o usuário controle se os argumentos devem ou não ser adiados. Enquanto estamos nisso, também podemos dar ao usuário a opção entre adiar com e sem memoização. Por exemplo, a definição</p><p/><p><tt>(define (f a (b lazy) c (d lazy-memo))<br/>
<tt>...</tt>)<br/></tt></p><p/><p>definiria <tt>f</tt> para ser 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 memoizado. Assim, as definições de procedimentos comuns produzirão o mesmo comportamento que o Scheme comum, adicionando a declaração <tt>lazy-memo</tt> para cada parâmetro de cada procedimento composto produzirá o comportamento do avaliador preguiçoso definido nesta seção. Projete e implemente as alterações necessárias para produzir uma extensão do Scheme. Você precisará implementar novos procedimentos de sintaxe para lidar com a nova sintaxe para <tt>define</tt>. Você também deve providenciar <tt>eval</tt> ou <tt>apply</tt> para determinar quando os argumentos devem ser adiados e forçar ou atrasar os argumentos de acordo, e você deve providenciar o forçar a memoizar ou não, conforme apropriado.</p><p/><p>
<a name="%_sec_4.2.3" id="%_sec_4.2.3"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_4.2.3">4.2.3 Fluxos como listas preguiçosas</a></h3><p>
<a name="%_idx_4754" id="%_idx_4754"/><a name="%_idx_4756" id="%_idx_4756"/><a name="%_idx_4758" id="%_idx_4758"/><a name="%_idx_4760" id="%_idx_4760"/><a name="%_idx_4762" id="%_idx_4762"/>
<a name="%_idx_4764" id="%_idx_4764"/><a name="%_idx_4766" id="%_idx_4766"/><a name="%_idx_4768" id="%_idx_4768"/><a name="%_idx_4770" id="%_idx_4770"/>Na seção <a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a>, mostramos como implementar fluxos como listas atrasadas. Introduzimos formas especiais <tt>delay</tt> e <tt>cons-stream</tt>, o que nos permitiu construir uma “promessa” para calcular o <tt>cdr</tt> de um fluxo, sem realmente cumprir essa promessa até mais tarde. Poderíamos usar essa técnica geral de introdução de formas especiais sempre que precisarmos de mais controle sobre o processo de avaliação, mas isso é estranho. Por um lado, uma forma especial não é um objeto de primeira classe como um procedimento, portanto, não podemos usá-la junto com procedimentos de ordem superior.<a name="call_footnote_Temp_592" href="#footnote_Temp_592" id="call_footnote_Temp_592"><sup><small>39</small></sup></a> Além disso, fomos forçados a criar fluxos como um novo tipo de objeto de dados semelhante, mas não idêntico às listas, e isso exigiu a reimplementação de muitas operações de lista comuns (<tt>map</tt>, <tt>append</tt> e assim por diante) para uso com fluxos.</p><p>Com a avaliação preguiçosa, os fluxos e as listas podem ser idênticos, portanto, não há necessidade de formas especiais ou operações separadas de lista e fluxo. Tudo o que precisamos fazer é organizar para que <tt>cons</tt> não é estrito. Uma maneira de conseguir isso é estender o avaliador preguiçoso para permitir primitivas não estritas e implementar <tt>cons</tt> como um desses. Uma maneira mais fácil é lembrar (seção <a href="book-Z-H-14.html#%_sec_2.1.3">2.1.3</a>) que não há necessidade fundamental de implementar <tt>cons</tt> como uma primitiva. Em vez disso, podemos representar <a name="%_idx_4772" id="%_idx_4772"/>pares como procedimentos:<a name="call_footnote_Temp_593" href="#footnote_Temp_593" id="call_footnote_Temp_593"><sup><small>40</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_4774" id="%_idx_4774"/>(define (cons x y)<br/>
(lambda (m) (m x y)))<br/><a name="%_idx_4776" id="%_idx_4776"/>(define (car z)<br/>
(z (lambda (p q) p)))<br/><a name="%_idx_4778" id="%_idx_4778"/>(define (cdr z)<br/>
(z (lambda (p q) q)))<br/></tt></p><p/><p/><p>Em termos dessas operações básicas, as definições padrão das operações de lista funcionarão com infinitas listas (fluxos), bem como com as finitas, e as operações de fluxo podem ser implementadas como operações de lista. aqui estão alguns exemplos:</p><p>
</p><p/><p><tt><a name="%_idx_4780" id="%_idx_4780"/>(define (list-ref items n)<br/>
(if (= n 0)<br/>
(car items)<br/>
(list-ref (cdr items) (- n 1))))<br/><a name="%_idx_4782" id="%_idx_4782"/>(define (map proc items)<br/>
(if (null? items)<br/>
'()<br/>
(cons (proc (car items))<br/>
(map proc (cdr items)))))<br/><a name="%_idx_4784" id="%_idx_4784"/>(define (scale-list items factor)<br/>
(map (lambda (x) (* x factor))<br/>
items))<br/><a name="%_idx_4786" id="%_idx_4786"/>(define (add-lists list1 list2)<br/>
(cond ((null? list1) list2)<br/>
((null? list2) list1)<br/>
(else (cons (+ (car list1) (car list2))<br/>
(add-lists (cdr list1) (cdr list2))))))<br/><a name="%_idx_4788" id="%_idx_4788"/>(define ones (cons 1 ones))<br/><a name="%_idx_4790" id="%_idx_4790"/>(define integers (cons 1 (add-lists ones integers)))<br/><i>;;; L-Eval input:</i><br/>
(list-ref integers 17)<br/><i>;;; L-Eval value:</i><br/><i>18</i><br/></tt></p><p/><p/><p>Observe que essas listas preguiçosas são ainda mais preguiçosas do que os fluxos do capítulo 3: <tt>car</tt> da lista, bem como o <tt>cdr</tt>, está atrasado.<a name="call_footnote_Temp_594" href="#footnote_Temp_594" id="call_footnote_Temp_594"><sup><small>41</small></sup></a> De fato, mesmo acessando o <tt>car</tt> ou <tt>cdr</tt> de um par preguiçoso não precisa forçar o valor de um elemento da lista. O valor será forçado somente quando for realmente necessário – por exemplo, para uso como argumento de uma primitiva ou para ser impresso como resposta.</p><p>Pares preguiçosos também ajudam com o problema que surgiu com fluxos na seção <a href="book-Z-H-24.html#%_sec_3.5.4">3.5.4</a>, onde descobrimos que a formulação de modelos de sistemas de sistemas com laços pode exigir que os programas sejam espalhados com operações <a name="%_idx_4798" id="%_idx_4798"/><a name="%_idx_4800" id="%_idx_4800"/>de <tt>delay</tt> explícitas, além das fornecidas por <tt>cons-stream</tt>. Com uma 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 pretendemos originalmente na seção <a href="book-Z-H-24.html#%_sec_3.5.4">3.5.4</a>:</p><p>
</p><p/><p><tt><a name="%_idx_4802" id="%_idx_4802"/>(define (integral integrand initial-value dt)<br/>
(define int<br/>
(cons initial-value<br/>
(add-lists (scale-list integrand dt)<br/>
int)))<br/>
int)<br/><a name="%_idx_4804" id="%_idx_4804"/>(define (solve f y0 dt)<br/>
(define y (integral dy y0 dt))<br/>
(define dy (map f y))<br/>
y)<br/><i>;;; L-Eval input:</i><br/>
(list-ref (solve (lambda (x) x) 1 0.001) 1000)<br/><i>;;; L-Eval value:</i><br/><i>2.716924</i></tt></p><p/><p/><p>
</p><p><a name="%_thm_4.32" id="%_thm_4.32"/>
<b>Exercício 4.32.</b> Dê alguns exemplos que ilustram a diferença entre os fluxos do capítulo 3 e as listas preguiçosas “mais preguiçosas” descritas nesta seção. Como você pode tirar proveito dessa preguiça extra?</p><p/><p>
</p><p><a name="%_thm_4.33" id="%_thm_4.33"/>
<b>Exercício 4.33.</b> Ben Bitdiddle testa a implementação preguiçosa da lista dada acima avaliando a expressão</p><p/><p><tt>(car '(a b c))<br/></tt></p><p/><p>Para sua surpresa, isso produz um erro. Depois de pensar um pouco, ele percebe que as “listas” obtidas pela leitura de expressões citadas são diferentes das listas manipuladas pelas novas definições de <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt>. Modifique o tratamento do avaliador das expressões citadas, para que as listas citadas no laço do controlador produzam verdadeiras listas preguiçosas.</p><p/><p>
</p><p><a name="%_thm_4.34" id="%_thm_4.34"/>
<b>Exercício 4.34.</b> Modifique o laço do controlador do avaliador para que pares e listas preguiçosos sejam impressos de alguma maneira razoável. (O que você fará sobre listas infinitas?) Você também pode precisar modificar a representação de pares preguiçosos para que o avaliador possa identificá-los para imprimi-los.</p><p/><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_575" href="#call_footnote_Temp_575" id="footnote_Temp_575"><sup><small>31</small></sup></a> Snarf: “Para pegar, especialmente um documento ou <a name="%_idx_4674" id="%_idx_4674"/><a name="%_idx_4676" id="%_idx_4676"/><a name="%_idx_4678" id="%_idx_4678"/>arquivo grande com a finalidade de usá-lo com ou sem a permissão do proprietário”. Snarf abaixo: “Snarf, às vezes com a conotação de absorver, processar ou entender”. (Essas definições foram tiradas de Steele et al. 1983. Veja também Raymond 1993).</p><p><a name="footnote_Temp_576" href="#call_footnote_Temp_576" id="footnote_Temp_576"><sup><small>32</small></sup></a> A diferença entre a terminologia “preguiçosa” e a terminologia de “ordem normal” é um tanto imprecisa. Geralmente, “preguiçoso” se refere aos mecanismos de determinados avaliadores, enquanto “ordem normal” se refere à semântica de linguagens, independentemente de qualquer estratégia de avaliação específica. Mas essa não é uma distinção difícil e curta, e as duas terminologias são frequentemente usadas de forma intercambiável.</p><p><a name="footnote_Temp_577" href="#call_footnote_Temp_577" id="footnote_Temp_577"><sup><small>33</small></sup></a> A terminologia “estrita” versus “não estrita” significa essencialmente o mesmo que “ordem aplicativa” versus “ordem normal”, exceto que se refere a procedimentos e argumentos individuais, e não à linguagem como um todo. Em uma conferência sobre linguagens de programação, você pode ouvir alguém dizer: “A linguagem de ordem normal <a name="%_idx_4690" id="%_idx_4690"/>Hassle possui certas primitivas estritas. Outros procedimentos levam seus argumentos por avaliação preguiçosa”.</p><p><a name="footnote_Temp_580" href="#call_footnote_Temp_580" id="footnote_Temp_580"><sup><small>34</small></sup></a> A palavra <em>thunk</em> foi inventado por um grupo <a name="%_idx_4698" id="%_idx_4698"/><a name="%_idx_4700" id="%_idx_4700"/><a name="%_idx_4702" id="%_idx_4702"/>informal de trabalho que discutia a implementação da chamada por nome em Algol 60. Eles observaram que a maior parte da análise (“pensando sobre”) a expressão poderia ser feita em tempo de compilação; assim, em tempo de execução, a expressão já teria sido “debulhada” (Ingerman et al. 1960).</p><p><a name="footnote_Temp_581" href="#call_footnote_Temp_581" id="footnote_Temp_581"><sup><small>35</small></sup></a> Isso é análogo ao uso de <tt>force</tt><a name="%_idx_4708" id="%_idx_4708"/>nos objetos atrasados que foram introduzidos no capítulo 3 para representar fluxos. A diferença crítica entre o que fazemos aqui e o que fizemos no capítulo 3 é que construimos atrasos e forçando o avaliador, tornando-o uniforme e automático em todo a linguagem.</p><p><a name="footnote_Temp_582" href="#call_footnote_Temp_582" id="footnote_Temp_582"><sup><small>36</small></sup></a> Às vezes, a avaliação preguiçosa combinada com a memoização <a name="%_idx_4712" id="%_idx_4712"/>referido como <em>chamada por necessidade</em> passagem de argumento, em contraste com <em>chamada por nome</em> passagem de argumento. <a name="%_idx_4714" id="%_idx_4714"/><a name="%_idx_4716" id="%_idx_4716"/>(A chamada por nome, introduzida no Algol 60, é semelhante à avaliação preguiçosa não memoizada). Como projetistas de linguagem, podemos construir nosso avaliador para memoizar, não memoizar ou deixar essa opção para programadores (exercício <a href="#%_thm_4.31">4.31</a>) Como você pode esperar do capítulo 3, essas escolhas levantam questões que se tornam sutis e confusas na presença de atribuições. (Veja exercícios <a href="#%_thm_4.27">4.27</a> e <a href="#%_thm_4.29">4.29</a>). <a name="%_idx_4718" id="%_idx_4718"/>Um excelente artigo de Clinger (1982) tenta esclarecer as múltiplas dimensões da confusão que surgem aqui.</p><p><a name="footnote_Temp_585" href="#call_footnote_Temp_585" id="footnote_Temp_585"><sup><small>37</small></sup></a> Observe que também apagamos o <tt>env</tt> do thunk depois que o valor da expressão for calculado. Isso não faz diferença nos valores retornados pelo interpretador. No entanto, ajuda a economizar espaço, pois a remoção da referência do thunk para o <tt>env</tt> uma vez que não é mais necessário, permite que essa estrutura seja <a name="%_idx_4744" id="%_idx_4744"/><a name="%_idx_4746" id="%_idx_4746"/><em>coletado de lixo</em> e seu espaço reciclado, como discutiremos na seção <a href="book-Z-H-33.html#%_sec_5.3">5.3</a>.</p><p>Da mesma forma, poderíamos ter permitido ambientes desnecessários nos objetos atrasados memoizados da seção <a href="book-Z-H-24.html#%_sec_3.5.1">3.5.1</a> coletar lixo por ter <tt>memo-proc</tt> faça algo como <tt>(set! proc '())</tt> para descartar o procedimento <tt>proc</tt> (que inclui o ambiente em que o <tt>delay</tt> foi avaliado) após armazenar seu valor.</p><p><a name="footnote_Temp_587" href="#call_footnote_Temp_587" id="footnote_Temp_587"><sup><small>38</small></sup></a> Este exercício demonstra que a interação entre avaliação preguiçosa e efeitos colaterais pode ser muito confusa. É exatamente o que você pode esperar da discussão no capítulo 3.</p><p><a name="footnote_Temp_592" href="#call_footnote_Temp_592" id="footnote_Temp_592"><sup><small>39</small></sup></a> Este é precisamente o problema com o procedimento<tt>unless</tt>, como no exercício <a href="#%_thm_4.26">4.26</a>.</p><p><a name="footnote_Temp_593" href="#call_footnote_Temp_593" id="footnote_Temp_593"><sup><small>40</small></sup></a> Esta é a representação processual descrita no exercício <a href="book-Z-H-14.html#%_thm_2.4">2.4</a>. Essencialmente, qualquer representação processual (por exemplo, uma implementação de passagem de mensagens) também faria. Observe que podemos instalar essas definições no avaliador preguiçoso simplesmente digitando-as no laço do controlador. Se tivéssemos incluído originalmente <tt>cons</tt>, <tt>car</tt> e <tt>cdr</tt> como primitivas no ambiente global, elas serão redefinidas. (Veja também exercícios <a href="#%_thm_4.33">4.33</a> e <a href="#%_thm_4.34">4.34</a>).</p><p><a name="footnote_Temp_594" href="#call_footnote_Temp_594" id="footnote_Temp_594"><sup><small>41</small></sup></a> Isso nos permite criar versões atrasadas de tipos mais gerais de <a name="%_idx_4792" id="%_idx_4792"/>listar estruturas, não apenas sequências. Hughes 1990 discute algumas <a name="%_idx_4794" id="%_idx_4794"/><a name="%_idx_4796" id="%_idx_4796"/>aplicações de “árvores preguiçosas”.</p></div>
</body>
</html>