* Lecture 6A: Streams, Pt 1
https://youtu.be/JkGKLILLy0I
aside: good to see harry again -- feel like it's been a while


"last time, gerry really let the cat out of the bag" with

                   /A S S I G N M E N T/

                        /S T A T E/

                       /C H A N G E/

(F X) might have a side effect
(F X) again might have a different value

                   /T I M E/

                /I D E N T I T Y/

                     /S H A R I N G/

the environment model is a far cry from the substitution model.
we can no longer think about it like mathematics.
it's philosophically harder.

why did we get into this mess? to build modular systems.

we'd like to build in the computer systems that fall into pieces in a
way that mirrors reality.

the reason building systems like this is hard has nothing to do with
computers.

the real reason we have these problems is with the way we view
reality.

time is an illusion and nothing ever changes.

lets try some *stream processing*

a couple example procedures:

#+BEGIN_SRC scheme
  (define (sum-odd-squares tree)
    (if (leaf-node? tree)
	(if (odd? tree)
	    (square tree)
	    0)
	(+ (sum-odd-squares
	    (left-branch tree))
	   (sum-odd-squares
	    (right-branch tree)))))
#+END_SRC

#+BEGIN_SRC scheme
  (define (odd-fibs n)
    (define (next k)
      (if (> k n)
	  '()
	  (let ((f (fib k)))
	    (if (odd? f)
		(cons f (next (1+ k)))
		(next (1+ k))))))
    (next 1))
#+END_SRC

these two procedures look very different, but really they are rather
doing the same thing.

 enumerate the leaves  -->  filter odd? -->  map square --> accumulate
      of a tree                                             add from 0

 enumerate interval --> map fibbonacci --> filter odd? --> accumulate
      1 to n                                               cons from '()

these natural steps don't appear in the two procedures because we
don't have a good language for talking about them.

let's build an appropriate language.

 /S T R E A M S/

a stream is a data abstraction, like anything else.

: (cons-stream x y)
: (head s)
: (tail s)

    for any x y
: (head (cons-stream x y)) ;; x
: (tail (cons-stream x y)) ;; y

"the empty stream", like the empty list

#+BEGIN_SRC scheme
  (define (map-stream proc s)
    (if (empty-stream? s)
	the-empty-stream
	(cons-stream
	 (proc (head s))
	 (map-stream proc (tail s)))))
  (define (filter pred s)
    (cond
     ((empty-stream? s) the-empty-stream)
     ((pred (head s))
      (cons-stream (head s)
		   (filter pred
			   (tail s))))
     (else (filter pred (tail s)))))
  ;; etc as notated in the book
#+END_SRC

with those stream primitives,
#+BEGIN_SRC scheme
  (define (sum-odd-squares tree)
    (accumulate
     +
     0
     (map
      square
      (filter odd
	      (enumerate-tree tree)))))
  (define (odd-fibs n)
    (accumulate
     cons
     '()
     (filter
      odd
      (map fib (enum-interval 1 n)))))
#+END_SRC

we are establishing a CONVENTIONAL INTERFACE that allows us to glue
things together.

--> break

here are some more complicated examples

{{1 2 3 ...} {18 28 38 ...} ...}

with flatten, get contents of stream of streams

#+BEGIN_SRC scheme
  (define (flatten st-of-st)
    (accumulate append-streams
		the-empty-stream
		st-of-st))
  (define (flatmap func stream)
    (flatten (map func stream)))
#+END_SRC

GIVEN N, find all pairs of 0 < j < i ≤ n
   such that i + j is prime

eg for N=6:

 | i | j | i+j |
 |---+---+-----|
 | 2 | 1 |   3 |
 | 3 | 2 |   5 |
 | 4 | 1 |   5 |


#+BEGIN_SRC scheme
  (flatmap
   (lambda (i)
     (map
      (lambda (j) (list i j))
      (enum-interval 1 (-1+ i))))
   (enum-interval 1 n))

  (filter
   (lambda (p)
     (prime? (+ (car p) (cadr p))))
   (flatmap ...))

  (define (prime-sum-pairs n)
    (map
     (lambda (p)
       (list (car p)
	     (cadr p)
	     (+ (car p) (cadr p))))
     (filter ...)))
#+END_SRC

there is a lot of power in flatmaps of flatmaps of maps etc ...
this is how you can do nested-loop type shit

writing flatmaps of flatmaps ... is not fun, so we have the syntactic
sugar 'collect'

#+BEGIN_SRC scheme
  (define (prime-sum-pairs n)
    (collect
     (list i j (+ i j))
     ((i (enum-interval 1 n))
      (j (enum-interval 1 (-1+ i))))
     (prime? (+ i j)))
#+END_SRC

we can solve the 8 queens problem
: (safe? row col rest-of-positions) ;; is it safe to put a queen here?

the traditional way to solve this is with a method called backtracking

walk up and down the tree, but this is "too concerned with time"

#+BEGIN_SRC scheme
  (define (queens size)
    (define (fill-cols k)
      (if
       (= k 0)
       (singleton empty-board)
       (collect (adjoin-position try-row
				 k
				 rest-queens)
		((rest-queens (fill-cols (-1+ k)))
		 (try-row (enum-interval 1 size)))
		(safe? try-row k rest-queens)
		 )))
    (fill-cols size))
#+END_SRC

every time harry says "fill-cols" i hear "phil collins" lol

--> break

the weakness of "traditional" lookin programs (sans the streams) is
that they are "mixed up" -- the filtering and enumerating and
collecting is all intertwined.

this exact feature is also it's strength in efficiency.

we can have our cake and eat it too, by using these streams and giving
them the efficiency of traditional techniques. this power comes from
the fact that streams are not lists.

there's a lot of tuggin goin on lol

we need to implement on "on demand" data structure
(like a python generator)

: cons-stream
: head
: tail

: (cons-stream x y)
is an abbreviation for
: (cons x (delay y))
, a promise

: (head s) --> (car s)
: (tail s) --> (force (cdr s))
force calls in the promise

: (delay exp)
is an abbreviation for
: (λ () exp)

: (force p)
is just
: (p)

delay decouples the apparent order of events from the real order in
the machine

: (define (delay ex)
:   (memo-proc
:      (λ () ex)))

memo-proc saves previous computations

this great power comes from the lack of distinction between data and
procedures. we've written data structures that are rather like
procedures. that's what streams are.