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?

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.

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

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

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.