Drawing the stack

Consider the following code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16 def count(word, letter):
    total = 0
    for i in range(len(word)):
       if word[i] == letter:
          total = total + 1

    # STOP DRAWING: show the stack just before the return statement
    return total

def main():
    string = "eyes"
    search = "e"
    answer = count(string, search)
    print("The answer is %d" % (answer))

main()

Follow these steps to draw the stack:

Draw the empty stack and the heap.
When a function is called, create a stack frame for the function and put the frame on top of the stack. Usually, the first function called is main.
1. Allocate parameters, if any, on the stack. The main function typically does not have parameters but many other functions do.
2. Allocate variables used in the function. For very large programs, you may want to skip drawing loop variables because they change frequently and can clutter your diagram. However, you should get in the habit of including them until you are comfortable enough to understand when they can be excluded.
3. Execute the function line-by-line.
  - If another function is called, repeat at step 2.
  - If the function has a return value, we say that the function evaluates to be that value. Be sure to set the variable in the calling function to the returned value, if applicable.
4. When you reach the end of the function, remove it from the stack.
Continue executing the function that is now on top of the stack. If the stack is empty, the program is complete.

Below are the steps for drawing the stack for the code shown above. Line numbers are included so you can see how each line impacts the drawing. Try drawing the stack yourself and see if you get the same drawing!

Step	Line #	What happens to the stack diagram
1	16	Put a frame for `main` on the stack.
2	11	Put the variable `string` in the frame. Draw an arrow from `string` to a string "eyes" on the heap.
3	12	put `search` in the frame. Draw an arrow from `search` to a string “e” on the heap.
Figure 1. Stack Diagram after step 3.
4	13	The `count` function is called, so we make a stack frame for `count` and put it on top of the stack.
5	1	Put parameter `word` in the stack frame for `count`. Draw an arrow from `word` to the string "eyes", since that is the value pointed to by the argument `string`.
6	1	Put parameter `letter` in the stack frame for `count`. Draw an arrow from `letter` to the string "e", since that is the value pointed to by the argument `search`.
Figure 2. Stack Diagram after step 6.
7	2	Put the local variable `total` the stack frame from `count`. Draw arrow to an integer `0` on the heap.
8	3	In each iteration of the for loop, the loop variable `i` will take on the next value of the sequence `range(len(word))`. Since that sequence is 0, 1, 2, 3, draw an arrow from `i` to an integer `0` on the heap.
Figure 3. Stack Diagram after step 6.
9	5	When `i == 0`, `word[i] == letter`, so we increment `total` by 1. We draw a new arrow from `total` to an integer `1` on the heap. We can erase or cross out the old value for `total` on the heap.
10	3	At the next iteration of the for loop, draw a new arrow from `i` to an integer `1` on the heap. We can erase of cross out the old value for `i` on the heap. `word[i] != letter` in this iteration, we won’t execute the body of the if statement.
11	3	At the next iteration of the for loop, draw a new arrow from `i` to an integer `2` on the heap.
Figure 4. Stack Diagram after step 11.
12	5	When `i == 2`, `word[i] == letter`, so we increment `total` by 1. We draw a new arrow from `total` to an integer `2` on the heap. We can erase or cross out the old value for `total` on the heap.
13	3	At the next iteration of the for loop, draw a new arrow from `i` to an integer `3` on the heap. We can erase of cross out the old value for `i` on the heap. `word[i] != letter` in this iteration, we won’t execute the body of the if statement.
14	7	We reach the comment that says `#STOP DRAWING`. The stack diagram as it currently is drawn is what you should have come up with.
Figure 5. Stack Diagram after step 14.
15	8	If we were to continue with the `return` statement, we would remember that the return value is the integer `2` on the heap since that is what the return value, `total`, points to. We would then erase the stack frame for `count`, including all variables in `count` and all arrows coming out of those variables.
16	13	Draw an arrow from `answer` to the returned value on the heap, `2`.
17	14	The string `"The answer is 2"` is printed to the screen.
Figure 6. Stack Diagram after step 17.
18	15	The end of `main` is reached so we remove the stack frame for `main`.
Figure 7. Stack Diagram after step 18.

Drawing the stack: an example