CPSC 035: Stack Diagrams

A stack diagram is a way of visually representing the contents of memory at a moment in time during the execution of a program. We draw stack diagrams in a consistent way for the same reason that spoken languages have rules of syntax and grammar: to ensure that others can read what we have written. This page gives a description of how we draw stack diagrams in CS35.

Stack Frames

We begin our discussion with a simple example of a stack diagram. Below, we have a simple C++ program which statically allocates three variables (two ints and an int array) and then returns. To the right of that code, we have a corresponding stack diagram. Note that, because a stack diagram represents a moment in time, we must decide what moment our diagram is intended to represent. In this tutorial, we will do so using comments such as // DIAGRAM HERE in this example code.

  int main() {
    int x = 5;
    int y;
    int a[4];
    // DIAGRAM HERE
    return 0;
  }

At the time we reach the comment, the main function is running; we therefore have a stack frame (the rectangle) labeled main. Three variables have been statically allocated in main, which we represent by drawing the variables and their corresponding spaces in the main stack frame.

The first variable in the stack frame, x, has been initialized to 5 in the code. For this reason, we write a 5 in the box corresponding to it. The y variable has not been initialized; we represent this by leaving its space blank. Likewise, while we have statically allocated four ints by declaring the array a, we have not yet put anything into the array and so all of its positions are uninitialized.

Function Calls

When we call a function, that function executes completely and then our program resumes from where we made the call. Any stack variables that the caller had at the time of the call are preserved; they still have their old values when the call is finished. Thus, if our stack diagram represents a moment in time during a call, it must show that other functions are waiting for us to return to them (and show their variables’ values). We represent this by creating a stack of frames (rectangles), each containing the variables for that particular call.

  int pow(int base, int exp) {
    int acc = 1;
    for (int i=0;i<exp;i++) {
      acc = acc * base;
    }
    // DIAGRAM HERE
    return acc;
  }

  int main() {
    int b = 2;
    int e = 5;
    int answer = pow(b, e);
    return 0;
  }

In the above example, the pow function calculates a number raised to a positive integer power. The moment in time we are capturing is within the pow function, so we draw a diagram in which the pow stack frame appears above the main stack frame: when pow finishes, main will resume running. The parameters and local variables for pow appear within its frame, separated from the local variables of main.

Of note is the fact that the answer variable in main has not yet been initialized! A variable assignment like int answer = pow(b,e); must first compute the result of pow(b,e) and then assign that result to answer. Since we’re still in the middle of calling pow, the value of answer has not yet been decided.

Recursion

When calling a recursive function, each recursive call has its own variables with their own values. We represent this by showing a different stack frame for each recursive call. In other words, recursive calls are not special in stack diagrams; we draw them just as we would any other call.

  #include <iostream>
  using namespace std;

  int summation(int n) {
    if (n<2) {
      // DIAGRAM HERE
      return n;
    } else {
      return summation(n-1) + n;
    }
  }

  int main() {
    cout << summation(3) << endl;
    return 0;
  }

In the above example, the summation routine adds all of the numbers between 1 and n and returns the result. It does this recursively: summation(3) calls summation(2), for instance. Note how each recursive call has a distinct stack frame.

Of some interest in this diagram is that the main function has no variables of its own. Even though the frame is empty, we still draw it.

Dynamic Allocation

We use the term stack diagram because the diagram is focused on showing memory from the point of view of the stack. A more accurate term might be memory diagram, however, as we use stack diagrams to show dynamically allocated memory as well. In C++, dynamic allocation is accomplished using new (while deallocation occurs with delete and delete[]). We draw dynamically allocated memory to the right of the stack diagram and show pointers to that memory using arrows.

  #include <iostream>
  using namespace std;

  int main() {
    int* array1 = new int[5];
    int* array2 = new int[3];
    int* array3 = array1;
    array1[0] = 2;
    // DIAGRAM HERE
    delete[] array1;
    delete[] array2;
    return 0;
  }

Objects

In object-oriented programs, objects are combinations of data and routines which act on that data. In a stack diagram, we are only concerned with the data contained in the object. We represent an object in a fashion similar to a stack diagram: a series of variables (the object’s fields) in a container. We put the name of the object’s class on the right of its box to differentiate between objects and stack frames.

  #include <iostream>
  using namespace std;

  class Point {
  public:
    int x;
    int y;
  };

  int main() {
    Point* p = new Point();
    p->x = 4;
    // DIAGRAM HERE
    delete p;
    return 0;
  }

Dynamically allocated objects (such as the Point object above) are drawn in the heap memory to the right of the stack frames. Pointers to those objects are represented the same as for arrays: using an arrow. Here, the Point object’s x field has been initialized but its y field has not.