Home Notional Machines Community About

Representation-Based Notional Machines

What is a representation-based notional machine?

Representation-based notional machines map from a programming context to a context that is not a well known analogy but simply a different representation. There are different forms of such representations, such as diagrams, manipulatives, role-plays, and verbalizations.

Some representations are handmade (e.g., a diagram drawn on a board) while others are machine-generated (e.g., a visualization produced by a tool).

We collected and organized the following 38 representation-based notional machines:

Array as Clothesline
Representation
imperative / any Language:

Conceptual Advantage

Makes arrays tangible, embodied activity.

Draws Attention To

Arrays are compound data structures.
PLNM
array clothesline
array element clothespin
element index label on the pin
element value paper sheet in the pin
Collected by Felienne Hermans
Blackboard Processing
Representation
imperative / Processing Language:

Conceptual Advantage

Generates an idea of a dyamic program behavior.

Draws Attention To

How a program executes dynamically from a static program text.
PLNM
processor teacher
instruction action taken by teacher, reported in list
canvas drawing area on sheet of paper
Collected by Andreas Mühling
Call Stack as Diagram
Representation
imperative / any Language:

Conceptual Advantage

Distinguishes between variable values in the main function and the parameters and local variables in a called function.

Draws Attention To

Each function call/frame has its own set of stored values.
PLNM
local variable box with label at bottom of a frame labeled with function name
parameter box with label at the top of a frame labeled with function name
variable in main box with label in a frame called main
Collected by Craig S. Miller
Calls as Sequence Diagram
Representation
object-oriented / any Language:

Conceptual Advantage

Make visible the flow of computation through method calls and returns, showing how calls relate to objects, and how calls and returns are paired.

Draws Attention To

The idea of a method calls being communication between two objects.
PLNM
method call solid arrow from caller activation to callee activation
method return dashed arrow from callee activation to caller activation
activation tall box along lifeline from call arrow to return arrow
object box at top and lifeline down
thread line through all calls and returns from start to finish of diagram
Collected by Matthias Hauswirth
Control Flow as Graph 1. Sequence
Representation
imperative / Java Language:

Conceptual Advantage

See a method as a sequence of statements to execute, and make clear that that sequence starts when the method is called and ends when the method returns.

Draws Attention To

The idea of a 'sequence' in structured programming, where a sequence consists of statements to execute.
PLNM
statement rectangular node
control-flow between statements arrow from node to node
method entry round 'e' node at top
method exit round 'x' node at bottom
Collected by Matthias Hauswirth
Control Flow as Graph 2. Selection
Representation
imperative / Java Language:

Conceptual Advantage

Understand concept of selection from structured programming (conditional statements like if, if-else), and make clear that a statement may or may not execute, based on a decision taken earlier in the control flow.

Draws Attention To

The idea of a 'selection' in structured programming, where a data (the condition's value) is turned into control flow (the next statement to execute).
PLNM
... ...
if condition diamond-shaped node
condition outcome label on an arrow coming out of a condition (e.g., true, false)
Collected by Matthias Hauswirth
Control Flow as Graph 3. Multi-Way Selection
Representation
imperative / Java Language:

Conceptual Advantage

Understand concept of a multi-way selection (a conditional statement where the condition is not just a Boolean value, e.g., a switch-statement).

Draws Attention To

The idea of a multi-way 'selection' in structured programming, where a data (the condition's value) is turned into control flow (the next statement to execute).
PLNM
... ...
switch condition diamond-shaped node with multiple arrows leaving
switch cases label on arrows coming out of a switch (including 'default')
Collected by Matthias Hauswirth
Control Flow as Graph 4. Short-Circuit
Representation
imperative / Java Language:

Conceptual Advantage

Understand concept of short-circuit Boolean operators (|| and &&), and see how they only evaluate their right operand if needed.

Draws Attention To

The idea that for short-circuit Boolean operators, the second operand may never be evaluated (allowing common constructs like if (o!=null && o.length>0) ...
PLNM
... ...
|| in condition 'false' arrow to extra diamond node
&& in condition 'true' arrow to extra diamond node
Collected by Matthias Hauswirth
Control Flow as Graph 5. Repetition
Representation
imperative / Java Language:

Conceptual Advantage

Understand concept of repetition from structured programming (loops like while, do-while, or for), where a given statement can be executed multiple times, by simply following the arrows through the cycle.

Draws Attention To

The idea of a 'repetition' in structured programming, where control-flow leads to statements getting executed multiple times
PLNM
... ...
back edge arrow pointing to a node that came prior in the flow (introducing a cycle)
while-, do-while-, for-loop cycle in the graph
Collected by Matthias Hauswirth
Control Flow as Structured Code Annotations 1. Static Structure
Representation
imperative / any Language:

Conceptual Advantage

The notional machine is not an entirely separate representation from the code but acts as a secondary notation to add invisible aspects of the code execution.

Draws Attention To

Static view of control flow (possible paths), identification of expressions.
PLNM
control flow arrows, superimposed on the code
expression rectangular outline around expression, superimposed on the code
Collected by Peter Donaldson
Control Flow as Structured Code Annotations 2. Dynamic Behavior
Representation
imperative / any Language:

Conceptual Advantage

The notional machine is not an entirely separate representation from the code but acts as a secondary notation to add invisible aspects of the code execution.

Draws Attention To

Dynamic view of control flow (actual execution); evaluation of expressions; declaration, initialisation, access and assignment of variables.
PLNM
... (all aspects from 1-Static Structure)
instruction execution add current step number to arrow leading in, then execute by adding to or looking up information in memory table, expression evaluator, or output areas
expression evaluation copy expression, substitute values, and evaluate it in expression evaluation area
variable declaration find first blank column in memory table and add name of variable in first row; value added underneath if initialised
variable assignment find variable in the memory table, strike through existing entry, and add entry to row below.
conditionals and loops evaluate control expression to 'True' or 'False', then follow relevant labelled control path to next instruction
Collected by Peter Donaldson
Expression as Tree 1. Arithmetic
Representation
imperative, OO / Java Language:

Conceptual Advantage

A large fraction of code consists of expressions. Students already know about expressions from school arithmetic. This notional machine makes the structure of such simple expressions explicit, and provides a way to explain their bottom-up step-by-step evaluation.

Draws Attention To

The structure, typing, and evaluation of arithmetic expressions students still know from school.
PLNM
expression tree of nodes linked together
operator green node
operand hole in a node where a child node can be attached
subexpression inside expression subtree connected to a node's hole
type of subexpression blue tag above subexpressions's root node
numerical literal tree node labeled with the number
variable tree node labeled with name of variable of a numeric type
unary arithmetic operator (+, -) tree node with operator in front of a hole
binary arithmetic operator (+, -, *, /, %) tree node with operator between two holes
Collected by Matthias Hauswirth
Expression as Tree 2. Logic
Representation
imperative, OO / Java Language:

Conceptual Advantage

Makes explicit the fact that logic expressions have the same structural properties as the well known arithmetic expressions.

Draws Attention To

The structure, typing, and evaluation of expressions involving logic operators and Boolean literals.
PLNM
... (all aspects from 1-Arithmetic)
Boolean literal leaf tree node labeled with true or with false
variable leaf tree node labeled with name of variable of type boolean
unary negation operator (!) tree node with operator in front of a hole
binary logical operator (|, &, ||, &&) tree node with operator between two holes
Collected by Matthias Hauswirth
Expression as Tree 3. Objects
Representation
imperative, OO / Java Language:

Conceptual Advantage

Makes explicit the fact that object allocation, method invocation, and field access are just expressions and can be composed like any other expression.

Draws Attention To

The structure, typing, and evaluation of expressions involving instances and classes.
PLNM
... (all aspects from 2-Logic)
null tree node containing 'null'
this tree node containing 'this'
instantiation tree node with 'new', class name, and a parentheses containing comma-separated holes for constructor parameters
variable tree node containing name of variable of an Object type
instance field access tree node containing a hole, a dot, and a field name
instance method invocation tree node with a hole, a dot, and parentheses containing comma-separated holes for method parameters
class field access tree node containing class name, a dot, and a field name
class method invocation tree node with class name, a dot, and parentheses containing comma-separated holes for method parameters
Collected by Matthias Hauswirth
Expression as Tree 4. Arrays
Representation
imperative, OO / Java Language:

Conceptual Advantage

Makes explicit the fact that array allocation and access are also just expressions and can be composed like any other expression.

Draws Attention To

The structure, typing, and evaluation of expressions involving arrays.
PLNM
... (all aspects from 3-Objects)
array allocation tree node with 'new', element type, and [hole] for each dimension
array length tree node with a hole and '.length'
array element access tree node with a hole, and [hole]
Collected by Matthias Hauswirth
Expression as Tree 5. Comparisons & Conditionals
Representation
imperative, OO / Java Language:

Conceptual Advantage

Makes explicit the fact that comparisons are just expressions (they produce a boolean value), and that one can construct expressions with the ternary conditional operator (providing a boolean value as the first operand).

Draws Attention To

The structure, typing, and evaluation of expressions involving comparisons and conditionals.
PLNM
... (all aspects from 4-Arrays)
binary comparison operator (==, !=, <, <=, >=, >) tree node with operator between two holes
ternary conditional operator (?:) tree node with a hole for the condition, '?', a hole for the then-value, ':', and a hole for the else-value
Collected by Matthias Hauswirth
Function as Spreadsheet Cell
Representation
any / any Language:

Conceptual Advantage

The spreadsheet shows how input is transferred to output in several steps. It shows the core of the functionality that students need to implement. It allows students to experiment with changing input and functionality, and it provides students test cases.

Draws Attention To

It shows the students how output depends on input and calculation. It shows the different steps in the calculation.
PLNM
function cell transforming input to output
Collected by Johan Jeuring
Paper Linked Lists
Representation
imperative / Java Language:

Conceptual Advantage

Helps students plan and debug code

Draws Attention To

The fact that each reference can only point to a single thing
PLNM
Object Type written and underlined in a rectangle
variable variable name followed by a small box
int number written in a small box
reference arrow originating from a small box
null X written in a small box
local variable free floating
instance variable shown inside an object
Collected by Colleen Lewis
Physical Java 1. Arrays & Refs
Representation
imperative / Java Language:

Conceptual Advantage

Shows the need for references and shows int arrays as sequences of ints.

Draws Attention To

Two references can refer to the same array. And arrays are just sequences of variables.
PLNM
int number written on paper in a small blue pocket
int array sequence of int variables
variable variable name followed by a small box
stack frame rectangle with the method name written on the side containing all local variables
reference pocket containing a remote control with a ribbon to the referent
null empty pocket with an X shown in the back
Collected by Colleen Lewis
Physical Java 2. Physical Objects
Representation
imperative / Java Language:

Conceptual Advantage

Ignores instance variables when first introducing objects.

Draws Attention To

Creation of objects and aliasing.
PLNM
... (all aspects of Physical Java 1)
object a small stuffed animal with a resemblance to the name of the object
instance variables (not represented)
Collected by Colleen Lewis
Physical Java 3. Written Objects
Representation
imperative / Java Language:

Conceptual Advantage

Helps students plan code; avoids confusion of crossed out arrows.

Draws Attention To

The effect of resetting references.
PLNM
... (all aspects of Physical Java 1)
object object type written/underlined in a rectangle
int number written in a small box
instance variables shown in an object
Collected by Colleen Lewis
Physical Java 4. Refs as Arrows
Representation
imperative / Java Language:

Conceptual Advantage

Introduces references as arrows (i.e., something more standard)

Draws Attention To

Standard ways of drawing Java memory (X for null, arrows for references).
PLNM
... (all aspects of Physical Java 3)
reference arrow originating from a small box
null X written in a small box
Collected by Colleen Lewis
Physical Java 5. Paper List/ListNode
Representation
imperative / Java Language:

Conceptual Advantage

Helps students plan code; avoids confusion of crossed out arrows.

Draws Attention To

The effect of resetting references.
PLNM
... (all aspects of Physical Java 4)
local variable free floating variable
stack frame (not represented)
Collected by Colleen Lewis
Physical Java 6. Inheritance
Representation
imperative / Java Language:

Conceptual Advantage

Distinguish between the type of the reference and the type of the object.

Draws Attention To

Reference type constrains what methods can be called and object type determines what method is called.
PLNM
... (all aspects of Physical Java 2)
variable type sticky note with the name of the type next to the pocket that holds the reference
parent reference a remote control that only has buttons corresponding to the things that the parent object knows how to do.
child object a stuffed animal that - as a child - 'does what it wants' and not necessarily what the parent would do.
Collected by Colleen Lewis
Program State as Graph
Representation
object-oriented / Java Language:

Conceptual Advantage

Graphs make the relevant parts of program state explicit and support detailed explanations by instructor.

Draws Attention To

Program state, and especially variables and references.
PLNM
stack frame red rectangle, with method name and line number in left compartment, boxes for paremeters and local variables in right compartment
object purple rectangle, with class name in left compartment, boxes for instance variables in right compartment
array blue rectangle consisting of boxes for elements
static fields yellow rectangle, with class name in left compartment, boxes for class variables in right compartment
variable box inside a rectangle
reference value solid arrow pointing to a rectangle
primitive value value written inside a box
callee-caller relationship dashed red arrow from callee stack frame to caller stack frame
Collected by Craig S. Miller
Python Computer 1. Beginning
Representation
imperative / Python Language:

Conceptual Advantage

Expandable 'offline' model of program execution. In its beginning stage, it only covers control flow and variables (without references) of Python scripts.

Draws Attention To

Semantics of control flow in Python. Visible effects of each line on the 'state' of the Python computer.
PLNM
memory table of identifer and value
instruction update of state according to defined rules
variable entry in the table
conditional conditional evaluator (flag) that affects the 'program counter'
control flow program counter that identifies next line to get executed and is updated according to a set of rules
Collected by Andreas Mühling
Python Computer 2. Intermediate
Representation
imperative / Python Language:

Conceptual Advantage

Expandable 'offline' model of program execution. In its intermediate stage (V2) it covers everything of V1 plus definition and execution of sub-routines (functions) of Python scripts.

Draws Attention To

Scoping (global vs. local variables) and sub-routines with parameters and return values.
PLNM
... ...
method table table of identifier and starting line
scope 'sub-table' area in the memory
parameter entry in the memory sub-table of a function call
Collected by Andreas Mühling
Python Computer 3. Advanced
Representation
imperative / Python Language:

Conceptual Advantage

Expandable 'offline' model of program execution. In its advanced stage (V3) it covers everything of V1 and V2 plus lists and references.

Draws Attention To

Object types and references.
PLNM
... ...
heap object table of address and value
reference addresss used as a value (denoted in <...>)
object entry in object table with address and value
Collected by Andreas Mühling
Python Computer 4. Ultimate
Representation
imperative / Python Language:

Conceptual Advantage

Expandable 'offline' model of program execution. In its ultimate stage (V4) it covers everything of V1, V2 and V3 plus classes, objects and methods.

Draws Attention To

Methods and classes.
PLNM
... ...
method entry in the table of sub-routines
object entry in object table with address and value(s)
Collected by Andreas Mühling
Recursion Demo with Python Tutor
Representation
imperative / Python Language:

Conceptual Advantage

Demonstrates what happens to variable values when they are passed to a function. Distinguishes frame elements among each recursive call. Shows separate stack frames, each with own parameters and variables, for each recursive call.

Draws Attention To

Addition of each stack frame as each recursive call is made. Collapse of stack frame as function completes and returns value.
PLNM
frame group of elements with function name
parameter labeled box inside frame
local variable labeled box inside frame
Collected by Craig S. Miller
Stack and Heap Diagram 1. Objects
Representation
imperative, OO / Java Language:

Conceptual Advantage

Makes explicit the notion of an object, that groups together all the variables that correspond to the object's state.

Draws Attention To

An object's state.
PLNM
object red rounded rectangle, with class name containing instance variables
instance variable box inside object, with name, type, value
Collected by Matthias Hauswirth
Stack and Heap Diagram 2. Stack Frames
Representation
imperative, OO / Java Language:

Conceptual Advantage

Makes explicit the notion of a stack frame (activation record), that groups together all the temporary variables needed during a method execution.

Draws Attention To

A method's state (variables that have a lifetime as long as the execution of the method).
PLNM
stack one side of the drawing (labeled stack), containing zero or more stacked 'stack frame' rectangles
stack frame grey rectangle, with method name, containing local variables and parameters of the method
local variable box inside stack frame, with name, type, value
parameter box inside stack frame, with name, type, value
Collected by Matthias Hauswirth
Stack and Heap Diagram 3. References
Representation
imperative, OO / Java Language:

Conceptual Advantage

Makes explicit the notion of a reference, which refers to a specific object, and the notion of a null value as a reference that does not point anywhere.

Draws Attention To

References.
PLNM
... (all aspects of 1 - Objects and 2 - Stack Frames)
reference value arrow from a variable rectangle (anywhere, i.e., in the stack or the heap) to an object rounded rectangle
null value a ground symbol (i.e., the absence of an arrow)
Collected by Matthias Hauswirth
Stack and Heap Diagram 4. Arrays
Representation
imperative, OO / Java Language:

Conceptual Advantage

Makes explicit that arrays are heap objects where elements are accessed by index, and where the length is stored in a special read-only field. Particularly useful when explaining arrays of arrays.

Draws Attention To

Arrays.
PLNM
... (all aspects of 1 - Objects, 2 - Stack Frames, 3 - References)
array red rounded rectangle on the heap, labeled with array type
array element a field in the array, with index, type, and value
array length a field in the array, with name 'length' and type int, and a value corresponding to the number of elements
Collected by Matthias Hauswirth
Typed Boxes Memory
Representation
imperative & OO / Java, C#, ... Language:

Conceptual Advantage

Students need to understand that program variables (or collections of variables in an object) refer to memory locations, which might contain different kinds of values, and that statements (methods) change memory locations for variables (objects).

Draws Attention To

Different kinds of variables (objects) take up different space in memory. Statements and methods change the memory, which is visualized by changing the contents of the boxes when executing a statement or method.
PLNM
variable typed box/memory location
statement changes a memory location
object collection of boxes in memory
method changes an object
Collected by Johan Jeuring
Variable as Clothespin
Representation
imperative / any Language:

Conceptual Advantage

Makes variable tangible, helps prevent multiple values misconception

Draws Attention To

Variables contain *one* value
PLNM
variable clothespin
variable name label on the pin
value paper sheet in the pin
Collected by Felienne Hermans
Variable Trace Table
Representation
imperative / any Language:

Conceptual Advantage

Shows how variables are updated with assignments.

Draws Attention To

Variable values and their assignment.
PLNM
variable table heading
value last element listed in the column
Collected by Craig S. Miller
Verbal Expressions
Representation
imperative / any Language:

Conceptual Advantage

Distinguishes between (string) literals and variables that represent them. Makes white-space characters and punctuation explicit.

Draws Attention To

Individual characters in a string.
PLNM
literal string pronounce each character in string
variable pronounce 'the variable' and give its whole name
Collected by Craig S. Miller

Forms of NMs

Analogies Representations

What is a Notional Machine?

A notional machine is a pedagogic device to assist the understanding of some aspect of programs or programming.

About this Site

About Information for Developers Information for Contributors