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 2.56 differentiation rule

Image
Exercise 2.56.    Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the  deriv  program and defining appropriate procedures  exponentiation? ,  base ,  exponent , and  make-exponentiation . (You may use the symbol  **  to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. SOLUTION The code and tests are here .
Read more

SICP Exercise 1.28 (Miller-Rabin Test)

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st power modulo  n  using the  expmod  procedure. However, whenever we perform the squaring step in  expmod , we check to see if we have discovered a ``nontrivial square root of 1 modulo  n ,'' that is, a number not equal to 1 or  n  - 1 whose square is equal to 1 modulo  n . It is possible to prove that if such a nontrivial square root of 1 exists, then  n  is not prime. It is also possible to prove that if  n  is an odd number that is not prime, then, for at least half the numbers a < n , co
Read more

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 procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain. SOLUTION & DISCUSSION The streams based procedure 'solve' in this exercise exposed several issues in my metacircular evaluator implementation. I discovered that streams are not at all handled properly by my evaluator. Moreover, the &
Read more