Log in Page Discussion History Go to the site toolbox

Exercise 3.51

From BluWiki

Section 3.5 Exercises

Exercise 3.50

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)

Code for implementing the stream procedures (using macros) in DrScheme is available at this site from MIT's course. It's also necessary to include (require (lib "defmacro.ss")) to use macros.

Without memoization (delay)

When (stream-map proc stream) is evaluated, (proc (stream-car stream)) is evaluated, and a "promise" to evaluate (proc (stream-car <element>)) for each additional element of stream is saved. Note that no promise is saved if for the first element.

When (stream-ref stream n) is evaluated, (stream-cdr <element>) is evaluated for elements 0 through n-1, and then (stream-car <n'th element>) is evaluated and returned.

In the case of (stream-ref x 5), this means that (show i) is evaluated for i=1,2,3,4,5 (as we take stream-cdr of successive elements), and then the result of (show 5) (which is 5) is returned. The interpreter then prints out this return value.

(define x (stream-map show (stream-enumerate-interval 0 10)))
0
(stream-ref x 5)
1
2
3
4
55
(stream-ref x 7)
1
2
3
4
5
6
77
With memoization (memo-proc)

With memoization of the delayed procedure, the only thing that changes is that promises are not evaluated the second time the result is needed. In this case, (show n) only executes the first time it's return value is needed, and subsequent calls just return the cached value. Therefore, display-line is only used once for each number.

(define x (stream-map show (stream-enumerate-interval 0 10)))
0
(stream-ref x 5)
1
2
3
4
55
(stream-ref x 7)
6
77

Site Toolbox:

Personal tools
GNU Free Documentation License 1.2
This page was last modified on 19 October 2007, at 18:16.
Disclaimers - About BluWiki