forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-31.html
1319 lines (1087 loc) · 62.4 KB
/
book-Z-H-31.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.1"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_5.1">5.1 Designing
Register Machines</a></h2>
<p><a name="%_idx_5462"></a><a name="%_idx_5464"></a><a name="%_idx_5466"></a><a name="%_idx_5468"></a><a name="%_idx_5470"></a><a name="%_idx_5472"></a> To design a register
machine, we must design its <em>data paths</em> (registers and
operations) and the <em>controller</em> that sequences these
operations. To illustrate the design of a simple register
machine, let us examine Euclid's Algorithm, which is used to
compute <a name="%_idx_5474"></a>the greatest common divisor
(GCD) of two integers. As we saw in <a name="%_idx_5476"></a>section <a href="book-Z-H-11.html#%_sec_1.2.5">1.2.5</a>, Euclid's Algorithm can
be carried out by an iterative process, as specified by the
following procedure:</p>
<p><tt>(define (gcd a b)<br />
(if (= b 0)<br />
a<br />
(gcd b (remainder a b))))<br />
</tt></p>
<p>A machine to carry out this algorithm must keep track of two
numbers, <em>a</em> and <em>b</em>, so let us assume that these
numbers are stored in two registers with those names. The basic
operations required are testing whether the contents of register
<tt>b</tt> is zero and computing the remainder of the contents of
register <tt>a</tt> divided by the contents of register
<tt>b</tt>. The remainder operation is a complex process, but
assume for the moment that we have a primitive device that
computes remainders. On each cycle of the GCD algorithm, the
contents of register <tt>a</tt> must be replaced by the contents
of register <tt>b</tt>, and the contents of <tt>b</tt> must be
replaced by the remainder of the old contents of <tt>a</tt>
divided by the old contents of <tt>b</tt>. It would be convenient
if these replacements could be done simultaneously, but in our
model of register machines we will assume that only one register
can be assigned a new value at each step. To accomplish the
replacements, our machine will use a third ``temporary''
register, which we call <tt>t</tt>. (First the remainder will be
placed in <tt>t</tt>, then the contents of <tt>b</tt> will be
placed in <tt>a</tt>, and finally the remainder stored in
<tt>t</tt> will be placed in <tt>b</tt>.)</p>
<p><a name="%_idx_5478"></a><a name="%_idx_5480"></a>We can
illustrate the registers and operations required for this machine
by using the data-path diagram shown in figure <a href="#%_fig_5.1">5.1</a>. In this diagram, the registers (<tt>a</tt>,
<tt>b</tt>, and <tt>t</tt>) are represented by rectangles. Each
way to assign a value to a register is indicated by an arrow with
an <tt>X</tt> behind the head, pointing from the source of data
to the register. We can think of the <tt>X</tt> as a button that,
when pushed, allows the value at the source to ``flow'' into the
designated register. The label next to each button is the name we
will use to refer to the button. The names are arbitrary, and can
be chosen to have mnemonic value (for example, <tt>a<-b</tt>
denotes pushing the button that assigns the contents of register
<tt>b</tt> to register <tt>a</tt>). The source of data for a
register can be another register (as in the <tt>a<-b</tt>
assignment), an operation result (as in the <tt>t<-r</tt>
assignment), or a constant (a built-in value that cannot be
changed, represented in a data-path diagram by a triangle
containing the constant).</p>
<p>An operation that computes a value from constants and the
contents of registers is represented in a data-path diagram by a
trapezoid containing a name for the operation. For example, the
box marked <tt>rem</tt> in figure <a href="#%_fig_5.1">5.1</a> represents an operation that computes the
remainder of the contents of the registers <tt>a</tt> and
<tt>b</tt> to which it is attached. Arrows (without buttons)
point from the input registers and constants to the box, and
arrows connect the operation's output value to registers. A test
is represented by a circle containing a name for the test. For
example, our GCD machine has an operation that tests whether the
contents of register <tt>b</tt> is zero. A test also has arrows
from its input <a name="%_idx_5482"></a><a name="%_idx_5484"></a>registers and constants, but it has no output
arrows; its value is used by the controller rather than by the
data paths. Overall, the data-path diagram shows the registers
and operations that are required for the machine and how they
must be connected. If we view the arrows as wires and the
<tt>X</tt> buttons as switches, the data-path diagram is very
like the wiring diagram for a machine that could be constructed
from electrical components.</p>
<p><a name="%_fig_5.1"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.1:</b> Data paths for a GCD machine.
</div>
<table width="100%">
<tr>
<td><img src="ch5-Z-G-1.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_idx_5486"></a><a name="%_idx_5488"></a>In order for
the data paths to actually compute GCDs, the buttons must be
pushed in the correct sequence. We will describe this sequence in
terms of a controller diagram, as illustrated in
figure <a href="#%_fig_5.2">5.2</a>. The elements of the
controller diagram indicate how the data-path components should
be operated. The rectangular boxes in the controller diagram
identify data-path buttons to be pushed, and the arrows describe
the sequencing from one step to the next. The diamond in the
diagram represents a decision. One of the two sequencing arrows
will be followed, depending on the value of the data-path test
identified in the diamond. We can interpret the controller in
terms of a physical analogy: Think of the diagram as a maze in
which a marble is rolling. When the marble rolls into a box, it
pushes the data-path button that is named by the box. When the
marble rolls into a decision node (such as the test for
<tt>b</tt> = 0), it leaves the node on the path determined by the
result of the indicated test. Taken together, the data paths and
the controller completely describe a machine for computing GCDs.
We start the controller (the rolling marble) at the place marked
<tt>start</tt>, after placing numbers in registers <tt>a</tt> and
<tt>b</tt>. When the controller reaches <tt>done</tt>, we will
find the value of the GCD in register <tt>a</tt>. <a name="%_fig_5.2"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.2:</b> Controller for a GCD machine.
</div>
<table width="100%">
<tr>
<td><img src="ch5-Z-G-2.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_thm_5.1"></a> <b>Exercise
5.1.</b> <a name="%_idx_5490"></a>Design a register
machine to compute factorials using the iterative algorithm
specified by the following procedure. Draw data-path and
controller diagrams for this machine.</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><a name="%_sec_5.1.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.1.1">5.1.1 A Language
for Describing Register Machines</a></h3>
<p><a name="%_idx_5492"></a> Data-path and controller diagrams
are adequate for representing simple machines such as GCD, but
they are unwieldy for describing large machines such as a Lisp
interpreter. To make it possible to deal with complex machines,
we will create a language that presents, in textual form, all the
information given by the data-path and controller diagrams. We
will start with a notation that directly mirrors the
diagrams.</p>
<p>We define the data paths of a machine by describing the
registers and the operations. To describe a register, we give it
a name and specify the buttons that control assignment to it. We
give each of these buttons a name and specify the source of the
data that enters the register under the button's control. (The
source is a register, a constant, or an operation.) To describe
an operation, we give it a name and specify its inputs (registers
or constants).</p>
<p>We define the controller of a machine as a sequence of
<a name="%_idx_5494"></a><em>instructions</em> together with
<a name="%_idx_5496"></a><a name="%_idx_5498"></a><em>labels</em>
that identify <em>entry points</em> in the sequence. An
instruction is one of the following:</p>
<ul>
<li>The name of a data-path button to push to assign a value to
a register. (This corresponds to a box in the controller
diagram.)
<p><a name="%_idx_5500"></a><a name="%_idx_5502"></a></p>
</li>
<li>A <tt>test</tt> instruction, that performs a specified
test.
<p><a name="%_idx_5504"></a><a name="%_idx_5506"></a><a name="%_idx_5508"></a><a name="%_idx_5510"></a></p>
</li>
<li>A conditional branch (<tt>branch</tt> instruction) to a
location indicated by a controller label, based on the result
of the previous test. (The test and branch together correspond
to a diamond in the controller diagram.) If the test is false,
the controller should continue with the next instruction in the
sequence. Otherwise, the controller should continue with the
instruction after the label.
<p><a name="%_idx_5512"></a><a name="%_idx_5514"></a></p>
</li>
<li>An unconditional branch (<tt>goto</tt> instruction) naming
a controller label at which to continue execution.</li>
</ul>
<p>The machine starts at the beginning of the controller
instruction sequence and stops when execution reaches the end of
the sequence. Except when a branch changes the flow of control,
instructions are executed in the order in which they are
listed.</p>
<p><a name="%_fig_5.3"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.3:</b> A specification of the GCD
machine.
</div>
<table width="100%">
<tr>
<td>
<p><tt>(data-paths<br />
(registers<br />
((name a)<br />
(buttons ((name a<-b) (source (register b)))))<br />
((name b)<br />
(buttons ((name b<-t) (source (register t)))))<br />
((name t)<br />
(buttons ((name t<-r) (source (operation rem))))))<br />
<br />
(operations<br />
((name rem)<br />
(inputs (register a) (register b)))<br />
((name =)<br />
(inputs (register b) (constant 0)))))<br />
<br />
(controller<br />
test-b <em>; label</em><br />
(test =) <em>; test</em><br />
(branch (label gcd-done)) <em>; conditional branch</em><br />
(t<-r) <em>; button push</em><br />
(a<-b) <em>; button push</em><br />
(b<-t) <em>; button push</em><br />
(goto (label test-b)) <em>; unconditional branch</em><br />
gcd-done) <em>; label</em><br />
</tt></p>
</td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>Figure <a href="#%_fig_5.3">5.3</a> shows the GCD machine
described in this way. This example only hints at the generality
of these descriptions, since the GCD machine is a very simple
case: Each register has only one button, and each button and test
is used only once in the controller.</p>
<p>Unfortunately, it is difficult to read such a description. In
order to understand the controller instructions we must
constantly refer back to the definitions of the button names and
the operation names, and to understand what the buttons do we may
have to refer to the definitions of the operation names. We will
thus transform our notation to combine the information from the
data-path and controller descriptions so that we see it all
together.</p>
<p>To obtain this form of description, we will replace the
arbitrary button and operation names by the definitions of their
behavior. That is, instead of saying (in the controller) ``Push
button <tt>t<-r</tt>'' and separately saying (in the data
paths) ``Button <tt>t<-r</tt> assigns the value of the
<tt>rem</tt> operation to register <tt>t</tt>'' and ``The
<tt>rem</tt> operation's inputs are the contents of registers
<a name="%_idx_5516"></a><a name="%_idx_5518"></a><a name="%_idx_5520"></a><a name="%_idx_5522"></a><a name="%_idx_5524"></a><a name="%_idx_5526"></a><tt>a</tt> and
<tt>b</tt>,'' we will say (in the controller) ``Push the button
that assigns to register <tt>t</tt> the value of the <tt>rem</tt>
operation on the contents of registers <tt>a</tt> and
<tt>b</tt>.'' Similarly, instead of saying (in the controller)
``Perform the <tt>=</tt> test'' and separately saying (in the
data paths) ``The <tt>=</tt> test operates on the contents of
register <tt>b</tt> and the constant 0,'' we will say ``Perform
the <tt>=</tt> test on the <a name="%_idx_5528"></a><a name="%_idx_5530"></a>contents of register <tt>b</tt> and the constant
0.'' We will omit the data-path description, leaving only the
controller sequence. Thus, the GCD machine is described as
follows:</p>
<p><tt>(controller<br />
test-b<br />
(test (op =) (reg b) (const 0))<br />
(branch (label gcd-done))<br />
(assign t (op rem) (reg a) (reg b))<br />
(assign a (reg b))<br />
(assign b (reg t))<br />
(goto (label test-b))<br />
gcd-done)<br /></tt></p>
<p>This form of description is easier to read than the kind
illustrated in figure <a href="#%_fig_5.3">5.3</a>, but it
also has disadvantages:</p>
<ul>
<li>It is more verbose for large machines, because complete
descriptions of the data-path elements are repeated whenever
the elements are mentioned in the controller instruction
sequence. (This is not a problem in the GCD example, because
each operation and button is used only once.) Moreover,
repeating the data-path descriptions obscures the actual
data-path structure of the machine; it is not obvious for a
large machine how many registers, operations, and buttons there
are and how they are interconnected.</li>
<li>Because the controller instructions in a machine definition
look like Lisp expressions, it is easy to forget that they are
not arbitrary Lisp expressions. They can notate only legal
machine operations. For example, operations can operate
directly only on constants and the contents of registers, not
on the results of other operations.</li>
</ul>
<p>In spite of these disadvantages, we will use this
register-machine language throughout this chapter, because we
will be more concerned with understanding controllers than with
understanding the elements and connections in data paths. We
should keep in mind, however, that data-path design is crucial in
designing real machines.</p>
<p><a name="%_thm_5.2"></a> <b>Exercise
5.2.</b> <a name="%_idx_5532"></a>Use the
register-machine language to describe the iterative factorial
machine of exercise <a href="#%_thm_5.1">5.1</a>.</p>
<p><a name="%_sec_Temp_714"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_714">Actions</a></h4>
<p><a name="%_idx_5534"></a><a name="%_idx_5536"></a> Let us
modify the GCD machine so that we can type in the numbers whose
GCD we want and get the answer printed at our terminal. We will
not discuss how to make a machine that can read and print, but
will assume (as we do when we use <tt>read</tt> and
<tt>display</tt> in Scheme) that they are available as primitive
operations.<a href="#footnote_Temp_715" name="call_footnote_Temp_715" id="call_footnote_Temp_715"><sup><small>1</small></sup></a></p>
<p><a name="%_idx_5538"></a><tt>Read</tt> is like the operations
we have been using in that it produces a value that can be stored
in a register. But <tt>read</tt> does not take inputs from any
registers; its value depends on something that happens outside
the parts of the machine we are designing. We will allow our
machine's operations to have such behavior, and thus will draw
and notate the use of <tt>read</tt> just as we do any other
operation that computes a value.</p>
<p><a name="%_idx_5540"></a><tt>Print</tt>, on the other hand,
differs from the operations we have been using in a fundamental
way: It does not produce an output value to be stored in a
register. Though it has an effect, this effect is not on a part
of the machine we are designing. We will refer to this kind of
operation as an <em>action</em>. We will represent an action in a
data-path diagram just as we represent an operation that computes
a value -- as a trapezoid that contains the name of the action.
Arrows point to the action box from any inputs (registers or
constants). We also associate a button with the action. Pushing
the button makes the action happen. To make a controller push an
action <a name="%_idx_5542"></a><a name="%_idx_5544"></a>button
we use a new kind of instruction called <tt>perform</tt>. Thus,
the action of printing the contents of register <tt>a</tt> is
represented in a controller sequence by the instruction</p>
<p>
<tt>(perform (op print) (reg a))<br /></tt></p>
<p>Figure <a href="#%_fig_5.4">5.4</a> shows the data paths
and controller for the new GCD machine. Instead of having the
machine stop after printing the answer, we have made it start
over, so that it repeatedly reads a pair of numbers, computes
their GCD, and prints the result. This structure is like the
driver loops we used in the interpreters of chapter 4.</p>
<p><a name="%_fig_5.4"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.4:</b> A GCD machine that reads inputs
and prints results.
</div>
<table width="100%">
<tr>
<td>
<img src="ch5-Z-G-3.gif" border="0" />
<p><tt> (controller<br />
gcd-loop<br />
(assign a (op read))<br />
(assign b (op read))<br />
test-b<br />
(test (op =) (reg b) (const 0))<br />
(branch (label gcd-done))<br />
(assign t (op rem) (reg a) (reg b))<br />
(assign a (reg b))<br />
(assign b (reg t))<br />
(goto (label test-b))<br />
gcd-done<br />
(perform (op print) (reg a))<br />
(goto (label gcd-loop)))<br />
</tt></p>
</td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_sec_5.1.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.1.2">5.1.2 Abstraction
in Machine Design</a></h3>
<p><a name="%_idx_5546"></a> We will often define a machine to
include ``primitive'' operations that are actually very complex.
For example, in sections <a href="book-Z-H-34.html#%_sec_5.4">5.4</a> and <a href="book-Z-H-35.html#%_sec_5.5">5.5</a> we will treat Scheme's
environment manipulations as primitive. Such abstraction is
valuable because it allows us to ignore the details of parts of a
machine so that we can concentrate on other aspects of the
design. The fact that we have swept a lot of complexity under the
rug, however, does not mean that a machine design is unrealistic.
We can always replace the complex ``primitives'' by simpler
primitive operations.</p>
<p>Consider the GCD machine. The machine has an instruction that
computes the remainder of the contents of registers <tt>a</tt>
and <tt>b</tt> and assigns the result to register <tt>t</tt>. If
we want to construct the GCD machine without using a primitive
remainder operation, we must specify how to compute remainders in
terms of simpler operations, such as subtraction. Indeed, we can
write a Scheme procedure that finds remainders in this way:</p>
<p><tt>(define (remainder n d)<br />
(if (< n d)<br />
n<br />
(remainder (- n d) d)))<br />
</tt></p>
<p>We can thus replace the remainder operation in the GCD
machine's data paths with a subtraction operation and a
comparison test. Figure <a href="#%_fig_5.5">5.5</a> shows
the data paths and controller for the elaborated machine. The
instruction</p>
<p><a name="%_fig_5.5"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.5:</b> Data paths and controller for
the elaborated GCD machine.
</div>
<table width="100%">
<tr>
<td><img src="ch5-Z-G-4.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>
<tt>(assign t (op rem) (reg a) (reg b))<br />
</tt></p>
<p>in the GCD controller definition is replaced by a sequence of
instructions that contains a loop, as shown in
figure <a href="#%_fig_5.6">5.6</a>.</p>
<p><a name="%_fig_5.6"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.6:</b> Controller instruction sequence
for the GCD machine in figure <a href="#%_fig_5.5">5.5</a>.
</div>
<table width="100%">
<tr>
<td>
<p><tt>(controller<br />
test-b<br />
(test (op =) (reg b) (const 0))<br />
(branch (label gcd-done))<br />
(assign t (reg a))<br />
rem-loop<br />
(test (op <) (reg t) (reg b))<br />
(branch (label rem-done))<br />
(assign t (op -) (reg t) (reg b))<br />
(goto (label rem-loop))<br />
rem-done<br />
(assign a (reg b))<br />
(assign b (reg t))<br />
(goto (label test-b))<br />
gcd-done)<br /></tt></p>
</td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_thm_5.3"></a> <b>Exercise
5.3.</b> <a name="%_idx_5548"></a>Design a machine to
compute square roots using Newton's method, as described in
section <a href="book-Z-H-10.html#%_sec_1.1.7">1.1.7</a>:</p>
<p><tt>(define (sqrt x)<br />
(define (good-enough? guess)<br />
(< (abs (- (square guess) x)) 0.001))<br />
(define (improve guess)<br />
(average guess (/ x guess)))<br />
(define (sqrt-iter guess)<br />
(if (good-enough? guess)<br />
guess<br />
(sqrt-iter (improve guess))))<br />
(sqrt-iter 1.0))<br /></tt></p>
<p>Begin by assuming that <tt>good-enough?</tt> and
<tt>improve</tt> operations are available as primitives. Then
show how to expand these in terms of arithmetic operations.
Describe each version of the <tt>sqrt</tt> machine design by
drawing a data-path diagram and writing a controller definition
in the register-machine language.</p>
<p><a name="%_sec_5.1.3"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.1.3">5.1.3 Subroutines</a></h3>
<p><a name="%_idx_5550"></a><a name="%_idx_5552"></a> When
designing a machine to perform a computation, we would often
prefer to arrange for components to be shared by different parts
of the computation rather than duplicate the components. Consider
a machine that includes two GCD computations -- one that finds
the GCD of the contents of registers <tt>a</tt> and <tt>b</tt>
and one that finds the GCD of the contents of registers
<tt>c</tt> and <tt>d</tt>. We might start by assuming we have a
primitive <tt>gcd</tt> operation, then expand the two instances
of <tt>gcd</tt> in terms of more primitive operations.
Figure <a href="#%_fig_5.7">5.7</a> shows just the GCD
portions of the resulting machine's data paths, without showing
how they connect to the rest of the machine. The figure also
shows the corresponding portions of the machine's controller
sequence.</p>
<p><a name="%_fig_5.7"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.7:</b> Portions of the data paths and
controller sequence for a machine with two GCD computations.
</div>
<table width="100%">
<tr>
<td>
<img src="ch5-Z-G-5.gif" border="0" />
<p><tt>gcd-1<br />
(test (op =) (reg b) (const 0))<br />
(branch (label after-gcd-1))<br />
(assign t (op rem) (reg a) (reg b))<br />
(assign a (reg b))<br />
(assign b (reg t))<br />
(goto (label gcd-1))<br />
after-gcd-1<br />
<img src="book-Z-G-D-18.gif" border="0" /> <br />
gcd-2<br />
(test (op =) (reg d) (const 0))<br />
(branch (label after-gcd-2))<br />
(assign s (op rem) (reg c) (reg d))<br />
(assign c (reg d))<br />
(assign d (reg s))<br />
(goto (label gcd-2))<br />
after-gcd-2<br /></tt></p>
</td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>This machine has two remainder operation boxes and two boxes
for testing equality. If the duplicated components are
complicated, as is the remainder box, this will not be an
economical way to build the machine. We can avoid duplicating the
data-path components by using the same components for both GCD
computations, provided that doing so will not affect the rest of
the larger machine's computation. If the values in registers
<tt>a</tt> and <tt>b</tt> are not needed by the time the
controller gets to <tt>gcd-2</tt> (or if these values can be
moved to other registers for safekeeping), we can change the
machine so that it uses registers <tt>a</tt> and <tt>b</tt>,
rather than registers <tt>c</tt> and <tt>d</tt>, in computing the
second GCD as well as the first. If we do this, we obtain the
controller sequence shown in figure <a href="#%_fig_5.8">5.8</a>.</p>
<p>We have removed the duplicate data-path components (so that
the data paths are again as in figure <a href="#%_fig_5.1">5.1</a>), but the controller now has two GCD
sequences that differ only in their entry-point labels. It would
be better to replace these two sequences by branches to a single
sequence -- a <tt>gcd</tt> <em>subroutine</em> -- at the end of
which we branch back to the correct place in the main instruction
sequence. We can accomplish this as follows: Before branching to
<tt>gcd</tt>, we place a distinguishing value (such as 0
or 1) into a special register, <a name="%_idx_5554"></a><tt>continue</tt>. At the end of the
<tt>gcd</tt> subroutine we return either to <tt>after-gcd-1</tt>
or to <tt>after-gcd-2</tt>, depending on the value of the
<tt>continue</tt> register. Figure <a href="#%_fig_5.9">5.9</a> shows the relevant portion of the resulting
controller sequence, which includes only a single copy of the
<tt>gcd</tt> instructions.</p>
<p><a name="%_fig_5.8"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.8:</b> Portions of the controller
sequence for a machine that uses the same data-path
components for two different GCD computations.
</div>
<table width="100%">
<tr>
<td>
<p><tt>gcd-1<br />
(test (op =) (reg b) (const 0))<br />
(branch (label after-gcd-1))<br />
(assign t (op rem) (reg a) (reg b))<br />
(assign a (reg b))<br />
(assign b (reg t))<br />
(goto (label gcd-1))<br />
after-gcd-1<br />
<img src="book-Z-G-D-18.gif" border="0" /><br />
gcd-2<br />
(test (op =) (reg b) (const 0))<br />
(branch (label after-gcd-2))<br />
(assign t (op rem) (reg a) (reg b))<br />
(assign a (reg b))<br />
(assign b (reg t))<br />
(goto (label gcd-2))<br />
after-gcd-2<br /></tt></p>
</td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_fig_5.9"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.9:</b> Using a <tt>continue</tt>
register to avoid the duplicate controller sequence in
figure <a href="#%_fig_5.8">5.8</a>.
</div>
<table width="100%">
<tr>
<td>
<p><tt>gcd<br />
(test (op =) (reg b) (const 0))<br />
(branch (label gcd-done))<br />
(assign t (op rem) (reg a) (reg b))<br />
(assign a (reg b))<br />
(assign b (reg t))<br />
(goto (label gcd))<br />
gcd-done<br />
(test (op =) (reg continue) (const 0)) <br />
(branch (label after-gcd-1))<br />
(goto (label after-gcd-2))<br />
<img src="book-Z-G-D-18.gif" border="0" /><br />
<em>;; Before branching to <tt>gcd</tt> from the first place where</em><br />
<em>;; it is needed, we place 0 in the <tt>continue</tt> register</em><br />
(assign continue (const 0))<br />
(goto (label gcd))<br />
after-gcd-1<br />
<img src="book-Z-G-D-18.gif" border="0" /><br />
<em>;; Before the second use of <tt>gcd</tt>, we place 1 in the <tt>continue</tt> register</em><br />
(assign continue (const 1))<br />
(goto (label gcd))<br />
after-gcd-2<br /></tt></p>
</td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_fig_5.10"></a></p>
<div align="left">
<div align="left">
<b>Figure 5.10:</b> Assigning labels to the
<tt>continue</tt> register simplifies and generalizes the
strategy shown in figure <a href="#%_fig_5.9">5.9</a>.
</div>
<table width="100%">
<tr>
<td>
<p><tt>gcd<br />
(test (op =) (reg b) (const 0))<br />
(branch (label gcd-done))<br />
(assign t (op rem) (reg a) (reg b))<br />
(assign a (reg b))<br />
(assign b (reg t))<br />
(goto (label gcd))<br />
gcd-done<br />
(goto (reg continue))<br />
<img src="book-Z-G-D-18.gif" border="0" /><br />
<em>;; Before calling <tt>gcd</tt>, we assign to <tt>continue</tt></em><br />
<em>;; the label to which <tt>gcd</tt> should return.</em><br />
(assign continue (label after-gcd-1))<br />
(goto (label gcd))<br />
after-gcd-1<br />
<img src="book-Z-G-D-18.gif" border="0" /><br />
<em>;; Here is the second call to <tt>gcd</tt>, with a different continuation.</em><br />
(assign continue (label after-gcd-2))<br />
(goto (label gcd))<br />
after-gcd-2<br /></tt></p>
</td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>This is a reasonable approach for handling small problems, but
it would be awkward if there were many instances of GCD
computations in the controller sequence. To decide where to
continue executing after the <tt>gcd</tt> subroutine, we would
need tests in the data paths and branch instructions in the
controller for all the places that use <tt>gcd</tt>. A more
powerful method for implementing subroutines is to have the
<tt>continue</tt> register hold the label of the entry point in
the controller sequence at which execution should continue when
the subroutine is finished. Implementing this strategy requires a
new kind of connection between the data paths and the controller
of a register machine: There must be a way to assign to a
register a label in the controller sequence in such a way that
this value can be fetched from the register and used to continue
execution at the designated entry point.</p>
<p><a name="%_idx_5556"></a><a name="%_idx_5558"></a>To reflect
this ability, we will extend the <tt>assign</tt> instruction of
the register-machine language to allow a register to be assigned
as value a label from the controller sequence (as a special kind
of constant). We will also extend the <tt>goto</tt> instruction
to allow execution to continue at the entry point described by
the contents of a register rather than only at an entry point
described by a constant label. Using these new constructs we can
terminate the <tt>gcd</tt> subroutine with a branch to the
location stored in the <tt>continue</tt> register. This leads to
the controller sequence shown in figure <a href="#%_fig_5.10">5.10</a>.</p>
<p>A machine with more than one subroutine could use multiple
continuation registers (e.g., <tt>gcd-continue</tt>,
<tt>factorial-continue</tt>) or we could have all subroutines
share a single <tt>continue</tt> register. Sharing is more
economical, but we must be careful if we have a subroutine
(<tt>sub1</tt>) that calls another subroutine (<tt>sub2</tt>).
Unless <tt>sub1</tt> saves the contents of <tt>continue</tt> in
some other register before setting up <tt>continue</tt> for the
call to <tt>sub2</tt>, <tt>sub1</tt> will not know where to go
when it is finished. The mechanism developed in the next section
to handle recursion also provides a better solution to this
problem of nested subroutine calls.</p>
<p><a name="%_sec_5.1.4"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_5.1.4">5.1.4 Using a
Stack to Implement Recursion</a></h3>
<p><a name="%_idx_5560"></a><a name="%_idx_5562"></a><a name="%_idx_5564"></a> <a name="%_idx_5566"></a>With the ideas
illustrated so far, we can implement any iterative process by
specifying a register machine that has a register corresponding
to each state variable of the process. The machine repeatedly
executes a controller loop, changing the contents of the
registers, until some termination condition is satisfied. At each
point in the controller sequence, the state of the machine
(representing the state of the iterative process) is completely
determined by the contents of the registers (the values of the
state variables).</p>
<p><a name="%_idx_5568"></a><a name="%_idx_5570"></a><a name="%_idx_5572"></a>Implementing recursive processes, however,
requires an additional mechanism. Consider the following
recursive method for computing factorials, which we first
examined in section <a href="book-Z-H-11.html#%_sec_1.2.1">1.2.1</a>:</p>
<p><tt>(define (factorial n)<br />
(if (= n 1)<br />
1<br />
(* (factorial (- n 1)) n)))<br />
</tt></p>
<p>As we see from the procedure, computing <em>n</em>! requires
computing (<em>n</em> - 1)!. Our GCD machine, modeled on the
procedure</p>
<p><tt>(define (gcd a b)<br />
(if (= b 0)<br />
a<br />
(gcd b (remainder a b))))<br />
</tt></p>
<p>similarly had to compute another GCD. But there is an
important difference between the <tt>gcd</tt> procedure, which
reduces the original computation to a new GCD computation, and
<tt>factorial</tt>, which requires computing another factorial as
a subproblem. In GCD, the answer to the new GCD computation is
the answer to the original problem. To compute the next GCD, we
simply place the new arguments in the input registers of the GCD
machine and reuse the machine's data paths by executing the same
controller sequence. When the machine is finished solving the
final GCD problem, it has completed the entire computation.</p>
<p>In the case of factorial (or any recursive process) the answer
to the new factorial subproblem is not the answer to the original
problem. The value obtained for (<em>n</em> - 1)! must be
multiplied by <em>n</em> to get the final answer. If we try to
imitate the GCD design, and solve the factorial subproblem by
decrementing the <tt>n</tt> register and rerunning the factorial
machine, we will no longer have available the old value of
<tt>n</tt> by which to multiply the result. We thus need a second
factorial machine to work on the subproblem. This second
factorial computation itself has a factorial subproblem, which
requires a third factorial machine, and so on. Since each
factorial machine contains another factorial machine within it,
the total machine contains an infinite nest of similar machines
and hence cannot be constructed from a fixed, finite number of
parts.</p>
<p>Nevertheless, we can implement the factorial process as a
register machine if we can arrange to use the same components for
each nested instance of the machine. Specifically, the machine
that computes <em>n</em>! should use the same components to work
on the subproblem of computing (<em>n</em> - 1)!, on the
subproblem for (<em>n</em> - 2)!, and so on. This is plausible
because, although the factorial process dictates that an
unbounded number of copies of the same machine are needed to
perform a computation, only one of these copies needs to be
active at any given time. When the machine encounters a recursive
subproblem, it can suspend work on the main problem, reuse the
same physical parts to work on the subproblem, then continue the
suspended computation.</p>
<p>In the subproblem, the contents of the registers will be
different than they were in the main problem. (In this case the
<tt>n</tt> register is decremented.) In order to be able to
continue the suspended computation, the machine must save the
contents of any registers that will be needed after the
subproblem is solved so that these can be restored to continue
the suspended computation. In the case of factorial, we will save
the old value of <tt>n</tt>, to be restored when we are finished
computing the factorial of the decremented <tt>n</tt>
register.<a href="#footnote_Temp_717" name="call_footnote_Temp_717" id="call_footnote_Temp_717"><sup><small>2</small></sup></a></p>
<p>Since there is no <em>a priori</em> limit on the depth of
nested recursive calls, we may need to save an arbitrary number
of register values. These values must be restored in the reverse
of the order in which they were saved, since in a nest of
recursions the last subproblem to be entered is the first to be
finished. This dictates the use of a <em>stack</em>, or ``last
in, first out'' data structure, to save register values. We can
extend the register-machine language to include a stack by adding
two kinds of instructions: Values are placed <a name="%_idx_5574"></a><a name="%_idx_5576"></a><a name="%_idx_5578"></a><a name="%_idx_5580"></a>on the stack using a
<tt>save</tt> instruction and restored from the stack using a
<tt>restore</tt> instruction. After a sequence of values has been
<tt>save</tt>d on the stack, a sequence of <tt>restore</tt>s will
retrieve these values in reverse order.<a href="#footnote_Temp_718" name="call_footnote_Temp_718" id="call_footnote_Temp_718"><sup><small>3</small></sup></a></p>
<p>With the aid of the stack, we can reuse a single copy of the
factorial machine's data paths for each factorial subproblem.
There is a similar design issue in reusing the controller
sequence that operates the data paths. To reexecute the factorial
computation, the controller cannot simply loop back to the
beginning, as with an iterative process, because after solving
the (<em>n</em> - 1)! subproblem the machine must still multiply
the result by <em>n</em>. The controller must suspend its
computation of <em>n</em>!, solve the (<em>n</em> - 1)!
subproblem, then continue its computation of <em>n</em>!. This
view of the factorial computation suggests the use of the
subroutine mechanism described in section <a href="#%_sec_5.1.3">5.1.3</a>, which has the controller use a <a name="%_idx_5582"></a><tt>continue</tt> register to transfer to the
part of the sequence that solves a subproblem and then continue
where it left off on the main problem. We can thus make a
factorial subroutine that returns to the entry point stored in
the <tt>continue</tt> register. Around each subroutine call, we
save and restore <tt>continue</tt> just as we do the <tt>n</tt>
register, since each ``level'' of the factorial computation will
use the same <tt>continue</tt> register. That is, the factorial
subroutine must put a new value in <tt>continue</tt> when it
calls itself for a subproblem, but it will need the old value in
order to return to the place that called it to solve a
subproblem.</p>
<p>Figure <a href="#%_fig_5.11">5.11</a> shows the data
paths and controller for a machine that implements the recursive
<tt>factorial</tt> procedure. The machine has a stack and three
registers, called <tt>n</tt>, <tt>val</tt>, and