SICP 3.5.2 Exercises

October 4, 2020 11:17

This section continues the trend of exploring how streams work, but gets a bit more into their application, especially with the inclusion of exercises involving power series. If you haven’t ever studied this part of mathematics, it’s going to make some of these problems much harder to solve, especially as they are not the sort easily worked out using the computer. They require an understanding of the math first, so that you can see how to use streams as a tool.

Here are a few resources that may help, but it’s a complex topic and if it’s one you’ve never even briefly gone over, it will be somewhat difficult to understand what’s going on here, and you may wish to skip some exercises. However, if you merely need a refresher or an expansion on what you may have once learned, you should be able to get by in this section.



This video in particular will explain where the series in Exercise 3.59 come from:

The cosine and sine functions are derived as power series

There are also some exercises that are more open-ended in the sense of just figuring out what something does, without necessarily executing it. That means that adding in tests is less straightforward. You can’t always fix it and check against an expected result, and even when you do, that might not mean you’ve understood how it worked. What I have done will hopefully both give a decent test and assist in the understanding of the application of the streams, so that you can experiment a bit on your own if you want to delve deeper.

For the exercises that are more about adding a feature to stream programming, it is generally possible to test the first few terms of an operation and see whether they match an expected list. I had created the stream-test procedure which tests whether all members of a stream match a given predicate (typically equality for these numeric streams). All we need to do is limit the streams to the same size, and suppose that if they match within the first 10 or so terms, the result is correct.

With the power series, rather than check the expected value of the terms (which is fairly close to giving up the answer), I added some functions to make it easier to check if the functions are indeed being modeled accurately. They evaluate the power series for some value x. That result may even be easier to understand than inspecting the coefficients themselves, as long as you know what a power series does. Most of the power series that someone would work with are equivalent to another math function, so if we evaluate the power series with enough terms, it should approximate the value of that other function. It’s not quite possible to just choose any value for the function and expect it to work, however, so there isn’t much room to experiment with alternatives here. The tests only tend to check one or two values, but that should be enough. In the exercise file, I’ve noted what the expected result is for some of the series tests.

I will explain how that stream is generated, in case you are familiar with power series and are interested in how it is checking the streams. You can skip this if you don’t care, and just want to run the tests.

Recall that our streams represent the coefficients on terms the series. Each coefficient is multiplied by xn where n is the index of that term. So we need to find the sum of a given number of those terms, starting with just the sequence of coefficients.

The first thing to do is construct a stream of the powers of x for any given x. That can be expressed as a recursive stream starting with a constant term of 1, which just multiplies by x to get the next term. Doing termwise multiplication using mul-streams with the ‘power series’ stream (e.g. the coefficient stream) then produces a stream of the actual power series’ terms. Then, to evaluate it, we calculate a partial sum of the terms, hopefully choosing enough that our result is accurate.

Here are the procedures used:

(define (powers-of-x x)
  (cons-stream 1 (scale-stream (powers-of-x x) x))

(define (eval-at x ps)
  (mul-streams ps (powers-of-x x))

(define (accum-n-of-stream n s)
  (define (iter-accum i str acc)
    (if (<= i 0)
        (iter-accum (- i 1) (stream-cdr str) (+ (stream-car str) acc) )
  (iter-accum n s 0)    

The last function, accum-n-of-stream, calculates the sum of n terms, and thus gives us an approximation of the function represented by the series. The accuracy of the result is dependent on the number of terms selected, and this will vary for each power series as well. It’s also critical to realize that for a power series representation, there is an ‘interval of convergence’, which means that for some series, only certain values of x will yield useful results.

As said, it’s not strictly necessary to understand the math to check the results in the examples I supplied. The trig functions especially are useful here, since they produce ‘interesting’ series with multiple terms, and there are some trig identities that let us check our operations even without evaluating at a particular point. If you want to test more values, though, you should at minimum be familiar with the expected value for these functions, or know how to calculate them. Note that a large number of terms may be required to get a good value for some comparisons, which could take a fair amount of processing time. Indeed, I have run into memory errors just when evaluating 100 terms (as in the file), so it may be necessary to reduce the number of terms to get a result. As powerful as streams are, they can have a high cost in space or time complexity (necessitating optimization of the procedures that operate on them).

There are two library files that need to be loaded at the start of the file for this section. The first is the ‘streambasic’ file from the last section, which will still allow delay to be re-defined to allow memoization or not. The second is called ‘stream_352’ and includes the add, scale, and merge operations as well as an implementation of stream-map. You’re free to replace that one with your own from 3.5.1. The stream_352 file also includes the pre-defined streams for several of the exercises, and procedures for extracting and displaying just a partial list from a stream, since most of the ones used in this section will be infinite.



Exercises 3.5.2