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!
Wait, you don’t use Firefox? Maybe you should switch browsers, and use one made by a non-profit whose business model doesn’t consist of selling your information (*cough*).
Use this all the time.
2 Exercises
Develop the parse000 function, that accepts an s-expression and uses a single match pattern to return true for s-expressions that are a list containing a number, the symbol 'chris, and a symbol (in that order). It should use an other pattern to return #f otherwise.
Note that in Typed Racket, the type Sexp is the one you want to use for s-expressions.
For this and the next few patterns, you may want to refer to the match pattern examples.
Develop the parse001 function, that accepts an s-expression and uses the same match pattern, but returns the symbol in case of success, and #f otherwise. Use a union type for the result.
Develop the parse002 function, that also uses a single pattern and that succeeds for s-expressions that are lists of length three whose second element is a list of real numbers. On success, it should return the list of numbers. On failure, it should return #f.
Note: on this problem you’ll probably run into one of the dark cornerns of TR+match, specifically occurring when you use a predicate pattern inside a ellipsis pattern. See the appropriate section in "Hints on using TR in CSC430" that’s linked to from the course webpage.
Develop the ohno function that accepts a value and returns the symbol 'okay if the input is a number, and otherwise uses error to signal an error where the error message includes the given value. Read the documentation for error to see how this works. Oh, well, here’s an example as well:
(error 'my-fun "expected foo, got ~e" 1234)
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.
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 method num-adds, that accepts an ArithC and returns the number of additions it contains.
Add a printf to your num-adds function that prints each tree on entry to the function.
Develop a parser for the Arith language. It should map Sexp to ArithC. It should use the match form. 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} Extend the parser and the interpreter to handle a new ^2 feature that squares a number. With this new feature, the grammar for the language is this:
Arith = num | {+ Arith Arith} | {* Arith Arith} | {^2 Arith} Develop the one-line function top-interp, that accepts an s-expression and calls the parser and then the interp function.
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. Optionally: use the All parametric polymorphism feature to widen the type so it can handle any kinds of lists.
Optional: 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)