-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbook-Z-H-35.html
2371 lines (2103 loc) · 147 KB
/
book-Z-H-35.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
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
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4n,
(c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>
<p><div class=navigation>[Go to <a href="book.html">first</a>,
<a href="book-Z-H-34.html">previous</a>,
<a href="book-Z-H-36.html">next</a> page; <a href="book-Z-H-4.html#%_toc_start">contents</a>; <a href="book-Z-H-38.html#%_index_start">index</a>]</div><p>
<a name="%_sec_5.5"></a>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_5.5">5.5 Compilation</a></h2><p>
<a name="%_idx_6194"></a>
The explicit-control evaluator of section <a href="book-Z-H-34.html#%_sec_5.4">5.4</a> is a
register machine whose controller interprets Scheme programs. In this
section we will see how to run Scheme programs on a register machine
whose controller is not a Scheme interpreter.<p>
<a name="%_idx_6196"></a><a name="%_idx_6198"></a>The explicit-control evaluator machine is universal -- it can carry out
any computational process that can be described in Scheme. The
evaluator's controller orchestrates the use of its data paths to
perform the desired computation. Thus, the evaluator's data paths are
universal: They are sufficient to perform any computation we desire,
given an appropriate controller.<a name="call_footnote_Temp_652" href="#footnote_Temp_652"><sup><small>33</small></sup></a><p>
<a name="%_idx_6200"></a><a name="%_idx_6202"></a>Commercial general-purpose computers are register machines organized
around a collection of registers and operations that constitute
an efficient and convenient universal set of data paths.
The controller for a general-purpose machine is an interpreter for
a register-machine language like the one we have been using. This
language is called the <a name="%_idx_6204"></a><em>native language</em> of the machine, or simply
<a name="%_idx_6206"></a><em>machine language</em>. Programs written in machine language are
sequences of instructions that use the machine's data paths.
For example, the <a name="%_idx_6208"></a>explicit-control evaluator's instruction sequence
can be thought of as a machine-language program for a general-purpose
computer rather than as the controller for a specialized interpreter
machine.<p>
<a name="%_idx_6210"></a><a name="%_idx_6212"></a>There are two common strategies for bridging the gap between
higher-level languages and register-machine languages. The
explicit-control evaluator illustrates the
strategy of interpretation. An interpreter written in the native
language of a machine configures the machine to execute programs
written in a language (called the <a name="%_idx_6214"></a><em>source language</em>) that may
differ from the native language of the machine performing the
evaluation. The primitive procedures of the source language are
implemented as a library of subroutines written in the native language
of the given machine. A program to be interpreted (called the <a name="%_idx_6216"></a><em>source program</em>) is represented as a data structure. The interpreter
traverses this data structure, analyzing the source program. As it
does so, it simulates the intended behavior of the source program by
calling appropriate primitive subroutines from the library.<p>
In this section, we explore the alternative strategy of <em>compilation</em>. A compiler for a given source language and machine
translates a source program into an equivalent program (called the
<a name="%_idx_6218"></a><em>object program</em>) written in the machine's native language. The
compiler that we implement in this section translates programs written
in Scheme into sequences of instructions to be executed using
the explicit-control evaluator machine's data paths.<a name="call_footnote_Temp_653" href="#footnote_Temp_653"><sup><small>34</small></sup></a><p>
Compared with interpretation, compilation can provide a great increase
in the efficiency of program execution, as we will explain below in
the overview of the compiler. On the other hand, an interpreter
provides a more powerful environment for interactive program
development and debugging, because the source program being executed
is available at run time to be examined and modified. In addition,
because the entire library of primitives is present, new programs can
be constructed and added to the system during debugging.<p>
In view of the complementary advantages of compilation and
interpretation, modern program-development environments pursue a mixed
strategy. Lisp interpreters are generally organized so that
interpreted procedures and compiled procedures can call each other.
This enables a programmer to compile those parts of a program that are
assumed to be debugged, thus gaining the efficiency advantage of
compilation, while retaining the interpretive mode of execution for
those parts of the program that are in the flux of interactive
development and debugging. In
section <a href="#%_sec_5.5.7">5.5.7</a>, after we have implemented
the compiler, we will show how to interface it with our interpreter to
produce an integrated interpreter-compiler development system.<p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">An overview of the compiler</a></h4><p>
<a name="%_idx_6224"></a><a name="%_idx_6226"></a>
Our compiler is much like our interpreter, both in its structure and in
the function it performs. Accordingly, the mechanisms used by the
compiler for analyzing expressions will be similar to those used by
the interpreter. Moreover, to make it easy to interface compiled and
interpreted code, we will design the compiler to generate code that
obeys the same conventions of <a name="%_idx_6228"></a>register usage as the interpreter: The
environment will be kept in the <tt>env</tt> register, argument lists
will be accumulated in <tt>argl</tt>, a procedure to be applied will be
in <tt>proc</tt>, procedures will return their answers in <tt>val</tt>,
and the location to which a procedure should return will be kept in
<tt>continue</tt>.
In general, the compiler translates a source program into an object
program that performs essentially the same register operations as
would the interpreter in evaluating the same source program.<p>
This description suggests a strategy for implementing a rudimentary
compiler: We traverse the expression in the same way the
interpreter does. When we encounter a register instruction that the
interpreter would perform in evaluating the expression, we do not
execute the instruction but instead accumulate it into a sequence. The
resulting sequence of instructions will be the object code. Observe
the <a name="%_idx_6230"></a><a name="%_idx_6232"></a>efficiency advantage of compilation over interpretation. Each
time the interpreter evaluates an expression -- for example,
<tt>(f 84 96)</tt> -- it performs the work of
classifying the expression (discovering that this
is a procedure application) and testing for the end of the operand list
(discovering that there are two operands). With a
compiler, the expression is analyzed only once, when the
instruction sequence is generated at compile time. The object code
produced by the compiler contains only the instructions that evaluate
the operator and the two operands, assemble the argument list,
and apply the procedure (in <tt>proc</tt>) to the arguments (in <tt>argl</tt>).<p>
<a name="%_idx_6234"></a>This is the same kind of optimization we implemented in the
analyzing evaluator of section <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>.
But there are further opportunities to gain efficiency in compiled code.
As the interpreter runs, it follows a process that must be applicable
to any expression in the language. In contrast, a given segment of
compiled code is meant to execute some particular expression. This
can make a big difference, for example in the use of the stack to
save registers. When the interpreter evaluates an expression, it must
be prepared for any contingency. Before evaluating a subexpression,
the interpreter saves all
registers that will be needed later, because
the subexpression might require an arbitrary evaluation.
A compiler, on the other hand, can exploit the structure of the
particular expression it is processing to generate code that avoids
unnecessary stack operations.<p>
As a case in point, consider the combination <tt>(f 84 96)</tt>. Before
the interpreter evaluates the operator of the combination, it prepares
for this evaluation by saving the registers containing the operands
and the environment, whose values will be needed later. The
interpreter then evaluates the operator to obtain the result in <tt>val</tt>, restores the saved registers, and finally moves the result from
<tt>val</tt> to <tt>proc</tt>. However, in the particular expression we are
dealing with, the operator is the symbol <tt>f</tt>, whose evaluation is
accomplished by the machine operation <tt>lookup-variable-value</tt>,
which does not alter any registers. The compiler that we implement in
this section will take advantage of this fact and generate code that
evaluates the operator using the instruction
<p><tt>(assign proc (op lookup-variable-value) (const f) (reg env))<br>
</tt><p>
This code not only avoids the unnecessary saves and
restores but also assigns the value of the lookup directly to
<tt>proc</tt>, whereas the interpreter would obtain the result in <tt>val</tt>
and then move this to <tt>proc</tt>.<p>
A compiler can also optimize access to the environment. Having
analyzed the code, the compiler can in many cases know in which frame
a particular variable will be located and access that frame directly,
rather than performing the <tt>lookup-variable-value</tt> search. We
will discuss how to implement such variable access in
section <a href="#%_sec_5.5.6">5.5.6</a>. Until then, however, we will
focus on the kind of register and stack optimizations described above.
There are many other optimizations that can be performed by a
compiler, such as coding primitive operations ``in line'' instead of
using a general <tt>apply</tt> mechanism (see
exercise <a href="#%_thm_5.38">5.38</a>); but we will not emphasize these here.
Our main goal in this section is to illustrate the compilation process
in a simplified (but still interesting) context.<p>
<a name="%_sec_5.5.1"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.1">5.5.1 Structure of the Compiler</a></h3><p>
<a name="%_idx_6236"></a>
<a name="%_idx_6238"></a>In section <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a> we modified our original
metacircular interpreter to separate analysis from execution. We
analyzed each expression to produce an execution procedure that took
an environment as argument and performed the required operations. In
our compiler, we will do essentially the same analysis. Instead of
producing execution procedures, however, we will generate sequences of
instructions to be run by our register machine.<p>
The procedure <tt>compile</tt> is the top-level dispatch in the compiler.
It corresponds to the <tt>eval</tt> procedure of
section <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>, the <tt>analyze</tt> procedure of
section <a href="book-Z-H-26.html#%_sec_4.1.7">4.1.7</a>, and the <tt>eval-dispatch</tt>
entry point of the explicit-control-evaluator in
section <a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>.
The compiler, like the interpreters, uses the <a name="%_idx_6240"></a>expression-syntax
procedures defined in section <a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a>.<a name="call_footnote_Temp_654" href="#footnote_Temp_654"><sup><small>35</small></sup></a>
<tt>Compile</tt> performs a case
analysis on the syntactic type of the expression to be compiled. For
each type of expression, it dispatches to a specialized <a name="%_idx_6242"></a><em>code
generator</em>:<p>
<p><tt><a name="%_idx_6244"></a>(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>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Targets and linkages</a></h4><p>
<a name="%_idx_6246"></a><tt>Compile</tt> and the code generators that it calls take two arguments
in addition to the expression to compile. There is a <a name="%_idx_6248"></a><em>target</em>,
which specifies the register in which the compiled code is to return
the value of the expression. There is also a <a name="%_idx_6250"></a><em>linkage
descriptor</em>, which describes how the code resulting from the
compilation of the expression should proceed when it has finished its
execution. The linkage descriptor can require that the code do one of
the following three things:<p>
<p><ul>
<li>continue at the next instruction in sequence (this is
<a name="%_idx_6252"></a>specified by the linkage descriptor <tt>next</tt>),<p>
<li>return from the procedure being compiled (this is specified
<a name="%_idx_6254"></a>by the linkage descriptor <tt>return</tt>), or<p>
<li>jump to a named entry point (this is specified by using the
designated label as the linkage descriptor).
</ul><p><p>
For example, compiling the expression <tt>5</tt> (which is
self-evaluating) with a target of the <tt>val</tt> register and a
linkage of <tt>next</tt> should produce the instruction<p>
<p><tt>(assign val (const 5))<br>
</tt><p>
Compiling the same expression with a linkage of <tt>return</tt> should
produce the instructions<p>
<p><tt>(assign val (const 5))<br>
(goto (reg continue))<br>
</tt><p>
In the first case, execution will continue with the next instruction
in the sequence. In the second case, we will return from a procedure
call. In both cases, the value of the expression will be placed into
the target <tt>val</tt> register.<p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Instruction sequences and stack usage</a></h4><p>
<p>
<a name="%_idx_6256"></a><a name="%_idx_6258"></a>Each code generator returns an <em>instruction sequence</em> containing
the object code it has generated for the expression. Code generation
for a compound expression is accomplished by combining the output from
simpler code generators for component expressions, just as
evaluation of a compound expression is accomplished by evaluating the
component expressions.<p>
The simplest method for combining instruction sequences is a procedure
<a name="%_idx_6260"></a>called <tt>append-instruction-sequences</tt>. It takes as arguments any
number of instruction sequences that are to be executed sequentially;
it appends them and returns the combined sequence. That is, if
<<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>> and <<em><em>s</em><em>e</em><em>q</em><sub>2</sub></em>> are sequences of instructions, then
evaluating
<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>
produces the sequence
<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>
<a name="%_idx_6262"></a>Whenever registers might need to be saved, the compiler's code generators use
<a name="%_idx_6264"></a><tt>preserving</tt>, which is a more subtle method for combining
instruction sequences. <tt>Preserving</tt> takes three arguments: a set
of registers and two instruction sequences that are to be executed
sequentially. It appends the sequences in such a way that the
contents of each register in the set is preserved over the execution
of the first sequence, if this is needed for the execution of the
second sequence. That is, if the first sequence modifies the register
and the second sequence actually needs the register's original
contents, then <tt>preserving</tt> wraps a <tt>save</tt> and a <tt>restore</tt>
of the register around the first sequence before appending the
sequences. Otherwise, <tt>preserving</tt> simply returns the appended
instruction sequences. Thus, for example,
<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>
produces one of the following four sequences of instructions, depending on how
<<em><em>s</em><em>e</em><em>q</em><sub>1</sub></em>> and <<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>> and <<em><em>r</em><em>e</em><em>g</em><sub>2</sub></em>>:<p>
<p><p><p><div align=left><img src="ch5-Z-G-9.gif"></div><p><p>
By using <tt>preserving</tt> to combine instruction sequences the
compiler avoids unnecessary stack operations. This also isolates the
details of whether or not to generate <tt>save</tt> and <tt>restore</tt>
instructions within the <tt>preserving</tt> procedure, separating them
from the concerns that arise in writing each of the individual code
generators.
In fact no <tt>save</tt> or <tt>restore</tt> instructions are explicitly
produced by the code generators.<p>
In principle, we could represent an instruction sequence simply as a
list of instructions. <tt>Append-instruction-sequences</tt> could then
combine instruction sequences by performing an ordinary list <tt>append</tt>. However, <tt>preserving</tt> would then be a complex operation,
because it would have to analyze each instruction sequence to
determine how the sequence uses its registers. <tt>Preserving</tt>
would be inefficient as well as complex, because it would have to
analyze each of its instruction sequence arguments, even though these
sequences might themselves have been constructed by calls to <tt>preserving</tt>, in which case their parts would have already been
analyzed. To avoid such repetitious analysis we will associate with each
instruction sequence some information about its register use.
When we construct a basic instruction sequence we
will provide this information explicitly,
and the procedures that combine instruction sequences will derive
register-use information for the combined sequence from the
information associated with the component sequences.<p>
An instruction sequence will contain three pieces of information:
<p><ul>
<li>the set of registers that must be initialized before the
instructions in the sequence are executed (these registers are said to
be <em>needed</em> by the sequence),<p>
<li>the set of registers whose values are modified by the
instructions in the sequence, and<p>
<li>the actual instructions (also called <em>statements</em>) in
the sequence.
</ul><p><p>
We will represent an instruction sequence as a list of its three
parts. The constructor for instruction sequences is thus<p>
<p><tt><a name="%_idx_6266"></a>(define (make-instruction-sequence needs modifies statements)<br>
(list needs modifies statements))<br>
</tt><p><p>
For example, the two-instruction sequence that looks up the value of
the variable <tt>x</tt> in the current environment, assigns the result
to <tt>val</tt>, and then returns, requires registers <tt>env</tt> and <tt>continue</tt> to have been initialized, and modifies register <tt>val</tt>.
This sequence would therefore be constructed as<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>
We sometimes need to construct an instruction sequence with no statements:
<p><tt><a name="%_idx_6268"></a>(define (empty-instruction-sequence)<br>
(make-instruction-sequence '() '() '()))<br>
</tt><p>
<p>
The procedures for combining instruction sequences are shown in
section <a href="#%_sec_5.5.4">5.5.4</a>.<p>
<p><a name="%_thm_5.31"></a>
<b>Exercise 5.31.</b> <a name="%_idx_6270"></a><a name="%_idx_6272"></a>In evaluating a procedure application, the explicit-control evaluator
always saves and restores
the <tt>env</tt> register around the evaluation of the operator, saves and
restores <tt>env</tt> around the evaluation of each operand (except the
final one), saves and restores <tt>argl</tt> around the evaluation of each
operand, and saves and restores <tt>proc</tt> around the evaluation of the
operand sequence. For each of the following combinations, say which
of these <tt>save</tt> and <tt>restore</tt> operations are superfluous and
thus could be eliminated by the compiler's <tt>preserving</tt> mechanism:<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><a name="%_thm_5.32"></a>
<b>Exercise 5.32.</b> <a name="%_idx_6274"></a><a name="%_idx_6276"></a>Using the <tt>preserving</tt> mechanism, the compiler will avoid saving
and restoring <tt>env</tt> around the evaluation of the operator of a
combination in the case where the operator is a symbol. We could also
build such optimizations into the evaluator. Indeed, the
explicit-control evaluator of section <a href="book-Z-H-34.html#%_sec_5.4">5.4</a> already
performs a similar optimization, by treating combinations with no
operands as a special case.<p>
<p><p>a. Extend the explicit-control evaluator to recognize as a separate class
of expressions combinations whose operator is a symbol, and to take
advantage of this fact in evaluating such expressions.<p>
<p><p>b. Alyssa P. Hacker suggests that by extending the evaluator to recognize
more and more special cases we could incorporate all the compiler's
optimizations, and that this would eliminate the advantage of compilation
altogether. What do you think of this idea?
<p><p>
<a name="%_sec_5.5.2"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.2">5.5.2 Compiling Expressions</a></h3><p>
In this section and the next we implement the code generators to which the <tt>compile</tt> procedure dispatches.<p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Compiling linkage code</a></h4><p>
<a name="%_idx_6278"></a>In general, the output of each code generator will end with
instructions -- generated by the procedure <tt>compile-linkage</tt> -- that
implement the required linkage. If the linkage is <tt>return</tt> then
we must generate the instruction <tt>(goto (reg continue))</tt>. This
needs the <tt>continue</tt> register and does not modify any registers.
If the linkage is <tt>next</tt>, then we needn't include any additional
instructions. Otherwise, the linkage is a label, and we generate a
<tt>goto</tt> to that label, an instruction that does not need or modify
any registers.<a name="call_footnote_Temp_657" href="#footnote_Temp_657"><sup><small>36</small></sup></a><p>
<p><tt><a name="%_idx_6292"></a>(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>
The linkage code is appended to an instruction sequence by <tt>preserving</tt>
the <tt>continue</tt> register, since a <tt>return</tt> linkage will
require the <tt>continue</tt> register:
If the given instruction sequence modifies <tt>continue</tt> and the
linkage code needs it, <tt>continue</tt> will be saved and restored.<p>
<p><tt><a name="%_idx_6294"></a>(define (end-with-linkage linkage instruction-sequence)<br>
(preserving '(continue)<br>
instruction-sequence<br>
(compile-linkage linkage)))<br>
</tt><p><p>
<p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Compiling simple expressions</a></h4><p>
<a name="%_idx_6296"></a><a name="%_idx_6298"></a><a name="%_idx_6300"></a>The code generators for self-evaluating expressions,
quotations, and variables construct instruction
sequences that assign the required value to the target register
and then proceed as specified by the linkage descriptor.<p>
<p><tt><a name="%_idx_6302"></a>(define (compile-self-evaluating exp target linkage)<br>
(end-with-linkage linkage<br>
(make-instruction-sequence '() (list target)<br>
`((assign ,target (const ,exp))))))<br>
<br>
<a name="%_idx_6304"></a>(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>
<br>
<a name="%_idx_6306"></a>(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>
All these assignment instructions modify the target register,
and the one that looks up a variable needs the <tt>env</tt> register.<p>
<a name="%_idx_6308"></a><a name="%_idx_6310"></a>Assignments and definitions are handled much as they are in the
interpreter. We recursively generate code that computes the value to
be assigned to the variable, and append to it a two-instruction
sequence that actually sets or defines the variable and assigns the
value of the whole expression (the symbol <tt>ok</tt>) to the target
register. The recursive compilation has target <tt>val</tt> and linkage
<tt>next</tt> so that the code will put its result into <tt>val</tt> and
continue with the code that is appended after it. The appending is
done preserving <tt>env</tt>, since the environment is needed for setting
or defining the variable and the code for the variable value could be
the compilation of a complex expression that might modify the
registers in arbitrary ways.<p>
<p><tt><a name="%_idx_6312"></a>(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>
<br>
<a name="%_idx_6314"></a>(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>
The appended two-instruction sequence requires <tt>env</tt> and <tt>val</tt>
and modifies the target. Note that although we preserve <tt>env</tt> for
this sequence, we do not preserve <tt>val</tt>, because the <tt>get-value-code</tt> is designed to explicitly place its result in <tt>val</tt> for use by this sequence.
(In fact, if we did preserve <tt>val</tt>, we would
have a bug, because this would cause the previous contents of <tt>val</tt> to be restored right after the <tt>get-value-code</tt> is run.)<p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Compiling conditional expressions</a></h4><p>
<a name="%_idx_6316"></a>The code for an <tt>if</tt> expression
compiled with a given target and linkage has the form<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>
To generate this code, we compile the predicate, consequent,
and alternative, and combine the resulting code with instructions
to test the predicate result and with newly generated labels
to mark the true and false branches and the end of the conditional.<a name="call_footnote_Temp_658" href="#footnote_Temp_658"><sup><small>37</small></sup></a>
In this arrangement of code, we must branch around the true branch
if the test is false. The only slight complication is in how the
linkage for the true branch should be handled. If the linkage for the
conditional is <tt>return</tt> or a label, then the true and false
branches will both use this same linkage. If the linkage is <tt>next</tt>, the true branch ends with a jump around the code for the false
branch to the label at the end of the conditional.<p>
<p><tt><a name="%_idx_6324"></a>(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>
<tt>Env</tt> is preserved around the predicate code because it could be needed by
the true and false branches, and <tt>continue</tt> is preserved because it could
be needed by the linkage code in those branches. The code for the true and
false branches (which are not executed sequentially) is appended using a
special combiner <tt>parallel-instruction-sequences</tt> described in
section <a href="#%_sec_5.5.4">5.5.4</a>.<p>
Note that <tt>cond</tt> is a derived expression, so all that the
compiler needs to do handle it is to apply the <tt>cond->if</tt>
transformer (from section <a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a>) and
compile the resulting <tt>if</tt> expression.<p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Compiling sequences</a></h4><p>
<a name="%_idx_6326"></a>The compilation of sequences (from procedure bodies or explicit <tt>begin</tt> expressions) parallels their evaluation. Each expression of the
sequence is compiled -- the last expression with the linkage specified
for the sequence, and the other expressions with linkage <tt>next</tt>
(to execute the rest of the sequence).
The instruction sequences for the individual expressions are appended
to form a single instruction sequence, such that <tt>env</tt> (needed for
the rest of the sequence) and <tt>continue</tt> (possibly needed for the
linkage at the end of the sequence) are preserved.<p>
<p><tt><a name="%_idx_6328"></a>(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>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Compiling <tt>lambda</tt> expressions</a></h4><p>
<a name="%_idx_6330"></a><tt>Lambda</tt> expressions construct procedures.
The object code for a <tt>lambda</tt> expression must have the form<p>
<p><tt><<em>construct procedure object and assign it to target register</em>><br>
<<em>linkage</em>><br>
</tt><p>
When we compile the <tt>lambda</tt> expression, we also generate the code for the
procedure body. Although the body won't be executed at the time of procedure
construction, it is convenient to insert it into the object code right after
the code for the <tt>lambda</tt>. If the linkage for the <tt>lambda</tt> expression
is a label or <tt>return</tt>, this is fine. But if the linkage is <tt>next</tt>,
we will need to skip around the code for the procedure body by using a linkage
that jumps to a label that is inserted after the body. The object code thus
has the form<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>
<tt>Compile-lambda</tt> generates the code for constructing the procedure
object followed by the code for the procedure body.
The procedure object will be constructed at run time by combining
the current environment (the environment at the point of definition)
with the entry point to the compiled procedure body (a newly generated
label).<a name="call_footnote_Temp_659" href="#footnote_Temp_659"><sup><small>38</small></sup></a><p>
<p><tt><a name="%_idx_6340"></a>(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>
<tt>Compile-lambda</tt> uses the special combiner <tt>tack-on-instruction-sequence</tt>
(section <a href="#%_sec_5.5.4">5.5.4</a>) rather than <tt>append-instruction-sequences</tt> to append the procedure body to the <tt>lambda</tt>
expression code, because the body is not part of the sequence of instructions
that will be executed when the combined sequence is entered; rather, it is in
the sequence only because that was a convenient place to put it.<p>
<tt>Compile-lambda-body</tt> constructs the code for the body of the
procedure. This code begins with a label for the entry point. Next
come instructions that will cause the run-time evaluation environment
to switch to the correct environment for evaluating the procedure
body -- namely, the definition environment of the procedure, extended
to include the bindings of the formal parameters to the arguments with
which the procedure is called. After this comes the code for the
sequence of expressions that makes up the procedure body.
The sequence is compiled with linkage <tt>return</tt> and target <tt>val</tt>
so that it will end by returning from the procedure with the
procedure result in <tt>val</tt>.<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>
<a name="%_sec_5.5.3"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.5.3">5.5.3 Compiling Combinations</a></h3><p>
<a name="%_idx_6342"></a><a name="%_idx_6344"></a>
The essence of the compilation process is the compilation of procedure
applications.
The code for a combination compiled with a given target and linkage
has the form
<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>
The registers <tt>env</tt>, <tt>proc</tt>, and <tt>argl</tt> may have to be
saved and restored during evaluation of the operator and operands.
Note that this is the only place in the compiler where a target other
than <tt>val</tt> is specified.<p>
The required code is generated by <tt>compile-application</tt>. This
recursively compiles the operator, to produce code that puts the
procedure to be applied into <tt>proc</tt>, and compiles the operands, to
produce code that evaluates the individual operands of the
application. The instruction sequences for the operands are combined
(by <tt>construct-arglist</tt>) with code that constructs the list of
arguments in <tt>argl</tt>, and the resulting argument-list code is
combined with the procedure code and the code that performs the
procedure call (produced by <tt>compile-procedure-call</tt>). In
appending the code sequences, the <tt>env</tt> register must be preserved
around the evaluation of the operator (since evaluating the operator
might modify <tt>env</tt>, which will be needed to evaluate the
operands), and the <tt>proc</tt> register must be preserved around the
construction of the argument list (since evaluating the operands might
modify <tt>proc</tt>, which will be needed for the actual procedure
application). <tt>Continue</tt> must also be preserved throughout, since
it is needed for the linkage in the procedure call.<p>
<p><tt><a name="%_idx_6346"></a>(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>
The code to construct the argument list will evaluate each operand into
<tt>val</tt> and then <tt>cons</tt> that value onto the argument list being
accumulated in <tt>argl</tt>.
Since we <tt>cons</tt> the arguments onto <tt>argl</tt> in sequence, we must
start with the last argument and end with the first, so that the
arguments will appear in order from first to last in the resulting list.
Rather than waste an instruction by initializing <tt>argl</tt> to the empty list
to set up for this sequence of evaluations,
we make the first code sequence construct the initial <tt>argl</tt>.
The general form of the argument-list construction is thus as follows:<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><br>
<<em>compilation of first operand, targeted to <tt>val</tt></em>><br>
(assign argl (op cons) (reg val) (reg argl))<br>
</tt><p>
<tt>Argl</tt> must be preserved around each operand evaluation except
the first (so that arguments accumulated so far won't be lost), and
<tt>env</tt> must be preserved around each operand evaluation
except the last (for use by subsequent operand evaluations).<p>
Compiling this argument code is a bit tricky, because of
the special treatment of the first operand to be evaluated and the
need to preserve <tt>argl</tt> and <tt>env</tt> in different places.
The <tt>construct-arglist</tt> procedure takes as arguments the code that
evaluates the individual operands. If there are no operands at all, it simply
emits the instruction<p>
<p><tt>(assign argl (const ()))<br>
</tt><p>
Otherwise, <tt>construct-arglist</tt> creates code that initializes <tt>argl</tt> with the last argument, and appends code that evaluates
the rest of the arguments and adjoins them to <tt>argl</tt> in
succession. In order to process the arguments from last to
first, we must reverse the list of operand code sequences from the order
supplied by <tt>compile-application</tt>.<p>
<p><tt><a name="%_idx_6348"></a>(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>
<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>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Applying procedures</a></h4><p>
After evaluating the elements of a combination, the compiled code must
apply the procedure in <tt>proc</tt> to the arguments in <tt>argl</tt>. The
code performs essentially the same dispatch as the <tt>apply</tt> procedure in the
metacircular evaluator of section <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a> or the
<tt>apply-dispatch</tt> entry point in the explicit-control evaluator of
section <a href="book-Z-H-34.html#%_sec_5.4.1">5.4.1</a>. It checks whether the
procedure to be applied is a primitive procedure or a compiled
procedure. For a primitive procedure, it uses <tt>apply-primitive-procedure</tt>; we will see shortly how it handles
compiled procedures. The procedure-application code has the following
form:<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>
Observe that the compiled branch must skip around the primitive
branch. Therefore, if the linkage for the original procedure call was
<tt>next</tt>, the compound branch must use a linkage that jumps to a
label that is inserted after the primitive branch. (This is similar
to the linkage used for the true branch in <tt>compile-if</tt>.)<p>
<p><tt><a name="%_idx_6350"></a>(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>
The primitive and compound branches, like the true
and false branches in <tt>compile-if</tt>, are appended using
<tt>parallel-instruction-sequences</tt> rather than the ordinary <tt>append-instruction-sequences</tt>, because they will
not be executed sequentially.<p>
<a name="%_sec_IGNORE"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_IGNORE">Applying compiled procedures</a></h4><p>
The code that handles procedure application is the most subtle part of
the compiler, even though the instruction sequences it generates are
very short. A compiled procedure (as constructed by <tt>compile-lambda</tt>) has an entry point, which is a label that designates
where the code for the procedure starts. The code at this entry point
computes a result in <tt>val</tt> and returns by executing the
instruction <tt>(goto (reg continue))</tt>. Thus, we might expect the
code for a compiled-procedure application (to be generated by <tt>compile-proc-appl</tt>) with a given target and linkage to look like this
if the linkage is a label
<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>
or like this if the linkage is <tt>return</tt>.
<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>
This code sets up <tt>continue</tt> so that the procedure will return to a
label <tt>proc-return</tt> and jumps to the procedure's entry point. The code
at <tt>proc-return</tt> transfers the procedure's result from <tt>val</tt>
to the target register (if necessary) and then jumps to
the location specified by the linkage.
(The linkage is always <tt>return</tt> or a label, because <tt>compile-procedure-call</tt> replaces a <tt>next</tt> linkage for the
compound-procedure branch by an <tt>after-call</tt> label.)<p>
In fact, if the target is not <tt>val</tt>, that is exactly the code our
compiler will generate.<a name="call_footnote_Temp_660" href="#footnote_Temp_660"><sup><small>39</small></sup></a>
Usually, however, the target is <tt>val</tt> (the only time the compiler
specifies a different register is when targeting the evaluation of an
operator to <tt>proc</tt>), so the procedure result is put directly into
the target register and there is no need to return to a special
location that copies it. Instead, we simplify the code by
setting up <tt>continue</tt> so that the procedure will ``return''
directly to the place specified by the caller's linkage:
<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>
If the linkage is a label, we set up <tt>continue</tt> so that the procedure will return to
that label. (That is, the <tt>(goto (reg continue))</tt> the procedure
ends with becomes equivalent to the <tt>(goto (label <<em>linkage</em>>))</tt> at
<tt>proc-return</tt> above.)
<p><tt>(assign continue (label <<em>linkage</em>>))<br>
(assign val (op compiled-procedure-entry) (reg proc))<br>
(goto (reg val))<br>
</tt><p>
If the linkage is <tt>return</tt>, we don't need to set up <tt>continue</tt>
at all: It already holds the desired location. (That is, the <tt>(goto (reg continue))</tt> the procedure ends with goes directly to the
place where the <tt>(goto (reg continue))</tt> at <tt>proc-return</tt> would
have gone.)
<p><tt>(assign val (op compiled-procedure-entry) (reg proc))<br>
(goto (reg val))<br>
</tt><p>
<a name="%_idx_6352"></a><a name="%_idx_6354"></a>With this implementation of the <tt>return</tt> linkage, the compiler
generates tail-recursive code. Calling a procedure as the final step
in a procedure body does a direct transfer, without saving any
information on the stack.<p>
Suppose instead that we had handled the case of a procedure call with
a linkage of <tt>return</tt> and a target of <tt>val</tt> as shown above for
a non-<tt>val</tt> target. This would destroy tail recursion. Our
system would still give the same value for any expression. But each
time we called a procedure, we would save <tt>continue</tt> and return
after the call to undo the (useless) save. These extra saves would
accumulate during a nest of procedure calls.<a name="call_footnote_Temp_661" href="#footnote_Temp_661"><sup><small>40</small></sup></a><p>
<tt>Compile-proc-appl</tt> generates the above procedure-application code by
considering four cases, depending on whether the target for the call
is <tt>val</tt> and whether the linkage is <tt>return</tt>.
Observe that the instruction sequences are
declared to modify all the registers, since executing the procedure
body can change the registers in arbitrary ways.<a name="call_footnote_Temp_662" href="#footnote_Temp_662"><sup><small>41</small></sup></a>
Also note that the code sequence for the case with target <tt>val</tt>
and linkage <tt>return</tt> is declared to need <tt>continue</tt>: Even
though <tt>continue</tt> is not explicitly used in the two-instruction
sequence, we must be sure that <tt>continue</tt> will have the correct
value when we enter the compiled procedure.<p>
<p><tt><a name="%_idx_6376"></a>(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>