Functional Problem Solving (CSC 151 2014F) : Readings
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: We consider the constraints we might place upon procedures and mechanisms for expressing those constraints.
Several of the Scheme procedures that we have written or studied
in preceding labs presuppose that their arguments will meet
specific preconditions -- constraints
on the types or values of its arguments. For instance, the
drawings-leftmost
procedure from the third
reading on list recursion requires its argument to be
a non-empty list of drawings.
;;; Procedure: ;;; drawing-leftmost ;;; Parameters: ;;; drawing1, a drawing ;;; drawing2, a drawing ;;; Purpose: ;;; Determine the leftmost of drawing1 and drawing2. ;;; Produces: ;;; leftmost, a drawing. ;;; Preconditions: ;;; drawing1 and drawing2 have the correct form for drawings. ;;; Postconditions: ;;; leftmost is equal to either drawing1 or drawing2. ;;; leftmost either begins in the same column as both drawing1 and ;;; drawing2 or begins in the same column as one, and begins to the ;;; left of the other. (define drawing-leftmost (lambda (drawing1 drawing2) (if (< (drawing-left drawing1) (drawing-left drawing2)) drawing1 drawing2))) ;;; Procedure: ;;; drawings-leftmost ;;; Parameters: ;;; drawings, a list of drawings ;;; Purpose: ;;; Find the leftmost drawing in drawings. ;;; Produces: ;;; leftmost, a drawing. ;;; Preconditions: ;;; drawings is nonempty. ;;; drawings contains only drawings. ;;; Postconditions: ;;; leftmost is an element of drawings. ;;; For each drawing, d, in drawings. ;;; (drawing-left leftmost) <= (drawing-left d) (define drawings-leftmost (lambda (drawings) (if (null? (cdr drawings)) (car drawings) (drawing-leftmost (car drawings) (drawings-leftmost (cdr drawings))))))
If some careless programmer invokes
drawings-leftmost
and gives it, as an argument,
the empty list, or a list in which one of the elements is not a drawing,
or perhaps even some Scheme value that is not a list at all, the
computation that the definition of drawings-leftmost
describes cannot be completed.
>
(drawings-leftmost null)
cdr: expects argument of type <pair>; given ()>
(drawings-leftmost (list 1))
1>
(drawings-leftmost 2)
cdr: expects argument of type <pair>; given 2
As you can see, none of these error messages are particularly helpful.
And, worse yet, in one case drawings-leftmost
returns
a value, but that value is not a drawing.
Whose responsibility is it to handle these types of errors? As we will
see, it is possible to share responsibility between the person who writes
a procedure and the person who calls a procedure.
A procedure definition is like a contract between the author
of the definition and someone who invokes the procedure. The
postconditions of the procedure are what the
author guarantees: When the computation directed by the procedure is
finished, the postconditions shall be met. Usually the postconditions
are constraints on the value of the result returned by the procedure.
For instance, the postcondition of the square
procedure,
(define square (lambda (val) (* val val)))
is that the result is the square of the argument val
.
The preconditions are the guarantees that the invoker of a procedure makes
to the author, the constraints that the arguments shall meet. For
instance, it is a precondition of the square
procedure that
val
is a number.
If the invoker of a procedure violates its preconditions, then the
contract is broken and the author's guarantee of the postconditions
is void. (If val
is, say, a list or a drawing, then the
author can't very well guarantee to return its square. What would that
even mean?) To make it
less likely that an invoker violates a precondition by mistake, it is
usual to document preconditions carefully and to include occasional
checks in one's programs, ensuring that the preconditions are met
before starting a complicated computation.
Many of Scheme's primitive procedures have such preconditions, which they enforce by aborting the computation and displaying a diagnostic message when the preconditions are not met:
>
(/ 1 0)
/: division by zero>
(log 0)
log: undefined for 0>
(+ 1 'two)
+: expects type <number> as 2nd argument, given: two; other arguments were: 1>
(length 116)
length: expects argument of type <proper list>; given 116
To enable us to enforce preconditions in the same way,
most implementations of Scheme provides a procedure named
error
, which takes a string as its first argument.
Calling the error
procedure aborts the entire computation
of which the call is a part and causes the string to be displayed as
a diagnostic message.
For instance, we could enforce drawings-leftmost
's
precondition that its parameter be a non-empty list of drawings by
rewriting its definition thus:
(define drawings-leftmost (lambda (drawings) (when (or (not (list? drawings)) (null? drawings) (not (all-drawings? drawings))) (error "drawings-leftmost: requires a non-empty list of drawings")) (if (null? (cdr drawings)) (car drawings) (drawing-leftmost (car drawings) (drawings-leftmost (cdr drawings))))))
In this definition, we assume the existence of an
all-drawings?
predicate that takes any list as
its argument and determines whether or not all of the elements of that
list are drawings. We will have to write that procedure soon.
Now the drawings-leftmost
procedure enforces its
preconditions
>
(drawings-leftmost null)
drawings-leftmost: requires a non-empty list of drawings>
(drawings-leftmost (list 1))
drawings-leftmost: requires a non-empty list of drawings>
(drawings-leftmost 2)
drawings-leftmost: requires a non-empty list of drawings
Of course, while these error messages are better than the original
error messages, they don't tell us the complete story. In particular,
they don't tell us what the value of the incorrect parameter is. Fortunately,
error
can take additional parameters, which it
presents verbatim.
(define drawings-leftmost (lambda (drawings) (when (or (not (list? drawings)) (null? drawings) (not (all-drawings? drawings))) (error "drawings-leftmost: requires a non-empty list of drawings, given " drawings)) (if (null? (cdr drawings)) (car drawings) (drawing-leftmost (car drawings) (drawings-leftmost (cdr drawings))))))
>
(drawings-leftmost null)
drawings-leftmost: requires a non-empty list of drawings, given '()>
(drawings-leftmost (list 1))
drawings-leftmost: requires a non-empty list of drawings, given '(1)>
(drawings-leftmost 2)
drawings-leftmost: requires a non-empty list of drawings, given 2
Including precondition testing in your procedures often makes them markedly easier to analyze and check, so we recommend the practice, especially during program development. There is a trade-off, however: It takes time to test the preconditions, and that time will be consumed on every invocation of the procedure. Since time is often a scarce resource, it makes sense to save time by skipping the test when you can prove that the precondition will be met. This often happens when you, as programmer, control the context in which the procedure is called as well as the body of the procedure itself.
For example, in the preceding definition of
drawings-leftmost
, although it is useful to test the
precondition when the procedure is invoked “from outside”
by a potentially irresponsible caller, it is a waste of time to
repeat the test of the precondition for any of the recursive calls
to the procedure. At the point of the recursive call, you already
know that drawings
is a list of drawings (because you
tested that precondition on the way in) and that its cdr is not empty
(because the body of the procedure explicitly tests for that condition
and does something other than a recursive call if it is met). Hence,
the cdr must also be a non-empty list of strings. It is unnecessary
(and therefore wasteful) to confirm this again at the beginning of
the recursive call.
One solution to this problem is to replace the definition of
drawings-leftmost
with two separate procedures,
a “husk” and a “kernel”. The husk interacts
with the outside world, performs the precondition test, and launches
the recursion. The kernel is supposed to be invoked only when the
precondition can be proven true; its job is to perform the main work
of the original procedure, as efficiently as possible:
(define drawings-leftmost (lambda (drawings) ; Make sure that drawings is a non-empty list of drawings (when (or (not (list? drawings)) (null? drawings) (not (all-drawings? drawings))) (error "drawings-leftmost: requires a non-empty list of drawings, given " drawings)) ; Find the leftmost of that list. (drawings-leftmost-kernel drawings))) (define drawings-leftmost-kernel (lambda (drawings) (if (null? (cdr drawings)) (car drawings) (drawing-leftmost (car drawings) (drawings-leftmost-kernel (cdr drawings))))))
The kernel has the same preconditions as the husk procedure, but does not need to enforce them, because we invoke it only in situations where we already know that the preconditions are satisfied.
The one weakness in this idea is that some potentially irresponsible caller might still call the kernel procedure directly, bypassing the husk procedure that he's supposed to invoke. In a subsequent reading and lab, we'll see that there are a few ways to put the kernel back inside the husk without losing the efficiency gained by dividing the labor in this way.
Are we done? Mostly. However, instead of giving the same error message
for every type of error, we might customize error messages for the
particular kind of error, giving a different error message in each
case. The drawings-leftmost
procedure is perhaps
not the best example, because all three kinds of errors are essentially
a failure to provide a non-empty list of drawings, but we'll use it as
a demonstration anyway.
(define drawings-leftmost (lambda (drawings) (cond [(not (list? drawings)) (error "drawings-leftmost: requires a non-empty list of drawings, received a non-list: " drawings)] [(null? drawings) (error "drawings-leftmost: requires a non-empty list of drawings, received the empty list")] [(not (all-drawings? drawings)) (error "drawings-leftmost: requires a non-empty list of drawings, received a list that includes at least one non-drawing: " drawings)] [else (drawings-leftmost-kernel drawings)]))) (define drawings-leftmost-kernel (lambda (drawings) (if (null? (cdr drawings)) (car drawings) (drawing-leftmost (car drawings) (drawings-leftmost-kernel (cdr drawings))))))
Now, our messsages are a bit more informative.
>
(drawings-leftmost null)
drawings-leftmost: requires a non-empty list of drawings, received the empty list>
(drawings-leftmost 1)
drawings-leftmost: requires a non-empty list of drawings, received a non-list: 1>
(drawings-leftmost (list 2))
drawings-leftmost: requires a non-empty list of drawings, received a list that includes at least one non-drawing: '(2)
In general, we include precondition checking in our procedures using the following pattern.
(define safe-procedure (lambda (parameters) (cond [(precondition-check-1) (error "failed first precondition" parameters)] [(precondition-check-2) (error "failed second precondition" parameters)] ... [(precondition-check-n) (error "failed last precondition" parameters)] [else (procedure-kernel parameters)])))
In an earlier class session, you may have written 6P documentation for a quadratic root finding procedure similar to the following:
;;; Procedure ;;; quadratic-root ;;; Parameters: ;;; a, a real number ;;; b, a real number ;;; c, a real number ;;; Purpose: ;;; Find the root of the polynomial ax^2+bx+c with the largest absolute value ;;; Produces: ;;; root, a real number ;;; Preconditions: ;;; FORTHCOMING ;;; Postconditions: ;;; root = ( -b + sqrt(b^2-4*ac) ) / (2*a) (define quadratic-root (lambda (a b c) (/ (+ (- b) (sqrt (- (* b b) (* 4 a c)))) (* 2 a))))
a. What are the preconditions for
quadratic-root
? Document them in the 6Ps.
b. Following a pattern similar to
safe-procedure
, add a
cond
statement to quadratic-root
and verify its preconditions.