04-testing-fnptrs.txt

Last time: 1) Tail recursion 2) Helper functions 3) Recursive invariants 4) Testing introduction Today, we'll finish talking about testing, and then look at how to generalize functions by passing other functions as arguments. The outline for today is: * The testing process * The problem of "nearly identical" functions * Function pointer syntax * Generalization via function pointers **** The Testing Process To test some piece of code (either a component or a whole piece), there are several steps. 1) Understand the specification 2) Identify the required behaviors 3) Write specific tests 4) Know the answers in advance 5) Include stress tests 1) Understand the specification Before you can test something for correctness, you need to know what "correct" is. For an entire assignment, read through the spec very carefully, and make a note of everything it says you have to do. This is best done far away from a computer, in a comfy setting, with a tasty coffee or tea. If you read it carefully enough, the spec will tell you everything you need to know about "correctness". To complete most assignments, you'll have to break down the solution into constituent parts. As we'll see, it is up to you to write the specification of most of these parts, which means you are simultaneously judge and jury. This makes your job quite a bit harder, as there is no external source to tell you what is "supposed" to happen. Sometimes your program as a whole may not work correctly because your specification is incorrect (e.g. you misunderstood the definition of standard deviation). 2) Identify behaviors For each specification---of a project or a component---it is possible to boil the specification down to a list of things that must and must not happen. These are the "required behaviors" and a correct implementation must exhibit all of them. Note that a required behavior is really a "class" of behaviors. For example, a program that adds to numbers only has one behavior---that it adds numbers correctly. The list of behaviors is *not* adding 1 and 1 and getting 2, adding 1 and 2 and getting 3, etc. As you read the spec in step 1, it helps if you make a note of each required behavior that you find. Ex: program should print an error message and exit if payment is less than zero. 3) Write specific test cases For each of your required behaviors, write a test case (or possibly a set of test cases) that checks the set of required behaviors. To the extent possible, the test case should check *exactly* one behavior---no more! That way, if the case fails, you know where to start looking. There are two classes of test cases that make sense: * simple inputs * boundary conditions Simple cases are those that are "expected" or "normal" for the problem at hand. The test case that we gave you for project 1 is an example of a simple test case. "Boundary" cases are at the edges of what is expected, or formed to exploit some detail of implementation. What might be a boundary condition for project 1? For example, suppose we have a function that sorts a list of numbers, where the list can contain no more than 10 items. A simple case might look like this: (1 5 4 3 9) Boundary cases might include: () /* the empty list */ (1) /* a list with one object */ (1 1 1 1 1) /* a list of identical objects */ (1 2 3 4 5) /* a pre-sorted list */ (5 4 3 2 1) /* an inverted list */ (-1 2 -3 4 -5) /* a list with negative #s */ (1 3 5 7 9 2 4 6 8 10) /* a max-size list */ 4) Know the answers in advance. Avoid writing test cases, flinging them at the code, and quickly glancing at the output. It's too easy to fool yourself that way. Before you run a test case, write down what you expect a correct answer to be. Then, run your test case. If the result differs in *any* way from what you expected, try to figure out why. Your expectation could have been wrong, or your implementation is. Either way, there is something to fix. Doing this ABSOLUTELY REQUIRES that you understand the specification. Because, if your understanding of the spec is wrong, you will solve it incorrectly, and your incorrect solution will agree perfectly with your incorrect prediction of what should happen. 5) Include stress tests Once you've tested each individual behavior, it's time to test all of them in concert. For this, you want *large* and *long running* test cases. It's important that these cases be large, to exercise resource limits in your program. It's important that they be long-running, because some errors are the result of lots of little bugs that individually don't matter much, but as they cascade produce catastrophic results. **** The joys of automation As you develop test cases for some code, it pays to write *other* programs that subject this code to those test cases automatically. This is important because, as the number of test cases grows (and the hour grows late) people get tired, and start to make mistakes. Computers, however, never get tired, so take advantage of this. That way, every time you make any change to your code---no matter how trivial---you can go back and test all of the behaviors. When you create such "test suites" it's a good idea to start with the easiest test cases and work your way up. That way, if a later case fails, you know it's probably not because of behaviors already tested. Furthermore, if your code has a basic bug, many complex behaviors can be adversely affected. In evaluating EECS 280 projects, all of our "correctness testing" is completely automated. I run one command, and take a (sometimes lengthy) coffee break. +++++++++++++++++++++++++++++++++++++++++++++ In project two, you're asked to write a function to add all the elements in a list, and another to multiply all the elements in a list. These are almost exactly the same function. Writing almost the exact same function twice is almost certainly a bad idea. There are two main reasons for this: 1) it's wasteful of your time 2) if you find a better way to perform the underlying computation, you have to change many different versions of the same thing; this is prone to error. Remember back in the second lecture, when we defined the notion of a variable's "type": A variable's type tells us two things: * the set of possible values that object may assume * the set of operations possible on/with that object So far, we've been working with types like "int". The type int can take values from the range [INT_MIN .. INT_MAX], and there are a variety of operations (+, -, *, /, etc.) that can be performed on ints. For this class, we'll be talking about the type "list_t". This is one of the two "fundamental types" we'll be working with in Project 2. (Note: when we define a user type, we often name it with something ending in _t, by convention.) A list can hold a sequence of zero or more integers. It also happens that there is a recursive definition for the values that a list can take. A valid list is either the EMPTY_LIST or an integer followed by another valid list Here are some examples of valid lists ( 1 2 3 4 ) // a list of four elements ( 2 5 2 ) // a list of three elements ( ) // a list of zero elements--the empty list There are also several operations that can be applied to lists. There are only three we need for this lecture. list_first takes a list, and returns the first element(an integer) from the list. list_rest takes a list and returns the list comprising all but the first element. Both of these are defined only on non-empty lists. To know whether a list is empty or not, we get a function list_isEmpty. It takes a list and returns the boolean "true" if the argument is an empty list, and "false" otherwise. Now, let's suppose we want to write a (tail-recursive) function to find the smallest element in a list. The recursive definition of this problem is: smallest(list) = the element (if list has only a single element) or the minimum of the first element and the smallest element from the rest of the list Note that this implies that smallest is not defined for the empty list, just like list_first and list_rest are not. Here is a tail-recursive solution. static int small_help(int so_far, list_t list) { if (list_isEmpty(list)) { return so_far; } else { int candidate = list_first(list); if (candidate < so_far) so_far = candidate; return small_help(so_far, list_rest(list)); } } int smallest(list_t list) // REQUIRES: list is not empty // EFFECTS: returns the smallest element contained in list { return small_help(list_first(list), list_rest(list)); } The intuition behind this solution is as follows. We take the first element of the list, and use that as our first guess as the smallest in the list. We then call small_help, which will walk down the list, looking for anything smaller than we've seen so far. If small_help is passed an empty list, that list can't have any element smaller than the smallest you've seen so far, So, the smallest so far must be the result. Otherwise, we take the next element from the list, and see if it is smaller than the smallest we've seen so far; if it is, it becomes our new "smallest so far" element. Then, we recurse. Question: list_first REQUIRES a non-empty list. Does this solution satisfy that REQUIREMENT in all cases? Why or why not? Suppose we now had to write the function largest. It's recursive definition is: largest(list) = the element (if list has only a single element) or the maximum of the first element and the largest element from the rest of the list This is almost identical to the definition of smallest, and unsurprisingly the solution is almost identical, too: static int large_help(int so_far, list_t list) { if (list_isEmpty(list)) { return so_far; } else { int candidate = list_first(list); if (candidate > so_far) so_far = candidate; return large_help(so_far, list_rest(list)); } } int largest(list_t list) // REQUIRES: list is not empty // EFFECTS: returns the largest element contained in list { return large_help(list_first(list), list_rest(list)); } In fact, the *only* differences between smallest and largest are: 1) the names of the function 2) the comment in the EFFECTS clause 3) the polarity of the comparison: < vs. > It seems silly to have to write what amounts to almost the same function twice. And, in fact, it *is* silly. Function pointers to the rescue! So far, we've only defined functions as entities that can be called. However, functions can also be referred to by variables, and passed as arguments to functions. Here's how it works. There are two functions we want to pick between: min() and max(). They are defined as follows: int min(int a, int b); // EFFECTS: returns the smaller of a and b. int max(int a, int b); // EFFECTS: returns the larger of a and b. The first thing to notice is that these two functions have precisely the same type signature: they both take two integers, and return an integer. Of course, they do completely different things, but that's okay---from a syntactic point of view, you call either of them the same way. Now, we need to know how to define a variable that points to a function taking two integers, and returning an integer. Here's how you say that: int (*foo)(int, int); You read this from "inside out". In other words: foo "foo" (*foo) "is a pointer" (*foo)( ); "to a function" (*foo)(int, int); "that takes two integers" int (*foo)(int, int); "and returns an integer" Once we've declared foo, we can assign any function to it: foo = min; This seems really odd, since we normally only think of functions as things you can call. But, since foo is a variable of the type: "a pointer to a function taking two ints and returning an int" and min's type is "a function taking two ints and returning an int", this is completely fine! Furthermore, after assigning min to foo, we can just call it as follows: foo(3, 5) and we'll get back 3! Now, we can re-write smallest in terms of our new friends function pointers: static int compare_help(int so_far, list_t list, int (*fn)(int, int)) { if (list_isEmpty(list)) { return so_far; } else { so_far = fn(so_far, list_first(list)); return compare_help(so_far, list_rest(list), fn); } } int smallest(list_t list) // REQUIRES: list is not empty // EFFECTS: returns the smallest element contained in list { return compare_help(list_first(list), list_rest(list), min); } This looks just like the old version of smallest. However, the difference is that rather than hard-code the method of comparison (<), we pass a function that does the work for us. Since we are passing min as the function, this walks the list looking for the smallest element. The cool thing is that, given this function, largest() is almost trivial to write: int largest(list_t list) // REQUIRES: list is not empty // EFFECTS: returns the largest element contained in list { return compare_help(list_first(list), list_rest(list), max); } compare_help does all the work and we only have to write it once! Many programmers have great fear of function pointers. Those programmers spend more time writing programs, by duplicating the same function over and over. Because you will not fear function pointers, you will have more free time to do, well, whatever you want.