-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathch3.tm
4248 lines (3151 loc) · 297 KB
/
ch3.tm
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
<TeXmacs|2.1.2>
<project|sicp.tm>
<style|<tuple|book|smart-ref|preview-ref>>
<\body>
<chapter|Modularity, Objects and State>
The preceding chapters introduced the basic elements from which programs
are made. We saw how<next-line>primitive procedures and primitive data are
combined to construct compound entities, and we learned that abstraction is
vital in helping us to cope with the complexity of large systems. But these
tools are not sufficient for designing programs. Effective program
synthesis also requires organizational principles that can guide us in
formulating the overall design of a program. In particular, we need
strategies to help us structure large systems so that they will be
<em|modular><index|modular>, that is, so that they can be divided
``naturally'' into coherent parts that can be separately developed and
maintained.
One powerful design strategy, which is particularly appropriate to the
construction of programs for modeling physical systems, is to base the
structure of our programs on the structure of the system being modeled. For
each object in the system, we construct a corresponding computational
object. For each system action, we define a symbolic operation in our
computational model. Our hope in using this strategy is that extending the
model to accommodate new objects or new actions will require no strategic
changes to the program, only the addition of the new symbolic analogs of
those objects or actions. If we have been successful in our system
organization, then to add a new feature or debug an old one we will have to
work on only a localized part of the system.
To a large extent, then, the way we organize a large program is dictated by
our perception of the system to be modeled. In this chapter we will
investigate two prominent organizational strategies arising from two rather
different ``world views'' of the structure of systems. The first
organizational strategy concentrates on <em|objects><index|object>, viewing
a large system as a collection of distinct objects whose behaviors may
change over time. An alternative organizational strategy concentrates on
the <em|streams><index|stream> of information that flow in the system, much
as an electrical engineer views a signal-processing system.
Both the object-based approach and the stream-processing approach raise
significant linguistic issues inprogramming. With objects, we must be
concerned with how a computational object can change and yet maintain its
identity. This will force us to abandon our old substitution model of
computation (<smart-ref|sec:1.1.5>) in favor of a more mechanistic but less
theoretically tractable <em|environment model><index|environment model> of
computation. The difficulties of dealing with objects, change, and identity
are a fundamental consequence of the need to grapple with time in our
computational models. These difficulties become even greater when we allow
the possibility of concurrent execution of programs. The stream approach
can be most fully exploited when we decouple simulated time in our model
from the order of the events that take place in the computer during
evaluation. We will accomplish this using a technique known as <em|delayed
evaluation><index|delayed evaluation>.
<section|Assignment and Local State>
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 <em|state
variables><index|state variable>, 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.
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.
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><index|local state variable> 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 <em|assignment operator><index|assignment operator> to enable us
to change the value associated with a name.
<subsection|Local State Variables><label|sec:3.1.1>
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 <scm|withdraw>, which takes
as argument an <verbatim|amount> to be withdrawn. If there is enough money
in the account to accommodate the withdrawal, then <verbatim|withdraw>
should return the balance remaining after the withdrawal. Otherwise,
<verbatim|withdraw> should return the message <em|Insufficient funds>. For
example, if we begin with $100 in the account, we should obtain the
following sequence of responses using withdraw:
<\scm-code>
(withdraw 25)
75
(withdraw 25)
50
(withdraw 60)
"Insufficient funds"
(withdraw 15)
35
</scm-code>
Observe that the expression <scm|(withdraw 25)>, 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.<\footnote>
Actually, this is not quite true. One exception was the random-number
generator in <smart-ref|sec:1.2.6>. Another exception involved the
operation/type tables we introduced in <smart-ref|sec:2.4.3>, where the
values of two calls to get with the same arguments depended on
intervening calls to put. On the other hand, until we introduce
assignment, we have no way to create such procedures ourselves.
</footnote>
To implement <scm|withdraw>, we can use a variable <scm|balance> to
indicate the balance of money in the account and define <scm|withdraw> as a
procedure that accesses <verbatim|balance>. The <verbatim|withdraw>
procedure checks to see if <verbatim|balance> is at least as large as the
requested <verbatim|amount>. If so, withdraw decrements balance by
<verbatim|amount> and returns the new value of <verbatim|balance>.
Otherwise, withdraw returns the <em|Insufficient funds> message. Here are
the definitions of <verbatim|balance> and <verbatim|withdraw>:
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define balance 100)
\ \ (define (withdraw amount)
\ \ \ \ (if (\<gtr\>= balance amount)
\ \ \ \ \ \ (begin
\ \ \ \ \ \ \ \ (set! balance (- balance amount))
\ \ \ \ \ \ \ \ balance)
\ \ \ \ \ \ "Insufficient funds"))<next-line>
<|unfolded-io>
100
</unfolded-io>
<\input|Scheme] >
\;
</input>
</session>
Decrementing balance is accomplished by the expression
<\scm-code>
(set! balance (- balance amount))
</scm-code>
This uses the <scm|set!> special form, whose syntax is
<\scm-code>
(set! \<less\>name\<gtr\> \<less\>new-value\<gtr\>)
</scm-code>
Here <em|\<less\>name\<gtr\>> is a symbol and <em|\<less\>new-value\<gtr\>>
is any expression. <scm|set!> changes <em|\<less\>name\<gtr\>> so that its
value is the result obtained by evaluating <em|\<less\>new-value\<gtr\>>.
In the case at hand, we are changing <verbatim|balance> so that its new
value will be the result of subtracting <verbatim|amount> from the previous
value of <verbatim|balance>.<\footnote>
The value of a <scm|set!> expression is implementation-dependent.
<scm|set!> should be used only for its effect, not for its value.
The name <scm|set!> reflects a naming convention used in Scheme:
Operations that change the values of variables (or that change data
structures, as we will see in <smart-ref|sec:3.3>) 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.
</footnote>
<verbatim|Withdraw> also uses the <scm|begin> special form to cause two
expressions to be evaluated in the case where the <scm|if> test is true:
first decrementing <verbatim|balance> and then returning the value of
<verbatim|balance>. In general, evaluating the expression
<\scm-code>
(begin \<less\>exp1\<gtr\> \<less\>exp2\<gtr\> ... \<less\>expk\<gtr\>)
</scm-code>
causes the expressions <verbatim|\<less\>exp1\<gtr\>> through
<verbatim|\<less\>expk\<gtr\>> to be evaluated in sequence and the value of
the final expression <verbatim|\<less\>expk\<gtr\>> to be returned as the
value of the entire <scm|begin> form.<\footnote>
We have already used <scm|begin> implicitly in our programs, because in
Scheme the body of a procedure can be a sequence of expressions. Also,
the <verbatim|\<less\>consequent\<gtr\>> part of each clause in a
<scm|cond> expression can be a sequence of expressions rather than a
single expression
</footnote>
Although <verbatim|withdraw> works as desired, the variable
<verbatim|balance> presents a problem. As specified above,
<verbatim|balance> 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 <verbatim|balance> internal to
<verbatim|withdraw>, so that <verbatim|withdraw> would be the only
procedure that could access <verbatim|balance> directly and any other
procedure could access <verbatim|balance> only indirectly (through calls to
<verbatim|withdraw>). This would more accurately model the notion that
<verbatim|balance> is a local state variable used by <verbatim|withdraw> to
keep track of the state of the account.
We can make <verbatim|balance> internal to <verbatim|withdraw> by rewriting
the definition as follow:
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define new-withdraw
\ \ (let ((balance 100))
\ \ \ \ (lambda (amount)
\ \ \ \ \ \ (if (\<gtr\>= balance amount)
\ \ \ \ \ \ \ \ (begin (set! balance (- balance amount)) balance)
\ \ \ \ \ \ \ \ "Insufficient funds"))))
<|unfolded-io>
new-withdraw
</unfolded-io>
</session>
What we have done here is use <scm|let> to establish an environment with a
local variable <verbatim|balance>, bound to the initial value <scm|100>.
Within this local environment, we use <scm|lambda> to create a procedure
that takes <verbatim|amount> as an argument and behaves like our previous
<verbatim|withdraw> procedure. This procedure -- returned as the result of
evaluating the <scm|let> expression -- is <verbatim|new-withdraw>, which
behaves in precisely the same way as <verbatim|withdraw> but whose variable
<verbatim|balance> is not accessible by any other procedure.<\footnote>
In programming-language jargon, the variable <verbatim|balance> is said
to be <em|encapsulated><index|encapsulated> within the
<verbatim|new-withdraw> procedure. Encapsulation reflects the general
system-design principle known as the <em|hiding principle><index|hiding
principle>: One can make a system more modular and robust by protecting
parts of the system from each other; that is, by providing information
access only to those parts of the system that have a ``need to know.''
</footnote>
Combining <scm|set!> 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 (<smart-ref|sec:1.1.5>) 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
<smart-ref|sec:3.1.3>.) As a consequence, we technically have at this point
no way to understand why the <verbatim|new-withdraw> procedure behaves as
claimed above. In order to really understand a procedure such as
<verbatim|new-withdraw>, we will need to develop a new model of procedure
application. In <smart-ref|sec:3.2> we will introduce such a model,
together with an explanation of <scm|set!> and local variables. First,
however, we examine some variations on the theme established <verbatim|by
new-withdraw>.
The following procedure, <verbatim|make-withdraw>, creates ``withdrawal
processors.'' The formal parameter <verbatim|balance> in
<verbatim|make-withdraw> specifies the initial amount of money in the
account.<\footnote>
In contrast with new-withdraw above, we do not have to use let to make
balance a local variable, since formal parameters are already local. This
will be clearer after the discussion of the environment model of
evaluation in <smart-ref|sec:3.2>. (See also exercise 3.10.)
</footnote>
<\session|scheme|default>
<\folded-io|Scheme] >
(define (make-withdraw balance)
\ \ (lambda (amount)
\ \ \ \ (if (\<gtr\>= balance amount)
\ \ \ \ \ \ (begin\
\ \ \ \ \ \ \ \ (set! balance (- balance amount))
\ \ \ \ \ \ \ \ balance)
\ \ \ \ \ \ "Insufficient funds")))
<|folded-io>
make-withdraw
</folded-io>
</session>
<verbatim|make-withdraw> can be used as follows to create two objects
<verbatim|W1> and <verbatim|W2>:
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define W1 (make-withdraw 100))
<|unfolded-io>
W1
</unfolded-io>
<\unfolded-io|Scheme] >
(define W2 (make-withdraw 100))
<|unfolded-io>
W2
</unfolded-io>
<\unfolded-io|Scheme] >
(W1 50)
<|unfolded-io>
50
</unfolded-io>
<\unfolded-io|Scheme] >
(W2 70)
<|unfolded-io>
30
</unfolded-io>
<\unfolded-io|Scheme] >
(W1 40)
<|unfolded-io>
10
</unfolded-io>
<\unfolded-io|Scheme] >
(W2 40)
<|unfolded-io>
"Insufficient funds"
</unfolded-io>
</session>
Observe that <verbatim|W1> and <verbatim|W2> are completely independent
objects, each with its own local state variable <verbatim|balance>.
Withdrawals from one do not affect the other.
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:
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define (make-account balance)
\ \ (define (withdraw amount)
\ \ \ \ (if (\<gtr\>= balance amount)
\ \ \ \ \ \ (begin (set! balance (- balance amount))
\ \ \ \ \ \ \ \ balance)
\ \ \ \ \ \ "Insufficient funds"))
\ \ (define (deposit amount)
\ \ \ \ (set! balance (+ balance amount))
\ \ \ \ balance)
(define (dispatch m)
\ \ (cond ((eq? m 'withdraw) withdraw)
\ \ \ \ \ \ \ \ ((eq? m 'deposit) deposit)
\ \ \ \ \ \ \ \ (else (error "Unknown request -- MAKE-ACCOUNT"))))
dispatch)
<|unfolded-io>
make-account
</unfolded-io>
<\input|Scheme] >
\;
</input>
</session>
Each call to <verbatim|make-account> sets up an environment with a local
state variable <verbatim|balance>. Within this environment,
<verbatim|make-account> defines procedures <verbatim|deposit> and
<verbatim|withdraw> that access <verbatim|balance> and an additional
procedure <verbatim|dispatch> that takes a ``message'' as input and returns
one of the two local procedures. The <verbatim|dispatch> procedure itself
is returned as the value that represents the bank-account object. This is
precisely the <em|message-passing> style of programming that we saw in
<smart-ref|sec:2.4.3>, although here we are using it in conjunction with
the ability to modify local variables.
<verbatim|make-account> can be used as follows:
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define acc (make-account 100))
<|unfolded-io>
dispatch
</unfolded-io>
<\unfolded-io|Scheme] >
((acc 'withdraw) 50)
<|unfolded-io>
50
</unfolded-io>
<\unfolded-io|Scheme] >
((acc 'withdraw) 60)
<|unfolded-io>
"Insufficient funds"
</unfolded-io>
<\unfolded-io|Scheme] >
((acc 'deposit) 40)
<|unfolded-io>
90
</unfolded-io>
<\unfolded-io|Scheme] >
((acc 'withdraw) 60)
<|unfolded-io>
30
</unfolded-io>
<\input|Scheme] >
\;
</input>
</session>
Each call to <verbatim|acc> returns the locally defined <verbatim|deposit>
or <verbatim|withdraw> procedure, which is then applied to the specified
amount. As was the case with <verbatim|make-withdraw>, another call to
<verbatim|make-account>
<\session|scheme|default>
<\input>
Scheme]\
<|input>
(define acc2 (make-account 100))
</input>
</session>
will produce a completely separate account object, which maintains its own
local <verbatim|balance>.
<\exercise>
An <em|accumulator><index|accumulator> 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 <verbatim|make-accumulator> that generates
accumulators, each maintaining an independent sum. The input to
<verbatim|make-accumulator> should specify the initial value of the sum;
for example
<\scm-code>
(define A (make-accumulator 5))
(A 10)
15
(A 10)
25
</scm-code>
</exercise>
<\exercise>
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 <verbatim|make-monitored> that takes as
input a procedure, <verbatim|f>, that itself takes one input. The result
returned by <verbatim|make-monitored> is a third procedure, say
<verbatim|mf>, that keeps track of the number of times it has been called
by maintaining an internal counter. If the input to mf is the special
symbol <verbatim|how-many-calls?>, then <verbatim|mf> returns the value
of the counter. If the input is the special symbol
<verbatim|reset-count>, then <verbatim|mf> resets the counter to zero.
For any other input, mf returns the result of calling <verbatim|f> on
that input and increments the counter. For instance, we could make a
monitored version of the <verbatim|sqrt> procedure:
<\scm-code>
(define s (make-monitored sqrt))
(s 100)
10
(s 'how-many-calls?)
1
</scm-code>
</exercise>
<\exercise>
Modify the <verbatim|make-account> procedure so that it creates
password-protected accounts. That is, <verbatim|make-account> should take
a symbol as an additional argument, as in
<\scm-code>
(define acc (make-account 100 'secret-password))
</scm-code>
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:
<\scm-code>
((acc 'secret-password 'withdraw) 40)
60
((acc 'some-other-password 'deposit) 50)
"Incorrect password"
</scm-code>
</exercise>
<\exercise>
Modify the <verbatim|make-account> procedure of exercise 3.3 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 <verbatim|call-the-cops>.
</exercise>
<subsection|The Benefits of Introducing Assignment>
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 <verbatim|rand> that, whenever it is called, returns an
integer chosen at random.
It is not at all clear what is meant by ``chosen at random.'' What we
presumably want is for successive calls to rand 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 <verbatim|rand-update> that has the
property that if we start with a given number <math|x<rsub|1>> and form:
<\verbatim-code>
<math|x<rsub|2>> = (rand-update <math|x<rsub|1>> )
<math|x<rsub|3>> = (rand-update <math|x<rsub|2>> )
</verbatim-code>
then the sequence of values <math|x<rsub|1>>, <math|x<rsub|3>>,
<math|x<rsub|3>>, ..., will have the desired statistical
properties.<\footnote>
One common way to implement <verbatim|rand-update> is to use the rule
that <math|x> is updated to <math|a*x + b modulo m>, where <math|a>,
<math|b>, and <math|m> are appropriately chosen integers. Chapter 3 of
Knuth 1981 includes an extensive discussion of techniques for generating
sequences of random numbers and establishing their statistical
properties. Notice that the <verbatim|rand-update> procedure computes a
mathematical function: Given the same input twice, it produces the same
output. Therefore, the number sequence produced by <verbatim|rand-update>
certainly is not ``random,'' if by ``random'' we insist that each number
in the sequence is unrelated to the preceding number. The relation
between ``real randomness'' and so-called
<em|pseudo-random><index|pseudo-random> sequences, which are produced by
well-determined computations and yet have suitable statistical
properties, is a complex question involving difficult issues in
mathematics and philosophy. Kolmogorov, Solomonoff, and Chaitin have made
great progress in clarifying these issues; a discussion can be found in
Chaitin 1975
</footnote>
We can implement <verbatim|rand> as a procedure with a local state variable
<verbatim|x> that is initialized to some fixed value
<verbatim|random-init>. Each call to <verbatim|rand> computes
<verbatim|rand-update> of the current value of <verbatim|x>, returns this
as the random number, and also stores this as the new value of
<verbatim|x>.
<\scm-code>
(define rand
\ \ (let ((x random-init))
\ \ \ \ (lambda ()
\ \ \ \ \ \ (set! x (rand-update x))
\ \ \ \ \ \ x)))
</scm-code>
Of course, we could generate the same sequence of random numbers without
using assignment by simply calling <verbatim|rand-update> directly.
However, this would mean that any part of our program that used random
numbers would have to explicitly remember the current value of <verbatim|x>
to be passed as an argument to <verbatim|rand-update>. To realize what an
annoyance this would be, consider using random numbers to implement a
technique called <em|Monte Carlo simulation><index|Monte Carlo simulation>.
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 <math|\<pi\>> using the fact that
<math|<frac*|6|\<pi\><rsup|2>>> 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.<\footnote>
This theorem is due to E. Cesàro. See section 4.5.2 of Knuth 1981 for a
discussion and a proof.
</footnote> To obtain the approximation to <math|\<pi\>>, we perform a
large number of experiments. In each experiment we choose two integers at
random and perform a test to see if their GCD is 1. The fraction of times
that the test is passed gives us our estimate of
<math|<frac*|6|\<pi\><rsup|2>>>, and from this we obtain our approximation
to <math|\<pi\>>.
The heart of our program is a procedure <verbatim|monte-carlo>, 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. <verbatim|monte-carlo> 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.
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define (estimate-pi trials)
\ \ (sqrt (/ 6 (monte-carlo trials cesaro-test))))
(define (cesaro-test)
\ \ (= (gcd (rand) (rand)) 1))
(define (monte-carlo trials experiment)
\ \ (define (iter trials-remaining trials-passed)
\ \ \ \ (cond\
\ \ \ \ \ \ ((= trials-remaining 0)
\ \ \ \ \ \ \ \ (/ trials-passed trials))
\ \ \ \ \ \ ((experiment)
\ \ \ \ \ \ \ \ (iter (- trials-remaining 1) (+ trials-passed 1)))
\ \ \ \ \ \ (else
\ \ \ \ \ \ \ \ (iter (- trials-remaining 1) trials-passed))))
\ \ (iter trials 0))
<|unfolded-io>
estimate-pi
</unfolded-io>
<\input|Scheme] >
\;
</input>
</session>
Now let us try the same computation using <verbatim|rand-update> directly
rather than <verbatim|rand>, the way we would be forced to proceed if we
did not use assignment to model local state:
<\session|scheme|default>
<\input>
Scheme]\
<|input>
(define (estimate-pi trials)
\ \ (sqrt (/ 6 (random-gcd-test trials random-init))))
(define (random-gcd-test trials initial-x)
\ \ (define (iter trials-remaining trials-passed x)
\ \ \ \ (let ((x1 (rand-update x)))
\ \ \ \ \ \ (let ((x2 (rand-update x1)))
\ \ \ \ \ \ \ \ (cond\
\ \ \ \ \ \ \ \ \ \ ((= trials-remaining 0)
\ \ \ \ \ \ \ \ \ \ \ \ (/ trials-passed trials))
\ \ \ \ \ \ \ \ \ \ ((= (gcd x1 x2) 1)
\ \ \ \ \ \ \ \ \ \ \ \ (iter (- trials-remaining 1) (+ trials-passed
1) x2))
\ \ \ \ \ \ \ \ \ \ <hlink||file:///C:/TJUPT/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A8%8B%E5%BA%8F%E7%9A%84%E6%9E%84%E9%80%A0%E5%92%8C%E8%A7%A3%E9%87%8A%C2%B7%E7%AC%AC2%E7%89%88%EF%BC%88%E4%B8%AD%E8%8B%B1%E5%8F%8C%E7%89%88%EF%BC%89/Structure%20and%20Interpretation%20of%20Computer%20Programs_2nd%20Edition%20by%20Harold%20Abelson,%20Gerald%20Jay%20Sussman.pdf#%E1%D6%CD4%F4%EB%BE%EF%u2014%03yB%DF%FD%C2%28footnote_Temp_331>(else
\ \ \ \ \ \ \ \ \ \ \ \ (iter (- trials-remaining 1) trials-passed
x2))))))
\ \ (iter trials 0 initial-x))
</input>
</session>
While the program is still simple, it betrays some painful breaches of
modularity. In our first version of the program, using <verbatim|rand>, we
can express the Monte Carlo method directly as a general<verbatim|
monte-carlo> procedure that takes as an argument an arbitrary experiment
procedure. In our second version of the program, with no local state for
the random-number generator, <verbatim|random-gcd-test> must explicitly
manipulate the random numbers <verbatim|x1> and <verbatim|x2> and recycle
<verbatim|x2> through the iterative loop as the new input to
<verbatim|rand-update>. 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 <verbatim|estimate-pi> 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 <verbatim|rand> procedure, so that
the details of random-number generation remain independent of the rest of
the program.
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.
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.
<\exercise>
<em|Monte Carlo integration><index|Monte Carlo integration> 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
<math|P(x, y)> that is true for points <math|(x, y)> in the region and
false for points not in the region. For example, the region contained
within a circle of radius <math|3> centered at <math|(5, 7)> is described
by the predicate that tests whether <math|(x - 5) <rsup|2> + (y -
7)<rsup|2>\<less\> 3<rsup|2>>. 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 <math|(2, 4)> and <math|(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 <math|(x,y)> that lie in the rectangle, and testing <math|P(x, y)>
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.
Implement Monte Carlo integration as a procedure
<verbatim|estimate-integral> that takes as arguments a predicate
<verbatim|P>, upper and lower bounds <verbatim|x1>, <verbatim|x2>,
<verbatim|y1>, and <verbatim|y2> for the rectangle, and the number of
trials to
\;
perform in order to produce the estimate. Your procedure should use the
same monte-carlo procedure that was used above to estimate <math|\<pi\>>.
Use your <verbatim|estimate-integral> to produce an estimate of by
measuring the area of a unit circle.
You will find it useful to have a procedure that returns a number chosen
at random from a given range. The following <verbatim|random-in-range>
procedure implements this in terms of the random procedure used in
<smart-ref|sec:1.2.6>, which returns a nonnegative number less than its
input.<\footnote>
MIT Scheme provides such a procedure. If random is given an exact
integer (as in <smart-ref|sec:1.2.6>) it returns an exact integer, but
if it is given a decimal value (as in this exercise) it returns a
decimal value.
</footnote>
<\session|scheme|default>
<\input>
Scheme]\
<|input>
(define (random-in-range low high)
\ \ (let ((range (- high low)))
\ \ \ \ (+ low (random range))))
</input>
</session>
</exercise>
<\exercise>
It is useful to be able to reset a random-number generator to produce a
sequence starting from a given value. Design a new <verbatim|rand>
procedure that is called with an argument that is either the symbol
<verbatim|generate> or the symbol <verbatim|reset> and behaves as
follows: <scm|(rand 'generate)> produces a new random number; <scm|((rand
'reset) \<less\>new-value\<gtr\>)> resets the internal state variable to
the designated <verbatim|\<less\>new-value\<gtr\>>. 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.
</exercise>
<subsection|The Cost of Introducing Assignment><label|sec:3.1.3>
As we have seen, the <scm|set!> 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 <smart-ref|sec:1.1.5>.
Moreover, no simple model with ``nice'' mathematical properties can be an
adequate framework for dealing with objects and assignment in programming
languages.
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 <em|functional programming><index|functional
programming>.
To understand how assignment complicates matters, consider a simplified
version of the <verbatim|make-withdraw> procedure of <smart-ref|sec:3.1.1>
that does not bother to check for an insufficient amount:
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define (make-simplified-withdraw balance)
\ \ (lambda (amount)
\ \ \ \ (set! balance (- balance amount))
\ \ \ \ balance))
<|unfolded-io>
make-simplified-withdraw
</unfolded-io>
<\unfolded-io|Scheme] >
(define W (make-simplified-withdraw 25))
<|unfolded-io>
W
</unfolded-io>
<\unfolded-io|Scheme] >
(W 20)
<|unfolded-io>
5
</unfolded-io>
<\unfolded-io|Scheme] >
(W 10)
<|unfolded-io>
-5
</unfolded-io>
<\input|Scheme] >
\;
</input>
</session>
Compare this procedure with the following <verbatim|make-decrementer>
procedure, which does not use <scm|set!>:
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define (make-decrementer balance)
\ \ (lambda (amount)
\ \ \ \ (- balance amount)))
<|unfolded-io>
make-decrementer
</unfolded-io>
<\input|Scheme] >
\;
</input>
</session>
<verbatim|make-decrementer> returns a procedure that subtracts its input
from a designated amount balance, but there is no accumulated effect over
successive calls, as with <verbatim|make-simplified-withdraw>:
<\session|scheme|default>
<\unfolded-io|Scheme] >
(define D (make-decrementer 25))
<|unfolded-io>
D
</unfolded-io>
<\unfolded-io|Scheme] >
(D 20)
<|unfolded-io>
5
</unfolded-io>
<\unfolded-io|Scheme] >
(D 10)
<|unfolded-io>
15
</unfolded-io>
<\input|Scheme] >
\;
</input>
</session>
We can use the substitution model to explain how
<verbatim|make-decrementer> works. For instance, let us analyze the
evaluation of the expression
<\scm-code>
((make-decrementer 25) 20)
</scm-code>
We first simplify the operator of the combination by substituting 25 for
<verbatim|balance> in the body of \ <verbatim|make-decrementer>. This
reduces the expression to
<\scm-code>
((lambda (amount) (- 25 amount)) 20)
</scm-code>
Now we apply the operator by substituting 20 for amount in the body of the
<scm|lambda> expression:
<\scm-code>
(- 25 20)
</scm-code>
The final answer is 5.
Observe, however, what happens if we attempt a similar substitution
analysis with <verbatim|make-simplified-withdraw>:
<\scm-code>
((make-simplified-withdraw 25) 20)
</scm-code>
We first simplify the operator by substituting 25 for <verbatim|balance> in
the body of <verbatim|make-simplified-withdraw>. This reduces the
expression to:<\footnote>
We don't substitute for the occurrence of <verbatim|balance> in the
<scm|set!> expression because the <verbatim|\<less\>name\<gtr\>> in a
<scm|set!> is not evaluated. If we did substitute for it, we would get
<scm|(set! 25 (- 25 amount))>, which makes no sense.
</footnote>
<\scm-code>
((lambda (amount) (set! balance (- 25 amount)) 25) 20)
</scm-code>
Now we apply the operator by substituting 20 for <verbatim|amount> in the
body of the <scm|lambda> expression:
<\scm-code>
(set! balance (- 25 20)) 25
</scm-code>
If we adhered to the substitution model, we would have to say that the
meaning of the procedure application is to first set <verbatim|balance> 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 <verbatim|balance> (before the effect
of the <scm|set!>) from the second occurrence of <verbatim|balance> (after
the effect of the <scm|set!>), and the substitution model cannot do this.
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 <scm|set!> 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