QUIZ #3 SOLUTIONS 1. stream-accumulate This was a hard problem, so don't feel too bad if you didn't get this. (Only one person had a correctly working solution. One person had a solution that worked but had DAVs, and two others had almost-working solutions.) (I should warn you, however, that much harder stream problems have been asked on exams in the past, usually involving some sick and twisted construction of interleaved streams.) On the other hand, if you did the partial-sums problem for HW11, this problem should have been easy. First, to define partial-sums and factorials in terms of stream-accumulate: (define (partial-sums s) (stream-accumulate + s)) (define factorials (stream-accumulate * naturals)) Now for stream-accumulate itself. (By the way, I meant the problem to be for infinite streams only, so none of the following solutions takes into account what happens when we run out of elements. Something to ponder: what changes would you have to make to handle finite cases?) (define (stream-accumulate op s) (define result (cons-stream (stream-car s) (stream-map op result (stream-cdr s) )) ) result) Note that the order of arguments to stream-map is important if op is not commutative. The method of staggering a stream against itself is generally a good way to generate streams in which each element depends on the previous element. Another way to define stream-accumulate: (define (stream-accumulate op s) (define (helper s sofar) (cons-stream sofar (helper (stream-cdr s) (op sofar (stream-car s)) ) )) (helper (stream-cdr s) (stream-car s)) ) Yet another way: (define (stream-cadr s) (stream-car (stream-cdr s)) ) (define (stream-cddr s) (stream-cdr (stream-cdr s)) ) (define (stream-accumulate op s) (cons-stream (stream-car s) (stream-accumulate op (cons-stream (op (stream-car s) (stream-cadr s)) (stream-cddr s) )) )) A couple of people came painfully close to the above version. There are lots of other ways to do this problem. An interesting attempt worth noting was: (define (almost-s-a op s) (cons-stream (stream-car s) (stream-map (lambda (item) (op (stream-car s) item)) (almost-s-a op (stream-cdr s)) ) )) This takes the element S1 and combines it with each of the subsequent elements S2, S3, .... It then takes S2 and combines it with each of the subsequent results, and so on. This isn't quite correct because it ultimately calculates elements such as S2 op (S1 op S3), which only have proper left-to-right folding behavior when op is both commutative and associative. (Going off on a tangent, for anyone curious about an operator that's associative but isn't commutative, an example is matrix multiplication. I can't think of a common operator that's commutative but not associative, however. A somewhat contrived example is: let a @ b denote a^2 + b^2. Then @ is commutative but not associative. If anyone can come up with something simpler, let me know.) ADVICE * Do NOT underestimate the power of mental type-checking! (Remember in high school physics and chemistry where you could solve a lot of calculation problems without thinking by applying "dimensional analysis"? This works remarkably well for programming too!) For example: op is an operator on the ELEMENTS of the input stream. Most people had the following mistake: (op (stream-car s) (stream-accumulate ...)) Since stream-accumulate returns a STREAM, this is a clear indication that something is seriously wrong. Once again, for each of your procedures, remember to think about what the return type is and what types of arguments the procedure takes. If you pass in the correct types and avoid type mismatches, you should be able to write code with MUCH fewer bugs. * Remember that using list/pair operations (car, cdr, ...) on streams is a data abstraction violation! (Once again, do mental type-checking!) * For stream questions, it's a good idea to check your answer by writing out the first few elements of your stream. * Elegant solutions are cool but brute force can be more straightforward. Don't be afraid to use helper procedures. (For example, for stream-accumulate, we could write a procedure (s-a-helper op stream n) that accumulates the first n elements of stream using op. This is certainly not an ideal solution, but if you're cramped for time, an ugly way that works is better than nothing.) * Be careful when using iterative processes on streams! Remember that iterative and recursive processes typically produce results in opposite orders. For finite streams, resulting streams may be in backwards order; for infinite streams, your process may never terminate! 2. concurrency + mutation First, since the set-car! and set-cdr! aren't modifying the SAME location in memory, they act independently of each other. So if we represent foo as a pair (x . y), where x is the symbol a and y is the list (b c), then we have the following four permutations: (x . y) (x . x) (y . x) (y . y) The first case (x . y) is impossible because regardless of serialization, the set-car! and a set-cdr! have to mutate the original list. NOTE THAT THE ABOVE REASONING IS SPECIFIC TO THIS PROBLEM. You most likely will not be able to generalize other concurrency problems like this. PART I For the first part, the two processes are serialized and cannot be interleaved, so either the (set-car! (cdr foo)) expression starts and finishes before (set-cdr! foo (car foo)) or vice-versa. Here's our original list: foo -->XX-->XX-->X/ | | | V V V a b c Now, if (set-car! foo (cdr foo)) occurs first, we then get: ____ | | | V foo -->XX-->XX-->X/ | | V V b c The subsequent (set-cdr! foo (car foo)) then has no effect. Now, if the (set-cdr! ...) occurs first, we then get: foo -->XX || VV a The subsequent (set-car! ...) has no effect. PART II For the first second part, the two processes use different serializers and thus can be interleaved. Let P1 be the (set-car! ...) process and P2 be the (set-cdr! ...) process. So in addition to the possibilities in Part I, we can have: P1 computes (cdr foo) P2 computes (car foo) P1 sets the car of foo P2 sets the cdr of foo or P1 computes (cdr foo) P2 computes (car foo) P2 sets the cdr of foo P1 sets the car of foo or P2 computes (car foo) P1 computes (cdr foo) P2 sets the cdr of foo P1 sets the car of foo or P2 computes (car foo) P1 computes (cdr foo) P1 sets the car of foo P2 sets the cdr of foo (For simplicity, I skipped the steps about accessing the variable foo. Since that never changes, neglecting it doesn't affect anything.) However you interleave the processes, they all produce the same result, because the two computation steps are independent of each other, and the two mutation steps are independent of each other. ____ | | | V foo -->XX XX-->X/ | | | V V V a b c ADVICE * ONLY CONS CREATES NEW PAIRS. * Don't forget your initial pointers! Now that we've learned about mutation, it should be clear why they're necessary. Consider a pair structure that contains cycles: How do we know where to begin? * A few people had S1 and S2 pointing to their boxes. S1 and S2 are serializers, NOT lists. S1 and S2 therefore point to PROCEDURES. (You didn't need to show them in the diagrams anyway.) * ONLY CONS CREATES NEW PAIRS. * You cannot point to individual boxes within pairs. See the week 4 lecture notes. * Remember that car and cdr return the things they're pointing TO. This means that (set-cdr! foo (car foo)) first finds what (car foo) points to and then sets foo's cdr to point to the result. * When dealing with mutation, it's much better to draw the box-and-pointer diagrams BEFORE trying to figure out what the interpreter would print. * Did I mention that only cons creates new pairs? * For concurrency problems, it might be beneficial to write out the steps. This may make it easier find the possible rearrangements.