SICP - Streams Part 2

I don't know if it was the material or just lack of sleep but this lecture whipped my ass. Though I must admit seeing the "infinite streams" in action made me very curious, it might be time to drop the lisp from the last two lectures into the Scheme interpreter and play around a bit. [hour of frustration later] ... ok the fact that apparently the MIT/GNU Scheme interpreter doesn't work the way Edwin working in 1986 is causing me a huge amount of headache, so I'll revisit it another day...



Notes:

Streams Part 2

Elements of a stream are only calculated when we ask for them.

(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)))))
 
Because we only compute what we need, a string can be infinitely long and still be usable.

(DEFINE (INTERGERS-FROM N)
(CONS-STREAM
N
(INTERGERS-FROM (+ N 1))))

(DEFINE INTEGERS (INTEGERS-FROM 1))

(NTH-STREAM 20 INTEGERS)
=> 21 ;;;starts counting from zero

Sieve of Eratosthenes
Algorithm for finding prime numbers by successively eliminating all integers that are divisible by a prime. Starting with two, cross out all divisible by two, then all divisible by three, then five, etc.

(DEFINE (SIEVE S)
(CONS-STREAM
(HEAD S)
(SIEVE (FILTER
(LAMBDA (X)
(NOT
(DIVISIBLE? X (HEAD S))))
(TAIL S)))))

DEFINE PRIMES
(SIEVE (INTEGER-FROM 2)))

(NTH-STREAM 20 PRIMES)
=> 73

(PRINT-STREAM PRIMES)
=> 2 3 5 7 ...

All of the streams we have looked at have been CONS generators. We can also look at processing the stream all at once.

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

(DEFINE ONES (CONS-STREAM 1 ONES))
really is
(DEFINE ONES (CONS 1 (DELAY ONES))

(DEFINE INTEGERS 
(CONS-STREAM 1
(ADD-STREAMS INTEGERS ONES)))

Integers are a thing, whose first thing is one, and every other thing is incremented by one. We can define integers with integers because deep down is the DELAY which we don't worry about when we define it.

(DEFINE (INTEGRAL S INITIAL-VALUE DT)
(DEFINE INT
(CONS-STREAM
INITIAL-VALUE
(ADD-STREAM (SCALE-STREAM DT S)
 INT)))
INT)

We can use this stream model to define integration. "Internal definition syntax"

(DEFINE FIBS 
(CONS-STREAM 0
(CONS-STREAM 1
(ADD-STREAMS FIBS (TAIL FIBS)))))

We start off, starts with 0 and 1, the rest are gotten by adding the FIBS to the TAIL of the FIBS. Should come as now surprise that we have recursive data, since we have recursive procedures and there is no real difference between procedures and data.

Stream can get hung up. Example of an integration procedure for the differential equation y' = y^2, y0 = 1, dt = .001. We need DY to define Y, and we need Y to define DY, so we can't define this integral. However, if we use a DELAY, we can define Y first.

We can create a language that includes a DELAY in every procedure we use.  Since everything has an implicit delay, we wouldn't need any explicit delays. "Normal-Order Evaluation" is the term for this evaluation model. "Applicative-Order" is how we HAVE been doing it.

If everything had this delay, then CONS effectively becomes CONS-STREAM and lists all become streams. The price we pay is that although our language becomes more elegant, it may become less expressive. Factorial procedure example. We can't really express iteration, end up with recursion instead.

The major reason you don't make your language normal order is that side effects make it unworkable.

Talks about the "debate over functional language" - there are no side effects because there are no assignment or time.  A functional advocate might argue that giving up assignment is a small price to pay. Counterexample is the Cesaro pi example, which can be repackaged as a stream.

Bank account may have an internal state (balance). User sends a request and the account sends back a message which is  the balance. Stream view can do the same thing without any side effects. Bank account processes a stream of transaction requests, with deposits coming in and withdrawls going out.  

Unknown if we can do purely functional, but there are areas where functional programming breaks down, particularly with regard to sharing. 

Mullet strikes again...