CSE 1729:
Introduction to Principles of
Programming
Programming with Sequences
and Streams
Robert McCartney
Scheduling: the end approaches
There will be one more homework, due December 8th at 11:59 PM. Note the unusual day (Thursday), but the semester ends on December 9th.
The final homework will be posted Tuesday, so you will have slightly over a week to do it.
There will be the normal lab this week (November 29). The lab on December 6 will be primarily a practice session, as were the labs before the prelims.
Final exam: Wednesday, December 14, 6:00-8:00. Here.
Consider the following code:
(define (sum-odd-squares tree)
(cond ((null? tree) 0)
((and (null? (left tree))
(null? (right tree)))
(if (odd? (value tree)) (square (value tree)) 0))
(else (+ (sum-odd-squares (left tree))
(sum-odd-squares (right tree)))))
And the following code:
(define (even-fibs n)
(define (next k)
(if (> k n)
‘()
(let ((f (fib k)))
(if (even? f)
(next 0))
(cons f (next (+ k 1)))
(next (+ k 1))))))
Similar?
(define (sum-odd-squares tree)
(cond ((null? tree) 0)
((and (null? (left tree))
(null? (right tree)))
(if (odd? (value tree)) (square (value tree)) 0))
(else (+ (sum-odd-squares (left tree))
(sum-odd-squares (right tree)))))
(define (even-fibs n)
(define (next k)
(if (> k n)
‘()
(next 0))
(cons f (next (+ k 1)))
(next (+ k 1))))))
(let ((f (fib k)))
(if (even? f)
Similar?
(sum-odd-squares tree)
enumerates the values at the leaves of a tree; filters them, selecting the odd ones;
squares each of the selected ones; and accumulates the results using +, starting with 0.
(even-fibs n)
enumerates the integers from 0 to n;
computes the Fibonacci number for each integer;
filters them, selecting the even ones; and
accumulates the results using cons, starting with the empty list.
✤ ✤ ✤ ✤
✤ ✤ ✤ ✤
As “signal processing” sequence
enumerate: tree leaves
filter: odd?
map: square
accumulate: +, 0
enumerate: integers 0-n
map: fib
filter: even?
accumulate: cons, ()
Using lists for sequences :
(define (filter pred seq)
(cond ((null? seq) ‘())
((pred (car seq))
(cons (car seq)(filter pred (cdr seq))))
(else
(filter pred (cdr seq)))))
(define (accumulate op init sequence)
(cond ((null? sequence) init)
(else
(op (car sequence)
(accumulate op init (cdr sequence))))))
;; map is already defined in language
Using lists for sequences (ctd.) :
(define (enumerate-leaves tree)
(define (is-leaf?)
(and (null? (right tree))(null? (left tree))) (cond ((null? tree) ‘())
((is-leaf?)
(list (value tree)))
(else
(append (enumerate-leaves (left tree))
(enumerate-leaves (right tree))))))
(define (enumerate-integers a b)
(cond ((> a b)'())
(else
(cons a (enumerate-integers (+ a 1) b)))))
Using these :
(define (sum-odd-squares tree)
(accumulate +
0
(map square
(filter odd?
(enumerate-tree tree)))))
(define (even-fibs n)
(accumulate cons
‘()
(filter even?
(map fib
(enumerate-integers 0 n)))))
Where are we going with this?
We would like to write programs in the “signal processing” style without being inefficient
We would like to be able to effectively use very large (or even infinite) sequences.
We would like to use sequences of things to model changing values
Answer: Streams
✤
✤
✤
Streams
A stream is an abstract data type that supports: empty-stream?, cons-
stream, stream-car, and stream-cdr. You may imagine a stream as
representing a sequence of elements so that:
empty-stream? determines if the sequence is empty,
cons-stream has 2 parameters, and returns a stream whose first element is the value of the 1st parameter, and whose tail is the value of the 2nd parameter
stream-car returns the first element of the stream (leaving it at the front of the stream),
stream-cdr returns the remainder of the stream (after removing the first element).
✤ ✤
✤
✤
Streams
A stream is an abstract data type that supports: empty-stream?, cons-
stream, stream-car, and stream-cdr. You may imagine a stream as
representing a sequence of elements so that:
empty-stream? determines if the sequence is empty,
cons-stream has 2 parameters, and returns a stream whose first element is the value of the 1st parameter, and whose tail is the value of the 2nd parameter
stream-car returns the first element of the stream (leaving it at the front of the stream),
stream-cdr returns the remainder of the stream (after removing the first element).
HEY! null?, cons, car, and cdr do exactly this with a SCHEME list!
✤ ✤
✤
✤
Compare: non-stream and stream implementations
(define (sum-primes a b)
(define (iter count accum)
(cond ((> count b) accum)
((prime? count)
(iter a 0))
(iter (+ count 1) (+ count accum)))
(else (iter (+ count 1) accum))))
(define (sum-primes a b)
(accumulate +
0
(filter prime?
(enumerate-integers a b))))
> (sum-primes 1000 100000)
Consider: find nth prime
; given function:
(define (nth index sequence)
(if (= index 1)
(car sequence)
(nth (- index 1)(cdr sequence))))
enumerate: integers a-b
filter: prime?
nth: index
Compare efficiency
(define (nth-prime index a b)
(cond ((> a b)’undefined)
((prime? a)
(if (= index 1)
a
(nth-prime (- index 1)(+ a 1) b)))
(else
(nth-prime index (+ a 1) b))))
(define (nth-prime index a b)
(nth index
(filter prime? (enumerate-integers a b))))
>(nth-prime 3 1000 100000)
Compare efficiency
(define (nth-prime index a b)
(cond ((> a b)’undefined)
((prime? a)
(if (= index 1)
a
(nth-prime (- index 1)(+ a 1) b)))
(else
(nth-prime index (+ a 1) b))))
(define (nth-prime index a b)
(nth index
(filter prime? (enumerate-integers a b))))
>(nth-prime 3 1000 100000)
1019
Suppose I want the code to work over any number of primes?
(define (nth-prime index)
(define (nth-p-iter val index)
(cond ((prime? val)
(if (= index 1)
a
(nth-p-iter (- index 1)(+ a 1))))
(else
(nth-p-iter index (+ a 1)))))
(nth-p-iter 2 index))
(define (nth-prime index)
(nth index
(filter prime? (enumerate-integers 2 ???))))
How many integers should I enumerate?
Streams need to support
Signal-processing style of programming Efficiency through interleaving of computation Large (potentially infinite) sequences.
Answer: delayed evaluation
Streams will work like lists, but they only evaluate their tails as required. Will use different functions: cons-stream, stream-car, and stream-cdr, analogous to cons, car, and cdr for lists.
✤ ✤ ✤
Stream operations
(cons-stream a b) returns a stream whose first element is
a, and whose tail (when evaluated) is b. Generally b will
evaluate to a stream.
b is not evaluated when (cons-stream a b) is evaluated.
(stream-car str) returns the first element of stream str (stream-cdr str) evaluates the tail of str and returns it.
We use the empty list ‘() to represent the empty stream, so we can use null? for empty-stream?
Ok, let’s try these out
(define (enumerate-integers a b)
(if (> a b)
‘()
(cons-stream a (enumerate-integers (+ a 1) b))))
> (define test (enumerate-integers 1 10))
> (stream-car test)
1> (stream-car (stream-cdr test))
2> test
(1 . #
(2 . #
Ok, let’s try these out (ctd.)
(define (stream-nth index stream)
(if (= index 1)
(stream-car stream)
(stream-nth (- index 1)(stream-cdr stream))))
> (stream-nth 1 test)
1
> (stream-nth 10 test)
10
> (stream-nth 11 test)
X X mcar: contract violation
expected: mpair?
given: ()
Hmm, let’s try something wild
(define (enumerate-integers-from a)
(cons-stream a (enumerate-integers-from (+ a 1))))
> (define test2 (enumerate-integers-from 1))
> (stream-car test2)
1
> (stream-car (stream-cdr test2))
2
> test2
(1 . #
> (cdr test2)
(2 . #
Whoa! How could this work?
(define (enumerate-integers-from a)
(cons-stream a (enumerate-integers-from (+ a 1))))
;; as opposed to
(define (enumerate-integers-from a)
(cons a (enumerate-integers-from (+ a 1))))
;; ?
Whoa! How could this work?
delay and force:
(delay form) packages form (without evaluation) so it can be evaluated
later
(force dform) takes a delayed form and evaluates it.
possible implementation:
(delay form) could be syntactic shorthand for (lambda () form)
in which case force could be implemented as
(define (force form)
(form))
Whoa! How could this work?
Given these:
(cons-stream a b) is syntactically equivalent to
(cons a (delay b))
(define (stream-car str)(car str))
(define (stream-cdr str)(force (cdr str))
However:
cons-stream cannot be a function delay cannot be a function
Code that works for any n?
(define (stream-nth index stream)
(if (= index 1)
(stream-car sequence)
(stream-nth (- index 1)(stream-cdr sequence))))
(define (nth-prime n)
(stream-nth n
(stream-filter prime?
(enumerate-integers-from 2))))
enumerate: integers from 2
filter: prime?
nth: n
Practical considerations
delay and force are defined in R5RS
We will supply definitions for cons-stream, stream- car, and stream-cdr that you can use (although the definitions for stream-car and stream-cdr in these slides would work fine).
✤
✤