Lab 3

Course Homepage

1 Crucial DrRacket tips Part 3

DrRacket has a really nice documentation system. You should figure out how to use it.

1. Start up Firefox. You don’t absolutely have to do this first, but it makes everything else go faster.

2. Start DrRacket. *IN EITHER WINDOW*, type "map". Without the quotes. Hit the F1 key. Firefox should open, with a bunch of choices.

3. Click on the word "map" in the first entry. Voila! Documentation!

4. 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, consisting of both a parse1 function and a desugar function. The parse1 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. EDIT: Follow the book’s definition, including (for instance) separate PlusS and PlusC structures.

  Write lots of test cases.

  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 the next assignment 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.

• Got it all working? Great! Now develop the parse2 function, that combines parse1 and desugar, mapping s-expressions directly to ArithC forms, by performing the desugaring in the parse function.

  Which approach (parse1 + desugar vs. parse2) makes more sense for this lab? Is there a situation in which the other one would make more sense?

• 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)