Notional Machines and Misconceptions in CS: Developing a Research Agenda at Dagstuhl

I facilitated a breakout group at the Dagstuhl Seminar on Assessment in Introductory Computer Science. We started talking about what students know and should know, and several of us started using terms like “notional machines” and “mental models” — and there were some strong disagreements. We decided to have a breakout group to define our terms, and came up with a fascinating set of issues and questions.  It was a large group (maybe a dozen?), and I think there were some differences in attendance between the two days, so I’m not going to try to list everyone here.

Definitions

We agreed on the definition of a notional machine (NM) as a set of abstractions that define the structure and behavior of a computational device. A notional machine includes a grammar and a vocabulary, and is specific to a programming paradigm. It’s consistent and predictive — given a notional machine and a program to run on that machine, we should be able to define the result. The abstract machine of a compiler is a possible notional machine. This definition meshes with duBoulay’s original one and the one that Juha Sorva used in his dissertation (which we could check, because Juha was there).

Note that a NM doesn’t include function. It doesn’t tell a user, “Why would I use this feature? What is it for?” Carsten Shulte and Ashok Goel both found that students tend to focus on structure and behavior, and significant expertise is needed before students can discern function for a program or a NM component.

In CS education, we care about the student’s understanding of the notional machine. Mental model isn’t the right term for that understanding, because (for some) that implies a consistent, executable model in the student’s head. But modern learning science suggests that students are more likely to have “knowledge in pieces” (e.g., diSessa). Students will try to explain one program using one set of predictions about program behavior, and another program in another way. They respond to different programs differently When Michael Caspersen tried to replicate the Dehnadi and Bornat paper (Camel has two humps paper, and its retraction), he found that students would use one rule set for interpreting assignment in part of the test, and another set of rules later — and they either didn’t care or didn’t notice that they were inconsistent.

An early form of student understanding of the NM is simply mimicry. “I saw the teacher type commands like this. So if I repeat them exactly, I should get the same behavior.” As they start to realize that the program causes behavior, cognitive load limits how much of the NM students can think about at once. They can’t predict as we would like them to, simply because they can’t think about all of the NM components and all of the program at once. The greatest challenge to understanding the NM is Roy Pea’s Superbug — the belief that the computer is in fact a human-like intelligent agent trying to discern our intentions.

We define student misconceptions (about the NM) as incorrect beliefs about the notional machine that are reliable (the student will use more than once) and common (more than one student uses it). There are lots of misunderstandings that pop up, but those aren’t interesting if they’re not common and reliable. We decided to avoid the “alternative conception” model in science education because, unlike natural science, we know ground truth. CS is a science of the artificial. We construct notional machines. Conceptions are provably correct or incorrect about the NM.

One of the challenging aspects of student understandings of NM is that our current evidence suggests that students never fix existing models. We develop new understandings, and learn new triggers/indices when to apply these understandings. Sometimes we layer new understandings so deeply that we can’t reach the old ones. Sometimes, when we are stressed or face edge/corner conditions, we fall back on previous understandings. We help students develop new understandings by constraining their process to an appropriate path (e.g., cognitive tutors, cognitive apprenticeship) or by providing the right contexts and examples (like in Betsy Davis’s paper with Mike Clancy Mind your P’s and Q’s).

Where do misconceptions come from?

We don’t know for sure, but we have hypotheses and research questions to explore:

• We know that some misconceptions come from making analogies to natural language.
• Teaching can lead to misconceptions. Sometimes it’s a slip of the tongue. For example, students often confuse IF and WHILE. How often do we say (when tracing a WHILE) loop, “IF the expression is true…” Of course, the teacher may not have the right understanding.Research Question (RQ): What is intersection between teacher and student misconceptions? Do teacher misconceptions explain most student misconceptions, or do most student misconceptions come from factors outside of teaching?
• Under-specification. Students may simply not see enough contexts or examples for them to construct a complete understanding.
• Students incorrectly applying prior knowledge. RQ: Do students try to understand programs in terms of spreadsheets, the most common computational model that most students see?
• Notation. We believe that = and == do lead to to significant misconceptions. RQ: Do Lisp’s set, Logo’s make/name, and Smalltalk’s back arrow lead to fewer assignment misconceptions? RQ: Dehnadi and Bornat did define a set of assignment misconceptions. How common are they? In what languages or contexts?

RQ: How much do students identify their own gaps in understanding of a NM (e.g., edge conditions, problem sets that don’t answer their questions)? Are they aware of what they don’t understand?  How do they try to answer their questions?

One advantage of CS over natural sciences is that we can design curriculum to cover the whole NM. (Gail Sinatra was mentioned as someone who has designed instruction to fill all gaps in a NM.) Shriram Krishnamurthi told us that he designs problem-sets to probe understanding of the Java notional machine that he expects students to miss, and his predictions are often right.

RQ: Could we do this automatically given a formal specification for an NM?  Could we define a set of examples that cover all paths in a NM?  Could we develop a model that predicts where students will likely develop misconceptions?

RQ: Do students try to understand their own computational world (e.g., how behavior in a Web page works, how an ATM works, how Web search works) with what we’re teaching them? Kathi Fisler predicts that they rarely do that, because transfer is hard. But if they’re actively trying to understand their computational world, it’s possible.

How do we find and assess gaps in student understanding?

We don’t know how much students think explicitly about a NM. We know from Juha’s work that students don’t always see visualizations as visible incarnations of the NM — for some students, it’s just another set of confusing abstractions.

Carsten Schulte pointed out that Ira Diethelm has a cool way of finding out what students are confused about. She gives them a “miracle question” — if you had an oracle that knew all, what one question would you ask about how the Internet works, or Scratch, or Java? Whatever they say — that’s a gap.

RQ: How we define the right set of examples or questions to probe gaps in understanding of a NM? Can we define it in terms of a NM? We want such a set to lead to reflection and self-explanation that might lead to improved understanding of the NM.

Geoffrey Herman had an interesting way of finding gaps in NM understanding: using historical texts. Turns out Newton used the wrong terms for many physical phenomena, or at least, the terms he used were problematic (“momentum” for both momentum and velocity) and we have better, more exact ones today. Terms that have changed meaning or have been used historically in more than one way tend to be the things that are hard to understand — for scholars past, and for students today.

State

State is a significant source of misconceptions for students. They often don’t differentiate input state, output state, and internal states. Visualization of state only works for students who can handle those kinds of abstractions. Specification of a NM through experimentation (trying out example programs) can really help if students see that programs causally determine behavior, and if they have enough cognitive load to computer behavior (and emergent behavior is particularly hard). System state is the collection of smaller states, which is a large tax on cognitive load. Geoffrey told us about three kinds of state problems: control state, data state, and indirection/reference state.

State has temporality, which is a source of misconceptions for students, like the common misconception that assignment states define a constraint, not an action in time. RQ: Why? Raymond Lister wondered about our understanding of state in the physical world and how that influences our understanding of state in the computational world. Does state in the real world have less temporality? Do students get confused about temporality in state in the physical world?

Another source of misconceptions is state in code, which is always invisible. The THEN part of an IF has implicit state — that block gets executed only if the expression is true. The block with a loop is different than the block after a condition (executed many times, versus once) but look identical. RQ: How common are code state misconceptions?

Scratch has state, but it’s implicit in sprites (e.g., position, costume). Deborah Fields and Yasmin Kafai found that students didn’t use variables much in state, but maybe because they didn’t tackle problems that needed them. RQ: What kinds of problems encourage use of state, and better understanding of state?

RQ: Some functional curricula move students from stateless computation to stateful computation. We don’t know if that’s easier. We don’t know if more/fewer/different misconceptions arise. Maybe the reverse is easier?

RQ: When students get confused about states, how do they think about? How do they resolve their gaps in understanding?

RQ: What if you start students thinking about data (state) before control? Most introductory curricula start out talking about control structures. Do students develop different understanding of state? Different misconceptions? What if you start with events (like in John Pane’s HANDS system)?

RQ: What if you teach different problem-solving strategies? Can we problematize gaps in NM understanding, so that students see them and actively try to correct them?