Bits and Behavior
Published in

Bits and Behavior

The tail end of a Dagstuhl break.

Dagstuhl trip report: learning and teaching programming language semantics

  • What affects a programming language’s semantics learnability?
  • Are notional machines necessary to support learning, or can learners just learn the semantics through causal inference?
  • What are the consequences of notional machines imperfectly conveying programming language semantics on learning, productivity, and software defects?
  • What are the most effective ways of teaching a notional machine?
  • Can a notional machine be equally effective at explaining a programming language’s semantics, or do they vary like most forms of instructional design based on prior knowledge, culture, and other factors?
Paul Denny gives his 80 second lightning talk.


Ben de Boulay, who coined the phrase “notional machines” in the 1980’s.

Ben de Boulay on notional machines

  • How do learner conceptions interfere with language semantics?
  • Are there studies comparing different types of notional machines?
  • Should we design languages for learnability, or just get better and teaching languages?
  • Should we teach notional machines for actual machines, or for abstract representations of machines?
  • Should notional machines be task, domain, and population-specific? Must they be in order to be effective?
  • How do you sequence learning? For novices, do you start with a full language, part of it, a toy language?
Tom Ball shares what he’s learned about Cognitively Guided Instruction

Cognitively guided instruction

Colleen Lewis explains knowledge in pieces

Knowledge in pieces

Informal poster sessions allowed for quick sharing
Mmm, beef curry.


Katie elegantly mapped several theories onto one framework

Structure, behavior, function

Robert Goldstone gives an epic survey of psychological factors

The psychology of programming

Ben Shapiro broadens our views to the sociocultural

Activity theory

Joe went into teacher mode to motivate the value of semantics.
The diagram that David Weintrop drew


  • The semantics of a programming language encode the abstract rules that govern the behavior of a program written in a programming language. (Though these semantics aren’t necessarily the same as the the semantics of the actual runtime that might execute a program.)
  • A notional machine is a pedagogical answer to the question “How do programs execution in this language” or “How does this program execute?” These might be natural language explanations, visualizations, diagrams, or other representations that answer this question in a way that produces learning about semantics. Notional machines are not perfect analogs of the semantics; they may be simplifications.
  • The result of encountering a notional machine should be a mental model in a learners’ mind. This may not perfectly reflect the notional machine conveyed.
Joe continued his tutorial on PL semantics after dinner.


More on semantics


Geoffrey Herman summarizes the group’s Gremlin metaphor of notional machines

Breakout reports

  • One group defined notional machines as a model between the source code and the actual machine, like a model of gravity that’s adequate within certain bounds, and useful to certain groups. Within this definition, notional machines can be stories and representations. This provoked questions like “What notional machines do instructors use and why?
  • Another group, led by my student Greg Nelson, focused more on mental models. They asked how to elicit and change learners’ mental models. They generated ideas like giving learners code, and having the make a video explaining how the code works, surfacing their mental models. They wondered how to validate assessments of mental models, whether mental models transfer between languages, how practice and feedback mediate the effect of notional machines on mental models, and whether to tell learners that notional machines are a simplification of semantics.
  • A third group wondered a lot about “lies” as well: how much should they simplify semantics, how much should they talk about these simplifications, and what choices do instructors make within this space? However, unlike the other groups, their questions were very teacher-centric. One reaction to this idea was that very few teachers actually know the “truth” about programming language semantics.
Sally Fincher draws a picture of semantic waves, placing notional machines at the bottom of the wave.
Shriram tries to refine what he views as a notional machine at a lower level of granularity.

Examples of notional machines

  • Explanations of semantics have a model of what’s happening in the machine, such as what is stored in memory.
  • Explanations have a view of that model of what is shown about the machine.
  • Explanations have a notion of the rules that govern the machine. Shriram argued that the rules are the notional machine.
  • Python Tutor provides no notional machine because it doesn’t explain the rules governing Python program execution. It does have a visualization of the machine’s content and behavior, but not the rules that shape it’s behavior.
  • Greg Nelson’s PLTutor does have a notional machine, because it does everything Python Tutor does, but also explains that rules that govern program execution.
  • Mark Guzdial showed several examples explaining the rules governing Smalltalk message passing, most of which were natural language sets of rules.
  • Shriram showed examples from How to Design Programs, which included a series of “rules of evaluation”, some of which deferred to algebraic expressions, but also function evaluation rules and conditional evaluation rules in prose, with code examples to teach the rules.

Brainstorming notional machines

  • Some notional machines leverage metaphor, implying semantic rules by leveraging prior knowledge about rules learners might have already encountered. For example, when we were looking at a program that had a dictionary data structure, some groups used metaphors of phone books to explain lookup behavior.
  • Some notional machines articulated mechanistic rules, similar to formal semantics. For example, in the dictionary example, a rule might be “the system reads the string between the brackets and then finds the matching string in the dictionary.”
  • Some notional machines expressed condition action rules for learners, such as “when you see an error like this, this is what you need to do to fix it.” These don’t really explain the rules governing program execution, but they do give learners a chance of inferring them.


Somehow, I was alone at the beginning of dinner, so I snapped a sad selfie. My randomly assigned table mates eventually arrived.

Dinner and evening

  • If what we teach is in a classroom, and how we assess that knowledge is in a classroom, but the point of the learning was for knowledge to be applied in the world, does any of the classroom knowledge actually transfer?
  • What is the “context” of learning programming? Is it really a classroom, or is it an IDE, or a rectangular layout of code, or just the text of code itself? And if knowledge is sensitive to these media, does practice and assessment on paper generalize to IDEs?
  • If a critical part of the context of programming in industry is the social context of programming, why do we try so hard to eliminate that context from learning contexts?
The breakout group on notional machines for non-programming language machines


  • Notional machines for things other than programming languages
  • Notional machines for Python and Scratch
  • Categorizing notional machines and the representations they use
  • Understanding the utility of notional machines for learning
  • Designing the instructional content of notional machines
Some examples of formalisms beyond programming languages that also need notional machines.

Notional machines beyond programming languages

  • Machine learning. The semantics of machine learning are quite different from PL semantics. How do we explain them and how do those explanations relate to explainability and interpretability discourses?
  • APIs/frameworks/libraries. One way to think of these is as programming languages with semantics but without syntax. Model view controller frameworks, React, callbacks, and other black boxed worlds all require some understanding of the semantics of these software architectures.
  • Distributed programs have their own unique semantics around coordinating independent machines.
  • Human-in-the-loop systems, including things like Mechanical Turk, Task Rabbit, and other forms of human computation where there’s some formalism, but also some component of human decision making and computation embedded in this formalism.
  • Spreadsheets and reactive languages, which have constraints, circular dependencies, and other invisible aspects of computation.
  • Game mechanics, which specify rules governing human decisions in a formal social context.
  • Proofs, which have their own semantics but often have no guidance.
  • Notional machines can use passive and active voice; these often indicate who is doing the work, the programmer or the computer.
  • Figuring out the triggering event that demand a notional machine is key to understanding both audience and context.
  • It’s often critical to take a language and envision a sequence of sublanguages in order to simplify the introduction of semantics.
  • Even really simple examples in JavaScript are really complex. For example, the code “black” is full of complexities about global objects, properties, special properties that affect the DOM, the lack of a need to define properties, CSS. This reveals the complexity of sequencing sublanguages of JavaScript, since even simple examples involve so much semantics.
A Dagstuhl photo in front of the chapel is a longstanding Dagstuhl tradition. I snapped a selfie before the official shot.

Other breakouts

  • One group explored the role of meta-cognition of semantics during program writing, and how to teach them in a way that ensures that learners simulate program behavior during program writing. They hypothesized that simulation is the moment of maximum impact of a notional machine; students may bring to bear a notional machine explanation at moments of confusion about semantics. They designed a study to explore this theory to try to answer the question “what events embedded in programming trigger students to trace code behavior?” by investigating learners doing a series of tasks in pairs to be able to observe tracing behavior.
  • Another group explored the dimensions along which notional machines vary, such as form, concept, semantics, learning goal, motivation for the student, how long it takes to teach, granularity, applicability, and audience. The group met further and distilled these dimensions, and tested them against several notional machines for different aspects of programming languages.
  • A third group talked about specific notional machines for Python and Scratch. They talked about Greg Wilson’s 14 rules of Python, and deconstructed the ways that it has different resolutions of detail, and layered references to semantics of other languages. In their second breakout, they dug deeper into Python and tried to design a learning progression of notional machines for Python, which involved adding a succession of semantic rules.
  • The other group talked about instructional design as it relates to notional machines. They generated guidelines for integrating notional machines, practice, and instruction together. The guidelines included things like “use diverse representations”, “bridge different representations”, “leverage human endowments such as gestures, audio, video”, “sustain engagement”, “mixing practice and instruction”, “adapt to social context”.
Ben Shapiro structures our thinking about JavaScript and the DOM.
When Mark asked me to get us ukulele, I had no clue why he asked *me* to get it. It made sense in hindsight!


  • Imagine all schools teach CS, but we have to use new languages, and have 5 years to figure it out. What do we design?
  • Imagine that Java is outlawed. How do we recover in CS education?
  • Imagine the world becomes Racket, Scala, and Haskell. What should the computing education undergraduate education community do?
Our large group engaged in deep thought.
  • It’s not enough to think about languages. One must also think about the tool and API ecosystem to support it.
  • There are many kinds of possible language semantics; what semantics do we think are important and how would we sequence them?
  • If we made programming language learning trivial, a lot of these questions about which language wouldn’t matter; people would just learn many languages.
  • The discussion revealed that many of the implicit learning objectives in CS curriculum are about programming and program design, not programming languages.
  • For some learning objectives, such as self-efficacy and programming problem solving, choice of programming language may or may not have a large impact.
  • Part of considering the language is also considering the language community and culture. This determines authenticity, how students see authenticity, and how they perceive cultures of computing.
  • Many learners many only ever learn one language. That’s in tension with ideas of having multiple language learning progressions.
  • Our local education policies and learning objectives likely define requirements for our programming languages, which demands different programming languages.
Greg Nelson talks about the importance of systems thinking in all of our reflection on computing education.

Closing thoughts

  • Programming language semantics are hard to understand, especially in their formal form.
  • Teaching semantics requires finding ways of explaining them that connect to students’ prior knowledge, but also engaging students in wanting to learn semantics.
  • There are many strategies for teaching semantics, including choosing languages with simpler semantics, developing learning progressions tied to sublanguages, and not only explaining, but assessing learners’ understanding of semantics.
  • Understanding programming language semantics is far from adequate for learning to program; we need to design ecosystems of tools, documentation, and communities for anyone to create anything meaningful with programming languages.
  • Programming languages are culturally-situated, value-laden artifacts, and therefore we are likely to need very different languages in different learning contexts.
  • We know almost nothing about programming language knowledge transfer, but computer scientists appear to strongly believe that transfer is trivial.
  • There are many media that can embody explanations of semantics, including books, interactive learning technologies, and even just teacher’s verbal articulations. We know little about the affordances these different media involve.
The original Dagstuhl castle after a morning of light rain.



This is the blog for the Code & Cognition lab, directed by professor Amy J. Ko, Ph.D. at the University of Washington. Here we reflect on our individual and collective struggle to understand computing and harness it for justice. See our work at

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Amy J. Ko

Professor of programming + learning + design + justice at the University of Washington Information School. Trans; she/her. #BlackLivesMatter.