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