All of Programming [ PART I ]

answer each time if they start from the same initial state (called a “seed”). Random testing can be appealing, as it can hit a wide range of cases quickly that you might not think of at all. For example, if your algorithm has six parameters, and you decide you want to test 100,000 possibilities for each parameter in all combinations, you will need test cases—even if you can do 10 trillion test cases per second (which would be beyond “fast” by modern standards), they will take about 3 million years to run! With random testing, you could run a few thousand or million cases and rely on the “Law of Large Numbers” to make it likely that you encounter a lot of varieties of relationships between the parameters. One tricky part about generating test cases algorithmically is that we need some way to verify the answer—and the function we are trying to test is what computes that answer. We obviously cannot trust our function to check itself, leaving us a seeming “chicken and egg” problem. In a very few cases, it may be appealing to write two versions of the function that can be used to check each other. This approach is appropriate when you are writing a complex implementation in order to achieve high performance, but you could also write a simpler (but slower) implementation whose correctness you would more readily be sure of. Here, it makes sense to implement both and test the complex/optimized algorithm against the simpler/slower algorithm on many test cases. We often test properties of the answer to see that it correct. For example, if we are testing an algorithm to compute the square root of a number, we can check that the answer times itself produces the original input (that is, that —or is within the expected error given the precision of the numbers involved.3) Testing this property

of the answer assures us that it was correct without requiring us to know (or be able to compute by other means) what it is. The previous technique works well for invertible functions (that is, where we can apply some inverse operation that should result in the original input), but many programming problems do not fit into this case. We may, however, be able to test other properties of the system to increase our confidence that it is correct. For example, imagine that we are writing software to simulate a network, which routes messages from sources to destinations (the details of how to implement this are beyond the skills we have learned so far, but that is not important for the example). Even without knowing the right answer, we can still test that certain properties of the system are obeyed: every message we send should be delivered to the proper destination, that delivery should happen exactly one time, no improper destinations should receive the messages, the delivery should occur in some reasonable time bound, and so on. Checking these properties does not check that the program gave the right answer (e.g., it may have routed the message by an incorrect but workable path), but it checks for certain classes of errors on those test cases. As with all test cases, this increases our confidence that the program is right but does not prove that it is right. Of course, we would need to test the other aspects of the answer in other ways—which may involve looking at the details of fewer answers by hand to ensure all details are right. This approach requires development of code that is not part of the main application—a program that not only sends the requests into the network model, but also tracks the status of those requests and checks for the proper outcomes. This additional program is called a test

harness—it is a program you write to run and test the main parts of your code. Developing such infrastructure can be time-consuming but is often a good investment of time, especially for large projects. 6.1.4 Asserts In any form of testing, it can be useful to not only check the end result, but also that the invariants of the system are maintained in the middle of its execution. An invariant is a property that is (or should be) always true at a given point in the program. When you know an invariant that should be true at a given point in the code, you can write an assert statement, which checks that it is true. assert(expr); checks that expr is true.4 If it is true, then nothing happens, and execution continues as normal. However, if expr is false, then it prints a message stating that an assertion failed, and aborts the program— terminating it immediately wherever it is. As an example, recall the printFactors function from one of the practice problems for Chapter 4. We could add some assert statements to express invariants of our algorithm: 1 void printFactors(int n) { 2 if (n <= 1) { 3 return; 4} 5 int p = 2; 6 while (!isPrime(n)) { 7 assert(isPrime(p)); //p should always be prime 8 assert(p < n); //p should always be less 9 if (n % p == 0) { 10 printf(\"%d * \", p); 11 n = n / p; 12 } 13 else { 14 p = nextPrimeAfter(p); //helper function to 15 }

16 } 17 printf(\"%d\\n\", n); 18 } Here, we have added two assert statements. The first, on line 7, checks that p is prime (using our isPrime function). This fact should always be true here—if it is not, our algorithm is broken (we may end up printing non- prime factors of the numbers, which is incorrect). How could such an error occur? One possibility would be a bug in nextPrimeAfter—the helper function we have written to find the next prime after a particular prime. Another possibility would be if we accidentally modify p in a way we do not intend to. Of course, if our code is correct, neither of these will happen, and the assert will do nothing, but the point is to help us if we do make a mistake. The second assert checks another invariant of our algorithm: p should always be less than n inside this loop (think about why this is). As with the first assert, we hope it has no effect—just checking that the expression is always true—but if something is wrong, it will help us detect the problem. Note that assert statements are an example of the principle that if our program has an error we want it to fail fast—that is, we would rather the program crash as soon after the error occurs as possible. The longer the program runs after an error occurs, the more likely it is to give incorrect answers and the more difficult it is to debug. Ideally, when our program has an error, we will have an assert fail immediately after it, pointing out exactly what the problem is and where it lies. In almost all cases, giving the wrong answer (due to an undetected error) is significantly worse than the program detecting the situation and crashing. To see this

tradeoff, consider the case of software to compute a missile launch trajectory. If there is an error in such software, would you rather it give incorrect launching instructions or print a message that an error occurred and abort? Many novice and intermediate programmers worry that asserts will slow their program down. In general, the slowdown is negligible, especially on fast modern computers. In many situations, 1–2% performance just does not matter—do you really care if you get your answer in 0.1 seconds versus 0.11 seconds? However, there are performance-critical situations where ever bit of speed matters. For these situations, you can pass the - DNDEBUG option to the compiler to turn off the asserts in your optimized code. For all other situations, keeping them active is generally advisable. Note that performance-critical code is the domain of expert programmers who also have a deep understanding of the underlying hardware—such is well beyond the scope of this book. 6.1.5 Regression Testing Another important consideration in real software is that your program changes over time. In “the real world,” your requirements may evolve (as your customers request new features or you release one version and move on to the next). You may also be fixing bugs or going back to add more complex functionality that you originally skipped in the interest of getting simpler parts working. Whatever the reason for your changes, you want to be sure that your modifications have not broken existing functionality—this is the job of regression testing. Regression testing is the process of running a set of test cases—your regression test suite—that have worked

in the past to ensure they still work on your current code. Regression tests are usually automated (e.g., via a shell script) and run frequently to detect newly introduced problems regularly. On large software projects with many developers, a common practice is to run “nightly regressions”—run the regression test suite on the code each night (when development is presumably less active) to detect bugs introduced during the day. Other development practices may involve running a regression test suite before checking the code into the revision control system (e.g., Git, Subversion, or Mercurial). 6.1.6 Code Review Another technique to increase your confidence in the correctness of your program is a code review. In a code review, another skilled programmer reviews the code you have written, looking for mistakes you might have made. Such a review is another way to address the “how to test for problems you did not think of” problem—the reviewer brings a fresh perspective to the code and may identify areas of concern you did not think about. Code reviews have one nice advantage over other forms of testing: often when your reviewer identifies a problem, she can propose steps towards fixing it. One form of code review is a code walk-through in which the programmer explains the algorithm and code to the reviewer. Typically, the reviewer is familiar with the problem and algorithm required to solve it, so the walk- through focuses on the code itself. The programmer goes line-by-line through the code, explaining to the reviewer what each line does, and why it is there. If the reviewer is not familiar with the problem/algorithm, the walk-through process may start with the programmer walking the reviewer through earlier steps of the programming

process—possibly even starting from Step 1: Work an Example Yourself. 6.2 Step 7: Debug Your Code Once you have found a problem in your code, you need to fix it—this process is called debugging. Many novice programmers (and even some moderately experienced programmers) debug in an ad hoc fashion—trying to change something in their code and hoping that it will fix their problem. Such an approach is seldom effective and often leads to much frustration. Returning to our doctor analogy from earlier, suppose you were sick and went to the doctor. Does your doctor say “Oh I don’t know what is wrong, but try this medicine. If it doesn’t fix things, come back tomorrow and we’ll try another medicine.” If your doctor does treat you this way, it might be time to find a new doctor! Trying random “fixes” in the hope that you will get lucky on one is not a good way to diagnose and fix problems. Even worse, if your symptoms change during this process, you have no idea if one of the random “fixes” you tried made things worse, or if your untreated condition is progressing. Similar analogies can be made to any profession that diagnoses and fixes problems (such as mechanics). Hopefully, your doctor (and mechanic) follow a more scientific approach to diagnosing and fixing problems. As do they, so should you in diagnosing and fixing your program. In fact, debugging should be an application of the scientific method, which you may have learned in a science class.

Figure 6.3: The scientific method. 6.2.1 Observe a Phenomenon Figure 6.3 shows a flowchart of the scientific method. All science starts with observing some phenomenon. In the natural sciences this might be noticing that objects fall towards the ground when not supported by anything, that finches in certain of the Galápagos Islands have different characteristics from other finches, or that the water level rises when you get into the bathtub. In programming, our observation of phenomena relates to the behavior of our programs on certain inputs (“My program gives the wrong answer when I give it an input of 42!”). These observations typically arise from our test cases but may happen under other circumstances (for example, the end user reports a problem we did not discover in testing). 6.2.2 Ask a Question Once you have observed a phenomenon, the next step in the scientific method is to ask a question. Asking a good question here is crucial to the success of the rest of our scientific endeavor. While a broad question such as “What is wrong with my program and how do I fix it?” may seem appealing, it may be quite difficult to answer. Instead, we should aim for more focused questions: “On which line of code does my program crash?” or “Why

does my program call myFunction with x = 3 and y = -42?”. Answering one question often leads to an observation that leads to another question—restarting the scientific process all over again. Discovering what is wrong in this iterative fashion is perfectly fine, and is in fact a great way to proceed. You start by asking “Which line does my program crash on?” then when you answer that, you ask “Why does it crash on this line?” the answer to that then leads you to ask “How is x = 3 and y = -42?” which in turn leads you to ask another question, and so on. Eventually, your chain of questions and answers leads you to the discovery of the problem, even if it is somewhat far removed from the visible symptom. 6.2.3 Gather Information and Apply Expert Knowledge Many people will say that forming a hypothesis is the next step of the scientific method. If you can form a hypothesis immediately, that is great. However, forming a good hypothesis is difficult, and forming one right away is often not possible. The next step of the scientific method is actually to gather information and combine it with your expert knowledge. Going back to our example of visiting the doctor, the doctor gathers information by examining the patient and combines it with her expert knowledge— years of training on symptoms of diseases and how the body works—to form a hypothesis. In the case of debugging, you need to gather information about what is happening in your program and combine this with your own expert knowledge on

programming. Your expert knowledge comes in two parts here. One is your knowledge of programming in general —the rules for how to execute code by hand that we learned in Chapter 2 (and will continue learning as we introduce more topics), and the other is your domain knowledge of the particular program you are writing—the expected behaviors of each part of it. Your expert knowledge will grow with practice in programming and the domain for which you are writing programs. However, gathering information effectively is a skill of its own. The information-gathering aspect of debugging is often conflated with the entirety of debugging—if you ask someone how they debug, they will often explain to you what techniques they use to gather information. The simplest way to gather information is to insert print statements (in C, calls to printf) to display the values of various variables at various points in the program. The resulting output can give you information about the control flow of the program (which statements were executed, and in what order—as shown by what order your print statements print their output), and of course the values of the variables you print. Gathering information by printing has the advantages that it is simple and requires no other knowledge or experience. However, it has several disadvantages as well. One is that changing what you print out requires recompiling and re-running your program. While this disadvantage may seem small, if your bug takes 15 minutes to manifest, restarting the program for each new piece of information you discover that you want can be quite time-consuming. Another disadvantage is that the output may be overwhelming (i.e., thousands of lines of output to sift through) if your program executes for even a

modest time before experiencing the problem. A third disadvantage is that it cannot replicate or replace many features that debuggers offer. Another approach to information gathering is to use a debugger—a tool specifically designed to aid programmers in the debugging process. The debugger is in fact primarily aimed at this piece of the debugging process—gathering information (sadly, it does not offer you hypotheses or expert knowledge). One widely-used debugger is GDB, which we cover in detail in Section D.2. We strongly recommend that you learn it, and if you intend to become a serious programmer, become an expert in it. We will mention generally what you can do with it here, but leave the details to Section D.2, as GDB has features that we relate to topics we have not learned yet. For now, we will discuss the high-level points of a debugger. When you run your program inside the debugger, you can give the debugger a variety of commands to control the execution of your program and get information from it. Note that Emacs understands how to interact with GDB, and using them together makes the entire process go much more smoothly. When you run your program inside of a debugger, it will run as normal until one of the following happens: (a) it exits, (b) it crashes5, or (c) it encounters a breakpoint (or watchpoint) you have set. A breakpoint is set on a particular line of code and instructs the debugger to stop the execution of your program whenever the execution arrow is on it. Breakpoints can be conditional—meaning you can specify that you only want to stop on some particular line when a conditional expression you specify is true. Watchpoints specify that you want to stop the program when a particular “box” changes.

Once your program is stopped, you can examine the state of the program by printing the values of expressions. The debugger will evaluate the expression and print the result for you—giving you information about the state of the program. Most often, you will want to print the values of variables to see what is going on, though you may print much more complex expressions if you wish. After printing some information, you will often want to continue executing in some fashion—either running until the debugger would stop naturally (as described above), or maybe just executing one more statement, then stopping. The debugger gives you the ability to choose either one. If you want to execute one statement at a time, and the current statement involves a function call, you have two options. You can either step over the call (asking the debugger to evaluate the entire function call and stop on the next line of the current function), or you can step into the function call (asking the debugger to follow the execution arrow inside the function and let you explore what is happening inside it). This approach to gathering information is more flexible than print statements—if you encounter one oddity, which suggests other things you need to explore, you can print them immediately. By contrast, if you print the value of a variable with a print statement, adding more print statements to investigate other variables requires recompiling and rerunning the program. The previous paragraph alludes to a common occurrence in the debugging process: recursive observations—gaining some information (e.g., seeing the value you printed for one variable) leads you to want some other information (e.g., to print some other variable). Often when you are investigating one

phenomenon (“My program crashes when I enter 3…”), you observe some other phenomenon (“y is 0 on line 42..”), which itself leads to a question meriting investigation (“How did that happen?”). The investigation of this second phenomenon proceeds according to the scientific method. In such a case, you are recursively applying the scientific method. We will learn about recursion as a programming technique in Chapter 7, but for now it suffices to say that recursion is when an algorithm (in this case, the scientific method) has a step that calls for you to apply the same algorithm to “smaller” (by some metric) inputs. Here, investigating the second observation may immediately solve your problem, may give you useful information to allow you to proceed, or may prove to be a red herring (something that was actually fine, but just surprised you—in which case, you just continue gathering information for your original question). 6.2.4 Form a Hypothesis The whole point of gathering all of this information is to help you form a hypothesis. Sometimes, you may be able to form a hypothesis right away—typically for problems that are simple relative to your experience level. However, forming a good hypothesis is generally hard and requires significant information gathering. Forming a good hypothesis is the key to proceeding effectively. A vague hypothesis is hard to test and not so useful in identifying the problem. As an extreme example, the hypothesis “My program is broken” is easily verified, but rather useless. The hypothesis “My program is dividing by 0 on line 47 for certain inputs” is more useful, but could be improved. Even better would be “My program is dividing by 0 on line 47 if y is odd and z is a

perfect square.” This (contrived) hypothesis is specific and clear—giving it two important characteristics for debugging. The first characteristic of a good hypothesis that this exhibits is that it is testable. For a hypothesis to be testable, it must make specific predictions about the behavior of the program: when I give the program inputs that meet (condition), I will observe (behavior). For such a hypothesis, you can execute test cases to either refute this hypothesis (e.g., if the program’s behavior does not match the predictions that the hypothesis makes) or to become confident enough in your hypothesis that you accept it.6 The contrived hypothesis we presented at the end of the previous paragraph is quite testable: we specify a certain category of inputs (y is odd and z is a perfect square) and exactly what behavior we expect to observe (division by 0 on line 47). The second characteristic of a good hypothesis for debugging is that it is actionable—if we convince ourselves that it is true, it provides us with an indication of either how to fix the error in our code, or what the next steps towards it are. In the case of our contrived hypothesis, confirmation would likely suggest a special case of the algorithm we did not consider. The fact that our hypothesis is specific (with regards to what types of inputs trigger the error) identifies the corner cases for us, guiding us to the path to fixing the problem. 6.2.5 Test the Hypothesis Once we have formed our hypothesis, we want to test it. In the simplest case, this may be trivial, as the evidence in front of us immediately convinces us beyond any doubt. If our hypothesis is “When x is 0, line 57: y / x

crashes the program.” and we just formed this hypothesis by printing x in our debugger when the program crashed on line 57, then we are already convinced the hypothesis is true. In such a case, we accept the hypothesis immediately and move on with no further testing. However, do not be lulled into a false sense that you should often or eagerly accept your hypothesis without any further testing. Ten or twenty minutes spent testing a hypothesis you are “pretty sure of” is a much better investment of your time than wasting five–10 hours making a larger mess of your code because you are acting on incorrect information. To illustrate the benefits of such a tradeoff, suppose that your notion of “pretty sure” corresponds to your hypothesis being correct 95% of the time—meaning your hypothesis is wrong one time in 20. On the one hand, if you spend (on average) 10 minutes testing each of 20 hypotheses, that amounts to 200 minutes (three hours, 20 minutes) of testing. On the other hand, if you blindly proceed, assuming your hypotheses are correct with no further testing—in 19 out of 20 cases, you will save yourself 10 minutes. However, in the case where you are incorrect, you might waste five–10 hours “fixing” your code based on an incorrect hypothesis about its broken behavior! This tradeoff represents a false economy—you think you are saving time by skipping the testing of the hypothesis, but you are actually wasting more time than you have saved when you are incorrect. You may think those time ratios sound a bit exaggerated, but once you convince yourself of incorrect information, it is quite easy to “go down the rabbit hole.” You make one seemingly logical conclusion from your false information after another. Once you change your code based on incorrect information, you are breaking

your code even more—introducing new errors rather than fixing the existing one(s). You now have to debug all of these problems, which is even harder because you are convinced of a false premise. Debugging when you are convinced of a false premise is especially frustrating because you start to reach a point where nothing makes sense. This frustration makes such situations especially important to avoid. Testing our hypothesis may proceed in a variety of ways—sometimes by a combination of them—such as: Constructing test cases. Sometimes our hypothesis will suggest a new test case (in the sense of the testing we discussed in Section 6.1), that we can use to produce the error under a variety of circumstances. Generally, these follow from the specific cases that your hypothesis makes predictions about: “My program will (something) with inputs that (something).” When your hypothesis suggests this sort of result, construct a test case with the values you were thinking of, and see if your program exhibits that behavior. Also, construct other test cases that do not meet the conditions to see if you were too specific. Inspecting the internal state of the program. We can use the same tools we used for gathering more information (print statements or the debugger) to inspect the internals of the program. This sort of testing is particularly useful when our hypothesis suggests something about the behavior or our program in its past—before it reaches the point where we observe the symptom. This past may be recent (“…but that means in the previous

iteration of the loop…” or “then x had to be odd on the last line….”) or the distant past (“… but for that to be the case, I had to have deleted (something) from (some data structure)…” or “…then y’s value has to have changed in a way I did not expect…”). Here we want to use the debugger to inspect the state we are interested in and see if it agrees with our hypothesis. Frequently, when we take this approach, discovering the surprising change in state will give us a clue to the problem. Adding asserts. Earlier, we discussed asserts as a testing tool; however, they are also useful for debugging. If our hypothesis suggests we are violating an invariant of our algorithm, we can often write an assert statement to check this invariant. If the assert does not fail, we refute the hypothesis. If the assert fails, it not only gives us confidence in our hypothesis, but also makes our program fail faster—the closer it fails to the actual source of the problem, the easier it is to fix. Code inspection. Another method to test your hypothesis is to inspect and analyze your code. Sometimes a simple hypothesis can be tested with a quick inspection. For example, if you hypothesize that you forgot to initialize a particular variable, you can frequently just look at the relevant portion of the code and see whether or not you have an initialization statement or not. While this technique is generally the best for “easy” hypotheses (such as the one just described), it typically

becomes much harder as you deal with more complex hypotheses. Of course, here “difficult” is relative to the programmer’s skill level. Novice programmers who seek the help of a much more experienced programmer may get the wrong impression about the debugging process by seeing their problems debugged by inspection. While the problems that the novice programmer faces seem complex and daunting, the experienced programmer—for whom the problems are easy and familiar— may debug it by inspection in a matter of seconds. Unfortunately, many novice programmers faced with such an experience take away the wrong lesson: debugging is magic or lucky guesswork. As we test, we will either convince ourselves that our hypothesis is correct and accept it, or we will find that it is not true and reject it. In the former case, we now know what is wrong with our program and are ready to correct it. Typically, identifying the precise problem and cause are 90% of the battle—thus if our hypothesis was a good one, we are most of the way there. Of course, sometimes our problem is severe and requires significant modifications to our program. In the worst cases, a significant redesign and implementation of large portions of the code from scratch. The decision to throw away large portions of code and redo them from scratch is not one to be taken lightly, nor an easy one to make. In making such a decision, the programmer should be wary of The Poker Player’s Fallacy—the temptation to make a decision based on prior investments rather than future outcomes. This term

comes from a fallacy that many novice poker players succumb to: betting based on how much they have already put into the pot, rather than how likely they are to win the hand (“I’m already in for $200, so I may as well bet another $10 on the off chance I win.”). If you are not likely to win the pot, betting another $10 is just throwing that money away. The smart poker player will only bet on her current hand if she thinks she can win (whether by a better hand or a bluff). Similarly, when evaluating whether to modify the current code or throw it away and start fresh, you should not consider how much time you have already put into it, but rather how much time it will take to fix the current code versus redesigning it from scratch. Note that this is not intended to suggest you should throw away your code and redesign it from scratch every time there is an error. Instead, you should contemplate the time required for both options and making a rational tradeoff. If instead of accepting your hypothesis, you find that you must reject it, do not despair. In investigating this hypothesis, you have gained valuable information that will inform your next hypothesis. You may find a new hypothesis immediately after you reject your current one (“Aha! the problem is not if z is even, but rather if it is a multiple of 8!”). If not, return to the information gathering stage and repeat the hypothesis formation process. One thing to be wary of when rejecting a hypothesis: there may be multiple errors in your code. Do not be mislead by symptoms of other errors masking your current problem. For example, suppose that the program you are testing and debugging has two errors in it. One of these errors causes the program to crash on line 99 if x is a multiple of 17. Another error causes the program to crash before it reaches lines 99 if x is greater than

10,000. You have formed a hypothesis that accurately describes the first error and are testing it with x=17,000 (which is a multiple of 17 and greater than 10,000). The fact that the program crashes sooner than we expect should not cause us to reject the hypothesis immediately. We must instead consider the possibility that there is another error that is triggered by overlapping conditions. When faced with such a possibility, we have two options. One option we might take is to defer our investigation of the first error while we try to debug the second. If we can fix this second error, we can retest the case and find that it does not contradict our original hypothesis on the first error. The other option we have is to confirm our suspicion that the difference in behavior (between what we observed and what we hypothesized) is in fact a symptom of a different problem, then proceed with testing the current hypothesis. Here, we must proceed with caution—we do not want to reject a valid hypothesis, but at the same time we must be careful not to accept a false one. We should confirm that the test case in question is actually not triggering the situation we intended to test—perhaps it is not reaching that point in the code, or not exhibiting the intended circumstances when it does reach that point. Once we have confirmed that the test case is not actually testing the hypothesis, we can continue with other cases. Of course, after we fix the current error, we should return to this case and find out what the other error is. 6.3 Practice Exercises Selected questions have links to answers in the back of the book.

• Question 6.1 : Why do we consider a test case that fails to be a good test case? • Question 6.2 : What is an assert statement? • Question 6.3 : Why do we want our code to “fail fast”? • Question 6.4 : In our discussion of black box testing, we considered an example of a function that sums a list of integers. We suggested that one might want to test on a list with negative numbers and on a list with many very large integers. What errors in the code might these cases expose? (Hint, think about what you learned in Chapter 3) • Question 6.5 : The C library has a function int abs(int i). Devise a set of black box test cases for this function. As with all testing, you should try hard to think of the difficult cases. Can you think of a case that will cause it to give the wrong answer? Hint: think about what you learned in Chapter 3 about how numbers are represented. In particular, you should try to come up with a number where abs(n) results in a negative number —e.g., one that makes this function print its message: 1 #include <stdlib.h> 2 #include <stdio.h> 3 4 void f(int x) { 5 int y = abs(x); 6 if (y < 0) { 7 printf(\"abs(%d) = %d. That can’ 8} 9} • Question 6.6 : Suppose I am testing the following function: 1 int something(int a, int b) { 2 int x = b - a; 3 int y = 1; 4 if (x > 0) {

5 y = x * (x + 1); 6} 7 if (y > a) { 8 return 42 - y; 9} 10 return y - b; 11 } and I use the following test cases (in this order): 1. 2. 3. 4. 5. 6. At what point do I have statement coverage of this function with my test cases? How about decision coverage? Path coverage? • Question 6.7 : Use the debugger to win the guessing game, whose code is shown below, in one guess. 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <sys/time.h> 4 5 int main(void) { 6 int guessesMade = 0; 7 int yourGuess; 8 char buffer[1024]; 9 struct timeval now; 10 //using the time to seed the random num 11 //is not very secure, but that doesn’t m 12 gettimeofday(&now, NULL); 13 srandom(now.tv_usec); 14 15 int myNumber = random(); 16 17 printf(\"I’m thinking of a number. 18

19 do { 20 if (guessesMade > 0) { 21 printf(\"Sorry that is not rig 22 } 23 printf(\"What number do you gues 24 if (fgets(buffer, 1024, stdin) 25 printf(\"Oh no, you are giving 26 return EXIT_FAILURE; 27 } 28 yourGuess = atoi(buffer); 29 guessesMade++; 30 } while (yourGuess != myNumber); 31 32 printf(\"That is correct, you won 33 return EXIT_SUCCESS; 34 } 5 Compiling and Running7 Recursion Generated on Thu Jun 27 15:08:37 2019 by L T XML

I Introduction to Programming in C6 Fixing Your Code: Testing and Debugging8 Pointers

Chapter 7 Recursion The ability to repeat the same computation (with different values for the variables) is key to many algorithms. So far, the algorithms we have seen have used iteration to express this repetition—they have used loops to repeat the steps until the appropriate conditions are met. However, there is another approach called recursion, in which the algorithm calls itself with different parameter values. Recursive functions—those that call themselves—are important to understand because many algorithms are much easier to write recursively. We will note that any function you can write recursively you can write iteratively and vice versa. However, for some problems, one style of algorithm may be simple, while the other may be quite complex. Mastering both is crucial to becoming a skilled programmer. 7.1 Reading Recursive Code As we typically do, we will start by learning to read before we learn to write. However, unlike most things we will encounter, there is actually not anything new to learn—we just follow the same rules that we have already learned. In fact, one of Chapter 2’s practice questions even had a recursive function for you to execute by hand. However, we will still remind you of the rules for executing function calls and underscore how they are exactly the same for a recursive function. We will start by working with the factorial function as an example. Recall that in math, the factorial of a number (written in math notation) is One thing you may notice here is that the mathematical definition of the function is recursive—the general case of is expressed in terms of the factorial of a smaller number ( ). Since the problem itself is recursive, a recursive algorithm is a natural choice. We will see how to

go about devising and implementing an algorithm in Section 7.2, but for now, we will just work from the following code, which computes factorial: 1 int factorial(int n) { 2 if (n <= 0) { 3 return 1; 4} 5 return n * factorial(n - 1); 6} If you take a second to examine this code, you will see that everything in it is something we have seen. Line 1 tells us that this function is called factorial, takes an int n, and returns an int. Line 2 has an if statement with a conditional expression (n <= ), which should be imminently familiar by now. Line 3 contains the “then” clause of the if statement, which just returns 1. Line 5 returns an expression that is the result of multiplying n by the result of calling the factorial function with the argument n - 1. Video 7.1: Executing the recursive factorial function by hand. Whenever our execution arrow reaches Line 5, we do everything exactly as we learned in Chapter 2. We multiply n (which we would read out of its box) by the value returned by factorial(n - 1). To compute factorial(n - 1)—which is itself a function call—we would need to draw a stack frame for factorial (with a box for the parameter n), compute n - 1 and copy it into the box for the parameter, note down where to return to, and move our execution arrow into the start of the factorial function. Video 7.1 walks through the execution of factorial(3). 7.2 Writing Recursive Functions Recall that in Section 4.5 we learned that when translating your steps to code, a complex step should be translated into a call to a function. If you do not already have a function that performs the task you require, you go and write that function once you finish the current one. Writing a recursive function is actually just a special case of this principle: the function we need to call just happens to be the one we are writing. If we are willing to accept that this function will work correctly when we finish it, then it is exactly what we need to use. At this point, many novice programmers are confused by the seeming “magic” of recursion: if you can just call the function you are

writing, why not just write 1 int factorial_broken(int n) { 2 return factorial_broken(n); 3} Surely, if the computer can figure out the “magic” of a function calling itself in our first example, it can do the same magic here. Of course, recursion is not actually magic. In our first example of factorial, we could execute factorial(3) by hand and come up with the correct answer. If we try to execute factorial_broken(3), we will actually never come up with an answer. Instead, we will recurse infinitely—that is factorial_broken(3) will just call factorial_broken(3), which will just call factorial_broken(3), and so on, forever. Executing this code by hand, we would quickly realize the problem, and stop. The computer, on the other hand, does not reason, and would continue following our instructions, until stopped by something—when it either runs out of memory to make frames, or when the user kills the program. Instead, let us better understand recursion by examining some key differences between the two functions. One key difference is that the first function was obtained by following the Seven Steps to write a program, and the recursive call corresponded to something we actually did in trying to solve the problem. By contrast, the factorial_broken function corresponds to saying “Look, the way you compute factorial is to just compute the factorial.” Such a statement is pretty useless in telling you how to perform the required task—although it does lend itself to the joke, “All you have to do to write a correct recursive function is write a correct recursive function.” The second difference is that the factorial function has a base case—a condition in which it can give an answer without calling itself—in addition to its recursive case—when the function calls itself. In this particular function, the base case is when n <= —the function just returns 1 without further work. Another important aspect of the correct factorial function is that the recursive calls always make progress toward the base case. In this particular case, whenever factorial calls itself, it does so with a smaller parameter value than its own (factorial(3) calls factorial(2), which calls factorial(1), which calls factorial(0)). Video 7.2: Writing factorial recursively. Now that we have some general principles in mind, it is time to see how we wrote the factorial function we saw earlier. Video 7.2 walks

through Steps 1–5 of the programming process for the factorial function. Another mathematical function that lends itself naturally to recursion is the Fibonacci function. The Fibonacci function is defined as follows: Video 7.3: Writing Fibonacci recursively. Video 7.3 shows Steps 1–5 of the programming process for the Fibonacci function. Observe that the resulting function has two base cases—if n is 0 or 1, and that all recursive calls make progress towards the base cases. If n is negative, the function negates it and recurses— this is “progress” since we then always work with positive numbers. If n is greater than 2, the function recurses on n - 1 and n - 2– which means that n is strictly decreasing as long as it is positive. The fact that we do n - 2 makes it important that 0 and 1 are both base cases. If 1 were not a base case, then fib(1) recursing on fib(n - 2) would call fib(-1), which would then call fib(1), which would then call fib(-1), and we would recurse infinitely. We will note that this implementation of the Fibonacci function is quite slow, even for moderately sized n. On my computer, computing fib(46) takes about 8 seconds—quite a long time for the computer. One incorrect conclusion that perpetuates as a bit of an “urban myth” is that recursion is slow. What is actually happening here is that the way that we have written our fib algorithm duplicates work—our implementation will compute fib(44) twice, fib(43) three times, fib(42) five times, fib(41) eight times, …, fib(1) 1,836,311,903 times, and fib(0) 1,134,903,170 times!1 In total, evaluating fib(46) will require 5,942,430,145 total calls to the Fibonacci function. Video 7.4 illustrates this duplication of work for fib(5). Video 7.4: Duplication of computation in Fibonacci. The problem here is not that recursion is slow. It is that algorithms that recompute the same thing millions of times are slow. For the moment, we are not terribly concerned with performance—we want to

focus on learning to write correctly working code. However, there are times when performance matters. In some cases, a horribly inefficient/slow algorithm such as this would be unacceptable, but anything reasonable works fine. In other cases, every last bit of performance counts, and highly skilled (and well-paid!) programmers spend hours refining their code for speed. What could we do if we had an algorithm such as this, but the slow performance were unacceptable? We need to find some way to express our algorithm such that it does not repeat work it has already done. In the case of Fibonacci, we could rethink our algorithm to work up from 0 and 1 (computing fib(2), then fib(3), then fib(4), and so on)—at any step, we just add together the previous two values (we compute fib(5) by adding together whatever we just computed for fib(3) and fib(4)). However, rethinking the algorithm may be tricky—to come up with a different approach, you need to convince yourself to think about the problem differently. Another way to fix the performance problem without changing the underlying algorithm is memoization2 —keeping a table of values that we have already computed and checking that table to see if we already know the answer before we recompute something. We will learn later how to efficiently store and look up data, which would make a memoized version of the function quite fast. 7.3 Tail Recursion The recursive functions we have seen so far use head recursion—they perform a computation after they make a recursive call. In the factorial example, after the recursive call to factorial, the returned result is multiplied by n before that answer is returned. There is another form of recursion called tail recursion. In tail recursion, the recursive call is the last thing the function does before returning. That is, for a tail-recursive function f, the only recursive call will be found in the context of return f(...);—as soon as the recursive call to f returns, this function immediately returns its result without any further computation. A generalization of this idea (separate from recursion) is a tail call— a function call is a tail call if the caller returns immediately after the called function returns, without further computation. Put another way: if function f calls function g, then the call to g is a tail call if the only thing f does after g returns is immediately return g’s return value (or if f’s return type is void, just return). These two concepts tie together in that a recursive function is tail-recursive if and only if its recursive call is a tail

call. To understand this definition, let us look at a tail-recursive implementation of the factorial function: 1 int factorial_helper(int n, int ans) { 2 //base case 3 if (n <= 0) { 4 return ans; 5} 6 //recursive call is a tail call 7 //after recursive call returns, just return its answer 8 return factorial_helper(n - 1, ans * n); 9} 10 int factorial(int n) { 11 return factorial_helper(n, 1); //tail call 12 } Here we have a tail-recursive helper function—a function our primary function calls to do much of the work. Helper functions are quite common with tail recursion but may appear in other contexts as well. The helper function takes an additional parameter for the answer, which it builds up as it recurses. The primary function just calls this function, passing in n and 1. Notice how the recursive call is a tail call. All that happens after that call returns is that its result is returned immediately. Note: the tail-recursive version of factorial does no less work than the original recursive version. In the original recursive version, the factorial of a number is created by a series of multiplications that occur after each recursive call. In the tail-recursive version, this multiplication takes place prior to the recursive call. The running product is stored in the second parameter to the tail-recursive function. Video 7.5: Execution of the tail-recursive implementation of factorial. Video 7.5 shows the execution of factorial(3) using this tail- recursive implementation. We will note that in this video (and many videos in the future), we elide the main calling factorial—even though all programs start with main, we will sometimes just show a program starting in the middle for the sake of brevity. In such videos, we will just start with the execution arrow inside the function and a frame set up for it with whatever arguments we want to demonstrate it with. You can imagine that this function was called by main (or some other function, which itself was called by main). After you watch this video, take a moment to write factorial using iteration (loops), and execute it by hand for n = 3. Do you notice any similarities between the iterative execution and the tail recursive execution? What about differences? Take a minute to try this out

(possibly re-watching the video after you do the iterative implementation/execution of factorial) before you proceed. To be concrete, let us consider the following iterative implementation of the factorial function: 1 int factorial(int n) { 2 int ans = 1; 3 while (n > 0) { 4 ans = ans * n; 5 n--; 6} 7 return ans; 8} Executing both of these implementations of the factorial function by hand shows that they behave pretty much the same way. The main difference is that the recursive function creates multiple frames, whereas the iterative function does not. However, an optimizing compiler will perform tail-recursion elimination and reuse the current frame on a tail- recursive call. Because the function returns immediately after the tail call completes, the compiler recognizes that the values in the frame will never be used again, so it can be overwritten. In fact, tail recursion and iteration are equivalent. Any algorithm we can write with iteration, we can trivially transform into tail recursion, and vice versa. A smart compiler will compile tail-recursive code and iterative code into the exact same instructions. In general, if we have a loop that looks like this (note that this is not truly C, but rather pseudo-code—it is code-like, but not exactly code): 1 t1 var1 = expr1; //t1..tN are types (like int) 2 t2 var2 = expr2; 3 ... 4 tN varN = exprN; 5 6 while(condition) { //whatever conditional expression 7 someCode; //we might do some other code here, eg printing thin 8 var1 = update1; 9 var2 = update2; 10 ... 11 varN = updateN; 12 } 13 return ansExpr; //some expression like var1 + var2 * var3 We can transform it into a tail recursion that looks like this3: 1 appropriateType helper(t1 var1, t2 var2, ..., tN varN) { 2 if (!condition) {

3 return ansExpr; 4} 5 someCode; 6 return helper(update1, update2, ..., updateN); 7} The inverse is also true—we can convert tail recursion to a while loop by doing the reverse. 7.4 Functional Programming The equivalence of tail recursion and iteration is especially important for functional programming languages. In a purely functional language, you cannot actually modify a value once you create it (at least not from the standpoint of the language: the compiler is free to reuse the same “box” if it can conclude you will never use it again). As such, there are not loops (which typically require modifying variables to change the conditions), but rather only recursive functions. What you would typically write as a loop, you instead just write as a tail-recursive function. Functional programming is a beautiful thing, and we highly recommend that any serious aspiring programmer become fluent in at least one functional language. One of the authors particularly loves SML (see Chapter 33) and highly recommends it. Even if your main line of programming work is in some other language (such as C, Java, C++, or Python), having experience in a functional language helps you think about problems in different ways and makes you a better programmer all around. Of course, you may also end up using a functional language for your primary work. 7.5 Mutual Recursion We may also find it useful to write some functions using mutual recursion—two or more functions that call each other. Recall that recursive functions come up when our generalized steps call for us to solve the same problem on parameter values closer to the base case(s). Mutually recursive functions occur when we write one function, find a complex step we want to abstract out into a second function, then go to write that second function, only to find a complex step that exactly matches the first function. Here, we again need to be careful to make sure the mutually recursive pair makes progress toward a base case, which does not require recursion—otherwise, we will recurse infinitely, and our program will not terminate.

As a (somewhat contrived) example, suppose we did not have the modulus (%) operator available and wanted to write a function to figure out if a positive number is even. We might start from the fact that 0 (is even) and 1 (is not even) are easy cases4 and use the fact that n is even if (and only if) n - 1 is odd. Such reasoning would lead us to the following code: 1 int isEven(unsigned int n) { 2 if (n == 0) { 3 return 1; 4} 5 if (n == 1) { 6 return 0; 7} 8 return isOdd(n - 1); //complicated step: abstract into a function 9} We would now need to proceed by writing the isOdd function, which we relied on in implementing isEven. In writing that, we might start from the fact that 0 (is not odd) and 1 (is odd) are easy cases and use the fact that n is odd if (and only if) n - 1 is even. We would then write: 1 int isOdd(unsigned int n) { 2 if (n == 0) { 3 return 0; 4} 5 if (n == 1) { 6 return 1; 7} 8 return isEven(n - 1); //already have a function to do this step 9} These two functions are mutually recursive—they call each other. Note that we will need to write the prototype (recall that the prototype for a function tells the name, return type, and argument types without providing the body) for the second function before the first to let the compiler know about the existence of the second function. The resulting code would look like this: 1 int isOdd(unsigned int n); //prototype for isOdd 2 int isEven(unsigned int n) { 3 if (n == 0) { 4 return 1; 5} 6 if (n == 1) { 7 return 0; 8} 9 return isOdd(n - 1); //complicated step: abstract into a function 10 } 11 int isOdd(unsigned int n) { 12 if (n == 0) { 13 return 0; }

} 1154 if (n == 1) { 16 return 1; 17 } 18 return isEven(n - 1); //already have a function to do this step 19 } Video 7.6 shows the execution of these mutually recursive functions. Note that the calls are tail calls, so the compiler may optimize the frame usage. Video 7.6: Execution of the mutually recursive isOdd and isEven functions. While our example here may be rather contrived (if you want to know if a number is odd or even, it is much more efficient to just test if n % 2 == or not), there are many important uses of mutually recursive functions. One common use is recursive descent parsing. Parsing is the process of analyzing input text to determine its meaning. A recursive descent parser is typically written by writing many functions (each of which parses a specific part of the input), which then mutually recurse to accomplish their jobs. We will not go into the details here, but you can imagine the mutually recursive nature by thinking about C functions and their arguments—for example, if you were writing the parser for a C compiler. At a high level, to parse a function call (f(arg1, arg2,...)) you would write a function parseCall. The parseCall would read the function name, and the open parenthesis, then repeatedly call another function, parseExpression to parse each argument (which must be an expression) —as well as checking if the argument is followed by a comma or a close parenthesis. The parseExpression function itself may encounter a function call, in which case, it would need to call parseCall. Such a situation would occur if the text being parsed looked like this f(3,g(42), h(x,y,z(1)))—some of the arguments to f are themselves function calls, and in fact, one of the arguments to h is also a function call. Such a parse often results in a mutually recursively defined data structure (we will learn more about recursive data structures in Part III)— meaning you have two (or more) types that recursively reference each other. Algorithms to operate on mutually recursive data structures typically lend themselves quite naturally to mutually recursive implementations. Of course, mutually recursive data structures may come up in a variety of other contexts as well. 7.6 Theory

Recursion has a strong relationship to the mathematical proof technique of induction. If you need a quick refresher on induction, it is a technique that lets us prove , where is some proposition about . (Translation: we would like to prove that is true for all positive, whole numbers, .) Proof by induction starts by proving the base case, . The proof then proceeds by showing the inductive case—either proving (weak induction) or (strong induction). The similarities between the two—having a base case and a recursive/inductive case working on smaller values—are not a random coincidence. Our recursive function computes some answer (with certain properties) for all possible inputs.5 The recursive function works by assuming the recursive case works correctly and using that fact to make the current case work correctly—much like the inductive case assumes that the proposition holds for smaller numbers and uses that fact to prove it for the “current” number. In fact, if we wanted to prove that a recursive function is correct, we would proceed by induction—and the structure of the inductive proof would mirror the structure of the recursive function. Recursion is not just limited to the natural numbers (unsigned ints). We can recurse with arguments of different types or on the natural numbers with a different ordering. In general, we can recurse on any set with a well-ordering (that is, a total ordering where every subset of the set has a least element) on it. We have seen this principle in action (though not explicitly discussed the theoretical implications) in our Fibonacci example. Here, our function operated on all integers (positive and negative). Proof by induction over all integers is a bit trickier, since they do not have a smallest value (thus base case) under their standard ordering. Our Fibonacci example was, however, theoretically sound, as we can well-order the integers by having a different ordering (which we will call ). Specifically, for our Fibonacci function, we would want the ordering Now, whenever fib(x) recurses to fib(y), we can see that —it is “less” on this well-ordering. We can then prove the function correct by induction using this same ordering.

We can use this principle to perform recursion (and correspondingly, induction) over types that are not directly numbers (of course, to a computer, everything is a number, as we learned earlier—which we will come back to in a second). Later, when we discuss recursively-defined data structures, such as lists and trees, this principle will be quite useful —we will want to recurse over the structure of the data. Fortunately, these structures have well-orderings, so we can recurse on them soundly. The “Everything Is a Number” principle actually appears in the mathematical theory related to well-ordered sets. We can take our well- ordered sets and “number” the elements, then just consider the ordering of those numbers. Technically, we may need the ordinal numbers to perform this numbering, but if you are not familiar with them, you can just imagine the natural numbers as being sufficient. All of this discussion of math is not just a theoretical curiosity. Instead, it gives us a formal way of understanding when our recursion is well-founded, versus when we may recurse infinitely. If we can construct a well-ordering of our parameters and show that every time we recurse we are recursing with values that are “less than” (under this well- ordering) what was passed in, we can conclude that our recursion will always terminate—that is, we will never recurse infinitely. Observe that this property implies we have a base case, as the well-ordering has a smallest element, so we are not allowed to recurse on that element (it is impossible to have anything smaller, so we cannot obey the rule of recursing on only smaller elements). This property may sound both wondrous (“Great! I can guarantee my recursions will never be infinite.”) and possibly daunting (“This sounds like a lot of math…My knowledge of well-ordered sets and the ordinals is kind of rusty.”). Fear not—for many recursive tasks, this ordering is much simpler than it sounds. We can make a measure function, which maps the parameter values to the naturals (or ordinals if needed) and convince ourselves that the measure decreases with every recursive call. For lists, we might measure them with their length, for trees we might measure them with their height, and so on. For most programming tasks, you will not actually need to formally prove any of this—you will just want to convince yourself that it is true to ensure you do not recurse infinitely. 7.7 Practice Exercises Selected questions have links to answers in the back of the book.

• Question 7.1 : Use recursion to write the function int pascal(int i, int j), which returns the number in the row and column of Pascal’s triangle (we will consider the first row and first column to be numbered , ). If and lie outside the triangle, your function should return 0. Recall that Pascal’s triangle looks like this: 1 11 12 1 13 31 14 641 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 ....continues infinitely..... Write a main function that tests your code with several values, and convince yourself it is correct. • Question 7.2 : The following code approximates the square root of a double and returns that approximation (Note: if you actually need the square root of something, just use the built in sqrt function (found in math.h)—which is faster and more accurate). 1 double mySqrt(double d) { 2 double lo = 0; 3 double hi = d; 4 double guess = d / 2; 5 while ( fabs(guess * guess - d) > 0.000001 ) { 6 if (guess * guess > d) { 7 //too high: 8 // reduce guess to midway between guess and lo 9 // reduce hi to previous guess 10 double temp = (guess - lo) / 2 + lo; 11 hi = guess; 12 guess = temp; 13 } 14 else { 15 //too low: 16 // increase guess to midway between guess and hi 17 // increase lo to previous guess 18 double temp = (hi - guess) / 2 + guess; 19 lo = guess; 20 guess = temp; 21 } 22 } 23 return guess; 24 } Convert the iterative solution presented above into a tail- recursive implementation that performs the same task. Hint: write a helper function.

• Question 7.3 : Execute the iterative and tail-recursive square root code (from the previous problem) by hand for d = 64.. Convince yourself that they are doing the same thing, and make sure you understand why the tail-call optimization (reusing the frames on a tail call) is correct. • Question 7.4 : What is the output when the following code is executed? 1 void g(int x) { 2 if (x != 0) { 3 g(x / 10); 4 printf(\"%d\", x % 10); 5} 6} 7 void f(int x) { 8 if (x < 0) { 9 printf(\"-\"); 10 g(-x); 11 } 12 else if (x == 0) { 13 printf(\"0\"); 14 } 15 else { 16 g(x); 17 } 18 printf(\"\\n\"); 19 } 20 int main(void) { 21 f(42); 22 f(-913); 23 return EXIT_SUCCESS; 24 } • Question 7.5 : Is the function g in the previous problem head- or tail-recursive? Why? • Question 7.6 : Write a recursive function unsigned power(unsigned x, unsigned y), which computes . Write a main function that tests it with several values, and convince yourself it is correct. • Question 7.7 : Write a recursive function void printHex(unsigned x), which takes an unsigned int and prints it out in hexadecimal. Recall from Section 3.1.2 that hexadecimal is base 16 and has digits with values 0–F. As always, write a main that tests your code for several values, and convince yourself it is correct. 6 Fixing Your Code: Testing and Debugging8 Pointers Generated on Thu Jun 27 15:08:37 2019 by L T XML

I Introduction to Programming in C7 Recursion9 Arrays

Chapter 8 Pointers One of the most important and powerful aspects of the C programming language is its use of pointers. Pointers give a programmer a significant amount of control and flexibility when programming, enabling solutions that are clean and efficient. However, they can also be a common source of confusion and bugs—primarily when people use them without understanding them or fail to plan properly. This chapter will introduce the concept of pointers and provide the reader with an in-depth understanding of what they are and how to use them correctly. Let us begin with a simple example to motivate the use of pointers. Suppose we want to write a swap function, which will take two integers and swap their values. With the programming tools we have so far, our function might look something like this: 1 void naive_swap(int x, int y) { // note: this does 2 int temp = x; 3 x = y; 4 y = temp; 5} 6 int main(void) { 7 int a = 3; 8 int b = 4; 9 swap(a, b); 10 printf(\"a = %d, b = %d\\n\", a, b); 11 return EXIT_SUCCESS; 12 } Unfortunately, this code is not going to have the functionality we intended. When we pass the arguments a and b to the function naive_swap, the function is given its own local copy of these variables. Although the function successfully swaps its copies of a and b, the original variables are left unchanged. You should be able to see this behavior yourself by applying the rules we have seen so far; however, to make sure

you understand clearly, Video 8.1 walks through the execution of this flawed code. Video 8.1: Stepping through a naïve (pointer-less) implementation of swap. In order to write our function, we need a way for a function to refer to its caller’s variables (in this case, a and b). Pointers provide exactly this functionality—the ability to refer to another location in the program—although they also have many other uses beyond just swapping data. 8.1 Pointer Basics Pointers are a way of referring to the location of a variable. Instead of storing a value like 5 or the character ’c’, a pointer’s value is the location of another variable. Later in this chapter we will discuss how this location is stored in hardware (i.e., as a number). Conceptually, you can think of the location as an arrow that points to another variable. Just like we can make variables that are integers, doubles, etc., we can make variables that are pointers. Such variables have a size (a number of bytes in memory), a name, and a value. They must be declared and initialized. Declaring a pointer In C, pointer (by itself) is not a type. It is a type constructor—a language construct that, when applied to another type, gives us a new type. In particular, adding a star (*) after any type names the type that is a pointer to that type. For example, the code char *my_char_pointer; (pronounced “char star my char pointer”) declares a variable with the name my_char_pointer with the type pointer to a char (a variable that points to a character). The declaration of the pointer tells you the name of the variable and type of variable that this pointer will be pointing to.

Figure 8.1: Pointer Basics. Code (left) and conceptual representation (right) of a variable x with value 5 and a variable xPtr, which points to x. Assigning to a Pointer As with all other variables, we can assign to pointers, changing their values. In the case of a pointer, changing its value means changing where it points— what its arrow points at. Just like other variables, we will want to initialize a pointer (giving it something to point at) before we use it for anything else. If we do not initialize a pointer before we use it, we have an arrow pointing at some random location in our program, and we will get bad behavior from our program—if we are lucky, it will crash. Assignment statements involving pointers follow the same rules that we have seen so far. However, we have not yet seen any way to get an arrow pointing at a box—which is what we need to assign to a pointer. To get an arrow pointing at a box (technically speaking, the address of that box in memory), we need a way to name that box, and then we need to use the & operator. Conceptually, the & operator (the symbol is called an “ampersand,” and the operator is named the “address-of” operator) gives us an arrow pointing at its operand. The code xPtr = &x;, for example, sets the value of the variable xPtr to the address of x. After it is initialized, xPtr points to the variable x. On the left of Figure 8.1, you can see code that declares an integer x and a pointer to an integer xPtr. In line 2, the value of x is initialized to 5 on the same line in which it is declared. In line 5, the value of xPtr is initialized to the location of x. Once initialized, xPtr points to x. The address-of operator can be applied to any lvalue (recall that an lvalue is an expression that “names a box”) and evaluates to an arrow pointing at the box named by the lvalue. The only kind of lvalue we have seen so far is a variable, which names its own box. Accordingly, for a variable x, the expression &x gives an arrow pointing at x’s box. It is important to note that the address of a variable is itself not an lvalue and thus not something that can be changed by the programmer. The code “&x = 5;” will not compile. A programmer can access the

location of a variable, but it is not possible to change the location of a variable. Note that in the context of pointers, the & symbol is a unary operator—an operator that takes only one operand. It is used before the lvalue whose address should be taken. This operator is not to be confused with the binary operator—an operator that takes two operands. The binary operator & performs a bitwise AND (performing a boolean AND on each binary bit of the two operands).1 Dereferencing a pointer Once we have arrows pointing at boxes, we want to make use of them by “following the arrow” and operating on the box it points at—either reading or changing the value in the box at the end of the arrow. Following the arrow is accomplished using the star symbol (*), a unary operator that dereferences a pointer.2 An example of the use of the dereference operator is shown in line 6 of Figure 8.1. *xPtr = 6; changes the value that xPtr points to (i.e., the value in the box at the end of the arrow—namely, x’s box)—to 6. Notice that the green arrow indicates this line has not yet been executed, hence x still has the value 5 in the conceptual representation. Once line 6 is executed, however, the value will be 6. Do not be confused by the two contexts in which you will see the star (*) symbol. In a variable declaration, such as int *p;), the star is part of the type name and tells us that we want a pointer to some other type (in our example, int * is the type of p). In an expression, the star is the dereference operator. For example, the code r = *p; gives the variable r a new value, namely the value inside the box p (which is an arrow) points to. The code *p = r; changes the value inside the box p points at to be a new value, namely the value of the variable r. As always, remember that you can think about declaration with initialization as two statements: int * q = &y; is the same as the two statements int *q; q = &y;. Generally when you work with pointers, you will use the star first to declare the variable and then later to dereference it. Only variables that are of a pointer type may be dereferenced.

8.2 A Picture Is Worth a Thousand Words When working with pointers, always draw pictures. Although there are only three basic pointer actions—declaring, assigning (including initializing), and dereferencing, trying to read code that does all of these actions—often multiple times within a single line—can be very confusing. Until you can successfully read code that uses pointers, it will be almost impossible to write code that does so. Furthermore, when you are writing code with pointers, careful planning—by drawing pictures—is even more important in order to write correct code. Pointers are variables and should be drawn like any other variable at the time of declaration. Draw a box with the name of the variable on the left and the value of the variable on the right. When a pointer has been declared but not yet initialized, it is not known where the pointer points. The uninitialized value can be represented with a question mark just as it is for uninitialized variables of other types. Video 8.2: Stepping through a simple series of pointer manipulations. As you learned in Section 2.1, assignment statements in C (x = y;) can be broken down into two parts. The left-hand side (here, x), which is the lvalue, is the box that will have a new value placed inside it. Before this chapter, lvalues were simply variables (e.g., x or y). With the introduction of pointers, we can also use the a derferenced pointer as an lvalue—if p is a pointer, then *p is an lvalue, as it names the box at the end of p’s arrow. For example, line 6 of Figure 8.1 assigns a value to the variable xPtr and line 7 assigns a value to the location that xPtr points to. The right-hand side (the y in the statement x = y;), which is the rvalue, is the value that will be placed inside the box/lvalue. With the introduction of pointers, we add two new types of expressions that can appear in rvalues: the address of an lvalue (&x) and the dereferencing of a pointer (*p).

Video 8.2 shows an example of some basic pointer code and the drawings that help us to correctly follow its behavior line by line. 8.3 swap, Revisited Now that we know about pointers, we can write functions that are able to access and manipulate the variables of another function—we can pass pointers to the locations we want the called function to operate on. We now have the tools to write a correct version of swap. The key is to pass the swap function pointers to the original variables a and b, as seen here: 1 void swap(int *x, int *y) { 2 int temp = *x; 3 *x = *y; 4 *y = temp; 5} 6 int main(void) { 7 int a = 3; 8 int b = 4; 9 swap(&a, &b); 10 printf(\"a = %d, b = %d\\n\", a, b); 11 return EXIT_SUCCESS; 12 } Because the variables x and y hold arrows pointing to the original variables a and b, the function can swap the caller function’s variables and not simply its own local copies. The parameters now tell us the locations of data to manipulate, rather than the values to manipulate. However, it can manipulate the values at those locations by dereferencing the pointers. Video 8.3 steps through the execution of this correct swap function. In this video (and many others with pointers, which will become quite common through the rest of the book), we may use different colors to draw different pointers. These colors have no significance in terms of the program behavior—there is nothing special about one pointer being dark blue and one being light blue. Instead, we just use different colors for visual clarity when the diagrams would be confusing if the pointers were all drawn in the same color.

Video 8.3: Stepping through a correct implementation of swap with pointers. 8.4 Pointers Under the Hood In a conceptual drawing, representing a pointer with an arrow is an effective way of showing what the pointer points to. From a technical perspective, however, an arrow does not make much sense. (How exactly does one represent an arrow in hardware? After all, “Everything Is a Number”—and arrows do not seem like numbers.) Figure 8.2: Data with Addresses. The mechanics of pointers make a little more sense when we look under the hood at the hardware representation. By now you are familiar with the idea that data is stored in your computer in bytes. Some data types, like characters, require one byte (eight bits), and some data types, like integers, require four bytes3 (32 bits). When we draw boxes for our variables, we do not necessarily think about how big the box is, but that information is implicit in the type of the variable. Addressing A computer keeps track of all of the data by storing it in memory. The hardware names each location in memory by a numeric address. As each different address refers to one byte of data, this type of storage is called byte- addressable memory. A visualization of what this looks like is shown in Figure 8.2. Each box represents a byte of memory,

and each byte has an address shown immediately to the left of it. For example, the address 208 contains one byte of data with the value 00000000. Figure 8.3: Generic drawing of bytes in memory and their addresses. Figure 8.3 (an expansion of Figure 3.10, which depicted the ASCII encoding of a string) shows the code, conceptual representation, and hardware representation of the declaration and initialization of one four-byte integer, four one-byte characters, and finally two four-byte pointers.4 Each variable has a base address. For example, the address of x is 104, and the address of c3 is 101. The variable x is small enough that it can be expressed within the first byte of its allocated space in memory. If it were larger (or simply negative), however, the bytes associated with addresses 105–107 would be non-zero.5 On a 32-bit machine, addresses are 32 bits in size. Therefore, pointers are always four bytes in size, regardless of the size of the data they point to. With this more concrete understanding of memory and addresses, the hardware representation of pointers becomes clear: pointers store the addresses of the variable they point to. The final variables, y and z, in Figure 8.3 show just that. The variable y is an integer pointer initialized to point to x. The conceptual drawing shows this as an arrow pointing to the box

labeled x. The hardware drawing shows this as a variable that has the value 104, the base address of x. The variable z is declared as a pointer to a char. Although a character is only one byte, an address is 32 bits, and so z is four bytes in size and contains the value 101, the location of c3. (If these variables were located in memory locations with higher addresses, the numerical values of the addresses would be larger, and there would be non-zero values across all four bytes of the pointers y and z.) Pointers are variables whose values are addresses. An important consequence of this fact is that a pointer can only point to addressable data. Expressions that do not correspond to a location in memory cannot be pointed to, and therefore a program cannot attempt to use the ampersand (address of) operator for these expressions. For example, neither 3 nor (x+y) are expressions that represent an addressable “box” in memory. Consequently, lines like these are illegal: int *ptr = &3; and int *ptr = &(x + y);. Note that 3 and (x+y) are not lvalues— they do not name boxes, which is why they cannot have an address. The compiler would reject this code, and we would need to correct it—primarily by thinking carefully about what we were trying to do (drawing a picture). A corollary to this rule is that an assignment statement can only assign a variable that corresponds to a location in memory. So expressions such as 3 = 4; or x + y + z = 2 will also trigger a compiler error. 8.4.1 A Program’s View of Memory On a 32-bit machine, where addresses are 32 bits in size, the entire memory space begins at 0x00000000 (in hex, each 0 represents 4 bits of 0) and ends at 0xFFFFFFFF (recall that 0x indicates hexadecimal, and that each F represents four binary 1’s). Every program has this entire address space6 at its disposal, and there is a convention for how a program uses this range of addresses. Figure 8.4 depicts where in memory a program’s various components are stored.

Figure 8.4: High-level depiction of a program’s memory layout. Code Given the repeated claims that “Everything Is a Number,” it should come as no surprise that a program itself can be represented by a series of numbers. Producing these numbers is the job of a compiler, which takes a program in a language like C and converts it into a bunch of numbers (called object code), which is readable by the computer. An instruction in C that adds two numbers together, for example, might be encoded as a 32-bit instruction in object code. Some of the 32 bits will tell the machine to perform addition, some of the bits will encode which two numbers to add, and some of the bits will tell the processor where it should store the computed sum. The compiler converts the C code into object code and also assigns each encoded instruction a location in memory. These encoded program instructions live in the Code portion of memory, shown in yellow in Figure 8.4. Static data The static data area contains variables that are accessible for the entire run of the program (e.g., global variables). Unlike a variable that is declared inside a function and is no longer accessible when the function returns, static variables are accessible until the entire program terminates (hence, the term static)). Conceptually, a static variable’s box remains “in the picture” for whole program, whereas other variables are usable for only a subset of the program’s lifetime. These variables are placed in their own location in memory, just past the Code portion of the program, shown as Static Data in green in Figure 8.4.

The final two sections of memory are for two different types of program data that are available at specific times during a program’s execution. The Heap (in purple) stores dynamically allocated data, which we will discuss in Chapter 12. The Stack (in orange) stores the local variables declared by each function. The stack is divided into stack frames (introduced in Section 2.3), which start when the function is called and last until it returns. The conceptual drawings throughout this book have primarily shown pictures of stack frames as boxes (one for each function) with local variables. In actuality, the stack is one contiguous piece of memory; each stack frame sits below the stack frame of the function that called it. Video 8.4: Stepping through our swap function with attention to what happens in hardware. With these details about how pointers work and how code is placed in memory, we can show a more detailed view of what happens during the execution of our swap function. Video 8.4 shows the same swap function’s execution, but with a contiguous view of the stack and memory addresses as the values of pointers. It also shows the code of the program stored in memory in four-byte boxes. The return address field of the stack—previously depicted in our conceptual drawings as a blue call site location–is also made explicit in this video. The return address is the address of the instruction that should be executed next after the function being called completes and returns. The calling convention—the specific details of how arguments are passed to and values are returned from functions —depicted in Video 8.4 resembles an x86 machine; the arguments to a function reside in the stack frame of the function that called it. This is slightly different from the conceptual drawings we have shown previously, in which the arguments were placed in the stack frame of the function being called. For a conceptual drawing, this is both sufficient and easy to understand. Hardware details will differ slightly for every target architecture.