Memory Diagrams: Tracing Line-by-Line Program Execution

Purpose and use of memory diagrams

The purpose, as mentioned, is to track how our program is executed line by line.
They help because the evaluation of a program often depends on many interrelated values; you have many different parameters to keep track.
They provide a clear, visual narrative of control flow and data flow as each statement is executed.
They support debugging by making state changes explicit and traceable.
They help reveal how changes in one part of the program affect other parts through dependencies and interactions.

What memory diagrams capture

Program state at a given moment includes values of variables, parameters, temporaries, and possibly memory allocations.
Distinguish memory regions and their roles: stack vs heap, plus registers and the program counter (if shown).
Stack frames for function calls: each call creates its own frame containing local variables and parameters; the return address is stored in the frame.
Data relationships: how variables reference each other, including pointers and references; aliasing can cause multiple names to refer to the same memory.
Evolution across statements: memory diagrams are updated as assignments and expressions are evaluated line by line.
Scope and lifetime: local variables exist while their frame is on the call stack; global variables persist for the program’s lifetime.
Recursion: multiple nested calls create a chain of frames; diagrams show the call stack growing and shrinking.
Heap-based objects: show heap allocations, object fields, and references from stack/local variables to heap objects.
Notation and visualization: often boxes represent values or variables, with arrows indicating pointers/references; addresses may be shown or omitted.
Types and values: include type information in each box when helpful (e.g., int, float, or object type).
Memory state representation: a mapping view is common, e.g., a value map from identifiers to contents.
If pointers are involved, show how dereferencing changes the observed values.
Example notations:
- Assignments can be shown as x
- x \leftarrow v indicates an update of x to v.
For formal representation, one might use a state mapping such as $St = { x \mapsto vx^{(t)}, y \mapsto v_y^{(t)}, \dots }$ to denote the program state after step t.
Update rule intuition: after line t that changes x to a new value, $vx^{(t)} = \text{expr}t(\text{previous state})$ .

Reading a memory diagram: step-by-step

Start at program entry with the initial frame (e.g., main) and initial values (or uninitialized locals).
For each executed line, update the diagram to reflect new values and any new frames.
Pay attention to evaluation order and side effects; some languages evaluate operands left-to-right or in a specified order, affecting intermediate states.
When a function is called, push a new frame on the stack with its own parameters and locals; when it returns, pop that frame and propagate the return value to the caller.
Distinguish by-value vs by-reference: by-value passes copies; by-reference allows the callee to modify the caller’s variables.
Track memory management events: allocations on the heap, deallocations, and potential destructors or finalizers.
Use the diagram to reason about correctness, such as whether later steps depend on a value that should have been updated earlier.

Example: tracing a tiny snippet

Consider the following simple sequence:
- Line 1: int a = 5;
- Line 2: int b = a + 2;
- Line 3: int c = b * 3;
- Line 4: return c;
Memory state after each line (in a single main frame):
- After line 1 (a = 5):
- main frame: { a = 5, b = ?, c = ? }
- After line 2 (b = a + 2):
- main frame: { a = 5, b = 7, c = ? }
- After line 3 (c = b * 3):
- main frame: { a = 5, b = 7, c = 21 }
- After line 4 (return c):
- main frame: { a = 5, b = 7, c = 21 }; return value = 21
In a more complex example with a function call, you would show a top-level frame for the caller, plus a new frame for the callee, with its own parameters and locals; after the call, the caller’s frame resumes with any return value.

Key concepts and terminology

State: the complete mapping of identifiers to values at a given moment, often denoted as $St = { x \mapsto vx^{(t)}, y \mapsto v_y^{(t)}, \dots }$ .
Stack: memory region that holds function call frames (local variables, parameters, return addresses).
Heap: memory region for dynamically allocated objects and data with lifetimes governed by allocation/deallocation.
Frame (call frame): a single function invocation’s local context on the call stack.
Call stack: the chain of active frames representing the path of nested function calls.
Local variables vs parameters: locals live in the callee’s frame; parameters are the inputs to a function within its frame.
Global variables: variables with program-wide lifetime, typically not on the local call stack.
Temporaries: intermediate results created during expression evaluation, often held in the current frame.
Pointers/references: values that refer to memory locations elsewhere (often on the heap or in another frame).
Aliasing: two or more names refer to the same memory location.
By-value vs by-reference (or by-pointer): semantics of how arguments are passed in a function call.
Allocation/deallocation events: when memory is requested (alloc) and released (free/delete/garbage collection).
Types and structure: including primitive vs composite types, object fields, and how they appear in memory.
Notation conventions: boxes for values, arrows for references, addresses as needed; use \leftarrow for assignments and \mapsto for mappings.

Implications for practice

Memory diagrams aid debugging by making hidden state changes explicit and traceable.
They support reasoning about scope, lifetime, and data dependencies across statements and function calls.
They help students connect code to memory behavior, deepening understanding of how programs compute results.
They provide a foundation for reasoning about performance aspects related to memory, such as stack depth and heap usage.
They highlight potential pitfalls: unexpected mutations via references, stale values, or incorrect assumptions about evaluation order.
In languages with complex memory management (garbage collection, manual memory management), diagrams can illustrate when and how memory is allocated and freed.

Notation and conventions

Memory diagrams commonly depict: frames (stack), heap objects, and value boxes.
Use arrows to show references/pointers from stack locals to heap-allocated objects, or between objects.
Label each box with the variable name and its current value (and optionally its type).
For formal clarity, you can express state updates with mappings, e.g., after a line, $St = S{t-1} \cup { x \mapsto v_x^{(t)} }$ where only changed entries are updated.
Example updates for an assignment: if line t assigns x := 5, then $vx^{(t)} = 5,$ while all other values remain as in $S{t-1}$ .
When documenting, it can be helpful to include both the textual description of the operation and the corresponding diagrammatic update.
If desired, annotate diagrams with simple pseudo-code to connect the visual state to the actual source lines.

Purpose and use of memory diagrams

The purpose, as mentioned, is to track how our Python program is executed line by line.
They help because the evaluation of a program often depends on many interrelated values; you have many different variables and parameters to keep track of.
They provide a clear, visual narrative of control flow and data flow as each statement in your Python code is executed.
They support debugging Python programs by making state changes explicit and traceable, helping you understand why your variables have unexpected values.
They help reveal how changes to one part of the program (especially with mutable objects) affect other parts through dependencies and interactions.

What memory diagrams capture

Program state at a given moment: This includes the current values of all active variables, function parameters, and intermediate results in your Python program. It also tracks the objects created in memory.
Distinguish memory regions and their roles:
- Stack: This is where Python manages function call frames. Each time a function is called, a new frame is added to the stack, containing local variables and parameters specific to that function call.
- Heap: This is where Python objects (like lists, dictionaries, custom class instances, strings, numbers, etc.) are stored. Python uses automatic garbage collection to manage memory in the heap, so you don't typically alloc or free memory yourself.
Stack frames for function calls: In Python, each function call creates its own isolated frame (sometimes called an activation record) on the call stack. This frame contains local variables and parameters that are unique to that specific function call. When the function finishes, its frame is removed from the stack.
Data relationships: Diagrams show how Python variables refer to objects in memory. If multiple variables refer to the same mutable object, this is called aliasing, and modifying the object through one variable will be reflected when accessing it through another.
Evolution across statements: Memory diagrams are dynamic; they are updated line by line to reflect new variable assignments, object creations, or modifications as your Python code executes.
Scope and lifetime: Diagrams illustrate when a Python variable is accessible (its scope, following rules like LEGB - Local, Enclosing, Global, Built-in) and how long it exists in memory. Local variables exist only while their function's frame is on the call stack, while global variables persist for the program's lifetime.
Recursion: For recursive functions, diagrams show the call stack growing with multiple nested frames, one for each recursive call. As the base case is reached and functions return, these frames are popped off the stack.
Heap-based objects: Python objects, like lists or dictionaries, are typically shown on the heap. Diagrams use arrows to represent variables on the stack (or other heap objects) referring to these heap-allocated objects and their contents.
Notation and visualization: Commonly, boxes represent variables or objects, with arrows indicating references. Values are written inside or next to variable boxes. For objects, their contents (e.g., list elements, dictionary key-value pairs) are shown within their box.
Types and values: Diagrams include the value stored in a variable and often implicitly the type (e.g., integer 5, string 'hello', list [1, 2]).
Memory state representation: When tracing, you might represent the state by showing current frames and their local variables. For instance, a frame might contain { 'a': 5, 'b': 7 }.
If variables are involved, show how accessing the object they refer to allows you to work with its components.
Example notation: Assignments are typically shown as x = 5 or x <-- 5 (meaning x now refers to the object 5).

Reading a memory diagram: step-by-step

Start at program entry: Begin with the initial execution for your Python script, which implicitly has a global frame. Initialize any global variables if present.
For each executed line, update the diagram: Systematically update the diagram after every Python statement. This includes:
- Changing the value a variable refers to due to an assignment.
- Pushing a new frame onto the stack when a function is called.
- Popping a frame off the stack when a function returns.
- Creating new objects on the heap.
Pay attention to evaluation order and side effects: In Python, expressions are evaluated in a specific order. Be aware of operations that might modify objects in place (side effects), especially with mutable types like lists or dictionaries.
When a function is called: A new frame is created and pushed onto the call stack. This frame gets its own parameters (which are initialized with the values passed by the caller) and local variables. Execution then transfers to this new function. When the function returns, its frame is popped, and the return value is passed back to the caller.
Distinguish how arguments are passed: In Python, arguments are passed by object reference. This means:
- If you pass an immutable object (like a number, string, or tuple), the function receives a reference to that object. The function cannot change the original object itself, though it can reassign its local parameter variable to refer to a different object.
- If you pass a mutable object (like a list, dictionary, or custom class instance), the function receives a reference to the same object that the caller has. The function can modify this object directly, and those changes will be visible to the caller.
Track memory management events: Your focus in Python will be on object creation and when objects might become candidates for garbage collection (i.e., when no variables refer to them anymore). You do not manually alloc or dealloc memory.
Use the diagram to reason about correctness: Diagrams are excellent for debugging. They help you trace data dependencies (e.g., does a function properly receive and use the correct list?) and identify unexpected mutations or incorrect assumptions about how variables are updated.

Example: tracing a tiny snippet

Consider the following simple Python sequence:

# Line 1: `a = 5`
# Line 2: `b = a + 2`
# Line 3: `c = b * 3`
# Line 4: `result = c`

Memory state after each line (in a single global/main frame):

After Line 1 (a = 5):
- Main/Global frame: { 'a': 5, 'b': ?, 'c': ?, 'result': ? } (where ? indicates not yet defined/initialized)
After Line 2 (b = a + 2):
- Main/Global frame: { 'a': 5, 'b': 7, 'c': ?, 'result': ? }
After Line 3 (c = b * 3):
- Main/Global frame: { 'a': 5, 'b': 7, 'c': 21, 'result': ? }
After Line 4 (result = c):
- Main/Global frame: { 'a': 5, 'b': 7, 'c': 21, 'result': 21 }

In a more complex example with a function call, you would show a global frame (or caller's frame), plus a new frame for the called function with its own parameters and local variables. After the function returns, the caller's frame resumes, potentially using the return value.

Key concepts and terminology

State: The complete snapshot of identifier-to-value mappings and the objects in memory at any point in your Python program's execution.
Stack: The memory area used by Python to manage function calls. It holds frames for actively running functions.
Heap: The flexible memory region where Python objects (like lists, dictionaries, strings, class instances) are stored. Memory management here is automatic via Python's garbage collector.
Frame (Call Frame / Activation Record): A specific context on the call stack for a single function invocation. It holds the function's parameters and local variables.
Call Stack: The ordered list of active function frames, representing the sequence of currently nested function calls. This dictates the current execution point.
Local variables vs parameters: Parameters are the values (or references to objects) passed into a function when it's called. Local variables are defined inside a function and exist only within that function's frame.
Global variables: Variables defined outside any function in a Python script. They are accessible throughout the program and persist for its entire execution.
Temporaries: Intermediate results created during the evaluation of complex Python expressions that are used briefly and then discarded.
References: In Python, variables don't strictly