I am doing SICP ex 3.52. I get the correct responses to "stream-ref" and "display-stream" expressions, and also get the correct value for "sum" after each expression given in the exercise. However, it all works without using the "memo-proc" optimization provided on page 439 just before the listed exercise.
I am using Guile on Linux and the only other addition I made to the code was a syntax definition at the top of the code for "cons-stream" to include the "delay" form.
Perhaps I am misunderstanding something but I don't even see a point where "memo-proc" is called in the execution. Is there something that Guile has built-in that already does this optimization provided by "memo-proc", which according to SICP serves to implement "delay" as a special-purpose memoized procedure.
Here is the memoized procedure in SICP...
(define (memo-proc proc)
(let ((already-run? false) (result false))
(lambda ()
(if (not already-run?)
(begin (set! result (proc))
(set! already-run? true)
result)
result))))
Related code for convenience...
(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
(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 (stream-for-each proc s)
(if (stream-null? s)
'done
(begin (proc (stream-car s))
(stream-for-each proc (stream-cdr s)))))
(define (display-stream s)
(stream-for-each display-line s))
(define (display-line x) (newline) (display x))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define (stream-enumerate-interval low high)
(if (> low high)
the-empty-stream
(cons-stream
low
(stream-enumerate-interval (+ low 1) high))))
(define (stream-filter pred stream)
(cond ((stream-null? stream) the-empty-stream)
((pred (stream-car stream))
(cons-stream (stream-car stream)
(stream-filter
pred
(stream-cdr stream))))
(else (stream-filter pred (stream-cdr stream)))))
And the sequence of expressions for the exercise...
(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)
I expect the results listed below and I do get them.
(define sum 0)
;; sum => 0
(define (accum x)
(set! sum (+ x sum))
sum)
;; sum => 0
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
;; sum => 1
(define y (stream-filter even? seq))
;; sum => 6
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
seq))
;; sum => 10
(stream-ref y 7)
;; sum => 136
;; => 136
(display-stream z)
;; sum => 210
;; => (10 15 45 55 105 120 190 210)
However, I get these results without using "memo-proc". However, without the "memo-proc" optimization I would expect to get a "sum" of 15 upon:
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
seq))
;; sum => 10
because the "accum" function would be called additional times as part of the stream "seq" would need to be enumerated a second time. I am hoping someone could help me see what I am missing.
I'm doing the exercises with Racket (with SICP package) and the default implementation of streams is memoized (see: Do Racket streams memoize their elements?). I presume Guile is doing the same.
This may be why the question says ‘consider’ as there is no easy way to verify the non-memoized behaviour.
In Chapter 4 we implement the language ourselves, for ex 4.18 you can implement streams from scratch. Using those naïve streams I get the following result for this exercise:
Naive Streams
=============
sum after stream-ref: 162
sum after display-stream: 362
And after adding this section's implementation of memo-proc:
Naive Streams with Memo-Proc
============================
sum after stream-ref: 136
sum after display-stream: 210
Update: the value of 'sum' at the various times during execution is not only affected by memoization. It is also affected by whether you use SICP style 'odd' streams or more conventional 'even' streams and, if using a modern scheme, by whether you use the built in map and filter or the ones from the text.
+----------------+-------------+-------------+--------------+--------------+
| | SICP Scheme | SICP Scheme | Racket With | Racket With |
| | With | Without | Text's | Built in |
| sum after: | Memoization | Memoization | Map & Filter | Map & Filter |
+----------------+-------------+-------------+--------------+--------------+
| define accum | 0 | 0 | 0 | 0 |
+----------------+-------------+-------------+--------------+--------------+
| define seq | 1 | 1 | 0 | 0 |
+----------------+-------------+-------------+--------------+--------------+
| define y | 6 | 6 | 6 | 0 |
+----------------+-------------+-------------+--------------+--------------+
| define z | 10 | 15 | 10 | 0 |
+----------------+-------------+-------------+--------------+--------------+
| stream-ref | 136 | 162 | 136 | 136 |
+----------------+-------------+-------------+--------------+--------------+
| display-stream | 210 | 362 | 210 | 210 |
+----------------+-------------+-------------+--------------+--------------+
For more on 'odd' and 'even' streams see the Rationale of Scheme's SRFI 41.
I've added the code used above to GitHub.