Stack Tracking

The goal of this lab is to practice predicting the behavior of programs using the stack model of computation.

Note: "stack tracking" can also be called "stack tracing" or simply "tracing" a program.

Exercises

For each of the following programs, give the state of the stack and what has been printed to the console at each of the commented program points (e.g., write five stack diagrams for program 1 below). Make sure to reproduce your diagrams exactly for each program state!

Note that it's common to abbreviate the program counter as simply PC. You may set the program counter to be one line after the comment.

(Hint: the labels are in order of where execution flows through the program!)

Program Exercise 1

void                //  1
f1 (void) {         //  2
    printf ("0");   //  3
    // Point (B, D) //  4
}                   //  5
                    //  6
void                //  7
f2 (void) {         //  8
    printf ("1");   //  9
    // Point (C)    // 10
    f1();           // 11
    printf ("2");   // 12
}                   // 13
                    // 14
int                 // 15
main (void) {       // 16
    // Point (A)    // 17
    printf ("3");   // 18
    f1();           // 19
    f2();           // 20
    // Point (E)    // 21
}                   // 22

Program Exercise 2


void                    //  1
f1 (void) {             //  2
    printf ("0");       //  3
    // Points (A, C, E) //  4
}                       //  5
                        //  6
void                    //  7
f2 (void) {             //  8
    // Points (B, D)    //  9
    printf ("1");       // 10
    f1();               // 11
}                       // 12
                        // 13
void                    // 14
f3 (void) {             // 15
    f2();               // 16
    printf ("2");       // 17
}                       // 18
                        // 19
int                     // 20
main (void) {           // 21
    printf ("3");       // 22
    f1();               // 23
    f2();               // 24
    f3();               // 25
    // Point (F)        // 26
}                       // 27

For those with extra time

The previous lab demonstrated this particularly atrocious program segment:

int a = 2;
int b = 4;

a /= (b++) % (++a);

printf("%d\n",a);
  1. Fully parenthesize the assignment statement.
  2. Combine the stack and substitution models by tracking the value of all the local variables as each subexpression is evaluated. Clearly identify which subexpression is evaluated at each step.
  3. If you have not already, verify your final answer is correct by compiling and running this program segment.
This is a derivative work of Mental Model Exercises, by Titus Klinge and Peter-Michael Osera, used under a Creative Commons Attribution-NonCommercial 4.0 license.