CSE 1729 – Introduction to Principles of Programming November 29, 2016 Laboratory Assignment 12
Ob jectives
• Program in “signal-processing” style • Work with streams
• Write and use some stream tools
Activities
To effectively write stream code you will need the Scheme primitives to deal with the stream data type. Add the following code to the beginning of your Racket file. You should be working in R5RS Scheme.
(define-syntax cons-stream (syntax-rules ()
((cons-stream head tail) (cons head (delay tail)))))
(define (stream-car x) (car x))
(define (stream-cdr x) (force (cdr x)))
(define stream-null? null?)
(This code, plus code for tracer, a useful thing, is available in the attached file stream-utils.rkt).
1. To use streams in signal-processing-style code we need to define the primitives. Here are a few to implement that have analogues in list programming. All should be ordered consistent with their stream parameter, and all should take advantage of delayed evaluation by using cons-stream, stream-car, and stream-cdr instead of cons, car, and cdr. Note: some of these were shown on the slides, but be careful as the slides may have had small bugs and should be cleaned up.
(a) (stream-filter p str) returns a stream made up of all of the elements of str for which the function p returns true.
(b) (stream-map f str) returns a stream made up of the results of applying function f to each element of str. Unlike the map function in Scheme this will only work for functions of 1 argument.
(c) (stream-nth index str) returns the nth element of a stream, where an index of 1 corre- sponds to the first element.
1
2. To make your debugging easier, write the Scheme function (str-to-list str k) which returns a list containing the first k elements of stream str.
3. Using your functions above where appropriate, write the following stream functions:
- (a) (scale-stream k str)returnsastreammadeupoftheresultsofmultiplyingeachelement
of str by k.
- (b) (add-streams str1 str2) returns a stream made up by adding the elements of the two streams pairwise. E.g., if str1 has the elements (s1 s2 s3) and str2 has the elements (t1 t2 t3), then (add-streams str1 str2) would have the elements (s1+t1 s2+t2 s3+t3).
- (c) (mult-streams str1 str2) returns a stream made up by multiplying the elements of the two streams pairwise. E.g., if str1 has the elements (s1 s2 s3) and str2 has the elements (t1 t2 t3), then (mult-streams str1 str2) would have the elements (s1*t1 s2*t2 s3*t3).
- (d) (append-streams str1 str2) returns a stream containing all of the elements of str1 followed by all of the elements of str2. (What happens if str1 is an infinite stream?)
4. Using your functions above where appropriate, write the following stream functions:
- (a) (enumerate-integer-stream) returns a stream made up of the non-negative integers in ascending order. HINT–use a helper function.
- (b) (odd-factors-of k) returns a stream made up all odd non-negative numbers that are evenly divisible by k. Write two different solutions to this in terms of your stream functions in signal-processing style.
- (c) (partial-sums str) returns a stream containing the partial sums of str, that is, if s1, s2, s3,s4,… are the elements of str, the result stream contains s1, s1+s2, s1+s2+s3, s1+s2+s3+s4, …
- (d) (square-stream) returns a stream made up of the squares of the non-negative integers in ascending order.
Provide three different implementations of this using your code above. Which one is best (or worst), and why?
2