Lab 3
1 Crucial DrRacket tips Part 3
DrRacket has a really nice documentation system. You should figure out how to use it.
Start up Firefox. You don’t absolutely have to do this first, but it makes everything else go faster.
Start DrRacket. *IN EITHER WINDOW*, type "map". Without the quotes. Hit the F1 key. Firefox should open, with a bunch of choices.
Click on the word "map" in the first entry. Voila! Documentation!
Use this all the time.
2 Exercises
Define the ArithC language described in the textbook in chapter 3. Please feel free to copy code from the texbook.
Develop the evaluation method described in the textbook. Call it interp. Write your test cases first!
Develop the method num-nums, that accepts an ArithC and returns a number indicating how many numbers it contains.
Develop a parser for the Arith language, consisting of a parse function and a desugar function. It should accept only well-formed s-expressions, and output ArithC’s. It should use the s-exp-match? form. It should handle subtraction and unary negation, as shown in the textbook. It should signal an error, by calling error, when the input is not well-formed. Here’s a grammar for the language:
Arith = num | {+ Arith Arith} | {* Arith Arith} | {- Arith Arith} | {- Arith} ... where id is an arbitrary symbol.
Use an auxiliary arithS definition and explicit desugaring, as described in the book.
Write lots of test cases. Use the test/exn form to test your error code.
This will be the basis for the parser that is a part of your remaining assignments, so it would behoove you to do a good job.
Develop the one-line top-interp, that accepts an s-expression and calls the parser and then the interp function.
Develop the doublemap function, that consumes a function and a list and returns the list formed by applying the function twice to each element of the original list. So, for instance, if the function passed in multiplies a number by six, then using doublemap with that function would multiply each number in the list by 36.
Develop the zip function, that consumes two lists of the same length and returns a new list of lists where each element of the new list is a list containing both of the corresponding elements from the original lists. Show me this one when it’s complete, for lab credit.
Optional: Develop the quicksortt function, that conumes a list of numbers and sorts them like this: the empty list is already sorted. Any other list is sorted by appending the result of sorting all elements smaller than or equal to the first element to the result of sorting all elements greater than the first element. (You may already know this algorithm, as... quicksort). You will definitely need some helper functions for this. Nevertheless, it’s a straightforward structural recursion.
Optional, from HtDP: Exercises 12.4.1 and 12.4.2. Two hints: write test cases first, and follow the template for functions on lists.
Super-optional, but lots of fun: exercises 32.2.1,2,3. (modeling missionaries and cannibals)