Section 4.2 Execution Traces
When programming, it is helpful to grasp the meaning of a program part by executing the code “in ones head”. For this purpose, we need to precisely understand the meaning of each statement of the program. This understanding is best practiced by writing execution traces of small programs on paper.
| line | res |
side effect |
| 11 | ||
| 12 | ||
| 13 | ? | call to factorial \(\rightarrow\)
|
| 14 | 6 | print res
|
| 15 | termination |
main| line | n |
res |
side effect |
| 1 | 3 | ||
| 2 | |||
| 3 | ? | ||
| 4 | 1 | ||
| 5 | |||
| 6 | 3 | ||
| 7 | 2 | ||
| 4 | |||
| 5 | |||
| 6 | 6 | ||
| 7 | 1 | ||
| 4 | |||
| 8 | return with the value 6 |
factorialWe represent execution traces in table form. Each line of a table represents the execution of a statement and visualizes the values of the variables before executing the statement. In the first column, we note the line number of the executed statement. For each variable declaration, we add another column with the declaration's identifier as its title. For simplicity, we assume that no declaration is shadowed by another one in a nested scope. A statement can have different effects on the state of the execution: For example, a variable declaration can allocate new containers, the end of a block can deallocate existing containers, and an assignment may read from or write to containers. In a line where the previous statement did not change a variable's content, we leave its column clear. The content of a freshly allocated container is undefined, which we represent with a question mark. Besides changes to contents of a variable's container, a statement can have “side effects”, for example calling a function or printing text on the screen. We note these in a column with the title “side effects”.
Every call of a function requires a new table in the execution trace. In our example, that is the call to
main that starts the program execution and the contained call to factorial. Execution traces can therefore be nested. We mark the connection to the called function's table in the “side effects” column of the calling function. As functions can be called multiple times and can even call themselves (directly or indirectly), there can be multiple tables for the same function in an execution trace. It is important to note that each call of a function has a separate binding to containers for its variables.
