SICP Exercise 3.52 sequence of stream expressions

Exercise 3.52.  Consider the sequence of expressions

(define sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(define y (stream-filter even? seq))
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
(stream-ref y 7)
(display-stream z)

What is the value of sum after each of the above expressions is evaluated? What is the printed response to evaluating the stream-ref and display-stream expressions? Would these responses differ if we had implemented (delay <exp>)simply as (lambda () <exp>) without using the optimization provided by memo-proc ? Explain.

SOLUTION

 The code and tests are here.

 ANALYSIS & EXPLANATION
Note 1:

stream-enumerate-interval produces the stream (Let’s call it s):
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
seq produces the stream:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210
y produces:
6, 10, 28, 36, 66, 78, 120, 136, 190, 210
z produces:
10, 15, 45, 55, 105, 120, 190, 210

Note 2: In the Racket streams implementation, when a stream is constructed the evaluations of both the car and the cdr are delayed until ‘stream-car’ and ‘stream-cdr’ are executed.

(define sum 0)

s: Does not Exist
seq: Does not Exist
y: Does not Exist
z: Does not Exist
sum is 0

(define (accum x)
  (set! sum (+ x sum))
sum)

s: Does not Exist
seq: Does not Exist
y: Does not Exist
z: Does not Exist
sum is 0

(define seq (stream-map accum (stream-enumerate-interval 1 20)))

s: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 (Stream just constructed)
seq: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210 (Stream just constructed)
y: Does not Exist
z: Does not Exist
sum is 0

(define y (stream-filter even? seq))

s: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
seq: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210
y: 6, 10, 28, 36, 66, 78, 120, 136, 190, 210 (Stream just constructed)
z: Does not Exist
sum is 6

(define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq))

s: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
seq: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210
y: 6, 10, 28, 36, 66, 78, 120, 136, 190, 210 (Stream exists but not accessed yet)
z: 10, 15, 45, 55, 105, 120, 190, 210 (Stream just constructed)
sum is 10

(stream-ref y 7)

s: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
seq: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210
y: 6, 10, 28, 36, 66, 78, 120, 136, 190, 210
z: 10, 15, 45, 55, 105, 120, 190, 210 (Stream exists but not accessed yet)
sum is 136
Printed Response is 136

(display-stream z)

s: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
seq: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210
y: 6, 10, 28, 36, 66, 78, 120, 136, 190, 210
z: 10, 15, 45, 55, 105, 120, 190, 210
sum is 210
Printed Response is:

10, 15, 45, 55, 105, 120, 190, 210

To the last question on whether the responses will differ if 'delay' were implemented without memoization, the answer is that the value of 'sum' will be higher since 'accum' will be applied multiple more times. Specifically, after y is defined, 'sum' is 6 but when z is defined, due to the absence of memoization 'accum' will be applied again on the elements 1, 2 and 3 from the enumerated interval. So z will be a  different stream from when memoization is used. Additionally 'seq' changes every time it is accessed. 

The explanation is also here.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this ...
Read more

SICP Exercise 3.11 make-account internal definitions with local state

Image
Exercise 3.11.    In section  3.2.3  we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section  3.1.1 : (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (define (dispatch m)     (cond...
Read more

SICP Exercise 3.13 make-cycle

Image
Exercise 3.13.    Consider the following  make-cycle  procedure, which uses the  last-pair  procedure defined in exercise  3.12 : (define (make-cycle x)   (set-cdr! (last-pair x) x)   x) Draw a box-and-pointer diagram that shows the structure  z  created by (define z (make-cycle (list 'a 'b 'c))) What happens if we try to compute  (last-pair z) ? SOLUTION The code is here: Exercise 3.13 make-cycle The box-and-pointer diagrams are here:
Read more