forked from twcamper/sicp-kindle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
book-Z-H-20.html
1093 lines (895 loc) · 56.3 KB
/
book-Z-H-20.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.1"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.1">3.1 Assignment and
Local State</a></h2>
<p><a name="%_idx_2836"></a><a name="%_idx_2838"></a> We
ordinarily view the world as populated by independent objects,
each of which has a state that changes over time. An object is
said to ``have state'' if its behavior is influenced by its
history. A bank account, for example, has state in that the
answer to the question ``Can I withdraw $100?'' depends upon the
history of deposit and withdrawal transactions. We can
characterize an object's state by one or more <a name="%_idx_2840"></a><em>state variables</em>, which among them
maintain enough information about history to determine the
object's current behavior. In a simple banking system, we could
characterize the state of an account by a current balance rather
than by remembering the entire history of account
transactions.</p>
<p>In a system composed of many objects, the objects are rarely
completely independent. Each may influence the states of others
through interactions, which serve to couple the state variables
of one object to those of other objects. Indeed, the view that a
system is composed of separate objects is most useful when the
state variables of the system can be grouped into closely coupled
subsystems that are only loosely coupled to other subsystems.</p>
<p>This view of a system can be a powerful framework for
organizing computational models of the system. For such a model
to be modular, it should be decomposed into computational objects
that model the actual objects in the system. Each computational
object must have its own <em>local state variables</em>
describing the actual object's state. Since the states of objects
in the system being modeled change over time, the state variables
of the corresponding computational objects must also change. If
we choose to model the flow of time in the system by the elapsed
time in the computer, then we must have a way to construct
computational objects whose behaviors change as our programs run.
In particular, if we wish to model state variables by ordinary
symbolic names in the programming language, then the language
must provide an <a name="%_idx_2842"></a><em>assignment
operator</em> to enable us to change the value associated with a
name.</p>
<p><a name="%_sec_3.1.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.1">3.1.1 Local State
Variables</a></h3>
<p><a name="%_idx_2844"></a><a name="%_idx_2846"></a> <a name="%_idx_2848"></a><a name="%_idx_2850"></a>To illustrate what we
mean by having a computational object with time-varying state,
let us model the situation of withdrawing money from a bank
account. We will do this using a procedure <tt>withdraw</tt>,
which takes as argument an <tt>amount</tt> to be withdrawn. If
there is enough money in the account to accommodate the
withdrawal, then <tt>withdraw</tt> should return the balance
remaining after the withdrawal. Otherwise, <tt>withdraw</tt>
should return the message <em>Insufficient funds.</em> For
example, if we begin with $100 in the account, we should obtain
the following sequence of responses using <tt>withdraw</tt>:</p>
<p><tt>(withdraw 25)<br />
<i>75</i><br />
(withdraw 25)<br />
<i>50</i><br />
(withdraw 60)<br />
<i>"Insufficient funds"</i><br />
(withdraw 15)<br />
<i>35</i><br /></tt></p>
<p>Observe that the expression <tt>(withdraw 25)</tt>, evaluated
twice, yields different values. This is a new kind of behavior
for a procedure. Until now, all our procedures could be viewed as
specifications for computing mathematical functions. A call to a
procedure computed the value of the function applied to the given
arguments, and two calls to the same procedure with the same
arguments always produced the same result.<a href="#footnote_Temp_321" name="call_footnote_Temp_321" id="call_footnote_Temp_321"><sup><small>1</small></sup></a></p>
<p>To implement <tt>withdraw</tt>, we can use a variable
<tt>balance</tt> to indicate the balance of money in the account
and define <tt>withdraw</tt> as a procedure that accesses
<tt>balance</tt>. The <tt>withdraw</tt> procedure checks to see
if <tt>balance</tt> is at least as large as the requested
<tt>amount</tt>. If so, <tt>withdraw</tt> decrements
<tt>balance</tt> by <tt>amount</tt> and returns the new value of
<tt>balance</tt>. Otherwise, <tt>withdraw</tt> returns the
<em>Insufficient funds</em> message. Here are the definitions of
<tt>balance</tt> and <tt>withdraw</tt>:</p>
<p><tt>(define balance 100)<br />
<br />
<a name="%_idx_2858"></a>(define (withdraw amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))<br />
</tt></p>
<p>Decrementing <tt>balance</tt> is accomplished by the
expression</p>
<p>
<tt>(set! balance (- balance amount))<br /></tt></p>
<p><a name="%_idx_2860"></a><a name="%_idx_2862"></a>This uses
the <tt>set!</tt> special form, whose syntax is</p>
<p>
<tt>(set! <<em>name</em>> <<em>new-value</em>>)<br />
</tt></p>
<p>Here <<em>name</em>> is a symbol and
<<em>new-value</em>> is any expression. <tt>Set!</tt>
changes <<em>name</em>> so that its value is the result
obtained by evaluating <<em>new-value</em>>. In the case at
hand, we are changing <tt>balance</tt> so that its new value will
be the result of subtracting <tt>amount</tt> from the previous
value of <tt>balance</tt>.<a href="#footnote_Temp_322" name="call_footnote_Temp_322" id="call_footnote_Temp_322"><sup><small>2</small></sup></a></p>
<p><a name="%_idx_2874"></a><a name="%_idx_2876"></a><tt>Withdraw</tt> also uses the <tt>begin</tt>
special form to cause two expressions to be evaluated in the case
where the <tt>if</tt> test is true: first decrementing
<tt>balance</tt> and then returning the value of
<tt>balance</tt>. In general, evaluating the expression</p>
<p>
<tt>(begin <<em>exp<sub>1</sub></em>> <<em>exp<sub>2</sub></em>> </tt>...
<<em>exp<sub><em>k</em></sub></em>>)<br /></p>
<p>causes the expressions <<em>exp<sub>1</sub></em>>
through <<em>exp<sub><em>k</em></sub></em>> to be evaluated
in sequence and the value of the final expression
<<em>exp<sub><em>k</em></sub></em>> to be returned as the
value of the entire <tt>begin</tt> form.<a href="#footnote_Temp_323" name="call_footnote_Temp_323" id="call_footnote_Temp_323"><sup><small>3</small></sup></a></p>
<p>Although <tt>withdraw</tt> works as desired, the variable
<tt>balance</tt> presents a problem. As specified above,
<tt>balance</tt> is a name defined in the global environment and
is freely accessible to be examined or modified by any procedure.
It would be much better if we could somehow make <tt>balance</tt>
internal to <tt>withdraw</tt>, so that <tt>withdraw</tt> would be
the only procedure that could access <tt>balance</tt> directly
and any other procedure could access <tt>balance</tt> only
indirectly (through calls to <tt>withdraw</tt>). This would more
accurately model the notion that <tt>balance</tt> is a local
state variable used by <tt>withdraw</tt> to keep track of the
state of the account.</p>
<p>We can make <tt>balance</tt> internal to <tt>withdraw</tt> by
rewriting the definition as follows:</p>
<p><tt><a name="%_idx_2884"></a>(define new-withdraw<br />
(let ((balance 100))<br />
(lambda (amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))))<br />
</tt></p>
<p>What we have done here is use <tt>let</tt> to establish an
environment with a local variable <tt>balance</tt>, bound to the
initial value 100. Within this local environment, we use
<tt>lambda</tt> to create a procedure that takes <tt>amount</tt>
as an argument and behaves like our previous <tt>withdraw</tt>
procedure. This procedure -- returned as the result of evaluating
the <tt>let</tt> expression -- is <tt>new-withdraw</tt>, which
behaves in precisely the same way as <tt>withdraw</tt> but whose
variable <tt>balance</tt> is not accessible by any other
procedure.<a href="#footnote_Temp_324" name="call_footnote_Temp_324" id="call_footnote_Temp_324"><sup><small>4</small></sup></a></p>
<p>Combining <tt>set!</tt> with local variables is the general
programming technique we will use for constructing computational
objects with local state. Unfortunately, using this technique
raises a serious problem: When we first introduced procedures, we
also introduced the substitution model of evaluation
(section <a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>)
to provide an interpretation of what procedure application means.
We said that applying a procedure should be interpreted as
evaluating the body of the procedure with the formal parameters
replaced by their values. The trouble is that, as soon as we
introduce assignment into our language, substitution is no longer
an adequate model of procedure application. (We will see why this
is so in section <a href="#%_sec_3.1.3">3.1.3</a>.) As a
consequence, we technically have at this point no way to
understand why the <tt>new-withdraw</tt> procedure behaves as
claimed above. In order to really understand a procedure such as
<tt>new-withdraw</tt>, we will need to develop a new model of
procedure application. In section <a href="book-Z-H-21.html#%_sec_3.2">3.2</a> we will introduce such a
model, together with an explanation of <tt>set!</tt> and local
variables. First, however, we examine some variations on the
theme established by <tt>new-withdraw</tt>.</p>
<p>The following procedure, <tt>make-withdraw</tt>, creates
``withdrawal processors.'' The formal parameter <tt>balance</tt>
in <tt>make-withdraw</tt> specifies the initial amount of money
in the account.<a href="#footnote_Temp_325" name="call_footnote_Temp_325" id="call_footnote_Temp_325"><sup><small>5</small></sup></a></p>
<p><tt><a name="%_idx_2894"></a>(define (make-withdraw balance)<br />
(lambda (amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds")))<br />
</tt></p>
<p><tt>Make-withdraw</tt> can be used as follows to create two
objects <tt>W1</tt> and <tt>W2</tt>:</p>
<p><tt>(define W1 (make-withdraw 100))<br />
(define W2 (make-withdraw 100))<br />
(W1 50)<br />
<i>50</i><br />
(W2 70)<br />
<i>30</i><br />
(W2 40)<br />
<i>"Insufficient funds"</i><br />
(W1 40)<br />
<i>10</i><br /></tt></p>
<p>Observe that <tt>W1</tt> and <tt>W2</tt> are completely
independent objects, each with its own local state variable
<tt>balance</tt>. Withdrawals from one do not affect the
other.</p>
<p>We can also create objects that handle deposits as well as
withdrawals, and thus we can represent simple bank accounts. Here
is a procedure that returns a ``bank-account object'' with a
specified initial balance:</p>
<p><tt><a name="%_idx_2896"></a><a name="%_idx_2898"></a>(define (make-account balance)<br />
(define (withdraw amount)<br />
(if (>= balance amount)<br />
(begin (set! balance (- balance amount))<br />
balance)<br />
"Insufficient funds"))<br />
(define (deposit amount)<br />
(set! balance (+ balance amount))<br />
balance)<br />
(define (dispatch m)<br />
(cond ((eq? m 'withdraw) withdraw)<br />
((eq? m 'deposit) deposit)<br />
(else (error "Unknown request -- MAKE-ACCOUNT"<br />
m))))<br />
dispatch)<br /></tt></p>
<p>Each call to <tt>make-account</tt> sets up an environment with
a local state variable <tt>balance</tt>. Within this environment,
<tt>make-account</tt> defines procedures <tt>deposit</tt> and
<tt>withdraw</tt> that access <tt>balance</tt> and an additional
procedure <tt>dispatch</tt> that takes a ``message'' as input and
returns one of the two local procedures. The <tt>dispatch</tt>
procedure itself is returned as the value that represents the
bank-account object. This is precisely the <a name="%_idx_2900"></a><em>message-passing</em> style of programming
that we saw in section <a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>, although here we are
using it in conjunction with the ability to modify local
variables.</p>
<p><tt>Make-account</tt> can be used as follows:</p>
<p><tt>(define acc (make-account 100))<br />
((acc 'withdraw) 50)<br />
<i>50</i><br />
((acc 'withdraw) 60)<br />
<i>"Insufficient funds"</i><br />
((acc 'deposit) 40)<br />
<i>90</i><br />
((acc 'withdraw) 60)<br />
<i>30</i><br /></tt></p>
<p>Each call to <tt>acc</tt> returns the locally defined
<tt>deposit</tt> or <tt>withdraw</tt> procedure, which is then
applied to the specified <tt>amount</tt>. As was the case with
<tt>make-withdraw</tt>, another call to <tt>make-account</tt></p>
<p>
<tt>(define acc2 (make-account 100))<br /></tt></p>
<p>will produce a completely separate account object, which
maintains its own local <tt>balance</tt>.</p>
<p><a name="%_thm_3.1"></a> <b>Exercise 3.1.</b> An
<a name="%_idx_2902"></a><em>accumulator</em> is a procedure that
is called repeatedly with a single numeric argument and
accumulates its arguments into a sum. Each time it is called, it
returns the currently accumulated sum. Write a procedure <a name="%_idx_2904"></a><tt>make-accumulator</tt> that generates
accumulators, each maintaining an independent sum. The input to
<tt>make-accumulator</tt> should specify the initial value of the
sum; for example</p>
<p><tt>(define A (make-accumulator 5))<br />
(A 10)<br />
<i>15</i><br />
(A 10)<br />
<i>25</i><br /></tt></p>
<p><a name="%_thm_3.2"></a> <b>Exercise 3.2.</b> In
software-testing applications, it is useful to be able to count
the number of times a given procedure is called during the course
of a computation. Write a procedure <a name="%_idx_2906"></a><a name="%_idx_2908"></a><a name="%_idx_2910"></a><tt>make-monitored</tt> that takes as input a
procedure, <tt>f</tt>, that itself takes one input. The result
returned by <tt>make-monitored</tt> is a third procedure, say
<tt>mf</tt>, that keeps track of the number of times it has been
called by maintaining an internal counter. If the input to
<tt>mf</tt> is the special symbol <tt>how-many-calls?</tt>, then
<tt>mf</tt> returns the value of the counter. If the input is the
special symbol <tt>reset-count</tt>, then <tt>mf</tt> resets the
counter to zero. For any other input, <tt>mf</tt> returns the
result of calling <tt>f</tt> on that input and increments the
counter. For instance, we could make a monitored version of the
<tt>sqrt</tt> procedure:</p>
<p><tt>(define s (make-monitored sqrt))<br />
<br />
(s 100)<br />
<i>10</i><br />
<br />
(s 'how-many-calls?)<br />
<i>1</i><br /></tt></p>
<p><a name="%_thm_3.3"></a> <b>Exercise
3.3.</b> <a name="%_idx_2912"></a><a name="%_idx_2914"></a>Modify the <tt>make-account</tt> procedure so
that it creates password-protected accounts. That is,
<tt>make-account</tt> should take a symbol as an additional
argument, as in</p>
<p>
<tt>(define acc (make-account 100 'secret-password))<br />
</tt></p>
<p>The resulting account object should process a request only if
it is accompanied by the password with which the account was
created, and should otherwise return a complaint:</p>
<p><tt>((acc 'secret-password 'withdraw) 40)<br />
<i>60</i><br />
<br />
((acc 'some-other-password 'deposit) 50)<br />
<i>"Incorrect password"</i><br /></tt></p>
<p><a name="%_thm_3.4"></a> <b>Exercise
3.4.</b> Modify the <tt>make-account</tt> procedure of
exercise <a href="#%_thm_3.3">3.3</a> by adding another
local state variable so that, if an account is accessed more than
seven consecutive times with an incorrect password, it invokes
the procedure <tt>call-the-cops</tt>.</p>
<p><a name="%_sec_3.1.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.2">3.1.2 The Benefits
of Introducing Assignment</a></h3>
<p><a name="%_idx_2916"></a> <a name="%_idx_2918"></a><a name="%_idx_2920"></a>As we shall see, introducing assignment into our
programming language leads us into a thicket of difficult
conceptual issues. Nevertheless, viewing systems as collections
of objects with local state is a powerful technique for
maintaining a modular design. As a simple example, consider the
design of a procedure <tt>rand</tt> that, whenever it is called,
returns an integer chosen at random.</p>
<p><a name="%_idx_2922"></a>It is not at all clear what is meant
by ``chosen at random.'' What we presumably want is for
successive calls to <tt>rand</tt> to produce a sequence of
numbers that has statistical properties of uniform distribution.
We will not discuss methods for generating suitable sequences
here. Rather, let us assume that we have a procedure
<tt>rand-update</tt> that has the property that if we start with
a given number <em>x</em><sub>1</sub> and form</p>
<p>
<tt><em>x</em><sub>2</sub> = (rand-update <em>x</em><sub>1</sub>)<br />
<em>x</em><sub>3</sub> = (rand-update <em>x</em><sub>2</sub>)<br />
</tt></p>
<p>then the sequence of values <em>x</em><sub>1</sub>,
<em>x</em><sub>2</sub>, <em>x</em><sub>3</sub>, <tt>...</tt>,
will have the desired statistical properties.<a href="#footnote_Temp_330" name="call_footnote_Temp_330" id="call_footnote_Temp_330"><sup><small>6</small></sup></a></p>
<p>We can implement <tt>rand</tt> as a procedure with a local
state variable <tt>x</tt> that is initialized to some fixed value
<tt>random-init</tt>. Each call to <tt>rand</tt> computes
<tt>rand-update</tt> of the current value of <tt>x</tt>, returns
this as the random number, and also stores this as the new value
of <tt>x</tt>.</p>
<p><tt><a name="%_idx_2934"></a>(define rand<br />
(let ((x random-init))<br />
(lambda ()<br />
(set! x (rand-update x))<br />
x)))<br /></tt></p>
<p>Of course, we could generate the same sequence of random
numbers without using assignment by simply calling
<tt>rand-update</tt> directly. However, this would mean that any
part of our program that used random numbers would have to
explicitly remember the current value of <tt>x</tt> to be passed
as an argument to <tt>rand-update</tt>. To realize what an
annoyance this would be, consider using random numbers to
implement a technique called <a name="%_idx_2936"></a><a name="%_idx_2938"></a><em>Monte Carlo simulation</em>.</p>
<p>The Monte Carlo method consists of choosing sample experiments
at random from a large set and then making deductions on the
basis of the probabilities estimated from tabulating the results
of those experiments. For example, we can approximate <a name="%_idx_2940"></a><img src="book-Z-G-D-9.gif" border="0" /> using
the fact that 6/<img src="book-Z-G-D-9.gif" border="0" /><sup>2</sup> is the probability that two integers chosen at
random will have no factors in common; that is, that their
greatest common divisor will be 1.<a href="#footnote_Temp_331" name="call_footnote_Temp_331" id="call_footnote_Temp_331"><sup><small>7</small></sup></a> To
obtain the approximation to <img src="book-Z-G-D-9.gif" border="0" />, we perform a large number of experiments. In each
experiment we choose two integers at random and perform a test
<a name="%_idx_2946"></a>to see if their GCD is 1. The fraction
of times that the test is passed gives us our estimate of
6/<img src="book-Z-G-D-9.gif" border="0" /><sup>2</sup>, and from
this we obtain our approximation to <img src="book-Z-G-D-9.gif" border="0" />.</p>
<p>The heart of our program is a procedure <tt>monte-carlo</tt>,
which takes as arguments the number of times to try an
experiment, together with the experiment, represented as a
no-argument procedure that will return either true or false each
time it is run. <tt>Monte-carlo</tt> runs the experiment for the
designated number of trials and returns a number telling the
fraction of the trials in which the experiment was found to be
true.</p>
<p><tt><a name="%_idx_2948"></a>(define (estimate-pi trials)<br />
(sqrt (/ 6 (monte-carlo trials cesaro-test))))<br />
<a name="%_idx_2950"></a>(define (cesaro-test)<br />
(= (gcd (rand) (rand)) 1))<br />
<a name="%_idx_2952"></a>(define (monte-carlo trials experiment)<br />
(define (iter trials-remaining trials-passed)<br />
(cond ((= trials-remaining 0)<br />
(/ trials-passed trials))<br />
((experiment)<br />
(iter (- trials-remaining 1) (+ trials-passed 1)))<br />
(else<br />
(iter (- trials-remaining 1) trials-passed))))<br />
(iter trials 0))<br /></tt></p>
<p>Now let us try the same computation using <tt>rand-update</tt>
directly rather than <tt>rand</tt>, the way we would be forced to
proceed if we did not use assignment to model local state:</p>
<p><tt><a name="%_idx_2954"></a>(define (estimate-pi trials)<br />
(sqrt (/ 6 (random-gcd-test trials random-init))))<br />
(define (random-gcd-test trials initial-x)<br />
(define (iter trials-remaining trials-passed x)<br />
(let ((x1 (rand-update x)))<br />
(let ((x2 (rand-update x1)))<br />
(cond ((= trials-remaining 0) <br />
(/ trials-passed trials))<br />
((= (gcd x1 x2) 1)<br />
(iter (- trials-remaining 1)<br />
(+ trials-passed 1)<br />
x2))<br />
(else<br />
(iter (- trials-remaining 1)<br />
trials-passed<br />
x2))))))<br />
(iter trials 0 initial-x))<br /></tt></p>
<p>While the program is still simple, it betrays some painful
breaches of modularity. In our first version of the program,
using <tt>rand</tt>, we can express the Monte Carlo method
directly as a general <tt>monte-carlo</tt> procedure that takes
as an argument an arbitrary <tt>experiment</tt> procedure. In our
second version of the program, with no local state for the
random-number generator, <tt>random-gcd-test</tt> must explicitly
manipulate the random numbers <tt>x1</tt> and <tt>x2</tt> and
recycle <tt>x2</tt> through the iterative loop as the new input
to <tt>rand-update</tt>. This explicit handling of the random
numbers intertwines the structure of accumulating test results
with the fact that our particular experiment uses two random
numbers, whereas other Monte Carlo experiments might use one
random number or three. Even the top-level procedure
<tt>estimate-pi</tt> has to be concerned with supplying an
initial random number. The fact that the random-number
generator's insides are leaking out into other parts of the
program makes it difficult for us to isolate the Monte Carlo idea
so that it can be applied to other tasks. In the first version of
the program, assignment encapsulates the state of the
random-number generator within the <tt>rand</tt> procedure, so
that the details of random-number generation remain independent
of the rest of the program.</p>
<p>The general phenomenon illustrated by the Monte Carlo example
is this: From the point of view of one part of a complex process,
the other parts appear to change with time. They have hidden
time-varying local state. If we wish to write computer programs
whose structure reflects this decomposition, we make
computational objects (such as bank accounts and random-number
generators) whose behavior changes with time. We model state with
local state variables, and we model the changes of state with
assignments to those variables.</p>
<p>It is tempting to conclude this discussion by saying that, by
introducing assignment and the technique of hiding state in local
variables, we are able to structure systems in a more modular
fashion than if all state had to be manipulated explicitly, by
passing additional parameters. Unfortunately, as we shall see,
the story is not so simple.</p>
<p><a name="%_thm_3.5"></a> <b>Exercise
3.5.</b> <a name="%_idx_2956"></a><a name="%_idx_2958"></a><a name="%_idx_2960"></a><em>Monte Carlo
integration</em> is a method of estimating definite integrals by
means of Monte Carlo simulation. Consider computing the area of a
region of space described by a predicate <em>P</em>(<em>x</em>,
<em>y</em>) that is true for points (<em>x</em>, <em>y</em>) in
the region and false for points not in the region. For example,
the region contained within a circle of radius 3 centered at (5,
7) is described by the predicate that tests whether (<em>x</em> -
5)<sup>2</sup> + (<em>y</em> - 7)<sup>2</sup><u><</u>
3<sup>2</sup>. To estimate the area of the region described by
such a predicate, begin by choosing a rectangle that contains the
region. For example, a rectangle with diagonally opposite corners
at (2, 4) and (8, 10) contains the circle above. The desired
integral is the area of that portion of the rectangle that lies
in the region. We can estimate the integral by picking, at
random, points (<em>x</em>,<em>y</em>) that lie in the rectangle,
and testing <em>P</em>(<em>x</em>, <em>y</em>) for each point to
determine whether the point lies in the region. If we try this
with many points, then the fraction of points that fall in the
region should give an estimate of the proportion of the rectangle
that lies in the region. Hence, multiplying this fraction by the
area of the entire rectangle should produce an estimate of the
integral.</p>
<p>Implement Monte Carlo integration as a procedure <a name="%_idx_2962"></a><tt>estimate-integral</tt> that takes as
arguments a predicate <tt>P</tt>, upper and lower bounds
<tt>x1</tt>, <tt>x2</tt>, <tt>y1</tt>, and <tt>y2</tt> for the
rectangle, and the number of trials to perform in order to
produce the estimate. Your procedure should use the same
<tt>monte-carlo</tt> procedure that was used above to estimate
<img src="book-Z-G-D-9.gif" border="0" />. Use your
<tt>estimate-integral</tt> to produce an estimate of <img src="book-Z-G-D-9.gif" border="0" /> by measuring the area of a unit
circle.</p>
<p>You will find it useful to have a procedure that returns a
number chosen at random from a given range. The following
<tt>random-in-range</tt> procedure implements this in terms of
the <tt>random</tt> procedure used in section <a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>, which returns a
nonnegative number less than its input.<a href="#footnote_Temp_333" name="call_footnote_Temp_333" id="call_footnote_Temp_333"><sup><small>8</small></sup></a></p>
<p><tt><a name="%_idx_2970"></a>(define (random-in-range low high)<br />
(let ((range (- high low)))<br />
(+ low (random range))))<br />
</tt></p>
<p><a name="%_thm_3.6"></a> <b>Exercise
3.6.</b> <a name="%_idx_2972"></a><a name="%_idx_2974"></a>It is useful to be able to reset a random-number
generator to produce a sequence starting from a given value.
Design a new <tt>rand</tt> procedure that is called with an
argument that is either the symbol <tt>generate</tt> or the
symbol <tt>reset</tt> and behaves as follows: <tt>(rand
'generate)</tt> produces a new random number; <tt>((rand 'reset)
<<em>new-value</em>>)</tt> resets the internal state
variable to the designated <<em>new-value</em>>. Thus, by
resetting the state, one can generate repeatable sequences. These
are very handy to have when testing and debugging programs that
use random numbers.</p>
<p><a name="%_sec_3.1.3"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.3">3.1.3 The Costs of
Introducing Assignment</a></h3>
<p><a name="%_idx_2976"></a> As we have seen, the <tt>set!</tt>
operation enables us to model objects that have local state.
However, this advantage comes at a price. Our programming
language can no longer be interpreted in terms of the
substitution model of procedure application that we introduced in
section <a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>.
Moreover, no simple model with ``nice'' mathematical properties
can be an adequate framework for dealing with objects and
assignment in programming languages.</p>
<p>So long as we do not use assignments, two evaluations of the
same procedure with the same arguments will produce the same
result, so that procedures can be viewed as computing
mathematical functions. Programming without any use of
assignments, as we did throughout the first two chapters of this
book, is accordingly known as <a name="%_idx_2978"></a><em>functional programming</em>.</p>
<p><a name="%_idx_2980"></a>To understand how assignment
complicates matters, consider a simplified version of the
<tt>make-withdraw</tt> procedure of section <a href="#%_sec_3.1.1">3.1.1</a> that does not bother to check for an
insufficient amount:</p>
<p><tt><a name="%_idx_2982"></a>(define (make-simplified-withdraw balance)<br />
(lambda (amount)<br />
(set! balance (- balance amount))<br />
balance))<br />
(define W (make-simplified-withdraw 25))<br />
(W 20)<br />
<i>5</i><br />
(W 10)<br />
<i>- 5</i><br /></tt></p>
<p>Compare this procedure with the following
<tt>make-decrementer</tt> procedure, which does not use
<tt>set!</tt>:</p>
<p><tt><a name="%_idx_2984"></a>(define (make-decrementer balance)<br />
(lambda (amount)<br />
(- balance amount)))<br /></tt></p>
<p><tt>Make-decrementer</tt> returns a procedure that subtracts
its input from a designated amount <tt>balance</tt>, but there is
no accumulated effect over successive calls, as with
<tt>make-simplified-withdraw</tt>:</p>
<p><tt>(define D (make-decrementer 25))<br />
(D 20)<br />
<i>5</i><br />
(D 10)<br />
<i>15</i><br /></tt></p>
<p>We can use the substitution model to explain how
<tt>make-decrementer</tt> works. For instance, let us analyze the
evaluation of the expression</p>
<p><tt>((make-decrementer 25) 20)<br /></tt></p>
<p>We first simplify the operator of the combination by
substituting 25 for <tt>balance</tt> in the body of
<tt>make-decrementer</tt>. This reduces the expression to</p>
<p>
<tt>((lambda (amount) (- 25 amount)) 20)<br />
</tt></p>
<p>Now we apply the operator by substituting 20 for
<tt>amount</tt> in the body of the <tt>lambda</tt>
expression:</p>
<p><tt>(- 25 20)<br /></tt></p>
<p>The final answer is 5.</p>
<p>Observe, however, what happens if we attempt a similar
substitution analysis with <tt>make-simplified-withdraw</tt>:</p>
<p><tt>((make-simplified-withdraw 25) 20)<br /></tt></p>
<p>We first simplify the operator by substituting 25 for
<tt>balance</tt> in the body of
<tt>make-simplified-withdraw</tt>. This reduces the expression
to<a href="#footnote_Temp_335" name="call_footnote_Temp_335" id="call_footnote_Temp_335"><sup><small>9</small></sup></a></p>
<p>
<tt>((lambda (amount) (set! balance (- 25 amount)) 25) 20)<br />
</tt></p>
<p>Now we apply the operator by substituting 20 for
<tt>amount</tt> in the body of the <tt>lambda</tt>
expression:</p>
<p>
<tt>(set! balance (- 25 20)) 25<br /></tt></p>
<p>If we adhered to the substitution model, we would have to say
that the meaning of the procedure application is to first set
<tt>balance</tt> to 5 and then return 25 as the value of the
expression. This gets the wrong answer. In order to get the
correct answer, we would have to somehow distinguish the first
occurrence of <tt>balance</tt> (before the effect of the
<tt>set!</tt>) from the second occurrence of <tt>balance</tt>
(after the effect of the <tt>set!</tt>), and the substitution
model cannot do this.</p>
<p>The trouble here is that substitution is based ultimately on
the notion that the symbols in our language are essentially names
for values. But as soon as we introduce <tt>set!</tt> and the
idea that the value of a variable can change, a variable can no
longer be simply a name. Now a variable somehow refers to a place
where a value can be stored, and the value stored at this place
can change. In section <a href="book-Z-H-21.html#%_sec_3.2">3.2</a> we will see how environments
play this role of ``place'' in our computational model.</p>
<p><a name="%_sec_Temp_336"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_336">Sameness and
change</a></h4>
<p><a name="%_idx_2986"></a><a name="%_idx_2988"></a> The issue
surfacing here is more profound than the mere breakdown of a
particular model of computation. As soon as we introduce change
into our computational models, many notions that were previously
straightforward become problematical. Consider the concept of two
things being ``the same.''</p>
<p>Suppose we call <tt>make-decrementer</tt> twice with the same
argument to create two procedures:</p>
<p><tt>(define D1 (make-decrementer 25))<br />
(define D2 (make-decrementer 25))<br /></tt></p>
<p>Are <tt>D1</tt> and <tt>D2</tt> the same? An acceptable answer
is yes, because <tt>D1</tt> and <tt>D2</tt> have the same
computational behavior -- each is a procedure that subtracts its
input from 25. In fact, <tt>D1</tt> could be substituted for
<tt>D2</tt> in any computation without changing the result.</p>
<p>Contrast this with making two calls to
<tt>make-simplified-withdraw</tt>:</p>
<p>
<tt>(define W1 (make-simplified-withdraw 25))<br />
(define W2 (make-simplified-withdraw 25))<br /></tt></p>
<p>Are <tt>W1</tt> and <tt>W2</tt> the same? Surely not, because
calls to <tt>W1</tt> and <tt>W2</tt> have distinct effects, as
shown by the following sequence of interactions:</p>
<p><tt>(W1 20)<br />
<i>5</i><br />
(W1 20)<br />
<i>- 15</i><br />
(W2 20)<br />
<i>5</i><br /></tt></p>
<p>Even though <tt>W1</tt> and <tt>W2</tt> are ``equal'' in the
sense that they are both created by evaluating the same
expression, <tt>(make-simplified-withdraw 25)</tt>, it is
not true that <tt>W1</tt> could be substituted for <tt>W2</tt> in
any expression without changing the result of evaluating the
expression.</p>
<p>A language that supports the concept that ``equals can be
substituted for equals'' in an expresssion without changing the
value of the expression is said to be <a name="%_idx_2990"></a><a name="%_idx_2992"></a><a name="%_idx_2994"></a><em>referentially transparent</em>. Referential
transparency is violated when we include <tt>set!</tt> in our
computer language. This makes it tricky to determine when we can
simplify expressions by substituting equivalent expressions.
Consequently, reasoning about programs that use assignment
becomes drastically more difficult.</p>
<p>Once we forgo referential transparency, the notion of what it
means for computational objects to be ``the same'' becomes
difficult to capture in a formal way. Indeed, the meaning of
``same'' in the real world that our programs model is hardly
clear in itself. In general, we can determine that two apparently
identical objects are indeed ``the same one'' only by modifying
one object and then observing whether the other object has
changed in the same way. But how can we tell if an object has
``changed'' other than by observing the ``same'' object twice and
seeing whether some property of the object differs from one
observation to the next? Thus, we cannot determine ``change''
without some <em>a priori</em> notion of ``sameness,'' and we
cannot determine sameness without observing the effects of
change.</p>
<p><a name="%_idx_2996"></a>As an example of how this issue
arises in programming, consider the situation where Peter and
Paul have a bank account with $100 in it. There is a substantial
difference between modeling this as</p>
<p><tt>(define peter-acc (make-account 100))<br />
(define paul-acc (make-account 100))<br /></tt></p>
<p>and modeling it as</p>
<p><tt>(define peter-acc (make-account 100))<br />
(define paul-acc peter-acc)<br /></tt></p>
<p>In the first situation, the two bank accounts are distinct.
Transactions made by Peter will not affect Paul's account, and
vice versa. In the second situation, however, we have defined
<tt>paul-acc</tt> to be <em>the same thing</em> as
<tt>peter-acc</tt>. In effect, Peter and Paul now have a joint
bank account, and if Peter makes a withdrawal from
<tt>peter-acc</tt> Paul will observe less money in
<tt>paul-acc</tt>. These two similar but distinct situations can
cause confusion in building computational models. With the shared
account, in particular, it can be especially confusing that there
is one object (the bank account) that has two different names
(<tt>peter-acc</tt> and <tt>paul-acc</tt>); if we are searching
for all the places in our program where <tt>paul-acc</tt> can be
changed, we must remember to look also at things that change
<tt>peter-acc</tt>.<a href="#footnote_Temp_337" name="call_footnote_Temp_337" id="call_footnote_Temp_337"><sup><small>10</small></sup></a></p>
<p>With reference to the above remarks on ``sameness'' and
``change,'' observe that if Peter and Paul could only examine
their bank balances, and could not perform operations that
changed the balance, then the issue of whether the two accounts
are distinct would be moot. In general, so long as we never
modify data objects, we can regard a compound data object to be
precisely the totality of its pieces. For example, a rational
number is determined by giving its numerator and its denominator.
But this view is no longer valid in the presence of change, where
a compound data object has an ``identity'' that is something
different from the pieces of which it is composed. A bank account
is still ``the same'' bank account even if we change the balance
by making a withdrawal; conversely, we could have two different
bank accounts with the same state information. This complication
is a consequence, not of our programming language, but of our
perception of a bank account as an object. We do not, for
example, ordinarily regard a rational number as a changeable
object with identity, such that we could change the numerator and
still have ``the same'' rational number. <a name="%_sec_Temp_338"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_338">Pitfalls of
imperative programming</a></h4>
<p>In contrast to functional programming, programming that makes
extensive use of assignment is known as <a name="%_idx_3014"></a><a name="%_idx_3016"></a><em>imperative
programming</em>. In addition to raising complications about
computational models, programs written in imperative style are
susceptible to bugs that cannot occur in functional programs. For
example, recall the iterative factorial program from
section <a href="book-Z-H-11.html#%_sec_1.2.1">1.2.1</a>:</p>
<p><tt>(define (factorial n)<br />
(define (iter product counter)<br />
(if (> counter n)<br />
product<br />
(iter (* counter product)<br />
(+ counter 1))))<br />
(iter 1 1))<br /></tt></p>
<p>Instead of passing arguments in the internal iterative loop,
we could adopt a more imperative style by using explicit
assignment to update the values of the variables <tt>product</tt>
and <tt>counter</tt>:</p>
<p><tt><a name="%_idx_3018"></a>(define (factorial n)<br />
(let ((product 1)<br />
(counter 1))<br />
(define (iter)<br />
(if (> counter n)<br />
product<br />
(begin (set! product (* counter product))<br />
(set! counter (+ counter 1))<br />
(iter))))<br />
(iter)))<br /></tt></p>
<p><a name="%_idx_3020"></a><a name="%_idx_3022"></a>This does
not change the results produced by the program, but it does
introduce a subtle trap. How do we decide the order of the
assignments? As it happens, the program is correct as written.
But writing the assignments in the opposite order</p>
<p><tt>(set! counter (+ counter 1))<br />
(set! product (* counter product))<br /></tt></p>
<p>would have produced a different, incorrect result. In general,
programming with assignment forces us to carefully consider the
relative orders of the assignments to make sure that each
statement is using the correct version of the variables that have
been changed. This issue simply does not arise in functional
programs.<a href="#footnote_Temp_339" name="call_footnote_Temp_339" id="call_footnote_Temp_339"><sup><small>11</small></sup></a> The
complexity of imperative programs becomes even worse if we
consider applications in which several processes execute
concurrently. We will return to this in section <a href="book-Z-H-23.html#%_sec_3.4">3.4</a>. First, however, we will
address the issue of providing a computational model for
expressions that involve assignment, and explore the uses of
objects with local state in designing simulations.</p>
<p><a name="%_thm_3.7"></a> <b>Exercise
3.7.</b> <a name="%_idx_3026"></a>Consider the bank
account objects created by <tt>make-account</tt>, with the
password modification described in exercise <a href="#%_thm_3.3">3.3</a>. Suppose that our banking system requires
the ability to make joint accounts. Define a procedure <a name="%_idx_3028"></a><tt>make-joint</tt> that accomplishes this.
<tt>Make-joint</tt> should take three arguments. The first is a
password-protected account. The second argument must match the
password with which the account was defined in order for the
<tt>make-joint</tt> operation to proceed. The third argument is a
new password. <tt>Make-joint</tt> is to create an additional
access to the original account using the new password. For
example, if <tt>peter-acc</tt> is a bank account with password
<tt>open-sesame</tt>, then</p>
<p><tt>(define paul-acc<br />
(make-joint peter-acc 'open-sesame 'rosebud))<br />
</tt></p>
<p>will allow one to make transactions on <tt>peter-acc</tt>
using the name <tt>paul-acc</tt> and the password
<tt>rosebud</tt>. You may wish to modify your solution to
exercise <a href="#%_thm_3.3">3.3</a> to accommodate this
new feature.</p>
<p><a name="%_thm_3.8"></a> <b>Exercise
3.8.</b> <a name="%_idx_3030"></a><a name="%_idx_3032"></a>When we defined the evaluation model in
section <a href="book-Z-H-10.html#%_sec_1.1.3">1.1.3</a>, we
said that the first step in evaluating an expression is to
evaluate its subexpressions. But we never specified the order in
which the subexpressions should be evaluated (e.g., left to right
or right to left). When we introduce assignment, the order in
which the arguments to a procedure are evaluated can make a
difference to the result. Define a simple procedure <tt>f</tt>
such that evaluating <tt>(+ (f 0) (f 1))</tt> will return 0 if
the arguments to <tt>+</tt> are evaluated from left to right but
will return 1 if the arguments are evaluated from right to
left.</p>
<div class="smallprint">
<hr />
</div>
<div class="footnote">
<p><a href="#call_footnote_Temp_321" name="footnote_Temp_321" id="footnote_Temp_321"><sup><small>1</small></sup></a>
Actually, this is not quite true. One exception was the
<a name="%_idx_2852"></a><a name="%_idx_2854"></a>random-number
generator in section <a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>. Another exception
involved the <a name="%_idx_2856"></a>operation/type tables we
introduced in section <a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>, where the values of
two calls to <tt>get</tt> with the same arguments depended on
intervening calls to <tt>put</tt>. On the other hand, until we
introduce assignment, we have no way to create such procedures
ourselves.</p>
<p><a href="#call_footnote_Temp_322" name="footnote_Temp_322" id="footnote_Temp_322"><sup><small>2</small></sup></a> <a name="%_idx_2864"></a><a name="%_idx_2866"></a>The value of a
<tt>set!</tt> expression is implementation-dependent.
<tt>Set!</tt> should be used only for its effect, not for its
value.</p>
<p><a name="%_idx_2868"></a><a name="%_idx_2870"></a><a name="%_idx_2872"></a>The name <tt>set!</tt> reflects a naming
convention used in Scheme: Operations that change the values of
variables (or that change data structures, as we will see in
section <a href="book-Z-H-22.html#%_sec_3.3">3.3</a>) are
given names that end with an exclamation point. This is similar
to the convention of designating predicates by names that end
with a question mark.</p>
<p><a href="#call_footnote_Temp_323" name="footnote_Temp_323" id="footnote_Temp_323"><sup><small>3</small></sup></a> We have
already used <a name="%_idx_2878"></a><tt>begin</tt> implicitly
in our programs, because in Scheme the body of a procedure can
be a sequence of expressions. Also, the
<<em>consequent</em>> part of each clause in a <a name="%_idx_2880"></a><a name="%_idx_2882"></a><tt>cond</tt>
expression can be a sequence of expressions rather than a