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 both a parse function and a desugar function. The parse function should map Sexp to ArithS and the desugar function should map ArithSs to ArithCs. It should use the 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} Use an auxiliary arithS definition and explicit desugaring, as described in the book. Note that–like the book–you’ll need to use distinct PlusC and PlusS structures. This is because when you “flip the switch” to Typed Racket further down in this lab, Typed Racket will be unhappy about putting ArithS structures in fields that are of type ArithC. You can solve this with parametric polymorphism, but let’s just not go there yet.
Write lots of test cases. In order to test your exceptions, you’ll need to use the check-exn form, which requires a few teeny tiny things that you haven’t seen before: regular expressions and thunks.
So, suppose you’re testing a function named p that signals the error "Ouch my foot" when called with the number 13. Here’s how I’d write that test:
(check-exn #px"Ouch my foot" (lambda () (p 13))) There are about sixteen things that I should tell you about regular expressions and thunks, but this should be enough to get you started.
Note: This parser 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 desugar function and then the interp function.
Develop the doublemap function, that consumes a function from Number to Number and a list of Numbers 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 Number 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. Read that last sentence carefully.
Change the language level from racket to typed/racket, and change (require rackunit) to (require typed/rackunit) and un-comment all of your define-types and function type declarations. Also, add types to the fields of your structure definitions, so that (for instance) arg1 might become [arg1 : ExprC]. I would strongly encourage you to do this after you get everything else working. Also, it may be helpful to temporarily comment out big chunks of the program to simplify things.
FWIW, there are a bunch of ways to comment things out, but my favorite is to begin with "#;(" (looks like a disgruntled person with bad hair) and end with ")". Note that this only works if your parens are balanced.
Hint: use the Sexp type in typed/racket to refer to s-expressions.
Optional: Use All parametric polymorphic types to narrow the types of zip and doublemap.
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)