SICP 3.5.5

July 11, 2021 12:24

This is a brief section that continues the theme of practical uses for streams. This time there isn’t anything particularly intricate related to internal workings of the stream. Instead, it’s leading toward a particular idea, of a stream that can create the same effect as assignment to change state over time. Far from being an esoteric side topic on the way to building programs, it’s an idea that has garnered some interest in recent years, as it is at the heart of something called Functional Reactive Programming. If you’re interested in knowing more, you can search up resources on that topic.

There are only two exercises in this section. Because the results are partly determined by random values, it’s not possible to do a completely reliable test of all the results. In the first exercise, we can at least check that the output is repeatable, as that is a requirement. The actual values still need to be observed, though; a faulty implementation could produce output that passes a ‘repeatability’ test fairly easily. The randomness also means that we can’t guarantee a test did not pass merely by coincidence, nor can we test reliably for a negative outcome (i.e. test for patterns that ‘should’ be different). There are some statistical approaches that could be used if we actually wanted to test such a system, but I feel that would be taking the topic a bit far afield. This isn’t about random numbers, it’s about stream processing.

The text also doesn’t completely specify how the stream of requests is formatted. I made it so that the elements of the stream are either the token 'generate, or a list in the form ('reset x) where x indicates the number. The reason for using a list instead of a simple pair is so that input streams can be written out more straightforwardly as quoted lists. To simplify the creation of the input even more, there’s a procedure that converts ‘abbreviated’ forms (using the letters g and r instead of the full words). To use the test input streams, make sure that your version accepts requests in the full-word form. Additionally, the wording of the exercise seems to imply that a reset request might also give an output of the specified value, as it refers to resetting the ‘sequence’, whereas generate makes a ‘new’ value. Some of the tests that rely on stream references have an alternate version, depending on whether resets produce output or not.

One of the test sequences also checks that two streams produced in this fashion do not interfere with each other when they are run ‘concurrently’. This isn’t so much concurrency from a processing point of view, but in terms of the event streams. We know (or can expect) that the random values in the stream are not actually computed until the first time an element of the stream is referenced. We want to ensure two things: Firstly, if we access the same stream reference later on, we don’t get a different value. (This is likely handled by memoization of streams). Secondly, we need to make sure nothing disrupts the way the random numbers of a given stream are generated, so that ‘the same’ calculations produce the same result no matter where they occur in stream time or actual time. Technically all that is needed in this case is that a reset command produces the same output sequence after it, and we can’t be certain of ‘when’ the calculations occur (e.g. what we call a stream might pre-compute 5 or 10 random values in advance, and we’d be none the wiser). So it’s still a bit questionable from a testing point of view. If this part is giving you trouble, consider it optional, but at least be aware of it as something to keep in mind if taking this section’s functional approach to time-ordered events.

The second exercise is to redo Exercise 3.6 using streams. While there are definitely some functions from that exercise that would be useful to include here, I consider it an element of the exercise to understand just what can be re-used and what might need to be updated. I did, however, include an implementation of a Pseudo-random Number Generator, and a few interface functions for it. You may choose to use this one, or whatever built-in random function your own interpreter uses.


Exercises 3.5.5