Stack vs Heap + Intro to Environment Diagrams

What is "The Stack"?

The stack is the program's "working space." It consists of a bunch of 'frames' that will correspond with each function call.

The stack is specifically ordered and follows the same structure as your function calls!

^ each plate represents a function call!

Each frame added to the stack corresponds with a function call, and will contain: the name of the function definition, a list of the variable names/boxes holding their bound values (this includes parameters and their corresponding arguments!), and an 'rv' return value box.

When a function is finished executing, that frame is "popped" (erased) off the stack.

Variables in the stack will never point to other things on the stack!

What is "The Heap"?

The heap is essentially dynamic memory. Variables (that are not primitive values) in the stack point to functions, arrays, and objects in the heap! As elements in arrays and properties of objects change, the heap also changes!

The heap is unordered and contains structures that must be referenced by the stack! If there is no reference to something on the heap from the stack, eventually that object will be "garbage collected" (AKA...goodbye forever)

This is a broad conceptual overview of what the stack and the heap are for! Reference the other pages under "The State of the Program" for specifics on how to create and manage environment diagrams.

The Tracing Process

When tracing through an example with an environment diagram, you will follow a general process:

Establish a frame for main
Establish local variables which are those declared inside a function's body in the frame
When encountering functions:
1. Establish a new frame for the function
2. Establish parameters as local variables assigned the value of the arguments
3. Keep track of the return value, plug this value in to where we 'bookmarked' (where the function was called originally)

Environment Diagram Example

import { print } from "introcs";

export let main = async () => { //1 - main frame added to stack
        let a = 2; // 2 - variable 'a' is added to the main frame and initialized to 2
        let b = double(a); // 3.1 - establish a new 'double' frame on the stack...BOOKMARK
        print("a: " + a);
        print("b: " + b);
};

let double = (x: number): number => { //3.2 - add you parameters and corresponding arguments to the new stack
        let a = x * 2;
        return a;
};

main();

1. Establish a frame for main

When a function call is encountered, a new frame is added to the stack and it is labeled with the function's name. In this case, we will add a frame to our stack and label it as main.

2. Establish Local Variables

Within main, we can see that there are a few local variables that are declared. When a variable is declared and initialized, first evaluate the value on the right. In this case, it is the number literal 2. Then we establish it in the current frame by writing the variable name (in this case a) and initialize it by placing its value (2) in a box next to the name.

The next variable we encounter is b. When evaluating the value on the right, we see that it is a function call, so let's evaluate what the function call will return. Let's go through the steps when encountering a function...

3.1 Function Call --> Establish a Frame

Add a new frame to the stack under the main frame. Give the frame the function name, which in this case is double. Then, we need to establish value placeholders for each of the function's parameters. In this case, we establish a placeholder for x.

3.2 Function Call --> Evaluate and Assign Arguments

What is the name a bound to in the main frame? We look back in our diagram and see that it's value is 2. Since it is an argument, we copy its value to the corresponding parameter which is x in our double frame.

At this point, we will drop a bookmark where the function call occurred so we know to return back to this place. Then, we will jump into the first line of the function.

3.3 Within the Function Call...

First Line: A variable is declared and initialized. We will evaluate the value on the right which in this case is an arithmetic expression. To find the value of x, we look to the current frame in the stack for its value. In this case, x has a value of 2. The expression 2 * 2 then is 4. Now, we add an entry to for the newly declared value a to the current frame for double. There are 2 separate values for 'a' in our program and that is ok. 'a' in double is independent of and not associated with 'a' in main!

Second Line: A return statement. First evaluate the value it is returning which in this case is a. Look to the current frame in the stack for its value. In this case, a's value in the double frame is 4.

3.4 Function Call --> Keep Track of the return value

Now that we know the value of the return value, enter it in a box named rv in the current frame.

This is then returned to where the function call originated and its value will be substituted for the function call.

So back in main, the line where we left the bookmark will be evaluated as let b = 4. Therefore we can add an entry for the variable b in the current frame: main.

Printing and Name Resolution

Next, we need to print the values of a and b. To determine the value of these variables, we look to the current frame in the stack for its value. In this example, the value of a is 2 and the value of b is 4. Therefore our printed output is:

a: 2
b: 4

We have now reached the end of the main function. The main function has no return statement, so in the rv box we will draw a circle with a line through it, as we expect its return value is nothing. Our program is now finished running and we are done tracing!

Comp 110 Stack vs Heap + Intro to Environment Diagrams