The Ohio State University – Page 5

If you've spent any time in a STEM field, you've hopefully learned the power of drawing pictures. From free-body diagrams to chemical formulas, being able to draw a good picture will always help you solve problems. In the world of computer science, we have our own set of drawing tools. We often call them tracing tables, and they help us reason about our code. How to Make Sense of Code As someone who codes regularly, I might be able to get a feel for what a chunk of code does at a glance. That's because code tends to exhibit recognizable patterns that can be identified by someone with more experience. If, however, you're new to coding, you might not have those pattern recognition skills fleshed out yet. For you, the general approach to making sense of code is to read it line-by-line. But the question becomes, what exactly should you be doing on each line that helps you make sense of the code? My advice: track program state. The process of tracking state can be done in many ways, but the typical strategy is to write down all of your variables and change them as they're updated. In this article, I'll show you a nice strategy for doing that. Making a Tracing Table A tracing table is a tool that is best used on programming languages that work with state (i.e., imperative programming languages). Luckily, the vast majority of popular programming languages operate this way (e.g., Java, Python, C++, etc). The reason we want a programming language that maintains state is that tables allow us to represent changes in state over time. Let me show you an example: StatementStateint x = 0x = 0 In this table, we have a program that has a single line of code: int x = 0. After this line is executed, we know the program state has changed: we have introduced a variable, x, that stores a value, 0. Therefore, we show that change in state in the following row of the table. This structure can be extended to any kind of code block. That said, there are a few scenarios where this structure just won't do. Tracing a Loop In a previous article, I shared the following tracing table for a loop: StatementStateint x = 0;x = 0int i = 1;x = 0i = 1while (i < 5) {x = 0, 1, 3, 6i = 1, 2, 3, 4x += i;x = 1, 3, 6, 10i = 1, 2, 3, 4i++;x = 1, 3, 6, 10i = 2, 3, 4, 5}x = 10i = 5 One thing you might notice about this tracing table is that there are multiple values on a given line. The reason for this structure is that loops can execute multiple times. Therefore, we need to show that the same value changes over time. To do that, we use commas to separate the previous value from the new one. And to make it extremely clear what the current value is, we cross out the old values. Tracing Recursion While loops can make tracing a bit more complicated, there are other structures as well which can throw a wrench in things like recursion. Because a new method is called with each step of recursion, we can't rely on our listing trick from above. As a result, there are basically two ways to handle recursion: 1) create a new tracing table each time you recurse or 2) trust the recursion works. It may seem silly, but option 2 is actually a pretty solid way of going about it. It allows you to do things like this: StatementStatepublic static int factorial(int x)x = 5int product = factorial(x - 1) * x;x = 5product = 120return product The reason this form of tracing works is that we assume that 4! will be computed correctly (i.e., 24). Then, we can multiply 5 by the result to get 120. One of the drawbacks of this technique is that we can never know if our code actually works because we exercise all of the recursive calls. In this case, there's actually a bug with our recursion: there's no base case. As a result, I generally recommend starting with the smallest input first and working our way up through a technique known as confidence building (i.e., test this code for 0! then 1! then 2! and so on). Other Ways to Trace Code The technique described above is the way we trace loops at Ohio State. That said, as I mentioned before, tracing can be done in a variety of ways. For example, several reference recommend tracking variables only: ETH Zurich Department of Computer Science CS 310 Course @ University of Wisconsin Other sources use similar structures to OSU, with some opting for tracking statements, variables, and program outputs. As a result, I'd recommend looking around for a tracing structure you prefer. The exact method doesn't matter that much. At any rate, that's all I wanted to cover today. Hopefully, this was useful to you! If you'd like more articles like this, let me know. In the meantime, check out some of these related articles: Summarizing Community Beliefs Around Commenting Code The Difference Between Private and Public in Java And as always, if you want to go above and beyond to support the content, feel free to check out this list. There, you'll find links to my YouTube, Discord, and Patreon. Take care!