CSE 413 Au12 Assignment 4 - Streams and Things

Due: Online via the Catalyst Dropbox by 11 pm, Thursday, Oct. 25, 2012.

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. 19.

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 fibonacci3 in the lazy.rkt file from lecture. Suppose we evaluate the expression (fibonacci3 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 fibonacci3 is defined, the value (closure) it is bound to, and details of any other environments, closures, or data structures that are part of the fibonacci3 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.

(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

Turn in a file containing your answers to the questions from Part I, your hw4.rkt source file for part II, and a transcript file demonstrating the evaluation and results of your functions.

For the problems in part I please turn in a PDF file named hw1.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 3MB in size..

For part II, turn in the hw4.rkt source file and a text file named hw4demo.rkt containing the transcript of a Racket session demonstrating the results produced by your functions for suitable test cases. This should contain enough to show that your functions work, but no more than necessary to do that. Part of your grade will be determined by the quality of the test cases you use for this. (Don't worry if there are some minor typos in the transcript - just make a comment (;; line) to indicate anything we should ignore.) To save the transcript of the DrRacket interactions window to a file, use File > Save Other... > Save Interactions as Text... .