Next / Previous / Contents / Shipman's homepage

8. Trace tables

Constructing a trace table can be a useful way to self-verify your code. Trace tables are also useful in peer review.

The idea behind a trace table is to show all the state changes that occur during each possible path through a prime. This is another reason to keep the pieces of your design small: large, complex pieces have more possible execution paths.

To build a trace table, examine your intended functions and note the set of state items that appear on the left sides of the “:=”. Each row of the trace table corresponds to one state item. Each column represents a point in time. Each cell of the table, then, shows the value of a state item at a given point in one path through the prime.

Here is a very simple example. First, the code, a sequence of two primes. We number the primes for convenience in referring to them in the trace table.

    #-- 1
    # [ ally  :=  integers from 1 to n inclusive
    #   gumCount  :=  gumCount + 1 ]
    ally = range(1, n+1)
    gumCount += 1

    #-- 2
    # [ somey  :=  even elements of ally ]
    somey = [ k
              for k in ally
              if k%2 == 0 ]

Three state items appear on the left side of “:=” parts: ally, gumCount, and somey. So our trace table will have three rows. The table will have two columns: one column for the state after prime [1] and another column for the state after prime [2].

Filling in the trace table for this example. is straightforward. We examine the intended function for each prime. For each state item that changes, we enter the new state in the column for that prime. Describing the new state is another writing task: you may describe it algebraically, or in prose, or in any mixture of the two.

Here is the trace table after prime 1.

State itemAfter [1]
allyints in [1,n]
gumCountgumCount+1

Our description of the new state of ally is more modern math than Python: we use the notation [1,n] to mean a closed interval that uses the endpoints, and we use the term “int” to mean integers, figuring that anyone who reviews this code had better know Python at least that well. Know your audience: write your state descriptions so that your peer reviewers can understand them, given that they know the language and they are going to be looking at the code at the same time.

The new state for gumCount depends on the previous state, which is outside the scope of this code sequence. The expression “gumCount+1” means, whatever gumCount had in it when we started, it is one larger now.

Moving on to prime [2], we'll need to add a new row to the table for the new state item (somey) that changes. Here is the final table.

State itemAfter [1]After [2]
allyints in [1,n]ints in [1,n]
gumCountgumCount+1gumCount+1
somey even ints in [1,n]

For each of the four basic branch structures, there is a corresponding rule for constructing the trace table.

8.1. Trace table for sequence

The construction of the trace table for a sequence of two primes, A followed by B, is straightforward, as demonstrated in Section 8, “Trace tables”.

There is one additional consideration. The second prime, B, must be reachable. If prime A contains one of the forms described in Section 5.5.1, “Terminal special forms”, then clearly prime B can never execute. This is a red flag for peer reviewers.