Difference between revisions of "Streams Assignment"
(19 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
[https://www.coursera.org/learn/programming-languages-part-b/supplement/YqQwn/notes-and-tips-for-section-5 Notes and Tips] credit to [https://vault.hanover.edu/~skiadas/ Charilaos Skiadas] | [https://www.coursera.org/learn/programming-languages-part-b/supplement/YqQwn/notes-and-tips-for-section-5 Notes and Tips] credit to [https://vault.hanover.edu/~skiadas/ Charilaos Skiadas] | ||
− | = | + | =Credit= |
{{GrossmanCredit}} | {{GrossmanCredit}} | ||
[https://www.coursera.org/learn/programming-languages-part-b/programming/VsOW3/homework-4-instructions Coursera Instructions] | [https://www.coursera.org/learn/programming-languages-part-b/programming/VsOW3/homework-4-instructions Coursera Instructions] | ||
− | |||
− | |||
− | |||
− | |||
=Provided Code for Graphical Output= | =Provided Code for Graphical Output= | ||
Line 38: | Line 34: | ||
complete several of the problems, of course. We hope these tests’ expected (visual) behavior is not difficult | complete several of the problems, of course. We hope these tests’ expected (visual) behavior is not difficult | ||
for you to figure out. | for you to figure out. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
=Helpful Guide / Warning= | =Helpful Guide / Warning= | ||
Line 55: | Line 46: | ||
=Code to Implement= | =Code to Implement= | ||
+ | {{RacketToImplement|uw4|sequence<br/>string-append-map<br/>list-nth-mod<br/>stream-for-n-steps<br/>funny-number-stream<br/>dan-then-dog<br/>stream-add-zero<br/>cycle-lists<br/>vector-assoc<br/>cached-assoc<br/>|uw4}} | ||
+ | |||
+ | <!-- MACRO: while-less --> | ||
==Exercises== | ==Exercises== | ||
===1) sequence=== | ===1) sequence=== | ||
− | Write a function sequence that takes 3 arguments low, high, and stride, all assumed to be numbers. | + | Write a function <code>sequence</code> that takes 3 arguments low, high, and stride, all assumed to be numbers. |
Further assume stride is positive. sequence produces a list of numbers from low to high (including | 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: | low and possibly high) separated by stride and in sorted order. Sample solution: 4 lines. Examples: | ||
{| class="wikitable" style="margin: auto;" | {| class="wikitable" style="margin: auto;" | ||
− | + | !Call | |
− | + | !Result | |
|- | |- | ||
|(sequence 3 11 2) | |(sequence 3 11 2) | ||
Line 76: | Line 70: | ||
===2) string-append-map=== | ===2) string-append-map=== | ||
− | Write a function string-append-map that takes a list of strings xs and a string suffix and returns a | + | Write a function <code>string-append-map</code> 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 | 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). You must use Racket-library | with suffix (with no extra space between the element and suffix). You must use Racket-library | ||
Line 82: | Line 76: | ||
===3) list-nth-mod=== | ===3) list-nth-mod=== | ||
− | + | Write a function <code>list-nth-mod</code> 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 | 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 ith element of the list where we count from zero and i is the remainder produced when dividing n by the | + | empty, terminate the computation with (error "list-nth-mod: empty list"). Else return the ith 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 |
− | list’s length. Library functions length, remainder, car, and list-tail are all useful – see the Racket | ||
documentation. Sample solution is 6 lines. | documentation. Sample solution is 6 lines. | ||
==Streams== | ==Streams== | ||
− | 4 | + | ===4) stream-for-n-steps=== |
+ | Write a function <code>stream-for-n-steps</code> that takes a stream s and a number n. It returns a list holding | ||
the first n values produced by s in order. Assume n is non-negative. Sample solution: 5 lines. Note: | the first n values produced by s in order. Assume n is non-negative. Sample solution: 5 lines. Note: | ||
You can test your streams with this function instead of the graphics code. | You can test your streams with this function instead of the graphics code. | ||
− | 5 | + | ===5) funny-number-stream=== |
+ | Write a stream <code>funny-number-stream</code> that is like the stream of natural numbers (i.e., 1, 2, 3, ...) | ||
except numbers divisble by 5 are negated (i.e., 1, 2, 3, 4, -5, 6, 7, 8, 9, -10, 11, ...). Remember a stream | except numbers divisble 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 | 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. | be another stream. | ||
− | 6 | + | ===6) dan-then-dog=== |
+ | Write a stream <code>dan-then-dog</code>, where the elements of the stream alternate between the strings "dan.jpg" | ||
and "dog.jpg" (starting with "dan.jpg"). More specifically, dan-then-dog should be a thunk that | and "dog.jpg" (starting with "dan.jpg"). More specifically, dan-then-dog should be a thunk that | ||
when called produces a pair of "dan.jpg" and a thunk that when called produces a pair of "dog.jpg" | when called produces a pair of "dan.jpg" and a thunk that when called produces a pair of "dog.jpg" | ||
and a thunk that when called... etc. Sample solution: 4 lines. | and a thunk that when called... etc. Sample solution: 4 lines. | ||
− | 7 | + | ===7) stream-add-zero=== |
− | produce v for its | + | Write a function <code>stream-add-zero</code> that takes a stream s and returns another stream. If s would |
− | + | produce v for its ith element, then (stream-add-zero s) would produce the pair (0 . v) for its | |
− | + | ith element. Sample solution: 4 lines. Hint: Use a thunk that when called uses s and recursion. | |
− | |||
Note: One of the provided tests in the file using graphics uses (stream-add-zero dan-then-dog) | Note: One of the provided tests in the file using graphics uses (stream-add-zero dan-then-dog) | ||
with place-repeatedly. | with place-repeatedly. | ||
− | 8 | + | ===8) cycle-lists=== |
+ | Write a function <code>cycle-lists</code> 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 | 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 | stream are pairs where the first part is from xs and the second part is from ys. The stream cycles | ||
Line 113: | Line 109: | ||
would produce, (1 . "a"), (2 . "b"), (3 . "a"), (1 . "b"), (2 . "a"), (3 . "b"), (1 . "a"), | would produce, (1 . "a"), (2 . "b"), (3 . "a"), (1 . "b"), (2 . "a"), (3 . "b"), (1 . "a"), | ||
(2 . "b"), etc. | (2 . "b"), etc. | ||
+ | |||
Sample solution is 6 lines and is more complicated than the previous stream problems. Hints: Use one | 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 | 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. | itself with (+ n 1) inside a thunk. | ||
− | + | ||
− | 9 | + | ==Memoization== |
+ | ===9) vector-assoc=== | ||
+ | Write a function <code>vector-assoc</code> that takes a value v and a vector vec. It should behave like Racket’s | ||
assoc library function except (1) it processes a vector (Racket’s name for an array) instead of a list, | assoc library function except (1) it processes a vector (Racket’s name for an array) instead of a list, | ||
(2) it allows vector elements not to be pairs in which case it skips them, and (3) it always takes exactly | (2) it allows vector elements not to be pairs in which case it skips them, and (3) it always takes exactly | ||
Line 124: | Line 123: | ||
equal to v, else return the first pair with an equal car field. Sample solution is 9 lines, using one local | equal to v, else return the first pair with an equal car field. Sample solution is 9 lines, using one local | ||
recursive helper function. | recursive helper function. | ||
− | 10 | + | |
+ | ===10) cached-assoc=== | ||
+ | Write a function <code>cached-assoc</code> 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 | one argument v and returns the same thing that (assoc v xs) would return. However, you should | ||
use an n-element cache of recent results to possibly make this function faster than just calling assoc | use an n-element cache of recent results to possibly make this function faster than just calling assoc | ||
Line 131: | Line 132: | ||
used-and-possibly-mutated each time the function returned by cached-assoc is called. Assume n is | used-and-possibly-mutated each time the function returned by cached-assoc is called. Assume n is | ||
positive. | positive. | ||
+ | |||
The cache starts empty (all elements #f). When the function returned by cached-assoc is called, it | 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 | first checks the cache for the answer. If it is not there, it uses assoc and xs to get the answer and if | ||
Line 137: | Line 139: | ||
to the cache it is put in position 0, the next pair is put in position 1, etc. up to position n − 1 and | 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. | then back to position 0 (replacing the pair already there), then position 1, etc. | ||
+ | |||
Hints: | 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. | |
− | use a second variable to keep track of which cache slot will be replaced next. After modifying the | + | * 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. |
− | cache, increment this variable (with set!) or set it back to 0. | + | * Sample solution is 15 lines. |
− | + | ||
− | cache and when you are not. But remove these print expressions before submitting your code. | + | ==Macro== |
− | + | ===11) while-less=== | |
− | 11 | + | (Challenge Problem:) 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: | 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. | |
− | 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. Sample solution is 9 lines. Example: | Hint: Define and use a recursive thunk. Sample solution is 9 lines. Example: | ||
− | (define a 2) | + | |
+ | <nowiki>(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 "x") a)) | ||
− | (while-less 7 do (begin (set! a (+ a 1)) (print "x") a)) | + | (while-less 7 do (begin (set! a (+ a 1)) (print "x") a))</nowiki> |
− | 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. | + | 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. |
+ | |||
+ | =Test= | ||
+ | Test your functions. The unit tests you have been provided are intentionally minimal. | ||
+ | |||
+ | {{RacketUnitTest|uw4test|uw4}} | ||
+ | |||
+ | The example tests in <code>hw4test.rkt</code> are grouped into a small test suite using Racket’s unit-testing framework. | ||
+ | |||
+ | You do not need to understand the details, but it is worthwhile to do so by reading [http://docs.racket-lang.org/rackunit/quick-start.html http://docs.racket-lang.org/rackunit/quick-start.html]. | ||
+ | |||
+ | =Pledge, Acknowledgments, Citations= | ||
+ | {{Pledge|lab-uw4-streams}} |
Latest revision as of 15:42, 10 February 2022
Contents
Notes and Tips
Notes and Tips credit to Charilaos Skiadas
Credit
All credit for this assignment goes to Prof. Grossman and his team at UW.
Provided Code for Graphical Output
The code at the top of hw4combined_tests_with_graphics.rkt
uses a graphics library to provide a simple,
entertaining (?) 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). (Sample image files that will work well are available on the course website. Put them in the same directory as your code.) Every pause seconds (where pause is a decimal, i.e., 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 demonstrate how to use place-repeatedly
. The provided tests require you to
complete several of the problems, of course. We hope these tests’ expected (visual) behavior is not difficult
for you to figure out.
Helpful Guide / Warning
The first three problems are “warm-up” exercises for Racket. Subsequent problems dive into streams (4–8) and memoization (10). Some short problems may be difficult. Go slowly and focus on using what you learned about thunks, streams, etc.
Some problems require that you use a few standard-library functions that were not used in lecture. 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 in the class what library functions are useful and how they work.
Code to Implement
file: | src/main/racket/uw4/uw4.rkt | ![]() |
functions: | sequence string-append-map list-nth-mod stream-for-n-steps funny-number-stream dan-then-dog stream-add-zero cycle-lists vector-assoc cached-assoc |
Exercises
1) sequence
Write a function sequence
that takes 3 arguments low, high, and stride, all assumed to be numbers.
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) | ’(3 5 7 9 11) |
(sequence 3 8 3) | ’(3 6) |
(sequence 3 2 1) | ’() |
2) string-append-map
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). You must use Racket-library
functions map and string-append. Sample solution: 2 lines.
3) list-nth-mod
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 ith 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.
Streams
4) stream-for-n-steps
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. Assume n is non-negative. Sample solution: 5 lines. Note:
You can test your streams with this function instead of the graphics code.
5) funny-number-stream
Write a stream funny-number-stream
that is like the stream of natural numbers (i.e., 1, 2, 3, ...)
except numbers divisble 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.
6) dan-then-dog
Write a stream dan-then-dog
, where the elements of the stream alternate between the strings "dan.jpg"
and "dog.jpg" (starting with "dan.jpg"). More specifically, dan-then-dog should be a thunk that
when called produces a pair of "dan.jpg" and a thunk that when called produces a pair of "dog.jpg"
and a thunk that when called... etc. Sample solution: 4 lines.
7) stream-add-zero
Write a function stream-add-zero
that takes a stream s and returns another stream. If s would
produce v for its ith element, then (stream-add-zero s) would produce the pair (0 . v) for its
ith element. Sample solution: 4 lines. Hint: Use a thunk that when called uses s and recursion.
Note: One of the provided tests in the file using graphics uses (stream-add-zero dan-then-dog)
with place-repeatedly.
8) cycle-lists
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.
Memoization
9) vector-assoc
Write a function vector-assoc
that takes a value v and a vector vec. It should behave like Racket’s
assoc library function except (1) it processes a vector (Racket’s name for an array) instead of a list,
(2) it allows vector elements not to be pairs in which case it skips them, and (3) it always takes exactly
two arguments. Process the vector elements in order starting from 0. You must 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.
10) cached-assoc
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
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 must be a Racket vector of length n
that is created by the call to cached-assoc (use Racket library function vector or make-vector) and
used-and-possibly-mutated each time the function returned by cached-assoc is called. Assume n is
positive.
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.
- 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.
Macro
11) while-less
(Challenge Problem:) 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. 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 "x") 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.
Test
Test your functions. The unit tests you have been provided are intentionally minimal.
file: | uw4test.rkt | ![]() |
source folder: | src/test/racket/uw4 |
note: ensure that you have removed all printing to receive credit for any assignment.
The example tests in hw4test.rkt
are grouped into a small test suite using Racket’s unit-testing framework.
You do not need to understand the details, but it is worthwhile to do so by reading http://docs.racket-lang.org/rackunit/quick-start.html.
Pledge, Acknowledgments, Citations
file: | lab-uw4-streams-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge