[A transcript of the SIGCSE 2008 conference: Table of Contents]
During the second session of the day, I bounced among several sessions, but the highlight was Stuart Reges talking about an interesting little problem -- not a problem he had, but a problem that appeared on the advanced placement exam in CS taken by high-school students. This problem stood out in an analysis of the data drawn from student performance on the 1988. Yes, that is twenty years ago! Donald Knuth is famous for saying that perhaps only 2% of people have the sort of mind needed to be a computer science. He actually wrote, "I conclude that roughly 2% of all people 'think algorithmically', in the sense that they can reason rapidly about algorithmic processes." But is it that those 2% have that the rest do not? In his talk, Stuart read another passage from Knuth that speculates about one possible separator:The other missing concept that seems to separate mathematicians from computer scientists is related to the 'assignment operation' :=, which changes values of quantities. More precisely, I would say that the missing concept is the dynamic notion of the state of a process. 'How did I get here? What is true now? What should happen next if m going to get to the end?' Changing states of affairs, or snapshots of a computation, seem to be intimately related to algorithms and algorithmic thinking.In studying student performance on the 1988 AP exam, Reges found that performance on a small set of "powerhouse questions" was inordinately predictive of success on the exam as a whole, and of those five one stood out as most predictive. This question offers evidence in support of Knuth's speculation about "getting" assignment. Here it is:
If b is a Boolean variable, then the statement b := (b = false) has what effect?What a fun little question -- so simple, but with layers. It involves assignment, but also sequencing of operations, because the temporary result of (b = false) must be computed before assigning to b. (Do you know the answer?) You can read about the correlations and much more about the analysis in Stuart's paper and slides, which are available on this resource page The full analysis may be interesting only to a subset of us, perhaps as few as 2%... I really enjoyed seeing the data and reading about how Stuart thought through the data. But here I'd like to think more about what this implies for how students reason, and how we teach. This notion of state, the ability to take and manipulate "snapshots of a computation", does seem to be one of the necessary capabilities of students who succeed in computer science. With his speculation, Knuth is suggesting that how people think about computation matters. Stuart also quoted one of my heroes, Robert Floyd, who upon hearing an earlier version of this talk commented:
- It causes a compile-time error message.
- It causes a run-time error message.
- It causes b to have value false regardless of its value just before the statement was executed.
- It always changes the value of b.
- It changes the value of b if and only if b had value true just before the statement was executed.
These questions seem to test whether a student has a model of computation; whether they can play computer in their head.This is something folks in CS education think a lot about, but unfortunately we in then trenches teaching intro CS often don't apply what we know consistently or consciously. Whether we think about it or not, or whether we act on it or not, students almost certainly bring a naive computational model with them when they enter our courses. In the world of math and CS, we might refer to this as a naive operational semantics. How do variables work? What happens when an if statement executes? Or a loop? Or an assignment statement? I have read a few papers that investigate novice thinking about these issues, but I must confess to not having a very firm sense of what CS education researchers have studied and what they have learned. I do have a sense that the physics education community has a more complete understanding of their students' naive (mis)understanding of the physical world and how to engage students there. (Unfortunately, doing that doesn't always help.) Someone in the crowd suggested that we teach a specific operational semantics to students in CS1, as some authors do. That's a good idea complicated by the kinds of languages and programming models that we often teach. I think that we can do better just by remembering that our students have naive computational model in their heads and trying to find out how they understand variables, selection, loops, and assignments statements. Stuart gave a great example of how he does this. He now sometimes asks his students this question:
public static int mystery(int n) {
int x = 0;
while (n % 2 == 0) {
// Point A
n = n / 2;
x++;
// Point B
}
// Point C
return x;
}
Is (n % 2 == 0) always true, never true, or sometimes
true/sometimes false at points A, B and C?
Stuart reported that many of his students think (n % 2 == 0)
is always true at Point B because it's inside the loop, and the
while loop condition guarantees that the condition is
always true inside the loop. One wonders what these students
think about infinite loops.
If we understand what students think in such basic situations,
we are much better positioned to help students debug their
programs -- and to write programs in a more reliable way.
One way to help students learn and enjoy more is to give them
tools to succeed. And recognizing when and how what students
already think incorrectly is a prerequisite to that.
Plus, these are multiple-choice questions, which will make
some students and professors even happier!
-----