sicp-3-5-1-streams-are-delayed-lists

#lang racket

;; Racket has built-in streams, but this is the book implementation.  Use
;; define-syntax-rule to create the new special forms my-delay and cons-stream.

;; STREAMS

(define (memo-proc proc)
  (define already-run? false)
  (define result false)
  (lambda ()
    (cond [(not already-run?)
           (set! result (proc))
           (set! already-run? true)
           result]
          [else result])))

(define-syntax-rule (my-delay e) (memo-proc (lambda () e)))
(define (my-force delayed-object) (delayed-object))

(define (stream-car s) (car s))
(define (stream-cdr s) (my-force (cdr s)))

;; Use this definition of cons-stream for memoized streams.
(define-syntax-rule (cons-stream a b) (cons a (my-delay b)))

;; ;; Use this definition of cons-stream for un-memoized streams.
;; (define-syntax-rule (no-memo-delay e) (lambda () e))
;; (define-syntax-rule (cons-stream a b) (cons a (no-memo-delay b)))

(define the-empty-stream empty)
(define stream-null? empty?)

(define (my-stream-ref s n)
  (if (zero? n)
    (stream-car s)
    (my-stream-ref (stream-cdr s) (sub1 n))))

(define (my-stream-map proc s)
  (if (stream-null? s)
    the-empty-stream
    (cons-stream (proc (stream-car s))
                 (my-stream-map proc (stream-cdr s)))))

(define (my-stream-filter pred s)
  (cond [(stream-null? s) the-empty-stream]
        [(pred (stream-car s))
         (cons-stream (stream-car s)
                      (my-stream-filter pred (stream-cdr s)))]
        [else (my-stream-filter pred (stream-cdr s))]))

(define (my-stream-for-each proc s)
  (cond [(stream-null? s) 'done]
        [else (proc (stream-car s))
              (my-stream-for-each proc (stream-cdr s))]))

(define (display-stream s) (my-stream-for-each displayln s))

(define (stream-enumerate-interval low high)
  (if (> low high)
    the-empty-stream
    (cons-stream low
                 (stream-enumerate-interval (add1 low) high))))

;;;;;;;;;;
;; 3.50 ;;
;;;;;;;;;;

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

;; TEST

(define s1 (stream-enumerate-interval 1 5))
(define s2 (stream-enumerate-interval 11 15))
(define t (my-generalized-stream-map + s1 s2))
(my-stream-ref t 3)
;; 18
(display-stream t)
;; 12
;; 14
;; 16
;; 18
;; 20
;; 'done

;;;;;;;;;;
;; 3.51 ;;
;;;;;;;;;;

(define (show x)
  (displayln x)
  x)

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

;; WITH MEMOIZATION

(my-stream-ref x 5)
;; 0
;; 1
;; 2
;; 3
;; 4
;; 5
;; 5

(my-stream-ref x 7)
;; 6
;; 7
;; 7

;; Suppose proc has a side-effect, like show does here.  How is this side-effect
;; expressed when we stream-map proc down a stream s?  What would be the
;; difference if we used un-memoized streams?

;; Let t be (my-stream-map proc s).  When t is evaluated, the stream-car is
;; evaluated, but evaluation of the stream-cdr is delayed.  The stream-car of t is
;; proc of the stream-car of s.  This application of proc will produce a
;; side-effect.  But since a stream is stored as a pair consisting of a value and
;; a delayed expression, the stream-car will never again produce its side-effect
;; because that computation is never repeated.  (In effect the definition of
;; stream automatically caches the stream-car.)  This is true for both memoized
;; and un-memoized streams.

;; For later stream elements, however, there is a difference.  With memoized
;; streams, later elements will only express their side-effect the first time they
;; are forced, simply because caching prevents the repetition of the computation
;; that produces the side-effect.  With un-memoized streams, however, the
;; side-effect will be repeated every time the later elements are forced.

;; For example, repeating the above with un-memoized streams:

;; ;; WITHOUT MEMOIZATION

;; (my-stream-ref x 5)
;; ;; 0
;; ;; 1
;; ;; 2
;; ;; 3
;; ;; 4
;; ;; 5
;; ;; 5

;; (my-stream-ref x 7)
;; ;; 1 ; notice there is no 0 this time
;; ;; 2
;; ;; 3
;; ;; 4
;; ;; 5
;; ;; 6
;; ;; 7
;; ;; 7

;;;;;;;;;;
;; 3.52 ;;
;;;;;;;;;;

;; WITH MEMOIZATION

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

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

(define y (my-stream-filter even? seq))
sum ; sum 2
;; 6

(define z (my-stream-filter (lambda (x) (zero? (remainder x 5))) seq))
sum ; sum 3
;; 10

(my-stream-ref y 7)
;; 136
sum ; sum 4
;; 136

(display-stream z)
;; 10
;; 15
;; 45
;; 55
;; 105
;; 120
;; 190
;; 210
;; 'done
sum ; sum 5
;; 210

;; How are we getting these sums?

;; seq is: 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210
;; y is: 6 10 28 36 66 78 120 136 190 210
;; z is: 10 15 45 55 105 120 190 210

;; Whenever a new element of seq is evaluated, accum has the side-effect of adding
;; its index to sum.

;; At sum 1, seq is evaluated.  So its stream-car is evaluated.  So accum is
;; applied to 1.  Hence sum = sum + 1 = 0 + 1 = 1.

;; At sum 2, y is evaluated.  So its stream-car is evaluated.  This means forcing
;; two more elements to get the first even element of seq.  So accum is applied to
;; 2 and 3.  Hence sum = sum + 2 + 3 = 1 + 2 + 3 = 6.

;; At sum 3, z is evaluated.  So its stream-car is evaluated.  This means forcing
;; another element from seq, the fourth element, in order to get the first element
;; divisible by 5.  So accum is applied to 4.  Hence sum = sum + 4 = 6 + 4 = 10.

;; At sum 4, (my-stream-ref y 7) evaluates the first eight elements of y, which
;; means evaluating the first 16 elements of seq (in order to get the first eight
;; even elements).  The first four of these sixteen elements have already been
;; forced, so accum gets applied to 5, 6, 7, up through 16.  Hence sum = sum + 5 +
;; 6 + 7 + ... + 16 = 10 + 5 + 6 + 7 + ... + 16 = 136.

;; At sum 5, all of the elements of z are evaluated, which means all twenty
;; elements of seq get evaluated.  The first sixteen of those have already been
;; forced.  So accum gets applied to 17, 18, 19, and 20.  Hence sum = sum + 17 +
;; 18 + 19 + 20 = 136 + 17 + 18 + 19 + 20 = 210.

;; How would this change for un-memoized streams?

;; With un-memoized streams, stream elements repeat their side-effect every
;; time they are evaluated;  except for the stream-car, which only ever expresses
;; its side-effect once, as discussed in 3.51.

;; Also note that seq is no longer deterministic, but its values will change
;; depending on how many times it has been invoked.  This is because invoking seq
;; calls accum, which increases sum, which in turn changes accum and seq.  This
;; means y and z will also change depending on how often seq has been invoked,
;; because they too depend on seq.  This complicates the answers we get below.

;; ;; WITHOUT MEMOIZATION

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

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

;; (define y (my-stream-filter even? seq))
;; sum
;; ;; 6

;; (define z (my-stream-filter (lambda (x) (zero? (remainder x 5))) seq))
;; sum
;; ;; 15

;; (my-stream-ref y 7)
;; ;; 162
;; sum
;; ;; 162

;; (display-stream z)
;; ;; 15
;; ;; 180
;; ;; 230
;; ;; 305
;; ;; 'done
;; sum
;; ;; 362