Hi, my name is Will Crichton, and I’m a CS PhD student at Stanford advised by Pat
Hanrahan and Maneesh Agrawala. Program tracing is the task of mentally simulating
a program with concrete inputs to produce a concrete output. For example, to trace this
program, you would mentally compute q is equal to five, e is equal to 3, and so on. So why
should we care about tracing? click
First, tracing is a foundational skill in CS education, as it indicates a basic understanding
of programming language semantics. Students who can correctly trace programs perform better
on comprehension tasks. And tracing isn’t just for students — expert programmers use
tracing to understand code that doesn’t match any of their existing schema. Hence,
if we want to better understand programmers, then we should better understand tracing.
The thesis of our paper is that a core cognitive challenge of tracing is holding program state,
like variables and the call stack, in working memory. Working memory is a psychological
model of how people store and manipulate temporary information. The most famous result about
working memory is that people universally have a limited capacity of so-called “chunks”.
And so the general goal of our research was to quantify the different ways that working
memory limits our ability to remember program state. In the paper, we have four experiments,
but for now I’ll focus just one: click the relationship between working memory and tracing
a straight-line program. The core question of this experiment is: what
is the precise set of mental steps that a person would go through while tracing? For
example, here’s a possible cognitive model. First, click you store x associated to 3 in
your working memory. Then you try to compute x + 4 click by looking up the value of x in
working memory, computing 3 + 4, and storing y goes to 7, click and so on.
One way to view this model is by looking at a persons’ attention over time. *click So
this graph shows each line of code, and how that person’s attention moves between the
code over time. If a person reads top to bottom, it would look like this. But let’s say they
forgot the value of y while tracing z = y - 2. click Then their graph might look like
this
Here, they visit z, then revisit y to recompute its value, then return to z and finish tracing
the program. To test whether this model accurately describes
how people trace programs, we ran an experiment where participants traced short straight-line
program using this web UI. In each program, variables are assigned to either constants
or expressions. We blurred out the right hand side of each assignment, and only showed the
text when the user hovers over the line with their mouse. Then their mouse is essentially
a proxy for their attention, similar to an eye tracking study.
Here are some actual traces from participants in our study. First, we observed that participants
adopted one of two distinct strategies that we called “linear” and “on-demand”.
Linear is going primarily top to bottom as hypothesized. For example, the top middle
trace is very clearly linear.
By contrast, the on-demand strategy is characterized by starting at the last statement, and then
following data dependencies. In the bottom left graph, the participant started at b = o
+ s, then went to o, then went to s, and so on. As a heuristic, we classified each person’s
trace as linear if visited the first line of code before they visited the last line
of code.
We wanted to quantify the relationship between each strategy and working memory. Our hypothesis
was that a person is more likely to forget information they visited earlier, and so people
tracing linearly would forget more constants, and people tracing on-demand would forget
more expressions. We couldn’t directly observe forgetting, so we proxied forgetting by the
number of times someone visited a line of code more than once.
Under this model, we computed the distribution of revisits. In this graph, the x-axis separates
each strategy, linear and on-demand, and the y-axis shows the average number of revisits
per node type. Within a strategy, the colors differentiate revisits to lines with expressions
in blue, or lines with constants in orange. The results showed that between the two strategies,
participants were equally likely to revisit constant values, but more likely to revisit
expressions in the on-demand case. This result is somewhat consistent with our hypothesis
in that on-demand tracers would revisit their earliest lines first. Another implication
is that people adopting the on-demand strategy overall forgot program state more often, which
could mean that the on-demand tracing strategy has a greater load on working memory.
Either way, a clear implication for design is that programming environments should provide
cognitive support for both strategies. For example, showing information about all variables
defined before a point as on the left, or showing all later uses of a variable as on
the right.