Trace tables for calls

Why this matters

Real programs are made of small functions, and each function is usually short. A function for tax calls a function for a rate. A function for an order calls the tax function once per item. When the program runs, control jumps from one function to the next, does some work, and jumps back. A bug in this kind of program is rarely on one line. It is in the order of the jumps, or in a value that went into the wrong call.

The trace table from the dry-run lesson works well for one loop that changes a few variables. It becomes hard to read when the program jumps between functions, because each function has its own variables and each call waits for another call to finish. This lesson adds two tools for that case: a call tree, which shows which function calls which, and a trace table for calls, which records each call on its own row.

A call is a request for a function to do its work. The function that asks is the caller. The function that is asked is the callee. When the callee finishes, it sends back a value with RETURN, and the caller continues from the line where it asked. The value sent back is the return value.

The pseudocode conventions lesson introduced FUNCTION and RETURN. This lesson assumes you can read them. It does not repeat how to trace a loop, which is the subject of the tracing and dry-runs lesson.

The idea: a helper that asks another helper

Imagine a bakery order. The customer asks the cashier for a total. The cashier does not know the tax rate, so the cashier asks the manager. The manager looks up the rate and says 18 percent. The cashier then adds the tax and gives the total to the customer.

Three people, three jobs, and each one waits for the next. The cashier cannot finish until the manager answers. The customer cannot finish until the cashier answers. Program functions behave the same way. The total is the cashier's job, the rate is the manager's job, and the caller always waits for the callee.

Here are three functions that do this. The first gives the tax on one price. The second gives the price with tax added. The third adds up the price with tax for every item in an order:

1  FUNCTION tax_for(price)
2      RETURN price * 0.18, rounded to 2 decimal places
3  END FUNCTION
 
4  FUNCTION price_with_tax(price)
5      tax <- tax_for(price)
6      RETURN price + tax, rounded to 2 decimal places
7  END FUNCTION
 
8  FUNCTION order_total(prices)
9      total <- 0
10     FOR EACH p IN prices
11         total <- total + price_with_tax(p)
12     END FOR
13     RETURN total, rounded to 2 decimal places
14 END FUNCTION

FOR EACH p IN prices means "take each item of the list in turn and call it p". It is a counted loop without a counter. The meaning is the same as the FOR loops in the pseudocode conventions lesson, only the list is the thing being counted.

Line 5 is the call that matters for this lesson. price_with_tax does not know how the tax is worked out. It asks tax_for for the answer and waits. Line 11 does the same thing, once per item, with price_with_tax.

Here is the Python for the same three functions. The round calls keep the decimal places tidy:

def tax_for(price):
    return round(price * 0.18, 2)
 
def price_with_tax(price):
    tax = tax_for(price)
    return round(price + tax, 2)
 
def order_total(prices):
    total = 0
    for p in prices:
        total = total + price_with_tax(p)
    return round(total, 2)
 
print(order_total([100, 50]))

Run it with python3 order_total.py:

177.0

The answer is 177.0. The rest of the lesson shows how to get that answer by hand, before running anything, and how to check it.

Building a call tree

A call tree is a picture of who asked whom. Each call is a node. A call that a function makes is written under that function, indented one step further. The top of the tree is the call that started everything, which here is the line print(order_total([100, 50])).

To build the tree, start at the top call and read its body from the first line down. Each time you reach a call to another function, write that call one level deeper. Then move into that function and do the same. When the function has no more calls, you are at a leaf, and you go back up.

For order_total([100, 50]), the steps are:

1. order_total starts. Its body has a loop, and the loop calls price_with_tax with the first item, 100. Write price_with_tax(100) one level down.
2. price_with_tax(100) starts. Its first line calls tax_for(100). Write tax_for(100) one level further down.
3. tax_for(100) has no calls in its body. It is a leaf. It returns 18.0, and the tree stops growing here.
4. Back in price_with_tax(100), the next line uses the return value and returns 118.0. This call has no more calls, so it is finished.
5. Back in order_total, the loop goes on to the second item, 50. Write price_with_tax(50) at the same level as the first one, because it is a second call from the same caller.
6. The same pattern repeats: tax_for(50) is a leaf under price_with_tax(50).

The finished tree looks like this:

order_total(prices=[100, 50])
    price_with_tax(100)
        tax_for(100)
    price_with_tax(50)
        tax_for(50)

Three rules help when reading a tree.

The first rule: a line at a deeper level is called by the line directly above it that is one level shallower. tax_for(100) is called by price_with_tax(100), not by order_total.

The second rule: calls at the same level under the same caller run one after another, in the order they appear in the code. price_with_tax(100) finishes before price_with_tax(50) starts.

The third rule: a call at one level does not finish until everything under it has finished. price_with_tax(100) cannot return 118.0 until tax_for(100) has returned 18.0.

A tree shows structure. It does not show values. To see what each call receives and returns, you need a trace table.

Building a trace table for calls

A trace table for calls has one row for each call, or for each event in a call. An event is either a call starting or a call finishing. Each row records four things: the step number, what happened, the values inside the call at that moment, and what was returned or what the call is still waiting for.

The table uses four columns, which keeps the table easy to fill in by hand.

Read the table in order, from top to bottom. The step numbers are the order of events, not the line numbers of the code. Step 4 is the same call as step 2, continuing after its callee has returned. Each call appears at least twice: once when it starts and once when it finishes. The starting row names the inputs. The finishing row names the answer.

The "Waiting" column carries the key information. A call that is waiting is still open. Reading the rows where a call waits, from the top of the table, shows what is still unfinished at each step. At step 3, three calls are open at the same time: order_total, price_with_tax and tax_for. That set of open calls is called the call stack. It works like a stack of plates. The last call placed on top is the first one to finish.

Check the table against the run. The traced version of the program prints a line at each start and finish, so the printed order can be matched row by row:

def tax_for(price):
    print(f"enter tax_for(price={price})")
    result = round(price * 0.18, 2)
    print(f"return tax_for -> {result}")
    return result
 
def price_with_tax(price):
    print(f"enter price_with_tax(price={price})")
    tax = tax_for(price)
    result = round(price + tax, 2)
    print(f"return price_with_tax -> {result}")
    return result
 
def order_total(prices):
    print(f"enter order_total(prices={prices})")
    total = 0
    for p in prices:
        total = total + price_with_tax(p)
        print(f"  total is now {total}")
    print(f"return order_total -> {round(total, 2)}")
    return round(total, 2)
 
print("main: result =", order_total([100, 50]))

enter order_total(prices=[100, 50])
enter price_with_tax(price=100)
enter tax_for(price=100)
return tax_for -> 18.0
return price_with_tax -> 118.0
  total is now 118.0
enter price_with_tax(price=50)
enter tax_for(price=50)
return tax_for -> 9.0
return price_with_tax -> 59.0
  total is now 177.0
return order_total -> 177.0
main: result = 177.0

The printed lines match the table row for row. The enter lines are the starting rows, the return lines are the finishing rows, and the total is now lines are the rows where the caller adds a result. The traced version is only for checking. In your own work, you fill in the table first and then compare it with the run.

Worked example 2: values are copied into the call

The first example passes a list, but most calls pass single values. A common surprise is what happens to a variable when it is passed into a function. The rule for this course is that the function gets a copy of the value. A change to the copy inside the function does not change the variable outside it.

1  FUNCTION add_bonus(points)
2      points <- points + 10
3      RETURN points
4  END FUNCTION
 
5  score <- 5
6  new_score <- add_bonus(score)
7  PRINT score, new_score

Build the table for lines 5 to 7. The trace table has one variable outside the call (score) and one inside (points), so it needs a column for each. Inside a call, the parameter is a new variable with the name points. It starts with the value that was passed.

At step 3, the value 15 exists only in the points column. The score column still holds 5. The result is then stored in new_score, and score is never changed. The output is:

def add_bonus(points):
    points = points + 10
    print("inside add_bonus, points =", points)
    return points
 
score = 5
new_score = add_bonus(score)
print("score =", score, "new_score =", new_score)

inside add_bonus, points = 15
score = 5 new_score = 15

The inside line shows 15, and the last line shows that score is still 5. Notice that the table had a column for the value after the call finished, and it was marked gone. A parameter exists only while its call is running. Once the call returns, the variable named points no longer exists, and the next call to add_bonus gets a fresh copy.

Worked example 3: a call that calls itself

Some functions call themselves. This is called recursion. The lesson on recursion and backtracking covers it in full. Here we only need the call tree and the trace table, which work the same way as before.

The function below computes the factorial of a number. The factorial of 3 is 3 times 2 times 1, which is 6. The function calls itself with a smaller number each time, until it reaches 0. A call with 0 does not call anything, so it is a leaf. This is the base case, the case that stops the calls.

def fact(n, depth):
    print("  " * depth + f"call fact({n})")
    if n == 0:
        result = 1
    else:
        result = n * fact(n - 1, depth + 1)
    print("  " * depth + f"return {result}")
    return result
 
print(fact(3, 0))

The depth parameter is only there to indent the printed lines. It shows how deep each call sits in the tree, which is the same structure the call tree shows. Run it with python3 fact_trace.py:

call fact(3)
  call fact(2)
    call fact(1)
      call fact(0)
      return 1
    return 1
  return 2
return 6
6

The indentation in the output is the call tree. The calls go down from fact(3) to fact(0). The returns come back up in the reverse order, so fact(1) returns 1 to fact(2), which returns 2 to fact(3), which returns 6.

Here is the same story as a trace table with the calls waiting:

The table has one row for each call and one for each return. Step 4 is the only call with no waiting, because its body has no call to make. The base case is the row where the chain stops.

Common mistakes

Mistake 1: a function prints the answer but does not return it. A function that ends without a RETURN gives back a special value called None in Python. The caller then receives nothing useful. Here is a short program that shows the error:

def double(x):
    print(x * 2)
 
y = double(3)
print("y is", y)
print(y + 1)

6
y is None
Traceback (most recent call last):
  File "no_return.py", line 6, in <module>
    print(y + 1)
          ~~^~~
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The function printed 6 and then stopped. The caller stored None in y, and the line y + 1 failed. In a trace table, the fix is a row that says "returns 6". If the row for the finishing call says "prints 6" instead, you have found the mistake before running the code.

Mistake 2: passing the wrong number of values. Each parameter in a function's header needs a value when the function is called. A call that leaves one out fails at once, before any line of the body runs. Here is an example:

def tax_for(price):
    return round(price * 0.18, 2)
 
print(tax_for())

Traceback (most recent call last):
  File "missing_arg.py", line 4, in <module>
    print(tax_for())
          ~~~~~~~^^
TypeError: tax_for() missing 1 required positional argument: 'price'

When you write a call row in a trace table, write the values you pass in the starting row. If a call row has fewer values than the function's header, the table shows the mistake.

Mistake 3: expecting a change inside a function to reach the caller. The add_bonus example shows that the caller's variable is not changed. A common fix that does not work is to write add_bonus(score) and then expect score to be 15. The fix is to take the return value and store it: score <- add_bonus(score). The trace table shows the difference, because the outside column changes only when the caller stores the result.

Mistake 4: a recursive call with no base case. A recursive function needs a case that stops the calls. Without one, the calls never end, and Python stops the program when the chain gets too deep. Here is fact with the base case removed:

def fact(n):
    return n * fact(n - 1)
 
print(fact(3))

The start and end of the error output are shown below. The middle part repeats the same two lines many times, so it is cut out. The repeat count depends on the Python version:

Traceback (most recent call last):
  File "no_base.py", line 4, in <module>
    print(fact(3))
          ~~~~^^^
  File "no_base.py", line 2, in fact
    return n * fact(n - 1)
...
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

In the call tree, this is a branch that never ends. Before you run a recursive function, draw its tree for a small input, and check that some call reaches the base case and returns.

Mistake 5: writing a return value in the wrong row. A trace table is only useful if each return appears in the row of the call that made it. A common error is to write the answer of tax_for(50) in the row for price_with_tax(100), because the rows are close together. Use the call tree to check which call owns each row before you fill in the value.

Practice

Exercise 1. Draw the call tree for main_value() in this program, and give the value it returns.

def double(x):
    return x * 2
 
def quad(x):
    return double(double(x))
 
def main_value():
    return quad(3)

Show the answer

The call tree is:

main_value()
    quad(3)
        double(3)
        double(6)

quad(3) calls double(3) first, which returns 6. It then calls double(6), which returns 12. So quad(3) returns 12, and main_value() returns 12. Adding a print to double and quad that shows each call and each return value, plus print("quad result:", main_value()) at the end, gives this output:

enter quad(3)
enter double(3)
return double -> 6
enter double(6)
return double -> 12
return quad -> 12
quad result: 12

Exercise 2. Fill in a trace table for total(1, 10) with these functions. Use the four-column layout from this lesson.

def add_fee(x):
    return x + 2
 
def total(a, b):
    return add_fee(a) + add_fee(b)

Show the answer

The result is 15. Running print(total(1, 10)) prints 15.

Exercise 3. The function below is meant to add a fee to a price, but the answer is always None. Find the mistake and fix it.

def add_fee(price):
    total = price + 2
    print(total)
 
result = add_fee(10)
print(result)

Show the answer

The function prints total but never returns it. A function with no RETURN gives back None, so result is None. The fix is to replace the print with a return:

def add_fee(price):
    total = price + 2
    return total
 
result = add_fee(10)
print(result)

This prints 12. In the trace table, the row for the finishing call must say "returns 12", not "prints 12".

Exercise 4. Draw the call tree and fill in a trace table for sum_to(3), using this function:

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

Show the answer

The call tree is:

sum_to(3)
    sum_to(2)
        sum_to(1)
            sum_to(0)

Running print(sum_to(3)) prints 6, which matches the last row of the table.

Exercise 5. A program has three functions. main calls a, a calls b, and b calls c once. Then a calls c a second time. Draw the call tree. Then say how many rows a trace table for this program needs if each call has a starting row and a finishing row.

Show the answer

The call tree is:

main()
    a()
        b()
            c()
        c()

There are five calls in total: main, a, b, and two calls to c, one under b and one under a. Each call has a starting row and a finishing row, so the table needs ten rows.

Summary

• A call tree shows which function calls which, with each callee indented under its caller.
• Calls at the same level under one caller run in the order they appear in the code, and each one finishes before the next starts.
• A trace table for calls has one row when a call starts and one when it finishes, and the "waiting" column shows which calls are still open.
• A parameter gets a copy of the value passed in, so changes inside a function reach the caller only through the return value.
• A recursive call tree must reach a base case, or the calls never end and Python raises a RecursionError.
• Check a hand-made trace table against a run by printing a line at each start and finish, then comparing the printed order row by row.