forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-34.html
1235 lines (990 loc) · 61.1 KB
/
book-Z-H-34.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:https://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http:https://www.cs.rice.edu/~dorai/tex2page -->
<head>
<meta name="generator" content="HTML Tidy for Linux (vers 7 December 2008), see www.w3.org" />
<title>Structure and Interpretation of Computer Programs</title>
<link href="book-Z-C.css" title="default" rel="stylesheet" type="text/css" />
<meta name="robots" content="noindex,follow" />
</head>
<body>
<mbp:pagebreak />
<p><a name="%_sec_5.4"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_5.4">5.4 The
Explicit-Control Evaluator</a></h2>
<p><a name="%_idx_5996"></a> In section <a href="book-Z-H-31.html#%_sec_5.1">5.1</a> we saw how to transform
simple Scheme programs into descriptions of register machines. We
will now perform this transformation on a more complex program,
the metacircular evaluator of sections <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>-<a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>, which shows how the
behavior of a Scheme interpreter can be described in terms of the
procedures <tt>eval</tt> and <tt>apply</tt>. The
<em>explicit-control evaluator</em> that we develop in this
section shows how the underlying procedure-calling and
argument-passing mechanisms used in the evaluation process can be
described in terms of operations on registers and stacks. In
addition, the explicit-control evaluator can serve as an
implementation of a Scheme interpreter, written in a language
that is very similar to the native machine language of
conventional computers. The evaluator can be executed by the
register-machine simulator of section <a href="book-Z-H-32.html#%_sec_5.2">5.2</a>. Alternatively, it can be
used as a starting point for building a machine-language
implementation of a Scheme evaluator, or even a <a name="%_idx_5998"></a><a name="%_idx_6000"></a><a name="%_idx_6002"></a>special-purpose machine for evaluating Scheme
expressions. Figure <a href="#%_fig_5.16">5.16</a> shows
such a hardware implementation: a silicon chip that acts as an
evaluator for Scheme. The chip designers started with the
data-path and controller specifications for a register machine
similar to the evaluator described in this section and used
design automation programs to construct the integrated-circuit
layout.<a href="#footnote_Temp_765" name="call_footnote_Temp_765" id="call_footnote_Temp_765"><sup><small>19</small></sup></a></p>
<p><a name="%_sec_Temp_766"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_766">Registers and
operations</a></h4>
<p><a name="%_idx_6006"></a> <a name="%_idx_6008"></a>In
designing the explicit-control evaluator, we must specify the
operations to be used in our register machine. We described the
metacircular evaluator in terms of abstract syntax, using
procedures such as <tt>quoted?</tt> and <tt>make-procedure</tt>.
In implementing the register machine, we could expand these
procedures into sequences of elementary list-structure memory
operations, and implement these operations on our register
machine. However, this would make our evaluator very long,
obscuring the basic structure with details. To clarify the
presentation, we will include as primitive operations of the
register machine the syntax procedures given in
section <a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a> and
the procedures for representing environments and other run-time
data given in sections <a href="book-Z-H-26.html#%_sec_4.1.3">4.1.3</a> and <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>. In order to completely
specify an evaluator that could be programmed in a low-level
machine language or implemented in hardware, we would replace
these operations by more elementary operations, using the
list-structure implementation we described in
section <a href="book-Z-H-33.html#%_sec_5.3">5.3</a>.</p>
<p><a name="%_fig_5.16"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.16:</b> A silicon-chip implementation
of an evaluator for Scheme.
</div>
<table width="100%">
<tr>
<td><img src="chip.jpg" border="0" height="310" /></td>
</tr>
<tr>
<td><a name="%_idx_6010"></a><a name="%_idx_6012"></a><a name="%_idx_6014"></a></td>
</tr>
</table>
</div>
<p><a name="%_idx_6016"></a><a name="%_idx_6018"></a><a name="%_idx_6020"></a><a name="%_idx_6022"></a><a name="%_idx_6024"></a><a name="%_idx_6026"></a><a name="%_idx_6028"></a><a name="%_idx_6030"></a>Our Scheme evaluator
register machine includes a stack and seven registers:
<tt>exp</tt>, <tt>env</tt>, <tt>val</tt>, <tt>continue</tt>,
<tt>proc</tt>, <tt>argl</tt>, and <tt>unev</tt>. <tt>Exp</tt> is
used to hold the expression to be evaluated, and <tt>env</tt>
contains the environment in which the evaluation is to be
performed. At the end of an evaluation, <tt>val</tt> contains the
value obtained by evaluating the expression in the designated
environment. The <tt>continue</tt> register is used to implement
recursion, as explained in section <a href="book-Z-H-31.html#%_sec_5.1.4">5.1.4</a>. (The evaluator needs to
call itself recursively, since evaluating an expression requires
evaluating its subexpressions.) The registers <tt>proc</tt>,
<tt>argl</tt>, and <tt>unev</tt> are used in evaluating
combinations.</p>
<p>We will not provide a data-path diagram to show how the
registers and operations of the evaluator are connected, nor will
we give the complete list of machine operations. These are
implicit in the evaluator's controller, which will be presented
in detail.</p>
<p><a name="%_sec_5.4.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.4.1">5.4.1 The Core of
the Explicit-Control Evaluator</a></h3>
<p><a name="%_idx_6032"></a> The central element in the evaluator
is the sequence of instructions beginning at
<tt>eval-dispatch</tt>. This corresponds to the <tt>eval</tt>
procedure of the metacircular evaluator described in
section <a href="book-Z-H-26.html#%_sec_4.1.1">4.1.1</a>.
When the controller starts at <tt>eval-dispatch</tt>, it
evaluates the expression specified by <tt>exp</tt> in the
environment specified by <tt>env</tt>. When evaluation is
complete, the controller will go to the entry point stored in
<tt>continue</tt>, and the <tt>val</tt> register will hold the
value of the expression. As with the metacircular <tt>eval</tt>,
the structure of <tt>eval-dispatch</tt> is a case analysis on the
syntactic type of the expression to be evaluated.<a href="#footnote_Temp_767" name="call_footnote_Temp_767" id="call_footnote_Temp_767"><sup><small>20</small></sup></a></p>
<p><tt><a name="%_idx_6034"></a>eval-dispatch<br />
(test (op self-evaluating?) (reg exp))<br />
(branch (label ev-self-eval))<br />
(test (op variable?) (reg exp))<br />
(branch (label ev-variable))<br />
(test (op quoted?) (reg exp))<br />
(branch (label ev-quoted))<br />
(test (op assignment?) (reg exp))<br />
(branch (label ev-assignment))<br />
(test (op definition?) (reg exp))<br />
(branch (label ev-definition))<br />
(test (op if?) (reg exp))<br />
(branch (label ev-if))<br />
(test (op lambda?) (reg exp))<br />
(branch (label ev-lambda))<br />
(test (op begin?) (reg exp))<br />
(branch (label ev-begin))<br />
(test (op application?) (reg exp))<br />
(branch (label ev-application))<br />
(goto (label unknown-expression-type))<br /></tt></p>
<p><a name="%_sec_Temp_768"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_768">Evaluating
simple expressions</a></h4>
<p><a name="%_idx_6036"></a> Numbers and strings (which are
self-evaluating), variables, quotations, and <tt>lambda</tt>
expressions have no subexpressions to be evaluated. For these,
the evaluator simply places the correct value in the <tt>val</tt>
register and continues execution at the entry point specified by
<tt>continue</tt>. Evaluation of simple expressions is performed
by the following controller code:</p>
<p><tt><a name="%_idx_6038"></a>ev-self-eval<br />
(assign val (reg exp))<br />
(goto (reg continue))<br />
<a name="%_idx_6040"></a>ev-variable<br />
(assign val (op lookup-variable-value) (reg exp) (reg env))<br />
(goto (reg continue))<br />
<a name="%_idx_6042"></a>ev-quoted<br />
(assign val (op text-of-quotation) (reg exp))<br />
(goto (reg continue))<br />
<a name="%_idx_6044"></a>ev-lambda<br />
(assign unev (op lambda-parameters) (reg exp))<br />
(assign exp (op lambda-body) (reg exp))<br />
(assign val (op make-procedure)<br />
(reg unev) (reg exp) (reg env))<br />
(goto (reg continue))<br /></tt></p>
<p>Observe how <tt>ev-lambda</tt> uses the <tt>unev</tt> and
<tt>exp</tt> registers to hold the parameters and body of the
lambda expression so that they can be passed to the
<tt>make-procedure</tt> operation, along with the environment in
<tt>env</tt>.</p>
<p><a name="%_sec_Temp_769"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_769">Evaluating
procedure applications</a></h4>
<p><a name="%_idx_6046"></a><a name="%_idx_6048"></a> A procedure
application is specified by a combination containing an operator
and operands. The operator is a subexpression whose value is a
procedure, and the operands are subexpressions whose values are
the arguments to which the procedure should be applied. The
metacircular <tt>eval</tt> handles applications by calling itself
recursively to evaluate each element of the combination, and then
passing the results to <tt>apply</tt>, which performs the actual
procedure application. The explicit-control evaluator does the
same thing; these recursive calls are implemented by
<tt>goto</tt> instructions, together with <a name="%_idx_6050"></a>use of the stack to save registers that will be
restored after the recursive call returns. Before each call we
will be careful to identify which registers must be saved
(because their values will be needed later).<a href="#footnote_Temp_770" name="call_footnote_Temp_770" id="call_footnote_Temp_770"><sup><small>21</small></sup></a></p>
<p>We begin the evaluation of an application by evaluating the
operator to produce a procedure, which will later be applied to
the evaluated operands. To evaluate the operator, we move it to
the <tt>exp</tt> register and go to <tt>eval-dispatch</tt>. The
environment in the <tt>env</tt> register is already the correct
one in which to evaluate the operator. However, we save
<tt>env</tt> because we will need it later to evaluate the
operands. We also extract the operands into <tt>unev</tt> and
save this on the stack. We set up <tt>continue</tt> so that
<tt>eval-dispatch</tt> will resume at
<tt>ev-appl-did-operator</tt> after the operator has been
evaluated. First, however, we save the old value of
<tt>continue</tt>, which tells the controller where to continue
after the application.</p>
<p><tt><a name="%_idx_6056"></a>ev-application<br />
(save continue)<br />
(save env)<br />
(assign unev (op operands) (reg exp))<br />
(save unev)<br />
(assign exp (op operator) (reg exp))<br />
(assign continue (label ev-appl-did-operator))<br />
(goto (label eval-dispatch))<br /></tt></p>
<p><a name="%_idx_6058"></a>Upon returning from evaluating the
operator subexpression, we proceed to evaluate the operands of
the combination and to accumulate the resulting arguments in a
list, held in <tt>argl</tt>. First we restore the unevaluated
operands and the environment. We initialize <tt>argl</tt> to an
empty list. Then we assign to the <tt>proc</tt> register the
procedure that was produced by evaluating the operator. If there
are no operands, we go directly to <tt>apply-dispatch</tt>.
Otherwise we save <tt>proc</tt> on the stack and start the
argument-evaluation loop:<a href="#footnote_Temp_771" name="call_footnote_Temp_771" id="call_footnote_Temp_771"><sup><small>22</small></sup></a></p>
<p><tt>ev-appl-did-operator<br />
(restore unev) <em>; the operands</em><br />
(restore env)<br />
(assign argl (op empty-arglist))<br />
(assign proc (reg val)) <em>; the operator</em><br />
(test (op no-operands?) (reg unev))<br />
(branch (label apply-dispatch))<br />
(save proc)<br /></tt></p>
<p>Each cycle of the argument-evaluation loop evaluates an
operand from the list in <tt>unev</tt> and accumulates the result
into <tt>argl</tt>. To evaluate an operand, we place it in the
<tt>exp</tt> register and go to <tt>eval-dispatch</tt>, after
setting <tt>continue</tt> so that execution will resume with the
argument-accumulation phase. But first we save the arguments
accumulated so far (held in <tt>argl</tt>), the environment (held
in <tt>env</tt>), and the remaining operands to be evaluated
(held in <tt>unev</tt>). A special case is made for the
evaluation of the last operand, which is handled at
<tt>ev-appl-last-arg</tt>.</p>
<p><tt>ev-appl-operand-loop<br />
(save argl)<br />
(assign exp (op first-operand) (reg unev))<br />
(test (op last-operand?) (reg unev))<br />
(branch (label ev-appl-last-arg))<br />
(save env)<br />
(save unev)<br />
(assign continue (label ev-appl-accumulate-arg))<br />
(goto (label eval-dispatch))<br /></tt></p>
<p>When an operand has been evaluated, the value is accumulated
into the list held in <tt>argl</tt>. The operand is then removed
from the list of unevaluated operands in <tt>unev</tt>, and the
argument-evaluation continues.</p>
<p><tt>ev-appl-accumulate-arg<br />
(restore unev)<br />
(restore env)<br />
(restore argl)<br />
(assign argl (op adjoin-arg) (reg val) (reg argl))<br />
(assign unev (op rest-operands) (reg unev))<br />
(goto (label ev-appl-operand-loop))<br /></tt></p>
<p>Evaluation of the last argument is handled differently. There
is no need to save the environment or the list of unevaluated
operands before going to <tt>eval-dispatch</tt>, since they will
not be required after the last operand is evaluated. Thus, we
return from the evaluation to a special entry point
<tt>ev-appl-accum-last-arg</tt>, which restores the argument
list, accumulates the new argument, restores the saved procedure,
and goes off to perform the application.<a href="#footnote_Temp_772" name="call_footnote_Temp_772" id="call_footnote_Temp_772"><sup><small>23</small></sup></a></p>
<p><tt>ev-appl-last-arg<br />
(assign continue (label ev-appl-accum-last-arg))<br />
(goto (label eval-dispatch))<br />
ev-appl-accum-last-arg<br />
(restore argl)<br />
(assign argl (op adjoin-arg) (reg val) (reg argl))<br />
(restore proc)<br />
(goto (label apply-dispatch))<br /></tt></p>
<p><a name="%_idx_6070"></a>The details of the
argument-evaluation loop determine the order in which the
interpreter evaluates the operands of a combination (e.g., left
to right or right to left -- see exercise <a href="book-Z-H-20.html#%_thm_3.8">3.8</a>). This order is not
determined by the metacircular evaluator, which inherits its
control structure from the underlying Scheme in which it is
implemented.<a href="#footnote_Temp_773" name="call_footnote_Temp_773" id="call_footnote_Temp_773"><sup><small>24</small></sup></a> Because
the <tt>first-operand</tt> selector (used in
<tt>ev-appl-operand-loop</tt> to extract successive operands from
<tt>unev</tt>) is implemented as <tt>car</tt> and the
<tt>rest-operands</tt> selector is implemented as <tt>cdr</tt>,
the explicit-control evaluator will evaluate the operands of a
combination in left-to-right order.</p>
<p><a name="%_sec_Temp_774"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_774">Procedure
application</a></h4>
<p>The entry point <tt>apply-dispatch</tt> corresponds to the
<tt>apply</tt> procedure of the metacircular evaluator. By the
time we get to <tt>apply-dispatch</tt>, the <tt>proc</tt>
register contains the procedure to apply and <tt>argl</tt>
contains the list of evaluated arguments to which it must be
applied. The saved value of <tt>continue</tt> (originally passed
to <tt>eval-dispatch</tt> and saved at <tt>ev-application</tt>),
which tells where to return with the result of the procedure
application, is on the stack. When the application is complete,
the controller transfers to the entry point specified by the
saved <tt>continue</tt>, with the result of the application in
<tt>val</tt>. As with the metacircular <tt>apply</tt>, there are
two cases to consider. Either the procedure to be applied is a
primitive or it is a compound procedure.</p>
<p><tt><a name="%_idx_6072"></a>apply-dispatch<br />
(test (op primitive-procedure?) (reg proc))<br />
(branch (label primitive-apply))<br />
(test (op compound-procedure?) (reg proc)) <br />
(branch (label compound-apply))<br />
(goto (label unknown-procedure-type))<br /></tt></p>
<p><a name="%_idx_6074"></a>We assume that each primitive is
implemented so as to obtain its arguments from <tt>argl</tt> and
place its result in <tt>val</tt>. To specify how the machine
handles primitives, we would have to provide a sequence of
controller instructions to implement each primitive and arrange
for <tt>primitive-apply</tt> to dispatch to the instructions for
the primitive identified by the contents of <tt>proc</tt>. Since
we are interested in the structure of the evaluation process
rather than the details of the primitives, we will instead just
use an <tt>apply-primitive-procedure</tt> operation that applies
the procedure in <tt>proc</tt> to the arguments in <tt>argl</tt>.
For the purpose of simulating the evaluator with the simulator of
section <a href="book-Z-H-32.html#%_sec_5.2">5.2</a> we use
the procedure <tt>apply-primitive-procedure</tt>, which calls on
the underlying Scheme system to perform the application, just as
we did for the metacircular evaluator in section <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>. After computing the
value of the primitive application, we restore <tt>continue</tt>
and go to the designated entry point.</p>
<p><tt><a name="%_idx_6076"></a>primitive-apply<br />
(assign val (op apply-primitive-procedure)<br />
(reg proc)<br />
(reg argl))<br />
(restore continue)<br />
(goto (reg continue))<br /></tt></p>
<p><a name="%_idx_6078"></a>To apply a compound procedure, we
proceed just as with the metacircular evaluator. We construct a
frame that binds the procedure's parameters to the arguments, use
this frame to extend the environment carried by the procedure,
and evaluate in this extended environment the sequence of
expressions that forms the body of the procedure.
<tt>Ev-sequence</tt>, described below in section <a href="#%_sec_5.4.2">5.4.2</a>, handles the evaluation of the
sequence.</p>
<p><tt><a name="%_idx_6080"></a>compound-apply<br />
(assign unev (op procedure-parameters) (reg proc))<br />
(assign env (op procedure-environment) (reg proc))<br />
(assign env (op extend-environment)<br />
(reg unev) (reg argl) (reg env))<br />
(assign unev (op procedure-body) (reg proc))<br />
(goto (label ev-sequence))<br /></tt></p>
<p><tt>Compound-apply</tt> is the only place in the interpreter
where the <tt>env</tt> register is ever assigned a new value.
Just as in the metacircular evaluator, the new environment is
constructed from the environment carried by the procedure,
together with the argument list and the corresponding list of
variables to be bound.</p>
<p><a name="%_sec_5.4.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.4.2">5.4.2 Sequence
Evaluation and Tail Recursion</a></h3>
<p><a name="%_idx_6082"></a> The portion of the explicit-control
evaluator at <tt>ev-sequence</tt> is analogous to the
metacircular evaluator's <tt>eval-sequence</tt> procedure. It
handles sequences of expressions in procedure bodies or in
explicit <tt>begin</tt> expressions.</p>
<p>Explicit <tt>begin</tt> expressions are evaluated by placing
the sequence of expressions to be evaluated in <tt>unev</tt>,
saving <tt>continue</tt> on the stack, and jumping to
<tt>ev-sequence</tt>.</p>
<p><tt><a name="%_idx_6084"></a>ev-begin<br />
(assign unev (op begin-actions) (reg exp))<br />
(save continue)<br />
(goto (label ev-sequence))<br /></tt></p>
<p>The implicit sequences in procedure bodies are handled by
jumping to <tt>ev-sequence</tt> from <tt>compound-apply</tt>, at
which point <tt>continue</tt> is already on the stack, having
been saved at <tt>ev-application</tt>.</p>
<p>The entries at <tt>ev-sequence</tt> and
<tt>ev-sequence-continue</tt> form a loop that successively
evaluates each expression in a sequence. The list of unevaluated
expressions is kept in <tt>unev</tt>. Before evaluating each
expression, we check to see if there are additional expressions
to be evaluated in the sequence. If so, we save the rest of the
unevaluated expressions (held in <tt>unev</tt>) and the
environment in which these must be evaluated (held in
<tt>env</tt>) and call <tt>eval-dispatch</tt> to evaluate the
expression. The two saved registers are restored upon the return
from this evaluation, at <tt>ev-sequence-continue</tt>.</p>
<p>The final expression in the sequence is handled differently,
at the entry point <tt>ev-sequence-last-exp</tt>. Since there are
no more expressions to be evaluated after this one, we need not
save <tt>unev</tt> or <tt>env</tt> before going to
<tt>eval-dispatch</tt>. The value of the whole sequence is the
value of the last expression, so after the evaluation of the last
expression there is nothing left to do except continue at the
entry point currently held on the stack (which was saved by
<tt>ev-application</tt> or <tt>ev-begin</tt>.) Rather than
setting up <tt>continue</tt> to arrange for
<tt>eval-dispatch</tt> to return here and then restoring
<tt>continue</tt> from the stack and continuing at that entry
point, we restore <tt>continue</tt> from the stack before going
to <tt>eval-dispatch</tt>, so that <tt>eval-dispatch</tt> will
continue at that entry point after evaluating the expression.</p>
<p><tt><a name="%_idx_6086"></a>ev-sequence<br />
(assign exp (op first-exp) (reg unev))<br />
(test (op last-exp?) (reg unev))<br />
(branch (label ev-sequence-last-exp))<br />
(save unev)<br />
(save env)<br />
(assign continue (label ev-sequence-continue))<br />
(goto (label eval-dispatch))<br />
ev-sequence-continue<br />
(restore env)<br />
(restore unev)<br />
(assign unev (op rest-exps) (reg unev))<br />
(goto (label ev-sequence))<br />
ev-sequence-last-exp<br />
(restore continue)<br />
(goto (label eval-dispatch))<br /></tt></p>
<p><a name="%_sec_Temp_775"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_775">Tail
recursion</a></h4>
<p><a name="%_idx_6088"></a><a name="%_idx_6090"></a> In
chapter 1 we said that the process described by a procedure
such as</p>
<p><tt>(define (sqrt-iter guess x)<br />
(if (good-enough? guess x)<br />
guess<br />
(sqrt-iter (improve guess x)<br />
x)))<br />
</tt></p>
<p>is an iterative process. Even though the procedure is
syntactically recursive (defined in terms of itself), it is not
logically necessary for an evaluator to save information in
passing from one call to <tt>sqrt-iter</tt> to the next.<a href="#footnote_Temp_776" name="call_footnote_Temp_776" id="call_footnote_Temp_776"><sup><small>25</small></sup></a> An
evaluator that can execute a procedure such as <tt>sqrt-iter</tt>
without requiring increasing storage as the procedure continues
to call itself is called a <a name="%_idx_6092"></a><em>tail-recursive</em> evaluator. <a name="%_idx_6094"></a><a name="%_idx_6096"></a>The metacircular
implementation of the evaluator in chapter 4 does not
specify whether the evaluator is tail-recursive, because that
evaluator inherits its mechanism for saving state from the
underlying Scheme. With the explicit-control evaluator, however,
we can trace through the evaluation process to see when procedure
calls cause a net accumulation of information on the stack.</p>
<p>Our evaluator is tail-recursive, because in order to evaluate
the final expression of a sequence we transfer directly to
<tt>eval-dispatch</tt> without saving any information on the
stack. Hence, evaluating the final expression in a sequence --
even if it is a procedure call (as in <tt>sqrt-iter</tt>, where
the <tt>if</tt> expression, which is the last expression in the
procedure body, reduces to a call to <tt>sqrt-iter</tt>) -- will
not cause any information to be accumulated on the stack.<a href="#footnote_Temp_777" name="call_footnote_Temp_777" id="call_footnote_Temp_777"><sup><small>26</small></sup></a></p>
<p>If we did not think to take advantage of the fact that it was
unnecessary to save information in this case, we might have
implemented <tt>eval-sequence</tt> by treating all the
expressions in a sequence in the same way -- saving the
registers, evaluating the expression, returning to restore the
registers, and repeating this until all the expressions have been
evaluated:<a href="#footnote_Temp_778" name="call_footnote_Temp_778" id="call_footnote_Temp_778"><sup><small>27</small></sup></a></p>
<p><tt><a name="%_idx_6100"></a>ev-sequence<br />
(test (op no-more-exps?) (reg unev))<br />
(branch (label ev-sequence-end))<br />
(assign exp (op first-exp) (reg unev))<br />
(save unev)<br />
(save env)<br />
(assign continue (label ev-sequence-continue))<br />
(goto (label eval-dispatch))<br />
ev-sequence-continue<br />
(restore env)<br />
(restore unev)<br />
(assign unev (op rest-exps) (reg unev))<br />
(goto (label ev-sequence))<br />
ev-sequence-end<br />
(restore continue)<br />
(goto (reg continue))<br /></tt></p>
<p>This may seem like a minor change to our previous code for
evaluation of a sequence: The only difference is that we go
through the save-restore cycle for the last expression in a
sequence as well as for the others. The interpreter will still
give the same value for any expression. But this change is fatal
to the tail-recursive implementation, because we must now return
after evaluating the final expression in a sequence in order to
undo the (useless) register saves. These extra saves will
accumulate during a nest of procedure calls. Consequently,
processes such as <tt>sqrt-iter</tt> will require space
proportional to the number of iterations rather than requiring
constant space. This difference can be significant. For example,
<a name="%_idx_6102"></a>with tail recursion, an infinite loop
can be expressed using only the procedure-call mechanism:</p>
<p><tt>(define (count n)<br />
(newline)<br />
(display n)<br />
(count (+ n 1)))<br /></tt></p>
<p>Without tail recursion, such a procedure would eventually run
out of stack space, and expressing a true iteration would require
some control mechanism other than procedure call.</p>
<p><a name="%_sec_5.4.3"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.4.3">5.4.3 Conditionals,
Assignments, and Definitions</a></h3>
<p><a name="%_idx_6104"></a>As with the metacircular evaluator,
special forms are handled by selectively evaluating fragments of
the expression. For an <tt>if</tt> expression, we must evaluate
the predicate and decide, based on the value of predicate,
whether to evaluate the consequent or the alternative.</p>
<p>Before evaluating the predicate, we save the <tt>if</tt>
expression itself so that we can later extract the consequent or
alternative. We also save the environment, which we will need
later in order to evaluate the consequent or the alternative, and
we save <tt>continue</tt>, which we will need later in order to
return to the evaluation of the expression that is waiting for
the value of the <tt>if</tt>.</p>
<p><tt><a name="%_idx_6106"></a>ev-if<br />
(save exp) <em>; save expression for later</em><br />
(save env)<br />
(save continue)<br />
(assign continue (label ev-if-decide))<br />
(assign exp (op if-predicate) (reg exp))<br />
(goto (label eval-dispatch)) <em>; evaluate the predicate</em><br />
</tt></p>
<p>When we return from evaluating the predicate, we test whether
it was true or false and, depending on the result, place either
the consequent or the alternative in <tt>exp</tt> before going to
<tt>eval-dispatch</tt>. Notice that restoring <tt>env</tt> and
<tt>continue</tt> here sets up <tt>eval-dispatch</tt> to have the
correct environment and to continue at the right place to receive
the value of the <tt>if</tt> expression.</p>
<p><tt>ev-if-decide<br />
(restore continue)<br />
(restore env)<br />
(restore exp)<br />
(test (op true?) (reg val))<br />
(branch (label ev-if-consequent))<br />
<br />
ev-if-alternative<br />
(assign exp (op if-alternative) (reg exp))<br />
(goto (label eval-dispatch))<br />
ev-if-consequent<br />
(assign exp (op if-consequent) (reg exp))<br />
(goto (label eval-dispatch))<br /></tt></p>
<p><a name="%_sec_Temp_779"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_779">Assignments
and definitions</a></h4>
<p><a name="%_idx_6108"></a>Assignments are handled by
<tt>ev-assignment</tt>, which is reached from
<tt>eval-dispatch</tt> with the assignment expression in
<tt>exp</tt>. The code at <tt>ev-assignment</tt> first evaluates
the value part of the expression and then installs the new value
in the environment. <tt>Set-variable-value!</tt> is assumed to be
available as a machine operation.</p>
<p><tt><a name="%_idx_6110"></a>ev-assignment<br />
(assign unev (op assignment-variable) (reg exp))<br />
(save unev) <em>; save variable for later</em><br />
(assign exp (op assignment-value) (reg exp))<br />
(save env)<br />
(save continue)<br />
(assign continue (label ev-assignment-1))<br />
(goto (label eval-dispatch)) <em>; evaluate the assignment value</em><br />
ev-assignment-1<br />
(restore continue)<br />
(restore env)<br />
(restore unev)<br />
(perform<br />
(op set-variable-value!) (reg unev) (reg val) (reg env))<br />
(assign val (const ok))<br />
(goto (reg continue))<br /></tt></p>
<p><a name="%_idx_6112"></a>Definitions are handled in a similar
way:</p>
<p><tt><a name="%_idx_6114"></a>ev-definition<br />
(assign unev (op definition-variable) (reg exp))<br />
(save unev) <em>; save variable for later</em><br />
(assign exp (op definition-value) (reg exp))<br />
(save env)<br />
(save continue)<br />
(assign continue (label ev-definition-1))<br />
(goto (label eval-dispatch)) <em>; evaluate the definition value</em><br />
ev-definition-1<br />
(restore continue)<br />
(restore env)<br />
(restore unev)<br />
(perform<br />
(op define-variable!) (reg unev) (reg val) (reg env))<br />
(assign val (const ok))<br />
(goto (reg continue))<br /></tt></p>
<p><a name="%_thm_5.23"></a> <b>Exercise
5.23.</b> <a name="%_idx_6116"></a><a name="%_idx_6118"></a><a name="%_idx_6120"></a>Extend the evaluator to
handle derived expressions such as <tt>cond</tt>, <tt>let</tt>,
and so on (section <a href="book-Z-H-26.html#%_sec_4.1.2">4.1.2</a>). You may ``cheat'' and
assume that the syntax transformers such as <tt>cond->if</tt>
are available as machine operations.<a href="#footnote_Temp_781" name="call_footnote_Temp_781" id="call_footnote_Temp_781"><sup><small>28</small></sup></a></p>
<p><a name="%_thm_5.24"></a> <b>Exercise
5.24.</b> <a name="%_idx_6122"></a>Implement
<tt>cond</tt> as a new basic special form without reducing it to
<tt>if</tt>. You will have to construct a loop that tests the
predicates of successive <tt>cond</tt> clauses until you find one
that is true, and then use <tt>ev-sequence</tt> to evaluate the
actions of the clause.</p>
<p><a name="%_thm_5.25"></a> <b>Exercise
5.25.</b> <a name="%_idx_6124"></a><a name="%_idx_6126"></a>Modify the evaluator so that it uses
normal-order evaluation, based on the lazy evaluator of
section <a href="book-Z-H-27.html#%_sec_4.2">4.2</a>.</p>
<p><a name="%_sec_5.4.4"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.4.4">5.4.4 Running the
Evaluator</a></h3>
<p><a name="%_idx_6128"></a> <a name="%_idx_6130"></a><a name="%_idx_6132"></a>With the implementation of the explicit-control
evaluator we come to the end of a development, begun in
chapter 1, in which we have explored successively more
precise models of the evaluation process. We started with the
relatively informal substitution model, then extended this in
chapter 3 to the environment model, which enabled us to deal
with state and change. In the metacircular evaluator of
chapter 4, we used Scheme itself as a language for making
more explicit the environment structure constructed during
evaluation of an expression. Now, with register machines, we have
taken a close look at the evaluator's mechanisms for storage
management, argument passing, and control. At each new level of
description, we have had to raise issues and resolve ambiguities
that were not apparent at the previous, less precise treatment of
evaluation. To understand the behavior of the explicit-control
evaluator, we can simulate it and monitor its performance.</p>
<p><a name="%_idx_6134"></a><a name="%_idx_6136"></a>We will
install a driver loop in our evaluator machine. This plays the
role of the <tt>driver-loop</tt> procedure of
section <a href="book-Z-H-26.html#%_sec_4.1.4">4.1.4</a>.
The evaluator will repeatedly print a prompt, read an expression,
evaluate the expression by going to <tt>eval-dispatch</tt>, and
print the result. The following instructions form the beginning
of the explicit-control evaluator's controller sequence:<a href="#footnote_Temp_784" name="call_footnote_Temp_784" id="call_footnote_Temp_784"><sup><small>29</small></sup></a></p>
<p><tt><a name="%_idx_6142"></a><a name="%_idx_6144"></a>read-eval-print-loop<br />
(perform (op initialize-stack))<br />
(perform<br />
(op prompt-for-input) (const ";;; EC-Eval input:"))<br />
(assign exp (op read))<br />
(assign env (op get-global-environment))<br />
(assign continue (label print-result))<br />
(goto (label eval-dispatch))<br />
<a name="%_idx_6146"></a>print-result<br />
(perform<br />
(op announce-output) (const ";;; EC-Eval value:"))<br />
(perform (op user-print) (reg val))<br />
(goto (label read-eval-print-loop))<br /></tt></p>
<p><a name="%_idx_6148"></a><a name="%_idx_6150"></a>When we
encounter an error in a procedure (such as the ``unknown
procedure type error'' indicated at <tt>apply-dispatch</tt>), we
print an error message and return to the driver loop.<a href="#footnote_Temp_785" name="call_footnote_Temp_785" id="call_footnote_Temp_785"><sup><small>30</small></sup></a></p>
<p><tt><a name="%_idx_6152"></a>unknown-expression-type<br />
(assign val (const unknown-expression-type-error))<br />
(goto (label signal-error))<br />
<a name="%_idx_6154"></a>unknown-procedure-type<br />
(restore continue) <em>; clean up stack (from <tt>apply-dispatch</tt>)</em><br />
(assign val (const unknown-procedure-type-error))<br />
(goto (label signal-error))<br />
<a name="%_idx_6156"></a>signal-error<br />
(perform (op user-print) (reg val))<br />
(goto (label read-eval-print-loop))<br /></tt></p>
<p>For the purposes of the simulation, we initialize the stack
each time through the driver loop, since it might not be empty
after an error (such as an undefined variable) interrupts an
evaluation.<a href="#footnote_Temp_786" name="call_footnote_Temp_786" id="call_footnote_Temp_786"><sup><small>31</small></sup></a></p>
<p><a name="%_idx_6158"></a>If we combine all the code fragments
presented in sections <a href="#%_sec_5.4.1">5.4.1</a>-<a href="#%_sec_5.4.4">5.4.4</a>, we can create an evaluator machine
model that we can run using the register-machine simulator of
section <a href="book-Z-H-32.html#%_sec_5.2">5.2</a>.</p>
<p><tt>(define eceval<br />
(make-machine<br />
'(exp env val proc argl continue unev)<br />
eceval-operations<br />
'(<br />
read-eval-print-loop<br />
<<em>entire machine controller as given above</em>><br />
)))<br /></tt></p>
<p>We must define Scheme procedures to simulate the operations
used as primitives by the evaluator. These are the same
procedures we used for the metacircular evaluator in
section <a href="book-Z-H-26.html#%_sec_4.1">4.1</a>,
together with the few additional ones defined in footnotes
throughout section <a href="#%_sec_5.4">5.4</a>.</p>
<p><tt>(define eceval-operations<br />
(list (list 'self-evaluating? self-evaluating)<br />
<em><complete list of operations for eceval machine></em>))<br />
</tt></p>
<p>Finally, we can initialize the global environment and run the
evaluator:</p>
<p>
<tt>(define the-global-environment (setup-environment))<br />
<br />
(start eceval)<br />
<i>;;; EC-Eval input:</i><br />
(define (append x y)<br />
(if (null? x)<br />
y<br />
(cons (car x)<br />
(append (cdr x) y))))<br />
<i>;;; EC-Eval value:</i><br />
<i>ok</i><br />
<i>;;; EC-Eval input:</i><br />
(append '(a b c) '(d e f))<br />
<i>;;; EC-Eval value:</i><br />
<i>(a b c d e f)</i><br /></tt></p>
<p>Of course, evaluating expressions in this way will take much
longer than if we had directly typed them into Scheme, because of
the multiple levels of simulation involved. Our expressions are
evaluated by the explicit-control-evaluator machine, which is
being simulated by a Scheme program, which is itself being
evaluated by the Scheme interpreter.</p>
<p><a name="%_sec_Temp_787"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_787">Monitoring the
performance of the evaluator</a></h4>
<p><a name="%_idx_6160"></a> <a name="%_idx_6162"></a>Simulation
can be a powerful tool to guide the implementation of evaluators.
Simulations make it easy not only to explore variations of the
register-machine design but also to monitor the performance of
the simulated evaluator. For example, one important factor in
performance is how efficiently the evaluator uses the stack. We
can observe the number of stack operations required to evaluate
various expressions by defining the evaluator register machine
with the version of the simulator that collects statistics on
stack use (section <a href="book-Z-H-32.html#%_sec_5.2.4">5.2.4</a>), and adding an
instruction at the evaluator's <tt>print-result</tt> entry point
to print the statistics:</p>
<p><tt><a name="%_idx_6164"></a>print-result<br />
(perform (op print-stack-statistics))<em>; added instruction</em><br />
(perform<br />
(op announce-output) (const ";;; EC-Eval value:"))<br />
</tt>... <em>; same as before</em><br />
</p>
<p>Interactions with the evaluator now look like this:</p>
<p><tt><i>;;; EC-Eval input:</i><br />
(define (factorial n)<br />
(if (= n 1)<br />
1<br />
(* (factorial (- n 1)) n)))<br />
<i>(total-pushes = 3 maximum-depth = 3)</i><br />
<i>;;; EC-Eval value:</i><br />
<i>ok</i><br />
<i>;;; EC-Eval input:</i><br />
(factorial 5)<br />
<i>(total-pushes = 144 maximum-depth = 28)</i><br />
<i>;;; EC-Eval value:</i><br />
<i>120</i><br /></tt></p>
<p>Note that the driver loop of the evaluator reinitializes the
stack at the start of each interaction, so that the statistics
printed will refer only to stack operations used to evaluate the
previous expression.</p>
<p><a name="%_thm_5.26"></a> <b>Exercise
5.26.</b> <a name="%_idx_6166"></a><a name="%_idx_6168"></a><a name="%_idx_6170"></a>Use the monitored stack
to explore the tail-recursive property of the evaluator
(section <a href="#%_sec_5.4.2">5.4.2</a>). Start the
evaluator and define the iterative <tt>factorial</tt> procedure
from section <a href="book-Z-H-11.html#%_sec_1.2.1">1.2.1</a>:</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>Run the procedure with some small values of <em>n</em>. Record
the maximum stack depth and the number of pushes required to
compute <em>n</em>! for each of these values.</p>
<p>a. You will find that the maximum depth required to evaluate
<em>n</em>! is independent of <em>n</em>. What is that depth?</p>
<p>b. Determine from your data a formula in terms of <em>n</em>
for the total number of push operations used in evaluating
<em>n</em>! for any <em>n</em> <u>></u> 1. Note that the
number of operations used is a linear function of <em>n</em> and
is thus determined by two constants.</p>
<p><a name="%_thm_5.27"></a> <b>Exercise
5.27.</b> <a name="%_idx_6172"></a>For comparison with
exercise <a href="#%_thm_5.26">5.26</a>, explore the
behavior of the following procedure for computing factorials
recursively:</p>
<p><tt>(define (factorial n)<br />
(if (= n 1)<br />
1<br />
(* (factorial (- n 1)) n)))<br />
</tt></p>
<p>By running this procedure with the monitored stack, determine,
as a function of <em>n</em>, the maximum depth of the stack and
the total number of pushes used in evaluating <em>n</em>! for
<em>n</em> <u>></u> 1. (Again, these functions will be
linear.) Summarize your experiments by filling in the following
table with the appropriate expressions in terms of
<em>n</em>:</p>
<table border="1">
<tr>
<td valign="top"></td>
<td valign="top">Maximum depth</td>
<td valign="top">Number of pushes</td>
</tr>
<tr>
<td valign="top">Recursive</td>
<td valign="top"></td>
<td valign="top"></td>
</tr>
<tr>
<td valign="top">factorial</td>
<td valign="top"></td>
<td valign="top"></td>
</tr>
<tr>
<td valign="top">Iterative</td>
<td valign="top"></td>
<td valign="top"></td>