|CSC 153: Computer Science Fundamentals||Grinnell College||Spring, 2005|
|Laboratory Exercise Reading|
This reading discusses several elements of program correctness and design:
Several of the Scheme procedures that we have written or studied in
preceding labs presuppose that their arguments will meet specific
pre-conditions. Pre-Conditions are constraints on the types or
values of its arguments. For instance, the
procedure from the lab on recursion won't
work unless it is given a non-empty list of strings:
> (longest-on-list '(3 6 7)) Error in string-length: 6 is not a string. Type (debug) to enter the debugger. > (longest-on-list '()) Error in cdr: () is not a pair. Type (debug) to enter the debugger.
Similarly, a post-condition specifies what should be true at the end of a procedure. In Scheme, a post-condition typically is a statement of what a procedure should return.
It is good programming style to state the pre- and post-conditions for each procedure as comments. Thus, a careful programmer would start the longest-on-list procedure as follows:
(define longest-on-list (lambda (ls) ;Pre-conditon: ls is non-empty list of strings ;Post-condition: procedure returns the string on ls of longest length
One can think of pre- and post-conditions as a type of contract between the developer of a procedure and the user of that procedure.
As with a contract, pre- and post-conditions also have implications concerning who to blame if something goes wrong.
Although the user of a procedure has the responsiblity for meeting its pre-conditions, computer scientists continue to debate whether procedures should check that the pre-conditions actually are met. Here, in summary, are the two arguments.
Pre-conditions should always be checked as a safety matter; a procedure should be sufficiently robust that it will detect variances in incoming data and respond in a controlled way.
Since meeting pre-conditions is a user's responsibility, a developer should not add complexity to a procedure by handling unnecessary cases; further, the execution time should not be increased for a responsible user just to check situations that might arise by careless users.
Actual practice tends to acknowledge both perspectives in differing contexts. More checking is done when applications are more critical. As an extreme example, in software to launch a missle or administer drugs to a patient, software may perform extensive tests of correctness before taking an action -- the cost of checking may be much less than the consequences resulting from unmet pre-conditions.
As a less extreme position, it is common to check pre-conditions once -- especially when checking is relatively easy and quick, but not to check repeatedly when the results of a check can be inferred. (More about this shortly.)
So far, we've been relying on the underlying implementation of Chez Scheme to detect and report such errors. Sometimes this is an adequate way of dealing with them, but in other cases one might prefer to write the procedure in such a way that it checks and enforces its preconditions before performing any operations on its arguments.
In Chez Scheme, this can be done by adding, at the beginning of the body of
the procedure, an
if-expression that tests the precondition
and invokes a procedure named
error if the condition is not met:
(define longest-on-list (lambda (ls) ;Pre-condition: ls is non-empty list of strings ;Post-condition: returns the string on ls of longest length ;; Check pre-conditions (if (or (null? ls) (not (list-of-strings? ls))) (error 'longest-on-list "the argument must be a non-empty list of strings")) ;; Find the longest string on the list. (if (null? (cdr ls)) (car ls) (longer-string (car ls) (longest-on-list (cdr ls)))))) (define list-of-strings? (lambda (ls) ;Pre-condition: none ;Post-condition: returns #t if ls is a non-empty list of strings (or (null? ls) (and (pair? ls) (string? (car ls)) (list-of-strings? (cdr ls))))))
list-of-strings? procedure tests whether its argument is a
list in which each element is a string. (In English:
ls is a
list of strings if it is either the empty list or a pair in which the
first element is a string and the rest is a list of strings.) The
definition of the
longest-on-list procedure is the same as the
one provided in the lab on recursion, except that the precondition is now
being tested: The
error procedure is invoked if either the
incoming argument is empty or it is something other than a list of
With this version of
longest-on-list, the error messages are
> (longest-on-list '(3 6 7)) Error in longest-on-list: the argument must be a non-empty list of strings. Type (debug) to enter the debugger. > (longest-on-list '()) Error in longest-on-list: the argument must be a non-empty list of strings. Type (debug) to enter the debugger.
The error is detected and reported before the procedure gets down to the
point where it might try to apply
string-length to a number
cdr to an empty list.
Chez Scheme provides another procedure that can be used like
error and takes the same two arguments: The
warning procedure prints out a warning message, but does not
interrupt the computation in progress; instead, Chez Scheme rushes on and
attempts to complete the job. (Often it eventually encounters an actual
error and gives up, but one can call
warning regardless of
whether or not it presages an error.)
When developing procedures, it is often useful to include pre-condition testing in your procedures, as this can simplify the task of identifying what happened when something goes wrong.
However, as noted above, the inclusion of pre-condition testing increases execution time. Of course, a single test may be relatively fast, but repeated testing can slow execution execution considerably. Since time is often a scarce resource, it makes sense to save it 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
although it is useful to test the precondition when the procedure is
invoked ``from outside'' by an 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
ls is a list of strings (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), so the cdr must also be a
non-empty list of strings. So it's unnecessary to confirm this again at
the beginning of the recursive call.
One solution to this problem is to replace the definition of
longest-on-list 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
(define longest-on-list (lambda (ls) ;Pre-condition: ls is non-empty list of strings ;Post-conditions: returns error if pre-condition is not met ; otherwise, returns the string on ls of longest length ;; Check pre-conditions (if (or (null? ls) (not (list-of-strings? ls))) (error 'longest-on-list "the argument must be a non-empty list of strings")) ;; Find the longest string on the list. (longest-on-list-kernel ls))) (define longest-on-list-kernel (lambda (ls) ;Pre-condition: ls is non-empty list of strings ;Post-conditions: returns the string on ls of longest length (if (null? (cdr ls)) (car ls) (longer-string (car ls) (longest-on-list-kernel (cdr ls))))))
In later readings, we'll see that there are a couple of ways to put the kernel back inside the husk without losing the efficiency gained by dividing the labor in this way.
Checking pre-conditions verifies that assumptions for a procedure are met. After writing code, a programmer also should provide evidence that the code is correct. Often, this means that the programmer should think carefully about how code should be tested. (While software-development companies normally have separate testing groups to check that an overall produce meets its specifications, individual programmers are responsible for checking their own code as well.)
In testing, the main goal should be to try to find all possible errors; that is, one should try to find test cases which might break the code. Note this is a different perspective than seeing if one can find many test cases that work correctly: if code works correctly for in one case, then the code may work correctly for many similar cases. Overall, one should identify and test as many types of circumstances as possible.
In identifying test cases, one useful strategy involves listing various circumstances that might occur. Consider, for example, the longest-on-list procedure described above. Since the procedure involves a search through the entire list, testing might include the following:
Each of these situations examines a different part of typical processing. More generally, before testing begins, we should identify different types of circumstances that might occur. Once these circumstances are determined, we should construct test data for each situation, so that our testing will cover a full range of possibilities.
In determining possible situations for testing, two approaches are commonly identified:
White-Box Testing: Code is examined to determine each of the possible conditions that may arise, and tests are developed to exercise each part of the code.
Black-Box Testing: The problem is examined to determine the logical cases that might arise. Test cases are developed without reference to details of code.
A list of potential situations together with specific test data that check each of those situations is called a test plan.
While the initial running of a program has been known to produce helpful and correct results, your past programming experience probably suggests that some errors usually arise somewhere in the problem-solving process. Specifications may be incomplete or inaccurate, algorithms may contain flaws, or the coding process may be incorrect. Edsger Dijkstra, a very distinguished computer scientist, has observed¹ that in most disciplines such difficulties are called errors or mistakes, but that in computing this terminology is usually softened, and flaws are called bugs. (It seems that people are often more willing to tolerate errors in computer programs than in other products.)²
Novice programmers sometimes approach the task of finding and correcting an error by trial and error, making successive small changes in the source code ("tweaking" it), and reloading and re-testing it after each change, without giving much thought to the probable cause of the error or to how making the change will affect its operation. This approach to debugging is ineffective, for two reasons:
Tweaking is time-consuming. Novice programmers tend to have a naive confidence that the next small change in the source code, whatever it is, will fix the problem. This is seldom the case. If you detect an error in a procedure, and the first tweak doesn't fix it, the next twelve tweaks probably won't either -- so don't bother with them. Push yourself away from the keyboard and study the context. Don't make even one more change in the source code until you're ready to test a well-thought-out hypothesis about the cause of the error. (This is also a good time to make a separate copy of the procedure, in Emacs, so that you can backtrack to the current version if subsequent experimentation requires extensive temporary rewriting.)
Tweaking usually fixes only a specific, local problem. Very often an error is a symptom of a general misunderstanding on the part of the programmer, one that affects the operation of the procedure in cases other than the one being tested. Unless you address this general problem, tweaking a procedure in such a way that it passes the particular test that it formerly failed is likely to make your program worse instead of better.
A much more time-efficient approach to debugging is to examine exactly what code is doing. While a variety of tools can help you analyze code, a primary technique involves carefully tracing through what a procedure is actually doing. While we'll explore several mechanisms to help with this process through the semester, one of the simplest and most effective is the trace-define capability found in Chez Scheme.
Chez Scheme allows you to examine every call and return of a procedure, by replacing define by trace-define at the start of a procedure definition.
For example, suppose define is replaced by trace-define in the defintion of longest-on-list and longest-on-list-kernel as given earlier in this lab:
(trace-define longest-on-list (lambda (ls) ;Pre-condition: ls is non-empty list of strings ;Post-conditions: returns error if pre-condition is not met ; otherwise, returns the string on ls of longest length ;; Check pre-conditions (if (or (null? ls) (not (list-of-strings? ls))) (error 'longest-on-list "the argument must be a non-empty list of strings")) ;; Find the longest string on the list. (longest-on-list-kernel ls))) (trace-define longest-on-list-kernel (lambda (ls) ;Pre-condition: ls is non-empty list of strings ;Post-conditions: returns the string on ls of longest length (if (null? (cdr ls)) (car ls) (longer-string (car ls) (longest-on-list-kernel (cdr ls))))))
With this adjustment, Chez Scheme will report the value of each parameter when these procedures are called, and the value of the result when each procedure call finishes. A sample interaction follows.
> (longest-on-list '("To" "be" "or" "not" "to" "be")) |(longest-on-list ("To" "be" "or" "not" "to" "be")) |(longest-on-list-kernel ("To" "be" "or" "not" "to" "be")) | (longest-on-list-kernel ("be" "or" "not" "to" "be")) | |(longest-on-list-kernel ("or" "not" "to" "be")) | | (longest-on-list-kernel ("not" "to" "be")) | | |(longest-on-list-kernel ("to" "be")) | | | (longest-on-list-kernel ("be")) | | | "be" | | |"to" | | "not" | |"not" | "not" |"not" "not" >
In this listing, the procedure longest-on-list is invoked at the Scheme prompt. With trace-define the procedure call is echoed with the full parameter list. Procedure longest-on-list-kernel then is called several times, and the listing shows the parameter used in the each call. Once the recursion has finished, the listing shows the results returned at each stage. Indenting helps to align the result of a procedure call with the corresponding call to that procedure.
This document is available on the World Wide Web as
created January 13, 1998 by John David Stone and Henry
last revised February 3, 2005 by Henry M. Walker
|For more information, please contact Henry M. Walker at email@example.com.|