forked from ldct/isicp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path3-3-modeling.html
2077 lines (1631 loc) · 98.1 KB
/
3-3-modeling.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 XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<meta charset="UTF-8">
<link rel="stylesheet" type="text/css" href="web-worker-interpreter/deps/codemirror/lib/codemirror.css" />
<link rel="stylesheet" type="text/css" href="css/isicp.css" />
<link rel="stylesheet" type="text/css" href="css/footnotes.css" />
<link rel="stylesheet" type="text/css" href="css/theme.css" />
<script src="js/helper.js"></script>
<script src="js/jquery.min.js"></script>
<script src="web-worker-interpreter/deps/codemirror/lib/codemirror.js"></script>
<script src="web-worker-interpreter/deps/codemirror/mode/scheme/scheme.js"></script>
<script src="web-worker-interpreter/coding.js"> </script>
<script>
set_interpreter_path("web-worker-interpreter/");
set_language("scheme");
</script>
<script src="js/footnotes.js"></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$']]}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<title> iSICP 3.3 - Modeling with Mutable Data </title>
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-36868476-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
</head>
<body>
<div id="sidebox">
<div class="tab"></div>
<div class="content">
<p>
<a href="index.html" class="navlink"> <img src='images/home.svg' width=32 height=32> </a>
<span id="toc-link" class="navlink"> <img src='images/list.svg' width=32 height=32> </span>
<span id="currently-editing-link" class="navlink"> <img src='images/file-edit.svg' width=32 height=32> </span>
<script src="http://cdn.jotfor.ms/static/feedback2.js?3.2.310" type="text/javascript">
new JotformFeedback({
formId:'40222623177447',
base:'http://jotform.me/',
windowTitle:'Notify Me',
background:'#FFA500',
fontColor:'#FFFFFF',
type:false,
height:500,
width:700
});
</script>
<a class="lightbox-40222623177447" style="cursor:pointer;color:blue;text-decoration:underline;"><img src='images/envelope.svg' width=32 height=32></a>
<p>
<div id="currently-editing"> </div>
<script>
function hideAll() {
$("#currently-editing").hide();
$("#toc").hide();
}
$("#currently-editing-link").click(function() {
hideAll();
$("#currently-editing").show();
});
$("#toc-link").click(function() {
hideAll();
$("#toc").show();
});
</script>
<div id="toc"> </div>
<p style='font-size:12px'> (Click on the left edge of this green box to hide it!)
<script>
hideAll();
$("#toc").show();
</script>
</div>
</div>
<script>
$('#sidebox .tab').toggle(function(){
$('#sidebox').animate({'right':'0%'});
}, function(){
$('#sidebox').animate({'right':'-30%'});
});
$(document).ready(createTOC);
</script>
<div id="main">
<h2> Modeling with Mutable Data </h2>
<p> 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 <tt>mutators</tt> , 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
<div id="scheme-set-balance">
(set-balance! <account> <new-value>)
</div>
<script>
no_output_frozen_prompt("scheme-set-balance");
</script>
<p> that changes the balance of the designated account to the designated new value. Data objects for which mutators are defined are known as <tt>mutable data objects</tt>.
<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 2-2. We also present some examples of simulations in which complex systems are modeled as collections of objects with local state.
<h3> Mutable List Structure </h3>
<p> 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.
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-13.gif">
<p> <b>Figure 3.12:</b> Lists <tt>x</tt>: <tt>((a b) c d)</tt> and <tt>y</tt>: <tt>(e f)</tt>.
</div>
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-14.gif">
<p> <b>Figure 3.13:</b> Effect of <tt>(set-car! x y)</tt> on the lists in Figure 3-12.
</div>
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-15.gif">
<p> <b>Figure 3.14:</b> Effect of <tt>(define z (cons y (cdr x)))</tt> on the lists in Figure 3-12.
</div>
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-16.gif">
<p> <b>Figure 3.15:</b> Effect of <tt>(set-cdr! x y)</tt> on the lists in Figure 3-12.
</div>
<p> 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 name="footnote_link_3-16" class="footnote_link" href="#footnote_3-16">16</a>
<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 3-12. 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 3-13. 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 name="footnote_link_3-17" class="footnote_link" href="#footnote_3-17">17</a>
<p> Compare Figure 3-13 with Figure 3-14, 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 3-12. 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> 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 3-12 is shown in Figure 3-15. 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> <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 name="footnote_link_3-18" class="footnote_link" href="#footnote_3-18">18</a>
<div id="scheme-define-cons-with-set">
(define (get-new-pair) '(() ()))
(define (cons x y)
(let ((new (get-new-pair)))
(set-car! new x)
(set-cdr! new y)
new))
</div>
<script>
prompt("scheme-define-cons-with-set");
</script>
<p>
<div class="exercise">
<p> <b>Exercise 3.12:</b> The following procedure for appending lists was introduced in section 2-2-1:
<div id="scheme-define-append">
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))
</div>
<script>
prompt("scheme-define-append");
</script>
<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>.)
<div id="scheme-define-append-inplace">
(define (append! x y)
(set-cdr! (last-pair x) y)
x)
</div>
<script>
prompt("scheme-define-append-inplace", ["scheme-define-last-pair"]);
</script>
<p> Here <tt>last-pair</tt> is a procedure that returns the last pair in its argument:
<div id="scheme-define-last-pair">
(define (last-pair x)
(if (null? (cdr x))
x
(last-pair (cdr x))))
</div>
<script>
prompt("scheme-define-last-pair");
</script>
<p> Consider the interaction
<div id="scheme-define-test-append-inplace">
(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))
z
;(a b c d)
(cdr x)
;<response>
(define w (append! x y))
w
;(a b c d)
(cdr x)
;<response>
</div>
<script>
no_output_frozen_prompt("scheme-define-test-append-inplace");
</script>
<p> What are the missing <tt><response></tt>s? Draw box-and-pointer diagrams to explain your answer.
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.13:</b> Consider the following <tt>make-cycle</tt> procedure, which uses the <tt>last-pair</tt> procedure defined in Exercise 3-12:
<div id="scheme-define-make-cycle">
(define (make-cycle x)
(set-cdr! (last-pair x) x)
x)
</div>
<script>
prompt("scheme-define-make-cycle", ["scheme-define-last-pair"]);
</script>
<p> Draw a box-and-pointer diagram that shows the structure <tt>z</tt> created by
<div id="scheme-define-z-cycle">
(define z (make-cycle (list 'a 'b 'c)))
</div>
<script>
prompt("scheme-define-z-cycle", ["scheme-define-make-cycle"]);
</script>
<p> What happens if we try to compute <tt>(last-pair z)</tt>?
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.14:</b> The following procedure is quite useful, although obscure:
<div id="scheme-define-mystery">
(define (mystery x)
(define (loop x y)
(if (null? x)
y
(let ((temp (cdr x)))
(set-cdr! x y)
(loop temp x))))
(loop x '()))
</div>
<script>
prompt("scheme-define-mystery");
</script>
<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>? </div>
<h4> Sharing and identity </h4>
<p> We mentioned in section 3-1-3 the theoretical issues of ``sameness'' and ``change'' raised by the introduction of assignment. These issues arise in practice when individual pairs are <tt>shared</tt> among different data objects. For example, consider the structure formed by
<div id="scheme-define-x">
(define x (list 'a 'b))
</div>
<script>
prompt("scheme-define-x");
</script>
<div id="scheme-define-z1">
(define z1 (cons x x))
</div>
<script>
prompt("scheme-define-z1", ["scheme-define-x"]);
</script>
<p> As shown in Figure 3-16, <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.
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-17.gif">
<p> <b>Figure 3.16:</b> The list <tt>z1</tt> formed by <tt>(cons x x)</tt>.
</div>
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-18.gif">
<p> <b>Figure 3.17:</b> The list <tt>z2</tt> formed by <tt>(cons (list 'a 'b) (list 'a 'b))</tt>.
</div>
<p> In contrast to Figure 3-16, Figure 3-17 shows the structure created by
<div id="scheme-define-z2">
(define z2 (cons (list 'a 'b) (list 'a 'b)))
</div>
<script>
prompt("scheme-define-z2");
</script>
<p> In this structure, the pairs in the two <tt>(a b)</tt> lists are distinct, although the actual symbols are shared.<a name="footnote_link_3-19" class="footnote_link" href="#footnote_3-19">19</a>
<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:
<div id="scheme-define-set-to-wow">
(define (set-to-wow! x)
(set-car! (car x) 'wow)
x)
</div>
<script>
prompt("scheme-define-set-to-wow");
</script>
<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>:
<div id="scheme-z1">
z1
</div>
<script>
prompt("scheme-z1", ["scheme-define-z1"]);
</script>
<p>
<div id="scheme-test-set-to-wow-z1">
(set-to-wow! z1)
</div>
<script>
prompt("scheme-test-set-to-wow-z1", ["scheme-define-z1", "scheme-define-set-to-wow"]);
</script>
<p>
<div id="scheme-z2">
z2
</div>
<script>
prompt("scheme-z2", ["scheme-define-z2"]);
</script>
<p>
<div id="scheme-test-set-to-wow-z2">
(set-to-wow! z2)
</div>
<script>
prompt("scheme-test-set-to-wow-z2", ["scheme-define-z2", "scheme-define-set-to-wow"]);
</script>
<p> One way to detect sharing in list structures is to use the predicate <tt>eq?</tt>, which we introduced in section 2-3-1 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 Figure 3-16 and Figure 3-17, <tt>(eq? (car z1) (cdr z1))</tt> is true and <tt>(eq? (car z2) (cdr z2))</tt> is false.
<p> 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 name="footnote_link_3-20" class="footnote_link" href="#footnote_3-20">20</a>
<div class="exercise">
<p> <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.
</div>
<p>
<div class="exercise">
<p> <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:
<div id="scheme-define-count-pairs">
(define (count-pairs x)
(if (not (pair? x))
0
(+ (count-pairs (car x))
(count-pairs (cdr x))
1)))
</div>
<script>
prompt("scheme-define-count-pairs");
</script>
<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.
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.17:</b> Devise a correct version of the <tt>count-pairs</tt> procedure of Exercise 3-16 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.)
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.18:</b> 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 3-13 constructed such lists.
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.19:</b> Redo Exercise 3-18 using an algorithm that takes only a constant amount of space. (This requires a very clever idea.)
</div>
<h4> Mutation is just assignment </h4>
<p> When we introduced compound data, we observed in section 2-1-3 that pairs can be represented purely in terms of procedures:
<div id="scheme-define-cons">
(define (cons x y)
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
(else (error "Undefined operation -- CONS" m))))
dispatch)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
</div>
<script>
prompt("scheme-define-cons");
</script>
<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 3-1-1:
<div id="scheme-define-cons-set-car-cdr">
(define (cons x y)
(define (set-x! v) (set! x v))
(define (set-y! v) (set! y v))
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else (error "Undefined operation -- CONS" m))))
dispatch)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
(define (set-car! z new-value)
((z 'set-car!) new-value)
z)
(define (set-cdr! z new-value)
((z 'set-cdr!) new-value)
z)
</div>
<script>
prompt("scheme-define-cons-set-car-cdr");
</script>
<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 name="footnote_link_3-21" class="footnote_link" href="#footnote_3-21">21</a>
<div class="exercise">
<p> <b>Exercise 3.20:</b> Draw environment diagrams to illustrate the evaluation of the sequence of expressions
<div id="scheme-test-procedural-set-car-cdr">
(define x (cons 1 2))
(define z (cons x x))
(set-car! (cdr z) 17)
(car x) ;should be 17. apologies.
</div>
<script>
prompt("scheme-test-procedural-set-car-cdr", ["scheme-define-cons-set-car-cdr"]);
</script>
<p> using the procedural implementation of pairs given above. (Compare Exercise 3-11.)
</div>
<h3> Representing Queues </h3>
<p> 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 3-3-3 will show how to represent data structures called tables.
<p> A <tt>queue</tt> is a sequence in which items are inserted at one end (called the <tt>rear</tt> of the queue) and deleted from the other end (the <tt>front</tt> ). Figure 3-18 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 <tt>FIFO</tt> (first in, first out) buffer.
<pre style="margin-left:30%">
Operation Resulting Queue
(define q (make-queue))
(insert-queue! q 'a) a
(insert-queue! q 'b) a b
(delete-queue! q) b
(insert-queue! q 'c) b c
(insert-queue! q 'd) b c d
(delete-queue! q) c d
</pre>
<div class="figure">
<p> <b>Figure 3.18:</b> Queue operations.
</div>
<p> In terms of data abstraction, we can regard a queue as defined by the following set of operations:
<ul>
<li>
<p> a constructor: <tt>(make-queue)</tt> returns an empty queue (a queue containing no items).
</li>
<li>
<p> two selectors:
<p> <tt>(empty-queue? <queue>)</tt> tests if the queue is empty.
<p> <tt>(front-queue <queue>)</tt> returns the object at the front of the queue, signaling an error if the queueis empty; it does not modify the queue.
</li>
<li>
<p> two mutators:
<p> <tt> (insert-queue! <queue> <item>)</tt> inserts the item at the rear of the queue and returns the modified queue as its value.
<p> <tt> (delete-queue! <queue>)</tt> 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 [theta](n) steps for a list of n items. A simple modification to the list representation overcomes this disadvantage by allowing the queue operations to be implemented so that they require [theta](1) steps; that is, so that the number of steps needed is independent of the length of the queue.
<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> 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 3-19 illustrates this representation.
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-19.gif">
<p> <b>Figure 3.19:</b> Implementation of a queue as a list with front and rear pointers.
</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:
<div id="scheme-define-queue-accessors">
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))
</div>
<script>
prompt("scheme-define-queue-accessors");
</script>
<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:
<div id="scheme-define-empty-queue?">
(define (empty-queue? queue) (null? (front-ptr queue)))
</div>
<script>
prompt("scheme-define-empty-queue?", ["scheme-define-queue-accessors"]);
</script>
<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:
<div id="scheme-define-make-queue">
(define (make-queue) (cons '() '()))
</div>
<script>
prompt("scheme-define-make-queue", ["scheme-define-empty-queue?"]);
</script>
<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:
<div id="scheme-define-front-queue">
(define (front-queue queue)
(if (empty-queue? queue)
(error "FRONT called with an empty queue" queue)
(car (front-ptr queue))))
</div>
<script>
prompt("scheme-define-front-queue", ["scheme-define-make-queue"]);
</script>
<p> To insert an item in a queue, we follow the method whose result is indicated in Figure 3-20. 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.
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-20.gif">
<p> <b>Figure 3.20:</b> Result of using <tt>(insert-queue! q 'd)</tt> on the queue of Figure 3-19.
</div>
<div id="scheme-define-insert-queue">
(define (insert-queue! queue item)
(let ((new-pair (cons item '())))
(cond ((empty-queue? queue)
(set-front-ptr! queue new-pair)
(set-rear-ptr! queue new-pair)
queue)
(else
(set-cdr! (rear-ptr queue) new-pair)
(set-rear-ptr! queue new-pair)
queue))))
</div>
<script>
prompt("scheme-define-insert-queue", ["scheme-define-front-queue"]);
</script>
<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 3-21):<a name="footnote_link_3-22" class="footnote_link" href="#footnote_3-22">22</a>
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-21.gif">
<p> <b>Figure 3.21:</b> Result of using <tt>(delete-queue! q)</tt> on the queue of Figure 3-20.
</div>
<p>
<div id="scheme-define-queue">
(define (delete-queue! queue)
(cond ((empty-queue? queue)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! queue (cdr (front-ptr queue)))
queue)))
</div>
<script>
prompt("scheme-define-queue", ["scheme-define-insert-queue"]);
</script>
<p>
<div class="exercise">
<p> <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:
<div id="scheme-test-queue">
(define q1 (make-queue))
(insert-queue! q1 'a)
(insert-queue! q1 'b)
(delete-queue! q1)
(delete-queue! q1)
</div>
<script>
prompt("scheme-test-queue", ["scheme-define-queue"]);
</script>
<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 <tt>print-queue</tt> that takes a queue as input and prints the sequence of items in the queue.
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.22:</b> 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
<div id="scheme-define-make-queue-dispatch">
(define (make-queue)
(let ((front-ptr ... )
(rear-ptr ... ))
;<definitions of internal procedures>
(define (dispatch m) ...)
dispatch))
</div>
<script>
prompt("scheme-define-make-queue-dispatch");
</script>
<p> Complete the definition of <tt>make-queue</tt> and provide implementations of the queue operations using this representation.
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.23:</b> 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 name="footnote_link_3-23" class="footnote_link" href="#footnote_3-23">23</a> All operations should be accomplished in $\Theta(1)$ steps.
</div>
<h3> Representing Tables </h3>
<p> When we studied various ways of representing sets in Chapter 2, we mentioned in section 2-3-3 the task of maintaining a table of records indexed by identifying keys. In the implementation of data-directed programming in section 2-4-3, 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> 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 <tt>backbone</tt> 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 <tt>headed list</tt> . 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 3-22 shows the box-and-pointer diagram for the table
<pre>
a: 1
b: 2
c: 3
</pre>
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-22.gif">
<p> <b>Figure 3.22:</b> A table represented as a headed list.
</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 name="footnote_link_3-24" class="footnote_link" href="#footnote_3-24">24</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.
<div id="scheme-define-lookup">
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))
</div>
<script>
prompt("scheme-define-lookup");
</script>
<div id="scheme-define-assoc">
(define (assoc key records)
(cond ((null? records) false)
((equal? key (car (car records))) (car records)) ;todo: caar
(else (assoc key (cdr records)))))
</div>
<script>
prompt("scheme-define-assoc");
</script>
<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 name="footnote_link_3-25" class="footnote_link" href="#footnote_3-25">25</a>
<div id="scheme-define-insert-table">
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table
(cons (cons key value) (cdr table)))))
'ok)
</div>
<script>
prompt("scheme-define-insert-table", ["scheme-define-lookup", "scheme-define-assoc"]);
</script>
<p> To construct a new table, we simply create a list containing the symbol <tt>*table*</tt>:
<div id="scheme-define-table">
(define (make-table)
(list '*table*))
</div>
<script>
prompt("scheme-define-table", ["scheme-define-insert-table"]);
</script>
<h4> Two-dimensional tables </h4>
<p> In a two-dimensional table, each value is indexed by two keys. We can construct such a table as a one-dimensional table in which each key identifies a subtable. Figure 3-23 shows the box-and-pointer diagram for the table
<pre>
math:
+: 43
-: 45
*: 42
letters:
a: 97
b: 98
</pre>
<p> which has two subtables. (The subtables don't need a special header symbol, since the key that identifies the subtable serves this purpose.)
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-23.gif">
<p> <b>Figure 3.23:</b> A two-dimensional table.
</div>
<p> When we look up an item, we use the first key to identify the correct subtable. Then we use the second key to identify the record within the subtable.
<div id="scheme-define-lookup-2table">
(define (lookup key-1 key-2 table)
(let ((subtable (assoc key-1 (cdr table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(cdr record)
false))
false)))
</div>
<script>
prompt("scheme-define-lookup-2table");
</script>
<p> To insert a new item under a pair of keys, we use <tt>assoc</tt> to see if there is a subtable stored under the first key. If not, we build a new subtable containing the single record (<tt>key-2</tt>, <tt>value</tt>) and insert it into the table under the first key. If a subtable already exists for the first key, we insert the new record into this subtable, using the insertion method for one-dimensional tables described above:
<div id="scheme-define-insert-2table">
(define (insert! key-1 key-2 value table)
(let ((subtable (assoc key-1 (cdr table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(set-cdr! record value)
(set-cdr! subtable
(cons (cons key-2 value)
(cdr subtable)))))
(set-cdr! table
(cons (list key-1
(cons key-2 value))
(cdr table)))))
'ok)
</div>
<script>
prompt("scheme-define-insert-2table", ["scheme-define-assoc", "scheme-define-lookup-2table"]);
</script>
<h4> Creating local tables </h4>
<p> The <tt>lookup</tt> and <tt>insert!</tt> operations defined above take the table as an argument. This enables us to use programs that access more than one table. Another way to deal with multiple tables is to have separate <tt>lookup</tt> and <tt>insert!</tt> procedures for each table. We can do this by representing a table procedurally, as an object that maintains an internal table as part of its local state. When sent an appropriate message, this "table object" supplies the procedure with which to operate on the internal table. Here is a generator for two-dimensional tables represented in this fashion:
<div id="scheme-define-make-2table">
(define (make-table)
(let ((local-table (list '*table*)))
(define (lookup key-1 key-2)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(cdr record)
false))
false)))
(define (insert! key-1 key-2 value)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(set-cdr! record value)
(set-cdr! subtable
(cons (cons key-2 value)
(cdr subtable)))))
(set-cdr! local-table
(cons (list key-1
(cons key-2 value))
(cdr local-table)))))
'ok)
(define (dispatch m)
(cond ((eq? m 'lookup-proc) lookup)
((eq? m 'insert-proc!) insert!)
(else (error "Unknown operation -- TABLE" m))))
dispatch))
</div>
<script>
prompt("scheme-define-make-2table", ["scheme-define-insert-2table"]);
</script>
<p> Using <tt>make-table</tt>, we could implement the <tt>get</tt> and <tt>put</tt> operations used in section 2-4-3 for data-directed programming, as follows:
<div id="scheme-define-get-put">
(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))
</div>
<script>
prompt("scheme-define-get-put", ["scheme-define-make-2table"]);
</script>
<p> <tt>Get</tt> takes as arguments two keys, and <tt>put</tt> takes as arguments two keys and a value. Both operations access the same local table, which is encapsulated within the object created by the call to <tt>make-table</tt>.
<div class="exercise">
<p> <b>Exercise 3.24:</b> In the table implementations above, the keys are tested for equality using <tt>equal?</tt> (called by <tt>assoc</tt>). This is not always the appropriate test. For instance, we might have a table with numeric keys in which we don't need an exact match to the number we're looking up, but only a number within some tolerance of it. Design a table constructor <tt>make-table</tt> that takes as an argument a <tt>same-key?</tt> procedure that will be used to test ``equality'' of keys. <tt>Make-table</tt> should return a <tt>dispatch</tt> procedure that can be used to access appropriate <tt>lookup</tt> and <tt>insert!</tt> procedures for a local table.
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.25:</b> Generalizing one- and two-dimensional tables, show how to implement a table in which values are stored under an arbitrary number of keys and different values may be stored under different numbers of keys. The <tt>lookup</tt> and <tt>insert!</tt> procedures should take as input a list of keys used to access the table.
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.26:</b> To search a table as implemented above, one needs to scan through the list of records. This is basically the unordered list representation of section 2-3-3. For large tables, it may be more efficient to structure the table in a different manner. Describe a table implementation where the (key, value) records are organized using a binary tree, assuming that keys can be ordered in some way (e.g., numerically or alphabetically). (Compare Exercise 2-66 of Chapter 2.)
</div>
<p>
<div class="exercise">
<p> <b>Exercise 3.27:</b> <tt>Memoization</tt> (also called <tt>tabulation</tt> ) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from section 1-2-2 the exponential process for computing Fibonacci numbers:
<div id="scheme-define-fib">
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
</div>
<script>
prompt("scheme-define-fib");
</script>
<p> The memoized version of the same procedure is
<div id="scheme-define-memo-fib">
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
</div>
<script>
prompt("scheme-define-memo-fib", ["scheme-define-memoize"]);
</script>
<p> where the memoizer is defined as
<div id="scheme-define-memoize">
(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))
</div>
<script>
prompt("scheme-define-memoize", ["scheme-define-table"]);
</script>
<p> Draw an environment diagram to analyze the computation of <tt>(memo-fib 3)</tt>. Explain why <tt>memo-fib</tt> computes the nth Fibonacci number in a number of steps proportional to n. Would the scheme still work if we had simply defined <tt>memo-fib</tt> to be <tt>(memoize fib)</tt>? </div>
<h3> A Simulator for Digital Circuits </h3>
<p> Designing complex digital systems, such as computers, is an important engineering activity. Digital systems are constructed by interconnecting simple elements. Although the behavior of these individual elements is simple, networks of them can have very complex behavior. Computer simulation of proposed circuit designs is an important tool used by digital systems engineers. In this section we design a system for performing digital logic simulations. This system typifies a kind of program called an <em>event-driven simulation</em> , in which actions ("events") trigger further events that happen at a later time, which in turn trigger more events, and so so.
<p> Our computational model of a circuit will be composed of objects that correspond to the elementary components from which the circuit is constructed. There are <tt>wires</tt> , which carry <tt>digital signals</tt> . A digital signal may at any moment have only one of two possible values, 0 and 1. There are also various types of digital <tt>function boxes</tt> , which connect wires carrying input signals to other output wires. Such boxes produce output signals computed from their input signals. The output signal is delayed by a time that depends on the type of the function box. For example, an <tt>inverter</tt> is a primitive function box that inverts its input. If the input signal to an inverter changes to 0, then one inverter-delay later the inverter will change its output signal to 1. If the input signal to an inverter changes to 1, then one inverter-delay later the inverter will change its output signal to 0. We draw an inverter symbolically as in Figure 3-24. An <tt>and-gate</tt> , also shown in Figure 3-24, is a primitive function box with two inputs and one output. It drives its output signal to a value that is the <tt>logical and</tt> of the inputs. That is, if both of its input signals become 1, then one and-gate-delay time later the and-gate will force its output signal to be 1; otherwise the output will be 0. An <tt>or-gate</tt> is a similar two-input primitive function box that drives its output signal to a value that is the <tt>logical or</tt> of the inputs. That is, the output will become 1 if at least one of the input signals is 1; otherwise the output will become 0.
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-24.gif">
<p> <b>Figure 3.24:</b> Primitive functions in the digital logic simulator.
</div>
<p> We can connect primitive functions together to construct more complex functions. To accomplish this we wire the outputs of some function boxes to the inputs of other function boxes. For example, the <tt>half-adder</tt>
<p> circuit shown in Figure 3-25 consists of an or-gate, two and-gates, and an inverter. It takes two input signals, A and B, and has two output signals, S and C. S will become 1 whenever precisely one of A and B is 1, and C will become 1 whenever A and B are both 1. We can see from the figure that, because of the delays involved, the outputs may be generated at different times. Many of the difficulties in the design of digital circuits arise from this fact.
<div class="figure">
<img src="http://mitpress.mit.edu/sicp/full-text/book/ch3-Z-G-25.gif">
<p> <b>Figure 3.25:</b> A half-adder circuit.
</div>
<p> We will now build a program for modeling the digital logic circuits we wish to study. The program will construct computational objects modeling the wires, which will ``hold'' the signals. Function boxes will be modeled by procedures that enforce the correct relationships among the signals.
<p> One basic element of our simulation will be a procedure <tt>make-wire</tt>, which constructs wires. For example, we can construct six wires as follows:
<div id="scheme-define-6-wires">
(define a (make-wire))
(define b (make-wire))
(define c (make-wire))
(define d (make-wire))
(define e (make-wire))
(define s (make-wire))
</div>
<script>
prompt("scheme-define-6-wires", ["scheme-define-make-wire"]);
</script>
<p> We attach a function box to a set of wires by calling a procedure that constructs that kind of box. The arguments to the constructor procedure are the wires to be attached to the box. For example, given that we can construct and-gates, or-gates, and inverters, we can wire together the half-adder shown in Figure 3-25:
<div id="scheme-wire-up-wires">
(or-gate a b d)
;ok
(and-gate a b c)
;ok
(inverter c e)
;ok
(and-gate d e s)
;ok
</div>
<script>
prompt("scheme-wire-up-wires");
</script>
<p> Better yet, we can explicitly name this operation by defining a procedure <tt>half-adder</tt> that constructs this circuit, given the four external wires to be attached to the half-adder:
<div id="scheme-define-half-adder">
(define (half-adder a b s c)
(let ((d (make-wire)) (e (make-wire)))
(or-gate a b d)
(and-gate a b c)
(inverter c e)
(and-gate d e s)