forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-22.html
2904 lines (2214 loc) · 136 KB
/
book-Z-H-22.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_3.3"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.3">3.3 Modeling with
Mutable Data</a></h2>
<p><a name="%_idx_3128"></a> Chapter 2 dealt with compound
data as a means for constructing computational objects that have
several parts, in order to model real-world objects that have
several aspects. In that chapter we introduced the discipline of
data abstraction, according to which data structures are
specified in terms of constructors, which create data objects,
and selectors, which access the parts of compound data objects.
But we now know that there is another aspect of data that
chapter 2 did not address. The desire to model systems
composed of objects that have changing state leads us to the need
to modify compound data objects, as well as to construct and
select from them. In order to model compound objects with
changing state, we will design data abstractions to include, in
addition to selectors and constructors, operations called
<a name="%_idx_3130"></a><em>mutators</em>, which modify data
objects. For instance, modeling a banking system requires us to
change account balances. Thus, a data structure for representing
bank accounts might admit an operation</p>
<p>
<tt>(set-balance! <<em>account</em>> <<em>new-value</em>>)<br />
</tt></p>
<p>that changes the balance of the designated account to the
designated new value. Data objects for which mutators are defined
are known as <em>mutable data objects</em>.</p>
<p>Chapter 2 introduced pairs as a general-purpose ``glue''
for synthesizing compound data. We begin this section by defining
basic mutators for pairs, so that pairs can serve as building
blocks for constructing mutable data objects. These mutators
greatly enhance the representational power of pairs, enabling us
to build data structures other than the sequences and trees that
we worked with in section <a href="book-Z-H-15.html#%_sec_2.2">2.2</a>. We also present some
examples of simulations in which complex systems are modeled as
collections of objects with local state.</p>
<p><a name="%_sec_3.3.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.3.1">3.3.1 Mutable List
Structure</a></h3>
<p><a name="%_idx_3132"></a><a name="%_idx_3134"></a> <a name="%_idx_3136"></a><a name="%_idx_3138"></a> The basic operations
on pairs -- <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt> -- can
be used to construct list structure and to select parts from list
structure, but they are incapable of modifying list structure.
The same is true of the list operations we have used so far, such
as <tt>append</tt> and <tt>list</tt>, since these can be defined
in terms of <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt>. To
modify list structures we need new operations.</p>
<p><a name="%_fig_3.12"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.12:</b> Lists <tt>x</tt>: <tt>((a b) c
d)</tt> and <tt>y</tt>: <tt>(e f)</tt>.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-13.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_fig_3.13"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.13:</b> Effect of <tt>(set-car! x
y)</tt> on the lists in figure <a href="#%_fig_3.12">3.12</a>.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-14.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_fig_3.14"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.14:</b> Effect of <tt>(define z (cons
y (cdr x)))</tt> on the lists in figure <a href="#%_fig_3.12">3.12</a>.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-15.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_fig_3.15"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.15:</b> Effect of <tt>(set-cdr! x
y)</tt> on the lists in figure <a href="#%_fig_3.12">3.12</a>.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-16.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_idx_3140"></a><a name="%_idx_3142"></a><a name="%_idx_3144"></a><a name="%_idx_3146"></a>The primitive mutators
for pairs are <tt>set-car!</tt> and <tt>set-cdr!</tt>.
<tt>Set-car!</tt> takes two arguments, the first of which must be
a pair. It modifies this pair, replacing the <tt>car</tt> pointer
by a pointer to the second argument of <tt>set-car!</tt>.<a href="#footnote_Temp_349" name="call_footnote_Temp_349" id="call_footnote_Temp_349"><sup><small>16</small></sup></a></p>
<p>As an example, suppose that <tt>x</tt> is bound to the list
<tt>((a b) c d)</tt> and <tt>y</tt> to the list <tt>(e f)</tt> as
illustrated in figure <a href="#%_fig_3.12">3.12</a>.
Evaluating the expression <tt>(set-car! x y)</tt> modifies the
pair to which <tt>x</tt> is bound, replacing its <tt>car</tt> by
the value of <tt>y</tt>. The result of the operation is shown in
figure <a href="#%_fig_3.13">3.13</a>. The structure
<tt>x</tt> has been modified and would now be printed as
<tt>((e f) c d)</tt>. The pairs representing the
list <tt>(a b)</tt>, identified by the pointer that was replaced,
are now detached from the original structure.<a href="#footnote_Temp_350" name="call_footnote_Temp_350" id="call_footnote_Temp_350"><sup><small>17</small></sup></a></p>
<p>Compare figure <a href="#%_fig_3.13">3.13</a> with
figure <a href="#%_fig_3.14">3.14</a>, which illustrates the
result of executing <tt>(define z (cons y (cdr x)))</tt> with
<tt>x</tt> and <tt>y</tt> bound to the original lists of
figure <a href="#%_fig_3.12">3.12</a>. The variable
<tt>z</tt> is now bound to a new pair created by the
<tt>cons</tt> operation; the list to which <tt>x</tt> is bound is
unchanged.</p>
<p>The <tt>set-cdr!</tt> operation is similar to
<tt>set-car!</tt>. The only difference is that the <tt>cdr</tt>
pointer of the pair, rather than the <tt>car</tt> pointer, is
replaced. The effect of executing <tt>(set-cdr! x y)</tt> on the
lists of figure <a href="#%_fig_3.12">3.12</a> is shown in
figure <a href="#%_fig_3.15">3.15</a>. Here the <tt>cdr</tt>
pointer of <tt>x</tt> has been replaced by the pointer to <tt>(e
f)</tt>. Also, the list <tt>(c d)</tt>, which used to be the
<tt>cdr</tt> of <tt>x</tt>, is now detached from the
structure.</p>
<p><a name="%_idx_3158"></a><tt>Cons</tt> builds new list
structure by creating new pairs, while <tt>set-car!</tt> and
<tt>set-cdr!</tt> modify existing pairs. Indeed, we could
implement <tt>cons</tt> in terms of the two mutators, together
with a procedure <tt>get-new-pair</tt>, which returns a new pair
that is not part of any existing list structure. We obtain the
new pair, set its <tt>car</tt> and <tt>cdr</tt> pointers to the
designated objects, and return the new pair as the result of the
<tt>cons</tt>.<a href="#footnote_Temp_351" name="call_footnote_Temp_351" id="call_footnote_Temp_351"><sup><small>18</small></sup></a></p>
<p><tt><a name="%_idx_3160"></a>(define (cons x y)<br />
(let ((new (get-new-pair)))<br />
(set-car! new x)<br />
(set-cdr! new y)<br />
new))<br /></tt></p>
<p><a name="%_thm_3.12"></a> <b>Exercise
3.12.</b> <a name="%_idx_3162"></a>The following
procedure for appending lists was introduced in
section <a href="book-Z-H-15.html#%_sec_2.2.1">2.2.1</a>:</p>
<p><tt><a name="%_idx_3164"></a>(define (append x y)<br />
(if (null? x)<br />
y<br />
(cons (car x) (append (cdr x) y))))<br />
</tt></p>
<p><tt>Append</tt> forms a new list by successively
<tt>cons</tt>ing the elements of <tt>x</tt> onto <tt>y</tt>. The
procedure <tt>append!</tt> is similar to <tt>append</tt>, but it
is a mutator rather than a constructor. It appends the lists by
splicing them together, modifying the final pair of <tt>x</tt> so
that its <tt>cdr</tt> is now <tt>y</tt>. (It is an error to call
<tt>append!</tt> with an empty <tt>x</tt>.)</p>
<p><tt><a name="%_idx_3166"></a>(define (append! x y)<br />
(set-cdr! (last-pair x) y)<br />
x)<br /></tt></p>
<p>Here <tt>last-pair</tt> is a procedure that returns the last
pair in its argument:</p>
<p><tt><a name="%_idx_3168"></a>(define (last-pair x)<br />
(if (null? (cdr x))<br />
x<br />
(last-pair (cdr x))))<br />
</tt></p>
<p>Consider the interaction</p>
<p><tt>(define x (list 'a 'b))<br />
(define y (list 'c 'd))<br />
(define z (append x y))<br />
z<br />
<i>(a b c d)</i><br />
(cdr x)<br />
<<em>response</em>><br />
(define w (append! x y))<br />
w<br />
<i>(a b c d)</i><br />
(cdr x)<br />
<<em>response</em>><br /></tt></p>
<p>What are the missing <<em>response</em>>s? Draw
box-and-pointer diagrams to explain your answer.</p>
<p><a name="%_thm_3.13"></a> <b>Exercise
3.13.</b> <a name="%_idx_3170"></a>Consider the
following <tt>make-cycle</tt> procedure, which uses the
<tt>last-pair</tt> procedure defined in exercise <a href="#%_thm_3.12">3.12</a>:</p>
<p><tt><a name="%_idx_3172"></a>(define (make-cycle x)<br />
(set-cdr! (last-pair x) x)<br />
x)<br /></tt></p>
<p>Draw a box-and-pointer diagram that shows the structure
<tt>z</tt> created by</p>
<p>
<tt>(define z (make-cycle (list 'a 'b 'c)))<br />
</tt></p>
<p>What happens if we try to compute <tt>(last-pair z)</tt>?</p>
<p><a name="%_thm_3.14"></a> <b>Exercise 3.14.</b> The
following procedure is quite useful, although obscure:</p>
<p><tt><a name="%_idx_3174"></a>(define (mystery x)<br />
(define (loop x y)<br />
(if (null? x)<br />
y<br />
(let ((temp (cdr x)))<br />
(set-cdr! x y)<br />
(loop temp x))))<br />
(loop x '()))<br /></tt></p>
<p><tt>Loop</tt> uses the ``temporary'' variable <tt>temp</tt> to
hold the old value of the <tt>cdr</tt> of <tt>x</tt>, since the
<tt>set-cdr!</tt> on the next line destroys the <tt>cdr</tt>.
Explain what <tt>mystery</tt> does in general. Suppose <tt>v</tt>
is defined by <tt>(define v (list 'a 'b 'c 'd))</tt>. Draw the
box-and-pointer diagram that represents the list to which
<tt>v</tt> is bound. Suppose that we now evaluate <tt>(define w
(mystery v))</tt>. Draw box-and-pointer diagrams that show the
structures <tt>v</tt> and <tt>w</tt> after evaluating this
expression. What would be printed as the values of <tt>v</tt> and
<tt>w</tt> ?</p>
<p><a name="%_sec_Temp_355"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_355">Sharing and
identity</a></h4>
<p><a name="%_idx_3176"></a><a name="%_idx_3178"></a> <a name="%_idx_3180"></a><a name="%_idx_3182"></a>We mentioned in
section <a href="book-Z-H-20.html#%_sec_3.1.3">3.1.3</a> the
theoretical issues of ``sameness'' and ``change'' raised by the
introduction of assignment. These issues arise in practice when
individual pairs are <em>shared</em> among different data
objects. For example, consider the structure formed by</p>
<p><tt>(define x (list 'a 'b))<br />
(define z1 (cons x x))<br /></tt></p>
<p>As shown in figure <a href="#%_fig_3.16">3.16</a>,
<tt>z1</tt> is a pair whose <tt>car</tt> and <tt>cdr</tt> both
point to the same pair <tt>x</tt>. This sharing of <tt>x</tt> by
the <tt>car</tt> and <tt>cdr</tt> of <tt>z1</tt> is a consequence
of the straightforward way in which <tt>cons</tt> is implemented.
In general, using <tt>cons</tt> to construct lists will result in
an interlinked structure of pairs in which many individual pairs
are shared by many different structures.</p>
<p><a name="%_fig_3.16"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.16:</b> The list <tt>z1</tt> formed by
<tt>(cons x x)</tt>.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-17.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_fig_3.17"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.17:</b> The list <tt>z2</tt> formed by
<tt>(cons (list 'a 'b) (list 'a 'b))</tt>.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-18.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>In contrast to figure <a href="#%_fig_3.16">3.16</a>,
figure <a href="#%_fig_3.17">3.17</a> shows the structure
created by</p>
<p>
<tt>(define z2 (cons (list 'a 'b) (list 'a 'b)))<br />
</tt></p>
<p>In this structure, the pairs in the two <tt>(a b)</tt> lists
are distinct, although the actual symbols are shared.<a href="#footnote_Temp_356" name="call_footnote_Temp_356" id="call_footnote_Temp_356"><sup><small>19</small></sup></a></p>
<p>When thought of as a list, <tt>z1</tt> and <tt>z2</tt> both
represent ``the same'' list, <tt>((a b) a b)</tt>. In general,
sharing is completely undetectable if we operate on lists using
only <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt>. However, if
we allow mutators on list structure, sharing becomes significant.
As an example of the difference that sharing can make, consider
the following procedure, which modifies the <tt>car</tt> of the
structure to which it is applied:</p>
<p><tt>(define (set-to-wow! x)<br />
(set-car! (car x) 'wow)<br />
x)<br /></tt></p>
<p>Even though <tt>z1</tt> and <tt>z2</tt> are ``the same''
structure, applying <tt>set-to-wow!</tt> to them yields different
results. With <tt>z1</tt>, altering the <tt>car</tt> also changes
the <tt>cdr</tt>, because in <tt>z1</tt> the <tt>car</tt> and the
<tt>cdr</tt> are the same pair. With <tt>z2</tt>, the
<tt>car</tt> and <tt>cdr</tt> are distinct, so
<tt>set-to-wow!</tt> modifies only the <tt>car</tt>:</p>
<p><tt>z1<br />
<i>((a b) a b)</i><br />
<br />
(set-to-wow! z1)<br />
<i>((wow b) wow b)</i><br />
<br />
z2<br />
<i>((a b) a b)</i><br />
<br />
(set-to-wow! z2)<br />
<i>((wow b) a b)</i><br /></tt></p>
<p>One way to detect sharing in list structures is to use the
predicate <a name="%_idx_3186"></a><a name="%_idx_3188"></a><tt>eq?</tt>, which we introduced in
section <a href="book-Z-H-16.html#%_sec_2.3.1">2.3.1</a> as
a way to test whether two symbols are equal. More generally,
<tt>(eq? x y)</tt> tests whether <tt>x</tt> and <tt>y</tt> are
the same object (that is, whether <tt>x</tt> and <tt>y</tt> are
equal as pointers). Thus, with <tt>z1</tt> and <tt>z2</tt> as
defined in figures <a href="#%_fig_3.16">3.16</a>
and <a href="#%_fig_3.17">3.17</a>, <tt>(eq? (car z1)
(cdr z1))</tt> is true and <tt>(eq? (car z2) (cdr z2))</tt>
is false.</p>
<p><a name="%_idx_3190"></a>As will be seen in the following
sections, we can exploit sharing to greatly extend the repertoire
of data structures that can be represented by pairs. On the other
hand, sharing can also be dangerous, since modifications made to
structures will also affect other structures that happen to share
the modified parts. The mutation operations <tt>set-car!</tt> and
<tt>set-cdr!</tt> should be used with care; unless we have a good
understanding of how our data objects are shared, mutation can
have unanticipated results.<a href="#footnote_Temp_357" name="call_footnote_Temp_357" id="call_footnote_Temp_357"><sup><small>20</small></sup></a></p>
<p><a name="%_thm_3.15"></a> <b>Exercise
3.15.</b> Draw box-and-pointer diagrams to explain the
effect of <tt>set-to-wow!</tt> on the structures <tt>z1</tt> and
<tt>z2</tt> above.</p>
<p><a name="%_thm_3.16"></a> <b>Exercise 3.16.</b> Ben
Bitdiddle decides to write a procedure to count the number of
pairs in any list structure. ``It's easy,'' he reasons. ``The
number of pairs in any structure is the number in the
<tt>car</tt> plus the number in the <tt>cdr</tt> plus one more to
count the current pair.'' So Ben writes the following
procedure:</p>
<p><tt><a name="%_idx_3192"></a>(define (count-pairs x)<br />
(if (not (pair? x))<br />
0<br />
(+ (count-pairs (car x))<br />
(count-pairs (cdr x))<br />
1)))<br /></tt></p>
<p>Show that this procedure is not correct. In particular, draw
box-and-pointer diagrams representing list structures made up of
exactly three pairs for which Ben's procedure would return 3;
return 4; return 7; never return at all.</p>
<p><a name="%_thm_3.17"></a> <b>Exercise
3.17.</b> Devise a correct version of the
<tt>count-pairs</tt> procedure of exercise <a href="#%_thm_3.16">3.16</a> that returns the number of distinct pairs
in any structure. (Hint: Traverse the structure, maintaining an
auxiliary data structure that is used to keep track of which
pairs have already been counted.)</p>
<p><a name="%_thm_3.18"></a> <b>Exercise
3.18.</b> <a name="%_idx_3194"></a>Write a procedure
that examines a list and determines whether it contains a cycle,
that is, whether a program that tried to find the end of the list
by taking successive <tt>cdr</tt>s would go into an infinite
loop. Exercise <a href="#%_thm_3.13">3.13</a> constructed
such lists.</p>
<p><a name="%_thm_3.19"></a> <b>Exercise
3.19.</b> Redo exercise <a href="#%_thm_3.18">3.18</a> using an algorithm that takes only a
constant amount of space. (This requires a very clever idea.)</p>
<p><a name="%_sec_Temp_363"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_363">Mutation is
just assignment</a></h4>
<p><a name="%_idx_3196"></a><a name="%_idx_3198"></a><a name="%_idx_3200"></a><a name="%_idx_3202"></a> When we introduced
compound data, we observed in section <a href="book-Z-H-14.html#%_sec_2.1.3">2.1.3</a> that pairs can be
represented purely in terms of procedures:</p>
<p><tt><a name="%_idx_3204"></a>(define (cons x y)<br />
(define (dispatch m)<br />
(cond ((eq? m 'car) x)<br />
((eq? m 'cdr) y)<br />
(else (error "Undefined operation -- CONS" m))))<br />
dispatch)<br />
<a name="%_idx_3206"></a>(define (car z) (z 'car))<br />
<a name="%_idx_3208"></a>(define (cdr z) (z 'cdr))<br />
</tt></p>
<p>The same observation is true for mutable data. We can
implement mutable data objects as procedures using assignment and
local state. For instance, we can extend the above pair
implementation to handle <tt>set-car!</tt> and <tt>set-cdr!</tt>
in a manner analogous to the way we implemented bank accounts
using <tt>make-account</tt> in section <a href="book-Z-H-20.html#%_sec_3.1.1">3.1.1</a>:</p>
<p><tt><a name="%_idx_3210"></a>(define (cons x y)<br />
(define (set-x! v) (set! x v))<br />
(define (set-y! v) (set! y v))<br />
(define (dispatch m)<br />
(cond ((eq? m 'car) x)<br />
((eq? m 'cdr) y)<br />
((eq? m 'set-car!) set-x!)<br />
((eq? m 'set-cdr!) set-y!)<br />
(else (error "Undefined operation -- CONS" m))))<br />
dispatch)<br />
<a name="%_idx_3212"></a>(define (car z) (z 'car))<br />
<a name="%_idx_3214"></a>(define (cdr z) (z 'cdr))<br />
<a name="%_idx_3216"></a>(define (set-car! z new-value)<br />
((z 'set-car!) new-value)<br />
z)<br />
<a name="%_idx_3218"></a>(define (set-cdr! z new-value)<br />
((z 'set-cdr!) new-value)<br />
z)<br /></tt></p>
<p>Assignment is all that is needed, theoretically, to account
for the behavior of mutable data. As soon as we admit
<tt>set!</tt> to our language, we raise all the issues, not only
of assignment, but of mutable data in general.<a href="#footnote_Temp_364" name="call_footnote_Temp_364" id="call_footnote_Temp_364"><sup><small>21</small></sup></a></p>
<p><a name="%_thm_3.20"></a> <b>Exercise
3.20.</b> Draw environment diagrams to illustrate the
evaluation of the sequence of expressions</p>
<p><tt>(define x (cons 1 2))<br />
(define z (cons x x))<br />
(set-car! (cdr z) 17)<br />
(car x)<br />
<i>17</i><br /></tt></p>
<p>using the procedural implementation of pairs given above.
(Compare exercise <a href="book-Z-H-21.html#%_thm_3.11">3.11</a>.)</p>
<p><a name="%_sec_3.3.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.3.2">3.3.2 Representing
Queues</a></h3>
<p><a name="%_idx_3220"></a> The mutators <tt>set-car!</tt> and
<tt>set-cdr!</tt> enable us to use pairs to construct data
structures that cannot be built with <tt>cons</tt>, <tt>car</tt>,
and <tt>cdr</tt> alone. This section shows how to use pairs to
represent a data structure called a queue. Section <a href="#%_sec_3.3.3">3.3.3</a> will show how to represent data
structures called tables.</p>
<p>A <em>queue</em> is a sequence in which items are inserted at
one end (called the <a name="%_idx_3222"></a><em>rear</em> of the
queue) and deleted from the other end (the <a name="%_idx_3224"></a><em>front</em>). Figure <a href="#%_fig_3.18">3.18</a> shows an initially empty queue in which
the items <tt>a</tt> and <tt>b</tt> are inserted. Then <tt>a</tt>
is removed, <tt>c</tt> and <tt>d</tt> are inserted, and
<tt>b</tt> is removed. Because items are always removed in the
order in which they are inserted, a queue is sometimes called a
<a name="%_idx_3226"></a><em>FIFO</em> (first in, first out)
buffer.</p>
<p><a name="%_fig_3.18"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.18:</b> Queue operations.
</div>
<table width="100%">
<tr>
<td>
<table border="0">
<tr>
<td valign="top">Operation</td>
<td valign="top">Resulting Queue</td>
</tr>
<tr>
<td valign="top"><tt>(define q
(make-queue))</tt></td>
<td valign="top"></td>
</tr>
<tr>
<td valign="top"><tt>(insert-queue! q 'a)</tt></td>
<td valign="top"><tt>a</tt></td>
</tr>
<tr>
<td valign="top"><tt>(insert-queue! q 'b)</tt></td>
<td valign="top"><tt>a b</tt></td>
</tr>
<tr>
<td valign="top"><tt>(delete-queue! q)</tt></td>
<td valign="top"><tt>b</tt></td>
</tr>
<tr>
<td valign="top"><tt>(insert-queue! q 'c)</tt></td>
<td valign="top"><tt>b c</tt></td>
</tr>
<tr>
<td valign="top"><tt>(insert-queue! q 'd)</tt></td>
<td valign="top"><tt>b c d</tt></td>
</tr>
<tr>
<td valign="top"><tt>(delete-queue! q)</tt></td>
<td valign="top"><tt>c d</tt></td>
</tr>
</table>
</td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><a name="%_idx_3228"></a><a name="%_idx_3230"></a>In terms of
data abstraction, we can regard a queue as defined by the
following set of operations:</p>
<ul>
<li>a constructor:<br />
<a name="%_idx_3232"></a><tt>(make-queue)</tt><br />
returns an empty queue (a queue containing no items).</li>
<li>two selectors:<br />
<a name="%_idx_3234"></a><tt>(empty-queue?
<<em>queue</em>>)</tt><br />
tests if the queue is empty.<br />
<a name="%_idx_3236"></a><tt>(front-queue
<<em>queue</em>>)</tt><br />
returns the object at the front of the queue, signaling an
error if the queue is empty; it does not modify the queue.</li>
<li>two mutators:<br />
<a name="%_idx_3238"></a><tt>(insert-queue!
<<em>queue</em>> <<em>item</em>>)</tt><br />
inserts the item at the rear of the queue and returns the
modified queue as its value.<br />
<a name="%_idx_3240"></a><tt>(delete-queue!
<<em>queue</em>>)</tt><br />
removes the item at the front of the queue and returns the
modified queue as its value, signaling an error if the queue is
empty before the deletion.</li>
</ul>
<p>Because a queue is a sequence of items, we could certainly
represent it as an ordinary list; the front of the queue would be
the <tt>car</tt> of the list, inserting an item in the queue
would amount to appending a new element at the end of the list,
and deleting an item from the queue would just be taking the
<tt>cdr</tt> of the list. However, this representation is
inefficient, because in order to insert an item we must scan the
list until we reach the end. Since the only method we have for
scanning a list is by successive <tt>cdr</tt> operations, this
scanning requires <img src="book-Z-G-D-3.gif" border="0" />(<em>n</em>) steps for a list of <em>n</em> items. A simple
modification to the list representation overcomes this
disadvantage by allowing the queue operations to be implemented
so that they require <img src="book-Z-G-D-3.gif" border="0" />(1)
steps; that is, so that the number of steps needed is independent
of the length of the queue.</p>
<p>The difficulty with the list representation arises from the
need to scan to find the end of the list. The reason we need to
scan is that, although the standard way of representing a list as
a chain of pairs readily provides us with a pointer to the
beginning of the list, it gives us no easily accessible pointer
to the end. The modification that avoids the drawback is to
represent the queue as a list, together with an additional
pointer that indicates the final pair in the list. That way, when
we go to insert an item, we can consult the rear pointer and so
avoid scanning the list.</p>
<p>A queue is represented, then, as a pair of pointers,
<tt>front-ptr</tt> and <tt>rear-ptr</tt>, which indicate,
respectively, the first and last pairs in an ordinary list. Since
we would like the queue to be an identifiable object, we can use
<tt>cons</tt> to combine the two pointers. Thus, the queue itself
will be the <tt>cons</tt> of the two pointers.
Figure <a href="#%_fig_3.19">3.19</a> illustrates this
representation.</p>
<p><a name="%_fig_3.19"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.19:</b> Implementation of a queue as a
list with front and rear pointers.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-19.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>To define the queue operations we use the following
procedures, which enable us to select and to modify the front and
rear pointers of a queue:</p>
<p><tt><a name="%_idx_3242"></a>(define (front-ptr queue) (car queue))<br />
<a name="%_idx_3244"></a>(define (rear-ptr queue) (cdr queue))<br />
<a name="%_idx_3246"></a>(define (set-front-ptr! queue item) (set-car! queue item))<br />
<a name="%_idx_3248"></a>(define (set-rear-ptr! queue item) (set-cdr! queue item))<br />
</tt></p>
<p>Now we can implement the actual queue operations. We will
consider a queue to be empty if its front pointer is the empty
list:</p>
<p><tt><a name="%_idx_3250"></a>(define (empty-queue? queue) (null? (front-ptr queue)))<br />
</tt></p>
<p>The <tt>make-queue</tt> constructor returns, as an initially
empty queue, a pair whose <tt>car</tt> and <tt>cdr</tt> are both
the empty list:</p>
<p><tt><a name="%_idx_3252"></a>(define (make-queue) (cons '() '()))<br />
</tt></p>
<p>To select the item at the front of the queue, we return the
<tt>car</tt> of the pair indicated by the front pointer:</p>
<p><tt><a name="%_idx_3254"></a>(define (front-queue queue)<br />
(if (empty-queue? queue)<br />
(error "FRONT called with an empty queue" queue)<br />
(car (front-ptr queue))))<br />
</tt></p>
<p>To insert an item in a queue, we follow the method whose
result is indicated in figure <a href="#%_fig_3.20">3.20</a>. We first create a new pair whose
<tt>car</tt> is the item to be inserted and whose <tt>cdr</tt> is
the empty list. If the queue was initially empty, we set the
front and rear pointers of the queue to this new pair. Otherwise,
we modify the final pair in the queue to point to the new pair,
and also set the rear pointer to the new pair.</p>
<p><a name="%_fig_3.20"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.20:</b> Result of using
<tt>(insert-queue! q 'd)</tt> on the queue of
figure <a href="#%_fig_3.19">3.19</a>.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-20.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><tt><a name="%_idx_3256"></a>(define (insert-queue! queue item)<br />
(let ((new-pair (cons item '())))<br />
(cond ((empty-queue? queue)<br />
(set-front-ptr! queue new-pair)<br />
(set-rear-ptr! queue new-pair)<br />
queue)<br />
(else<br />
(set-cdr! (rear-ptr queue) new-pair)<br />
(set-rear-ptr! queue new-pair)<br />
queue)))) <br />
</tt></p>
<p>To delete the item at the front of the queue, we merely modify
the front pointer so that it now points at the second item in the
queue, which can be found by following the <tt>cdr</tt> pointer
of the first item (see figure <a href="#%_fig_3.21">3.21</a>):<a href="#footnote_Temp_366" name="call_footnote_Temp_366" id="call_footnote_Temp_366"><sup><small>22</small></sup></a></p>
<p><a name="%_fig_3.21"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.21:</b> Result of using
<tt>(delete-queue! q)</tt> on the queue of
figure <a href="#%_fig_3.20">3.20</a>.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-21.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p><tt><a name="%_idx_3258"></a>(define (delete-queue! queue)<br />
(cond ((empty-queue? queue)<br />
(error "DELETE! called with an empty queue" queue))<br />
(else<br />
(set-front-ptr! queue (cdr (front-ptr queue)))<br />
queue))) <br />
</tt></p>
<p><a name="%_thm_3.21"></a> <b>Exercise 3.21.</b> Ben
Bitdiddle decides to test the queue implementation described
above. He types in the procedures to the Lisp interpreter and
proceeds to try them out:</p>
<p><tt>(define q1 (make-queue))<br />
(insert-queue! q1 'a)<br />
<i>((a) a)</i><br />
(insert-queue! q1 'b)<br />
<i>((a b) b)</i><br />
(delete-queue! q1)<br />
<i>((b) b)</i><br />
(delete-queue! q1)<br />
<i>(() b)</i><br /></tt></p>
<p>``It's all wrong!'' he complains. ``The interpreter's response
shows that the last item is inserted into the queue twice. And
when I delete both items, the second <tt>b</tt> is still there,
so the queue isn't empty, even though it's supposed to be.'' Eva
Lu Ator suggests that Ben has misunderstood what is happening.
``It's not that the items are going into the queue twice,'' she
explains. ``It's just that the standard Lisp printer doesn't know
how to make sense of the queue representation. If you want to see
the queue printed correctly, you'll have to define your own print
procedure for queues.'' Explain what Eva Lu is talking about. In
particular, show why Ben's examples produce the printed results
that they do. Define a procedure <a name="%_idx_3260"></a><tt>print-queue</tt> that takes a queue as input
and prints the sequence of items in the queue.</p>
<p><a name="%_thm_3.22"></a> <b>Exercise
3.22.</b> <a name="%_idx_3262"></a>Instead of
representing a queue as a pair of pointers, we can build a queue
as a procedure with local state. The local state will consist of
pointers to the beginning and the end of an ordinary list. Thus,
the <tt>make-queue</tt> procedure will have the form</p>
<p><tt>(define (make-queue)<br />
(let ((front-ptr </tt>...)<br />
(rear-ptr <tt>...</tt>))<br />
<<em>definitions of internal procedures</em>><br />
(define (dispatch m) <tt>...</tt>)<br />
dispatch))<br /></p>
<p>Complete the definition of <tt>make-queue</tt> and provide
implementations of the queue operations using this
representation.</p>
<p><a name="%_thm_3.23"></a> <b>Exercise
3.23.</b> <a name="%_idx_3264"></a><a name="%_idx_3266"></a>A <em>deque</em> (``double-ended queue'') is a
sequence in which items can be inserted and deleted at either the
front or the rear. Operations on deques are the constructor
<tt>make-deque</tt>, the predicate <tt>empty-deque?</tt>,
selectors <tt>front-deque</tt> and <tt>rear-deque</tt>, and
mutators <tt>front-insert-deque!</tt>,
<tt>rear-insert-deque!</tt>, <tt>front-delete-deque!</tt>, and
<tt>rear-delete-deque!</tt>. Show how to represent deques using
pairs, and give implementations of the operations.<a href="#footnote_Temp_370" name="call_footnote_Temp_370" id="call_footnote_Temp_370"><sup><small>23</small></sup></a> All
operations should be accomplished in <img src="book-Z-G-D-3.gif" border="0" />(1) steps.</p>
<p><a name="%_sec_3.3.3"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.3.3">3.3.3 Representing
Tables</a></h3>
<p><a name="%_idx_3268"></a> <a name="%_idx_3270"></a>When we
studied various ways of representing sets in chapter 2, we
mentioned in section <a href="book-Z-H-16.html#%_sec_2.3.3">2.3.3</a> the task of maintaining
a table of records indexed by identifying keys. In the
implementation of data-directed programming in
section <a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>, we
made extensive use of two-dimensional tables, in which
information is stored and retrieved using two keys. Here we see
how to build tables as mutable list structures.</p>
<p><a name="%_idx_3272"></a>We first consider a one-dimensional
table, in which each value is stored under a single key. We
implement the table as a list of records, each of which is
implemented as a pair consisting of a key and the associated
value. The records are glued together to form a list by pairs
whose <tt>car</tt>s point to successive records. These gluing
pairs are called the <a name="%_idx_3274"></a><em>backbone</em>
of the table. In order to have a place that we can change when we
add a new record to the table, we build the table as a <a name="%_idx_3276"></a><a name="%_idx_3278"></a><em>headed list</em>. A
headed list has a special backbone pair at the beginning, which
holds a dummy ``record'' -- in this case the arbitrarily chosen
symbol <tt>*table*</tt>. Figure <a href="#%_fig_3.22">3.22</a> shows the box-and-pointer diagram for the
table</p>
<p><tt>a: 1<br />
b: 2<br />
c: 3<br /></tt></p>
<p><a name="%_fig_3.22"></a></p>
<div align="left">
<div align="left">
<b>Figure 3.22:</b> A table represented as a
headed list.
</div>
<table width="100%">
<tr>
<td><img src="ch3-Z-G-22.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>To extract information from a table we use the <tt>lookup</tt>
procedure, which takes a key as argument and returns the
associated value (or false if there is no value stored under that
key). <tt>Lookup</tt> is defined in terms of the <tt>assoc</tt>
operation, which expects a key and a list of records as
arguments. Note that <tt>assoc</tt> never sees the dummy record.
<tt>Assoc</tt> returns the record that has the given key as its
<tt>car</tt>.<a href="#footnote_Temp_371" name="call_footnote_Temp_371" id="call_footnote_Temp_371"><sup><small>24</small></sup></a>
<tt>Lookup</tt> then checks to see that the resulting record
returned by <tt>assoc</tt> is not false, and returns the value
(the <tt>cdr</tt>) of the record.</p>
<p><tt><a name="%_idx_3280"></a>(define (lookup key table)<br />
(let ((record (assoc key (cdr table))))<br />
(if record<br />
(cdr record)<br />
false)))<br />
<a name="%_idx_3282"></a>(define (assoc key records)<br />
(cond ((null? records) false)<br />
((equal? key (caar records)) (car records))<br />
(else (assoc key (cdr records)))))<br />
</tt></p>
<p>To insert a value in a table under a specified key, we first
use <tt>assoc</tt> to see if there is already a record in the
table with this key. If not, we form a new record by
<tt>cons</tt>ing the key with the value, and insert this at the
head of the table's list of records, after the dummy record. If
there already is a record with this key, we set the <tt>cdr</tt>
of this record to the designated new value. The header of the
table provides us with a fixed location to modify in order to
insert the new record.<a href="#footnote_Temp_372" name="call_footnote_Temp_372" id="call_footnote_Temp_372"><sup><small>25</small></sup></a></p>
<p><tt><a name="%_idx_3284"></a>(define (insert! key value table)<br />
(let ((record (assoc key (cdr table))))<br />