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

April 6, 2018 at 7:00 am 14 comments

“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.

Entry filed under: Uncategorized. Tags: , , .

States requiring CS for all students may be making a mistake: Responding to unfunded mandates High School CS Teacher’s Experience like University CS Teacher’s: “Code Shock”

14 Comments Add your own

  • 1. alanone1  |  April 6, 2018 at 9:09 am

    This is so bizarrely different from how “learning to code” was conducted ca. 1961 when I started in earnest as an enlisted man in the US Air Force.

    There was a preselection test (by IBM). If you passed you were transferred to Air Training Command for a class and to work. The class — for the IBM 1401 computer — was one wall to wall week. At the end, you knew the machine, and could write code for it (machine code) using the Autocoder assembler.

    You could try your program with an operator a maximum of 3-5 minutes per day. The operator would flip switches for you, and do core dumps, etc.

    The on the job training that followed was done by converting real flow charts for real jobs into working 1401 code. These got progressively more intense, and we were encouraged to start learning how to design — primarily by talking (i.e. drinking beer) with programmers who had more experience. The general feeling was that “decent design” took about two years of doing and making to acquire.

    Meanwhile, you would be doing the very same process for the other computers at ATC. The machine code architectures were very different in those days, so learning a few machines forced a collection of useful abstractions about “programming per se” to be developed. Many of these were rendered as “favorite macros” — so one evolved a “poor man’s higher level language” as time progressed.

    The first intensive week of training was a lot of arcane stuff to deal with. The positive aspect of it is that “the notional machine” was “the actual machine” at its lowest nuts and bolts level. This brought a feeling of solidity, once absorbed.

    A belief I’ve had since is that for higher level languages, “programming should be done in the graphical debugger” (because a decent graphical debugger can “show the machine” you are programming (albeit the high level machine). We made Etoys so that the workspace and the debugger are the same thing (there’s nothing called “a debugger”).

    The first good graphical debugger I used was “RAID” from the Stanford PDP-1 time-sharing system (famously shown in the “Ellis D. Kropotechev and His Magical Mystery Machine” movie by Gary Feldman).

    I feel kind of sick to my stomach when I see high school and college kids trying to learn to program without at least something as good as RAID to help. This is completely not understanding “Cognitive Load” etc.!

    What got missed in the 50 years since RAID to now?

    Reply
    • 2. alanone1  |  April 6, 2018 at 9:30 am

      P.S. I think if I ran a college — at least an engineering college — I would do a “learn to program camp” for an intensive week or two before the freshman semester started, and would try to “be mechanical” about the organization of tools and materials: to show and use them with graphical representations that would make the most impact, and extend 7±2 as much as possible.

      Reply
      • 3. Mark Guzdial  |  April 6, 2018 at 10:46 am

        These aren’t engineering students. These are liberal arts, design, and business students. Their tools and materials aren’t the tools and materials of engineers.

        Reply
        • 4. alanone1  |  April 6, 2018 at 10:54 am

          I think I would still try a one week camp. Maybe before sophomore year?

          For certain subjects, being able to go deep with fewer distractions can have large results with many learners. I think this works with programming because there are only a few things that need to be learned early on, but they need to be done a lot to get them grooved into actual thinking tools.

          Reply
    • 5. Mark Guzdial  |  April 6, 2018 at 10:55 am

      I found the Ellis D. Kroptechev movie here: https://www.youtube.com/watch?v=Dv5shcFi-og

      The empirical results on graphical debuggers and program visualizations aren’t stunningly good. Juha Sorva and Moti Ben-Ari have some of the strongest empirical results, but even they don’t get everyone. “CS for All” is a high bar. Even just “CS for everyone who is going to do end-user programming” means that we lose students if we start at the hardware.

      Yes, the goals have changed a lot in 50 years. We’re not teaching future programmers. We’re teaching future professionals who want to understand the computing in their lives and possibly (likely) do some end-user programming in a high-level language. There’s no pre-selection test.

      What is an effective way to teach a notional machine is an open and interesting question. Starting from the hardware and working up the stack is one way of doing it. It’s how Yale Patt does it, too. I know of no empirical results showing that anyone but Yale Patt can teach CS1 with his approach except for him, and I’ve heard that Yale’s drop/fail rate is pretty high, too. I like the Bootstrap/Racket/SICP approaches that use algebra as the foundation of the notional machine. It would be interested in trying to teach PDP-11 machine/assembler explicitly as a lead-in to C, since that’s essentially the notional machine for C.

      When I taught Squeak, I introduced the notional machine twice: At the beginning of class, and at the end. At the beginning, everyone ignored me — they didn’t want to know how it worked. They just wanted to make stuff. At the end, they finally understood their misconceptions, but until they made the bugs, they didn’t want to attend to how it worked.

      Reply
      • 6. alanone1  |  April 6, 2018 at 11:07 am

        Hi Mark

        I think you misunderstood. I wasn’t suggesting that we teach hardware first today, but that a really good graphical debugger can help greatly with learning to internalize the machine that the language presents.

        In Squeak it is possible to program in the debugger, but this was not made into a end-user friendly facility (and I don’t think the existing Squeak debugger is suitable for end-users).

        But I can certainly imagine a graphical debugging environment for end-users that would help them much better internalize what is going on and how to make things and make them go. Someone has probably done a study on “intrinsic interest in learning” vs “desire for results” — my guess is that most people fall strongly into the latter camp.

        However, we are set up to learn what’s around us whether we want to or not, so “making an environment” is likely to be very powerful for most people, whether interested in learning or not.

        I.e. consider what the GUI design does, and why it works.

        Reply
        • 7. Mark Guzdial  |  April 6, 2018 at 11:20 am

          Hi Alan,

          Ahhh — that helps. You’re not saying hardware as the notional machine. You’re saying that whatever the notional machine is, it should be represented graphically, and students should program and debug within that representation of the notional machine. Is that right?

          The model of learning you’re describing (“intrinsic interest in learning” vs “desire for results”) is the core of Pat Alexander’s “Model of Domain Learning.” She points out that no novice can make progress because of an intrinsic interest in the field because, by definition, they don’t know the field. They’re driven by social pressures or the pressure of wanting to get something done. Intrinsic interest may come later.

          It’s still really hard to graphically represent a notional machine, especially for modern languages like Python. I think you (and Shriram Krishnamurthi) might reasonably point out that we should be inventing notional machines that are easier to represent graphically, and by extension, teach. Juha Sorva’s dissertation points out just how hard it is to represent data in a way that students recognize maps to the textual variable names — students don’t see the mapping. My student, Katie Cunningham, has been studying how students trace code, how they visualize the behavior of the notional machine for themselves. She sees that just about everyone represents the history of values in the variables, but almost no visualization system does. And I don’t know of any visualization system that successfully represents objects.

          – Mark

          Reply
          • 8. alanone1  |  April 6, 2018 at 11:36 am

            >You’re saying that whatever the notional machine is, it should be represented graphically, and students should program and debug within that representation of the notional machine. Is that right?

            Yes.

            I had intrinsic interest in Physics before I understood Physics. So I’m not sure I agree with Pat Alexander. But she is definitely right that more interest may come later as more things are understood (if they are taught and learned well enough).

            I have a -very strong feeling-™ that it is quite possible to make a good oop notional machine visualizer. As with most difficult design problems, I’m guessing that trying to design a -whole situation- that facilitates the goals will be much better than trying work with existing languages.

            Reply
    • 9. Mark Guzdial  |  April 6, 2018 at 11:07 am

      Alan, in the Smalltalk-72 Instruction Manual, you and Adele explain the Smalltalk notional machine very explicitly. Your explanation is a great example of a notional machine. You’re not talking about how the hardware works. Rather, you describe how to think about how the virtual machine works, how “3 + 4” can be understood with ‘message sending,’ which wasn’t implemented in the hardware itself.

      Would you have wanted Smalltalk-72 users to learn machine language and assembler first? Why? Why isn’t it enough for them to understand this notional machine?

      Explaining how Smalltalk-72 works

      Reply
      • 10. alanone1  |  April 6, 2018 at 11:17 am

        Hi Mark

        See my comment above. You misunderstood what I was trying to say, mostly because I wasn’t crisp enough.

        Adele and I always wanted to do experiments with the Smalltalk-72 approach vs “how I really wanted Smalltalk-72 to look” vs doing a much more graphical cradle for Smalltalk-72 programs. The first two would contrast the light abstraction and heavier machinery in the existing Smalltalk-72 with a more abstract but more readable syntax.

        None of the experiments happened. Both of us were surprised that the message receiving machinery was not a learning barrier for the mostly 12 year olds that we dealt with. The experiment that did happen was — if you can use Smalltalk-72 at all, you have also learned how to extend both the syntax and semantics (and that worked quite well).

        The other interesting thing about Smalltalk-72 was that any object was also an interpreter for the messages sent to it, so that set of mysteries was exposed from the beginning.

        Reply
        • 11. alanone1  |  April 6, 2018 at 11:21 am

          P.S. I should have mentioned that the “Manual” was not for the kids, but as documentation for general adults as part of what it meant to do computer science in those days.

          In the manual, there is a part that shows how we taught the children — Adele’s “Joe the box”, done in a narrative style so the reader can follow along.

          Just as in Etoys, we found that a session of 1-to-1 hands on tutoring using already existing objects was the fastest and surest way to foster learning.

          Reply
  • 12. gasstationwithoutpumps  |  April 6, 2018 at 5:03 pm

    Your post here contrasts interestingly with my latest post:
    https://gasstationwithoutpumps.wordpress.com/2018/04/04/quiz-disappointment/
    In which I ended up quizzing students right after they had seen a detailed working of the exact quiz question.

    It would have been interesting if you had given the quiz again right after your live coding session and seen how many could then get the solution right.

    Reply
    • 13. Mark Guzdial  |  April 8, 2018 at 8:36 am

      I saw your post and had the same thought, that we’re both trying to respond to disappointing quiz grades in our teaching. I agree that it would have been interesting to re-do the quiz. I also like that we’re both making changes because of empirical data, vs student comments.

      Reply
  • […] was reading Mark Gudial’s recent blog post and thought it was a great example of something I’ve been ruminating on recently… […]

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Trackback this post  |  Subscribe to the comments via RSS Feed


Recent Posts

April 2018
M T W T F S S
« Mar   May »
 1
2345678
9101112131415
16171819202122
23242526272829
30  

Feeds

Blog Stats

  • 1,526,805 hits

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 5,288 other followers

CS Teaching Tips


%d bloggers like this: