CSE 413 14au Assignment 4 - Streams and Things

Due: Online via the Catalyst Dropbox by 11 pm, Thursday, Oct. 23, 2014.

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

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

Part I. Written (paper) problems

Consider the following function definition
```
(define addn-to-list
  (lambda (n lst)
    (map (lambda (x) (+ n x)) lst)))
```
Also, 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.)

Now suppose we evaluate (addn-to-list 1 '(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.

(Election year special) 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 use 2 (small) mutually recursive 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.

Function 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 list. Hints: letrec, assoc, set!.

What to Hand In

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 when printed and does not exceed roughly 2 or 3 MB in size..

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.

Be sure that your name is included at the beginning of each file in a comment.