SICP Series (3) - Stream Processing Application - Sieving Primes

I personally think stream-like data structures exist mainly to postpone the moment of real computation — data is only produced when truly needed. Incidentally, their existence also solves how computers describe ‘infinity’: as long as you can always fetch data from the data source, the source can be considered infinite.

Among stream processing applications, the algorithm that impressed me deeply is the prime sieve problem — defined recursively and implemented quite concisely.

I suggest understanding car and cdr before reading this.

Stream Basics

; streams are used like cons, car, cdr, but the implementation differs slightly
(define s (cons-stream 1 (cons-stream 2 nil)))
s
;Value: {1 ...} this stream starts with 1

; get the first datum
(car s)
(stream-car s)
;Value: 1

; get the second datum
(cdr s)
;Value: #[cell 13] what you get is not a stream but a function body

; when you really need the second datum, use force to get it, or directly use stream-cdr
(force (cdr s))
(stream-cdr s)
;Value: {2 ...} get the stream starting with 2

Stream Implementation

From the example above, in the stream implementation car and stream-car act identically; the difference between cdr and stream-cdr is one call to force — so we only need to define force properly.

; must be defined as a macro; interested readers can look here: https://stackoverflow.com/a/14641015/5563477
; in cons, our defined cdr is not b but a function; when called, this function returns b
(define-syntax my-cons-stream
  (syntax-rules ()
    ((my-cons-stream a b)
     (cons a (lambda () b)))))

; in force, after y is given, treat y as a function and call it
(define (my-force y)
  (y)
)
(define head car)
(define (tail s)
  (my-force (cdr s))
)
; head and tail are the stream-car and stream-cdr above

Some Stream Operations

The code below doesn’t consider that streams may end; real code should consider this problem.

The Stream of All Positive Integers

This stream has a property: each later item is 1 greater than the previous — so it can be defined recursively:

(define (all-num n)
  (my-cons-stream
    n
    (all-num (+ 1 n))
  )
)
(define integers (all-num 1))

integers
;Value: (1 . #[compound-procedure 12])

(tail integers)
;Value: (2 . #[compound-procedure 13])

Getting the Nth Element of a Stream

Just keep getting the stream’s next item until we obtain the element we want:

(define (my-stream-ref n s)
  (if (= n 1)
    (head s)
    (my-stream-ref (-1+ n) (tail s))
  )
)

; when we want the 5th element
(my-stream-ref 5 integers)
;Value: 5

Operating on This Stream to Get a New Stream

For example, operating on the positive-integer stream to double every element can be done like this:

(define (my-stream-map proc s)
  (my-cons-stream
    (proc (head s))
    (my-stream-map proc (tail s))
  )
)

(define zoom
  (my-stream-map (lambda(x) (* x 2)) integers)
)
; after zooming, the 5th number is 10
(my-stream-ref 5 zoom)
;Value: 10

Filtering the Data in This Stream to Get a New Stream

For example, operating on the positive-integer stream to take only the odd numbers can be done like this:

(define (my-filter-stream pred s)
  (cond
    ((pred (head s))
      (my-cons-stream
        (head s)
        (my-filter-stream pred (tail s))
      )
    )
    (else
      (my-filter-stream pred (tail s))
    )
  )
)


(define (divisible? x y)
  (= (remainder x y) 0)
)

(define odds
  (my-filter-stream
    (lambda (x) (not (divisible? x 2)))
    integers
  )
)

(my-stream-ref 5 odds)
;Value: 9 — the 5th odd number is 9

The Prime Sieve Algorithm

The following content comes from Wikipedia: https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95

Simply put: once we obtain a prime, filter out all subsequent integers divisible by it; the sequence we get is then a sequence of primes. Written in scheme:

(define (sieve s)
  (my-cons-stream
    (head s)
    (sieve ; filter out subsequent integers divisible by (head s), as a stream
      (my-filter-stream
        (lambda (x) (not (divisible? x (head s))))
        (tail s))
    )
  )
)

; note: primes start from 2, not 1
(define prime
  (sieve (all-num 2))
)

(my-stream-ref 9 prime)
; Value: 23 ; the 9th prime is 23

This recursive implementation can be said to perfectly match the definition.

Summary

In SICP, when introducing streams the teacher viewed them from an electrical-engineering perspective: circuit signals fluctuate and are continuous; passing through different rectifiers they can undergo many changes yet remain continuous — this is a kind of stream.

Although our data-structures course never covered it, a stream is actually an extended data structure, and also a kind of control logic. When you represent certain data as a stream, it means other parts of the program must also adapt to this change. It postpones a piece of code’s real execution time, allowing data to be produced only when truly used.

Stream processing is a powerful tool; programs can be implemented entirely stream-style, but this brings one problem: you may have no idea when a function will be called. Therefore I personally think such data structures suit the interaction points between several parts of a program or between several programs — like between producer and consumer, especially for multi-level consumers: submitting each completed task effectively prevents downstream consumers from starving.

Appendix: JS Implementation

// I won't fancily implement with lambda or dispatch — a two-element array is enough
// This code cannot run: all_num errors at definition time; cons-stream's definition needs macros,
// but JS has no macros..
// stream_cons = function(x, y) {
//   return [x, () =>y];
// }
// all_num = function(n) {
//   return stream_cons(n,all_num(n+1));
// }
// all_num(3);

let stream_cons, stream_car, stream_cdr, all_num, stream_ref, stream_map, stream_filter;

stream_cons = function(x, y) {
  if (typeof(y) === 'function'){
    return [x, y];
  } else {
    return [x, () =>y];
  }
}
stream_car = function(s) {
  return s[0];
}
stream_cdr = function(s) {
  return s[1]();
}

all_num = function(n) {
  return stream_cons(
    n,
    () => all_num(n+1) //NOTE: explicit delay needed here
  );
}

stream_ref = function(N, s) {
  if (N==1) return stream_car(s);
  return stream_ref(N-1, stream_cdr(s));
}

integers = all_num(1);
stream_ref(5, integers);
// 5

stream_map = function(proc, s) {
  return stream_cons(
    proc(stream_car(s)),
    () => stream_map(proc, stream_cdr(s)) // explicit delay needed here
  )
}
zoom = stream_map((x)=>x*2, integers);
stream_ref(5, zoom); // 10

stream_filter = function(pred, s) {
  if(pred(stream_car(s))) {
    return stream_cons(
      stream_car(s),
      () => stream_filter(pred, stream_cdr(s))
    );
  }
  return stream_filter(pred, stream_cdr(s));
}
odds = stream_filter((x) => x%2==1, integers);
stream_ref(7, odds); // 13


sieve = function(s) {
  return stream_cons(
    stream_car(s),
    () => sieve( // explicit delay
      stream_filter((x) => !(x % (stream_car(s))==0), stream_cdr(s))
    )
  );
}
prime = sieve(all_num(2));
stream_ref(9, prime);
// 23

for(var i=1; i<=9; i++) {
  console.log(stream_ref(i,prime));
}