Teaching to develop a mental model of program behavior: How do students learn the notional machine

“To understand a program you must become both the machine and the program” – Perlis 1982, cited in Sorva 2013

I’ve been thinking for a few years now about an open research question in computing education. How do students come to understand how programs work? Put in a more technical way, How do students develop their mental model of the language’s notional machine?

I have been thinking about this question in terms of Ashok Goel’s Structure-Behavior-Function (SBF) model of how people think about systems.

• Structure is the parts of the system — for us in CS, think about the code.
• Function is what the system does — for us in CS, the requirements or the description of what the program is supposed to do.
• Behavior is how the structural elements interact to achieve the function. It’s the understanding of the semantic model of the programming language (the notional machine) plus how that plays out in a specific program.

There are studies of students learning notional machines (e.g., Raymond Lister and Juha Sorva are some of the top researchers here). What I don’t know is how it develops and how to help it develop. Lister tells us the stages of development (e.g., of tracing skill). Sorva tells us about theories of how to teach the notional machine, but with little evidence. We have models for how people learn to read and write code (e.g., Elliot Soloway’s plans). But we not have a cognitive model for how they develop a mental model of how the code works.

A Pedagogical Problem That I Faced

I’m teaching Media Computation (n=234) this semester, and students had a disappointing performance on two programming problems on a recent quiz. (We have a 30 minute quiz every other week.) They didn’t really bomb, but an average of 82% on one programming problem (Problem #3 below) and 76% on the second (Problem #4) was lower than I was hoping for. Those are all mostly due to partial credit — only 25 of my 234 students got full credit on Problem #4. Worse yet, we had a “simple” matching problem where we offered four pictures and four programs — which program generated which picture? More than half the students got at least two wrong. The score on the matching problem was 72%, even lower than the programming task problems. My conclusion is that my students can’t yet read code and understand it.

How do I teach my students to understand code?

With my researcher hat on, I don’t have a solid answer. With my teacher hat on, I have to do something. So, I drew on what I know from the research to come up with a best guess solution.

I decided to drop the next two lecture topics from the schedule, to instead re-focus on manipulation of pictures. I know from the learning sciences literature that it’s much better to go deeper than broader. Teaching for mastery is more important than teaching for coverage. Things that students know well are more likely to persist and transfer than things that students are merely familiar with.

I decided to do a live-coded session revisiting the quiz. I had graded a bunch of the programming problems on the quiz. I saw several different strategies for solving those two problems. I had a unique teachable moment here — every student had attempted these two problems. They were primed for the right answer. I decided to solve the problems in a live-coding session (starting from a blank editor, and talking aloud as I wrote the code) in each of the ways that I saw students doing it — three ways for the first problem, four ways for the second problem. While I wrote, I drew pictures to describe the behavior, drawing from Sorva’s visualization approach and the SILC emphasis on sketching rather than diagrams. After writing each program, I tested it on a picture. Along the way, I answered questions and wrote additional examples based on those questions.

This idea is based on Marton’s Variation Theory. You have to vary critical aspects of examples for students to figure out the differences. Janet Kolodner talks about a similar idea when she emphasizes contrasting cases for learning informed by case-based reasoning.  In SBF terms, I was keeping the Function constant, but varying the Structure and Behavior. In Goal-Plan-Code terms, I was achieving the same Goal, but varying the underlying Plan and Code.

Could an exploration of these variations/contrasts help students see how the code changes related to behavior changes?  I don’t actually know how to evaluate the result as a researcher, but as a teacher, I got good response from students.  I’m looking forward to seeing how they do on similar problems on future quizzes.

The rest of this blog post is a static replay of the lecture. I’ll show you the slides I showed, the sketches I made, and the code I wrote (while talking aloud).

Problem clearTopHalf

Solution #1: Iterate through all pixels

def clearTopHalf1(pic):
  h = getHeight(pic)
  for pixel in getPixels(pic):
     y = getY(pixel)
     if y < h/2:
       setColor(pixel,white)

Solution #2: Iterate through half of the pixel indices

def clearTopHalf2(pic):
  all = getPixels(pic)
  for index in range(0,len(all)/2):
    pixel = all[index]
    setColor(pixel,white)

Solution #3: Iterate through all x and y positions in the top half

def clearTopHalf3(pic):
  h = getHeight(pic)
  w = getWidth(pic)
  for y in range(0,h/2):
   for x in range(0,w):
    pixel = getPixel(pic,x,y)
    setColor(pixel,white)

A student asked, “Could we do x first and then y?” Sure!

def clearTopHalf3b(pic):
  h = getHeight(pic)
  w = getWidth(pic)
  for x in range(0,w):
    for y in range(0,h/2):
       pixel = getPixel(pic,x,y)
       setColor(pixel,white)

Pause for Reflection and Discussion

At this point, I asked students to turn to the person next to them and ask, “Which one do you prefer? Which makes the most sense to you?”

I always encourage students to discuss during peer instruction questions. I have never had such an explosion of noise as I did with this invitation. From wandering around the room, what I heard students discussing was, “This is what I did, and this is what I got wrong.”

When we had the whole class discussion, the first and third approaches (all pixels or coordinates) were the preferences. Students who spoke up disliked the index approach — it felt “like there’s too much indirection” (said one student).

Problem copyThirdDown

Solution #1: Iterating through all pixels

def copyAThird1(pic):
  h = getHeight(pic)
  for pixel in getPixels(pic):
    x = getX(pixel)
    y = getY(pixel)
    if y < h/3:
      targetPixel=getPixel(pic,x,y+(2*h/3))
      setColor(targetPixel,getColor(pixel))

Solution #2: Iterate through first 1/3 of pixels

def copyAThird2(pic):
  all = getPixels(pic)
  h = getHeight(pic)
  for index in range(0,len(all)/3):
    pixel = all[index]
    color = getColor(pixel)
    x = getX(pixel)
    y = getY(pixel)
    targetPixel = getPixel(pic,x,y+(2*h/3))
    setColor(targetPixel,color)

Solution #3: Iterate through top 1/3 of picture by coordinates

def copyAThird3(pic):
  h = getHeight(pic)
  w = getWidth(pic)
  for x in range(0,w):
   for y in range(0,h/3):
    pixel = getPixel(pic,x,y)
    color = getColor(pixel)
    #Copies
    targetPixel = getPixel(pic,x,y+(2*h/3))
    setColor(targetPixel,color)

At this point, someone said that they did it by subtracting y from the height. I showed them that this approach mirrors. This is the first incorrect solution that I demonstrated.

def copyAThird3b(pic):
  h = getHeight(pic)
  w = getWidth(pic)
  for x in range(0,w):
    for y in range(0,h/3):
      pixel = getPixel(pic,x,y)
      color = getColor(pixel)
      # Mirrors instead of copies
      targetPixel = getPixel(pic,x,h-y-1)
      setColor(targetPixel,color)

Solution #4: Iterating through the bottom 1/3 of the picture by x and y coordinates

This was an unusual approach that I saw a few students try: They used nested loops to iterate through the bottom 2/3 of pixel coordinates, and then compute the top 1/3 to copy down. They iterated through the target and computed the source.

def copyAThird4(pic):
  h = getHeight(pic)
  w = getWidth(pic)
  for x in range(0,w):
    for y in range(2*h/3,h):
      targetPixel=getPixel(pic,x,y)
      srcPixel=getPixel(pic,x,y-(2*h/3))
      setColor(targetPixel,getColor(srcPixel))

After I wrote that program, someone asked, “Couldn’t you make an empty picture and copy the top third into the new picture at the top and bottom?” With her guidance, I modified the program above to create a new version, which does exactly as she describes, leaving the middle third blank. So, this was the second incorrect version I wrote to respond to student queries.

def copyAThirdEmpty(pic):
  h = getHeight(pic)
  w = getWidth(pic)
  canvas = makeEmptyPicture(w,h)
  for x in range(0,w):
    for y in range(0,h/3):
      pixel = getPixel(pic,x,y)
      color = getColor(pixel)
      targetPixel = getPixel(canvas,x,y)
      setColor(targetPixel,color)
      targetPixel = getPixel(canvas,x,y+(2*h/3))
      setColor(targetPixel,color)
  explore(canvas)

When I asked students a second time which version made the most sense to them, there was a bigger split. Indexing the array continued to be the least preferred one, but students liked both versions with nested loops, and many still preferred the first version.