-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbook-Z-H-35.html
More file actions
910 lines (737 loc) · 136 KB
/
book-Z-H-35.html
File metadata and controls
910 lines (737 loc) · 136 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
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
<?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.5" id="%_sec_5.5"/>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_5.5">5.5 Compilação</a></h2><p>
<a name="%_idx_6194" id="%_idx_6194"/>O avaliador de controle explícito da seção <a href="book-Z-H-34.html#%_sec_5.4">5.4</a> é uma máquina de registradores cujo controlador interpreta os programas do Scheme. Nesta seção, veremos como executar os programas do Scheme em uma máquina de registradores cujo controlador não é um interpretador do Scheme.</p><p>
<a name="%_idx_6196" id="%_idx_6196"/><a name="%_idx_6198" id="%_idx_6198"/>A máquina do avaliador de controle explícito é universal – ela pode executar qualquer processo computacional que possa ser descrito em Scheme. O controlador do avaliador orquestra o uso de seus caminhos de dados para executar o cálculo desejado. Assim, os caminhos de dados do avaliador são universais: são suficientes para executar qualquer cálculo que desejamos, considerando um controlador apropriado.<a name="call_footnote_Temp_794" href="#footnote_Temp_794" id="call_footnote_Temp_794"><sup><small>33</small></sup></a></p><p>
<a name="%_idx_6200" id="%_idx_6200"/><a name="%_idx_6202" id="%_idx_6202"/>Os computadores comerciais de uso geral são máquinas de registradores organizadas em torno de uma coleção de registradores e operações que constituem um conjunto universal de caminhos de dados eficiente e conveniente. O controlador de uma máquina de uso geral é um interpretador para uma linguagem de máquina de registradores como a que estamos usando. Essa linguagem é chamada de <a name="%_idx_6204" id="%_idx_6204"/><em>linguagem nativa</em> da máquina, ou simplesmente <a name="%_idx_6206" id="%_idx_6206"/><em>linguagem de máquina</em>. Programas escritos em linguagem de máquina são sequências de instruções que usam os caminhos de dados da máquina. Por exemplo, <a name="%_idx_6208" id="%_idx_6208"/>a sequência de instruções do avaliador de controle explícito pode ser vista como um programa de linguagem de máquina para um computador de uso geral, e não como o controlador de uma máquina de interpretador especializada.</p><p>
<a name="%_idx_6210" id="%_idx_6210"/><a name="%_idx_6212" id="%_idx_6212"/>Existem duas estratégias comuns para preencher a lacuna entre linguagens de nível superior e linguagens de máquina de registradores. O avaliador de controle explícito ilustra a estratégia de interpretação. Um interpretador escrito na linguagem nativa de uma máquina configura a máquina para executar programas gravados em uma linguagem(chamada de <a name="%_idx_6214" id="%_idx_6214"/><em>linguagem de origem</em>) que podem diferir da linguagem nativa da máquina que executa a avaliação. Os procedimentos primitivos da linguagem de origem são implementados como uma biblioteca de sub-rotinas escritas na linguagem nativa da máquina especificada. Um programa a ser interpretado (chamado de <a name="%_idx_6216" id="%_idx_6216"/><em>programa de origem</em>) é representado como uma estrutura de dados. O interpretador percorre essa estrutura de dados, analisando o programa de origem. Ao fazer isso, ele simula o comportamento pretendido do programa de origem chamando sub-rotinas primitivas apropriadas da biblioteca.</p><p>Nesta seção, exploramos a estratégia alternativa de <em>compilação</em>. Um compilador para uma determinada linguagem de origem e máquina converte um programa de origem em um programa equivalente (chamado de <a name="%_idx_6218" id="%_idx_6218"/><em>programa objeto</em>) escrito na linguagem nativa da máquina. O compilador que implementamos nesta seção converte programas escritos em Scheme em sequências de instruções a serem executadas usando os caminhos de dados da máquina do avaliador de controle explícito.<a name="call_footnote_Temp_795" href="#footnote_Temp_795" id="call_footnote_Temp_795"><sup><small>34</small></sup></a></p><p>Comparado com a interpretação, a compilação pode fornecer um grande aumento na eficiência da execução do programa, como explicaremos abaixo na visão geral do compilador. Por outro lado, um interpretador fornece um ambiente mais poderoso para o desenvolvimento e a depuração do programa interativo, pois o programa de origem que é executado está disponível no tempo de execução para ser examinado e modificado. Além disso, como toda a biblioteca de primitivas está presente, novos programas podem ser construídos e adicionados ao sistema durante a depuração.</p><p>Em vista das vantagens complementares da compilação e interpretação, os ambientes modernos de desenvolvimento de programas buscam uma estratégia mista. Os interpretadores Lisp geralmente são organizados para que procedimentos interpretados e procedimentos compilados possam se chamar. Isso permite que um programador compile as partes de um programa que se supõe serem depuradas, obtendo assim a vantagem de eficiência da compilação, mantendo o modo interpretativo de execução para as partes do programa que estão no fluxo de desenvolvimento e depuração interativos. Na seção <a href="#%_sec_5.5.7">5.5.7</a>, depois de implementar o compilador, mostraremos como fazer a interface com nosso interpretador para produzir um sistema integrado de desenvolvimento de interpretador-compilador.</p><p>
<a name="%_sec_Temp_796" id="%_sec_Temp_796"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_796">Uma visão geral do compilador</a></h4><p>
<a name="%_idx_6224" id="%_idx_6224"/><a name="%_idx_6226" id="%_idx_6226"/>Nosso compilador é muito parecido com o nosso interpretador, tanto em sua estrutura quanto na função que ele executa. Portanto, os mecanismos usados pelo compilador para analisar expressões serão semelhantes aos usados pelo interpretador. Além disso, para facilitar a interface de código compilado e interpretado, projetaremos o compilador para gerar código que obedeça às mesmas convenções de <a name="%_idx_6228" id="%_idx_6228"/>uso de registradores como interpretador: O ambiente será mantido no registrador <tt>env</tt>, listas de argumentos serão acumuladas em <tt>argl</tt>, um procedimento a ser aplicado estará em <tt>proc</tt>, os procedimentos retornarão suas respostas em <tt>val</tt>, e o local para o qual um procedimento deve retornar será mantido em <tt>continue</tt>. Em geral, o compilador converte um programa de origem em um programa de objeto que executa essencialmente as mesmas operações de registrador que faria o interpretador na avaliação do mesmo programa de origem.</p><p>Esta descrição sugere uma estratégia para implementar um compilador rudimentar: Atravessamos a expressão da mesma maneira que o interpretador. Quando encontramos uma instrução de registrador que o interpretador executaria ao avaliar a expressão, não executamos a instrução, mas a acumulamos em uma sequência. A sequência resultante de instruções será o código do objeto. Observe a <a name="%_idx_6230" id="%_idx_6230"/><a name="%_idx_6232" id="%_idx_6232"/>vantagem de eficiência da compilação sobre a interpretação. Sempre que o interpretador avalia uma expressão – por exemplo, <tt>(f 84 96)</tt> – executa o trabalho de classificar a expressão (descobrindo que este é uma aplicação de procedimento) e testando o final da lista de operandos (descobrindo que existem dois operandos). Com um compilador, a expressão é analisada apenas uma vez, quando a sequência de instruções é gerada no tempo de compilação. O código do objeto produzido pelo compilador contém apenas as instruções que avaliam o operador e os dois operandos, montam a lista de argumentos e aplicam o procedimento (em <tt>proc</tt>) aos argumentos (em <tt>argl</tt>)</p><p>
<a name="%_idx_6234" id="%_idx_6234"/>Esse é o mesmo tipo de otimização que implementamos no avaliador de análise da seção <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>. Mas existem outras oportunidades para obter eficiência no código compilado. À medida que o interpretador é executado, segue um processo que deve ser aplicável a qualquer expressão na linguagem. Por outro lado, um determinado segmento de código compilado deve executar uma expressão específica. Isso pode fazer uma grande diferença, por exemplo, no uso da pilha para salvar registradores. Quando o interpretador avalia uma expressão, ela deve estar preparada para qualquer contingência. Antes de avaliar uma subexpressão, o interpretador salva todos os registradores necessários posteriormente, pois a subexpressão pode exigir uma avaliação arbitrária. Um compilador, por outro lado, pode explorar a estrutura da expressão específica que está processando para gerar código que evita operações desnecessárias de pilha.</p><p>Como exemplo, considere a combinação <tt>(f 84 96)</tt>. Antes de o interpretador avaliar o operador da combinação, ele se prepara para essa avaliação salvando os registradores que contêm os operandos e o ambiente, cujos valores serão necessários posteriormente. O interpretador avalia o operador para obter o resultado em <tt>val</tt>, restaura os registradores salvos e, finalmente, move o resultado de <tt>val</tt> para <tt>proc</tt>. No entanto, na expressão específica com a qual estamos lidando, o operador é o símbolo <tt>f</tt>, cuja avaliação é realizada pela operação da máquina <tt>lookup-variable-value</tt>, que não altera nenhum registrador. O compilador que implementamos nesta seção aproveitará esse fato e gerará código que avalia o operador usando a instrução</p><p/><p><tt>(atribui proc (op-lookup-variable-value) (const f) (reg env))<br/></tt></p><p/><p>Esse código não apenas evita salvamentos e restaurações desnecessários, mas também atribui o valor da pesquisa diretamente a <tt>proc</tt>, enquanto o interpretador obteria o resultado em <tt>val</tt> e depois mova isso para <tt>proc</tt>.</p><p>Um compilador também pode otimizar o acesso ao ambiente. Após analisar o código, o compilador pode, em muitos casos, saber em qual quadro uma determinada variável será localizada e acessar diretamente esse quadro, em vez de executar o <tt>lookup-variable-value</tt> procurar. Discutiremos como implementar esse acesso variável na seção <a href="#%_sec_5.5.6">5.5.6</a>. Até lá, no entanto, focaremos no tipo de otimização de registradores e empilhamento descrito acima. Existem muitas outras otimizações que podem ser executadas por um compilador, como codificar operações primitivas “in line” em vez de usar um método geral. O mecanismo <tt>apply</tt> (ver exercício <a href="#%_thm_5.38">5.38</a>); mas não enfatizaremos isso aqui. Nosso principal objetivo nesta seção é ilustrar o processo de compilação em um contexto simplificado (mas ainda interessante).</p><p>
<a name="%_sec_5.5.1" id="%_sec_5.5.1"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.1">5.5.1 Estrutura do compilador</a></h3><p>
<a name="%_idx_6236" id="%_idx_6236"/>
<a name="%_idx_6238" id="%_idx_6238"/>Na seção <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a> modificamos nosso interpretador metacircular original para separar a análise da execução. Analisamos cada expressão para produzir um procedimento de execução que utilizou um ambiente como argumento e executou as operações necessárias. Em nosso compilador, faremos essencialmente a mesma análise. Em vez de produzir procedimentos de execução, no entanto, geraremos sequências de instruções a serem executadas pela nossa máquina de registradores.</p><p>O procedimento <tt>compile</tt> é o despacho de nível superior no compilador. Corresponde ao procedimento <tt>eval</tt> da seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>, o procedimento <tt>analyze</tt> da seção <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>, e o ponto de entrada <tt>eval-dispatch</tt> do avaliador de controle explícito na seção <a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>. O compilador, como os interpretadores, usa os <a name="%_idx_6240" id="%_idx_6240"/>procedimentos de sintaxe de expressão definidos na seção <a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a>.<a name="call_footnote_Temp_797" href="#footnote_Temp_797" id="call_footnote_Temp_797"><sup><small>35</small></sup></a><tt>Compile</tt> realiza uma análise de caso no tipo sintático da expressão a ser compilada. Para cada tipo de expressão, ele é despachado para um <a name="%_idx_6242" id="%_idx_6242"/><em>gerador de código</em> especializado:</p><p>
</p><p/><p><tt><a name="%_idx_6244" id="%_idx_6244"/>(define (compile exp target linkage)<br/>
(cond ((self-evaluating? exp)<br/>
(compile-self-evaluating exp target linkage))<br/>
((quoted? exp) (compile-quoted exp target linkage))<br/>
((variable? exp)<br/>
(compile-variable exp target linkage))<br/>
((assignment? exp)<br/>
(compile-assignment exp target linkage))<br/>
((definition? exp)<br/>
(compile-definition exp target linkage))<br/>
((if? exp) (compile-if exp target linkage))<br/>
((lambda? exp) (compile-lambda exp target linkage))<br/>
((begin? exp)<br/>
(compile-sequence (begin-actions exp)<br/>
target<br/>
linkage))<br/>
((cond? exp) (compile (cond->if exp) target linkage))<br/>
((application? exp)<br/>
(compile-application exp target linkage))<br/>
(else<br/>
(error "Unknown expression type -- COMPILE" exp))))<br/></tt></p><p/><p/><p>
<a name="%_sec_Temp_798" id="%_sec_Temp_798"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_798">Alvos e ligações</a></h4><p>
<a name="%_idx_6246" id="%_idx_6246"/><tt>Compile</tt> e os geradores de código que chama recebem dois argumentos, além da expressão para compilar. Existe um <a name="%_idx_6248" id="%_idx_6248"/><em>alvo</em>, que especifica o registrador no qual o código compilado deve retornar o valor da expressão. Há também um <a name="%_idx_6250" id="%_idx_6250"/><em>descritor de ligação</em>, que descreve como o código resultante da compilação da expressão deve prosseguir quando a execução for concluída. O descritor de ligação pode exigir que o código execute uma das três seguintes ações:</p><p>
</p><p/><ul><li>continue na próxima instrução em sequência (isto é <a name="%_idx_6252" id="%_idx_6252"/>especificado pelo descritor de ligação <tt>next</tt>),<p>
</p></li><li>retorno do procedimento que é compilado (isso é especificado <a name="%_idx_6254" id="%_idx_6254"/>pelo descritor de ligação <tt>return</tt>) ou<p>
</p></li><li>pule para um ponto de entrada nomeado (isso é especificado usando o rótulo designado como o descritor de ligação).</li></ul><p/><p>Por exemplo, compilando a expressão <tt>5</tt> (que é auto-avaliada) com um alvo do registrador <tt>val</tt> e uma ligação de <tt>next</tt> deve produzir a instrução</p><p>
</p><p/><p><tt>(assign val (const 5))<br/></tt></p><p/><p>Compilar a mesma expressão com uma ligação de <tt>return</tt> deve produzir as instruções</p><p>
</p><p/><p><tt>(assign val (const 5))<br/>
(goto (reg continue))<br/></tt></p><p/><p>No primeiro caso, a execução continuará com a próxima instrução na sequência. No segundo caso, retornaremos de uma chamada de procedimento. Nos dois casos, o valor da expressão será colocado no registrador alvo <tt>val</tt>.</p><p>
<a name="%_sec_Temp_799" id="%_sec_Temp_799"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_799">Sequências de instruções e uso da pilha</a></h4><p>
</p><p>
<a name="%_idx_6256" id="%_idx_6256"/><a name="%_idx_6258" id="%_idx_6258"/>Cada gerador de código retorna uma <em>sequência de instruções</em> contendo o código do objeto que ele gerou para a expressão. A geração de código para uma expressão composta é realizada combinando a saída de geradores de código mais simples para expressões de componentes, assim como a avaliação de uma expressão composta é realizada avaliando as expressões de componentes.</p><p>O método mais simples para combinar sequências de instruções é um procedimento <a name="%_idx_6260" id="%_idx_6260"/>chamado <tt>append-instruction-sequences</tt>. Toma como argumento qualquer número de sequências de instruções que devem ser executadas sequencialmente; anexa-os e retorna a sequência combinada. Ou seja, se <<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>> e <<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>> são sequências de instruções e depois avaliam</p><p/><p><tt>(append-instruction-sequences <<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>> <<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>>)<br/></tt></p><p/><p>produz a sequência</p><p/><p><tt><<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>><br/>
<<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>><br/></tt></p><p/><p/><p>
<a name="%_idx_6262" id="%_idx_6262"/>Sempre que os registradores precisarem ser salvos, os geradores de código do compilador usam <a name="%_idx_6264" id="%_idx_6264"/><tt>preserving</tt>, que é um método mais sutil para combinar sequências de instruções. <tt>Preserving</tt> usa três argumentos: um conjunto de registradores e duas sequências de instruções que devem ser executadas sequencialmente. Ele anexa as sequências de forma que o conteúdo de cada registrador no conjunto seja preservado durante a execução da primeira sequência, se isso for necessário para a execução da segunda sequência. Ou seja, se a primeira sequência modifica o registrador e a segunda sequência realmente precisa do conteúdo original do registrador, <tt>preserving</tt> envolve um <tt>save</tt> e um <tt>restore</tt> do registrador em torno da primeira sequência antes de anexá-las. De outra forma, <tt>preserving</tt> simplesmente retorna as sequências de instruções anexadas. Assim, por exemplo,</p><p/><p><tt>(preserving (list <<em><em>r</em><em>e</em><em>g</em><sub>1</sub></em>> <<em><em>r</em><em>e</em><em>g</em><sub>2</sub></em>>) <<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>> <<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>>)<br/></tt></p><p/><p>produz uma das quatro sequências de instruções a seguir, dependendo de como <<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>> e <<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>> use <<em><em>r</em><em>e</em><em>g</em><sub>1</sub></em>> e <<em><em>r</em><em>e</em><em>g</em><sub>2</sub></em>>:</p><p>
</p><p/><p/><p/><div align="left"><img src="images/ch5-Z-G-9.gif" border="0"/></div><p/><p>Usando <tt>preserving</tt> para combinar sequências de instruções, o compilador evita operações desnecessárias de pilha. Isso também isola os detalhes de gerar ou não instruções <tt>save</tt> e <tt>restore</tt> dentro do <tt>preserving</tt>, separando-os das preocupações que surgem ao escrever cada um dos geradores de código individuais. De fato nenhuma instrução <tt>save</tt> ou <tt>restore</tt> é produzida explicitamente pelos geradores de código.</p><p>Em princípio, poderíamos representar uma sequência de instruções simplesmente como uma lista de instruções. <tt>Append-instruction-sequences</tt> poderia então combinar sequências de instruções executando uma lista comum <tt>append</tt>. Contudo, <tt>preserving</tt> seria então uma operação complexa, pois teria que analisar cada sequência de instruções para determinar como a sequência usa seus registradores. <tt>Preserving</tt> seria ineficiente e complexo, pois teria que analisar cada um de seus argumentos de sequência de instruções, mesmo que essas sequências possam ter sido construídas por chamadas para <tt>preserving</tt>, caso em que suas partes já teriam sido analisadas. Para evitar essa análise repetitiva, associaremos a cada sequência de instruções algumas informações sobre o uso do registrador. Quando construímos uma sequência de instruções básica, fornecemos essas informações explicitamente, e os procedimentos que combinam sequências de instruções derivam informações de uso de registrador para a sequência combinada a partir das informações associadas às sequências de componentes.</p><p>Uma sequência de instruções conterá três informações:</p><p/><ul><li>o conjunto de registradores que deve ser iniciado antes que as instruções na sequência sejam executadas (esses registradores são considerados <em>necessários</em> pela sequência),<p>
</p></li><li>o conjunto de registradores cujos valores são modificados pelas instruções na sequência e<p>
</p></li><li>as instruções reais (também chamadas <em>afirmações</em>) na sequência.</li></ul><p/><p>Representaremos uma sequência de instruções como uma lista de suas três partes. O construtor para sequências de instruções é assim</p><p>
</p><p/><p><tt><a name="%_idx_6266" id="%_idx_6266"/>(define (make-instruction-sequence needs modifies statements)<br/>
(list needs modifies statements))<br/></tt></p><p/><p/><p>Por exemplo, a sequência de duas instruções que pesquisa o valor da variável <tt>x</tt> no ambiente atual, atribui o resultado a <tt>val</tt> e, em seguida, retorna, requer registradores <tt>env</tt> e <tt>continue</tt> iniciado e modifica o registrador <tt>val</tt>. Esta sequência seria, portanto, construída como</p><p>
</p><p/><p><tt>(make-instruction-sequence '(env continue) '(val)<br/>
'((assign val<br/>
(op lookup-variable-value) (const x) (reg env))<br/>
(goto (reg continue))))<br/></tt></p><p/><p/><p>Às vezes, precisamos construir uma sequência de instruções sem instruções:</p><p/><p><tt><a name="%_idx_6268" id="%_idx_6268"/>(define (empty-instruction-sequence)<br/>
(make-instruction-sequence '() '() '()))<br/></tt></p><p/><p>
</p><p>Os procedimentos para combinar sequências de instruções são mostrados na seção <a href="#%_sec_5.5.4">5.5.4</a>.</p><p>
</p><p><a name="%_thm_5.31" id="%_thm_5.31"/>
<b>Exercício 5.31.</b> <a name="%_idx_6270" id="%_idx_6270"/><a name="%_idx_6272" id="%_idx_6272"/>Ao avaliar uma aplicação de procedimento, o avaliador de controle explícito sempre salva e restaura o registrador <tt>env</tt> em torno da avaliação do operador, salva e restaura <tt>env</tt> em torno da avaliação de cada operando (exceto o final), salva e restaura <tt>argl</tt> em torno da avaliação de cada operando e salva e restaura <tt>proc</tt> em torno da avaliação da sequência do operando. Para cada uma das seguintes combinações, diga qual dessas operações <tt>save</tt> e <tt>restore</tt> são supérfluas e, portanto, poderiam ser eliminadas pelo mecanismo <tt>preserving</tt> do compilador:</p><p>
</p><p/><p><tt>(f 'x 'y)<br/><br/>
((f) 'x 'y)<br/><br/>
(f (g 'x) y)<br/><br/>
(f (g 'x) 'y)<br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_5.32" id="%_thm_5.32"/>
<b>Exercício 5.32.</b> <a name="%_idx_6274" id="%_idx_6274"/><a name="%_idx_6276" id="%_idx_6276"/>Usando o mecanismo <tt>preserving</tt>, o compilador evitará salvar e restaurar <tt>env</tt> em torno da avaliação do operador de uma combinação no caso em que o operador é um símbolo. Também poderíamos incorporar essas otimizações no avaliador. De fato, o avaliador de controle explícito da seção <a href="book-Z-H-34.html#%_sec_5.4">5.4</a> já realiza uma otimização semelhante, tratando combinações sem operandos como um caso especial.</p><p>
</p><p/><p>a. Estenda o avaliador de controle explícito para reconhecer como uma classe separada de combinações de expressões cujo operador é um símbolo e aproveitar esse fato na avaliação de tais expressões.</p><p>
</p><p/><p>b. Alyssa P. Hacker sugere que, estendendo o avaliador para reconhecer casos cada vez mais especiais, poderíamos incorporar todas as otimizações do compilador e isso eliminaria completamente a vantagem da compilação. O que você pensa dessa ideia?</p><p/><p>
<a name="%_sec_5.5.2" id="%_sec_5.5.2"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.2">5.5.2 Compilando expressões</a></h3><p>Nesta seção e na próxima, implementamos os geradores de código nos quais o <tt>compile</tt> despachos de procedimento.</p><p>
<a name="%_sec_Temp_802" id="%_sec_Temp_802"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_802">Compilando Código de Ligação</a></h4><p>
<a name="%_idx_6278" id="%_idx_6278"/>Em geral, a saída de cada gerador de código termina com instruções – geradas pelo procedimento <tt>compile-linkage</tt> – que implementem a ligação necessária. Se a ligação for <tt>return</tt> então devemos gerar a instrução <tt>(goto (reg continue))</tt>. Isso precisa do registrador <tt>continue</tt> e não modifica nenhum registrador. Se a ligação for <tt>next</tt>, não precisamos incluir instruções adicionais. Caso contrário, a ligação é um rótulo e geramos um <tt>goto</tt> para esse rótulo, uma instrução que não precisa nem modifica nenhum registrador.<a name="call_footnote_Temp_803" href="#footnote_Temp_803" id="call_footnote_Temp_803"><sup><small>36</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_6292" id="%_idx_6292"/>(define (compile-linkage linkage)<br/>
(cond ((eq? linkage 'return)<br/>
(make-instruction-sequence '(continue) '()<br/>
'((goto (reg continue)))))<br/>
((eq? linkage 'next)<br/>
(empty-instruction-sequence))<br/>
(else<br/>
(make-instruction-sequence '() '()<br/>
`((goto (label ,linkage)))))))<br/></tt></p><p/><p>O código de ligação é anexado a uma sequência de instruções pelo uso de <tt>preserving</tt> no registrador <tt>continue</tt>, uma vez que <tt>return</tt> ligação exigirá o registrador <tt>continue</tt>: Se a sequência de instruções especificada modificar <tt>continue</tt> e o código de ligação precisa, <tt>continue</tt> será salvo e restaurado.</p><p>
</p><p/><p><tt><a name="%_idx_6294" id="%_idx_6294"/>(define (end-with-linkage linkage instruction-sequence)<br/>
(preserving '(continue)<br/>
instruction-sequence<br/>
(compile-linkage linkage)))<br/></tt></p><p/><p/><p>
</p><p>
<a name="%_sec_Temp_804" id="%_sec_Temp_804"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_804">Compilando expressões simples</a></h4><p>
<a name="%_idx_6296" id="%_idx_6296"/><a name="%_idx_6298" id="%_idx_6298"/><a name="%_idx_6300" id="%_idx_6300"/>Os geradores de código para expressões, cotações e variáveis de auto-avaliação constroem sequências de instruções que atribuem o valor necessário ao registrador de destino e, em seguida, prosseguem conforme especificado pelo descritor de ligação.</p><p>
</p><p/><p><tt><a name="%_idx_6302" id="%_idx_6302"/>(define (compile-self-evaluating exp target linkage)<br/>
(end-with-linkage linkage<br/>
(make-instruction-sequence '() (list target)<br/>
`((assign ,target (const ,exp))))))<br/><a name="%_idx_6304" id="%_idx_6304"/>(define (compile-quoted exp target linkage)<br/>
(end-with-linkage linkage<br/>
(make-instruction-sequence '() (list target)<br/>
`((assign ,target (const ,(text-of-quotation exp)))))))<br/><a name="%_idx_6306" id="%_idx_6306"/>(define (compile-variable exp target linkage)<br/>
(end-with-linkage linkage<br/>
(make-instruction-sequence '(env) (list target)<br/>
`((assign ,target<br/>
(op lookup-variable-value)<br/>
(const ,exp)<br/>
(reg env))))))<br/></tt></p><p/><p>Todas essas instruções de atribuição modificam o registrador de destino e aquele que procura uma variável precisa do registrador <tt>env</tt>.</p><p>
<a name="%_idx_6308" id="%_idx_6308"/><a name="%_idx_6310" id="%_idx_6310"/>As atribuições e definições são tratadas da mesma forma que no interpretador. Geramos recursivamente um código que calcula o valor a ser atribuído à variável e anexamos a ela uma sequência de duas instruções que realmente define ou define a variável e atribui o valor de toda a expressão (o símbolo <tt>ok</tt>) para o registrador de destino. A compilação recursiva possui o alvo <tt>val</tt> e ligação <tt>next</tt> para que o código coloque seu resultado em <tt>val</tt> e continue com o código que é anexado depois dele. O anexo é feito preservando <tt>env</tt>, uma vez que o ambiente é necessário para definir ou definir a variável e o código para o valor da variável pode ser a compilação de uma expressão complexa que pode modificar os registradores de maneira arbitrária.</p><p>
</p><p/><p><tt><a name="%_idx_6312" id="%_idx_6312"/>(define (compile-assignment exp target linkage)<br/>
(let ((var (assignment-variable exp))<br/>
(get-value-code<br/>
(compile (assignment-value exp) 'val 'next)))<br/>
(end-with-linkage linkage<br/>
(preserving '(env)<br/>
get-value-code<br/>
(make-instruction-sequence '(env val) (list target)<br/>
`((perform (op set-variable-value!)<br/>
(const ,var)<br/>
(reg val)<br/>
(reg env))<br/>
(assign ,target (const ok))))))))<br/><a name="%_idx_6314" id="%_idx_6314"/>(define (compile-definition exp target linkage)<br/>
(let ((var (definition-variable exp))<br/>
(get-value-code<br/>
(compile (definition-value exp) 'val 'next)))<br/>
(end-with-linkage linkage<br/>
(preserving '(env)<br/>
get-value-code<br/>
(make-instruction-sequence '(env val) (list target)<br/>
`((perform (op define-variable!)<br/>
(const ,var)<br/>
(reg val)<br/>
(reg env))<br/>
(assign ,target (const ok))))))))<br/></tt></p><p/><p>A sequência de duas instruções em anexo requer <tt>env</tt> e <tt>val</tt> e modifica o alvo. Observe que, embora preservemos <tt>env</tt> para esta sequência, não preservamos <tt>val</tt>, pois o <tt>get-value-code</tt> foi projetado para colocar explicitamente seu resultado em <tt>val</tt> para uso por esta sequência. (De fato, se preservássemos <tt>val</tt>, teríamos um erro, pois isso causaria o conteúdo anterior de <tt>val</tt> para ser restaurado logo após o <tt>get-value-code</tt> é executado).</p><p>
<a name="%_sec_Temp_805" id="%_sec_Temp_805"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_805">Compilando expressões condicionais</a></h4><p>
<a name="%_idx_6316" id="%_idx_6316"/>O código para uma expressão <tt>if</tt> compilada com um determinado alvo e ligação possui a forma</p><p>
</p><p/><p><tt> <<em>compilation of predicate, target <tt>val</tt>, linkage <tt>next</tt></em>><br/>
(test (op false?) (reg val))<br/>
(branch (label false-branch))<br/>
true-branch<br/>
<<em>compilation of consequent with given target and given linkage or <tt>after-if</tt></em>><br/>
false-branch<br/>
<<em>compilation of alternative with given target and linkage</em>><br/>
after-if<br/></tt></p><p/><p/><p>Para gerar esse código, compilamos o predicado, consequente e alternativo, e combinamos o código resultante com instruções para testar o resultado do predicado e com rótulos recém-gerados para marcar as ramificações verdadeiras e falsas e o final da condicional.<a name="call_footnote_Temp_806" href="#footnote_Temp_806" id="call_footnote_Temp_806"><sup><small>37</small></sup></a> Nesse arranjo de código, devemos ramificar o ramo verdadeiro se o teste for falso. A única complicação ligeira está em como a ligação para o ramo verdadeiro deve ser tratada. Se a ligação para o condicional for <tt>return</tt> ou um rótulo, os ramos verdadeiro e falso usarão o mesmo vínculo. Se a ligação for <tt>next</tt>, a ramificação verdadeira termina com um salto ao redor do código da ramificação falsa para o rótulo no final da condicional.</p><p>
</p><p/><p><tt><a name="%_idx_6324" id="%_idx_6324"/>(define (compile-if exp target linkage)<br/>
(let ((t-branch (make-label 'true-branch))<br/>
(f-branch (make-label 'false-branch)) <br/>
(after-if (make-label 'after-if)))<br/>
(let ((consequent-linkage<br/>
(if (eq? linkage 'next) after-if linkage)))<br/>
(let ((p-code (compile (if-predicate exp) 'val 'next))<br/>
(c-code<br/>
(compile<br/>
(if-consequent exp) target consequent-linkage))<br/>
(a-code<br/>
(compile (if-alternative exp) target linkage)))<br/>
(preserving '(env continue)<br/>
p-code<br/>
(append-instruction-sequences<br/>
(make-instruction-sequence '(val) '()<br/>
`((test (op false?) (reg val))<br/>
(branch (label ,f-branch))))<br/>
(parallel-instruction-sequences<br/>
(append-instruction-sequences t-branch c-code)<br/>
(append-instruction-sequences f-branch a-code))<br/>
after-if))))))<br/></tt></p><p/><p>
<tt>Env</tt> é preservado em torno do código de predicado, pois pode ser necessário pelas ramificações verdadeiro e falso e <tt>continue</tt> é preservado, pois poderia ser necessário pelo código de ligação nessas ramificações. O código para as ramificações verdadeiras e falsas (que não são executadas sequencialmente) é anexado usando um combinador especial <tt>parallel-instruction-sequences</tt> descrito na seção <a href="#%_sec_5.5.4">5.5.4</a>.</p><p>Observe que <tt>cond</tt> é uma expressão derivada; portanto, tudo o que o compilador precisa fazer para lidar com isso é aplicar o <tt>cond->if</tt> transformador (da seção <a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a>) e compilar o resultado da expressão <tt>if</tt>.</p><p>
<a name="%_sec_Temp_807" id="%_sec_Temp_807"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_807">Compilando sequências</a></h4><p>
<a name="%_idx_6326" id="%_idx_6326"/>A compilação de sequências (de corpos de procedimentos ou expressões <tt>begin</tt> explícitas) é paralelo à sua avaliação. Cada expressão da sequência é compilada – a última expressão com a ligação especificada para a sequência e as outras expressões com a ligação <tt>next</tt> (para executar o restante da sequência). As sequências de instruções para as expressões individuais são anexadas para formar uma única sequência de instruções, de modo que <tt>env</tt> (necessário para o resto da sequência) e <tt>continue</tt> (possivelmente necessário para a ligação no final da sequência) são preservados.</p><p>
</p><p/><p><tt><a name="%_idx_6328" id="%_idx_6328"/>(define (compile-sequence seq target linkage)<br/>
(if (last-exp? seq)<br/>
(compile (first-exp seq) target linkage)<br/>
(preserving '(env continue)<br/>
(compile (first-exp seq) target 'next)<br/>
(compile-sequence (rest-exps seq) target linkage))))<br/></tt></p><p/><p/><p>
<a name="%_sec_Temp_808" id="%_sec_Temp_808"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_808">Compilando expressões <tt>lambda</tt></a></h4><p>
<a name="%_idx_6330" id="%_idx_6330"/>Expressões <tt>lambda</tt> constroem procedimentos. O código do objeto para uma expressão <tt>lambda</tt> deve ter a forma</p><p>
</p><p/><p><tt><<em>construct procedure object and assign it to target register</em>><br/>
<<em>linkage</em>><br/></tt></p><p/><p>Quando compilamos a expressão <tt>lambda</tt>, também geramos o código para o corpo do procedimento. Embora o corpo não seja executado no momento da construção do procedimento, é conveniente inseri-lo no código do objeto logo após o código para o <tt>lambda</tt>. Se a ligação para a expressão <tt>lambda</tt> é um rótulo ou <tt>return</tt>, Isto é bom. Mas se a ligação for <tt>next</tt>, precisaremos ignorar o código do corpo do procedimento usando um link que salta para um rótulo que é inserido após o corpo. O código do objeto, portanto, possui a forma</p><p>
</p><p/><p><tt> <<em>construct procedure object and assign it to target register</em>><br/>
<<em>code for given linkage</em>><em>or</em> <tt>(goto (label after-lambda))</tt><br/>
<<em>compilation of procedure body</em>><br/>
after-lambda<br/></tt></p><p/><p/><p>
<tt>Compile-lambda</tt> gera o código para construir o objeto de procedimento seguido pelo código para o corpo do procedimento. O objeto de procedimento será construído em tempo de execução combinando o ambiente atual (o ambiente no ponto de definição) com o ponto de entrada no corpo do procedimento compilado (um rótulo recém-gerado).<a name="call_footnote_Temp_809" href="#footnote_Temp_809" id="call_footnote_Temp_809"><sup><small>38</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_6340" id="%_idx_6340"/>(define (compile-lambda exp target linkage)<br/>
(let ((proc-entry (make-label 'entry))<br/>
(after-lambda (make-label 'after-lambda)))<br/>
(let ((lambda-linkage<br/>
(if (eq? linkage 'next) after-lambda linkage)))<br/>
(append-instruction-sequences<br/>
(tack-on-instruction-sequence<br/>
(end-with-linkage lambda-linkage<br/>
(make-instruction-sequence '(env) (list target)<br/>
`((assign ,target<br/>
(op make-compiled-procedure)<br/>
(label ,proc-entry)<br/>
(reg env)))))<br/>
(compile-lambda-body exp proc-entry))<br/>
after-lambda))))<br/></tt></p><p/><p>
<tt>Compile-lambda</tt> usa o combinador especial <tt>tack-on-instruction-sequence</tt> (seção <a href="#%_sec_5.5.4">5.5.4</a>) em vez de <tt>append-instruction-sequences</tt> anexar o corpo do procedimento ao código <tt>lambda</tt> de expressão, pois o corpo não faz parte da sequência de instruções que serão executadas quando a sequência combinada for inserida; pelo contrário, está na sequência apenas, pois esse era um local conveniente para colocá-lo.</p><p>
<tt>Compile-lambda-body</tt> constrói o código para o corpo do procedimento. Este código começa com um rótulo para o ponto de entrada. Em seguida, vêm as instruções que farão com que o ambiente de avaliação em tempo de execução alterne para o ambiente correto para avaliar o corpo do procedimento – ou seja, o ambiente de definição do procedimento, estendido para incluir as ligações dos parâmetros formais aos argumentos com os quais o procedimento é realizado. chamado. Depois disso, vem o código para a sequência de expressões que compõe o corpo do procedimento. A sequência é compilada com ligação <tt>return</tt> e alvo <tt>val</tt> para que termine retornando do procedimento com o resultado do procedimento em <tt>val</tt>.</p><p>
</p><p/><p><tt>(define (compile-lambda-body exp proc-entry)<br/>
(let ((formals (lambda-parameters exp)))<br/>
(append-instruction-sequences<br/>
(make-instruction-sequence '(env proc argl) '(env)<br/>
`(,proc-entry<br/>
(assign env (op compiled-procedure-env) (reg proc))<br/>
(assign env<br/>
(op extend-environment)<br/>
(const ,formals)<br/>
(reg argl)<br/>
(reg env))))<br/>
(compile-sequence (lambda-body exp) 'val 'return))))<br/></tt></p><p/><p/><p>
<a name="%_sec_5.5.3" id="%_sec_5.5.3"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.3">5.5.3 Compilando combinações</a></h3><p>
<a name="%_idx_6342" id="%_idx_6342"/><a name="%_idx_6344" id="%_idx_6344"/>A essência do processo de compilação é a compilação de aplicação de procedimento. O código para uma combinação compilada com um determinado destino e ligação possui a forma</p><p/><p><tt><<em>compilation of operator, target <tt>proc</tt>, linkage <tt>next</tt></em>><br/>
<<em>evaluate operands and construct argument list in <tt>argl</tt></em>><br/>
<<em>compilation of procedure call with given target and linkage</em>><br/></tt></p><p/><p>Os registradores <tt>env</tt>, <tt>proc</tt> e <tt>argl</tt> pode ter que ser salvo e restaurado durante a avaliação do operador e operandos. Observe que este é o único local no compilador em que um destino diferente de <tt>val</tt> é especificado.</p><p>O código necessário é gerado por <tt>compile-application</tt>. Isso recursivamente compila o operador, para produzir código que coloca o procedimento a ser aplicado no <tt>proc</tt> e compila os operandos para produzir código que avalia os operandos individuais da aplicação. As sequências de instruções para os operandos são combinadas (por <tt>construct-arglist</tt>) com código que constrói a lista de argumentos em <tt>argl</tt>, e o código da lista de argumentos resultante é combinado com o código do procedimento e o código que executa a chamada do procedimento (produzido por <tt>compile-procedure-call</tt>) Ao anexar as sequências de código, o registrador <tt>env</tt> deve ser preservado em torno da avaliação do operador (uma vez que a avaliação do operador pode modificar <tt>env</tt>, o que será necessário para avaliar os operandos) e o registrador <tt>proc</tt> deve ser preservado em torno da construção da lista de argumentos (uma vez que a avaliação dos operandos pode modificar <tt>proc</tt>, que será necessário para a aplicação do procedimento real). <tt>Continue</tt> também deve ser preservado por toda parte, pois é necessário para a ligação na chamada de procedimento.</p><p>
</p><p/><p><tt><a name="%_idx_6346" id="%_idx_6346"/>(define (compile-application exp target linkage)<br/>
(let ((proc-code (compile (operator exp) 'proc 'next))<br/>
(operand-codes<br/>
(map (lambda (operand) (compile operand 'val 'next))<br/>
(operands exp))))<br/>
(preserving '(env continue)<br/>
proc-code<br/>
(preserving '(proc continue)<br/>
(construct-arglist operand-codes)<br/>
(compile-procedure-call target linkage)))))<br/></tt></p><p/><p/><p>O código para construir a lista de argumentos avaliará cada operando em <tt>val</tt> e depois <tt>cons</tt> esse valor na lista de argumentos sendo acumulado em <tt>argl</tt>. Desde que usamos <tt>cons</tt> nos argumentos para <tt>argl</tt> em sequência, devemos começar com o último argumento e terminar com o primeiro, para que os argumentos apareçam na ordem do primeiro ao último na lista resultante. Em vez de desperdiçar uma instrução iniciando <tt>argl</tt> para a lista vazia a ser configurada para essa sequência de avaliações, fazemos com que a primeira sequência de código construa a inicial <tt>argl</tt>. A forma geral da construção da lista de argumentos é assim:</p><p>
</p><p/><p><tt><<em>compilation of last operand, targeted to <tt>val</tt></em>><br/>
(assign argl (op list) (reg val))<br/>
<<em>compilation of next operand, targeted to <tt>val</tt></em>><br/>
(assign argl (op cons) (reg val) (reg argl))<br/><tt>...</tt><<em>compilation of first operand, targeted to <tt>val</tt></em>><br/>
(assign argl (op cons) (reg val) (reg argl))<br/></tt></p><p/><p>
<tt>Argl</tt> deve ser preservado em torno de cada avaliação de operando, exceto a primeira (para que os argumentos acumulados até agora não sejam perdidos) e <tt>env</tt> deve ser preservado em torno de cada avaliação de operando, exceto a última (para uso em avaliações subsequentes de operando).</p><p>Compilar esse código de argumento é um pouco complicado, devido ao tratamento especial do primeiro operando a ser avaliado e à necessidade de preservar <tt>argl</tt> e <tt>env</tt> em lugares diferentes. O procedimento <tt>construct-arglist</tt> leva como argumentos o código que avalia os operandos individuais. Se não houver operandos, simplesmente emitirá a instrução</p><p>
</p><p/><p><tt>(assign argl (const ()))<br/></tt></p><p/><p>De outra forma, <tt>construct-arglist</tt> cria código que inicia <tt>argl</tt> com o último argumento e anexa o código que avalia o restante dos argumentos e os anexa a <tt>argl</tt> em sucessão. Para processar os argumentos do último ao primeiro, devemos reverter a lista de sequências de código do operando da ordem fornecida por <tt>compile-application</tt>.</p><p>
</p><p/><p><tt><a name="%_idx_6348" id="%_idx_6348"/>(define (construct-arglist operand-codes)<br/>
(let ((operand-codes (reverse operand-codes)))<br/>
(if (null? operand-codes)<br/>
(make-instruction-sequence '() '(argl)<br/>
'((assign argl (const ()))))<br/>
(let ((code-to-get-last-arg<br/>
(append-instruction-sequences<br/>
(car operand-codes)<br/>
(make-instruction-sequence '(val) '(argl)<br/>
'((assign argl (op list) (reg val)))))))<br/>
(if (null? (cdr operand-codes))<br/>
code-to-get-last-arg<br/>
(preserving '(env)<br/>
code-to-get-last-arg<br/>
(code-to-get-rest-args<br/>
(cdr operand-codes))))))))<br/>
(define (code-to-get-rest-args operand-codes)<br/>
(let ((code-for-next-arg<br/>
(preserving '(argl)<br/>
(car operand-codes)<br/>
(make-instruction-sequence '(val argl) '(argl)<br/>
'((assign argl<br/>
(op cons) (reg val) (reg argl)))))))<br/>
(if (null? (cdr operand-codes))<br/>
code-for-next-arg<br/>
(preserving '(env)<br/>
code-for-next-arg<br/>
(code-to-get-rest-args (cdr operand-codes))))))<br/></tt></p><p/><p/><p>
<a name="%_sec_Temp_810" id="%_sec_Temp_810"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_810">Aplicando procedimentos</a></h4><p>Após avaliar os elementos de uma combinação, o código compilado deve aplicar o procedimento em <tt>proc</tt> para os argumentos em <tt>argl</tt>. O código executa essencialmente o mesmo envio que o procedimento <tt>apply</tt> no avaliador metacircular da seção <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> ou o ponto de entrada <tt>apply-dispatch</tt> no avaliador de controle explícito da seção <a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>. Ele verifica se o procedimento a ser aplicado é um procedimento primitivo ou um procedimento compilado. Para um procedimento primitivo, ele usa <tt>apply-primitive-procedure</tt>; veremos em breve como ele lida com procedimentos compilados. O código da aplicação de procedimento possui o seguinte formato:</p><p>
</p><p/><p><tt> (test (op primitive-procedure?) (reg proc))<br/>
(branch (label primitive-branch))<br/>
compiled-branch<br/>
<<em>code to apply compiled procedure with given target and appropriate linkage</em>><br/>
primitive-branch<br/>
(assign <<em>target</em>><br/>
(op apply-primitive-procedure)<br/>
(reg proc)<br/>
(reg argl))<br/>
<<em>linkage</em>><br/>
after-call<br/></tt></p><p/><p>Observe que o ramo compilado deve pular o ramo primitivo. Portanto, se a ligação para a chamada de procedimento original foi <tt>next</tt>, a ramificação composta deve usar uma ligação que salta para um rótulo que é inserido após a ramificação primitiva. (É semelhante ao vínculo usado para a ramificação verdadeira em <tt>compile-if</tt>).</p><p>
</p><p/><p><tt><a name="%_idx_6350" id="%_idx_6350"/>(define (compile-procedure-call target linkage)<br/>
(let ((primitive-branch (make-label 'primitive-branch))<br/>
(compiled-branch (make-label 'compiled-branch))<br/>
(after-call (make-label 'after-call)))<br/>
(let ((compiled-linkage<br/>
(if (eq? linkage 'next) after-call linkage)))<br/>
(append-instruction-sequences<br/>
(make-instruction-sequence '(proc) '()<br/>
`((test (op primitive-procedure?) (reg proc))<br/>
(branch (label ,primitive-branch))))<br/>
(parallel-instruction-sequences<br/>
(append-instruction-sequences<br/>
compiled-branch<br/>
(compile-proc-appl target compiled-linkage))<br/>
(append-instruction-sequences<br/>
primitive-branch<br/>
(end-with-linkage linkage<br/>
(make-instruction-sequence '(proc argl)<br/>
(list target)<br/>
`((assign ,target<br/>
(op apply-primitive-procedure)<br/>
(reg proc)<br/>
(reg argl)))))))<br/>
after-call))))<br/></tt></p><p/><p>Os ramos primitivos e compostos, como os ramos verdadeiro e falso em <tt>compile-if</tt>, são anexados usando <tt>parallel-instruction-sequences</tt> ao invés do comum <tt>append-instruction-sequences</tt>, pois eles não serão executados sequencialmente.</p><p>
<a name="%_sec_Temp_811" id="%_sec_Temp_811"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_811">Aplicando procedimentos compilados</a></h4><p>O código que manipula a aplicação de procedimento é a parte mais sutil do compilador, mesmo que as sequências de instruções que ele gera sejam muito curtas. Um procedimento compilado (construído por <tt>compile-lambda</tt>) possui um ponto de entrada, que é um rótulo que indica onde o código do procedimento é iniciado. O código neste ponto de entrada calcula um resultado em <tt>val</tt> e retorna executando a instrução <tt>(goto (reg continue))</tt>. Portanto, podemos esperar que o código para uma aplicação de procedimento compilado (seja gerado por <tt>compile-proc-appl</tt>) com um determinado alvo e ligação se pareça com isto se a ligação for um rótulo</p><p/><p><tt> (assign continue (label proc-return))<br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/>
proc-return<br/>
(assign <<em>target</em>> (reg val)) <em>; included if target is not <tt>val</tt></em><br/>
(goto (label <<em>linkage</em>>)) <em>; linkage code</em><br/></tt></p><p/><p>ou assim se a ligação for <tt>return</tt>.</p><p/><p><tt> (save continue)<br/>
(assign continue (label proc-return))<br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/>
proc-return<br/>
(assign <<em>target</em>> (reg val)) <em>; included if target is not <tt>val</tt></em><br/>
(restore continue)<br/>
(goto (reg continue)) <em>; linkage code</em><br/></tt></p><p/><p>Este código configura <tt>continue</tt> para que o procedimento retorne a um rótulo <tt>proc-return</tt> e pula para o ponto de entrada do procedimento. O código em <tt>proc-return</tt> transfere o resultado do procedimento de <tt>val</tt> para o registrador alvo (se necessário) e depois pula para o local especificado pela ligação. (A ligação é sempre <tt>return</tt> ou um rótulo, pois <tt>compile-procedure-call</tt> substitui um <tt>next</tt> ligação para o ramo do procedimento composto por um <tt>after-call</tt> rótulo).</p><p>De fato, se o alvo não for <tt>val</tt>, esse é exatamente o código que nosso compilador irá gerar.<a name="call_footnote_Temp_812" href="#footnote_Temp_812" id="call_footnote_Temp_812"><sup><small>39</small></sup></a> Geralmente, no entanto, o alvo é <tt>val</tt> (o único momento em que o compilador especifica um registrador diferente é ao direcionar a avaliação de um operador para <tt>proc</tt>), para que o resultado do procedimento seja colocado diretamente no registrador de destino e não seja necessário retornar a um local especial que o copie. Em vez disso, simplificamos o código configurando <tt>continue</tt> para que o procedimento “retorne” diretamente ao local especificado pela ligação do chamador:</p><p/><p><tt><<em>set up <tt>continue</tt> for linkage</em>><br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/></tt></p><p/><p>Se a ligação for um rótulo, montamos <tt>continue</tt> para que o procedimento retorne a esse rótulo. (Ou seja, o procedimento <tt>(goto (reg continue))</tt> termina com torna-se equivalente ao <tt>(goto (label <<em>linkage</em>>))</tt> às <tt>proc-return</tt> acima).</p><p/><p><tt>(assign continue (label <<em>linkage</em>>))<br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/></tt></p><p/><p>Se a ligação for <tt>return</tt>, não precisamos configurar <tt>continue</tt>. Ela já contém o local desejado. (Ou seja, o procedimento <tt>(goto (reg continue))</tt> termina com vai diretamente para o local onde o <tt>(goto (reg continue))</tt> às <tt>proc-return</tt> teria ido).</p><p/><p><tt>(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/></tt></p><p/><p>
<a name="%_idx_6352" id="%_idx_6352"/><a name="%_idx_6354" id="%_idx_6354"/>Com esta implementação do <tt>return</tt> ligação, o compilador gera código recursivo de cauda. Chamar um procedimento como a etapa final no corpo de um procedimento faz uma transferência direta, sem salvar nenhuma informação na pilha.</p><p>Suponha que, em vez disso, tivéssemos lidado com o caso de uma chamada de procedimento com uma ligação de <tt>return</tt> e um alvo de <tt>val</tt> como mostrado acima para um <tt>val</tt> alvo. Isso destruiria a recursão de cauda. Nosso sistema ainda daria o mesmo valor para qualquer expressão. Mas cada vez que chamamos um procedimento, economizamos <tt>continue</tt> e retorne após a chamada para desfazer o salvamento (inútil). Esses salvamentos extras se acumulariam durante um aninhamento de chamadas de procedimento.<a name="call_footnote_Temp_813" href="#footnote_Temp_813" id="call_footnote_Temp_813"><sup><small>40</small></sup></a></p><p>
<tt>Compile-proc-appl</tt> gera o código de aplicação de procedimento acima considerando quatro casos, dependendo se o alvo da chamada é <tt>val</tt> e se a ligação é <tt>return</tt>. Observe que as sequências de instruções são declaradas para modificar todos os registradores, pois a execução do corpo do procedimento pode alterá-los de maneira arbitrária.<a name="call_footnote_Temp_814" href="#footnote_Temp_814" id="call_footnote_Temp_814"><sup><small>41</small></sup></a> Observe também que a sequência de código para o caso com destino <tt>val</tt> e ligação <tt>return</tt> é declarado necessário <tt>continue</tt>: Apesar de <tt>continue</tt> não é explicitamente usado na sequência de duas instruções, devemos ter certeza de que <tt>continue</tt> terá o valor correto quando inserirmos o procedimento compilado.</p><p>
</p><p/><p><tt><a name="%_idx_6376" id="%_idx_6376"/>(define (compile-proc-appl target linkage)<br/>
(cond ((and (eq? target 'val) (not (eq? linkage 'return)))<br/>
(make-instruction-sequence '(proc) all-regs<br/>
`((assign continue (label ,linkage))<br/>
(assign val (op compiled-procedure-entry)<br/>
(reg proc))<br/>
(goto (reg val)))))<br/>
((and (not (eq? target 'val))<br/>
(not (eq? linkage 'return)))<br/>
(let ((proc-return (make-label 'proc-return)))<br/>
(make-instruction-sequence '(proc) all-regs<br/>
`((assign continue (label ,proc-return))<br/>
(assign val (op compiled-procedure-entry)<br/>
(reg proc))<br/>
(goto (reg val))<br/>
,proc-return<br/>
(assign ,target (reg val))<br/>
(goto (label ,linkage))))))<br/>
((and (eq? target 'val) (eq? linkage 'return))<br/>
(make-instruction-sequence '(proc continue) all-regs<br/>
'((assign val (op compiled-procedure-entry)<br/>
(reg proc))<br/>
(goto (reg val)))))<br/>
((and (not (eq? target 'val)) (eq? linkage 'return))<br/>
(error "return linkage, target not val -- COMPILE"<br/>
target))))<br/></tt></p><p/><p>
</p><p>
<a name="%_sec_5.5.4" id="%_sec_5.5.4"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.4">5.5.4 Combinando sequências de instruções</a></h3><p>
<a name="%_idx_6378" id="%_idx_6378"/>Esta seção descreve os detalhes de como as sequências de instruções são representadas e combinadas. Lembre-se da seção <a href="#%_sec_5.5.1">5.5.1</a> que uma sequência de instruções é representada como uma lista dos registradores necessários, os registradores modificados e as instruções reais. Também consideraremos um rótulo (símbolo) como um caso degenerado de uma sequência de instruções, que não precisa nem modifica nenhum registrador. Portanto, para determinar os registradores necessários e modificados pelas sequências de instruções, usamos os seletores</p><p/><p><tt><a name="%_idx_6380" id="%_idx_6380"/>(define (registers-needed s)<br/>
(if (symbol? s) '() (car s)))<br/><a name="%_idx_6382" id="%_idx_6382"/>(define (registers-modified s)<br/>
(if (symbol? s) '() (cadr s)))<br/><a name="%_idx_6384" id="%_idx_6384"/>(define (statements s)<br/>
(if (symbol? s) (list s) (caddr s)))<br/></tt></p><p/><p>e para determinar se uma determinada sequência precisa ou modifica um determinado registrador, usamos os predicados</p><p/><p><tt><a name="%_idx_6386" id="%_idx_6386"/>(define (needs-register? seq reg)<br/>
(memq reg (registers-needed seq)))<br/><a name="%_idx_6388" id="%_idx_6388"/>(define (modifies-register? seq reg)<br/>
(memq reg (registers-modified seq)))<br/></tt></p><p/><p>Em termos desses predicados e seletores, podemos implementar os vários combinadores de sequência de instruções usados em todo o compilador.</p><p>O combinador básico é <tt>append-instruction-sequences</tt>. Isso leva como argumento um número arbitrário de sequências de instruções que devem ser executadas sequencialmente e retorna uma sequência de instruções cujas instruções são as instruções de todas as sequências anexadas. O ponto sutil é determinar os registradores necessários e modificados pela sequência resultante. Modifica os registradores que são modificados por qualquer uma das sequências; ele precisa dos registradores que devem ser iniciados antes que a primeira sequência possa ser executada (os registradores necessários para a primeira sequência), com os registradores necessários para qualquer uma das outras sequências que não são iniciadas (modificadas) pelas sequências que a precedem.</p><p>As sequências são anexadas duas de cada vez por <tt>append-2-sequences</tt>. São necessárias duas sequências de instruções <tt>seq1</tt> e <tt>seq2</tt> e retorna a sequência de instruções cujas instruções são as instruções de <tt>seq1</tt> seguido pelas declarações de <tt>seq2</tt>, cujos registradores modificados são aqueles que são modificados por <tt>seq1</tt> ou <tt>seq2</tt> e cujos registradores necessários são os registradores necessários para <tt>seq1</tt> com os registradores necessários para <tt>seq2</tt> que não são modificados por <tt>seq1</tt>. (Em termos de operações de conjunto, o novo conjunto de registradores necessários é a união do conjunto de registradores necessário <tt>seq1</tt> com a diferença definida dos registradores necessários para <tt>seq2</tt> e os registradores modificados por <tt>seq1</tt>). Portanto, <tt>append-instruction-sequences</tt> é implementado da seguinte maneira:</p><p>
</p><p/><p><tt><a name="%_idx_6390" id="%_idx_6390"/>(define (append-instruction-sequences . seqs)<br/>
(define (append-2-sequences seq1 seq2)<br/>
(make-instruction-sequence<br/>
(list-union (registers-needed seq1)<br/>
(list-difference (registers-needed seq2)<br/>
(registers-modified seq1)))<br/>
(list-union (registers-modified seq1)<br/>
(registers-modified seq2))<br/>
(append (statements seq1) (statements seq2))))<br/>
(define (append-seq-list seqs)<br/>
(if (null? seqs)<br/>
(empty-instruction-sequence)<br/>
(append-2-sequences (car seqs)<br/>
(append-seq-list (cdr seqs)))))<br/>
(append-seq-list seqs))<br/></tt></p><p/><p/><p>Este procedimento usa algumas operações simples para manipular conjuntos representados como listas, semelhantes à representação de conjunto (não ordenada) descrita na seção <a href="book-Z-H-16.html#%_sec_2.3.3">2.3.3</a>:</p><p/><p><tt><a name="%_idx_6392" id="%_idx_6392"/>(define (list-union s1 s2)<br/>
(cond ((null? s1) s2)<br/>
((memq (car s1) s2) (list-union (cdr s1) s2))<br/>
(else (cons (car s1) (list-union (cdr s1) s2)))))<br/><a name="%_idx_6394" id="%_idx_6394"/>(define (list-difference s1 s2)<br/>
(cond ((null? s1) '())<br/>
((memq (car s1) s2) (list-difference (cdr s1) s2))<br/>
(else (cons (car s1)<br/>
(list-difference (cdr s1) s2)))))<br/></tt></p><p/><p/><p>
<tt>Preserving</tt>, o segundo maior combinador de sequência de instruções, faz uma lista de registradores <tt>regs</tt> e duas sequências de instruções <tt>seq1</tt> e <tt>seq2</tt> que devem ser executados sequencialmente. Retorna uma sequência de instruções cujas instruções são as instruções de <tt>seq1</tt> seguido pelas declarações de <tt>seq2</tt>, com as instruções <tt>save</tt> e <tt>restore</tt> em torno de <tt>seq1</tt> para proteger os registradores em <tt>regs</tt> que são modificados por <tt>seq1</tt> mas necessário por <tt>seq2</tt>. Para conseguir isso, <tt>preserving</tt> primeiro cria uma sequência que possui o requerido <tt>save</tt> s seguidos pelas declarações de <tt>seq1</tt> seguido pelo requerido <tt>restore</tt> s. Essa sequência precisa que os registradores sejam salvos e restaurados, além dos registradores necessários para <tt>seq1</tt> e modifica os registradores modificados por <tt>seq1</tt> exceto os que são salvos e restaurados. Essa sequência acrescentada e <tt>seq2</tt> são então anexados da maneira usual. O procedimento a seguir implementa essa estratégia recursivamente, percorrendo a lista de registradores a serem preservados:<a name="call_footnote_Temp_815" href="#footnote_Temp_815" id="call_footnote_Temp_815"><sup><small>42.</small></sup></a>
</p><p/><p><tt><a name="%_idx_6398" id="%_idx_6398"/>(define (preserving regs seq1 seq2)<br/>
(if (null? regs)<br/>
(append-instruction-sequences seq1 seq2)<br/>
(let ((first-reg (car regs)))<br/>
(if (and (needs-register? seq2 first-reg)<br/>
(modifies-register? seq1 first-reg))<br/>
(preserving (cdr regs)<br/>
(make-instruction-sequence<br/>
(list-union (list first-reg)<br/>
(registers-needed seq1))<br/>
(list-difference (registers-modified seq1)<br/>
(list first-reg))<br/>
(append `((save ,first-reg))<br/>
(statements seq1)<br/>
`((restore ,first-reg))))<br/>
seq2)<br/>
(preserving (cdr regs) seq1 seq2)))))<br/></tt></p><p/><p/><p>Outro combinador de sequência, <tt>tack-on-instruction-sequence</tt>, é usado por <tt>compile-lambda</tt> anexar um corpo de procedimento a outra sequência. Como o corpo do procedimento não está “alinhado” para ser executado como parte da sequência combinada, seu uso de registrador não afeta o uso de registrador da sequência na qual está incorporado. Assim, ignoramos os conjuntos de registradores necessários e modificados do corpo do procedimento quando o colocamos na outra sequência.</p><p>
</p><p/><p><tt><a name="%_idx_6400" id="%_idx_6400"/>(define (tack-on-instruction-sequence seq body-seq)<br/>
(make-instruction-sequence<br/>
(registers-needed seq)<br/>
(registers-modified seq)<br/>
(append (statements seq) (statements body-seq))))<br/></tt></p><p/><p/><p>
<tt>Compile-if</tt> e <tt>compile-procedure-call</tt> use um combinador especial chamado <tt>parallel-instruction-sequences</tt> anexar os dois ramos alternativos que seguem um teste. Os dois ramos nunca serão executados sequencialmente; para qualquer avaliação específica do teste, uma ramificação ou outra será inserida. Por esse motivo, os registradores necessários para o segundo ramo ainda são necessários pela sequência combinada, mesmo que sejam modificados pelo primeiro ramo.</p><p>
</p><p/><p><tt><a name="%_idx_6402" id="%_idx_6402"/>(define (parallel-instruction-sequences seq1 seq2)<br/>
(make-instruction-sequence<br/>
(list-union (registers-needed seq1)<br/>
(registers-needed seq2))<br/>
(list-union (registers-modified seq1)<br/>
(registers-modified seq2))<br/>
(append (statements seq1) (statements seq2))))<br/></tt></p><p/><p/><p>
<a name="%_sec_5.5.5" id="%_sec_5.5.5"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.5">5.5.5 Um exemplo de código compilado</a></h3><p>
<a name="%_idx_6404" id="%_idx_6404"/><a name="%_idx_6406" id="%_idx_6406"/>Agora que vimos todos os elementos do compilador, examinaremos um exemplo de código compilado para ver como se encaixam. Compilaremos a definição de uma recursiva procedimento <tt>factorial</tt> chamando <tt>compile</tt>:</p><p>
</p><p/><p><tt>(compile<br/>
'(define (factorial n)<br/>
(if (= n 1)<br/>
1<br/>
(* (factorial (- n 1)) n)))<br/>
'val<br/>
'next)<br/></tt></p><p/><p>Especificamos que o valor da expressão <tt>define</tt> deve ser colocada no registrador <tt>val</tt>. Não nos importamos com o que o código compilado faz depois de executar o <tt>define</tt>, então nossa escolha de <tt>next</tt> como o descritor de ligação é arbitrário.</p><p>
<tt>Compile</tt> determina que a expressão é uma definição, por isso chama <tt>compile-definition</tt> compilar código para calcular o valor a ser atribuído (orientado para <tt>val</tt>), seguido pelo código para instalar a definição, seguido pelo código para colocar o valor do <tt>define</tt> (que é o símbolo <tt>ok</tt>) no registrador de destino, seguido finalmente pelo código de ligação. <tt>Env</tt> é preservado em torno do cálculo do valor, pois é necessário para instalar a definição. Porque a ligação é <tt>next</tt>, não há código de ligação neste caso. O esqueleto do código compilado é assim</p><p>
</p><p/><p><tt> <<em>save <tt>env</tt> if modified by code to compute value</em>><br/>
<<em>compilation of definition value, target <tt>val</tt>, linkage <tt>next</tt></em>><br/>
<<em>restore <tt>env</tt> if saved above</em>><br/>
(perform (op define-variable!)<br/>
(const factorial)<br/>
(reg val)<br/>
(reg env))<br/>
(assign val (const ok))<br/></tt></p><p/><p/><p>A expressão que deve ser compilada para produzir o valor para a variável <tt>factorial</tt> é uma expressão <tt>lambda</tt> cujo valor é o procedimento que calcula fatoriais. <tt>Compile</tt> lida com isso chamando <tt>compile-lambda</tt>, que compila o corpo do procedimento, o rotula como um novo ponto de entrada e gera a instrução que combinará o corpo do procedimento no novo ponto de entrada com o ambiente de tempo de execução e atribuirá o resultado a <tt>val</tt>. A sequência então ignora o código do procedimento compilado, inserido neste momento. O próprio código do procedimento começa estendendo o ambiente de definição do procedimento por um quadro que liga o parâmetro formal <tt>n</tt> ao argumento do procedimento. Depois vem o corpo do procedimento real. Como esse código para o valor da variável não modifica o registrador <tt>env</tt>, o opcional <tt>save</tt> e <tt>restore</tt> mostrado acima não são gerados. (O código do procedimento em <tt>entry2</tt> não é executado neste momento, portanto, seu uso de <tt>env</tt> é irrelevante). Portanto, o esqueleto do código compilado se torna</p><p>
</p><p/><p><tt> (assign val (op make-compiled-procedure)<br/>
(label entry2)<br/>
(reg env))<br/>
(goto (label after-lambda1))<br/>
entry2<br/>
(assign env (op compiled-procedure-env) (reg proc))<br/>
(assign env (op extend-environment)<br/>
(const (n))<br/>
(reg argl)<br/>
(reg env))<br/>
<<em>compilation of procedure body</em>><br/>
after-lambda1<br/>
(perform (op define-variable!)<br/>
(const factorial)<br/>
(reg val)<br/>
(reg env))<br/>
(assign val (const ok))<br/></tt></p><p/><p/><p>Um corpo do procedimento é sempre compilado (por <tt>compile-lambda-body</tt>) como uma sequência com destino <tt>val</tt> e ligação <tt>return</tt>. A sequência neste caso consiste em uma única expressão <tt>if</tt>:</p><p>
</p><p/><p><tt>(if (= n 1)<br/>
1<br/>
(* (factorial (- n 1)) n))<br/></tt></p><p/><p>
<tt>Compile-if</tt> gera código que primeiro calcula o predicado (orientado para <tt>val</tt>), verifica o resultado e ramifica em torno da ramificação verdadeira se o predicado for falso. <tt>Env</tt> e <tt>continue</tt> são preservados em torno do código de predicado, pois podem ser necessários para o restante da expressão <tt>if</tt>. Desde que a expressão <tt>if</tt> é a expressão final (e única expressão) na sequência que compõe o corpo do procedimento, seu alvo é <tt>val</tt> e sua ligação é <tt>return</tt>, para que os desvios verdadeiro e falso sejam compilados com o destino <tt>val</tt> e ligação <tt>return</tt>. (Ou seja, o valor da condicional, que é o valor calculado por qualquer uma de suas ramificações, é o valor do procedimento).</p><p>
</p><p/><p><tt> <<em>save <tt>continue</tt>, <tt>env</tt> if modified by predicate and needed by branches</em>><br/>
<<em>compilation of predicate, target <tt>val</tt>, linkage <tt>next</tt></em>><br/>
<<em>restore <tt>continue</tt>, <tt>env</tt> if saved above</em>><br/>
(test (op false?) (reg val))<br/>
(branch (label false-branch4))<br/>
true-branch5<br/>
<<em>compilation of true branch, target <tt>val</tt>, linkage <tt>return</tt></em>><br/>
false-branch4<br/>
<<em>compilation of false branch, target <tt>val</tt>, linkage <tt>return</tt></em>><br/>
after-if3<br/></tt></p><p/><p/><p>O predicado <tt>(= n 1)</tt> é uma chamada de procedimento. Isso consulta o operador (o símbolo <tt>=</tt>) e coloca esse valor em <tt>proc</tt>. Em seguida, reúne os argumentos <tt>1</tt> e o valor de <tt>n</tt> para dentro <tt>argl</tt>. Então ele testa se <tt>proc</tt> contém um procedimento primitivo ou composto e despacha para um ramo primitivo ou um ramo composto de acordo. Ambos os ramos são retomados no <tt>after-call</tt> rótulo. Os requisitos para preservar registradores em torno da avaliação do operador e operandos não resultam em economia de registradores, pois nesse caso essas avaliações não modificam os registradores em questão.</p><p>
</p><p/><p><tt> (assign proc<br/>
(op lookup-variable-value) (const =) (reg env))<br/>
(assign val (const 1))<br/>
(assign argl (op list) (reg val))<br/>
(assign val (op lookup-variable-value) (const n) (reg env))<br/>
(assign argl (op cons) (reg val) (reg argl))<br/>
(test (op primitive-procedure?) (reg proc))<br/>
(branch (label primitive-branch17))<br/>
compiled-branch16<br/>
(assign continue (label after-call15))<br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/>
primitive-branch17<br/>
(assign val (op apply-primitive-procedure)<br/>
(reg proc)<br/>
(reg argl))<br/>
after-call15<br/></tt></p><p/><p/><p>O ramo verdadeiro, que é a constante 1, compila (com o destino <tt>val</tt> e ligação <tt>return</tt>) para</p><p>
</p><p/><p><tt> (assign val (const 1))<br/>
(goto (reg continue))<br/></tt></p><p/><p>O código para a ramificação falsa é outra chamada de procedimento, em que o procedimento é o valor do símbolo <tt>*</tt> e os argumentos são <tt>n</tt> e o resultado de outra chamada de procedimento (uma chamada para <tt>factorial</tt>) Cada uma dessas chamadas configura <tt>proc</tt> e <tt>argl</tt> e seus próprios ramos primitivos e compostos. A figura <a href="#%_fig_5.17">5.17</a> mostra a compilação completa da definição do procedimento <tt>factorial</tt>. Observe que o possível <tt>save</tt> e <tt>restore</tt> do <tt>continue</tt> e <tt>env</tt> ao redor do predicado, mostrado acima, são de fato gerados, pois esses registradores são modificados pela chamada de procedimento no predicado e necessários para a chamada de procedimento e o <tt>return</tt> ligação nos ramos.</p><p><a name="%_thm_5.33" id="%_thm_5.33"/>
<b>Exercício 5.33.</b> Considere a seguinte definição de um procedimento fatorial, que é ligeiramente diferente da dada acima:</p><p/><p><tt>(define (factorial-alt n)<br/>
(if (= n 1)<br/>
1<br/>
(* n (factorial-alt (- n 1)))))<br/></tt></p><p/><p>Compile este procedimento e compare o código resultante com o produzido para <tt>factorial</tt>. Explique as diferenças encontradas. Um dos programas é executado com mais eficiência que o outro?</p><p/><p>
</p><p><a name="%_thm_5.34" id="%_thm_5.34"/>
<b>Exercício 5.34.</b> <a name="%_idx_6408" id="%_idx_6408"/><a name="%_idx_6410" id="%_idx_6410"/>Compilar o procedimento fatorial iterativo</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>Anote o código resultante, mostrando a diferença essencial entre o código para versões iterativas e recursivas de <tt>factorial</tt> isso faz com que um processo crie espaço na pilha e o outro execute no espaço constante.</p><p>
</p><p>
<a name="%_fig_5.17" id="%_fig_5.17"/></p><p/><div align="left"><table width="100%"><tr><td><p/><p><tt><em>;; construct the procedure and skip over code for the procedure body</em><br/> (assign val<br/> (op make-compiled-procedure) (label entry2) (reg env))<br/> (goto (label after-lambda1))<br/><br/> ;; entry2 <em>; calls to <tt>factorial</tt> will enter here </em><br/> (assign env (op compiled-procedure-env) (reg proc))<br/> (assign env<br/> (op extend-environment) (const (n)) (reg argl) (reg env))<br/><em>;; begin actual procedure body</em><br/> (save continue)<br/> (save env)<br/><br/><em>;; compute <tt>(= n 1)</tt></em><br/> (assign proc (op lookup-variable-value) (const =) (reg env))<br/> (assign val (const 1))<br/> (assign argl (op list) (reg val))<br/> (assign val (op lookup-variable-value) (const n) (reg env))<br/> (assign argl (op cons) (reg val) (reg argl))<br/> (test (op primitive-procedure?) (reg proc))<br/> (branch (label primitive-branch17))<br/> compiled-branch16<br/> (assign continue (label after-call15))<br/> (assign val (op compiled-procedure-entry) (reg proc))<br/> (goto (reg val))<br/> primitive-branch17<br/> (assign val (op apply-primitive-procedure) (reg proc) (reg argl))<br/><br/> ;; after-call15 <em>; <tt>val</tt> now contains result of <tt>(= n 1)</tt></em><br/> (restore env)<br/> (restore continue)<br/> (test (op false?) (reg val))<br/> (branch (label false-branch4))<br/> ;; true-branch5 <em>; return 1</em><br/> (assign val (const 1))<br/> (goto (reg continue))<br/><br/> false-branch4<br/><em>;; compute and return <tt>(* (factorial (- n 1)) n)</tt></em><br/> (assign proc (op lookup-variable-value) (const *) (reg env))<br/> (save continue)<br/> (save proc) <em>; save <tt>*</tt></em> procedure<br/> (assign val (op lookup-variable-value) (const n) (reg env))<br/> (assign argl (op list) (reg val))<br/> (save argl) <em>; save partial argument list for <tt>*</tt></em><br/><br/><em>;; compute <tt>(factorial (- n 1))</tt>, which is the other argument for <tt>*</tt></em><br/> (assign proc<br/> (op lookup-variable-value) (const factorial) (reg env))<br/> (save proc) <em>; save <tt>factorial</tt> procedure</em><br/></tt></p><p/><p>
</p><p/><p/></td></tr><caption align="bottom"><div align="left"><b>Figura 5.17:</b> Compilação da definição do procedimento <tt>fatorial</tt> (continua na próxima página).</div></caption><tr><td>
<a name="%_idx_6412" id="%_idx_6412"/>
</td></tr></table></div><p/><p>
<a name="%_fig_5.17" id="%_fig_5.17"/></p><p/><div align="left"><table width="100%"><tr><td><p/><p><tt><em>;; compute <tt>(- n 1)</tt>, which is the argument for <tt>factorial</tt></em><br/> (assign proc (op lookup-variable-value) (const -) (reg env))<br/> (assign val (const 1))<br/> (assign argl (op list) (reg val))<br/> (assign val (op lookup-variable-value) (const n) (reg env))<br/> (assign argl (op cons) (reg val) (reg argl))<br/> (test (op primitive-procedure?) (reg proc))<br/> (branch (label primitive-branch8))<br/> compiled-branch7<br/> (assign continue (label after-call6))<br/> (assign val (op compiled-procedure-entry) (reg proc))<br/> (goto (reg val))<br/> primitive-branch8<br/> (assign val (op apply-primitive-procedure) (reg proc) (reg argl))<br/><br/> ;; after-call6 <em>; <tt>val</tt> now contains result of <tt>(- n 1)</tt></em><br/> (assign argl (op list) (reg val))<br/> (restore proc) <em>; restore <tt>factorial</tt></em><br/><em>;; apply <tt>factorial</tt></em><br/> (test (op primitive-procedure?) (reg proc))<br/> (branch (label primitive-branch11))<br/> compiled-branch10<br/> (assign continue (label after-call9))<br/> (assign val (op compiled-procedure-entry) (reg proc))<br/> (goto (reg val))<br/> primitive-branch11<br/> (assign val (op apply-primitive-procedure) (reg proc) (reg argl))<br/><br/> ;; after-call9 <em>; <tt>val</tt> now contains result of <tt>(factorial (- n 1))</tt></em><br/> (restore argl) <em>; restore partial argument list for <tt>*</tt></em><br/> (assign argl (op cons) (reg val) (reg argl))<br/> (restore proc) <em>; restore <tt>*</tt></em><br/> (restore continue)<br/><em>;; apply <tt>*</tt></em> and return its value<br/> (test (op primitive-procedure?) (reg proc))<br/> (branch (label primitive-branch14))<br/> compiled-branch13<br/><em>;; note that a compound procedure here is called tail-recursively</em><br/> (assign val (op compiled-procedure-entry) (reg proc))<br/> (goto (reg val))<br/> primitive-branch14<br/> (assign val (op apply-primitive-procedure) (reg proc) (reg argl))<br/> (goto (reg continue))<br/> after-call12<br/> after-if3<br/> after-lambda1<br/><em>;; assign the procedure to the variable <tt>factorial</tt></em><br/> (perform<br/> (op define-variable!) (const factorial) (reg val) (reg env))<br/> (assign val (const ok))<br/></tt></p><p/><p>
</p><p/><p/></td></tr><caption align="bottom"><div align="left"><b>Figura 5.17:</b>(contínuo)</div></caption><tr><td>
</td></tr></table></div><p/><p>
</p><p><a name="%_thm_5.35" id="%_thm_5.35"/>
<b>Exercício 5.35.</b> Qual expressão foi compilada para produzir o código mostrado na figura <a href="#%_fig_5.18">5.18</a>?<a name="%_fig_5.18" id="%_fig_5.18"/></p><p/><div align="left"><table width="100%"><tr><td><p/><p><tt> (assign val (op make-compiled-procedure) (label entry16)<br/>
(reg env))<br/>
(goto (label after-lambda15))<br/>
entry16<br/>
(assign env (op compiled-procedure-env) (reg proc))<br/>
(assign env<br/>
(op extend-environment) (const (x)) (reg argl) (reg env))<br/>
(assign proc (op lookup-variable-value) (const +) (reg env))<br/>
(save continue)<br/>
(save proc)<br/>
(save env)<br/>
(assign proc (op lookup-variable-value) (const g) (reg env))<br/>
(save proc)<br/>
(assign proc (op lookup-variable-value) (const +) (reg env))<br/>
(assign val (const 2))<br/>
(assign argl (op list) (reg val))<br/>
(assign val (op lookup-variable-value) (const x) (reg env))<br/>
(assign argl (op cons) (reg val) (reg argl))<br/>
(test (op primitive-procedure?) (reg proc))<br/>
(branch (label primitive-branch19))<br/>
compiled-branch18<br/>
(assign continue (label after-call17))<br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/>
primitive-branch19<br/>
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))<br/>
after-call17<br/>
(assign argl (op list) (reg val))<br/>
(restore proc)<br/>
(test (op primitive-procedure?) (reg proc))<br/>
(branch (label primitive-branch22))<br/>
compiled-branch21<br/>
(assign continue (label after-call20))<br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/>
primitive-branch22<br/>
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))<br/></tt></p><p/><p>
</p><p/><p/></td></tr><caption align="bottom"><div align="left"><b>Figura 5.18:</b> Um exemplo de saída do compilador (continua na próxima página). Veja o exercício <a href="#%_thm_5.35">5.35</a>.</div></caption><tr><td>
</td></tr></table></div><p/><p>
<a name="%_fig_5.18" id="%_fig_5.18"/></p><p/><div align="left"><table width="100%"><tr><td><p/><p><tt>after-call20<br/>
(assign argl (op list) (reg val))<br/>
(restore env)<br/>
(assign val (op lookup-variable-value) (const x) (reg env))<br/>
(assign argl (op cons) (reg val) (reg argl))<br/>
(restore proc)<br/>
(restore continue)<br/>
(test (op primitive-procedure?) (reg proc))<br/>
(branch (label primitive-branch25))<br/>
compiled-branch24<br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/>
primitive-branch25<br/>
(assign val (op apply-primitive-procedure) (reg proc) (reg argl))<br/>
(goto (reg continue))<br/>
after-call23<br/>
after-lambda15<br/>
(perform (op define-variable!) (const f) (reg val) (reg env))<br/>
(assign val (const ok))<br/></tt></p><p/><p>
</p><p/><p/></td></tr><caption align="bottom"><div align="left"><b>Figura 5.18:</b>(contínuo)</div></caption><tr><td>
</td></tr></table></div><p>
</p><p/><p>
</p><p><a name="%_thm_5.36" id="%_thm_5.36"/>
<b>Exercício 5.36.</b> <a name="%_idx_6414" id="%_idx_6414"/><a name="%_idx_6416" id="%_idx_6416"/>Que ordem de avaliação nosso compilador produz para operandos de uma combinação? É da esquerda para a direita, da direita para a esquerda ou de alguma outra ordem? Onde no compilador esta ordem é determinada? Modifique o compilador para que ele produza outra ordem de avaliação. (Veja a discussão da ordem de avaliação do avaliador de controle explícito na seção <a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>). Como a alteração da ordem da avaliação do operando afeta a eficiência do código que constrói a lista de argumentos?</p><p/><p>
</p><p><a name="%_thm_5.37" id="%_thm_5.37"/>
<b>Exercício 5.37.</b> <a name="%_idx_6418" id="%_idx_6418"/><a name="%_idx_6420" id="%_idx_6420"/>Uma maneira de entender o compilador <tt>preserving</tt> Um mecanismo para otimizar o uso da pilha é ver quais operações extras seriam geradas se não usássemos essa ideia. Modificar <tt>preserving</tt> para que ele sempre gere as operações <tt>save</tt> e <tt>restore</tt>. Compile algumas expressões simples e identifique as operações desnecessárias de pilha que são geradas. Compare o código com o gerado com o mecanismo do <tt>preserving</tt> intacto.</p><p/><p>
</p><p><a name="%_thm_5.38" id="%_thm_5.38"/>
<b>Exercício 5.38.</b> <a name="%_idx_6422" id="%_idx_6422"/><a name="%_idx_6424" id="%_idx_6424"/>Nosso compilador é inteligente em evitar operações desnecessárias de pilha, mas não é nada inteligente quando se trata de compilar chamadas para os procedimentos primitivos da linguagem em termos das operações primitivas fornecidas pela máquina. Por exemplo, considere quanto código é compilado para calcular <tt>(+ a 1)</tt>: O código configura uma lista de argumentos em <tt>argl</tt>, coloca o procedimento de adição primitivo (encontrado ao procurar o símbolo <tt>+</tt> no ambiente) em <tt>proc</tt> e testa se o procedimento é primitivo ou composto. O compilador sempre gera código para executar o teste, bem como código para ramificações primitivas e compostas (apenas uma delas será executada). Não mostramos a parte do controlador que implementa primitivas, mas presumimos que essas instruções utilizem operações aritméticas primitivas nos caminhos de dados da máquina. Considere quanto menos código seria gerado se o compilador pudesse gerar primitivas do <em>código aberto</em> – isto é, se pudesse gerar código para usar diretamente essas operações primitivas da máquina. A expressão <tt>(+ a 1)</tt> pode ser compilado em algo tão simples quanto <a name="call_footnote_Temp_822" href="#footnote_Temp_822" id="call_footnote_Temp_822"><sup><small>43</small></sup></a>
</p><p/><p><tt>(assign val (op lookup-variable-value) (const a) (reg env))<br/>
(assign val (op +) (reg val) (const 1))<br/></tt></p><p/><p>Neste exercício, estenderemos nosso compilador para oferecer suporte à codificação aberta de primitivas selecionadas. O código de finalidade especial será gerado para chamadas para esses procedimentos primitivos, em vez do código geral da aplicação de procedimento. Para suportar isso, melhoraremos nossa máquina com registradores de argumentos especiais <tt>arg1</tt> e <tt>arg2</tt>. As operações aritméticas primitivas da máquina receberão suas entradas de <tt>arg1</tt> e <tt>arg2</tt>. Os resultados podem ser colocados em <tt>val</tt>, <tt>arg1</tt> ou <tt>arg2</tt>.</p><p>O compilador deve ser capaz de reconhecer a aplicação de uma primitiva de código aberto no programa de origem. Melhoraremos o envio no procedimento <tt>compile</tt> para reconhecer os nomes dessas primitivas, além das <a name="%_idx_6426" id="%_idx_6426"/>palavras reservadas (as formas especiais) atualmente reconhecidas.<a name="call_footnote_Temp_823" href="#footnote_Temp_823" id="call_footnote_Temp_823"><sup><small>44</small></sup></a> Para cada formulário especial, nosso compilador possui um gerador de código. Neste exercício, construiremos uma família de geradores de código para as primitivas de código aberto.</p><p>a. As primitivas de código aberto, diferentemente das formas especiais, precisam de seus operandos avaliados. Escreva um gerador de código <tt>spread-arguments</tt> para uso por todos os geradores de código de código aberto. <tt>Spread-arguments</tt> deve pegar uma lista de operandos e compilar os operandos dados orientados a registradores de argumentos sucessivos. Observe que um operando pode conter uma chamada para uma primitiva de código aberto; portanto, os registradores de argumentos deverão ser preservados durante a avaliação do operando.</p><p>b. Para cada um dos procedimentos primitivos <tt>=</tt>, <tt>*</tt>, <tt>-</tt> e <tt>+</tt>, escreva um gerador de código que faça uma combinação com esse operador, com um destino e um descritor de ligação, e produz código para espalhar os argumentos nos registradores e, em seguida, execute a operação direcionada para o destino especificado com a ligação especificada. Você apenas precisa manipular expressões com dois operandos. Faço <tt>compile</tt> despachar para esses geradores de código.</p><p>c. Experimente o seu novo compilador no <tt>factorial</tt> exemplo. Compare o código resultante com o resultado produzido sem codificação aberta.</p><p>d. Estenda seus geradores de código para <tt>+</tt> e <tt>*</tt> para que eles possam manipular expressões com números arbitrários de operandos. Uma expressão com mais de dois operandos deverá ser compilada em uma sequência de operações, cada uma com apenas duas entradas.</p><p/><p>
<a name="%_sec_5.5.6" id="%_sec_5.5.6"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.6">5.5.6 Endereçamento léxico</a></h3><p>
<a name="%_idx_6428" id="%_idx_6428"/><a name="%_idx_6430" id="%_idx_6430"/>Uma das otimizações mais comuns executadas pelos compiladores é a otimização da pesquisa de variáveis. Nosso compilador, como o implementamos até agora, gera código que usa a operação <tt>lookup-variable-value</tt> da máquina avaliadora. Ele procura uma variável comparando-a com cada variável atualmente ligada, trabalhando quadro a quadro para fora através do ambiente de tempo de execução. Essa pesquisa pode ser cara se os quadros estiverem profundamente aninhados ou se houver muitas variáveis. Por exemplo, considere o problema de procurar o valor de <tt>x</tt> enquanto avalia a expressão <tt>(* x y z)</tt> em uma aplicação do procedimento retornado por</p><p>
</p><p/><p><tt>(let ((x 3) (y 4))<br/>
(lambda (a b c d e)<br/>
(let ((y (* a b x))<br/>
(z (+ c d x)))<br/>
(* x y z))))<br/></tt></p><p/><p>Desde que uma expressão <tt>let</tt> é apenas açúcar sintático para um <tt>lambda</tt> combinação, essa expressão é equivalente a</p><p>
</p><p/><p><tt>((lambda (x y)<br/>
(lambda (a b c d e)<br/>
((lambda (y z) (* x y z))<br/>
(* a b x)<br/>
(+ c d x))))<br/>
3<br/>
4)<br/></tt></p><p/><p>Cada vez <tt>lookup-variable-value</tt> procura por <tt>x</tt>, ele deve determinar que o símbolo <tt>x</tt> não é <tt>eq?</tt> para <tt>y</tt> ou <tt>z</tt> (no primeiro quadro), nem para <tt>a</tt>, <tt>b</tt>, <tt>c</tt>, <tt>d</tt> ou <tt>e</tt> (no segundo quadro). Presumiremos, por enquanto, que nossos programas não usam <tt>define</tt> – que variáveis são ligadas apenas com <tt>lambda</tt>. Porque a nossa linguagem é no <a name="%_idx_6432" id="%_idx_6432"/>escopo lexical, o ambiente de tempo de execução para qualquer expressão terá uma estrutura que é paralela à estrutura lexical do programa em que a expressão aparece.<a name="call_footnote_Temp_824" href="#footnote_Temp_824" id="call_footnote_Temp_824"><sup><small>45</small></sup></a> Assim, o compilador pode saber, quando analisa a expressão acima, que cada vez que o procedimento é aplicado, a variável <tt>x</tt> no <tt>(* x y z)</tt> serão encontrados dois quadros fora do quadro atual e será a primeira variável nesse quadro.</p><p>
<a name="%_idx_6434" id="%_idx_6434"/>Podemos explorar esse fato inventando um novo tipo de operação de pesquisa variável, <tt>lexical-address-lookup</tt>, que toma como argumento um ambiente e um <em>endereço lexical</em> que consiste em dois números: um <em>número do quadro</em>, que especifica quantos quadros passar e um <em>número de deslocamento</em>, que especifica quantas variáveis serão passadas nesse quadro. <a name="%_idx_6436" id="%_idx_6436"/><tt>Lexical-address-lookup</tt> produzirá o valor da variável armazenada nesse endereço lexical em relação ao ambiente atual. Se adicionarmos a operação <tt>lexical-address-lookup</tt> em nossa máquina, podemos fazer o compilador gerar código que faça referência a variáveis usando esta operação, em vez de <tt>lookup-variable-value</tt>. Da mesma forma, nosso código compilado pode usar uma nova operação <a name="%_idx_6438" id="%_idx_6438"/><tt>lexical-address-set!</tt> em vez de <tt>set-variable-value!</tt>.</p><p>Para gerar esse código, o compilador deve ser capaz de determinar o endereço lexical de uma variável que está prestes a compilar uma referência. O endereço lexical de uma variável em um programa depende de onde alguém está no código. Por exemplo, no programa a seguir, o endereço de <tt>x</tt> na expressão <<em>e1</em>> é (2,0) – dois quadros atrás e a primeira variável no quadro. Nesse ponto <tt>y</tt> está no endereço (0,0) e <tt>c</tt> está no endereço (1,2). Na expressão <<em>e2</em>>, <tt>x</tt> está em (1,0), <tt>y</tt> está em (1,1) e <tt>c</tt> está em (0,2).</p><p>
</p><p/><p><tt>((lambda (x y)<br/>
(lambda (a b c d e)<br/>
((lambda (y z) <<em>e1</em>>)<br/>
<<em>e2</em>><br/>
(+ c d x))))<br/>
3<br/>
4)<br/></tt></p><p/><p/><p>
<a name="%_idx_6440" id="%_idx_6440"/>Uma maneira de o compilador produzir código que usa endereçamento lexical é manter uma estrutura de dados chamada <em>ambiente de tempo de compilação</em>. Isso controla quais variáveis estarão em quais posições em quais quadros no ambiente de tempo de execução quando uma operação de acesso variável específica for executada. O ambiente de tempo de compilação é uma lista de quadros, cada um contendo uma lista de variáveis. (Obviamente, não haverá valores ligados às variáveis, pois os valores não são computados no tempo de compilação). O ambiente de tempo de compilação se torna um argumento adicional para <tt>compile</tt> e é passado para cada gerador de código. A chamada de nível superior para <tt>compile</tt> usa um ambiente de tempo de compilação vazio. Quando um <tt>lambda</tt> corpo é compilado, <tt>compile-lambda-body</tt> estende o ambiente de tempo de compilação por um quadro que contém os parâmetros do procedimento, para que a sequência que compõe o corpo seja compilada com esse ambiente estendido. Em cada ponto da compilação, <tt>compile-variable</tt> e <tt>compile-assignment</tt> use o ambiente de tempo de compilação para gerar os endereços lexicais apropriados.</p><p>Exercícios <a href="#%_thm_5.39">5.39</a> através <a href="#%_thm_5.43">5.43</a> descreva como concluir esse esboço da estratégia de endereçamento lexical para incorporar a pesquisa lexical no compilador. Exercício <a href="#%_thm_5.44">5.44</a> descreve outro uso para o ambiente de tempo de compilação.</p><p>
</p><p><a name="%_thm_5.39" id="%_thm_5.39"/>
<b>Exercício 5.39.</b> <a name="%_idx_6442" id="%_idx_6442"/><a name="%_idx_6444" id="%_idx_6444"/>Escreva um procedimento <tt>lexical-address-lookup</tt> que implementa a nova operação de pesquisa. Ele deve receber dois argumentos – um endereço lexical e um ambiente de tempo de execução – e retornar o valor da variável armazenada no endereço lexical especificado. <tt>Lexical-address-lookup</tt> deve sinalizar um erro se o valor da variável for o símbolo <tt>*unassigned*</tt>.<a name="call_footnote_Temp_826" href="#footnote_Temp_826" id="call_footnote_Temp_826"><sup><small>46</small></sup></a> Escreva também um procedimento <tt>lexical-address-set!</tt> que implementa a operação que altera o valor da variável em um endereço lexical especificado.</p><p/><p>
</p><p><a name="%_thm_5.40" id="%_thm_5.40"/>
<b>Exercício 5.40.</b> <a name="%_idx_6450" id="%_idx_6450"/>Modifique o compilador para manter o ambiente de tempo de compilação, conforme descrito acima. Ou seja, adicione um argumento de ambiente de tempo de compilação para <tt>compile</tt> e os vários geradores de código, e estenda-o em <tt>compile-lambda-body</tt>.</p><p/><p>
</p><p><a name="%_thm_5.41" id="%_thm_5.41"/>
<b>Exercício 5.41.</b> <a name="%_idx_6452" id="%_idx_6452"/>Escreva um procedimento <tt>find-variable</tt> que usa como argumento uma variável e um ambiente de tempo de compilação e retorna o endereço lexical da variável em relação a esse ambiente. Por exemplo, no fragmento de programa mostrado acima, o ambiente em tempo de compilação durante a compilação da expressão <<em>e1</em>> é <tt>((y z) (a b c d e) (x y))</tt>. <tt>Find-variable</tt> deve produzir</p><p>
</p><p/><p><tt>(find-variable 'c '((y z) (a b c d e) (x y)))<br/><i>(1 2)</i><br/><br/>
(find-variable 'x '((y z) (a b c d e) (x y)))<br/><i>(2 0)</i><br/><br/>
(find-variable 'w '((y z) (a b c d e) (x y)))<br/><i>not-found</i><br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_5.42" id="%_thm_5.42"/>
<b>Exercício 5.42.</b> Usando <tt>find-variable</tt> do exercício <a href="#%_thm_5.41">5.41</a> reescrever <tt>compile-variable</tt> e <tt>compile-assignment</tt> para emitir instruções de endereço lexical. Nos casos em que <tt>find-variable</tt> retorna <tt>not-found</tt> (ou seja, onde a variável não está no ambiente de tempo de compilação), os geradores de código devem usar as operações do avaliador, como antes, para procurar a ligação. (O único local em que uma variável que não é encontrada no tempo de compilação pode estar é no ambiente global, que faz parte do ambiente de tempo de execução, mas não faz parte do ambiente de tempo de compilação.<a name="call_footnote_Temp_830" href="#footnote_Temp_830" id="call_footnote_Temp_830"><sup><small>47</small></sup></a> Portanto, se desejar, você pode fazer com que as operações do avaliador olhem diretamente no ambiente global, o que pode ser obtido com a operação <tt>(op get-global-environment)</tt>, em vez de procurá-los em todo o ambiente de tempo de execução encontrado em <tt>env</tt>). Teste o compilador modificado em alguns casos simples, como o aninhado <tt>lambda</tt> combinação no início desta seção.</p><p/><p>
</p><p><a name="%_thm_5.43" id="%_thm_5.43"/>
<b>Exercício 5.43.</b> <a name="%_idx_6454" id="%_idx_6454"/><a name="%_idx_6456" id="%_idx_6456"/>Discutimos na seção <a href="book-Z-H-26.html#%_sec_4.1.6">4.1.6</a> que definições internas para estrutura de blocos não devem ser consideradas “reais” <tt>define</tt> s. Em vez disso, um corpo de procedimento deve ser interpretado como se as variáveis internas definidas fossem instaladas como comuns <tt>lambda</tt> variáveis iniciadas com seus valores corretos usando <tt>set!</tt>. Seção <a href="book-Z-H-26.html#%_sec_4.1.6">4.1.6</a> e exercitar <a href="book-Z-H-26.html#%_thm_4.16">4.16</a> mostrou como modificar o interpretador metacircular para fazer isso analisando as definições internas. Modifique o compilador para executar a mesma transformação antes de compilar um corpo do procedimento.</p><p/><p>
</p><p><a name="%_thm_5.44" id="%_thm_5.44"/>
<b>Exercício 5.44.</b> <a name="%_idx_6458" id="%_idx_6458"/><a name="%_idx_6460" id="%_idx_6460"/><a name="%_idx_6462" id="%_idx_6462"/><a name="%_idx_6464" id="%_idx_6464"/>Nesta seção, focamos no uso do ambiente de tempo de compilação para produzir endereços lexicais. Mas existem outros usos para ambientes em tempo de compilação. Por exemplo, no exercício <a href="#%_thm_5.38">5.38</a> aumentamos a eficiência do código compilado por procedimentos primitivos de código aberto. Nossa implementação tratou os nomes dos procedimentos de código aberto como palavras reservadas. Para que um programa renove esse nome, o mecanismo descrito no exercício <a href="#%_thm_5.38">5.38</a> ainda o codificaria como primitivo, ignorando a nova ligação. Por exemplo, considere o procedimento</p><p>
</p><p/><p><tt>(lambda (+ * a b x y)<br/>
(+ (* a x) (* b y)))<br/></tt></p><p/><p>que calcula uma combinação linear de <tt>x</tt> e <tt>y</tt>. Podemos chamá-lo com argumentos <tt>+matrix</tt>, <tt>*matrix</tt> e quatro matrizes, mas o compilador de código aberto ainda codificaria o código <tt>+</tt> e a <tt>*</tt> no <tt>(+ (* a x) (* b y))</tt> como primitivo <tt>+</tt> e <tt>*</tt>. Modifique o compilador de código aberto para consultar o ambiente de tempo de compilação para compilar o código correto para expressões que envolvam os nomes de procedimentos primitivos. (O código funcionará corretamente desde que o programa não funcione <tt>define</tt> ou <tt>set!</tt> esses nomes).</p><p/><p>
<a name="%_sec_5.5.7" id="%_sec_5.5.7"/>
</p><h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.7">5.5.7 Interface do código compilado com o avaliador</a></h3><p>
<a name="%_idx_6466" id="%_idx_6466"/><a name="%_idx_6468" id="%_idx_6468"/><a name="%_idx_6470" id="%_idx_6470"/>Ainda não explicamos como carregar o código compilado na máquina do avaliador ou como executá-lo. Assumiremos que a máquina avaliadora de controle explícito foi definida como na seção <a href="book-Z-H-34.html#%_sec_5.4.4">5.4.4</a>, com as operações adicionais especificadas na nota de rodapé<a href="#footnote_Temp_809">38.</a>. Implementaremos um procedimento <a name="%_idx_6472" id="%_idx_6472"/><tt>compile-and-go</tt> que compila uma expressão do Scheme, carrega o código do objeto resultante na máquina do avaliador e faz com que a máquina execute o código no ambiente global do avaliador, imprima o resultado e insira o laço do controlador do avaliador. Também modificaremos o avaliador para que expressões interpretadas possam chamar procedimentos compilados e também interpretados. Podemos então colocar um procedimento compilado na máquina e usar o avaliador para chamá-lo:</p><p>
</p><p/><p><tt>(compile-and-go<br/>
'(define (factorial n)<br/>
(if (= n 1)<br/>
1<br/>
(* (factorial (- n 1)) n))))<br/><i> ;;; EC-Eval value:</i><br/><i>ok</i><br/><i> ;;; EC-Eval input:</i><br/>
(factorial 5)<br/><i>;;; EC-Eval value:</i><br/><i>120</i><br/></tt></p><p/><p/><p>Para permitir que o avaliador manipule procedimentos compilados (por exemplo, para avaliar a chamada para <tt>factorial</tt> acima), precisamos alterar o código em <tt>apply-dispatch</tt> (seção <a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>), para que ele reconheça procedimentos compilados (diferente dos procedimentos compostos ou primitivos) e transfira o controle diretamente para o ponto de entrada do código compilado:<a name="call_footnote_Temp_833" href="#footnote_Temp_833" id="call_footnote_Temp_833"><sup><small>48</small></sup></a>
</p><p/><p><tt><a name="%_idx_6474" id="%_idx_6474"/>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/>
(test (op compiled-procedure?) (reg proc)) <br/>
(branch (label compiled-apply))<br/>
(goto (label unknown-procedure-type))<br/><a name="%_idx_6476" id="%_idx_6476"/>compiled-apply<br/>
(restore continue)<br/>
(assign val (op compiled-procedure-entry) (reg proc))<br/>
(goto (reg val))<br/></tt></p><p/><p>Observe a restauração de <tt>continue</tt> às <tt>compiled-apply</tt>. Lembre-se de que o avaliador foi organizado de modo que, no <tt>apply-dispatch</tt>, a continuação estaria no topo da pilha. O ponto de entrada do código compilado, por outro lado, espera que a continuação esteja em <tt>continue</tt>, tão <tt>continue</tt> deve ser restaurado antes que o código compilado seja executado.</p><p>Para nos permitir executar algum código compilado ao iniciar a máquina do avaliador, adicionamos uma instrução <tt>branch</tt> no início da máquina do avaliador, o que faz com que a máquina vá para um novo ponto de entrada se o registrador <tt>flag</tt> está definido.<a name="call_footnote_Temp_834" href="#footnote_Temp_834" id="call_footnote_Temp_834"><sup><small>49</small></sup></a></p><p>
</p><p/><p><tt> (branch (label external-entry)) <em>; branches if <tt>flag</tt> is set</em><br/>
read-eval-print-loop<br/>
(perform (op initialize-stack))<br/>
<tt>...</tt></tt></p><p/><p>
<tt>External-entry</tt> assume que a máquina foi iniciada com <tt>val</tt> contendo a localização de uma sequência de instruções que coloca um resultado em <tt>val</tt> e termina com <tt>(goto (reg continue))</tt>. A partir deste ponto de entrada, salta para o local designado por <tt>val</tt>, mas primeiro atribui <tt>continue</tt> para que a execução retorne para <tt>print-result</tt>, que imprime o valor em <tt>val</tt> e depois vai para o início do ciclo de leitura-avaliação-impressão do avaliador.<a name="call_footnote_Temp_835" href="#footnote_Temp_835" id="call_footnote_Temp_835"><sup><small>50.</small></sup></a></p><p>
</p><p/><p><tt><a name="%_idx_6482" id="%_idx_6482"/>external-entry<br/>
(perform (op initialize-stack))<br/>
(assign env (op get-global-environment))<br/>
(assign continue (label print-result))<br/>
(goto (reg val))<br/></tt></p><p/><p>Agora podemos usar o procedimento a seguir para compilar uma definição de procedimento, executar o código compilado e executar o laço leitura-avaliação-impressão para que possamos tentar o procedimento. Como queremos que o código compilado retorne ao local em <tt>continue</tt> com seu resultado em <tt>val</tt>, compilamos a expressão com um destino de <tt>val</tt> e uma ligação de <tt>return</tt>. Para transformar o código do objeto produzido pelo compilador em instruções executáveis para a máquina de registradores do avaliador, usamos o procedimento <tt>assemble</tt> do simulador de máquina de registradores (seção <a href="book-Z-H-32.html#%_sec_5.2.2">5.2.2</a>) Em seguida, iniciamos o registrador <tt>val</tt> para apontar para a lista de instruções, defina o <tt>flag</tt> para que o avaliador vá para <tt>external-entry</tt> e inicie o avaliador.</p><p>
</p><p/><p><tt><a name="%_idx_6484" id="%_idx_6484"/>(define (compile-and-go expression)<br/>
(let ((instructions<br/>
(assemble (statements<br/>
(compile expression 'val 'return))<br/>
eceval)))<br/>
(set! the-global-environment (setup-environment))<br/>
(set-register-contents! eceval 'val instructions)<br/>
(set-register-contents! eceval 'flag true)<br/>
(start eceval)))<br/></tt></p><p/><p/><p>
<a name="%_idx_6486" id="%_idx_6486"/>Se configuramos o monitoramento de pilha, como no final da seção <a href="book-Z-H-34.html#%_sec_5.4.4">5.4.4</a>, podemos examinar o uso da pilha do código compilado:</p><p>
</p><p/><p><tt>(compile-and-go<br/>
'(define (factorial n)<br/>
(if (= n 1)<br/>
1<br/>
(* (factorial (- n 1)) n))))<br/><br/><i>(total-pushes = 0 maximum-depth = 0)</i><br/><i> ;;; EC-Eval value:</i><br/><i>ok</i><br/><i> ;;; EC-Eval input:</i><br/>
(factorial 5)<br/><i>(total-pushes = 31 maximum-depth = 14)</i><br/><i>;;; EC-Eval value:</i><br/><i>120</i><br/></tt></p><p/><p>
<a name="%_idx_6488" id="%_idx_6488"/>Compare este exemplo com a avaliação de <tt>(factorial 5)</tt> usando a versão interpretada do mesmo procedimento, mostrada no final da seção <a href="book-Z-H-34.html#%_sec_5.4.4">5.4.4</a>. A versão interpretada requer 144 empilhamentos e uma profundidade máxima da pilha de 28. Isso ilustra a otimização resultante de nossa estratégia de compilação.</p><p>
<a name="%_sec_Temp_836" id="%_sec_Temp_836"/>
</p><h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_836">Interpretação e compilação</a></h4><p>
<a name="%_idx_6490" id="%_idx_6490"/><a name="%_idx_6492" id="%_idx_6492"/>Com os programas desta seção, agora podemos experimentar estratégias de execução alternativas de interpretação e compilação.<a name="call_footnote_Temp_837" href="#footnote_Temp_837" id="call_footnote_Temp_837"><sup><small>51</small></sup></a> Um interpretador eleva a máquina ao nível do programa do usuário; um compilador reduz o programa do usuário ao nível da linguagem da máquina. Podemos considerar a linguagem Scheme (ou qualquer linguagem de programação) como uma família coerente de abstrações erguidas na linguagem de máquina. Os interpretadores são bons para o desenvolvimento e depuração interativos de programas, pois as etapas de execução do programa são organizadas em termos dessas abstrações e, portanto, são mais inteligíveis para o programador. O código compilado pode ser executado mais rapidamente, pois as etapas de execução do programa são organizadas em termos de linguagem de máquina, e o compilador é livre para fazer otimizações que abrangem as abstrações de nível superior.<a name="call_footnote_Temp_838" href="#footnote_Temp_838" id="call_footnote_Temp_838"><sup><small>52</small></sup></a></p><p>As alternativas de interpretação e compilação também levam a <a name="%_idx_6504" id="%_idx_6504"/>estratégias diferentes para portar linguagens para novos computadores. Suponha que desejamos implementar o Lisp para uma nova máquina. Uma estratégia é começar com o avaliador de controle explícito da seção <a href="book-Z-H-34.html#%_sec_5.4">5.4</a> e traduza suas instruções para instruções da nova máquina. Uma estratégia diferente é começar com o compilador e alterar os geradores de código para que eles gerem código para a nova máquina. A segunda estratégia nos permite executar qualquer programa Lisp na nova máquina, compilando-o primeiro com o compilador em execução no nosso sistema Lisp original e ligando-o a uma versão compilada da biblioteca de tempo de execução.<a name="call_footnote_Temp_839" href="#footnote_Temp_839" id="call_footnote_Temp_839"><sup><small>53</small></sup></a> Melhor ainda, podemos compilar o próprio compilador e executá-lo na nova máquina para compilar outros programas Lisp.<a name="call_footnote_Temp_840" href="#footnote_Temp_840" id="call_footnote_Temp_840"><sup><small>54</small></sup></a> Ou podemos compilar um dos interpretadores da seção <a href="book-Z-H-26.html#%_sec_4.1">4.1</a> para produzir um interpretador executado na nova máquina.</p><p>
</p><p><a name="%_thm_5.45" id="%_thm_5.45"/>
<b>Exercício 5.45.</b> <a name="%_idx_6506" id="%_idx_6506"/><a name="%_idx_6508" id="%_idx_6508"/>Ao comparar as operações de pilha usadas pelo código compilado com as operações de pilha usadas pelo avaliador para o mesmo cálculo, podemos determinar até que ponto o compilador otimiza o uso da pilha, tanto em velocidade (reduzindo o número total de operações de pilha) quanto em no espaço (reduzindo a profundidade máxima da pilha). A comparação desse uso otimizado da pilha com o desempenho de uma máquina para fins especiais para o mesmo cálculo fornece algumas indicações da qualidade do compilador.</p><p>
</p><p/><p>a. Exercício <a href="book-Z-H-34.html#%_thm_5.27">5.27</a> solicitou que você determinasse, em função da <em>n</em>, o número de empilhamentos e a profundidade máxima da pilha necessária ao avaliador para calcular <em>n</em>! usando o procedimento fatorial recursivo dado acima. Exercício <a href="book-Z-H-32.html#%_thm_5.14">5.14</a> solicitou que você fizesse as mesmas medições para a máquina fatorial para fins especiais mostrada na figura <a href="book-Z-H-31.html#%_fig_5.11">5.11</a>. Agora execute a mesma análise usando o procedimento compilado <tt>factorial</tt>.</p><p>Pegue a proporção do número de empilhamentos na versão compilada para o número de empilhamentos na versão interpretada e faça o mesmo para a profundidade máxima da pilha. Como o número de operações e a profundidade da pilha usada para calcular <em>n</em>! são lineares <em>n</em>, essas taxas devem aproximar-se das constantes <em>n</em> torna-se grande. O que são essas constantes? Da mesma forma, encontre as proporções de uso da pilha na máquina para fins especiais e o uso na versão interpretada.</p><p>Compare as proporções para código de finalidade especial versus código interpretado com as proporções para código compilado versus código interpretado. Você deve achar que a máquina para fins especiais se sai muito melhor que o código compilado, pois o código do controlador personalizado deve ser muito melhor do que o produzido pelo nosso compilador rudimentar de uso geral.</p><p>
</p><p/><p>b. Você pode sugerir melhorias no compilador que o ajudem a gerar código com desempenho mais próximo da versão personalizada?</p><p/><p>
</p><p><a name="%_thm_5.46" id="%_thm_5.46"/>
<b>Exercício 5.46.</b> <a name="%_idx_6510" id="%_idx_6510"/><a name="%_idx_6512" id="%_idx_6512"/>Realize uma análise como a do exercício <a href="#%_thm_5.45">5.45</a> determinar a eficácia da compilação do procedimento de Fibonacci recursivo em árvore</p><p>
</p><p/><p><tt>(define (fib n)<br/>
(if (< n 2)<br/>
n<br/>
(+ (fib (- n 1)) (fib (- n 2)))))<br/></tt></p><p/><p>comparado com a eficácia do uso da máquina de Fibonacci para fins especiais <a href="book-Z-H-31.html#%_fig_5.12">5.12</a>. (Para medir o desempenho interpretado, consulte o exercício <a href="book-Z-H-34.html#%_thm_5.29">5.29</a>). Para Fibonacci, o recurso de tempo usado não é linear em <em>n</em>; portanto, as proporções das operações de pilha não se aproximarão de um valor limite independente de <em>n</em>.</p><p/><p>
</p><p><a name="%_thm_5.47" id="%_thm_5.47"/>
<b>Exercício 5.47.</b> Esta seção descreveu como modificar o avaliador de controle explícito para que o código interpretado possa chamar procedimentos compilados. Mostre como modificar o compilador para que os procedimentos compilados possam chamar não apenas procedimentos primitivos e procedimentos compilados, mas também procedimentos interpretados. Isso requer modificação <tt>compile-procedure-call</tt> para lidar com o caso de procedimentos compostos (interpretados). Certifique-se de lidar com tudo as mesmas combinações <tt>target</tt> e <tt>linkage</tt> como em <tt>compile-proc-appl</tt>. Para executar o aplicativo de procedimento real, o código precisa ir para o ponto de entrada <tt>compound-apply</tt> do avaliador. Esse rótulo não pode ser diretamente referenciado no código do objeto (pois o montador exige que todos os rótulos referenciados pelo código que monta sejam definidos lá), portanto, adicionaremos um registrador chamado <tt>compapp</tt> à máquina do avaliador para manter esse ponto de entrada e adicione uma instrução para iniciá-lo:</p><p/><p><tt> (assign compapp (label compound-apply))<br/>
(branch (label external-entry)) <em>; branches if <tt>flag</tt> is set</em><br/>
read-eval-print-loop<br/>
<tt>...</tt></tt></p><p/><p>Para testar seu código, comece definindo um procedimento <tt>f</tt> que chama um procedimento <tt>g</tt>. Use <tt>compile-and-go</tt> para compilar a definição de <tt>f</tt> e inicie o avaliador. Agora, digitando no avaliador, defina <tt>g</tt> e tente ligar <tt>f</tt>.</p><p/><p>
</p><p><a name="%_thm_5.48" id="%_thm_5.48"/>
<b>Exercício 5.48.</b> <a name="%_idx_6514" id="%_idx_6514"/>A interface <tt>compile-and-go</tt> implementada nesta seção é estranha, pois o compilador pode ser chamado apenas uma vez (quando a máquina do avaliador é iniciada). Melhore a interface do compilador-interpretador fornecendo uma primitiva <tt>compile-and-run</tt> que pode ser chamada de dentro do avaliador de controle explícito da seguinte maneira:</p><p>
</p><p/><p><tt><i>;;; EC-Eval input:</i><br/>
(compile-and-run<br/>
'(define (factorial n)<br/>
(if (= n 1)<br/>
1<br/>
(* (factorial (- n 1)) n))))<br/><i>;;; EC-Eval value:</i><br/><i>ok</i><br/><i>;;; EC-Eval input:</i><br/>
(factorial 5)<br/><i>;;; EC-Eval value:</i><br/><i>120</i><br/></tt></p><p/><p>
</p><p/><p>
</p><p><a name="%_thm_5.49" id="%_thm_5.49"/>
<b>Exercício 5.49.</b> Como alternativa ao uso do laço de leitura-avaliação-impressão do avaliador de controle explícito, projete uma máquina de registradores que execute um laço de leitura-compilação-execução-impressão. Ou seja, a máquina deve executar um laço que lê uma expressão, a compila, monta e executa o código resultante e imprime o resultado. Isso é fácil de executar em nossa configuração simulada, pois podemos organizar os procedimentos <tt>compile</tt> e <tt>assemble</tt> como “operações de máquina de registradores”.</p><p/><p>
</p><p><a name="%_thm_5.50" id="%_thm_5.50"/>
<b>Exercício 5.50.</b> <a name="%_idx_6516" id="%_idx_6516"/>Use o compilador para compilar o avaliador metacircular da seção <a href="book-Z-H-26.html#%_sec_4.1">4.1</a> e execute este programa usando o simulador de máquina de registradores. (Para compilar mais de uma definição por vez, você pode empacotar as definições em um <tt>begin</tt>). O interpretador resultante será executado muito lentamente por causa dos vários níveis de interpretação, mas fazer com que todos os detalhes funcionem é um exercício instrutivo.</p><p/><p>
</p><p><a name="%_thm_5.51" id="%_thm_5.51"/>
<b>Exercício 5.51.</b> <a name="%_idx_6518" id="%_idx_6518"/>Desenvolva uma implementação rudimentar do Scheme em C (ou em alguma outra linguagem de baixo nível de sua escolha) traduzindo o avaliador de controle explícito da seção <a href="book-Z-H-34.html#%_sec_5.4">5.4</a> para C. Para executar esse código, você também precisará fornecer rotinas apropriadas de alocação de armazenamento e outro suporte em tempo de execução.</p><p/><p>
</p><p><a name="%_thm_5.52" id="%_thm_5.52"/>
<b>Exercício 5.52.</b> <a name="%_idx_6520" id="%_idx_6520"/><a name="%_idx_6522" id="%_idx_6522"/><a name="%_idx_6524" id="%_idx_6524"/>Como contraponto ao exercício <a href="#%_thm_5.51">5.51</a>, modifique o compilador para compilar os procedimentos do Scheme em sequências de instruções em C. Compile o avaliador metacircular da seção <a href="book-Z-H-26.html#%_sec_4.1">4.1</a> para produzir um interpretador do Scheme escrito em C.</p><p>
</p><p>
</p><p/><div class="smallprint"><hr/></div><p>
</p><div class="footnote"><p><a name="footnote_Temp_794" href="#call_footnote_Temp_794" id="footnote_Temp_794"><sup><small>33</small></sup></a> Esta é uma afirmação teórica. Não afirmamos que os caminhos de dados do avaliador são um conjunto de caminhos de dados particularmente conveniente ou eficiente para um computador de uso geral. Por exemplo, eles não são muito bons para implementar cálculos de ponto flutuante de alto desempenho ou cálculos que manipulam intensamente vetores de bits.</p><p><a name="footnote_Temp_795" href="#call_footnote_Temp_795" id="footnote_Temp_795"><sup><small>34</small></sup></a> Na verdade, a máquina que executa o código compilado pode ser mais simples que a máquina do interpretador, pois <a name="%_idx_6220" id="%_idx_6220"/>não usaremos os registradores <tt>exp</tt> e <tt>unev</tt>. O interpretador os usava para conter partes de expressões não avaliadas. Com o compilador, no entanto, essas expressões são incorporadas ao código compilado que a máquina de registradores executará. Pela mesma razão, <a name="%_idx_6222" id="%_idx_6222"/>não precisamos das operações da máquina que lidam com a sintaxe da expressão. Porém, o código compilado usará algumas operações adicionais da máquina (para representar objetos de procedimento compilados) que não apareceram na máquina avaliadora de controle explícito.</p><p><a name="footnote_Temp_797" href="#call_footnote_Temp_797" id="footnote_Temp_797"><sup><small>35</small></sup></a> Observe, no entanto, que nosso compilador é um programa do Scheme, e os procedimentos de sintaxe que ele usa para manipular expressões são os procedimentos reais do Scheme usados com o avaliador metacircular. Para o avaliador de controle explícito, por outro lado, assumimos que operações de sintaxe equivalentes estavam disponíveis como operações para a máquina de registradores. (Obviamente, quando simulamos a máquina de registradores no Scheme, usamos os procedimentos reais do Scheme na simulação da máquina de registrador).</p><p><a name="footnote_Temp_803" href="#call_footnote_Temp_803" id="footnote_Temp_803"><sup><small>36</small></sup></a> Este procedimento usa um recurso do Lisp chamado <em><a name="%_idx_6280" id="%_idx_6280"/><a name="%_idx_6282" id="%_idx_6282"/><a name="%_idx_6284" id="%_idx_6284"/><a name="%_idx_6286" id="%_idx_6286"/><a name="%_idx_6288" id="%_idx_6288"/><a name="%_idx_6290" id="%_idx_6290"/>acento grave</em> (ou <em>notação de Quine</em>) é útil para construir listas. Preceder uma lista com um símbolo de acento grave é semelhante a citá-la, exceto que qualquer elemento na lista sinalizada com vírgula é avaliada.</p><p>Por exemplo, se o valor de <tt>linkage</tt> é o símbolo <tt>branch25</tt>, então a expressão <tt>`((goto (label ,linkage)))</tt> avalia para a lista <tt>((goto (label branch25)))</tt>. Da mesma forma, se o valor de <tt>x</tt> é a lista <tt>(a b c)</tt>, então <tt>`(1 2 ,(car x))</tt> avalia para a lista <tt>(1 2 a)</tt>.</p><p><a name="footnote_Temp_806" href="#call_footnote_Temp_806" id="footnote_Temp_806"><sup><small>37</small></sup></a> Não podemos simplesmente usar os rótulos <tt>true-branch</tt>, <tt>false-branch</tt> e <tt>after-if</tt> como mostrado acima, pois pode haver mais de um <tt>if</tt> no programa. <a name="%_idx_6318" id="%_idx_6318"/>O compilador usa o procedimento <tt>make-label</tt> para gerar etiquetas. <tt>Make-label</tt> recebe um símbolo como argumento e retorna um novo símbolo que começa com o símbolo fornecido. Por exemplo, chamadas sucessivas para <tt>(make-label 'a)</tt> retornaria <tt>a1</tt>, <tt>a2</tt>, e assim por diante. <tt>Make-label</tt> pode ser implementado de maneira semelhante à geração de nomes de variáveis exclusivos na linguagem de consulta, da seguinte maneira:</p><p/><p><tt>(define label-counter 0)<br/><br/>
(define (new-label-number)<br/>
(set! label-counter (+ 1 label-counter))<br/>
label-counter)<br/><br/><a name="%_idx_6320" id="%_idx_6320"/><a name="%_idx_6322" id="%_idx_6322"/>(define (make-label name)<br/>
(string->symbol<br/>
(string-append (symbol->string name)<br/>
(number->string (new-label-number)))))<br/></tt></p><p/><p>
</p><p><a name="footnote_Temp_809" href="#call_footnote_Temp_809" id="footnote_Temp_809"><sup><small>38</small></sup></a> Precisamos de operações de máquina para implementar uma estrutura de dados para representar procedimentos compilados, análoga à estrutura para procedimentos compostos descritos na seção <a href="book-Z-H-26.html#%_sec_4.1.3">4.1.3</a>:</p><p/><p><tt><a name="%_idx_6332" id="%_idx_6332"/>(define (make-compiled-procedure entry env)<br/>
(list 'compiled-procedure entry env))<br/><br/><a name="%_idx_6334" id="%_idx_6334"/>(define (compiled-procedure? proc)<br/>
(tagged-list? proc 'compiled-procedure))<br/><br/><a name="%_idx_6336" id="%_idx_6336"/>(define (compiled-procedure-entry c-proc) (cadr c-proc))<br/><br/><a name="%_idx_6338" id="%_idx_6338"/>(define (compiled-procedure-env c-proc) (caddr c-proc))<br/></tt></p><p/><p>
</p><p><a name="footnote_Temp_812" href="#call_footnote_Temp_812" id="footnote_Temp_812"><sup><small>39</small></sup></a> Na verdade, sinalizamos um erro quando o alvo não está <tt>val</tt> e a ligação é <tt>return</tt>, pois o único local que solicitamos <tt>return</tt> ligações está nos procedimentos de compilação, e nossa convenção é que os procedimentos retornam seus valores em <tt>val</tt>.</p><p><a name="footnote_Temp_813" href="#call_footnote_Temp_813" id="footnote_Temp_813"><sup><small>40</small></sup></a> Fazendo um <a name="%_idx_6356" id="%_idx_6356"/>compilador gerar código recursivo de cauda pode parecer uma ideia direta. Mas a maioria dos compiladores para linguagens comuns, incluindo C e Pascal, não faz isso e, portanto, essas linguagens não podem representar processos iterativos apenas em termos de chamada de procedimento. A dificuldade com <a name="%_idx_6358" id="%_idx_6358"/><a name="%_idx_6360" id="%_idx_6360"/><a name="%_idx_6362" id="%_idx_6362"/>a recursão de cauda nessas linguagens é que suas implementações usam a pilha para armazenar argumentos de procedimento e variáveis locais, bem como endereços de retorno. As implementações do Scheme descritas neste livro armazenam argumentos e variáveis na memória para serem coletados como lixo. A razão para usar a pilha para variáveis e argumentos é que ela evita a necessidade de coleta de lixo em linguagens que não a exigiriam e, geralmente, acredita-se ser mais eficiente. Compiladores Lisp sofisticados podem, de fato, usar a pilha para argumentos sem destruir a recursão de cauda. (Veja <a name="%_idx_6364" id="%_idx_6364"/>Hanson, 1990, para uma descrição). Há também um debate sobre se a alocação de pilha é realmente mais eficiente que a coleta de lixo, mas os detalhes parecem depender de pontos finos da arquitetura de computadores. (Veja <a name="%_idx_6366" id="%_idx_6366"/>Appel 1987 e <a name="%_idx_6368" id="%_idx_6368"/><a name="%_idx_6370" id="%_idx_6370"/>Miller e Rozas 1994 por pontos de vista opostos sobre esse assunto).</p><p><a name="footnote_Temp_814" href="#call_footnote_Temp_814" id="footnote_Temp_814"><sup><small>41</small></sup></a> A variável <a name="%_idx_6372" id="%_idx_6372"/><tt>all-regs</tt> está ligado à lista de nomes de todos os registradores:</p><p/><p><tt><a name="%_idx_6374" id="%_idx_6374"/>(define all-regs '(env proc val argl continue))<br/></tt></p><p/><p>
</p><p><a name="footnote_Temp_815" href="#call_footnote_Temp_815" id="footnote_Temp_815"><sup><small>42</small></sup></a> Observe que <tt>preserving</tt> chamadas <tt>append</tt> com três <a name="%_idx_6396" id="%_idx_6396"/>argumentos. Embora a definição de <tt>append</tt> mostrado neste livro aceita apenas dois argumentos, o Scheme fornece um procedimento padrão <tt>append</tt> que requer um número arbitrário de argumentos.</p><p><a name="footnote_Temp_822" href="#call_footnote_Temp_822" id="footnote_Temp_822"><sup><small>43</small></sup></a> Usamos o mesmo símbolo <tt>+</tt> aqui para indicar o procedimento da linguagem de origem e a operação da máquina. Em geral, não haverá uma correspondência individual entre primitivas da linguagem de origem e primitivas da máquina.</p><p><a name="footnote_Temp_823" href="#call_footnote_Temp_823" id="footnote_Temp_823"><sup><small>44</small></sup></a> Transformar as primitivas em palavras reservadas é geralmente uma péssima ideia, pois um usuário não pode reconfigurar esses nomes para procedimentos diferentes. Além disso, se adicionarmos palavras reservadas a um compilador em uso, os programas existentes que definem procedimentos com esses nomes deixarão de funcionar. Veja o exercício <a href="#%_thm_5.44">5.44</a> para ideias sobre como evitar esse problema.</p><p><a name="footnote_Temp_824" href="#call_footnote_Temp_824" id="footnote_Temp_824"><sup><small>45</small></sup></a> Isso não é verdade se permitirmos definições internas, a menos que as varremos. Veja o exercício <a href="#%_thm_5.43">5.43</a>.</p><p><a name="footnote_Temp_826" href="#call_footnote_Temp_826" id="footnote_Temp_826"><sup><small>46</small></sup></a> Esta é a modificação na pesquisa de variáveis <a name="%_idx_6446" id="%_idx_6446"/><a name="%_idx_6448" id="%_idx_6448"/>necessária, se implementarmos o método de verificação para eliminar definições internas (exercício <a href="#%_thm_5.43">5.43</a>) Precisamos eliminar essas definições para que o endereçamento lexical funcione.</p><p><a name="footnote_Temp_830" href="#call_footnote_Temp_830" id="footnote_Temp_830"><sup><small>47</small></sup></a> Endereços lexicais não podem ser usados para acessar variáveis no ambiente global, pois esses nomes podem ser definidos e redefinidos interativamente a qualquer momento. Com as definições internas varridas, como no exercício <a href="#%_thm_5.43">5.43</a>, as únicas definições que o compilador vê são as de nível superior, que atuam no ambiente global. A compilação de uma definição não faz com que o nome definido seja inserido no ambiente de tempo de compilação.</p><p><a name="footnote_Temp_833" href="#call_footnote_Temp_833" id="footnote_Temp_833"><sup><small>48</small></sup></a> Obviamente, os procedimentos compilados e os interpretados são compostos (não primitivos). Para compatibilidade com a terminologia usada no avaliador de controle explícito, nesta seção, usaremos “composto” para significar interpretado (em oposição a compilado).</p><p><a name="footnote_Temp_834" href="#call_footnote_Temp_834" id="footnote_Temp_834"><sup><small>49</small></sup></a> Agora que a máquina avaliadora começa com um <tt>branch</tt>, devemos sempre iniciar o registrador <tt>flag</tt> antes de iniciar a máquina do avaliador. Para iniciar a máquina em seu ciclo de leitura-avaliação-impressão comum, poderíamos usar</p><p/><p><tt><a name="%_idx_6478" id="%_idx_6478"/>(define (start-eceval)<br/>
(set! the-global-environment (setup-environment))<br/>
(set-register-contents! eceval 'flag false)<br/>
(start eceval))<br/></tt></p><p/><p>
</p><p><a name="footnote_Temp_835" href="#call_footnote_Temp_835" id="footnote_Temp_835"><sup><small>50</small></sup></a> Como um procedimento compilado é um objeto que o sistema pode tentar imprimir, também modificamos a operação de impressão do sistema <tt>user-print</tt> (da seção <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>) para que ele não tente imprimir os componentes de um procedimento compilado:</p><p/><p><tt><a name="%_idx_6480" id="%_idx_6480"/>(define (user-print object)<br/>
(cond ((compound-procedure? object)<br/>
(display (list 'compound-procedure<br/>
(procedure-parameters object)<br/>
(procedure-body object)<br/>
'<procedure-env>)))<br/>
((compiled-procedure? object)<br/>
(display '<compiled-procedure>))<br/>
(else (display object))))<br/></tt></p><p/><p>
</p><p><a name="footnote_Temp_837" href="#call_footnote_Temp_837" id="footnote_Temp_837"><sup><small>51</small></sup></a> Podemos melhorar ainda mais estendendo o compilador para permitir que o código compilado chame procedimentos interpretados. Veja o exercício <a href="#%_thm_5.47">5.47</a>.</p><p><a name="footnote_Temp_838" href="#call_footnote_Temp_838" id="footnote_Temp_838"><sup><small>52</small></sup></a> Independentemente da estratégia de execução, <a name="%_idx_6494" id="%_idx_6494"/>sofrerão uma sobrecarga significativa se insistirmos que os erros encontrados na execução de um programa do usuário sejam detectados e sinalizados, em vez de serem autorizados a matar o sistema ou produzir respostas erradas. Por exemplo, uma referência de matriz fora dos limites pode ser detectada verificando a validade da referência antes de executá-la. A sobrecarga da verificação, no entanto, pode ser muitas vezes o custo da própria referência da matriz, e um programador deve considerar a velocidade e a segurança para determinar se essa verificação é desejável. Um bom compilador deve ser capaz de produzir código com essas verificações, evitar verificações redundantes e permitir que os programadores controlem a extensão e o tipo de verificação de erro no código compilado.</p><p>
<a name="%_idx_6496" id="%_idx_6496"/>Os compiladores de linguagens populares, como C e C ++, dificilmente executam operações de verificação de erros no código em execução, para que sejam executadas o mais rápido possível. Como resultado, cabe aos programadores fornecer explicitamente a verificação de erros. Infelizmente, as pessoas geralmente negligenciam isso, mesmo em aplicações críticas em que a velocidade não é uma restrição. Seus programas levam vidas rápidas e perigosas. Por exemplo, o notório <a name="%_idx_6498" id="%_idx_6498"/>O “verme” que paralisou a Internet em 1988 explorou o <a name="%_idx_6500" id="%_idx_6500"/>UNIX<sup><em>T</em><em>M</em></sup> falha do sistema operacional em verificar se o buffer de entrada possui <a name="%_idx_6502" id="%_idx_6502"/>transbordou no daemon do dedo. (Veja Spafford 1989).</p><p><a name="footnote_Temp_839" href="#call_footnote_Temp_839" id="footnote_Temp_839"><sup><small>53</small></sup></a> Obviamente, com a interpretação ou a estratégia de compilação, devemos também implementar a alocação, a entrada e a saída de armazenamento da nova máquina e todas as várias operações que consideramos “primitivas” em nossa discussão sobre o avaliador e o compilador. Uma estratégia para minimizar o trabalho aqui é escrever o maior número possível de operações no Lisp e compilá-las para a nova máquina. Por fim, tudo se reduz a um pequeno núcleo (como a coleta de lixo e o mecanismo para aplicar as primitivas reais da máquina) que é codificado manualmente para a nova máquina.</p><p><a name="footnote_Temp_840" href="#call_footnote_Temp_840" id="footnote_Temp_840"><sup><small>54</small></sup></a> Essa estratégia leva a divertidos testes de correção do compilador, como verificar se a compilação de um programa na nova máquina, usando o compilador compilado, é idêntica à compilação do programa no sistema Lisp original. Rastrear a fonte das diferenças é divertido, mas geralmente frustrante, pois os resultados são extremamente sensíveis a detalhes minúsculos.</p></div>
</body>
</html>