Functional Problem Solving (CSC 151 2014F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: In this laboratory, you will consider mechanisms for verifying the preconditions of procedures. You will also consider some issues in the documentation of such procedures.
Make a copy of preconditions-lab.rkt
.
a. In the reading, we called drawings-leftmost
on
three erroneous inputs: the empty list, the value 1, and a list containing
the value 2. Check to see whether you get the same error messages as
were presented in the reading.
b. You may have noted that drawings-leftmost
requires an
all-drawings?
procedure.
Here's a definition of that procedure.
(define all-drawings? (lambda (lst) (or (null? lst) (and (drawing? (car lst)) (all-drawings? (cdr lst))))))
Add this definition to your definitions pane and check to see whether you now get the “appropriate” output.
c. What preconditions should all-drawings?
have?
d. Is it necessary to test those preconditions? Why or why not?
e. Compare your answers to the those in notes at the end of this lab.
f. Document the all-drawings?
procedure.
In the corresponding
reading, there is an extended version of
drawings-leftmost
that reports different errors.
Replace your current drawings-leftmost
with the new
version and verify that it does, in fact, report different errors.
Here is a procedure, index-of
, that takes two
arguments - a value,
val
, and a list, vals
- and
returns the index of val
in vals
.
(define index-of (lambda (val vals) (cond ; If the value appears first in the list, then its index is 0. [(equal? val (car vals)) 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. [else (+ 1 (index-of val (cdr vals)))])))
Here are some examples of index-of
in use.
>
(index-of "red" (list "red" "green" "blue" "yellow"))
0
>
(index-of "blue" (list "red" "green" "blue" "yellow"))
2
a. What preconditions should index-of
have?
b. What will happen if the preconditions are violated? Verify your answer experimentally.
c. Arrange for index-of
to explicitly signal
an error (by invoking the error
procedure)
if vals
is not a list.
d. Arrange for index-of
to explicitly signal
an error (by invoking the error
procedure) if
val
does not occur at all as an element of
vals
.
>
(index-of "black" (list "red" "green" "blue" "yellow"))
Error: The value does not appear in the list.
e. 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.
f. If val
does not occur as an element
of vals
, why might be better to have
index-of
throw an error?
g. Once you have explained your answers to e and f, you may want to check our notes on this problem.
h. Rewrite index-of
using a husk-and-kernel
strategy.
When you're done thinking about these questions, add your definition
of index-of
to your notes, as it is a very useful
procedure.
Consider the following procedure that increments the red component
of color
by 64.
;;; Procedure: ;;; irgb-much-redder ;;; Parameters: ;;; color, an integer-encoded RGB color ;;; Purpose: ;;; To produce a color that is much redder than color. ;;; Produces: ;;; newcolor, an integer-encoded RGB color ;;; Preconditions: ;;; FORTHCOMING ;;; Postconditions: ;;; (irgb-red new-color) = (+ 64 (irgb-red color)) ;;; (irgb-green new-color) = (irgb-green color) ;;; (irgb-blue new-color) = (irgb-blue color) (define irgb-much-redder (lambda (color) (irgb (+ 64 (irgb-red color)) (irgb-green color) (irgb-blue color))))
a. What preconditions must be met in order for
irgb-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,
(irgb-weighted-average
,
that makes a new color, each of whose components is computed by
multiplying the corresponding component of fraction
color1
color2
)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 (irgb-red color1)) (* (- 1 fraction) (irgb-red color2)))
a. What preconditions should irgb-weighted-average
have? (Think about restrictions on fraction
,
color1
, and color2
.)
b. How might you formally specify the postconditions for
irgb-weighted-average
?
c. Here is a simple definition of
rgb-weighted-average
.
(define irgb-weighted-average (lambda (fraction color1 color2) (let ([frac2 (- 1 fraction)]) (irgb (+ (* fraction (irgb-red color1)) (* frac2 (irgb-red color2))) (+ (* fraction (irgb-green color1)) (* frac2 (irgb-green color2))) (+ (* fraction (irgb-blue color1)) (* frac2 (irgb-blue color2)))))))
Rewrite irgb-weighted-average
to use a husk-and-kernel
strategy to test for preconditions.
Consider a procedure, (
, that builds a
new list by substituting list-substitute
lst
old
new
)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, (
, that, given a list of drawings and two
colors, makes a new copy of drawings-partially-recolor
drawings
old
new
)drawings
by using the
color new
whenever a drawing with color
old
appeared in the original list.
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 drawings
is a list of
drawings, before starting the recursion.
index-of
, Revisited
Rewrite index-of
using tail recursion and a husk
and kernel.
Here are some possible solutions.
a. The all-drawings?
procedure needs a list as a parameter.
b. It depends on how we will use all-drawings?
. 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.
e. 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.
f. 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.