# SICP 6b Streams II

## 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)
(nth-stream (-1+ n) (tail s))))

(define (print-stream s)
(cond ((empty-stream? s) "done")
(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
(sieve (filter
(lambda (x)
(not
(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
(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
```

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
int)))
int)
```

And also for Fibonacci numbers.

```(define fibs
(cons-stream 0
(cons-stream 1
```

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