126.001 SICPStreams – the lazy wayBeyond Scheme – designing language variants:• Streams – an alternative programming style3Streams – motivation• Imagine simulating the motion of a ball bouncing against a wall• Use state variables, clock, equations of motion to updateposition:velocity:Ball:position:elasticity:Wall:time:clock:4Streams – motivation • State of the simulation captured in instantaneous values of state variablesClock: 1 Ball: (x1 y1) Wall: e1Clock: 2 Ball: (x2 y2) Wall: e2Clock: 3 Ball: (x3 y3) Wall: e2Clock: 4 Ball: (x4 y4) Wall: e2Clock: 5 Ball: (x5 y5) Wall: e3…5Streams – motivation • Another view of the same informatonWall:e1e2e2e2e3…Clock:12345…Ball:(x1 y1)(x2 y2)(x3 y3)(x4 y4)(x5 y5)…6Streams – Basic Idea• Have each object output a continuous stream of information• State of the simulation captured in the history (or stream) of valuesxtyt8Remember our Lazy Language?• Normal (Lazy) Order Evaluation:• go ahead and apply operator with unevaluated argument subexpressions• evaluate a subexpression only when value is needed – to print– by primitive procedure (that is, primitive procedures are "strict" in their arguments)– on branching decisions–a few other cases• Memoization -- keep track of value after expression is evaluated• Compromise approach: give programmer control between normal and applicative order.29Variable Declarations: lazy and lazy-memo• Handle lazy and lazy-memo extensions in an upward-compatible fashion.;(lambda (a (b lazy) c (d lazy-memo)) ...)• "a", "c" are normal variables (evaluated before procedure application• "b" is lazy; it gets (re)-evaluated each time its value is actually needed• "d" is lazy-memo; it gets evaluated the first time its value is needed, and then that value is returned again any other time it is needed again.10The lazy way to streams• Or, users could implement a stream abstraction:(define (cons-stream x (y lazy-memo))(lambda (msg)(cond ((eq? msg 'stream-car) x)((eq? msg 'stream-cdr) y)(else (error "unknown stream msg" msg)))))(define (stream-car s) (s 'stream-car))(define (stream-cdr s) (s 'stream-cdr))• Use cons(define (cons-stream x (y lazy-memo))(cons x y))(define stream-car car)(define stream-cdr cdr)11Stream Object• A pair-like object, except the cdr part is lazy(not evaluated until needed):a thunk-memoavaluestream-carcons-streamstream-cdr•Example(define x (cons-stream 99 (/ 1 0)))(stream-car x) => 99(stream-cdr x) => error – divide by zeroBecause stream-cdris same as cdr, this is a primitive procedure application, hence forces evaluation12Decoupling computation from description• Can separate order of events in computer from apparent order of events in procedure description(list-ref(filter (lambda (x) (prime? x))(enumerate-interval 1 100000000))100)(define (stream-interval a b)(if (> a b)the-empty-stream(cons-stream a (stream-interval (+ a 1) b))))(stream-ref(stream-filter (lambda (x) (prime? x))(stream-interval 1 100000000))100)Creates 1M elementsCreates 100K elements13Stream-filter(define (stream-filter pred str)(if (pred (stream-car str))(cons-stream (stream-car str)(stream-filter pred(stream-cdr str)))(stream-filter pred(stream-cdr str))))15Decoupling Order of Evaluation(stream-ref(stream-filter (lambda (x) (prime? x))(stream-interval 2 100000000))100)Creates 1 element, plus a promiseCreates 1 element, plus a promise316Decoupling Order of Evaluation(stream-filter prime? (str-in 1 100000000))(st-in 2 10000000)1(stream-filter prime? )(stream-filter prime? ) (st-in 2 10000000)(stream-filter prime? )(st-in 3 10000000)2(stream-filter prime? (stream-cdr2From recursive call17One Possibility: Infinite Data Structures!• Some very interesting behavior(define ones (cons 1 ones))(define ones (cons-stream 1 ones))(stream-car (stream-cdr ones)) => 11onesThe infinite stream of 1's!ones: 1 1 1 1 1 1 ....(stream-ref ones 1) Î1(stream-ref ones 1000) Î1(stream-ref ones 10000000) Î 118Finite list procs turn into infinite stream procs(define (add-streams s1 s2)(cond ((empty-stream? s1) the-empty-stream)((empty-stream? s2) the-empty-stream)(else (cons-stream(+ (stream-car s1) (stream-car s2))(add-streams (stream-cdr s1) (stream-cdr s2))))))(define ints(cons-stream 1 (add-streams ones ints)))ones: 1 1 1 1 1 1 ....add-streams (str-cdr ones)(str-cdr ints)3 ...add-streams onesints2ints: 1 19XXXXXXXXXXXXXXXXXXXXXXXXXX7XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX2XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 3XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX510099989796959493929190898887868584838281807978777675747372716069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111098765432Finding all the primes20Using a sieve(define (sieve str)(cons-stream(stream-car str)(sieve (stream-filter (lambda (x) (not (divisible? x (stream-car str))))(stream-cdr str)))))(define primes(sieve (stream-cdr ints)))( 2 sieve (filter ints 2) )(2 3 sieve (filtersieve (filter ints 2)3))21Streams Programming• Signal processing:x[n] y[n]DelayG+• Streams model:add-streamsstream-scalexystream-cdrG422Integration as an example(define (integral integrand init dt)(define int(cons-streaminit(add-streams (stream-scale dt integrand)int)))int)(integral ones 0 2)=> 0 2 4 6 8Ones: 1 1 1 1 1Scale 2 2 2 2 2123An example: power seriesg(x) = g(0) + x g’(0) + x2/2 g’’(0) + x3/3! g’’’(0) + …For example:cos(x) = 1 – x2/2 + x4/24 - …sin(x) = x – x3/6 + x5/120 - …24An example: power seriesThink about this in stages, as a stream of values(define (powers x)(cons-stream 1(scale-stream x (powers x))))⇒1 x x2x3 …(define facts(cons-stream 1(mult-streams (stream-cdr ints) facts)))=> 1 2 6 24 …Think of (powers x) as giving all the powers of x starting at 1, then whole expression gives all the powers starting at xThink of facts as stream whose nth element is n!, then multiplying these two streams together gives a stream whose nth element is (n+1)!25An example: power series(define (series-approx coeffs)(lambda (x)(mult-streams(div-streams (powers x) (cons-stream 1 facts))coeffs)))g(x) = g(0) + x g’(0) + x2/2 g’’(0) + x3/3! g’’’(0) + …(define (stream-accum str)(cons-stream (stream-car str)(add-streams (stream-accum str)(stream-cdr str))))⇒g(0) ⇒g(0) + x g’(0)⇒g(0) + x g’(0) + x2/2 g’’(0)
View Full Document
Unlocking...