The CodeCheck Tracer

The CodeCheck Tracer is a toolkit that lets you write code tracing exercises.

TL;DR If you just want to see how to program the tracer, go to this JSBin, select File → Clone, turn off “Auto-run with JS”, and start messing with the code.

Why Tracing?

In an introductory programming class, students learn the basic constructs of a programming language: variables, branches, loops, functions, arrays, objects. Given a sequence of instructions, they are expected to trace through the execution and determine the instruction order and the effect on the variables.

There are tools that visualize the execution of a program, such as the admirable Python Tutor and JGrasp. Students can watch and follow along.

However, watching a visualization, no matter how compelling, is not quite the same as the skill that we want students to have—to predict steps. This is an important skill for two reasons.

When first learning a programming language, students need to know the semantics of the language constructs. They need to be able to work out on their own which code is executed next, or which variable is updated, and what its new value is. Students who cannot do this are unlikely to be successful writing their own programs.

When debugging a program, students need to predict the expected behavior of each step, so that they can recognize mismatches between expectations and actual behavior. Without this ability, debugging is likely to be frustrating and unproductive.

How do you get your students to do code tracing? Have you tried pencil and paper? If your students are like mine, grading hand-written tables and diagrams can be a real chore. The submissions often exhibit an amazing degree of formatting variations. That is why you want a tool that collects student input and automatically provides a score.

Could one simply take a step-by-step visualizer and rig it so that the student predicts the effect of every step? Unfortunately, this is too tedious for all but the simplest cases. Instead, tracing exercises need to be scaffolded to lead students to the interesting parts of a situation, and to elicit only the predictions that are important in the given context. For that, you need a tracer that can be customized.

About the CodeCheck Tracer

The CodeCheck Tracer lets you author tracing exercises. You decide what the student should see: code fragments, variables, objects, arrays, and so on. You can make the program run up to an interesting point, then ask students to predict the next line, update a variable, draw a pointer, or choose among higher-level tasks (such as “move left/move right” in a binary tree).

You first map out the exercise in your mind, perhaps after studying some examples. Then you write the code for the “puppet master”. In each step, you either ask the student or update the program state yourself.

That code is written in JavaScript, but have no fear. If you know Java, C++, or Python, you can quickly pick up the few JavaScript constructs that you need. The students do not see any JavaScript (unless, of course, you happen to teach them JavaScript).

The CodeCheck tracer API takes advantage of advanced JavaScript features (generators, proxies) that greatly simpilfy authoring. To wait for student input, you simply use a yield expression. When you change the value of a path such as myObj.myField, the visual representation is automatically updated.

You put the code inside a web page, together with your instructions. Students simply work through your web page. Or you can use the CodeCheck service to publish the page and enable scoring. If you like, the scores can end up in your learning management system. Read on for the details!

I developed the tracer from interactive elements for my Big Java/Big C++/Python for Everyone books. Those books have different exercise types for tracing variables, objects, and algorithms. The CodeCheck tracer combines them all. And it is driven by JavaScript code instead three different ad-hoc markup languages.

I added the tracer to CodeCheck so that students can learn to program in a three-step process:

  1. Understand existing code (tracing—this document)
  2. Assemble programs from parts (CodeCheck Parsons puzzles)
  3. Write code with scaffolding (CodeCheck programming problems)

After mastering these skills, students should be prepared to write code from scratch, so that they are ready for your own labs and projects.

Examples

Before getting into the details of how to author your own tracing exercises, work through the following samples. They give you an idea of the capabilities of the CodeCheck tracer, and how to put it to use at various levels of algorithmic sophistication.

Swapping Two Variables

The following activity shows what happens when you swap two variables the wrong way:

And here is the right way:

Tracing a Loop

This is a classic loop tracing exercise: reversing a string. For many students, it is not obvious how the algorithm works from reading the code. Once they trace through the steps, they understand.

Array Insertion

When inserting an element into a partially filled array a, all elements beyond the insertion location must be shifted. This trace shows how it works:

Why does one start at the end and work downwards? This trace explores what would happen if one moved the elements starting at the insertion position instead of starting at the end of the array.

NB. When my editor—not a computer scientist—worked through this exercise, she was impressed and said that she finally understood why that section was in the book.

A Pointer Diagram

The following example demonstrates deletion of the first element in a linked list.

When I asked this question in an exam before I used a code tracer, I despaired grading the result. Seemingly every student created a slightly different notation for the diagram. If you can use the tracer in your exam, great. I wasn't, but after my students trace a number of linked list scenarios in their homework, almost all of them use the tracer notation in the exam.

Higher Level Steps

This is a classic activity for learning the algorithm for finding the maximum value of a sequence. The initial value becomes the largest. Then each value is compared against the largest, and if it is larger, the largest value is updated. Here is the source code snippet:

int largest = a[0];
for (int i = 1; i < a.length; i++)
{
   if (a[i] > largest) { largest = a[i]; }
}
// largest now holds the largest of the elements in a

Instead of manually updating variables, the student clicks buttons for incrementing the index and updating the largest value.

Here, the animated code is purposefully not shown so that it doesn't give the answer away.

The API

As you have seen in the preceding examples, each exercise displays code, data, or both and either updates it for the students to see, or asks students to do the updating. In this section, you will learn step by step how to author your own exercises.

The Exercise Description

The tracing exercises show up on a web page just like this one. Here is the template:

<html>
  <head>
    <title>A CodeCheck Tracer Exercise</title> 
    <meta charset='utf-8'/> 
    <link href='https://horstmann.com/codecheck/css/codecheck_tracer.css' rel='stylesheet' type='text/css'/>
    <script type="module">//<![CDATA[
import { addExercise, Code, Obj, Frame /* and others as needed */ } from 'https://horstmann.com/codecheck/script/codecheck_tracer.js'
addExercise(function* (sim) {
  ...
})
//]]>
    </script>
  </head> 
  <body>
     <!-- Description of the exercise here-->
  </body>
</html>

A web page can contain any number of tracing exercises. Simply call addExercise multiple times. If you add <div class='codecheck_tracer'> in the body, the exercises are placed there. Otherwise, they are appended to the end of the body.

Alternatively, you can use the CodeCheck service to publish a page with a single tracing exercise. Visit the upload link. Supply a file tracer.js with the JavaScript code that you would otherwise place inside the script tag, and a file index.html with the description.

The Generator Function

For each exercise, you provide a generator function. That is a special kind of function that can be suspended for student input, and resumed when the correct input has been provided. You use the yield keyword whenever your code needs to wait.

function* (sim) { // The generator function
  ...
  yield code.ask(10)
    // Suspend so the student can click on code line 10
  ...
  vars.fib = yield sim.ask(8, 'What is the next value of fib?')
    // Suspend so the student can enter 8
  ...
  yield sim.next('We go back to the top of the loop')
    // Suspend so the student can click a Next button
  ...
  yield sim.pause()
    // Suspend so that a few seconds can elapse
  ...
}

Everything between the calls to yield executes at full speed, updating your own variables or the simulation's display.

You do not need to know how generator functions work. Simply use yield whenever you want to yield for student input.

Code Blocks

During the simulation, you add visual elements: code blocks, variables, objects, arrays, and so on. The most common visual element is a code block:

const code = sim.add(0, 0, new Code(`
int a = 5;
int b = 8;
int temp = a;
...
`))

Use a template string for the code, enclosed in backticks `...`. Such strings can span multiple lines.

If you want the code to show up in a pseudocode font, construct the object as new Code(`...`, { pseudo: true }).

Later you call methods on the Code object such as code.go(lineNumber) or yield code.ask(lineNumber).

Note: If you omit the lineNumber in these commands, it defaults to one more than the current line.

Also note that you add the Code object to the sim object, here at position (0, 0). The coordinate system has the origin in the upper left corner. The units are the width and height used for a “normal-sized” variable.

The add method returns the item passed to it, permitting the following shortcut:

cost code = sim.add(0, 0, new Code(`...`))

Variables

You add simulation variables in groups called frames.

const vars = sim.add(5, 0, new Frame())

Then add variables like this:

vars.i = 0
vars.greeting = 'Hello'

Now the variables i and greeting are displayed inside the frame. At any point, you can read the value of a variable as vars.i or change it as vars.i = newValue.

Use the JavaScript delete operator to remove a variable from a frame:

delete vars.i

Note: You typically use one frame per function or method.

Note: If you only need a single variable, you still put it into a frame.

When asking the student to update the value of a variable, you have two choices. You can call

vars.i = yield sim.ask(vars.i + 1)

An edit field is displayed in the header area. The student must enter the provided value, here the value of vars.i + 1.

Once the student has entered the correct value, that value becomes the value of the yield expression.

Alternatively, you can call

yield sim.set(vars.i, vars.i + 1)

The first argument to sim.set is a path to a displayed value, here vars.i. The user must click on the i variable. Then an edit field pops up over the selected variable, and the user must enter the updated value.

Try out both forms. They have a different feel. The sim.set form is more work for the student, but it makes it very clear which variable will be updated. The sim.ask form is more appropriate once students have gained some experience.

Paths and Equality Testing

An expression such as vars.i, vars.a[j] or obj.field is called a path. In general, a path is formed from a top-level node (such as a Frame or Obj) followed by one or more field selectors or array indexes. Paths have three roles in the CodeCheck tracer:

  1. When the path expression occurs on the left hand side of an assignment, the value and its visual representation are updated. For example, vars.i = 1. (Technically, vars is a “dynamic proxy”.)
  2. When combined with other expressions, the path expression yields the value that is stored in the given location. For example, vars.i + 1
  3. In a call such as sim.set(vars.i, 2), the path describes the location of the value to be set.

Most of the time, you don't have to think about paths. However, in one aspect, the magic fails. You cannot use ==, ===, !=, or !== to compare two paths. For example, the test vars.j == vars.j will never succeed even if the values are the same.

This is annoying, as any leaky abstraction is. The easiest remedy is to use the sim.eq method:

sim.eq(vars.i, vars.j) 

Or if you prefer, force conversion into JavaScript primitives:

vars.i + 0 === vars.j + 0

Objects and Arrays

Objects work the same way as frames. Create one like this:

const fred = sim.add(0, 5, new Obj('Person'))
fred.name = 'Fred Flintstone'
fred.age = 42

The only difference between an object and a frame is the visual appearance. An object appears as a blob with multiple fields. A frame has separate variables.

Finally, arrays. They are like objects with fields named 0, 1, 2, and so on. There is a special field length (not displayed) that represents the number of elements.

const numbers = sim.add(5, 5, new Arr('int []'))
numbers[0] = 42
numbers[1] = numbers[0] + 1
numbers.length = 5

You use the [] operator to set or read array elements. Whenever you update an element, the visual representation is immediately refreshed.

Assigning to length grows or shrinks the array.

If you want to focus on an algorithm instead of the in-memory representation, use a Seq instead of an array. It works the same way, but it takes less space:

const vars = sim.add(0, 0, new Frame())
vars.fib = sim.add(new Seq())
vars.fib[0] = 1
vars.fib[1] = 1
for (let n = 2; n <= 5; n++) 
   vars.fib[n] = vars.fib[n - 1] + vars.fib[n - 2]

Pointers

When the value of a variable, field, or array element is a heap object or array, an arrow is drawn:

const node1 = sim.add(0, 0, new Obj('Node'))
const node2 = sim.add(3, 0, new Obj('Node'))
node1.data = 'Fred'
node2.data = 'Wilma'
node1.next = node2 // Drawn as a pointer
node2.next = 'null'

C Style Pointers

In C/C++, a pointer can point to an arbitrary variable, even inside an array or structure. In order to draw such a pointer, you create a memory address object like this:

vars.a = new Arr()
vars.a[0] = 1
vars.a[1] = 3
vars.a[2] = 5
vars.p = new Addr(vars.a[0])

C/C++ style pointers are only valid if you set the language to C or C++:

sim.language = 'cpp'

Because the C/C++ rules for pointers are quite subtle, be careful what address you take. For example, new Addr(vars.a) represents an int (*)[3], a pointer to an array of three integers. If you want an int* to the beginning of the array, use new Addr(vars.a[0]).

The Start Event

You often want to pre-populate the simulation with visual elements that match the description. To achieve this, write the code for showing the visual elements that should appear before the student hits the start button, followed by

yield sim.start()

The simulation waits until the student hits the Start button.

Buttons

A button enables the student to carry out an arbitrary meaningful action without having to laboriously update variables.

To add a button, use the addButtons method. You supply the button label.

sim.addButtons('a[j] = a[i]', 'i++', 'j++')

In your generator function, call

yield sim.click('i++') // Wait for the user to click the button with label i++
vars.i++ // Then do the step

Why use a button? That way, the student doesn't have to locate i, read its value, and type in the increment. Buttons make sense whenever you want students to think at a higher level than reading and setting variables.

Tip: When using buttons, it is often a good idea to add a button with label 'Done' and to end the simulation with

yield sim.click('Done')

Sequences and Matrices

When asking questions about array/list/vector or 2D array/matrix algorithms, it can be nicer to have a compact representation of the data. That is what the Seq and Mat classes provide.

Here is the code that generates these samples:

const seq = sim.add(0, 0, new Seq([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]))
seq.index.i = 0
seq.index.j = seq.length - 1
const mat = sim.add(0, 3, new Mat([[16, 3, 2, 13], [5, 10, 11, 8], [9, 6, 7, 12], [4, 15, 14, 1]]))
mat.rowIndex.i = 1
mat.columnIndex.j = 1

Note the index variables that adorn the bottom of the sequence and the fringe of the matrix. You can read and write their values. For example, you can move the index i to the right with the statement:

seq.index.i++

The Terminal

When tracing a program with terminal output, you can display a terminal such as this one.

Use the print, println, or input methods to display program output and input.

const term = sim.add(0, 0, new Terminal())
term.println('Hello Sailor!')
term.print('How old are you? ')
term.input(42)

You can ask the user to predict an output:

term.print('Next year, you\'ll be ')
yield term.ask(43)

You can even ask for an unconstrained input and use it:

let age = parseInt(yield term.ask())
term.println(`Next year, you\'ll be ${age + 1}`)

API Summary

The following tables summarize the code tracer API. Parameters marked with ? are optional. The ... symbol indicates a seqence of parameters.

The prompt string, or a suitable default, is displayed in the instruction area. The secondary prompt, if present, is displayed as “small print” below.

Methods of the sim object
Method Explanation
eq(x, y) Tests whether x and y are equal. Each argument can be a value of a path.
add(gridX, gridY, item) Adds the item at the given location and returns item
remove(item) Removes the item
addButtons(...labels) Adds a button for each of the given labels
yield ask(value, prompt?, secondary?) Suspend the simulation until the user has provided the requested value. If the value is a heap element or an Edge, the user must select it. If the value is an Addr, the user must select the field to which it points. Otherwise the user enters the value in an input field. If value is undefined, then the user can enter any value, and the entered value is returned from yield.
yield set(path, value, prompt?, secondary?) Suspend the simulation until the user has selected the path location and provided the requested value. If the value is a heap element, the user must select it. Otherwise the user enters it in an input field centered over the current path value. Subsequently, the path value is updated with the given value.
yield pause(prompt?, secondary?) Suspend the simulation for a short pause.
yield next(prompt?, secondary?) Suspend the simulation until the user has clicked the Next button.
yield click(label, prompt?, secondary?) Suspend the simulation until the user has clicked the button with the givel label.
Methods of the Obj, Arr, and Frame Classes
Method Explanation
constructor(title?, config?) Constructs an empty object, array, or variable frame. If config.emptyTitle is set, it is used when there are no fields/elements/variables. Otherwise title or config.title is used.
Methods of the Code Class
Method Explanation
constructor(code, config?) Constructs a code object with the given code. The current line is 1. If config.pseudo is true, the code is displayed with a handwritten font.
go(line?) Advances the current line to the given one, or if none is given, to the next line.
yield ask(...lines) Suspend the simulation until the user has selected one of the given lines, or if no lines are given, the next selectable line. If the last argument is a string, it becomes the prompt.
Methods of the Terminal Class
Method Explanation
constructor() Constructs an empty terminal.
print(text), println(text) Appends the text to the terminal.
input(text) Appends the text to the terminal, marking it as user input.
yield ask(text) Prompts the user to type the text to be printed. If text is undefined, the user can type any text, and yield returns the user input.

Randomization

If you like, you can randomize values in an exercise. You need to tell the simulation what random values you generated so that the same values are used when the student clicks the Start Over button, or when a partially solved exercise is restored in an assignment.

The sim object has some useful methods for generating random values:

Methods for Generating Random Values
Method Explanation
randInt(a, b) A random integer ≥ a and ≤ b
randFloat(a, b) A random floating-point number ≥ a and ≤ b
randBoolean() A random true or false
randCodePoint(a, b) A random Unicode code point ≥ a and ≤ b. The arguments can be integers or strings of length 1. For example, randCodePoint('a', 'z') is a random lowercase letter.
randSelect(a, b, c, ...) Randomly selects one of the arguments.
randWord() Randomly selects a word from a list of about 3000 common and inoffensive English words.
randString(len, a, b) Randomly makes a string of the given length with characters ≥ a and ≤ b.
randIntArray(len, a, b) Fills an array of the given length with random integers ≥ a and ≤ b.
randDistinctInts(len, a, b) Fills an array of the given length with distinct random integers ≥ a and ≤ b.
randIntArray2(rows, columns, a, b) Fills a two-dimensional array of the given dimensions with random integers ≥ a and ≤ b.
randFloatArray(len, a, b) Fills an array of the given length with random floating-point numbers ≥ a and ≤ b.
randFloatArray2(rows, columns, a, b) Fills a two-dimensional array of the given dimensions with random floating-point numbers ≥ a and ≤ b.
randWordArray(len) Fills an array of the given length with random English words.
randSeed(seed?) Seeds the random number generator with a seed between 0 and 1. If no seed is supplied, a random seed is used and returned.

To use randomization, your generator function needs to have two parameters:

function* (sim, state)

If previous state is restored, the state variable is set, and you should use the state. Otherwise it is undefined, and you should initialize the state with your choice of random values:

if (state === undefined) {
  state = {
    a: Math.random(),
    b = Math.trunc(1 + 10 * Math.random())
  }
}

Use the state to initialize your variables:

vars.a = state.a
vars.b = state.b

If you only use the rand utility functions of the sim object, you can simply use the seed as the state:

if (state === undefined) {
  state = { seed: sim.randSeed() }
} else {
  sim.randSeed(state.seed)
}

Finally, call sim.start with the state, so that the simulation can give it back to you when the exercise is restarted:

yield sim.start(state)

Being the Puppet Master

To use the API effectively, you want to have the desired dialog with the student in mind. Except for the shortest code snippets, it is not effective to ask the student to click on every line and supply the new value of every variable.

Designing the Trace of an Event Sequence

Consider this example of swapping two variables.

int a = 5;
int b = 8;
int temp = a;
a = b;
b = temp;

Place the code inside a code element, and provide a frame for the variables:

const code = sim.add(0, 0, new Code(`
int a = 5;
int b = 8;
int temp = a;
a = b;
b = temp;`))
const vars = sim.add(0, 5, new Frame())

You do not want to bother the student with tracing the first two lines. They do not contribute to the core insight about swapping on which the student should focus. Instead, show the first two lines in slow motion:

vars.a = 5
yield sim.next('Initialized a') // Wait for the student to hit the Next button
code.go(2) 
vars.b = 8
yield sim.next('Initialized b')

Next, let's involve the student and ask about the value with which temp is initialized:

code.go(3)
vars.temp = yield sim.ask(vars.a)

That is followed by

code.go(4)
vars.a = yield sim.ask(vars.b)

and

code.go(5)
vars.b = yield sim.ask(vars.temp)

Note: You can use code.go() instead of code.go(2), code.go(3), and so on.

Note: Be sure not to forget the yield before sim.ask. The command

vars.temp = sim.ask(vars.a) // ERROR

sets vars.temp to the command that sim.ask wants to pass to the caller of the generator function.

Note: Instead of making the student click Next twice, you can use pause:

vars.a = 5
yield sim.pause('Initialized a') // Waits a few seconds
code.go(2)
vars.b = 8
yield sim.pause('Initialized b')

Note: If you want the student to click on the variables, use

yield sim.set(vars.temp, vars.a)

instead of

vars.temp = yield sim.ask(vars.a)

Tip: Experiment with these changes at this JSBin or JSFiddle. JSBin makes it easy to get started, but JSFiddle is a bit better for debugging.

Designing the Trace of a Loop

Consider the following loop that adds the digits of a number:

int n = 1729;
int sum = 0;
while (n > 0)
{
   int digit = n % 10;
   int sum = sum + digit;
   n = n / 10;
}
// ...

Let's start by translating to JavaScript without student interaction:

vars.n = 1729
code.go(); vars.sum = 0
code.go()
while (vars.n > 0)
{
  code.go(5); vars.digit = vars.n % 10
  code.go(); vars.sum = vars.sum + vars.digit
  code.go(); vars.n = Math.trunc(vars.n / 10)
  code.go(3)
}
code.go(9)

As written, this simulation will race through the steps of the algorithm and show the final result.

Which parts should the student do? Initializing n or moving to line 2 is busywork. But we want the student to realize how the digits are formed, and how the loop comes to an end:

vars.n = 1729
code.go(); vars.sum = 0
code.go()
while (vars.n > 0)
{
  yield code.ask(); vars.digit = yield sim.ask(vars.n % 10)
  code.go(5); vars.sum = yield sim.ask(vars.sum + vars.digit)
  code.go(); vars.n = yield sim.ask(Math.trunc(vars.n / 10))
  code.go(3)
}
yield code.ask(9)

That's a pretty effective exercise. Check it out at this JSFiddle

As an enhancement, you can randomize the array:

if (state === undefined) {
  state = {}
  state.n = sim.randInt(1000, 9999)
}
vars.n = state.n
yield sim.start(state)  

If you are ambitious, you can decide that the assignment to sum is boring after a couple of steps, and only ask it the first two times:

let count = 0
...
while (vars.n > 0)
{
  count++
  ...
  if (count <= 2) vars.sum = yield sim.ask(vars.sum + vars.digit)
  else { vars.sum = vars.sum + vars.digit; yield sim.next('The sum is updated') }
  ...
}

It is up to you how much work you put into an exercise. The key is to start simple and then to eliminate busywork that distracts from the key points that you want your students to think about.

Embedding the Tracer as an Iframe

If you embed a page with one or more tracer activities as an iframe, and add the script https://horstmann.com/codecheck/splice/splice-iframe.js to the head of your page, it will send messages to the parent, using postMessage. You would only care if you are building some kind of system that tracks user activity in tracer exercises.

The messages follow the draft SPLICE protocol, which is documented here.