Lab 03 Su11 CS61A

CS61A Summer 2011 Lab 3

1. Many Scheme procedures require a certain type of argument. For example, the arithmetic procedures only work if given numeric arguments. If given a non-number, an error results.

Suppose we want to write safe versions of procedures, that can check if the argument is okay, and either call the underlying procedure or return #f for a bad argument instead of giving an error. (We’ll restrict our attention to procedures that take a single argument.)

> (sqrt ’hello)

ERROR: magnitude: Wrong type in arg1 hello

> (type-check sqrt number? ’hello)

#f

> (type-check sqrt number? 4)

2

Write type-check. Its arguments are a function, a type-checking predicate that returns #t if and only if the datum is a legal argument to the function, and the datum.

2. We really don’t want to have to use type-check explicitly every time. Instead, we’d like to be able to use a safe-sqrt procedure:

> (safe-sqrt ’hello)

#f

> (safe-sqrt 4)

2

Don’t write safe-sqrt! Instead, write a procedure make-safe that you can use this way:

> (define safe-sqrt (make-safe sqrt number?) )

It should take two arguments, a function and a type-checking predicate, and return a new function that returns #f if its argument doesn’t satisfy the predicate.

The following lab exercises concern the change counting program on pages 40–41 of Abelson and Sussman.

3. Trace through the code and draw on paper what calls are produced by the following call:

(count-change 7)

4. Save a copy of the original program and comment it out by surrounding it in #| and |# Next, modify the copy of the cc procedure so that its kinds-of-coins parameter, instead of being an integer, is a sentence that contains the values of the coins to be used in making change. The coins should be tried in the sequence they appear in the sentence. For the count-change procedure to work the same in the revised program as in the original, it should call cc as follows:

(define (count-change amount)

(cc amount ’(50 25 10 5 1) ) )

5. Return to your original copy of the cc procedure (and comment out your modified one again using #| and |# ). Identify two ways to change the program to reverse the order in which coins are tried, that is, to change the program so that pennies are tried first, then nickels, then dimes, and so on. (If you only figure out one way that is fine. The goal is to feel comfortable with the count-change, cc, and first-denomination functions.)

6. Abelson and Sussman claim that this change would not affect the correctness of the computation. However, it does affect the efficiency of the computation. Implement one of the ways you devised in exercise 5 for reversing the order in which coins are tried, and determine the extent to which the number of calls to cc is affected by the revision. Verify your answer on the computer, and provide an explanation. Hint: limit yourself to nickels and pennies, and compare the trees resulting from (cc 5 2) for each order.

Note: Trace might be useful here....