Selected Solutions to Homework #8

Solution 8.1

The interpreter will print the following sequence:


==>  (define s (cons 5 (begin (display-line 7) 9)))
7
s
==>  (car s)
5
==>  (cdr s)
9
==>  (define s (cons-stream 5 (begin (display-line 7) 9)))
s
==>  (stream-car s)
5
==>  (stream-cdr s)
7
9

Notice how the difference appears in the only evaluation that has
side-efects, which is the display-line function.


Solution 8.2
If there is no memoization, the values returned are as follows.
==>  (define a 1)
a
==>  (define b (delay a))
b
==>  (define c (delay a))
c
==>  (define d (let ((a 1)) (delay a)))
d
==>  (set! a 2)
2
==>  (force b)
2
==>  (set! a 3)
3
==>  (force b)
3
==>  (force c)
3
==>  (force d)
1

If memoization is in effect, the only change is that the second 
call to (force b) will
give the result 2, because the body of the delayed expression is
not computed again.

Solution 8.3                                                 Page 2

The evaluation of (define x (stream-map show (enumerate-interval 0 10)))
will open a new environment for applying stream-map, binding the variable
proc to the procedure show and the variable stream  to (enumerate-interval
0 10). The application of stream-map will evaluate to:

(cons-stream (show (stream-car (enumerate-interval 0 10)))

    (stream-map show (stream-cdr (enumerate-interval 0 10))))

;;Then to

(cons (show (stream-car (enumerate-interval 0 10)))

    (delay (stream-map show (stream-cdr (enumerate-interval 0 10)))))

;;Applying show will result in evaluating (enumerate-interval 0 10)

(cons (show (stream-car (cons-stream 0 (enumerate-interval 1 10))))

    (delay (stream-map show (stream-cdr (enumerate-interval 0 10)))))

;;Which evaluates to

(cons (show (stream-car (cons 0 (delay (enumerate-interval 1 10)))))

    (delay (stream-map show (stream-cdr (enumerate-interval 0 10)))))

;;And to

(cons (show (car (cons 0 (delay (enumerate-interval 1 10)))))

    (delay (stream-map show (stream-cdr (enumerate-interval 0 10)))))


We can see that whenever a stream element is evaluated it will first be
printed out due to the application of the  show function. Thus the
interpreter will respond in the following manner (seperating the cases of
regular delay and memoized delay):


(define x (stream-map show (enumerate-interval 0 10)))

==> 0  ;;The result of (show 0)

==> x ;;The returned value of 'define'

(stream-ref x 5)

==> 1 ;;The result of (show 1)

==> 2 ;;The result of (show 2)

==> 3 ;;The result of (show 3)

==> 4 ;;The result of (show 4)

==> 5 ;;The result of (show 5)

==> 5 ;;The returned value


                                                             Page 3
(stream-ref x 7)

==> 1 ;;The result of (show 1)

==> 2 ;;The result of (show 2)

==> 3 ;;The result of (show 3)

==> 4 ;;The result of (show 4)

==> 5 ;;The result of (show 5)

==> 6 ;;The result of (show 6)

==> 7 ;;The result of (show 7)

==> 7 ;;The returned value

The memoized version (delay implemented using memo-proc) will be slighly
different:

(define x (stream-map show (enumerate-interval 0 10)))

==> 0  ;;The result of (show 0)

==> x ;;The returned value of 'define'

(stream-ref x 5)

==> 1 ;;The result of (show 1)

==> 2 ;;The result of (show 2)

==> 3 ;;The result of (show 3)

==> 4 ;;The result of (show 4)

==> 5 ;;The result of (show 5)

==> 5 ;;The returned value

(stream-ref x 7)

==> 6 ;;The result of (show 6), elements 1-5 are memoized

==> 7 ;;The result of (show 7)

==> 7 ;;The returned value


Solution 8.4
(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
        (apply proc (map stream-car argstreams))
        (apply stream-map 
               (cons proc 
                     (map stream-cdr argstreams))))))

(define (add-streams . argstreams)
  (apply stream-map (cons + argstreams)))

(define (mul-streams . argstreams)
  (apply stream-map (cons * argstreams)))

Solution 8.5


(define integers (cons-stream 1 (stream-map 1+ integers)))

(define odds (stream-filter odd? integers))

(define odds (cons-stream 1 (add-streams odds (scale-stream ones 2))))

(define factorials (cons-stream 1 (times-streams facts integers)))

Solution 8.6

There are no elements in the stream, but the system will get into an
infinite loop trying to evaluate the given expressions. The reason is
that although a computation of a whole stream is delayed, stream-filter
must find the head of the filtered stream so it has something to begin
with.  The problem is, that it will keep on looking for that single
item which will pass the filter. Unfortunately, it will keep on looking
forever.


Solution 8.7

(define (make-repeated func)
  (define identity (lambda (x) x))
  (cons-stream identity
               (stream-map (lambda (f) (lambda (x) (func (f x))))
                           (make-repeated func))))

Solution 8.8

(define (apply-streams stream-of-funcs stream-of-args)
  (cons-stream ((stream-car stream-of-funcs)
                (stream-car stream-of-args))
               (apply-streams (stream-cdr stream-of-funcs)
                              (stream-cdr stream-of-args))))


Solution 8.9

s1 = [ ID f2 f4 f8 ... ] where fi is a function that takes a function
                f and applies it i times . ID is the identity function
s2 = [ ID 1+ 2+ 3+ ... ] where i+ is a function that adds i to its
                 argument
Now obtain s3 by applied the repeating functions fk from s1 to the
                 functions of s2
s3 = [ ID 2+ 8+ 24+ ... ]  
so (apply-streams s3 ones) is [1 3 9 25 65 ... ]