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 Arith 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 the function interp. Write your test cases first!
Develop the function 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 ArithS to ArithC. The parser should use the match form in both functions. 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 Arith 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 unlike the book, Typed Racket gives us the ability to share structures between types, so there’s no need for separate PlusC and PlusS structures; just define your ArithS type as the ArithC type with the addition of the two extra forms.
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 (regexp (regexp-quote "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 1: 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.
Note 2: ... except that Assignment 2 doesn’t actually require desugaring, so you’re going to ripping out the two extra ArithS structures and the desugar function for the assignment.
Develop the one-line function top-interp, that accepts an s-expression and calls the parser and then the desugar function and then the interp function.
Develop the quicksortt function, that accepts a list of real numbers and an ordering function like > that maps two Reals to a Boolean 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 212 and 213, from the Word Games Section. Two hints: write test cases first, and follow the template for functions on lists.
Super-optional, but lots of fun: exercise 521 in 33.2. (modeling missionaries and cannibals)