Next / Previous / Contents / Shipman's homepage

8.2. Trace table for alternation

When your code uses the alternation branch structure, you will have to do two trace tables, one for each path through the code. Here is the general form:

    # [ if C ->
    #     A
    #   else ->
    #     B ]

If a prime contains such an alternation, here is how you construct the trace tables.

  1. Construct the trace table that shows the state changes for intended function A. Within this trace table, you may assume that condition C is true.

    Compare the final value of each state item with the desired final state in the overall intended function for the containing prime.

  2. Construct the trace table that shows the state changes for intended function B. Within this trace table, you may assume that condition C is false. Again, compare the final value of each state item with the value it should have according to the overall intended function.

Here is a real-world example: a function to find the real roots of a quadratic equation of the form ax2 + bx + c = 0. We perform this calculation in two steps.

  1. First we compute the discriminant, d = b2-4ac.

  2. If d < 0, there are no real roots.

    If d is zero, there is only one root, -b/2a.

    Otherwise there are two real roots, (-b-sqrt(d))/2a and (-b+sqrt(d))/2a.

Here is the code. The overall function is a sequence in which the second part is a three-part alternation, so there are three paths through the code.

def quadRoots(a, b, c):
    '''Find all real roots of the equation a*x**2 + b*x + c = 0.

      [ a, b, and c are numbers ->
          return a list of the real roots of a*x**2 + b*x + c = 0 ]
    '''
    #-- 1
    d = b*b - 4.0*a*c

    #-- 2
    # [ if d < 0 ->
    #     return a new, empty list
    #   else if d==0 ->
    #     return [-b/2a]
    #   else ->
    #     return [(-b+sqrt(d)/(2*a)), (-b-sqrt(d)/(2*a))] ]
    if d < 0:
        return []
    elif d == 0:    
        return [-b/(2.0*a)]
    else:
        rootD = d**0.5
        twoA = 2.0*a
        return [(-b-rootD)/twoA, (-b+rootD)/twoA]

Construction of the trace table starts with prime [1].

State itemAfter [1]
db**2 - 4.0*a*c

Of the three paths through the code, we'll start with the case where d is negative.

State itemAfter [1]After [2]
dsqrt(b)-4*a*csqrt(b)-4*a*c
Result []

When there are no real roots, the desired function result is an empty list, so this trace table checks.

Here's the second case, where the discriminant is zero.

State itemAfter [1]After [2]
d00
Result [-b/(2.0*a)]

Again, we check the final states in the above table against the overall intended function. Because in this case the discrimant is zero, a list containing -b/(2*a) is the correct value.

Here's the trace table for the case where the discriminant d is positive.

State itemAfter [1]After [2]
dsqrt(b)-4*a*csqrt(b)-4*a*c
Result  [ (-b+(sqrt(b)-4*a*c))/(2*a), (-b-(sqrt(b)-4*a*c))/(2*a) ]

This being the general case, the overall intended function requires that the return value be a list containing the two real roots: the last entry in the “Result” column matches this.

The fun begins when you have two or more alternations in a row. Suppose your code is structured like this:

    #-- 1
    # [ if C1 ->
    #     A1
    #   else ->
    #     B1
    ...

    #-- 2
    # [ if C2 ->
    #     A2
    #   else ->
    #     B2 ]
    ...

In the above structure, there are four paths through the code: A1 → A2, B1 → A2, A1 → B2, and B1 → B2.

Similarly, if your prime is broken into a sequence of three alternations, there are eight paths through the code, so you must construct eight trace tables. Again, by keeping your primes small and simple, you reduce the amount of work required to build trace tables.