Assignment No. 4 Solution

Note 1 This assignment is to be done individually




Note 2 You can discuss the assignment with others, but copying code is prohibited.




Due date: as indicated in Connex.




This assignment is worth 1% of your total course mark.




Submit electronically via Connex a single file with your solutions.




At the beginning of the class submit a paper copy of your program.




Objectives




After completing this assignment, you will have experience programming in Racket.




Introduction




You will write 10 Racket functions (not counting helper functions) and 1 Racket macro. Download hw4.rkt and hw4tests.rkt from the course website. Add to these files to complete your homework.




The first three problems are “warm-up” exercises. Subsequent problems dive into streams (4–8), mem-oization (10) and one macro (11). Go slowly and focus on using what you learned about thunks, streams, etc.

Some problems will require the use of a few standard-library functions that were are mentioned in the lectures. See the Racket documentation at http://docs.racket-lang.org/, particularly The Racket Guide, as necessary —looking up library functions, even in languages new to you, is an important skill. It is fine to discuss with others classmates what library functions are useful and how they work.




Your task, should you choose to accept it




Write a function sequence that takes 3 arguments low, high, and stride, all assumed to be num-bers. Further, assume stride is positive. sequence produces a list of numbers from low to high (including low and possibly high) separated by stride and in sorted order. Sample solution: 4 lines. Examples:



Call
Result
(sequence 3 11 2)
’(357911)
(sequence 3 8 3)
’(3 6)
(sequence 3 2 1)
’()







Write a function string-append-map that takes a list of strings xs and a string suffix and returns a list of strings. Each element of the output should be the corresponding element of the input appended with suffix (with no extra space between the element and suffix). Use Racket-library functions map and string-append. Sample solution: 2 lines.



1



Write a function list-nth-mod that takes a list xs and a number n. If the number is negative, terminate the computation with (error "list-nth-mod: negative number"). Else if the list is empty, terminate the computation with (error "list-nth-mod: empty list"). Else return the i-th element of the list where we count from zero and i is the remainder produced when dividing n by the list’s length. Library functions length, remainder, car, and list-tail are all useful —see the Racket documentation. Sample solution is 6 lines.



Write a function stream-for-n-steps that takes a stream s and a number n. It returns a list holding the first n values produced by s in order. Sample solution: 5 lines. Note: You can test your streams with this function instead of the graphics code.



5. . Write a stream funny-number-stream that is like the stream of natural numbers (i.e., 1, 2, 3, ...) except numbers divisible by 5 are negated (i.e., 1, 2, 3, 4, -5, 6, 7, 8, 9, -10, 11, ...). Remember a stream is a thunk that when called produces a pair. Here the car of the pair will be a number and the cdr will be another stream.




Write a stream cat-then-dog, where the elements of the stream alternate between the strings "cat.jpg" and "dog.jpg" (starting with "cat.jpg"). More specifically, cat-then-dog should be a thunk that when called produces a pair of "cat.jpg" and a thunk that when called produces a pair of "dog.jpg" and a thunk that when called... etc. Sample solution: 4 lines.



Write a function stream-add-zero that takes a stream s and returns another stream. If s would pro-duce v for its i-th element, then (stream-add-zero s) would produce the pair (0 . v) for its i-th element. Sample solution: 4 lines. Hint: Use a thunk that when called uses s and recursion. Note: One of the provided tests uses (stream-add-zero cat-then-dog) with place-repeatedly.



Write a function cycle-lists that takes two lists xs and ys and returns a stream. The lists may or may not be the same length, but assume they are both non-empty. The elements produced by the stream are pairs where the first part is from xs and the second part is from ys. The stream cycles forever through the lists. For example, if xs is ’(1 2 3) and ys is ’("a" "b"), then the stream
would produce, (1 . "a"), (2 . "b"), (3 . "a"), (1 . "b"), (2 . "a"), (3




"b"), (1 . "a"), (2 . "b"), etc.



Sample solution is 6 lines and is more complicated than the previous stream problems. Hints: Use one of the functions you wrote earlier. Use a recursive helper function that takes a number n and calls itself with (+ n 1) inside a thunk.




Write a function vector-assoc that takes a value v and a vector vec. It should behave like Racket’s assoc library function except:



it processes a vector (Racket’s name for an array) instead of a list and



it allows vector elements not to be pairs in which case it skips them.



Process the vector elements in order starting from 0. Use library functions vector-length, vector-ref, and equal?. Return #f if no vector element is a pair with a car field equal to v, else return the first pair with an equal car field. Sample solution is 9 lines, using one local recursive helper function.




Write a function cached-assoc that takes a list xs and a number n and returns a function that takes one argument v and returns the same thing that (assoc v xs) would return. However, you should



2



use an n-element cache of recent results to possibly make this function faster than just calling assoc (if xs is long and a few elements are returned often). The cache should be a vector of length n that is created by the call to cached-assoc and used-and-possibly-mutated each time the function returned by cached-assoc is called.




The cache starts empty (all elements #f). When the function returned by cached-assoc is called, it first checks the cache for the answer. If it is not there, it uses assoc and xs to get the answer and if the result is not #f (i.e., xs has a pair that matches), it adds the pair to the cache before returning (using vector-set!). The cache slots are used in a round-robin fashion: the first time a pair is added to the cache it is put in position 0, the next pair is put in position 1, etc. up to position n - 1 and then back to position 0 (replacing the pair already there), then position 1, etc.




Hints:




In addition to a variable for holding the vector whose contents you mutate with vector-set!, use a second variable to keep track of which cache slot will be replaced next. After modifying the cache, increment this variable (with set!) or set it back to 0 (as needed).




To test your cache, it can be useful to add print expressions so you know when you are using the cache and when you are not. But remove these print expressions before submitting your code.

Sample solution is 15 lines.




Define a macro that is used like (while-less e1 do e2) where e1 and e2 are expressions and while-less and do are syntax (keywords). The macro should do the following:



It evaluates e1 exactly once. It evaluates e2 at least once.

It keeps evaluating e2 until and only until the result is not a number less than the result of the evaluation of e1.




Assuming evaluation terminates, the result is #t.




Assume e1 and e2 produce numbers; your macro can do anything or fail mysteriously otherwise.




Hint: Define and use a recursive thunk that uses in its stopping condition the result of the first expres-sion. Sample solution is 9 lines. Example:




(define a 2)




(while-less 7 do (begin (set! a (+ a 1)) (print "x") a))




(while-less 7 do (begin (set! a (+ a 1)) (print "y") a))




Evaluating the second line will print "x" 5 times and change a to be 7. So evaluating the third line will print "x" 1 time and change a to be 8.




Provided Code




This time you are provided two test cases files. The first is hw4tests.rkt. This is the test file that will be used to grade your assignment. Run this file to test your code. Note that, because Racket is a dynamically typed language, all the functions you are expected to write have dummy defines. You will have to replace




3



these with their actual implementation. There are a total of 31 tests. It might be useful for you to inspect the tests.

The second test file is an hw4tests_2.rkt. The code at the top of this file uses a graphics library to provide a simple outlet for your streams. You need not understand this code (though it is not complicated) or even use it, but it may make the homework more fun. This is how you use it:




(open-window) returns a graphics window you can pass as the first argument to place-repeatedly.




(place-repeatedly window pause stream n) uses the first n values produced by stream. Each stream element must be a pair where the first value is an integer between 0 and 5 inclusive and the second value is a string that is the name of an image file (e.g., .jpg). The supplied files include some jpgs that will be used by this test. Make sure they are placed in the same directory as the Racket files. Every pause seconds (where pause is a floating-point number), the next stream value is retrieved, the corresponding image file is opened, and it is placed in the window using the number in the pair to choose its position in a 2x3 grid as follows:




0
1
2
3
4
5



Two of the provided tests in hw4graphicTest.rkt demonstrate how to use place-repeatedly. These tests are one-visual-test and visual-zero-only. You will have to run these functions by hand. The provided tests require you to complete several of the problems in the assignment.




Evaluation




Solutions should be:




Correct. We might use more tests than the ones provided. It will be run using SML/NJ.



In good style, including indentation and line breaks



As usual, submit your solution in a single file via connex. No need to upload your test files.



































































4