Need help to understand some of the SICP streams examples

Question

I'm trying to understand how this function works.

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
            (lambda (x)
              (not (divisible? x (stream-car stream))))
            (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

Simply, I use a stream that generates all the integers starting from 2 and, according to the book, it filters the rest of the stream that is not divisible by current element for each new element. How can this filter all the integers that are not divisible by current element without actually reading all the integers?

Answer 1

The definitions

(define (sieve stream)
  (cons-stream (stream-car stream)
   (sieve 
     (stream-filter (lambda (x) (not (divisible? x (stream-car stream))))
       (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

mean that

primes 
= 
  (sieve
    (integers-starting-from 2))
=
  (cons-stream 2
    (sieve 
      (stream-filter (lambda (x) (not (divisible? x 2)))
        (integers-starting-from 3))))
=
  (cons-stream 2
    (cons-stream 3
      (sieve 
        (stream-filter (lambda (x) (not (divisible? x 3)))
          (stream-filter (lambda (x) (not (divisible? x 2)))
            (integers-starting-from 4))))))
=
  (cons-stream 2
    (cons-stream 3
      (sieve 
        (stream-filter (lambda (x) (not (divisible? x 3)))
          (stream-filter (lambda (x) (not (divisible? x 2)))
            (integers-starting-from 5))))))
=
  (cons-stream 2
    (cons-stream 3
      (cons-stream 5
        (sieve 
          (stream-filter (lambda (x) (not (divisible? x 5)))
            (stream-filter (lambda (x) (not (divisible? x 3)))
              (stream-filter (lambda (x) (not (divisible? x 2)))
                (integers-starting-from 6))))))))

and further

=
  ....
=
  (cons-stream 2
   (cons-stream 3
    (cons-stream 5
     (cons-stream 7
       (sieve 
         (stream-filter (lambda (x) (not (divisible? x 7)))
          (stream-filter (lambda (x) (not (divisible? x 5)))
           (stream-filter (lambda (x) (not (divisible? x 3)))
            (stream-filter (lambda (x) (not (divisible? x 2)))
             (integers-starting-from 9))))))))))
=
  ....
=
  (cons-stream 2
   (cons-stream 3
    (cons-stream 5
     (cons-stream 7
      (cons-stream 11
        (sieve 
          (stream-filter (lambda (x) (not (divisible? x 11)))
           (stream-filter (lambda (x) (not (divisible? x 7)))
            (stream-filter (lambda (x) (not (divisible? x 5)))
             (stream-filter (lambda (x) (not (divisible? x 3)))
              (stream-filter (lambda (x) (not (divisible? x 2)))
                (integers-starting-from 12))))))))))))
=
  ....

which, hopefully, should give you a clearer picture of what is going on here.

(NB: a follow up entry).