STUDENT NAME: 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsFall 2004Recitation 22Lazy Evaluation and StreamsLazy Evaluation and StreamsStreams1. (cons-s tream a b) - equivalent to (con s a (delay b))2. (stream -car c) - equivalent to (car c)3. (stream -cdr c) - equivalent to (force (cdr c))Simple Streams:Zeros: (0 0 0 0 0 0 ....(define zerosOnes: (1 1 1 1 1 1 ....(define onesNatural numbers (called ints): (1 2 3 4 5 6 ....(define intsStream operatorsWe’d like to be able to operate on streams to modify them and combine them with other streams.For example, to do element-wise addition or multiplication:(define (add-streams s1 s2) (map2-stream + s1 s2 ))(define (mul-streams s1 s2) (map2-stream * s1 s2 ))(define (div-streams s1 s2) (map2-stream / s1 s2 ))Write map2-stream:(define (map2-stream op s1 s2)STUDENT NAME: 2Another possible operation is multiplying every element of the stream by a constant factor:(define (scale-stream x s)Implement the stream of factorials, which goes (1 1 2 6 24 1 20 ...:(define factsPower SeriesWe can approximate functions by summing terms of an app ropriate power series. A power serieshas the form:Xanxn= a0+ a1x + a2x2+ a3x3+ · · ·By selecting appropriate an, the series converges to the value of a function. One particularly usefulfunction for which this is the case is exwhich has the following power series:ex= 0! +x1!+x22!+x33!+ · · ·Since power series involve an infinite summation, of which we might only care about the first coupleterms, they are an excellent problem to tackle with streams. The stream will encode the co efficientsan. For example, to represent the f unction f (x) = 3, we’d use a stream whose first element was 3,and the rest are zeros. The following two procedures come in handy:(define (powers x)(cons-stream x (scale-stream x (powers x))))(define (sum-series s x n)(define (sum-helper s sum n)(if (= n 0)sum(sum-helper (stream-cdr s) (+ sum (stream-car s)) (- n 1))))(sum-helper (mul-streams s (power s x)) 0 n))Write an expression that computes a stream to repr esent the power series that converges to f (x) =2x + 5:(define two-x-plus-fiveSTUDENT NAME: 3Write an expression that computes th e stream for ex:(define e-to-the-xTo compute e5using 20 terms, we’d call (sum-series e-to -the-x 5 20).Since the stream represents a function, we can write operations which work on functions and try toimplement them in terms of the coefficients of the series. One such operation is integration. Theintegral of an infinite polynomial is also an infinite polynomial, but the coefficients will be different.In particular, we’ll want our integration function to return a stream whose constant term (fir s telement) is missing, as it can’t actually compute it from the series.(define (integrate-series s)Write a new definition of exusing integrate -series (Hint: what is the integral of ex?)(define e-to-the-xGiven that we can build exthis way, implement sin and cos in a similar fashion:(define sine(define cosineBonus Round Problem: Another operation is function multiplication. This involves multiplyingtwo infinite polynomials, wh ich is not the same as mul-streams, as that only does elementwisemultiplication.(define (mul-series s1 s2)Then this should look interestingly simple:(add-streams (mul-ser ies sine sine)(mul-series cosine
View Full Document
Unlocking...