SICP Goodness - Stream (4)

More exercise

5 minute read

Do you think Computer Science equals building websites and mobile apps?

Are you feeling that you are doing repetitive and not so intelligent work?

Are you feeling a bit sick about reading manuals and copy-pasting code and keep poking around until it works all day long?

Do you want to understand the soul of Computer Science?

If yes, read SICP!!!

Let’s do one more exercise.

Exercise 3.51: In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it: 

(define (show x)
  (display-line x)
  x)

What does the interpreter print in response to evaluating each expression in the following sequence? 

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

This is easy, let’s just type the code into REPL and see what happens.

1 ]=> (define x (stream-map show (stream-enumerate-interval 0 10)))
0
;Value: x

1 ]=> (stream-ref x 5)
12345
;Value: 5

1 ]=> (stream-ref x 7)
67
;Value: 7

Done. But I want to follow the execution step by step and see exactly what is happening. So let’s do it.

Starting with the first line of code:

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

Here is what happens by typing in that line of code:

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

; First stream-enumerate-interval gets evaluated
(define x (stream-map 
            show 
            (cons-stream 
              0 
              (stream-enumerate-interval 1 10))))

; Expand cons-stream since it is a macro
(define x (stream-map 
            show 
            (cons 
              0 
              (delay (stream-enumerate-interval 1 10)))))

; Expand delay since it is a macro
(define x (stream-map 
            show 
            (cons 
              0 
              (memo-proc (lambda () (stream-enumerate-interval 1 10))))))

; We should expand memo-proc here but since it is rather long, expand it in your mind please
; Expand stream-map
(define x (cons-stream 
            (show 0) 
            (stream-map 
              show 
              (stream-cdr 
                (cons 
                  0 
                  (memo-proc (lambda () (stream-enumerate-interval 1 10))))))))

; Expand cons-stream since it is macro
(define x (cons 
            (show 0) 
            (delay (stream-map 
                     show 
                     (stream-cdr (cons 
                                   0 
                                   (memo-proc (lambda () (stream-enumerate-interval 1 10)))))))))

; Expand delay
(define x (cons
            (show 0) 
            (memo-proc (lambda () 
                         (stream-map 
                           show 
                           (stream-cdr (cons 
                                         0 
                                         (memo-proc (lambda () (stream-enumerate-interval 1 10))))))))))
; print 0 here
(define x (cons
            0
            (memo-proc (lambda () 
                         (stream-map 
                           show 
                           (stream-cdr (cons 
                                         0 
                                         (memo-proc (lambda () (stream-enumerate-interval 1 10))))))))))

Now the second line

(stream-ref x 5)

; Put in x
(stream-ref (cons
              0
              (memo-proc (lambda () 
                           (stream-map 
                             show 
                             (stream-cdr (cons 
                                           0 
                                           (memo-proc (lambda () (stream-enumerate-interval 1 10)))))))))
            5)

; Expand stream-ref
(stream-ref (stream-cdr (cons
                          0
                          (memo-proc (lambda () 
                                       (stream-map 
                                         show 
                                         (stream-cdr (cons 
                                                       0 
                                                       (memo-proc (lambda () (stream-enumerate-interval 1 10))))))))))
            4)

; Expand stream-cdr and then force
(stream-ref ((memo-proc (lambda () 
                          (stream-map 
                            show 
                            (stream-cdr (cons 
                                          0 
                                          (memo-proc (lambda () (stream-enumerate-interval 1 10)))))))))
            4)

; Expand memo-proc
(stream-ref (stream-map 
              show 
              (stream-cdr (cons 
                            0 
                            (memo-proc (lambda () (stream-enumerate-interval 1 10))))))
            4)
            
; Expand stream-cdr
(stream-ref (stream-map 
              show 
              ((memo-proc (lambda () (stream-enumerate-interval 1 10)))))
            4)
            
; Expand memo-proc
(stream-ref (stream-map 
              show 
              (stream-enumerate-interval 1 10))
            4)
; Expand stream-enumerate-interval
(stream-ref (stream-map 
              show
              (cons-stream 1 (stream-enumerate-interval 2 10)))
            4)
            
; Expand cons-stream
(stream-ref (stream-map 
              show
              (cons 1 (memo-proc (lambda () (stream-enumerate-interval 2 10)))))
            4)

; Expand stream-map
(stream-ref (cons-stream 
              (show 1) 
              (stream-map 
                show 
                (stream-cdr (cons 1 (memo-proc (lambda () (stream-enumerate-interval 2 10)))))))
            4)
            
; Expand cons-stream
(stream-ref (cons 
              (show 1)
              (memo-proc (lambda () (stream-map 
                                      show 
                                      (stream-cdr (cons 
                                                    1 
                                                    (memo-proc (lambda () (stream-enumerate-interval 2 10)))))))))
            4)
            
; Print 1 here
(stream-ref (cons 
              1
              (memo-proc (lambda () (stream-map 
                                      show 
                                      (stream-cdr (cons 
                                                    1 
                                                    (memo-proc (lambda () (stream-enumerate-interval 2 10)))))))))
            4)
; Expand stream-ref
(stream-ref (stream-cdr (cons 
                          1
                          (memo-proc (lambda () (stream-map 
                                                  show 
                                                  (stream-cdr (cons 
                                                                1 
                                                                (memo-proc (lambda () (stream-enumerate-interval 2 10))))))))))
            3)
            
; Expand stream-cdr
(stream-ref ((memo-proc (lambda () (stream-map 
                                     show 
                                     (stream-cdr (cons 
                                                   1 
                                                   (memo-proc (lambda () (stream-enumerate-interval 2 10)))))))))
            3)

; Execute memo-proc
(stream-ref (stream-map 
              show 
              (stream-cdr (cons 
                            1 
                            (memo-proc (lambda () (stream-enumerate-interval 2 10))))))
            3)
            
; Expand stream-cdr
(stream-ref (stream-map 
              show 
              ((memo-proc (lambda () (stream-enumerate-interval 2 10)))))
            3)
            
; Execute memo-proc
(stream-ref (stream-map 
              show 
              (stream-enumerate-interval 2 10))
            3)

; Expand stream-enumerate-interval
(stream-ref (stream-map 
              show 
              (cons-stream 2 (stream-enumerate-interval 3 10)))
            3)

; Expand cons-stream
(stream-ref (stream-map 
              show 
              (cons 2 (memo-proc (lambda () (stream-enumerate-interval 3 10)))))
            3)

; Expand stream-map
(stream-ref (cons-stream 
              (show 2) 
              (stream-map 
                show 
                (stream-cdr (cons 
                              2 
                              (memo-proc (lambda () (stream-enumerate-interval 3 10)))))))
            3)

; Expand cons-stream
(stream-ref (cons 
              (show 2) 
              (memo-proc (lambda () (stream-map 
                                      show 
                                      (stream-cdr (cons 
                                                    2 
                                                    (memo-proc (lambda () (stream-enumerate-interval 3 10)))))))))
            3)

; Print 2 here
(stream-ref (cons 
              2
              (memo-proc (lambda () (stream-map 
                                      show 
                                      (stream-cdr (cons 
                                                    2 
                                                    (memo-proc (lambda () (stream-enumerate-interval 3 10)))))))))
            3)

; Let's speed up

; Print 3 here
(stream-ref (cons 
              3
              (memo-proc (lambda () (stream-map 
                                      show 
                                      (stream-cdr (cons 
                                                    3 
                                                    (memo-proc (lambda () (stream-enumerate-interval 4 10)))))))))
            2)

; Print 4 here
(stream-ref (cons 
              4
              (memo-proc (lambda () (stream-map 
                                      show 
                                      (stream-cdr (cons 
                                                    4 
                                                    (memo-proc (lambda () (stream-enumerate-interval 5 10)))))))))
            1)
            
; Print 5 here
(stream-ref (cons 
              5
              (memo-proc (lambda () (stream-map 
                                      show 
                                      (stream-cdr (cons 
                                                    5
                                                    (memo-proc (lambda () (stream-enumerate-interval 6 10)))))))))
            0)

; Expand stream-ref
(stream-car (cons 
              5
              (memo-proc (lambda () (stream-map 
                                      show 
                                      (stream-cdr (cons 
                                                    5
                                                    (memo-proc (lambda () (stream-enumerate-interval 6 10)))))))))
            0)
            
; Expand stream-car
5

Phew! If you are still awake and reading here, maybe you should try to evaluate the third line of code. I have to go to sleep now so see you next time.

comments powered by Disqus