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).

Answer 2

The trick is to think how stream-filter works. It is a function from streams to other streams, and this means that it does not actually need to filter the elements of the stream yet: instead it can return a stream which, as you ask for its elements, will filter them suitably.

In particular here is an implementation of stream-filter which I have called filter-stream:

(define (filter-stream test? stream)
  (cond
    ((stream-empty? stream)
     stream)
    ((test? (stream-car stream))
     (cons-stream (stream-car stream)
                  (filter-stream test? (stream-cdr stream))))
    (else
     (filter-stream predicate? (stream-cdr stream)))))

You can see how this works: it chunters down the stream it is given until it finds an element which passes the filter (or until it runs out of stream), at which point it uses cons-stream to construct a new stream consisting of the element that passed the predicate and the result of filtering all the other elements with the same predicate. But constructing that stream doesn't involve calling the predicate on all its elements: it just requires you to make a promise that, at the point someone asks you for an element of that stream, you will indeed filter the elements suitably to return the appropriate element.

In other words stream-filter is a function which takes a stream, which is a potentially infinite object and returns another stream, which again is potentially infinite. And it does this by simply promising to you that, at the point when you ask for some prefix of that infinite stream, it will then compute it for you, safe in the knowledge that you can never ask for all the elements of the stream.

sieve itself then repeatedly stacks these streams on top of each other: each time it finds a prime it constructs a stream which filters out multiples of that prime, from the stream it has been given which is already filtering out all multiples of primes lower than the prime it has just found.