SICP 3.5.3 Exercises

December 13, 2020 11:54

This section continues to delve into the power (as well as the perils) of processing data using streams. It is also one that is quite difficult to test directly, since it’s about comparing different approaches and fixing subtle mistakes. Some of the exercises involve modifications made for the sake of efficiency, or changes that otherwise do not alter the outward behavior. In those cases, the testing will only ensure that the output is still consistent and correct. Testing the improvements would likely involve a fairly complex system that’d be difficult to make work in multiple Scheme implementations, and I’d prefer to keep the tests as broadly applicable as possible.

Furthermore, these exercises mostly involve applications that rely on arithmetic calculations. That’s an additoinal complication for a testing approach that would easily check for the ‘correct’ output in most situations or across different interpreters. Exactly how precise the answer must be is an open question. Tests that simply check the eventual result are also less likely to be useful when solving the exercise, as it’s often more illuminating to see how a problem is developing as the stream is built.

The exercises will therefore not always include a direct comparison of ‘expected’ output for testing, and instead display a list of a certain number of stream values. There are still a number of useful ‘test’ inputs that should reveal the proper (or improper) workings of the procedures for some of the exercises. For most, it will be necessary to observe the entire sequence of outputs to see what is happening, and determine if that is what is desired.

Once again, there are a few new procedures defined in the text, and those are provided in a separate file, called ‘Stream_353’ in the library. Included with this are two useful test functions for streams. One of them will search through a stream until it finds a value that satisfies some predicate, and then it will return the index at which it was found. It does this by simply keeping a count of the index. Of course, it is possible that with an infinite stream, it might never find a value. Be aware that it may be necessary to kill the program if it gets stuck trying to reach a value (most of the example values searched for should take no more than a few seconds to process). Here is the code for that procedure:

(define (find-first-in-stream test str)
  (define (find-first-in-stream s count)
    (if (stream-null? s)
        (if (test (stream-car s))
            (find-first-in-stream (stream-cdr s) (add1 count))
  (find-first-in-stream str 1)

This section is still math-heavy, although the topics are, for the most part, not as advanced as in Section 3.5.2. The last few questions, however, are related to the field of electrical signal processing. It’s not totally necessary to understand the specific topics in order to solve the exercises, although following the block diagram in the text will be important. If you’re struggling with this, compare the diagram for the ‘integral’ processor in the text (Fig. 3.32) so that you can see how the blocks and signals correspond with streams and procedure calls. To further assist with these exercises, the examples I’ve provided give some typical uses for these sorts of simulation systems. If you do happen to be familiar with these topics, then these examples might help improve the connection with the text, although the limitations of this simulation model will be readily apparent.

For the zero-crossing exercises (3.74 – 3.76), I created a stream that generates a sine wave to test them. You should hopefully be familiar enough with sine waves as a function (or ‘signal’) to know what values to expect in the stream. Exactly how the output from the exercises should be presented, though, is a matter of interpretation. I’ve tried to write the inputs in such a way that the results produced can be compared to each other, but some modification may be needed for whichever approach you use. If you are still struggling with visualizing the ‘proper’ output for these lists of numbers, it may well help to make a plot of the lists of points in some other software (Doing that programatically in the interpreter is possible, but well beyond the scope of this already application-heavy section.)

There’s one more thing to note, related to measuring how long it takes for different methods to reach the same answer. Previously, measuring the ‘real time’ ‘Real’ time can include processes other than the measured one taken to execute some intensive calculation had to be accomplished with specialized code for each interpreter. Since I’ve mentioned how to use define-syntax to create our own special forms, it’s possible now to use a special form to give these calls a single interface. Hence, there is now the measure-time form that calls a procedure and instead of getting its output, reports the time taken. In the file, the form is only defined for Racket/Pretty Big and MIT-Scheme. If you know how to get your interpreter to measure the time taken by a procedure, you can likely substitute for one of those forms and use it on your own, if you so desire. If you do not want to measure the time taken, you can also alter the lines to simply execute the procedure, as there is an additional call-count variable that records the number of calls, which can be a stand-in for the actual time taken.


Exercises 3.5.3