Lab 4

1 FIRST

Finish prior labs. Ask questions.

2 SECOND

Crucial DrScheme tips Part 3:

DrScheme 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 DrScheme. *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!

Use this all the time.

3 THEN

• Develop the parser that we sketched on Monday in class. It should accept only well-formed s-expressions, and output AE’s. It should use the s-exp-match? form. It should handle 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:

  AE		=		num
  		|		{+ AE AE}
  		|		{- AE AE}
  		|		{- AE}

  ... where id is an arbitrary symbol.

  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 parse-eval, that accepts an s-expression and calls the parser and then the eval function from the last lab.

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

• 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: exercises 32.2.1,2,3. (modeling missionaries and cannibals)