CSE 413 23sp Assignment 4 - Streams and Things

Due: Tuesday, April 25, by 11 p.m. You should use Gradescope to submit your assignment in two parts, corresponding to the written and programming parts below. Details are given in the "What to hand in" section at the bottom of the assignment.

These problems concern function closures, environments, delayed evaluation, and related topics like streams and memos. For the later material in particular you will want to look at the diagram, slides, sample code, and lecture notes linked to the lecture calendar.

Your code should include your name and other identifying information as comments.

Part I. Written (paper) problems

In class we worked out an example showing the environments when a function (add-n-to-list n lst) is executed. Here is a slightly different, curried version of that function:
```
(define caddn-to-list
  (lambda (n)
    (lambda (lst)
      (map (lambda (x) (+ n x)) lst))))
```
For this problem, assume that function map is defined with
```
(define map (lambda (f x) ...)
```
(i.e., map's parameters are a function named f and a list named x, and map is the library function that returns a new list where each element of the new list is the result of applying function f to the corresponding element of the original list.)

Now suppose we evaluate the following Racket code after defining caddn-to-list:
```
(define cadd10 (caddn-to-list 10))
(cadd10 '(2 3 4))
```
Draw a diagram showing the environments, bindings, and values (including closures) that exist at the moment when map's arguments have been evaluated and bound to parameters f and x, right before evaluating the body of map itself. In other words, you do not need to trace the execution of map, just show all of the environments and bindings that exist right as we start evaluating the body of map. Be sure your diagram shows clearly how environments are linked together, i.e., how the environment scopes nest.
This question concerns the memo function fib3 in the lazy.rkt file from lecture. Suppose we evaluate the expression (fib3 4). Draw a diagram showing the details of environments and closures after that evaluation has finished and produced its result. Your diagram should show the environment where fib3 is defined, the value (closure) it is bound to, and values and other details of any other environments, closures, or data structures that are part of the fib3 closure or are connected to it.

Part II. Streams & Things

Write and test Racket functions to solve the following problems. You should save your function definitions in a single file named hw4.rkt. You should use RackUnit for your tests (as in homework 3) and your tests should be saved in a single file named hw4-tests.rkt.

The beginning of your hw4.rkt file must contain comments giving your name and UW netid. Then, following the line containing #lang racket, your file must contain the following separate line, written exactly as shown:

(provide (all-defined-out))

(This provides an interface needed for the grading software, as well as for your RackUnit tests, to execute your code, but is not something you need to worry about as long as it is written correctly.)

You may not include any additional top-level (global) function or data definitions in your submitted hw4.rkt file. Of course you can freely use nested data or function definitions in your solutions if needed (i.e., let, let*, or letrec).

(U.S. Politics) Write a stream red-blue, where the elements of the stream alternate between the strings "red" and "blue". More specifically, (red-blue) should produce a pair containing "red" and a thunk that when called produces a pair containing "blue" and a thunk that when called... etc. Hint: you might want to use two (small) mutually recursive nested functions.
Write a function (take st n) whose arguments are a stream st (a pair with a value and a thunk that produces the next pair in the stream), and an integer n. Function take should return a list containing the first n values produced by stream st. For example, given the red-blue stream from the previous problem, the result of (take red-blue 4) should be the list ("red" "blue" "red" "blue"). If nats is the natural number stream from the lecture sample code, (take nats 5) should produce the list (1 2 3 4 5).
Recall from assignment 1 that the number of possible combinations (subsets) of k things taken from a set of n items is given by the formula C(n,k) = n! / (k! (n-k)!), where ! is the factorial function. Write a function (combm n k) to compute C(n,k) with the following change from assignment 1: combm should use memoization to store previously computed values and, if called again with the same arguments n and k, it should return the previously computed and stored value rather than computing the value again. Newly computed values and the associated arguments should be stored in the memo table for use in future calls.

As with other functions in this assignment, combm should be self-contained, not relying on any other global functions or data defined outside the function. In particular, you likely need a function to compute n!, but it should be defined in an appropriate inner scope so it is not visible outside of function combm.

For this problem keep things simple: use an association list, and don't worry about how many previously computed values are stored in the memo list. Hints: letrec, assoc, set!.

What to Hand In

Use Gradescope to submit your solutions to this assignment in two parts.

For the problems in part I please turn in a pdf file named hw4.pdf with your answers. This can be a scanned handwritten document if that is convenient, as long as it is clear and legible. Gradescope's web site has several instructional videos and help pages to outline the process, and this guide has specific information about scanning and uploading pdf files containing assignments.

Unreadable solutions cannot be graded--no blurry photos, poor contrast, or illegible handwriting, please.
Type-written solutions are encouraged but not required.
If possible, don't split the solution to a problem across a page break.

For part II, turn in the hw4.rkt and hw4-tests.rkt files containing your solutions and tests. Your tests should be sufficient to show that your functions work, but should be chosen well and not be overly redundant. Part of your grade will be determined by the quality of the test cases you submit.