Lab: Models of Computation

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. This is very similar to the tracing that you did in CSC151.

A. Stack Tracking

In this problem we will predict the behavior of two pieces of code, given below.

              // Program 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 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

            

Exercises

For Program 1, 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. For point A, then point B, etc.). 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!)
Repeat for Program 2