-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbook-Z-H-34.html
More file actions
442 lines (346 loc) · 57 KB
/
book-Z-H-34.html
File metadata and controls
442 lines (346 loc) · 57 KB
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
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
<?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_5.4" id="%_sec_5.4"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_5.4">5.4 O avaliador de controle explícito</a></h2><p>
<a name="%_idx_5996" id="%_idx_5996"/>Na seção <a href="book-Z-H-31.html#%_sec_5.1">5.1</a> vimos como transformar programas simples do Scheme em descrições de máquinas de registradores. Agora, realizaremos essa transformação em um programa mais complexo, o avaliador metacircular das seções <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>-<a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>, que mostra como o comportamento de um interpretador do Scheme pode ser descrito em termos dos procedimentos <tt>eval</tt> e <tt>apply</tt>. O <em>avaliador de controle explícito</em> que desenvolvemos nesta seção mostra como os mecanismos subjacentes de chamada de procedimento e de passagem de argumento usados no processo de avaliação podem ser descritos em termos de operações em registradores e pilhas. Além disso, o avaliador de controle explícito pode servir como uma implementação de um interpretador do Scheme, escrito em uma linguagem muito semelhante à linguagem de máquina nativa dos computadores convencionais. O avaliador pode ser executado pelo simulador de máquina de registradores da seção <a href="book-Z-H-32.html#%_sec_5.2">5.2.</a>. Como alternativa, ele pode ser usado como ponto de partida para criar uma implementação em linguagem de máquina de um avaliador do Scheme, ou mesmo uma <a name="%_idx_5998" id="%_idx_5998"/><a name="%_idx_6000" id="%_idx_6000"/><a name="%_idx_6002" id="%_idx_6002"/>máquina de uso especial para avaliar expressões do Scheme. A figura <a href="#%_fig_5.16">5.16</a> mostra essa implementação de hardware: um chip de silício que atua como avaliador do Scheme. Os projetistas de chips começaram com as especificações do caminho de dados e do controlador de uma máquina de registradores semelhante ao avaliador descrito nesta seção e usaram programas de automação de projeto para construir o layout do circuito integrado.<a name="call_footnote_Temp_765" href="#footnote_Temp_765" id="call_footnote_Temp_765"><sup><small>19</small></sup></a></p><p>
</p><p>
<a name="%_sec_Temp_766" id="%_sec_Temp_766"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_766">Registradores e operações</a></h4><p>
<a name="%_idx_6006" id="%_idx_6006"/>
<a name="%_idx_6008" id="%_idx_6008"/>Ao projetar o avaliador de controle explícito, precisamos especificar as operações a serem usadas em nossa máquina de registradores. Descrevemos o avaliador metacircular em termos de sintaxe abstrata, usando procedimentos como <tt>quoted?</tt> e <tt>make-procedure</tt>. Ao implementar a máquina de registradores, poderíamos expandir esses procedimentos em sequências de operações elementares de memória de estrutura de lista e implementar essas operações em nossa máquina de registradores. No entanto, isso tornaria o nosso avaliador muito longo, obscurecendo a estrutura básica com detalhes. Para esclarecer a apresentação, incluiremos como operações primitivas da máquina de registradores os procedimentos de sintaxe fornecidos na seção <a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a> e os procedimentos para representar ambientes e outros dados de tempo de execução fornecidos nas seções <a href="book-Z-H-26.html#%_sec_4.1.3">4.1.3</a> e <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>. Para especificar completamente um avaliador que poderia ser programado em uma linguagem de máquina de baixo nível ou implementado em hardware, substituiríamos essas operações por operações mais elementares, usando a implementação de estrutura de lista descrita na seção <a href="book-Z-H-33.html#%_sec_5.3">5.3</a>.</p><p>
<a name="%_fig_5.16" id="%_fig_5.16"/></p><p/><div align="left"><table width="100%"><tr><td><img src="images/chip.jpg" border="0" height="310"/></td></tr><caption align="bottom"><div align="left"><b>Figura 5.16:</b> Uma implementação em circuito integrado de silício de um avaliador para o Scheme.</div></caption><tr><td>
<a name="%_idx_6010" id="%_idx_6010"/><a name="%_idx_6012" id="%_idx_6012"/><a name="%_idx_6014" id="%_idx_6014"/>
</td></tr></table></div><p/><p>
<a name="%_idx_6016" id="%_idx_6016"/><a name="%_idx_6018" id="%_idx_6018"/><a name="%_idx_6020" id="%_idx_6020"/><a name="%_idx_6022" id="%_idx_6022"/><a name="%_idx_6024" id="%_idx_6024"/><a name="%_idx_6026" id="%_idx_6026"/><a name="%_idx_6028" id="%_idx_6028"/><a name="%_idx_6030" id="%_idx_6030"/>Nossa máquina de registradores de avaliadores do Scheme inclui uma pilha e sete registradores: <tt>exp</tt>, <tt>env</tt>, <tt>val</tt>, <tt>continue</tt>, <tt>proc</tt>, <tt>argl</tt> e <tt>unev</tt>. <tt>Exp</tt> é usado para conter a expressão a ser avaliada e <tt>env</tt> contém o ambiente em que a avaliação deve ser realizada. No final de uma avaliação, <tt>val</tt> contém o valor obtido avaliando a expressão no ambiente designado. O registrador <tt>continue</tt> é usado para implementar a recursão, conforme explicado na seção <a href="book-Z-H-31.html#%_sec_5.1.4">5.1.4</a>. (O avaliador precisa se chamar recursivamente, pois avaliar uma expressão requer avaliar suas subexpressões). <tt>proc</tt>, <tt>argl</tt> e <tt>unev</tt> são usados na avaliação de combinações.</p><p>Não forneceremos um diagrama de caminho de dados para mostrar como os registradores e operações do avaliador estão conectados, nem forneceremos a lista completa de operações da máquina. Elas estão implícitas no controlador do avaliador, que serão apresentadas em detalhes.</p><p>
<a name="%_sec_5.4.1" id="%_sec_5.4.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.4.1">5.4.1 O núcleo do avaliador de controle explícito</a></h3><p>
<a name="%_idx_6032" id="%_idx_6032"/>O elemento central no avaliador é a sequência de instruções que começa em <tt>eval-dispatch</tt>. Isso corresponde ao procedimento <tt>eval</tt> do avaliador metacircular descrito na seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>. Quando o controlador inicia em <tt>eval-dispatch</tt>, avalia a expressão especificada por <tt>exp</tt> no ambiente especificado por <tt>env</tt>. Quando a avaliação estiver concluída, o controlador irá para o ponto de entrada armazenado em <tt>continue</tt>, e o registrador <tt>val</tt> manterá o valor da expressão. Tal como acontece com o <tt>eval</tt> metacircular, a estrutura de <tt>eval-dispatch</tt> é uma análise de caso sobre o tipo sintático da expressão a ser avaliada.<a name="call_footnote_Temp_767" href="#footnote_Temp_767" id="call_footnote_Temp_767"><sup><small>20</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_6034" id="%_idx_6034"/>eval-dispatch<br/>
(test (op self-evaluating?) (reg exp))<br/>
(branch (label ev-self-eval))<br/>
(test (op variable?) (reg exp))<br/>
(branch (label ev-variable))<br/>
(test (op quoted?) (reg exp))<br/>
(branch (label ev-quoted))<br/>
(test (op assignment?) (reg exp))<br/>
(branch (label ev-assignment))<br/>
(test (op definition?) (reg exp))<br/>
(branch (label ev-definition))<br/>
(test (op if?) (reg exp))<br/>
(branch (label ev-if))<br/>
(test (op lambda?) (reg exp))<br/>
(branch (label ev-lambda))<br/>
(test (op begin?) (reg exp))<br/>
(branch (label ev-begin))<br/>
(test (op application?) (reg exp))<br/>
(branch (label ev-application))<br/>
(goto (label unknown-expression-type))<br/></tt></p><p/><p/><p>
<a name="%_sec_Temp_768" id="%_sec_Temp_768"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_768">Avaliando expressões simples</a></h4><p>
<a name="%_idx_6036" id="%_idx_6036"/>Números e sequências de caracteres (que são autoavaliadas), variáveis, cotações e expressões <tt>lambda</tt> não possuem subexpressões a serem avaliadas. Para isso, o avaliador simplesmente coloca o valor correto no registador <tt>val</tt> e continua a execução no ponto de entrada especificado por <tt>continue</tt>. A avaliação de expressões simples é realizada pelo seguinte código do controlador:</p><p>
</p><p/><p><tt><a name="%_idx_6038" id="%_idx_6038"/>ev-self-eval<br/>
(assign val (reg exp))<br/>
(goto (reg continue))<br/><a name="%_idx_6040" id="%_idx_6040"/>ev-variable<br/>
(assign val (op lookup-variable-value) (reg exp) (reg env))<br/>
(goto (reg continue))<br/><a name="%_idx_6042" id="%_idx_6042"/>ev-quoted<br/>
(assign val (op text-of-quotation) (reg exp))<br/>
(goto (reg continue))<br/><a name="%_idx_6044" id="%_idx_6044"/>ev-lambda<br/>
(assign unev (op lambda-parameters) (reg exp))<br/>
(assign exp (op lambda-body) (reg exp))<br/>
(assign val (op make-procedure)<br/>
(reg unev) (reg exp) (reg env))<br/>
(goto (reg continue))<br/></tt></p><p/><p>Observe como <tt>ev-lambda</tt> usa os registradores <tt>unev</tt> e <tt>exp</tt> para manter os parâmetros e o corpo da expressão lambda para que eles possam ser passados para a operação <tt>make-procedure</tt>, com o ambiente <tt>env</tt>.</p><p>
<a name="%_sec_Temp_769" id="%_sec_Temp_769"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_769">Avaliando aplicações de procedimento</a></h4><p>
<a name="%_idx_6046" id="%_idx_6046"/><a name="%_idx_6048" id="%_idx_6048"/>Uma aplicações de procedimento é especificado por uma combinação que contém um operador e operandos. O operador é uma subexpressão cujo valor é um procedimento e os operandos são subexpressões cujos valores são os argumentos aos quais o procedimento deve ser aplicado. O <tt>eval</tt> metacircular lida com aplicações chamando-se recursivamente para avaliar cada elemento da combinação e passando os resultados para <tt>apply</tt>, que executa a aplicação de procedimento real. O avaliador de controle explícito faz o mesmo; essas chamadas recursivas são implementadas por instruções <tt>goto</tt>, com o<a name="%_idx_6050" id="%_idx_6050"/>uso da pilha para salvar registradores que serão restaurados após o retorno da chamada recursiva. Antes de cada chamada, teremos o cuidado de identificar quais registradores devem ser salvos (pois seus valores serão necessários posteriormente).<a name="call_footnote_Temp_770" href="#footnote_Temp_770" id="call_footnote_Temp_770"><sup><small>21</small></sup></a></p><p>Iniciamos a avaliação de uma aplicação avaliando o operador para produzir um procedimento, que será aplicado posteriormente aos operandos avaliados. Para avaliar o operador, movemos para o registrador <tt>exp</tt> e vamos para <tt>eval-dispatch</tt>. O ambiente no registrador <tt>env</tt> já é o correto para avaliar o operador. No entanto, economizamos <tt>env</tt>, pois precisaremos mais tarde para avaliar os operandos. Também extraímos os operandos para <tt>unev</tt> e salve isso na pilha. Montamos <tt>continue</tt> de modo a <tt>eval-dispatch</tt> será retomado às <tt>ev-appl-did-operator</tt> após o operador ter sido avaliado. Primeiro, porém, salvamos o valor antigo de <tt>continue</tt>, que informa ao controlador onde continuar após a aplicação.</p><p>
</p><p/><p><tt><a name="%_idx_6056" id="%_idx_6056"/>ev-application<br/>
(save continue)<br/>
(save env)<br/>
(assign unev (op operands) (reg exp))<br/>
(save unev)<br/>
(assign exp (op operator) (reg exp))<br/>
(assign continue (label ev-appl-did-operator))<br/>
(goto (label eval-dispatch))<br/></tt></p><p/><p/><p>
<a name="%_idx_6058" id="%_idx_6058"/>Ao retornar da avaliação da subexpressão do operador, passamos a avaliar os operandos da combinação e a acumular os argumentos resultantes em uma lista, mantida em <tt>argl</tt>. Primeiro, restauramos os operandos não avaliados e o ambiente. iniciamos <tt>argl</tt> para uma lista vazia. Então atribuímos ao registrador o procedimento <tt>proc</tt> produzido avaliando o operador. Se não houver operandos, vamos diretamente para <tt>apply-dispatch</tt>. Caso contrário, salvamos <tt>proc</tt> na pilha e inicie o laço de avaliação de argumentos:<a name="call_footnote_Temp_771" href="#footnote_Temp_771" id="call_footnote_Temp_771"><sup><small>22</small></sup></a></p><p>
</p><p/><p><tt>ev-appl-did-operator<br/>
(restore unev) <em>; the operands</em><br/>
(restore env)<br/>
(assign argl (op empty-arglist))<br/>
(assign proc (reg val)) <em>; the operator</em><br/>
(test (op no-operands?) (reg unev))<br/>
(branch (label apply-dispatch))<br/>
(save proc)<br/></tt></p><p/><p/><p>Cada ciclo do laço de avaliação de argumento avalia um operando da lista em <tt>unev</tt> e acumula o resultado em <tt>argl</tt>. Para avaliar um operando, o colocamos no registrador <tt>exp</tt> e vamos para <tt>eval-dispatch</tt>, após configurar <tt>continue</tt> para que a execução seja retomada com a fase de acumulação de argumentos. Mas primeiro salvamos os argumentos acumulados até agora (mantidos em <tt>argl</tt>), o ambiente (mantido em <tt>env</tt>) e os demais operandos a serem avaliados (realizados em <tt>unev</tt>) Um caso especial é feito para a avaliação do último operando, que é tratado em <tt>ev-appl-last-arg</tt>.</p><p>
</p><p/><p><tt>ev-appl-operand-loop<br/>
(save argl)<br/>
(assign exp (op first-operand) (reg unev))<br/>
(test (op last-operand?) (reg unev))<br/>
(branch (label ev-appl-last-arg))<br/>
(save env)<br/>
(save unev)<br/>
(assign continue (label ev-appl-accumulate-arg))<br/>
(goto (label eval-dispatch))<br/></tt></p><p/><p/><p>Quando um operando é avaliado, o valor é acumulado na lista mantida em <tt>argl</tt>. O operando é então removido da lista de operandos não avaliados em <tt>unev</tt>, e a avaliação do argumento continua.</p><p>
</p><p/><p><tt>ev-appl-accumulate-arg<br/>
(restore unev)<br/>
(restore env)<br/>
(restore argl)<br/>
(assign argl (op adjoin-arg) (reg val) (reg argl))<br/>
(assign unev (op rest-operands) (reg unev))<br/>
(goto (label ev-appl-operand-loop))<br/></tt></p><p/><p/><p>A avaliação do último argumento é tratada de maneira diferente. Não há necessidade de salvar o ambiente ou a lista de operandos não avaliados antes de ir para <tt>eval-dispatch</tt>, pois eles não serão necessários após a avaliação do último operando. Assim, retornamos da avaliação para um ponto de entrada especial <tt>ev-appl-accum-last-arg</tt>, que restaura a lista de argumentos, acumula o novo argumento, restaura o procedimento salvo e sai para executar a aplicação.<a name="call_footnote_Temp_772" href="#footnote_Temp_772" id="call_footnote_Temp_772"><sup><small>23</small></sup></a></p><p>
</p><p/><p><tt>ev-appl-last-arg<br/>
(assign continue (label ev-appl-accum-last-arg))<br/>
(goto (label eval-dispatch))<br/>
ev-appl-accum-last-arg<br/>
(restore argl)<br/>
(assign argl (op adjoin-arg) (reg val) (reg argl))<br/>
(restore proc)<br/>
(goto (label apply-dispatch))<br/></tt></p><p/><p/><p>
<a name="%_idx_6070" id="%_idx_6070"/>Os detalhes do laço de avaliação de argumento determinam a ordem em que o interpretador avalia os operandos de uma combinação (por exemplo, da esquerda para a direita ou da direita para a esquerda – veja o exercício <a href="book-Z-H-20.html#%_thm_3.8">3.8</a>) Essa ordem não é determinada pelo avaliador metacircular, que herda sua estrutura de controle do Scheme subjacente no qual é implementado.<a name="call_footnote_Temp_773" href="#footnote_Temp_773" id="call_footnote_Temp_773"><sup><small>24</small></sup></a> Porque o seletor <tt>first-operand</tt> (usado em <tt>ev-appl-operand-loop</tt> para extrair operandos sucessivos de <tt>unev</tt>) é implementado como <tt>car</tt> e o seletor <tt>rest-operands</tt> é implementado como <tt>cdr</tt>, o avaliador de controle explícito avaliará os operandos de uma combinação na ordem da esquerda para a direita.</p><p>
<a name="%_sec_Temp_774" id="%_sec_Temp_774"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_774">Aplicação do procedimento</a></h4><p>
</p><p>O ponto de entrada <tt>apply-dispatch</tt> corresponde ao procedimento <tt>apply</tt> do avaliador metacircular. Quando chegamos a <tt>apply-dispatch</tt>, o registrador <tt>proc</tt> contém o procedimento para aplicar e <tt>argl</tt> contém a lista de argumentos avaliados aos quais ele deve ser aplicado. O valor salvo de <tt>continue</tt> (originalmente passado para <tt>eval-dispatch</tt> e salvo em <tt>ev-application</tt>), que informa para onde retornar com o resultado da aplicação de procedimento, está na pilha. Quando aplicação é concluída, o controlador é transferido para o ponto de entrada especificado pelo <tt>continue</tt>, com o resultado da aplicação em <tt>val</tt>. Tal como acontece com a metacircular <tt>apply</tt>, há dois casos a serem considerados. O procedimento a ser aplicado é primitivo ou é um procedimento composto.</p><p>
</p><p/><p><tt><a name="%_idx_6072" id="%_idx_6072"/>apply-dispatch<br/>
(test (op primitive-procedure?) (reg proc))<br/>
(branch (label primitive-apply))<br/>
(test (op compound-procedure?) (reg proc)) <br/>
(branch (label compound-apply))<br/>
(goto (label unknown-procedure-type))<br/></tt></p><p/><p/><p>
<a name="%_idx_6074" id="%_idx_6074"/>Assumimos que cada primitiva é implementada de modo a obter seus argumentos de <tt>argl</tt> e colocar seu resultado em <tt>val</tt>. Para especificar como a máquina lida com as primitivas, teríamos de fornecer uma sequência de instruções do controlador para implementar cada primitivo e organizar <tt>primitive-apply</tt> enviar para as instruções da primitiva identificada pelo conteúdo de <tt>proc</tt>. Como estamos interessados na estrutura do processo de avaliação e não nos detalhes das primitivas, usaremos apenas uma operação <tt>apply-primitive-procedure</tt> que aplica o procedimento em <tt>proc</tt> para os argumentos em <tt>argl</tt>. Com o objetivo de simular o avaliador com o simulador da seção <a href="book-Z-H-32.html#%_sec_5.2">5.2.</a> usamos o procedimento <tt>apply-primitive-procedure</tt>, que solicita que o sistema Scheme subjacente execute a aplicação, assim como fizemos com o avaliador metacircular na seção <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>. Depois de calcular o valor da aplicação primitiva, restauramos <tt>continue</tt> e vá para o ponto de entrada designado.</p><p>
</p><p/><p><tt><a name="%_idx_6076" id="%_idx_6076"/>primitive-apply<br/>
(assign val (op apply-primitive-procedure)<br/>
(reg proc)<br/>
(reg argl))<br/>
(restore continue)<br/>
(goto (reg continue))<br/></tt></p><p/><p/><p>
<a name="%_idx_6078" id="%_idx_6078"/>Para aplicar um procedimento composto, procedemos da mesma forma que com o avaliador metacircular. Construímos um quadro que liga os parâmetros do procedimento aos argumentos, usamos esse quadro para estender o ambiente transportado pelo procedimento e avaliamos nesse ambiente estendido a sequência de expressões que forma o corpo do procedimento. <tt>Ev-sequence</tt>, descrito abaixo na seção <a href="#%_sec_5.4.2">5.4.2</a>, lida com a avaliação da sequência.</p><p>
</p><p/><p><tt><a name="%_idx_6080" id="%_idx_6080"/>compound-apply<br/>
(assign unev (op procedure-parameters) (reg proc))<br/>
(assign env (op procedure-environment) (reg proc))<br/>
(assign env (op extend-environment)<br/>
(reg unev) (reg argl) (reg env))<br/>
(assign unev (op procedure-body) (reg proc))<br/>
(goto (label ev-sequence))<br/></tt></p><p/><p/><p>
<tt>Compound-apply</tt> é o único lugar no interpretador em que o registrador <tt>env</tt> recebe um novo valor. Assim como no avaliador metacircular, o novo ambiente é construído a partir do ambiente realizado pelo procedimento, com a lista de argumentos e a lista correspondente de variáveis a serem ligadas.</p><p>
<a name="%_sec_5.4.2" id="%_sec_5.4.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.4.2">5.4.2 Avaliação de sequência e recursão de cauda</a></h3><p>
<a name="%_idx_6082" id="%_idx_6082"/>A parte do avaliador de controle explícito em <tt>ev-sequence</tt> é análogo ao do avaliador metacircular do procedimento <tt>eval-sequence</tt>. Ele lida com sequências de expressões em corpos de procedimentos ou em expressões <tt>begin</tt> explícitas.</p><p>Expressões <tt>begin</tt> explícitas são avaliadas colocando a sequência de expressões a serem avaliadas em <tt>unev</tt> salvando <tt>continue</tt> na pilha e pulando para <tt>ev-sequence</tt>.</p><p/><p><tt><a name="%_idx_6084" id="%_idx_6084"/>ev-begin<br/>
(assign unev (op begin-actions) (reg exp))<br/>
(save continue)<br/>
(goto (label ev-sequence))<br/></tt></p><p/><p>As sequências implícitas nos corpos dos procedimentos são tratadas saltando para <tt>ev-sequence</tt> de <tt>compound-apply</tt>, no ponto em que <tt>continue</tt> já está na pilha, tendo sido salvo em <tt>ev-application</tt>.</p><p>As entradas em <tt>ev-sequence</tt> e <tt>ev-sequence-continue</tt> formam um laço que avalia sucessivamente cada expressão em uma sequência. A lista de expressões não avaliadas é mantida em <tt>unev</tt>. Antes de avaliar cada expressão, verificamos se há expressões adicionais a serem avaliadas na sequência. Nesse caso, salvamos o restante das expressões não avaliadas (mantidas em <tt>unev</tt>) e o ambiente em que elas devem ser avaliadas (mantidas em <tt>env</tt>) e chamamos <tt>eval-dispatch</tt> para avaliar a expressão. Os dois registradores salvos são restaurados após o retorno desta avaliação, em <tt>ev-sequence-continue</tt>.</p><p>A expressão final na sequência é tratada de maneira diferente, no ponto de entrada <tt>ev-sequence-last-exp</tt>. Como não há mais expressões a serem avaliadas após esta, não precisamos salvar <tt>unev</tt> ou <tt>env</tt> antes de ir para <tt>eval-dispatch</tt>. O valor de toda a sequência é o valor da última expressão; portanto, após a avaliação da última expressão, não há mais nada a fazer, exceto continuar no ponto de entrada atualmente mantido na pilha (que foi salvo por <tt>ev-application</tt> ou <tt>ev-begin</tt>). Em vez de configurar <tt>continue</tt> para fazer com que <tt>eval-dispatch</tt> retorne aqui e então restaure <tt>continue</tt> da pilha e continuando naquele ponto de entrada, restauramos <tt>continue</tt> da pilha antes de ir para <tt>eval-dispatch</tt>, de modo que <tt>eval-dispatch</tt> continuará naquele ponto de entrada após avaliar a expressão.</p><p>
</p><p/><p><tt><a name="%_idx_6086" id="%_idx_6086"/>ev-sequence<br/>
(assign exp (op first-exp) (reg unev))<br/>
(test (op last-exp?) (reg unev))<br/>
(branch (label ev-sequence-last-exp))<br/>
(save unev)<br/>
(save env)<br/>
(assign continue (label ev-sequence-continue))<br/>
(goto (label eval-dispatch))<br/>
ev-sequence-continue<br/>
(restore env)<br/>
(restore unev)<br/>
(assign unev (op rest-exps) (reg unev))<br/>
(goto (label ev-sequence))<br/>
ev-sequence-last-exp<br/>
(restore continue)<br/>
(goto (label eval-dispatch))<br/></tt></p><p/><p/><p>
<a name="%_sec_Temp_775" id="%_sec_Temp_775"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_775">Recursão de cauda</a></h4><p>
<a name="%_idx_6088" id="%_idx_6088"/><a name="%_idx_6090" id="%_idx_6090"/>No capítulo 1, dissemos que o processo descrito por um procedimento como</p><p>
</p><p/><p><tt>(define (sqrt-iter guess x)<br/>
(if (good-enough? guess x)<br/>
guess<br/>
(sqrt-iter (improve guess x)<br/>
x)))<br/></tt></p><p/><p>fosse um processo iterativo. Embora o procedimento seja sintaticamente recursivo (definido em termos de si mesmo), não é logicamente necessário que um avaliador salve informações ao passar de uma chamada para outra. <tt>sqrt-iter</tt> para a próximo.<a name="call_footnote_Temp_776" href="#footnote_Temp_776" id="call_footnote_Temp_776"><sup><small>25</small></sup></a> Um avaliador que pode executar um procedimento como <tt>sqrt-iter</tt> sem a necessidade de aumentar o armazenamento, pois o procedimento continua a se chamar é chamado de avaliador <a name="%_idx_6092" id="%_idx_6092"/><em>recursivo de cauda</em>. <a name="%_idx_6094" id="%_idx_6094"/><a name="%_idx_6096" id="%_idx_6096"/>A implementação metacircular do avaliador no capítulo 4 não especifica se o avaliador é recursivo de cauda, pois esse avaliador herda seu mecanismo para salvar o estado do Scheme subjacente. No entanto, com o avaliador de controle explícito, podemos rastrear o processo de avaliação para ver quando as chamadas de procedimento causam um acúmulo líquido de informações na pilha.</p><p>Nosso avaliador é recursivo de cauda, pois, para avaliar a expressão final de uma sequência, transferimos diretamente para <tt>eval-dispatch</tt> sem salvar nenhuma informação na pilha. Portanto, avaliar a expressão final em uma sequência – mesmo que seja uma chamada de procedimento (como em <tt>sqrt-iter</tt>, onde a expressão <tt>if</tt>, que é a última expressão no corpo do procedimento, reduz a uma chamada para <tt>sqrt-iter</tt>) – não fará com que nenhuma informação seja acumulada na pilha.<a name="call_footnote_Temp_777" href="#footnote_Temp_777" id="call_footnote_Temp_777"><sup><small>26</small></sup></a></p><p>Se não pensássemos em tirar proveito do fato de que era desnecessário salvar informações nesse caso, poderíamos ter implementado <tt>eval-sequence</tt> tratando todas as expressões em uma sequência da mesma maneira – salvando os registradores, avaliando a expressão, retornando para restaurar os registradores e repetindo isso até que todas as expressões tenham sido avaliadas:<a name="call_footnote_Temp_778" href="#footnote_Temp_778" id="call_footnote_Temp_778"><sup><small>27</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_6100" id="%_idx_6100"/>ev-sequence<br/>
(test (op no-more-exps?) (reg unev))<br/>
(branch (label ev-sequence-end))<br/>
(assign exp (op first-exp) (reg unev))<br/>
(save unev)<br/>
(save env)<br/>
(assign continue (label ev-sequence-continue))<br/>
(goto (label eval-dispatch))<br/>
ev-sequence-continue<br/>
(restore env)<br/>
(restore unev)<br/>
(assign unev (op rest-exps) (reg unev))<br/>
(goto (label ev-sequence))<br/>
ev-sequence-end<br/>
(restore continue)<br/>
(goto (reg continue))<br/></tt></p><p/><p/><p>Isso pode parecer uma pequena alteração em nosso código anterior para avaliação de uma sequência: a única diferença é que passamos pelo ciclo de salvar e restaurar para a última expressão em uma sequência e para as outras. O interpretador ainda dará o mesmo valor para qualquer expressão. Mas essa mudança é fatal para a implementação recursiva de cauda, pois agora devemos retornar depois de avaliar a expressão final em uma sequência para desfazer os registradores (inúteis) salvos. Esses registradores extras serão acumulados durante um aninhamento de chamadas de procedimento. Consequentemente, processos como <tt>sqrt-iter</tt> exigirá espaço proporcional ao número de iterações, em vez de exigir espaço constante. Essa diferença pode ser significativa. Por exemplo, <a name="%_idx_6102" id="%_idx_6102"/>com recursão de cauda, um laço infinito pode ser expresso usando apenas o mecanismo de chamada de procedimento:</p><p>
</p><p/><p><tt>(define (count n)<br/>
(newline)<br/>
(display n)<br/>
(count (+ n 1)))<br/></tt></p><p/><p>Sem recursão de cauda, esse procedimento acabaria ficando sem espaço na pilha, e expressar uma iteração verdadeira exigiria algum mecanismo de controle além da chamada de procedimento.</p><p>
<a name="%_sec_5.4.3" id="%_sec_5.4.3"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.4.3">5.4.3 Condicionais, atribuições e definições</a></h3><p>
<a name="%_idx_6104" id="%_idx_6104"/>Como no avaliador metacircular, formas especiais são tratadas avaliando seletivamente fragmentos da expressão. Para uma expressão <tt>if</tt>, devemos avaliar o predicado e decidir, com base no valor do predicado, se deve avaliar o consequente ou a alternativa.</p><p>Antes de avaliar o predicado, salvamos a expressão <tt>if</tt> em si para que possamos extrair mais tarde a consequente ou alternativa. Também salvamos o ambiente, que precisaremos posteriormente para avaliar o consequente ou o alternativo, e salvamos <tt>continue</tt>, que precisaremos posteriormente para retornar à avaliação da expressão que aguarda o valor do <tt>if</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_6106" id="%_idx_6106"/>ev-if<br/>
(save exp) <em>; save expression for later</em><br/>
(save env)<br/>
(save continue)<br/>
(assign continue (label ev-if-decide))<br/>
(assign exp (op if-predicate) (reg exp))<br/>
(goto (label eval-dispatch)) <em>; evaluate the predicate</em><br/></tt></p><p/><p/><p>Quando voltamos da avaliação do predicado, testamos se era verdadeiro ou falso e, dependendo do resultado, colocamos o consequente ou a alternativa em <tt>exp</tt> antes de ir para <tt>eval-dispatch</tt>. Observe que a restauração <tt>env</tt> e <tt>continue</tt> aqui configura <tt>eval-dispatch</tt> para ter o ambiente correto e continuar no lugar certo para receber o valor da expressão <tt>if</tt>.</p><p>
</p><p/><p><tt>ev-if-decide<br/>
(restore continue)<br/>
(restore env)<br/>
(restore exp)<br/>
(test (op true?) (reg val))<br/>
(branch (label ev-if-consequent))<br/><br/>
ev-if-alternative<br/>
(assign exp (op if-alternative) (reg exp))<br/>
(goto (label eval-dispatch))<br/>
ev-if-consequent<br/>
(assign exp (op if-consequent) (reg exp))<br/>
(goto (label eval-dispatch))<br/></tt></p><p/><p/><p>
<a name="%_sec_Temp_779" id="%_sec_Temp_779"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_779">Atribuições e definições</a></h4><p>
<a name="%_idx_6108" id="%_idx_6108"/>As atribuições são tratadas por <tt>ev-assignment</tt>, que é alcançada a partir de <tt>eval-dispatch</tt> com a expressão de atribuição em <tt>exp</tt>. O código em <tt>ev-assignment</tt> primeiro avalia a parte do valor da expressão e depois instala o novo valor no ambiente. <tt>Set-variable-value!</tt> é considerado disponível como uma operação de máquina.</p><p>
</p><p/><p><tt><a name="%_idx_6110" id="%_idx_6110"/>ev-assignment<br/>
(assign unev (op assignment-variable) (reg exp))<br/>
(save unev) <em>; save variable for later</em><br/>
(assign exp (op assignment-value) (reg exp))<br/>
(save env)<br/>
(save continue)<br/>
(assign continue (label ev-assignment-1))<br/>
(goto (label eval-dispatch)) <em>; evaluate the assignment value</em><br/>
ev-assignment-1<br/>
(restore continue)<br/>
(restore env)<br/>
(restore unev)<br/>
(perform<br/>
(op set-variable-value!) (reg unev) (reg val) (reg env))<br/>
(assign val (const ok))<br/>
(goto (reg continue))<br/></tt></p><p/><p/><p>
<a name="%_idx_6112" id="%_idx_6112"/>As definições são tratadas de maneira semelhante:</p><p/><p><tt><a name="%_idx_6114" id="%_idx_6114"/>ev-definition<br/>
(assign unev (op definition-variable) (reg exp))<br/>
(save unev) <em>; save variable for later</em><br/>
(assign exp (op definition-value) (reg exp))<br/>
(save env)<br/>
(save continue)<br/>
(assign continue (label ev-definition-1))<br/>
(goto (label eval-dispatch)) <em>; evaluate the definition value</em><br/>
ev-definition-1<br/>
(restore continue)<br/>
(restore env)<br/>
(restore unev)<br/>
(perform<br/>
(op define-variable!) (reg unev) (reg val) (reg env))<br/>
(assign val (const ok))<br/>
(goto (reg continue))<br/></tt></p><p/><p>
</p><p>
</p><p><a name="%_thm_5.23" id="%_thm_5.23"/>
<b>Exercício 5.23.</b> <a name="%_idx_6116" id="%_idx_6116"/><a name="%_idx_6118" id="%_idx_6118"/><a name="%_idx_6120" id="%_idx_6120"/>Estenda o avaliador para lidar com expressões derivadas, como <tt>cond</tt>, <tt>let</tt> e assim por diante (seção <a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a>) Você pode “trapacear” e assumir que os transformadores de sintaxe, como <tt>cond->if</tt> estão disponíveis como operações da máquina.<a name="call_footnote_Temp_781" href="#footnote_Temp_781" id="call_footnote_Temp_781"><sup><small>28.</small></sup></a>
</p><p/><p>
</p><p><a name="%_thm_5.24" id="%_thm_5.24"/>
<b>Exercício 5.24.</b> <a name="%_idx_6122" id="%_idx_6122"/>Implemente <tt>cond</tt> como uma nova forma especial básica sem reduzi-la a <tt>if</tt>. Você terá que construir um laço que teste os predicados de sucessivos <tt>cond</tt> até encontrar uma verdadeira e, em seguida, use <tt>ev-sequence</tt> avaliar as ações da cláusula.</p><p/><p>
</p><p><a name="%_thm_5.25" id="%_thm_5.25"/>
<b>Exercício 5.25.</b> <a name="%_idx_6124" id="%_idx_6124"/><a name="%_idx_6126" id="%_idx_6126"/>Modifique o avaliador para que ele use a avaliação de ordem normal, com base no avaliador preguiçoso da seção <a href="book-Z-H-27.html#%_sec_4.2">4.2</a>.</p><p/><p>
<a name="%_sec_5.4.4" id="%_sec_5.4.4"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.4.4">5.4.4 Executando o avaliador</a></h3><p>
<a name="%_idx_6128" id="%_idx_6128"/>
<a name="%_idx_6130" id="%_idx_6130"/><a name="%_idx_6132" id="%_idx_6132"/>Com a implementação do avaliador de controle explícito, chegamos ao final de um desenvolvimento, iniciado no capítulo 1, no qual exploramos modelos sucessivamente mais precisos do processo de avaliação. Começamos com o modelo de substituição relativamente informal e, em seguida, estendemos isso no capítulo 3 ao modelo de ambiente, o que nos permitiu lidar com estado e mudança. No avaliador metacircular do capítulo 4, usamos o próprio Scheme como uma linguagem para tornar mais explícita a estrutura do ambiente construída durante a avaliação de uma expressão. Agora, com as máquinas de registradores, examinamos atentamente os mecanismos do avaliador para gerenciamento de armazenamento, passagem de argumentos e controle. Em cada novo nível de descrição, tivemos que levantar questões e resolver ambiguidades que não eram aparentes no tratamento anterior e menos preciso da avaliação. Para entender o comportamento do avaliador de controle explícito, podemos simulá-lo e monitorar seu desempenho.</p><p>
<a name="%_idx_6134" id="%_idx_6134"/><a name="%_idx_6136" id="%_idx_6136"/>Instalaremos um laço do controlador em nossa máquina avaliadora. Isso desempenha o papel do procedimento <tt>driver-loop</tt> de seção <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>. O avaliador imprime repetidamente um prompt, lê uma expressão, avalia a expressão acessando <tt>eval-dispatch</tt> e imprima o resultado. As instruções a seguir formam o início da sequência do controlador do avaliador de controle explícito:<a name="call_footnote_Temp_784" href="#footnote_Temp_784" id="call_footnote_Temp_784"><sup><small>29</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_6142" id="%_idx_6142"/><a name="%_idx_6144" id="%_idx_6144"/>read-eval-print-loop<br/>
(perform (op initialize-stack))<br/>
(perform<br/>
(op prompt-for-input) (const ";;; EC-Eval input:"))<br/>
(assign exp (op read))<br/>
(assign env (op get-global-environment))<br/>
(assign continue (label print-result))<br/>
(goto (label eval-dispatch))<br/><a name="%_idx_6146" id="%_idx_6146"/>print-result<br/>
(perform<br/>
(op announce-output) (const ";;; EC-Eval value:"))<br/>
(perform (op user-print) (reg val))<br/>
(goto (label read-eval-print-loop))<br/></tt></p><p/><p/><p>
<a name="%_idx_6148" id="%_idx_6148"/><a name="%_idx_6150" id="%_idx_6150"/>Quando encontramos um erro em um procedimento (como o “erro de tipo de procedimento desconhecido” indicado em <tt>apply-dispatch</tt>), imprimimos uma mensagem de erro e retornamos ao laço do controlador.<a name="call_footnote_Temp_785" href="#footnote_Temp_785" id="call_footnote_Temp_785"><sup><small>30</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_6152" id="%_idx_6152"/>unknown-expression-type<br/>
(assign val (const unknown-expression-type-error))<br/>
(goto (label signal-error))<br/><a name="%_idx_6154" id="%_idx_6154"/>unknown-procedure-type<br/>
(restore continue) <em>; clean up stack (from <tt>apply-dispatch</tt>)</em><br/>
(assign val (const unknown-procedure-type-error))<br/>
(goto (label signal-error))<br/><a name="%_idx_6156" id="%_idx_6156"/>signal-error<br/>
(perform (op user-print) (reg val))<br/>
(goto (label read-eval-print-loop))<br/></tt></p><p/><p/><p>Para os propósitos da simulação, iniciamos a pilha toda vez através do laço do controlador, pois ela pode não estar vazia após um erro (como uma variável indefinida) interromper uma avaliação.<a name="call_footnote_Temp_786" href="#footnote_Temp_786" id="call_footnote_Temp_786"><sup><small>31</small></sup></a></p><p>
<a name="%_idx_6158" id="%_idx_6158"/>Se combinarmos todos os fragmentos de código apresentados nas seções <a href="#%_sec_5.4.1">5.4.1</a>-<a href="#%_sec_5.4.4">5.4.4</a>, podemos criar um modelo de máquina avaliadora que podemos executar usando o simulador de máquina de registradores da seção <a href="book-Z-H-32.html#%_sec_5.2">5.2.</a>.</p><p>
</p><p/><p><tt>(define eceval<br/>
(make-machine<br/>
'(exp env val proc argl continue unev)<br/>
eceval-operations<br/>
'(<br/>
read-eval-print-loop<br/>
<<em>entire machine controller as given above</em>><br/>
)))<br/></tt></p><p/><p>Devemos definir procedimentos do Scheme para simular as operações usadas como primitivas pelo avaliador. Estes são os mesmos procedimentos que usamos para o avaliador metacircular na seção <a href="book-Z-H-26.html#%_sec_4.1">4.1</a>, com os poucos adicionais definidos nas notas de rodapé ao longo da seção <a href="#%_sec_5.4">5.4</a>.</p><p/><p><tt>(define eceval-operations<br/>
(list (list 'self-evaluating? self-evaluating)<br/>
<em><complete list of operations for eceval machine></em>))<br/></tt></p><p/><p/><p>Finalmente, podemos iniciar o ambiente global e executar o avaliador:</p><p/><p><tt>(define the-global-environment (setup-environment))<br/><br/>
(start eceval)<br/><i>;;; EC-Eval input:</i><br/>
(define (append x y)<br/>
(if (null? x)<br/>
y<br/>
(cons (car x)<br/>
(append (cdr x) y))))<br/><i>;;; EC-Eval value:</i><br/><i>ok</i><br/><i>;;; EC-Eval input:</i><br/>
(append '(a b c) '(d e f))<br/><i>;;; EC-Eval value:</i><br/><i>(a b c d e f)</i><br/></tt></p><p/><p/><p>Obviamente, avaliar expressões dessa maneira levará muito mais tempo do que se as tivéssemos digitado diretamente no Scheme, devido aos vários níveis de simulação envolvidos. Nossas expressões são avaliadas pela máquina do avaliador de controle explícito, que é simulado por um programa Scheme, que é avaliado pelo interpretador Scheme.</p><p>
<a name="%_sec_Temp_787" id="%_sec_Temp_787"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_787">Monitorando o desempenho do avaliador</a></h4><p>
<a name="%_idx_6160" id="%_idx_6160"/>
<a name="%_idx_6162" id="%_idx_6162"/>A simulação pode ser uma ferramenta poderosa para orientar a implementação dos avaliadores. As simulações facilitam não apenas explorar as variações do projeto da máquina de registradores, mas também monitorar o desempenho do avaliador simulado. Por exemplo, um fator importante no desempenho é a eficiência com que o avaliador usa a pilha. Podemos observar o número de operações de pilha necessárias para avaliar várias expressões, definindo a máquina de registradores do avaliador com a versão do simulador que coleta estatísticas sobre o uso da pilha (seção <a href="book-Z-H-32.html#%_sec_5.2.4">5.2.4</a>) e adicionando uma instrução às instruções ponto de entrada <tt>print-result</tt> do avaliador para imprimir as estatísticas:</p><p>
</p><p/><p><tt><a name="%_idx_6164" id="%_idx_6164"/>print-result<br/>
(perform (op print-stack-statistics))<em>; added instruction</em><br/>
(perform<br/>
(op announce-output) (const ";;; EC-Eval value:"))<br/>
<tt>...</tt> <em>; same as before</em><br/></tt></p><p/><p>As interações com o avaliador agora são assim:</p><p/><p><tt><i>;;; EC-Eval input:</i><br/>
(define (factorial n)<br/>
(if (= n 1)<br/>
1<br/>
(* (factorial (- n 1)) n)))<br/><i>(total-pushes = 3 maximum-depth = 3)</i><br/><i>;;; EC-Eval value:</i><br/><i>ok</i><br/><i>;;; EC-Eval input:</i><br/>
(factorial 5)<br/><i>(total-pushes = 144 maximum-depth = 28)</i><br/><i>;;; EC-Eval value:</i><br/><i>120</i><br/></tt></p><p/><p>Observe que o laço do controlador do avaliador reinicia a pilha no início de cada interação, para que as estatísticas impressas se refiram apenas às operações de pilha usadas para avaliar a expressão anterior.</p><p>
</p><p><a name="%_thm_5.26" id="%_thm_5.26"/>
<b>Exercício 5.26.</b> <a name="%_idx_6166" id="%_idx_6166"/><a name="%_idx_6168" id="%_idx_6168"/><a name="%_idx_6170" id="%_idx_6170"/>Use a pilha monitorada para explorar a propriedade recursiva de cauda do avaliador (seção <a href="#%_sec_5.4.2">5.4.2</a>) Inicie o avaliador e defina a iterativa procedimento <tt>factorial</tt> da seção <a href="book-Z-H-11.html#%_sec_1.2.1">1.2.1</a>:</p><p>
</p><p/><p><tt>(define (factorial n)<br/>
(define (iter product counter)<br/>
(if (> counter n)<br/>
product<br/>
(iter (* counter product)<br/>
(+ counter 1))))<br/>
(iter 1 1))<br/></tt></p><p/><p>Execute o procedimento com alguns pequenos valores de <em>n</em>. Registre a profundidade máxima da pilha e o número de empilhamentos necessários para calcular <em>n</em>! para cada um desses valores.</p><p>
</p><p/><p>a. Você descobrirá que a profundidade máxima necessária para avaliar <em>n</em>! é independente de <em>n</em>. Qual é essa profundidade?</p><p>
</p><p/><p>b. Determine a partir de seus dados uma fórmula em termos de <em>n</em> para o número total de operações de empilhamentos usadas na avaliação <em>n</em>! para qualquer <em>n</em><u>></u> 1 Observe que o número de operações utilizadas é uma função linear de <em>n</em> e é assim determinado por duas constantes.</p><p/><p>
</p><p><a name="%_thm_5.27" id="%_thm_5.27"/>
<b>Exercício 5.27.</b> <a name="%_idx_6172" id="%_idx_6172"/>Para comparação com exercício <a href="#%_thm_5.26">5.26</a>, explore o comportamento do procedimento a seguir para calcular fatoriais recursivamente:</p><p/><p><tt>(define (factorial n)<br/>
(if (= n 1)<br/>
1<br/>
(* (factorial (- n 1)) n)))<br/></tt></p><p/><p>Executando este procedimento com a pilha monitorada, determine, em função da <em>n</em>, a profundidade máxima da pilha e o número total de empilhamentos usados na avaliação <em>n</em>! para <em>n</em><u>></u> 1 (Novamente, essas funções serão lineares). Resuma seus experimentos preenchendo a tabela a seguir com as expressões apropriadas em termos de <em>n</em>:</p><p>
</p><table border="1"><tr><td valign="top"/><td valign="top">Profundidade máxima</td><td valign="top">Número de empilhamentos</td></tr><tr><td valign="top">Fatorial recursivo</td><td valign="top"/><td valign="top"/></tr><tr><td valign="top"></td><td valign="top"/><td valign="top"/></tr><tr><td valign="top">Fatorial iterativo</td><td valign="top"/><td valign="top"/></tr><tr><td valign="top"></td><td valign="top"/><td valign="top"/></tr><tr><td valign="top"/></tr></table><p>A profundidade máxima é uma medida da quantidade de espaço usada pelo avaliador na execução do cálculo, e o número de empilhamentos se correlaciona bem com o tempo necessário.</p><p/><p>
</p><p>
</p><p><a name="%_thm_5.28" id="%_thm_5.28"/>
<b>Exercício 5.28.</b> <a name="%_idx_6174" id="%_idx_6174"/><a name="%_idx_6176" id="%_idx_6176"/>Modifique a definição do avaliador alterando <tt>eval-sequence</tt> conforme descrito na seção <a href="#%_sec_5.4.2">5.4.2</a> para que o avaliador não seja mais recursivo de cauda. Execute novamente seus experimentos a partir dos exercícios <a href="#%_thm_5.26">5.26</a> e <a href="#%_thm_5.27">5.27</a> para demonstrar que ambas as versões do <tt>factorial</tt> Agora, o procedimento exige espaço que cresce linearmente com sua entrada.</p><p/><p>
</p><p><a name="%_thm_5.29" id="%_thm_5.29"/>
<b>Exercício 5.29.</b> <a name="%_idx_6178" id="%_idx_6178"/>Monitore as operações de pilha na computação de Fibonacci recursiva em árvore:</p><p>
</p><p/><p><tt><a name="%_idx_6180" id="%_idx_6180"/>(define (fib n)<br/>
(if (< n 2)<br/>
n<br/>
(+ (fib (- n 1)) (fib (- n 2)))))<br/></tt></p><p/><p>a. Dê uma fórmula em termos de <em>n</em> para a profundidade máxima da pilha necessária para calcular <em>F</em><em>i</em><em>b</em>(<em>n</em>) para <em>n</em><u>></u> 2) Dica: Na seção <a href="book-Z-H-11.html#%_sec_1.2.2">1.2.2</a> argumentamos que o espaço usado por esse processo cresce linearmente com <em>n</em>.</p><p>
</p><p/><p>b. Forneça uma fórmula para o número total de empilhamentos usados para calcular <em>F</em><em>i</em><em>b</em>(<em>n</em>) para <em>n</em><u>></u> 2) Você deve achar que o número de empilhamentos (que se correlaciona bem com o tempo usado) cresce exponencialmente com <em>n</em>. Dica: Seja <em>S</em>(<em>n</em>) o número de empilhamentos usados na computação <em>F</em><em>i</em><em>b</em>(<em>n</em>) Você deve poder argumentar que existe uma fórmula que expressa <em>S</em>(<em>n</em>) em termos de <em>S</em>(<em>n</em> - 1) <em>S</em>(<em>n</em> - 2), e alguma constante <em>k</em> fixa de “sobrecusto” é independente de <em>n</em>. Dê a fórmula e diga o que <em>k</em> é. Então mostre que <em>S</em>(<em>n</em>) pode ser expresso como <em>um</em> <em>F</em><em>i</em><em>b</em>(<em>n</em> + 1) + <em>b</em> e forneça os valores de <em>a</em> e <em>b</em>.</p><p/><p>
</p><p><a name="%_thm_5.30" id="%_thm_5.30"/>
<b>Exercício 5.30.</b> <a name="%_idx_6182" id="%_idx_6182"/><a name="%_idx_6184" id="%_idx_6184"/>Atualmente, nosso avaliador captura e sinaliza apenas dois tipos de erros – tipos de expressão desconhecidas e tipos de procedimentos desconhecidos. Outros erros nos tirarão do laço de leitura-avaliação-impressão. Quando executamos o avaliador usando o simulador de máquina de registradores, esses erros são detectados pelo sistema subjacente do Scheme. Isso é análogo ao travamento do computador quando um programa do usuário comete um erro.<a name="call_footnote_Temp_793" href="#footnote_Temp_793" id="call_footnote_Temp_793"><sup><small>32</small></sup></a> É um grande projeto fazer um sistema de erro real funcionar, mas vale a pena o esforço para entender o que está envolvido aqui.</p><p>
</p><p/><p>a. Erros que ocorrem no processo de avaliação, como uma tentativa de acessar uma variável não ligada, podem ser detectados alterando a operação de pesquisa para fazer com que ela retorne um código de condição distinto, que não pode ser um valor possível para qualquer variável do usuário. O avaliador pode testar esse código de condição e, em seguida, fazer o necessário para acessar <tt>signal-error</tt>. Encontre todos os lugares no avaliador onde essa mudança é necessária e corrija-os. Isso é muito trabalho.</p><p>
</p><p/><p>b. Muito pior é o problema de lidar com erros que são sinalizados pela aplicação de procedimentos primitivos, como uma tentativa de dividir por zero ou uma tentativa de extrair o <tt>car</tt> de um símbolo. Em um sistema de alta qualidade profissionalmente escrito, cada aplicação primitiva é verificada quanto à segurança como parte da primitiva. Por exemplo, toda chamada para <tt>car</tt> pode primeiro verificar se o argumento é um par. Se o argumento não for um par, a aplicação retornará um código de condição distinto ao avaliador, que reportaria a falha. Poderíamos providenciar isso em nosso simulador de máquina de registradores, verificando cada procedimento primitivo quanto à aplicabilidade e retornando um código de condição distinto apropriado em caso de falha. Então o código <tt>primitive-apply</tt> no avaliador pode verificar o código de condição e ir para <tt>signal-error</tt> se necessário. Crie essa estrutura e faça-a funcionar. Este é um projeto importante.</p><p/><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_765" href="#call_footnote_Temp_765" id="footnote_Temp_765"><sup><small>19</small></sup></a> Veja Batali et al. 1982 para mais <a name="%_idx_6004" id="%_idx_6004"/>informações sobre o circuito integrado e o método pelo qual ele foi projetado.</p><p><a name="footnote_Temp_767" href="#call_footnote_Temp_767" id="footnote_Temp_767"><sup><small>20</small></sup></a> Em nosso controlador, o despacho é escrito como uma sequência de instruções <tt>test</tt> e <tt>branch</tt>. Como alternativa, poderia ter sido escrito em um estilo orientado a dados (e em um sistema real provavelmente teria sido) para evitar a necessidade de executar testes sequenciais e facilitar a definição de novos tipos de expressão. Uma máquina projetada para executar o Lisp provavelmente incluiria um <tt>dispatch-on-type</tt> instruções que executariam com eficiência esses despachos orientados a dados.</p><p><a name="footnote_Temp_770" href="#call_footnote_Temp_770" id="footnote_Temp_770"><sup><small>21</small></sup></a> Este é um ponto importante, mas sutil, na tradução de algoritmos de uma linguagem processual, como Lisp, para uma linguagem de máquina de registradores. Como alternativa para salvar apenas o necessário, poderíamos salvar todos os registradores (exceto <tt>val</tt>) antes de cada chamada recursiva. Isso é chamado de disciplina de <a name="%_idx_6052" id="%_idx_6052"/><a name="%_idx_6054" id="%_idx_6054"/><em>pilha-quadro</em>. Isso funcionaria, mas poderia economizar mais registradores do que o necessário; isso pode ser uma consideração importante em um sistema em que as operações de pilha são caras. Salvar registradores cujo conteúdo não será necessário posteriormente também pode conter dados inúteis que poderiam ser coletados no lixo, liberando espaço para reutilização.</p><p><a name="footnote_Temp_771" href="#call_footnote_Temp_771" id="footnote_Temp_771"><sup><small>22</small></sup></a> Adicionamos aos procedimentos de estrutura de dados do avaliador na seção <a href="book-Z-H-26.html#%_sec_4.1.3">4.1.3</a> os dois procedimentos a seguir para manipular listas de argumentos:</p><p/><p><tt><a name="%_idx_6060" id="%_idx_6060"/>(define (empty-arglist) '())<br/><br/><a name="%_idx_6062" id="%_idx_6062"/>(define (adjoin-arg arg arglist)<br/>
(append arglist (list arg)))<br/></tt></p><p/><p>Também usamos um procedimento de sintaxe adicional para testar o último operando em uma combinação:</p><p/><p><tt><a name="%_idx_6064" id="%_idx_6064"/>(define (last-operand? ops)<br/>
(null? (cdr ops)))<br/></tt></p><p/><p>
</p><p><a name="footnote_Temp_772" href="#call_footnote_Temp_772" id="footnote_Temp_772"><sup><small>23</small></sup></a> A otimização do tratamento do último operando <a name="%_idx_6066" id="%_idx_6066"/>especialmente é conhecido como <i>recursão de cauda de evlis</i> (veja <a name="%_idx_6068" id="%_idx_6068"/>Wand 1980). Poderíamos ser um pouco mais eficientes no ciclo de avaliação de argumentos se tornarmos a avaliação do primeiro operando um caso especial também. Isso nos permitiria adiar a iniciação <tt>argl</tt> até depois de avaliar o primeiro operando, para evitar salvar <tt>argl</tt> nesse caso. O compilador na seção <a href="book-Z-H-35.html#%_sec_5.5">5.5</a> realiza essa otimização. (Compare o procedimento <tt>construct-arglist</tt> de seção <a href="book-Z-H-35.html#%_sec_5.5.3">5.5.3</a>).</p><p><a name="footnote_Temp_773" href="#call_footnote_Temp_773" id="footnote_Temp_773"><sup><small>24</small></sup></a> A ordem de avaliação do operando no avaliador metacircular é determinada pela ordem de avaliação dos argumentos para <tt>cons</tt> no procedimento <tt>list-of-values</tt> da seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> (veja exercício <a href="book-Z-H-26.html#%_thm_4.1">4.1</a>)</p><p><a name="footnote_Temp_776" href="#call_footnote_Temp_776" id="footnote_Temp_776"><sup><small>25</small></sup></a> Vimos na seção <a href="book-Z-H-31.html#%_sec_5.1">5.1</a> como implementar esse processo com uma máquina de registradores que não possuía pilha; o estado do processo foi armazenado em um conjunto fixo de registradores.</p><p><a name="footnote_Temp_777" href="#call_footnote_Temp_777" id="footnote_Temp_777"><sup><small>26</small></sup></a> Esta implementação da recursão de cauda em <tt>ev-sequence</tt> é uma variedade de uma técnica de otimização conhecida usada por muitos compiladores. Ao compilar um procedimento que termina com uma chamada de procedimento, é possível substituir a chamada por um salto para o ponto de entrada do procedimento chamado. A criação dessa estratégia no interpretador, como fizemos nesta seção, fornece a otimização de maneira uniforme em todo a linguagem.</p><p><a name="footnote_Temp_778" href="#call_footnote_Temp_778" id="footnote_Temp_778"><sup><small>27</small></sup></a> Podemos definir <tt>no-more-exps?</tt> do seguinte modo:</p><p/><p><tt><a name="%_idx_6098" id="%_idx_6098"/>(define (no-more-exps? seq) (null? seq))<br/></tt></p><p/><p>
</p><p><a name="footnote_Temp_781" href="#call_footnote_Temp_781" id="footnote_Temp_781"><sup><small>28</small></sup></a> Isso não é realmente uma trapaça. Em uma implementação real criada do zero, usaríamos nosso avaliador de controle explícito para interpretar um programa Scheme que executa transformações no nível da fonte, como <tt>cond->if</tt> em uma fase de sintaxe que é executada antes da execução.</p><p><a name="footnote_Temp_784" href="#call_footnote_Temp_784" id="footnote_Temp_784"><sup><small>29</small></sup></a> Assumimos aqui que <tt>read</tt> e as várias operações de impressão estão disponíveis como operações primitivas da máquina, o que é útil para a nossa simulação, mas completamente irreal na prática. Na verdade, essas são operações extremamente complexas. Na prática, elas seriam implementadas usando operações de baixo nível de entrada e saída, como a transferência de caracteres únicos de e para um dispositivo.</p><p>Para apoiar a operação <tt>get-global-environment</tt> que definimos</p><p/><p><tt><a name="%_idx_6138" id="%_idx_6138"/>(define the-global-environment (setup-environment))<br/><br/><a name="%_idx_6140" id="%_idx_6140"/>(define (get-global-environment)<br/>
the-global-environment)<br/></tt></p><p/><p>
</p><p><a name="footnote_Temp_785" href="#call_footnote_Temp_785" id="footnote_Temp_785"><sup><small>30</small></sup></a> Há outros erros que gostaríamos que o interpretador resolvesse, mas esses não são tão simples. Veja o exercício <a href="#%_thm_5.30">5.30</a>.</p><p><a name="footnote_Temp_786" href="#call_footnote_Temp_786" id="footnote_Temp_786"><sup><small>31</small></sup></a> Poderíamos executar a iniciação da pilha somente após erros, mas fazê-lo no laço do controlador será conveniente para monitorar o desempenho do avaliador, conforme descrito abaixo.</p><p><a name="footnote_Temp_793" href="#call_footnote_Temp_793" id="footnote_Temp_793"><sup><small>32</small></sup></a> Lamentavelmente, este é o estado normal em <a name="%_idx_6186" id="%_idx_6186"/>sistemas de linguagem convencionais baseados em compilador, como C. <a name="%_idx_6188" id="%_idx_6188"/><a name="%_idx_6190" id="%_idx_6190"/><a name="%_idx_6192" id="%_idx_6192"/>No UNIX<sup><em>T</em><em>M</em></sup> o sistema “despeja a memória” e no DOS/Windows<sup><em>T</em><em>M</em></sup> torna-se catatônico. O Macintosh<sup><em>T</em><em>M</em></sup> exibe uma foto de uma bomba explodindo e oferece a oportunidade de reiniciar o computador – se você tiver sorte.</p></div>
</body>
</html>