Homework 7: Streams & Testing Practice

Due: Friday, November 15 at 23:59
First Commit: Monday, November 11 at 23:59

This assignment is an intermezzo in the MiniScheme project. It consists of three parts. The first two ask you to practice working with streams. The second asks you to think about evaluating test suites for existing programs.

This homework should likely take you less time than a normal homework. I would encourage you to use the extra time towards working on Summary Problems, if you have not been already!

Your implementations will be in several files. The start of each file should be

#lang racket
; Your name(s) here.

Preliminaries

Click on the assignment link. The same partner making rules apply as normal. You can work in new teams for Homework 7, as this is not part of the MiniScheme Project.

Once you have accepted the assignment and created/joined a team, you can clone the repository on your computer by following the instructions and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style, as posted on Ed.

Submission

To submit your homework, you must commit and push to GitHub before the deadline.

Your repository should contain the following files

It may also a .gitignore file which tells Git to ignore files matching patterns in your working directory.

Any additional files you have added to your repository should be removed from the main branch. (You’re free to make other branches, if you desire, but make sure main contains the version of the code you want graded.)

Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.

Part 1. Basic Streams (20 points)

This homework gives you practice working with streams. As a reminder, streams are a data structure made possible by a new version of cons called stream-cons, which does not evaluate its arguments. The elements of the stream are not evaluated until the stream-first and stream-rest procedures force them.

Some reminders of the various stream procedures you can use are below (The Racket documentation has more).

#lang racket

(require racket/stream)

(define evens (stream-map (λ (n) (* 2 n)) ints))
(define ones (stream-cons 1 ones))
(define odds (stream-add ones evens))

(stream->list (stream-take ones 10))
(stream->list (stream-take odds 20))

For each exercise, write the procedure in hw7.rkt and a test suite (3 tests) and add the test suite to the all-tests test suite in tests.rkt. You might want to write the tests first. If you’ve forgotten how to write tests, consult your previous submissions.

You may wish to test your implementations on the infinite stream

(define test-stream
  (stream-cons 'x (stream-cons 'y (stream-cons 'z test-stream))))

You can use stream-take and stream->list to compare initial portions of the streams to lists.

  1. Write the function (stream-remove-all x s) which returns a stream with all occurrences of x removed from the stream s.
  2. Write the function (stream-replace x y s) which returns a stream with all occurrences of x in the stream s replaced with y.

Part 2. Filtering (20 points)

The file keyboard.rkt has the procedure (keyboard-stream) which returns a stream of whatever s-expressions you type. There is also an (output-stream s) procedure that takes a stream and outputs it one element at a time. Together, these set up a communication channel.

(output-stream (keyboard-stream))

This echoes whatever you type, and continues until you click on the eof box at the right. We will use this in the next set of exercises having to do with Grune’s Problem.

There is a famous problem due to Grune that is important in data communications. Consider a stream of characters, which we will model by typing single characters followed by enter/carriage return in response to (keyboard-stream)’s prompts. Most characters will be allowed to pass through unaltered. But if we ever receive two as in a row, then we will pass through just a single b and no a.

For these problems, your solutions should go in hw7.rkt. You should not modify keyboard.rkt.

  1. Write the filter grune-a-b that works as described above. For example, 
    > (output-stream (grune-a-b (keyboard-stream))) 
? a 
? b 
a 
b 
? c 
c 
? d 
d 
? a 
? a 
b 
? a 
? b 
a 
b 
? a 
? a 
b 
? <click eof>

    You can test using lists as your input stream and stream->list to convert the result to a list. For example, the above sequence of input can be tested by checking that

    (stream->list (grune-a-b '(a b c d a a a b a a)))

    returns

    '(a b c d b a b b)

    Similarly, the input stream '(a a a) should produce the output stream '(b a).

You are expected to write at least three meaningful tests for this function in tests.rkt.

  1. Now write a similar function, but abstract the a and b. Write a procedure (grune a b) which takes two arguments and produces a filter similar to grune-a-b but with the first argument taking the role of a and the second taking the role of b.

(grune 'x 'y) needs to return a procedure, similar to grune-a-b which works as a stream filter replacing two successive x by a single y. Here is a transcript of grune in action.

> (output-stream ((grune 'x 'y) (keyboard-stream))) 
   ? a 
   a 
   ? b 
   b 
   ? c 
   c 
   ? d 
   d 
   ? x 
   ? y 
   x 
   y 
   ? a 
   a 
   ? b 
   b 
   ? x 
   ? x 
   y 
   ? x 
   ? x 
   y 
   ? a 
   a 
   ? b 
   b 
   ? <click eof>

Notice that ((grune 'a 'b) s) has the same functionality as (grune-a-b s). Grune’s problem becomes interesting when we consider pipelining several Grune operations. If you did the last exercise correctly, you should be able to chain several grunes together.

> (output-stream ((grune 'c 'd) ((grune 'b 'c) ((grune 'a 'b) (keyboard-stream)))))
? a 
? b 
a 
? c 
b 
? d 
c 
d 
? e 
e 
? f 
f 
? g 
g 
? a
? a 
? a 
? a 
? a 
? a 
? a 
? a 
d 
? a 
? a 
? a 
? a 
? x 
c 
x 
? y 
y 
? z 
z 
? x 
x 
? y 
y 
? z 
z 
? <click eof>

You can write a better version of your grune-a-b implementation by writing

(define better-grune-a-b (grune 'a 'b))

You are expected to write at least three meaningful tests for this function in tests.rkt.

Part 3. Testing Test Suites (55 points)

Thus far this semester, you’ve been in the driver’s seat when it comes to writing and testing functions. This portion of the assignment asks you to read existing code and determine if it has been properly tested.

In suites.rkt there are two existing functions with existing test suites. Your job is to do the following, inline:

  1. Describe what the procedure is doing in English. Do this inline as a Racket comment.
  2. Look at the partially written test suite. Describe what situation/case each test is handling.
  3. Determine if there are situations/cases that are missing for the test suite. Add relevant tests and describe in English what situation/case they are handling. If no additional tests are needed, note that in a comment.

Assume that the implementations are correct, in other words they are operating as intended.

You will be graded on all three of the above components, including your explanations (although keep them concise!) and the quality of any additional tests.

Finishing up

Make sure you commit and push. Make sure your name is in all of the files you submit. Your friendly graders thank you!