sicpsgjd/3/4/jord/lecture.org

• Lecture 6A: Streams, Pt 1

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:

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

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

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

  (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

with those stream primitives,

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

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

  (define (flatten st-of-st)
    (accumulate append-streams
		the-empty-stream
		st-of-st))
  (define (flatmap func stream)
    (flatten (map func stream)))

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

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

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'

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

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"

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

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.