Search code examples
streamschemeread-eval-print-loopsicpmit-scheme

SICP Streams (Scheme) - CDR into the implicit stream of ones


(define ones (cons-stream 1 ones))
(stream-cdr ones)

returns an infinite sequence of evaluated 1s - i.e. I get ;Value: #0={1 1 1 1 1 1 1 and so on... - not the symbolic {1 1 ...} I would expect ...

On the other end if I define ints and cdr into it,

(define ints (cons-stream 1 (stream-map + ones ints)))
(stream-cdr ints)

I obtain the expected {1 2 ...}

Can anyone explain me why? I expect the stream-map definition to be not too far from

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

which I defined in ex 3.50 and returns the same result ... but this seems to (via (map stream-cdr argstreams)) stream-cdr into ones, which I would expect to result in the infinite sequence I get above!

Even though, if I understand correctly, due to cons-stream being a macro the second part inside the stream-map will only be lazily evaluated, at some point while I cdr into the ints stream I would expect to have to cdr into ones as well.. which instead doesn't seem to be happening! :/ Any help in understanding this would be very much appreciated!

(I also didn't override any scheme symbol and I'm running everything in MIT Scheme - Release 11.2 on OS X.)


Solution

  • (define ones (cons-stream 1 ones))
    (stream-cdr ones)
    

    returns an infinite sequence of evaluated ones.

    No it does not. (stream-cdr ones) = (stream-cdr (cons-stream 1 ones)) = ones. It is just one ones, not the sequence of ones.

    And what is ones?

    Its stream-car is 1, and its stream-cdr is ones.

    Whose stream-car is 1, and stream-cdr is ones again.

    And so if you (stream-take n ones) (with an obvious implementation of stream-take) you will receive an n-long list of 1s, whatever the (non-negative) n is.

    In other words, repeated cdring into ones produces an unbounded sequence of 1s. Or symbolically, {1 1 1 ...} indeed.


    After your edit it becomes clear the question is about REPL behavior. What you're seeing most probably has to do with the difference between sharing and recalculation, just like in letrec with the true reuse (achieved through self-referring binding) vs. the Y combinator with the recalculation ((Y g) == g (Y g)).

    You probably can see the behavior you're expecting, with the re-calculating definition (define (onesF) (cons-stream 1 (onesF))).

    I only have Racket, where

    (define ones (cons-stream 1 ones))
    (define (onesF) (cons-stream 1 (onesF)))
    (define ints (cons-stream 1 (stream-map + ones ints)))
    
    (stream-cdr ones)
    (stream-cdr (onesF))
    (stream-cdr ints)
    

    prints

    (mcons 1 #<promise>)
    (mcons 1 #<promise>)
    (mcons 2 #<promise>)
    

    Furthermore, having defined

    (define (take n s)
      (if (<= n 1)
          (if (= n 1)    ; prevent an excessive `force`
              (list (stream-car s))
              '())
          (cons (stream-car s)
                (take (- n 1)
                      (stream-cdr s)))))
    

    we get

    > (display (take 5 ones))
    (1 1 1 1 1)
    > (display (take 5 (onesF)))
    (1 1 1 1 1)
    > (display (take 5 ints))
    (1 2 3 4 5)