Find the Bug: A Book of Incorrect Programs

Description

If you're a programmer, you've probably spent a fair bit of timelooking through source code trying to find a bug. You know the routine: you'venarrowed the bug down to a small section of code, you know it's lurking inthere somewhere, but you can't make yourself see where it is. You are confidentthat eventually you will have the satisfaction of fixing the bug, but for themoment, all you feel is frustration.

So why, you might ask, would you voluntarily read a book thatrequires you to do exactly that, repeatedly?

The answer is that finding bugs by looking through source code isreally, in the end, the only way to fix bugs. You can run your tests, gatheryour data, wade through a debugger session, print all the verbose text youwant, but it eventually comes down to seeing where the code has to be changed.Sometimes the bug can be glaringly obvious, but oftentimes it is not. On thetheory that practicing something makes you better at it, it would seem logicalto practice a skill that makes finding bugs easier, faster, and lessfrustrating.

Furthermore, the more time you spend reading source code lookingfor bugs, the better you will be at finding them when you first review yourcode, when fixing bugs is cheap. As opposed to later, when the program hasalready been through a series of tests that need to be re-run if any code ischanged. Or even later, when the software has shipped and the bug is found by adisgruntled end user who wants a fix as soon as possible.

This book lists the source code to 50 programs. Each program hasexactly one bug in it (unless I missed one).

The 50 programs consist of five chapters of ten programs each,with each chapter's programs written in one of five different languages. Don'tbe concerned if you are unfamiliar with some of the languages; I have beguneach chapter with a brief summary describing the relevant syntactic features ofeach language. The goal of these descriptions is not to present a complete tutorialon a language, but instead to provide enough information to allow you toextract the logic from the code, and from there find the flaw in the logic. Ifyou're a programmer familiar with any language, you should be able to followalong. The specific language really doesn't matter here: the skills requiredare relevant to all programming languages.

For each program, I explain what it is trying to do and point outany unusual features of the language, after which comes the source code.Ideally you will be able to find the bug by looking at the source. If you arehaving trouble, I offer suggestions on how to approach analyzing the program,and then hints on specific inputs to use when walking through the code. FinallyI give an explanation of the bug, and discuss how it would manifest itself(something I encourage you to come up with on your own, since it will improveyour understanding of the code).

The kinds of bugs will vary: improperly calculated arithmeticexpressions, bad algorithms, incorrect assignments, returning the wrongvariable, and so on. There are no "gotchas" or subtle tricks thatwill only be apparent to those who are experts in a language. All the code willgo through a compiler or interpreter without errors.

The inspiration for this book came from my years working as aprogrammer at Microsoft. One of the duties we had was interviewing candidatesfor programming jobs, and during those interviews we almost always asked thecandidates to write some code on the office whiteboard. The problems were notespecially complicated: sorts, linked list operations, and so on, the kind ofalgorithm you could write, debug, and discuss in half an hour.

The code could be written in any language that the candidate feltcomfortable with (as long as they could explain it to the interviewer); thegoal was not to see if the candidate knew the precise syntax of a language, butto see if he or she could come up with something that was logically correct,and then offer a reasonable proof of that correctness.

These coding questions were designed as a challenge for thecandidates, but they also wound up being a challenge for the interviewer.Evaluating a candidate meant evaluating the code. This meant quicklyunderstanding and analyzing if the logic was correct, so you could discuss whatthe candidate had written, ask about optimizations, and project an air ofbenevolent omnipotence. Since candidates often came up with somewhat"unique" logic, you had to do a quick job of emulating a computer and"executing" their code to see if it worked. You weren't interested inwhat the candidate thought the code was going to do, orwhat he or she was busy telling you it was going to do,or what the code looked like it was going to do (and Inever saw a single candidate include comments in the whiteboard source code).You cared about what it actually did..

Emulating the computer and seeing past the surface of the code toits internal logic can be tricky. Just because someone states, "This codeis going to sort an array," does not mean it will necessarily sort anarray. Just because a variable is named distance_from_center, does not mean itnecessarily has the properly calculated distance from the center. Just becausea for loop appears in the code, does not mean that it actually loops thecorrect number of times.

In fact knowing what a program is supposed to do can blind you towhat the code actually does. It's hard to focus on every line of code, everyassignment, every loop, every comparison, and think hard about what it reallydoes. Yet you have to be able to do this, because that's what the computerdoes.

Beyond helping you debug your own programs, this can also helpyou review other people's code. Increasingly, code reviews are becoming a partof a programmer's job description, and not just informal ones to coverformatting and variable naming conventions. Code reviewers are now being askedto vouch for the quality of the code almost to the same extent as the originalauthor.

Reviewing code that someone else wrote (or code that you wrotelong enough ago to forget the details) is an acquired skill. It has beencompared to proofreading, but there is a key difference. The goal of writing isto pass information to someone who does not have it. Problems with writingoften involve an imperfect simulation of the intended audience: because theauthor knows the material so well, it is hard to imagine how the writing willcome across to someone who lacks that knowledge. Thus, putting your writingaway for a couple of weeks and then coming back to proofread it later (orreviewing someone else's writing), makes you more like the intended audience,so you can do a better job of seeing how they will react than you couldimmediately after you wrote it.

With code, your "audience" is an infallible computerthat will interpret the code exactly as it is written, and in doing sounfailingly extract the logic contained in the code. For a person to do thesame requires some careful study of the code. If code is unfamiliar then youprobably don't understand the details, and thus are lesslike your intended audience. This is why code reviews are so difficult: it isvery hard for people to simulate the dispassionate, perfect way in whichcomputers execute software, and easy for them to unintentionally skip overmistakes.

Back when I was a candidate myself, interviewing for a job atMicrosoft, I got into an argument with one of the employees who interviewed me.He had asked me a typical question: write a program to recursively reverse asentence. I produced some code and declared it correct. He disputed myassertion and pointed out what he claimed was a bug. I responded by showing howit would work successfully on some particular sample input. He continued toinsist that there was a bug. Eventually, we decided to type in and compile theprogram to see who was right. Unfortunately we couldn't get it to compile forsome reason, so we wound up debating the issue with only the source code asevidence, each of us simulating the computer in our minds. In the end I convincedhim I was right, I think. Well, I did get hired.

In this book I present to you 50 programs, each of the type thatwas asked in Microsoft interviews (including recursive sentence reversal),although some of them are a bit longer than would fit on a whiteboard. In thetradition of the rule that interview code could be written in any language,each chapter's ten programs are written in a different language:

C: A general-purpose language that for years was the language ofchoice for complicated systems and application development, and the language inwhich I wrote almost all my code for Microsoft. C was originally designed byDennis Ritchie at Bell Laboratories.

Python: An object-oriented scripting language, very powerful butalso useful for quickly writing small pieces of code. Python was developed byGuido van Rossum.

Java: An object-oriented programming language designed to allowprograms to be downloaded from a network and executed on any platform. Java wasinvented by a team at Sun Microsystems.

Perl: A scripting language, especially optimized for processingtext, often used to write CGI (Common Gateway Interface) programs to run on Webservers. Perl is the brainchild of Larry Wall.

x86 Assembly Language: The native language used by the x86 familyof microprocessors, difficult to understand and rarely written directly innowadays, but often needed to be read and understood by programmers analyzingtheir code in a debugger. The language was designed by Intel Corporation.

If you know one of these languages well, you may be tempted tostart with that chapter. This is fine, but I encourage you to try unfamiliarlanguages also. As mentioned earlier, the summary of the language at thebeginning of each chapter should be enough to get you going.

The bug, I should mention, were not found "in thewild," in code that someone else had written. The programs were written byme. A few programs are written in a non-intuitive way (non-intuitive to somepeople, anyway) in order to showcase a feature of a particular computerlanguage, or allow a certain type of bug to be hidden. In some cases the bugswere artificially injected; for the rest, I simply left in one of the bugs thatI found when debugging the code. I usually had plenty to choose from.

Before we get to the bugs, there is a chapter that gives sometips on how to walk through code. You can skip these if you are confident ofyour skills.

In each chapter, the programs are arranged in roughly increasingorder of difficulty (emphasis on "roughly", since different bugs willbaffle different people). The programs are mostly unrelated; you can tacklethem at your leisure, in any order. In a few places, programs build on previousones to solve a larger problem.

The bugs are classified according to a classification scheme,which is shown briefly in the next chapter, and explained in its entirety inAppendix A. Appendix B is an index of bugs by classification type, if you wantto focus on only a certain type of bug.

What is the goal of this book? First and foremost, it's a chanceto improve your code reviewing and debugging skills. It's also a way tochallenge yourself to solve the logic puzzle represented by each program, bothin figuring out how it works, and finding the bug. You may be able to gain someunderstanding of a programming language you are unfamiliar with. If you'recurious, it present somewhat of a glimpse into what a programming job interviewat Microsoft is like. And if you want to use the programs (once you fix thebug) for your own purposes, please feel free to do so.