Laboratory: Verifying Preconditions

You may have noted that spots-leftmost requires an all-spots? procedure. Here's a definition.

(define all-spots?
  (lambda (lst)
    (or (null? lst)
        (and (spot? (car lst))
             (all-spots? (cdr lst))))))

a. What preconditions should all-spots? have?

b. Is it necessary to test those preconditions? Why or why not?

c. Compare your answers to the those in notes at the end of this lab.

d. Document the all-spots? procedure.

a. Verify that spots-leftmost returns an appropriate error when given incorrect inputs.

b. In the corresponding reading, there is an extended version of spots-leftmost that reports different errors. Replace your current spots-leftmost with the new version and verify that it does, in fact, report different errors.

Here is a procedure, index-of, that takes a value, val, and a list, vals, as its arguments and returns the index of val in vals.

(define index-of
  (lambda (val vals)
    ; If the value appears first in the list
    (if (equal? val (car vals))
        ; Then its index is 0.
        0
        ; Otherwise, we find the index in the cdr.  Since we've
        ; thrown away the car in finding that index, we need to add 1
        ; to get its index in the overall list.
        (+ 1 (index-of val (cdr vals))))))

And here are some examples of index-of in use.

> (index-of color-red (list color-red color-green color-blue color-yellow))
0
> (index-of color-blue (list color-red color-green color-blue color-yellow))
2

a. What preconditions should index-of have?

b. Arrange for index-of to explicitly signal an error (by invoking the throw procedure) if vals is not a list.

c. Arrange for index-of to explicitly signal an error (by invoking the throw procedure) if val does not occur at all as an element of vals.

> (index-of color-black (list color-red color-green color-blue color-yellow))
Error: The value does not appear in the list.

d. Some programmers return special values to signal an error to the caller, rather than throw an error. If val does not occur as an element of vals, why might it be better to have index-of return a special value (such as -1 or #f) rather than throwing an error? Explain your answer.

e. If val does not occur as an element of vals, why might be better to have index-of throw an error?

f. Once you have explained your answers do d and e, you may want to check our notes on this problem.

g. Rewrite index-of using a husk-and-kernel strategy.

When you're done thinking about these questions, add index-of to your library as it is a very useful procedure.

Consider the following procedure that increments the red component of color by 64.

;;; Procedure:
;;;   rgb-much-redder
;;; Parameters:
;;;   color, an RGB color
;;; Purpose:
;;;   To produce a color that is much redder than color.
;;; Produces:
;;;   newcolor, a color
;;; Preconditions:
;;;   FORTHCOMING
;;; Postconditions:
;;;   (rgb-red new-color) = (+ 64 (rgb-red color))
;;;   (rgb-green new-color) = (rgb-green color)
;;;   (rgb-blue new-color) = (rgb-blue color)
(define rgb.much-redder
  (lambda (color)
     (rgb-new (+ 64 (rgb-red color)) (rgb-green color) (rgb-blue color))))

a. What preconditions must be met in order for rgb-much-redder to meet its postconditions?

b. Should we test those preconditions? Why or why not?

In a number of exercises, we were required to blend two colors. For example, we blended colors in a variety of ways to make interesting images, and we made a color more grey by averaging it with grey. In blending two colors, we are, in essence, creating an average of the two colors, but an average in which each color contributes a different fraction.

For this problem, we might write a procedure, (rgb-weighted-average fraction color1 color2), that makes a new color, each of whose components is computed by multiplying the corresponding component of color1 by fraction and adding that to the result of multiplying the corresponding component of color2 by (1-fraction). For example, we might compute the red component with

(+ (* fraction (rgb-red color1)) (* (- 1 fraction) (rgb-red color2)))

a. What preconditions should rgb-weighted-average have? (Think about restrictions on fraction, color1, and color2.)

b. How might you formally specify the postconditions for rgb-weighted-average?

c. Here is a simple definition of rgb-weighted-average.

(define rgb-weighted-average
  (lambda (fraction color1 color2)
    (let ((frac2 (- fraction 1)))
      (rgb-new (+ (* fraction (rgb-red color1)) (* frac2 (rgb-red color2)))
               (+ (* fraction (rgb-green color1)) (* frac2 (rgb-green color2)))
               (+ (* fraction (rgb-blue color1)) (* frac2 (rgb-blue color2)))))))

Rewrite rgb-weighted-average to use a husk-and-kernel strategy to test for preconditions.

Consider a procedure, (list-substitute lst old new), that builds a new list by substituting new for old whenever old appears in lst.

> (list-substitute (list "black" "red" "green" "blue" "black") "black" "white")
("white" "red" "green" "blue" "white")
> (list-substitute (list "black" "red" "green" "blue" "black") "yellow" "white")
("black" "red" "green" "blue" "black")
> (list-substitute null "yellow" "white")
()

a. Document this procedure, making sure to carefully consider the preconditions.

b. Implement this procedure, making sure to check the preconditions.

Consider a procedure, (spots-substitute spots old new), that, given a list of spots and two colors, makes a new copy of spots by using the color new whenever old appeared in the original spots.

a. What preconditions does this procedure have?

b. Implement this procedure, using the husk-and-kernel structure to ensure that old and new are rgb colors and that spots is a list of spots, before starting the recursion.

Rewrite index-of using tail recursion and a husk and kernel.

Here are some possible solutions.

a. The all-spots? procedure needs a list as a parameter.

b. It depends on how we will use all-spots?. If we are sure that it will only be called correctly (e.g., after we've already tested that the parameter is a list or in a context in which we can prove that the parameter is list), then it need not check its preconditions. Otherwise, it should check its preconditions.

Return to the problem.

d. If index-of explicitly checks its precondition using member?, we end up duplicating work. That is, we scan the list once to see if the value is there, and once to see its index. Even if index-of does not explicitly check its precondition, the caller may be called upon to do so, which still duplicates the work. By having index-of return a special value, we permit the client to have index-of do both.

e. In some cases, programs should stop when there is no index for a specified value. For example, a program that tries to look up a grade for a student should not continue if the student does not appear in the list. There are also some instances in which careless programmers do not check the return value, which can lead to unpredictable behavior.

Return to the problem.