Defining: What does it mean to understand computing?

May 24, 2012 at 7:52 am 26 comments

In the About page for this blog, I wrote, “Computing Education Research is about how people come to understanding computing, and how we can facilitate that understanding.”  Juha Sorva’s dissertation (now available!) helped me come to an understanding of what it means to “understand computing.”  I describe a fairly technical (in terms of cognitive and learning sciences) definition, which basically is Juha’s.  I end with some concrete pedagogical recommendations that are implied by this definition.

A Notional Machine:  Benedict DuBoulay wrote in the 1980’s about a “notional machine,” that is, an abstraction of the computer that one can use for thinking about what a computer can and will do.  Juha writes:

Du Boulay was probably the first to use the term notional machine for “the general properties of the machine that one is learning to control” as one learns programming. A notional machine is an idealized computer “whose properties are implied by the constructs in the programming language employed” but which can also be made explicit in teaching (du Boulay et al., 1981; du Boulay, 1986).

The notional machine is how to think about what the computer is doing.  It doesn’t have to be about the CPU at all. Lisp and Smalltalk each have small, well-defined notional machines — there is a specific definition of what happens when the program executes, in terms of application of S-expressions (Lisp) and in terms of message sending to instances of classes (Smalltalk).  C has a different notional machine, which isn’t at all like Lisp’s or Smalltalk’s.  C’s notional machine is closer to the notional machine of the CPU itself, but is still a step above the CPU itself (e.g., there are no assignment statements or types in assembly language). Java has a complicated notional machine, that involves both object-oriented semantics and bit-level semantics.

A notional machine is not a mental representation.  Rather, it’s a learning objective.  I suggest that understanding a realistic notional machine is implicitly a goal of computational thinking.  We want students to understand what a computer can do, what a human can do, and why that’s different.  For example, a computer can easily compare two numbers, can compare two strings with only slightly more effort, and has to be provided with an algorithm (that is unlikely to work like the human eye) to compare two images.  I’m saying “computer” here, but what I really mean is, “a notional machine.”  Finding a route from one place to another is easy for Google Maps or my GPS, but it requires programming for a notional machine to be able to find a route along a graph.  Counting the number of steps from the top of the tree to the furthest leaf is easy for us, but hard for novices to put in an algorithm.  While it’s probably not important for everyone to learn that algorithm, it’s important for everyone to understand why we need algorithms like that — to understand that computers have different operations (notional machines) than people.  If we want people to understand why we need algorithms, and why some things are harder for computers than humans, we want people to understand a notional machine.

Mental Models:  A mental model is a personal representation of some aspect of the world.  A mental model is executable (“runnable” in Don Norman’s terms) and allows us to make predictions.  When we turn on and off a switch, we predict that the light will go on and off.  Because you were able to read that sentence and know what I meant, you have a mental model of a light which has a switch. You can predict how it works.  A mental model is absolutely necessary to be able to debug a program: If you have to have a working expectation of what the program was supposed to do, and how it was supposed to get there, so that you can compare what it’s actually doing to that expectation.

So now I can offer a definition, based on Juha’s thesis:

To understand computing is to have a robust mental model of a notional machine.

My absolutely favorite part of Juha’s thesis is his Chapter 5, where he describes what we know about how mental models are developed.  I’ve already passed on the PDF of that chapter to my colleagues and student here at Georgia Tech.  He found some fascinating literature about the stages of mental model development, about how mental models can go wrong (it’s really hard to fix a flawed mental model!), and about the necessary pieces of a good mental model.  DeKleer and Brown provide a description of mental models in terms of sub-models, and tell us what principles are necessary for “robust” mental models.  The first and most important principle is this one (from Juha Sorva’s thesis, page 55):

  • The no-function-in-structure principle: the rules that specify the behavior of a system component are context free. That is, they are completely independent of how the overall system functions. For instance, the rules that describe how a switch in an electric circuit works must not refer, not even implicitly, to the function of the whole circuit. This is the most central of the principles that a robust model must follow.

When we think about a switch, we know that it opens and closes a circuit. A switch might turn on and off a light. That would be one function for the switch. A switch might turn on and off a fan. That’s another function for a switch. We know what a switch does, completely decontextualized from any particular role or function.  Thus, a robust mental model of a notional machine means that you can talk about what a computer can do, completely apart from what a computer is doing in any particular role or function.

A robust mental model of a notional machine thus includes an understanding of how an IF or WHILE or FOR statement works, or what happens when you call a method on an object in Java (including searching up the class hierarchy), or how types do — completely independently of any given program.  If you don’t know the pieces separately, you can’t make predictions, or understand how they work a particular function in a particular program.

It is completely okay to have a mental model that is incomplete.  Most people who use scissors don’t think about them as levers, but if you know physics or mechanical engineering, you understand different sub-models that you can use to inform your mental model of how scissors work.  You don’t even have to have a complete mental model of the notional machine of your language.  If you don’t have to deal with casting to different types, then you don’t have to know it.  Your mental model doesn’t have to encompass the notional machine.  You just don’t want your mental model to be wrong.  What you know should be right, because it’s so hard to change a mental model later.

These observations lead me to a pedagogical prediction:

Most people cannot develop a robust mental model of a notional machine without a language.

Absolutely, some people can understand what a computer can do without having a language given to them.  Turing came up with his machine, without anyone telling him what the operations of the machine could do.  But very few of us are Turings.  For most people, having a name (or a diagram — visual notations are also languages) for an operation (or sub-model, in DeKleer and Brown terms) makes it easier for us to talk about it, to reference it, to see it in the context of a given function (or program).

I’m talking about programming languages here in a very different way than how they normally enter into our conversation.  In much of the computational thinking discussion, programming is yet another thing to learn.  It’s a complexity, an additional challenge.  Here, I’m talking about languages as a notation which makes it easier to understand computing, to achieve computational thinking.  Maybe there isn’t yet a language that achieves these goals.

Here’s another pedagogical recommendation that Juha’s thesis has me thinking about:

We need to discuss both structure and function in our computing classes.

I suspect that most of the time when I describe “x = x + 1” in my classes, I say, “increment x.”  But that’s the function.  Structurally, that’s an assignment statement.  Do I make sure that I emphasize both aspects in my classes?  They need both, and to have a robust mental model, they probably need the structure emphasized more than the function.

We see that distinction between structure and function a lot in Juha’s thesis.  Juha not only does this amazing literature review, but he then does three studies of students using UUhistle.  UUhistle works for many students, but Juha also explores when it didn’t — which may be more interesting, from a research perspective.  A common theme in his studies is that some students didn’t really connect the visualization to the code.  They talk about these “boxes” and do random walks poking at graphics.  As he describes in one observation session (which I’m leaving unedited, because I enjoyed the honesty of Juha’s transcripts):

What Juha describes isn’t unique to program visualization systems. I suspect that all of us have seen or heard something pretty similar to the above, but with text instead of graphics.  Students do “random walks” of code all the time.  Juha talks a good bit about how to help his students better understand how UUhistle graphical representations map to code and to the notional machine.

Juha gives us a conceptual language to think about this with.  The boxes and “incomprehensible things” are structures that must be understood on their own terms, in order to develop robust mental models, and understood in terms of their function and role in a program. That’s a challenge for us as educators.

So here’s the full definition:  Computing education research is about understanding how people develop robust models of notional machines, and how we can help them achieve those mental models.

Entry filed under: Uncategorized. Tags: , , , .

NCWIT Pioneer Awards to two women of Project Mercury: Following their passions Stereotype threat and growth mindset: If we tell students intelligence is malleable, are we lying?

26 Comments Add your own

  • 1. Marty J Wolf  |  May 24, 2012 at 11:16 am

    How do “function” and “structure” differ from the notions “semantics” and “syntax”? I often have students think about these two notions and that there are different “syntaxes” for achieving the same semantics. ++x, x++, and x = x + 1 are different syntaxes to implement the semantics of “increment x”.

    Also, does your full definition (the last sentence) say precisely what you want it to say?

    • 2. Mark Guzdial  |  May 24, 2012 at 11:26 am

      “Semantics” and “syntax” are CS terms. “Function” and “structure” are used in other areas of science education. Ashok Goel and Cindy Hmelo teach the respiratory system in terms of structure (lungs, blood), behavior (how oxygen enters the bloodstream), and function (we live). Using structure, behavior, and function ties to a larger and better studied literature in science education.

      I hope my last sentence says what I want it to say! 🙂 But of course, I might have missed something. Please ask, or point out where you think there’s a mistake.

      • 3. Marty J Wolf  |  May 24, 2012 at 12:28 pm

        It seems to me that CSEd research could also be about how we help students achieve those mental models. The last phrase “we can help them achieve those mental models” says, at least to me, that we can do it, rather than stating that how we do it is part of CSEd research.

        • 4. Mark Guzdial  |  May 24, 2012 at 12:37 pm

          Ah — improperly defined parallel structure on my part! I meant for the “how” to apply to both phrases. I added in a second “how” to make that explicit. Thanks!

          • 5. Marty J Wolf  |  May 24, 2012 at 12:40 pm

            You’re welcome. And thank you for your blog. I have learned a lot and been inspired by it.

    • 6. chaikens  |  May 25, 2012 at 1:41 pm

      This semester I had begun to plan and execute some CS1 teaching elements in terms I called “meaning” and “purpose”. I’m glad to see related distinctions being rigorously investigated by Juha. Structure is an another category. The structure of x=x+1 is “assignment statement” plus the structure of its parts (variable and constant reference, arithmetic operator, assignment operator). The meaning “increment x” is meaningful in terms of the notional model (THANKS!). The purpose is why the programmer wanted to have the computer increment x at that particular spot in a dynamic execution of the code. It think the term “function” used above relates more to the meaning but it might entail the purpose.

      Juha’s results seem (from your summary) to imply that ALL these distinct things-to-understand are critical, and therefore equally so. Can’t wait to read it!

      We can now teach and question our students about structure, function, meaning, purpose, etc, in those terms.


  • 7. Shuchi Grover  |  May 24, 2012 at 11:29 am

    Thanks for sharing, Mark! This hits so very close to home. I would welcome an opportunity to have an in-depth discussion with you sometime and the approach I am working on taking to study/achieve these very same goals.

  • 8. Rob St. Amant  |  May 24, 2012 at 12:08 pm

    Very insightful, Mark. Thanks.

  • 9. Software Carpentry » No CT Without PL  |  May 24, 2012 at 1:11 pm

    […] a blog post earlier today, Mark Guzdial argues that computational thinking requires learning with a programming language. Unlike many such claims and counter-claims, his is based on a wealth of research, most recently an […]

  • 10. kjderricks  |  May 24, 2012 at 3:36 pm

    Reblogged this on kjderricks.

  • 11. Christian  |  May 25, 2012 at 6:32 am

    I disagree when you write that it is possible to understand what a computer can do without a language. The only evidence you cite is Turing, but he used English and mathematics as languages. Same with Von Neumann.Their programs looked like mathematical formulas. Would you care to clarify this point?

    • 12. Mark Guzdial  |  May 25, 2012 at 10:07 am

      Turing, and the inventors of the first electronic computers, invented their language. They created abstractions, which they defined on top of languages like mathematics and English and circuits. I would not bet against human capacity for learning and invention — I will be that SOME people can develop a mental model of a notional machine without a supportive notation. Those unusual people will invent their own. But given what we know about learning, MOST people will not.

      • 13. chaikens  |  May 25, 2012 at 2:12 pm

        Turing somehow invented an abstraction of what human computers do and together with that used mathematically-styled English, including defined notations like many other mathematicians do, to describe “programs” and a code for them as data. This “programming language” code HAD to be formalized in order to prove the undecidability results; not because (I guess) strict formalization is necessary for expressing algorithms to people. What Turing thought of first is a mystery of genius!
        PS: See
        for a review of
        Turing’s Cathedral: The Origins of the Digital Universe
        by George Dyson
        Pantheon, 401 pp., $29.95
        It suggests that von Neumann fulfilled the vision of a realization of Turing’s Universal Turing Machine (and he gave no credit to Turing!)

  • 14. gasstationwithoutpumps  |  May 25, 2012 at 10:45 am

    So, are the language wars among different computer science and computer engineering educators because of differences in belief about pedagogy, differences in the ease of constructing mental models given different languages, or differences in the desired notional machine?

    I suspect that people have been assuming that the goals of “teaching programming” are the same between different approaches, ignoring differences in the notional machine that they expect students to build mental models for.

    Are the calls for students to have multiple computer languages mainly about translating one notional machine between different surface representations, or constructing mental models for different notional machines?

    • 15. Mark Guzdial  |  May 25, 2012 at 11:19 am

      I don’t know which of the three hypotheses you present is the most likely, though I suspect it’s the latter two more than the first. The advantage of learning two languages is that you have to generalize two notional machines and developing a mental model that covers both. You necessarily have to go beyond surface understanding, when the surface changes.

      • 16. chaikens  |  May 25, 2012 at 1:44 pm

        Of course, “simulating” one notional machine by another (each with its own language to best express its notions) is grist for the mill of theoretical computer science, And in systems we implement one notional machine with another!

  • 17. guy  |  May 29, 2012 at 2:09 pm

    very, very interesting… thanks for sharing Mark.

  • […] how code is created, what it can do, and how flexible it is.  It’s very much about developing a mental model of a notional machine and gaining procedural literacy. But even expert programmers, especially the self-taught ones, can […]

  • […] you’re trying to achieve in the next three steps”) and that doing so helps students to develop a mental model of the process.  He has shown that using subgoals in instruction can help with learning and improve transfer in […]

  • […] computing-for-all perspective, suggesting instead that programming is too hard and too boring.  Computing is important for everyone, but the tools may not be right yet.  It isn’t obvious to me that programming must be too hard, must be too boring.  How […]

  • […] that the programmer doesn’t have to understand the machine.  The programmer does have to understand the notional machine (maybe not the silicon one), and that’s critical to really understanding computing. A program […]

  • […] Harel is correct in much of what he points out about the current state of computer science education, and his arguments are not new to education. Mark Guzdial, professor in the School of Interactive Computing at Georgia Institute of Technology, makes a similar argument here. […]

  • […] am excited to get quoted (and correctly!) in an article about the Finnish approach to using programming to teach across the curriculum. […]

  • […] 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 […]

  • […] introductory students use debuggers, or use visualization tools effectively (see Juha Sorva’s excellent dissertation for a description of how student use visualizers)? My hypothesis is that debuggers and visualizers presume that the user has an adequate mental […]

  • […] In a blog post inspired by Juha Sorva, I suggested a refinement of my original definition.  “Coming to understand computing” means to develop a workable mental model or to learn a notional machine of a computing system. Programming is about intentionally defining a process for a computational agent to execute at another time. A notional machine is an explanation for the behavior of a system — it’s a teacher’s attempt to influence the mental model that the student is forming about the system.  I learned more about notional machines at a later Dagstuhl, and I’m excited to be attending a Dagstuhl Seminar this week where I’ll learn a lot more about notional machines. […]


Leave a Reply

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

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

Facebook photo

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

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

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

Join 10,185 other subscribers


Recent Posts

Blog Stats

  • 2,060,426 hits
May 2012

CS Teaching Tips

%d bloggers like this: