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
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
function
`rand_update`
that has the property that if we start with a given
number `x_1` and form

x_2 = rand_update(x_1); x_3 = rand_update(x_2);

We can implement `rand` as a
function
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`.

function make_rand() { let x = random_init; function rand() { x = rand_update(x); return x; } return rand; } const rand = make_rand();

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 $\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
function
`monte_carlo`, which takes
as arguments the number of times to try an experiment, together with
the experiment, represented as a no-argument
function
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.

function estimate_pi(trials) { return math_sqrt(6 / monte_carlo(trials, cesaro_test)); } function cesaro_test() { return gcd(rand(), rand()) === 1; } function monte_carlo(trials, experiment) { function iter(trials_remaining, trials_passed) { if (trials_remaining === 0) { return trials_passed / trials; } else if (experiment()) { return iter(trials_remaining - 1, trials_passed + 1); } else { return iter(trials_remaining - 1, trials_passed); } } return 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:

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); if (trials_remaining === 0) { return trials_passed / trials; } else if (gcd(x1, x2) === 1) { return iter(trials_remaining - 1, trials_passed + 1, x2); } else { return 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`
function
that takes as an argument an
arbitrary `experiment`
function. 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
function
`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`
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.

function random_in_range(low, high) { const range = high - low; return low + random(range); }

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

let state = 2; function rand(symbol) { if (symbol === "reset") { return new_state => { state = new_state; }; } else { // symbol is "generate" state = (state * 1010) % 1101; return state; } }

[1]
One common way to implement
`rand_update`
is to use the rule that $x$ is updated to $ax+b$
modulo $m$, where $a$, $b$, and $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
`rand_update`
function
computes a mathematical function: Given the same input twice, it
produces the same output. Therefore, the number sequence produced by
`rand_update`
certainly is not *
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 .

random,if by

randomwe insist that each number in the sequence is unrelated to the preceding number. The relation between

real randomnessand so-called

[2]
This theorem is due to E.
Cesàro. See
section 4.5.2 of
Knuth 1981 for a discussion and a proof.

3.1.2 The Benefits of Introducing Assignment