SICP 3.5.5

July 25, 2021 11:36

Exercise 3.81

The basic form of the solution is to take the rand procedure that accepts an argument, and use stream-map to apply it to the input stream. Minor adjustments need to be made so that the requests are accepted in the format used by the stream. To make a version that does not produce output on reset requests, just add a stream-filter using number? and have the internal resetting procedure return a non-numeric value.

There is one more consideration for the stream version. To prevent two such random stream generators from interfering (in the manner of the ‘concurrency’ test), each needs its own pseudo-random number generator. If there is only one global PRNG, then the sequence will be inconsistent when requests are being handled by two different stream processors. In Racket, a new PRNG can be created using make-pseudo-random-generator, and passing the generator as an argument to the random procedure. The reset takes a little extra effort (as only the ‘current’ PRNG can be reset). In a truly concurrent system this reset would need to be handled using a synchronization mechanism to avoid problems. Other interpreters may have their own means of making new random generators. Alternatively, the PRNG can be a procedure of its own and avoid using the system’s built-in random number methods. (see 3.1.2, when the original rand was discussed, for more details).

Exercise 3.82

In order to model this after the version from Exercise 3.5, it’s useful to define random-in-range to work on a stream. Naturally the stream of random input values is one generated using the solution for Exercise 3.81; I used constant-gen as the request stream to just keep producing random values. Since this version of monte-carlo needs an experiment stream, not just the experiment as a procedure, we have to define a recursive stream-generation function that computes success or failure, and takes a random stream as its input (this is an internal definition, so P is the predicate already passed as an argument).

(define (experiment-stream rand-stream)
       (P (random-in-range x1 x2 rand-stream)
          (random-in-range y1 y2 (stream-cdr rand-stream))
       (experiment-stream (stream-cdr (stream-cdr rand-stream))) ; taking two values at a time

We have to take two random values at a time from the random-stream, which is why this can’t simply be another stream-map. It could be possible to use mapping by using multiple functions, but it’s reasonably easy to handle it in this fashion. This procedure does assume the random stream will be infinite, and therefore does not check if it can take two more values or not. This is an optimization to speed up the processing, since it really should not be run with a finite stream.

The last step is to compute the total area in order to scale the results properly. That leads to a call to scale-stream around the call to the stream version of monte-carlo. The inputs are set up with the initial values of passes and failures set to 0, and that is our final stream.

Solutions 3.5.5