# SICP 6b

Streams II

## Table of Contents

## 1 How long is a piece of string?

On-demand computation is built into streams. Let's recap.

(define (nth-stream n s) (if (= n 0) (head s) (nth-stream (-1+ n) (tail s)))) (define (print-stream s) (cond ((empty-stream? s) "done") (else (print (head s)) (print-stream (tail s)))))

A stream can be infinitely long.

(define (integers-from n) (cons-stream n (integers-from (+1 n)))) (define integers (integers-from 1)) (define (no-seven x) (not (= (remainder x 7) 0))) (define ns (filter no-seven integers))

If something is there whenever you look, is it really there or not?

## 2 Sieve of Eratosthenes

We saw Hero of Alexandria's method for calculating square roots in lecture 1a. Eratosthenes was a fellow Alexandrian, who created a method for calculating primes.

(define (sieve s) (cons-stream (head s) (sieve (filter (lambda (x) (not (divisible? x (head s)))) (tail s))))) (define primes (sieve (integers-from 2)))

`sieve`

is an infinitely recursive filter.

## 3 All-in-one inclusive

Procedures may process streams in one go. Take a look at two handy procedures.

(define (add-streams s1 s2) (cond ((empty-stream? s1) s2) ((empty-stream? s2) s1) (else (cons-stream (+ (head s1) (head s2)) (add-streams (tail s1) (tail s2)))))) (define (scale-stream c s) (map-stream (lambda (x) (* x c)) s))

Using these two procedures, we can create procedures that process streams all at once.

(define integers (cons-stream 1 (add-stream integers ones)))

This looks an awful lot like a finite state accumulator. We can use the same trick for integrals.

(define (integral s initial-value dt) (define int (cons-stream initial-value (add-streams (scale-stream dt s) int))) int)

And also for Fibonacci numbers.

(define fibs (cons-stream 0 (cons-stream 1 (add-streams fibs (tail fibs)))))

## 4 Drawing hands

As we have recursive procedures, it's natural we have recursive data too. We can still run into recursive problems however.

(define y (integral dy 1 .001)) (define dy (map square y))

This doesn't work due to the recursive definition. There is a solution however.

(define (integral delayed-s initial-value dt) (define int (cons-stream initial-value (let ((s (force delayed-s))) (add-streams (scale-stream dt s) int)))) int)

Change the `integral`

procedure to expect integrand to be a delayed object.
Then just need one more minor change.

(define y (integral (delay dy) 1 0.001))

## 5 Normal-order evaluation

The divorce of time in programs from time in computers has yielded powerful
methods of decomposition, all of which have remained hidden within
streams until now. By taking full advantage of this new method, we have started
to pull out the innards of streams, explicitly calling `delay`

and `force`

.

Spaghetti code can be avoided, by changing the language so that all procedures
act like `cons-stream`

. In *normal-order evaluation* languages (in constrast to
*applicative-order evaluation* languages), every procedure has an implicit
delay around its arguments. Streams wouldn't be needed, since lists would be
streams already. Miranda, by David Turner from the University of
Kent, is a normal-order evaluation language.

There is, however, a price.

We're trying to think about programming as a way to specify processes. And if we give up too much time, our language becomes more elegant, but it becomes a little bit less expressive. There are certain distinctions that we can't draw.

One of the disadvantages is that we can't really express iteration.

(define (fact-iter a) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))

With normal-order evaluation, the above code would run nowhere near as
efficiently. The *dragging tail problem* is an issue people writing operating
systems are faced with.

A more striking issue is that normal-order evaluation and side effects just don't mix. It's impossible to model objects with local state and change, and at the same time conjure normal-order tricks of decoupling time.

(define x 0) (define (id n) (set! x n) n) (define (inc a) (1+ a)) (define y (inc (id 3))) x 0 y 4 x 3

The whole idea of putting in delays is that you throw away time. But when we talk about state and set and change, that's exactly what we do want control of.

A so-called purely functional language has no side effects. The price is losing assignment.

Let's take an example which would be naturally thought of in terms of object, and approach it with a functional frame of mind.

(define (make-deposit-account balance deposit-stream) (cons-stream balance (make-deposit-account (+ balance (head deposit-stream)) (tail deposit-stream))))

We don't know if we can do everything without assignment, but there seem to be places where functional programming breaks down. Where it starts hurting is with objects and sharing and two independent agents being the same.

Say if we were to extend the bank account so that two users shared the same
account. The streams could be merged. *Fair merge* would alternately switch
between each user, and if one is empty at any point, take from the other stream
twice. However notice that we can't even explain the situation without talking
about time.

Note: it may be that with fair merge, assignment can be effectively simulated.