Structure and Interpretation of Computer Programs (46 page)

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
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
rand-update
that has the property that if we start with a given
number
x
₁
and form

x
₂
 = (rand-update 
x
₁
)
x
₃
 = (rand-update 
x
₂
)

then the sequence of values
x
₁
,
x
₂
,
x
₃
,
...
, will have the
desired statistical properties.
⁶

We can implement
rand
as a procedure with a local state variable
x
that is initialized to some fixed value
random-init
.
Each call to
rand
computes
rand-update
of the current
value of
x
, returns this as the random number, and also stores
this as the new value of
x
.

(define rand
  (let ((x random-init))
    (lambda ()
      (set! x (rand-update x))
      x)))

Of course, we could generate the same sequence of random numbers
without using assignment by simply calling
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
x
to be passed as an argument to
rand-update
. To realize what an
annoyance this would be, consider using random numbers to implement a
technique called
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
π using the fact
that 6/π
²
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.
⁷
To obtain
the approximation to π, 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 6/π
²
, and from this we obtain our
approximation to π.

The heart of our program is a procedure
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.
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.

(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))

Now let us try the same computation using
rand-update
directly
rather than
rand
, the way we would be forced to proceed if we
did not use assignment to model local state:

(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))
              (else
               (iter (- trials-remaining 1)
                     trials-passed
                     x2))))))
  (iter trials 0 initial-x))

While the program is still simple, it betrays some painful
breaches of modularity. In our first version of the program, using
rand
, we can express the Monte Carlo method directly as
a general
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,
random-gcd-test
must explicitly manipulate the random numbers
x1
and
x2
and recycle
x2
through the iterative loop as
the new input to
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
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
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 3.5.
  
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
P
(
x
,
y
) that is
true for points (
x
,
y
) 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 (
x
- 5)
²
+ (
y
- 7)
²
<
3
²
. 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 (
x
,
y
) that lie in the rectangle, and testing
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
estimate-integral
that takes as arguments a predicate
P
, upper
and lower bounds
x1
,
x2
,
y1
, and
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 π. Use
your
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
random-in-range
procedure implements this in terms of the
random
procedure used in section 
1.2.6
, which returns a nonnegative
number less than its input.
⁸

(define (random-in-range low high)
  (let ((range (- high low)))
    (+ low (random range))))

Exercise 3.6.
  
It is useful to be able to reset a random-number generator to produce
a sequence starting from a given value. Design a new
rand
procedure that is called with an argument that is either the symbol
generate
or the symbol
reset
and behaves as follows:
(rand
'generate)
produces a new random number;
((rand 'reset)
<
new-value
>)
resets the internal state variable to the designated
<
new-value
>. 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.

As we have seen, the
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
section 
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
functional programming
.

To understand how assignment complicates matters, consider a
simplified version of the
make-withdraw
procedure of
section 
3.1.1
that does not bother to check
for an insufficient amount:

(define (make-simplified-withdraw balance)
  (lambda (amount)
    (set! balance (- balance amount))
    balance))
(define W (make-simplified-withdraw 25))
(W 20)
5
(W 10)
- 5

Compare this procedure with the following
make-decrementer
procedure, which does not use
set!
:

(define (make-decrementer balance)
  (lambda (amount)
    (- balance amount)))

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
make-simplified-withdraw
:

(define D (make-decrementer 25))
(D 20)
5
(D 10)
15

We can use the substitution model to explain how
make-decrementer
works. For instance, let us analyze the evaluation
of the expression

((make-decrementer 25) 20)

We first simplify the operator of the combination by substituting 25
for
balance
in the body of
make-decrementer
. This reduces
the expression to

((lambda (amount) (- 25 amount)) 20)

Now we apply the operator by substituting 20 for
amount
in the
body of the
lambda
expression:

(- 25 20)

The final answer is 5.

Observe, however, what happens if we attempt a similar substitution
analysis with
make-simplified-withdraw
:

((make-simplified-withdraw 25) 20)

We first simplify the operator by substituting 25 for
balance
in
the body of
make-simplified-withdraw
.
This reduces the expression to
⁹

((lambda (amount) (set! balance (- 25 amount)) 25) 20)

Now we apply the operator by substituting 20 for
amount
in the
body of the
lambda
expression:

(set! balance (- 25 20)) 25

If we adhered to the substitution model, we would have to say that the
meaning of the procedure application is to first set
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
balance
(before the
effect of the
set!
) from the second occurrence of
balance
(after the effect of the
set!
), and the substitution model
cannot do this.