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 function 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
function
rand-update
rand_update
that has the property that if we start with a given number
$x_{1}$ and form
Original | JavaScript | |
$x_{2}$ = (rand-update $x_{1}$) $x_{3}$ = (rand-update $x_{2}$) | $x_2$ = rand_update($x_1$); $x_3$ = rand_update($x_2$); |
We can implement rand as a procedure function with a local state variable x that is initialized to some fixed value random-init. random_init. Each call to rand computes rand-update rand_update of the current value of x, returns this as the random number, and also stores this as the new value of x.
Original | JavaScript |
(define rand (let ((x random-init)) (lambda () (set! x (rand-update x)) x))) | function make_rand() { let x = random_init; return () => { x = rand_update(x); return x; }; } const rand = make_rand(); |
Of course, we could generate the same sequence of random numbers without using assignment by simply calling rand-update 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. 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 $\pi$ using the fact that $6/\pi^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.[2] To obtain the approximation to $\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 $6/\pi^2$, and from this we obtain our approximation to $\pi$.
The heart of our program is a procedure function monte-carlo, monte_carlo, which takes as arguments the number of times to try an experiment, together with the experiment, represented as a no-argument procedure function that will return either true or false each time it is run. Monte-carlo The function 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.
Original | JavaScript |
(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)) | function estimate_pi(trials) { return math_sqrt(6 / monte_carlo(trials, dirichlet_test)); } function dirichlet_test() { return gcd(rand(), rand()) === 1; } function monte_carlo(trials, experiment) { function iter(trials_remaining, trials_passed) { return trials_remaining === 0 ? trials_passed / trials : experiment() ? iter(trials_remaining - 1, trials_passed + 1) : iter(trials_remaining - 1, trials_passed); } return iter(trials, 0); } |
Now let us try the same computation using rand-update rand_update directly rather than rand, the way we would be forced to proceed if we did not use assignment to model local state:
Original | JavaScript |
(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)) | function estimate_pi(trials) { return math_sqrt(6 / random_gcd_test(trials, random_init)); } function random_gcd_test(trials, initial_x) { function iter(trials_remaining, trials_passed, x) { const x1 = rand_update(x); const x2 = rand_update(x1); return trials_remaining === 0 ? trials_passed / trials : gcd(x1, x2) === 1 ? iter(trials_remaining - 1, trials_passed + 1, x2) : iter(trials_remaining - 1, trials_passed, x2); } return 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 monte_carlo procedure function that takes as an argument an arbitrary experiment procedure. function. In our second version of the program, with no local state for the random-number generator, random-gcd-test 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. 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 function estimate-pi 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, function, 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.
Original | JavaScript |
(define (random-in-range low high) (let ((range (- high low))) (+ low (random range)))) | function random_in_range(low, high) { const range = high - low; return low + random(range); } |
random,if by
randomwe insist that each number in the sequence is unrelated to the preceding number. The relation between
real randomnessand so-called 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