29. Stack-Based Execution

CPython executes most bytecode with a stack machine. A stack machine uses an implicit operand stack instead of naming explicit source and destination registers in every instruction.

In CPython, this stack belongs to the current frame. It stores references to Python objects. Bytecode instructions push objects, pop objects, inspect objects, replace objects, and use objects to compute new results.

A simple expression:

x = a + b

is executed conceptually as:

LOAD_FAST a      push a
LOAD_FAST b      push b
BINARY_OP +      pop b and a, push result
STORE_FAST x     pop result into local x

The instruction stream does not say:

add local_a, local_b, local_x

Instead, it says:

load a
load b
add top two stack values
store result

The stack is the temporary workspace of the interpreter.

29.1 Why CPython Uses a Stack Machine

A stack machine gives bytecode a compact representation. Many instructions do not need explicit operand locations because they operate on the top of the stack.

For example:

return (a + b) * c

can be represented as:

LOAD_FAST a
LOAD_FAST b
BINARY_OP +
LOAD_FAST c
BINARY_OP *
RETURN_VALUE

The BINARY_OP instruction does not need to name its input registers. It always takes its operands from the stack.

This keeps bytecode simple:

instructions are small
operands are usually indexes or small integers
temporary values do not need names
compiler stack-depth analysis is straightforward
interpreter execution model is uniform

A register machine would encode more explicit operand locations:

r3 = add r1, r2
r4 = mul r3, r0
return r4

That can reduce the number of instructions in some designs, but it requires a different bytecode format and different compiler strategy. CPython has historically used a stack-oriented model.

29.2 The Frame Value Stack

Each executing frame has storage for temporary values.

Conceptually:

frame
    fast locals
    cell variables
    free variables
    value stack

For:

def f(a, b):
    return a + b

the frame may be understood as:

localsplus
    [0] a
    [1] b
    [2...] value stack

During execution:

LOAD_FAST a
    stack: [a]

LOAD_FAST b
    stack: [a, b]

BINARY_OP +
    stack: [a_plus_b]

RETURN_VALUE
    stack: []
    return a_plus_b

The stack stores PyObject * references. It does not store unboxed C integers, raw doubles, or machine words representing Python values in ordinary bytecode execution.

For a = 2 and b = 3, the stack holds pointers to Python integer objects.

stack slot 0 -> PyLongObject(2)
stack slot 1 -> PyLongObject(3)

29.3 Stack Pointer

The interpreter maintains a stack pointer for the current frame.

Conceptually:

PyObject **stack_pointer;

A push writes a value into the current stack slot and advances the pointer.

*stack_pointer = value;
stack_pointer++;

A pop moves the pointer back and reads the value.

stack_pointer--;
value = *stack_pointer;

The real CPython implementation uses macros, specialized storage, reference ownership conventions, and generated instruction code. But the core operation is still push and pop.

A simple stack trace:

initial:
    sp -> slot 0

push a:
    slot 0 = a
    sp -> slot 1

push b:
    slot 0 = a
    slot 1 = b
    sp -> slot 2

pop:
    sp -> slot 1
    value = slot 1

The stack pointer marks the next free stack slot.

29.4 Stack Effect

Every instruction has a stack effect.

The stack effect says how the instruction changes stack height.

The compiler uses stack effects to compute the maximum stack size needed by a code object.

That value is stored in the code object as co_stacksize.

def f(a, b, c):
    return (a + b) * c

print(f.__code__.co_stacksize)

co_stacksize tells CPython how much temporary stack space this code may require during execution.

29.5 Evaluating a Binary Expression

Consider:

def f(a, b, c):
    return a + b * c

Python precedence requires multiplication before addition.

The conceptual stack execution is:

LOAD_FAST a
LOAD_FAST b
LOAD_FAST c
BINARY_OP *
BINARY_OP +
RETURN_VALUE

Step by step:

The compiler chooses an instruction order that preserves Python expression semantics while using the stack.

29.6 Parentheses and Stack Order

Parentheses change evaluation order.

def f(a, b, c):
    return (a + b) * c

Conceptual bytecode:

LOAD_FAST a
LOAD_FAST b
BINARY_OP +
LOAD_FAST c
BINARY_OP *
RETURN_VALUE

Step by step:

The stack machine naturally represents nested expressions by evaluating subexpressions and leaving their results on the stack.

29.7 Operand Order

For binary operations, operand order matters.

For:

left - right

the interpreter must call subtraction with the correct left and right operands.

The stack before BINARY_OP - is:

[left, right]

The operation pops the right operand first, then the left operand:

right = pop();
left = pop();
result = subtract(left, right);
push(result);

If the order were reversed, subtraction, division, comparisons, and many user-defined operations would be wrong.

The same issue appears in calls, indexing, attribute setting, and unpacking.

29.8 Assignment Consumes Stack Values

Assignment uses stack values produced by expressions.

x = a + b

Conceptual execution:

LOAD_FAST a       stack: [a]
LOAD_FAST b       stack: [a, b]
BINARY_OP +       stack: [result]
STORE_FAST x      stack: []

STORE_FAST consumes the top stack value and stores it into a local slot.

For multiple assignments:

x = y = value

the compiler must duplicate or preserve the value so both names can be assigned.

Conceptually:

LOAD_FAST value
COPY
STORE_FAST x
STORE_FAST y

The exact bytecode varies by Python version, but the stack discipline is the same: assignment targets consume values from the stack.

29.9 Function Calls on the Stack

Function calls use the stack to arrange the callable and arguments.

For:

result = f(a, b)

the stack must contain the callable and arguments in a layout expected by the call instruction.

Conceptually:

LOAD_FAST f       stack: [f]
LOAD_FAST a       stack: [f, a]
LOAD_FAST b       stack: [f, a, b]
CALL 2            stack: [result]
STORE_FAST result stack: []

The call instruction knows the number of positional arguments. It consumes the callable and arguments, invokes the call machinery, and pushes the return value.

Function calls are more complex when they include:

keyword arguments
default values
starred arguments
double-starred mappings
bound methods
callable classes
C functions
Python functions
coroutines

But the evaluation stack still carries the immediate call operands.

29.10 Method Calls

Method calls are optimized because they are common.

For:

obj.method(arg)

the naive model is:

load obj
load attribute method
create bound method object
load arg
call bound method

Creating a bound method object for every call can be expensive.

CPython uses specialized method-call bytecodes and call paths to avoid unnecessary temporary objects when possible.

Conceptually, the optimized path tries to represent:

call underlying function with self and args

instead of:

create bound method object
then call it

The stack layout for method calls may therefore differ from plain function calls in implementation detail. The goal remains the same: arrange callable state and arguments so the call machinery can run efficiently.

29.11 Attribute Access and Stack Values

Attribute access consumes an object and produces an attribute value.

value = obj.name

Conceptually:

LOAD_FAST obj       stack: [obj]
LOAD_ATTR name      stack: [value]
STORE_FAST value    stack: []

LOAD_ATTR pops or reads the object, performs attribute lookup, and pushes the result.

Attribute lookup may involve:

type lookup
descriptor protocol
instance dictionary lookup
slots
properties
custom __getattribute__
custom __getattr__
inline cache checks

From the stack machine’s perspective, the operation is simple:

object in
attribute value out

The implementation behind that operation is large.

29.12 Subscription and Indexing

Subscription also uses the stack.

value = xs[i]

Conceptual execution:

LOAD_FAST xs       stack: [xs]
LOAD_FAST i        stack: [xs, i]
BINARY_SUBSCR      stack: [value]
STORE_FAST value   stack: []

For assignment:

xs[i] = value

the stack must hold the container, index, and assigned value.

Conceptually:

LOAD_FAST value    stack: [value]
LOAD_FAST xs       stack: [value, xs]
LOAD_FAST i        stack: [value, xs, i]
STORE_SUBSCR       stack: []

The exact order is chosen so STORE_SUBSCR can pop operands consistently.

29.13 Building Containers

List, tuple, set, and dict literals use the stack.

xs = [a, b, c]

Conceptually:

LOAD_FAST a
LOAD_FAST b
LOAD_FAST c
BUILD_LIST 3
STORE_FAST xs

Stack evolution:

BUILD_LIST 3 consumes three stack values and pushes one list object.

For a dictionary:

d = {"a": x, "b": y}

the stack may contain key and value objects before a dict-building instruction consumes them.

29.14 Unpacking

Unpacking reverses container construction.

a, b = pair

Conceptually:

LOAD_FAST pair
UNPACK_SEQUENCE 2
STORE_FAST a
STORE_FAST b

The unpack instruction consumes one iterable and pushes its elements.

The compiler must arrange store order so that the right variables receive the correct values.

For:

a, b = [1, 2]

the stack after unpacking may be conceptually:

[1, 2]

Then stores consume values.

Nested unpacking:

a, (b, c) = value

requires multiple unpack operations and careful stack ordering.

29.15 Comparisons

Comparisons consume operands and push a Boolean result or another comparison result.

x < y

Conceptually:

LOAD_FAST x
LOAD_FAST y
COMPARE_OP <

Stack:

before COMPARE_OP: [x, y]
after COMPARE_OP:  [result]

Chained comparisons are more subtle.

a < b < c

Python evaluates b only once and preserves it for the second comparison.

Conceptually:

load a
load b
compare a < b
if false, stop
keep b
load c
compare b < c

The stack machine must duplicate or rotate values to avoid evaluating b twice.

29.16 Boolean Short-Circuiting

Boolean expressions use jumps and the stack.

a and b

If a is false, Python returns a without evaluating b.

Conceptually:

LOAD_FAST a
if false, jump to end and keep a
POP_TOP
LOAD_FAST b
end:

For:

a or b

If a is true, Python returns a without evaluating b.

LOAD_FAST a
if true, jump to end and keep a
POP_TOP
LOAD_FAST b
end:

The stack is used to preserve the selected result.

This explains why Python’s and and or return one of their operands, not necessarily True or False.

result = [] or [1, 2]

returns:

[1, 2]

29.17 Conditional Expressions

A conditional expression:

x if cond else y

uses branches.

Conceptual bytecode:

LOAD_FAST cond
POP_JUMP_IF_FALSE else_branch

LOAD_FAST x
JUMP end

else_branch:
LOAD_FAST y

end:

The stack after the expression contains exactly one value: either x or y.

This is a key compiler invariant. No matter which branch executes, the stack shape at the merge point must be compatible.

29.18 Stack Shape Invariants

At control-flow merge points, the compiler must maintain consistent stack shape.

Example:

if cond:
    x = a
else:
    x = b

Both branches must leave the stack in a compatible state before control flow rejoins.

For expression-level branches:

result = a if cond else b

both branches must leave one value on the stack.

then branch leaves: [a]
else branch leaves: [b]
merge expects:      [one value]

If one branch left two values and another left one, later bytecode would not know what to consume.

Stack correctness is therefore a compiler responsibility as well as an interpreter responsibility.

29.19 Loops and the Stack

Loops use jumps. The stack must be balanced at loop boundaries.

Example:

while i < n:
    i += 1

Conceptual execution:

loop_start:
    LOAD_FAST i
    LOAD_FAST n
    COMPARE_OP <
    POP_JUMP_IF_FALSE loop_end

    LOAD_FAST i
    LOAD_CONST 1
    BINARY_OP +=
    STORE_FAST i

    JUMP loop_start

loop_end:

At loop_start, the stack must be in the expected shape each iteration. Usually it is empty for statement-level loops.

If the loop body left extra stack values, the next iteration would start corrupted.

29.20 For Loops

A for loop is based on the iterator protocol.

for x in xs:
    body(x)

Conceptually:

LOAD_FAST xs
GET_ITER

loop:
    FOR_ITER end
    STORE_FAST x

    LOAD_FAST body
    LOAD_FAST x
    CALL 1
    POP_TOP

    JUMP loop

end:

The iterator remains on the stack across loop iterations.

A simplified stack view:

after GET_ITER:
    [iterator]

FOR_ITER success:
    [iterator, next_value]

STORE_FAST x:
    [iterator]

loop body runs:
    [iterator]

FOR_ITER exhausted:
    []

This is an important case where a value intentionally remains on the stack across a control-flow region.

29.21 Try, Except, and Stack Discipline

Exception handling also depends on stack state.

For:

try:
    risky()
except ValueError:
    recover()

The interpreter must know:

which bytecode range is protected
where the handler starts
what stack depth to restore on exception
what exception values to make available

When an exception occurs, CPython unwinds to a known stack state before entering the handler.

This is necessary because the exception might occur while the stack contains temporary values.

Example:

x = f(g(), h())

If h() raises, the stack may already contain f and the result of g(). Exception handling must clean up these temporaries correctly.

29.22 Finally Blocks

A finally block must run during return, exception propagation, break, or continue.

def f():
    try:
        return 1
    finally:
        cleanup()

The interpreter must preserve the pending return while executing the cleanup.

Conceptually:

prepare return value
enter finally
run cleanup
if cleanup succeeds:
    resume return
if cleanup raises:
    discard pending return and propagate new exception

The stack and frame state must represent this pending control flow correctly.

finally is not just a branch. It is a control-flow interception point.

29.23 With Statements

A with statement compiles into calls to __enter__ and __exit__.

with cm() as value:
    body(value)

Conceptual behavior:

manager = cm()
exit = manager.__exit__
value = manager.__enter__()
try:
    body(value)
finally:
    exit(...)

The stack is used to keep context manager exit machinery available until the block exits.

This lets CPython correctly call __exit__ for normal completion and exception completion.

29.24 Stack Values Are References

Every stack slot holds a reference to a Python object.

That means stack operations interact with reference counting.

When an instruction pushes an object, it must ensure the object remains alive.

When an instruction removes an object from the stack and no longer owns it, it must release the reference if appropriate.

A simplified binary operation:

right = pop();
left = pop();

result = PyNumber_Add(left, right);

Py_DECREF(left);
Py_DECREF(right);

if (result == NULL) {
    goto error;
}

push(result);

The exact ownership rules vary by opcode and helper function. But the invariant is strict:

objects on the stack must remain alive
objects removed from the stack must be released when no longer needed

A stack bug can become a memory leak, use-after-free, crash, or wrong result.

29.25 Borrowed and Owned References

CPython instructions often distinguish borrowed references from owned references.

A borrowed reference means the code can use the object temporarily but does not own a new reference.

An owned reference means the code must eventually release it.

Stack entries generally need to be treated as owned or live references in a way that prevents premature deallocation.

For example, loading a constant from co_consts may read a borrowed reference from the constants tuple, then increment its reference count before placing it on the stack.

Conceptually:

value = code->consts[index];   /* borrowed */
Py_INCREF(value);              /* now owned */
push(value);

Again, modern CPython may use optimized macros, but the lifetime rule remains.

29.26 Stack and Garbage Collection

The value stack is part of the live root set.

If an object is on an active frame’s stack, it is reachable and must not be collected.

Example:

result = f(g(), h())

While evaluating the call, intermediate objects may exist only on the stack. They may not yet be stored in any local variable or container.

Conceptually:

stack:
    f
    result_of_g
    result_of_h

Those objects are live because the frame stack references them.

When the frame unwinds due to return or exception, CPython releases stack-held references.

29.27 Stack and Tracebacks

If an exception occurs, stack cleanup must happen before the traceback is exposed.

Example:

def f():
    return g(h())

If h() raises, the partially evaluated call to g must be abandoned. Temporaries on the stack must be decremented.

The traceback preserves frame and instruction information, but not arbitrary dead temporary stack values.

This is part of why exception handling code in the interpreter is delicate.

29.28 Stack-Based Execution and Specialization

Specialization does not remove the stack machine model.

A generic operation:

BINARY_OP +

may become a specialized operation for integer addition, string concatenation, or another common case.

But the stack contract stays the same:

input stack:  [left, right]
output stack: [result]

This is important. Specialization can change the internal fast path while preserving bytecode-level stack behavior.

For example:

generic BINARY_OP
    pop left and right
    call generic numeric dispatch
    push result

specialized int add
    pop left and right
    verify both are exact ints
    perform fast int path
    push result

If guards fail, the interpreter can fall back to the generic path.

29.29 Inline Caches and Stack Effects

Inline caches store metadata near bytecode instructions, but they do not behave like normal stack values.

For:

LOAD_ATTR name
CACHE
CACHE

the cache entries may occupy bytecode space or interpreter metadata, but they are not values pushed onto the Python evaluation stack.

The stack effect of LOAD_ATTR remains:

input:  [object]
output: [attribute_value]

The cache accelerates the transition from input to output.

This distinction matters when reading disassembly. Some displayed entries may represent interpreter cache machinery rather than user-visible operations.

29.30 Stack Depth Example

Consider:

def f(a, b, c, d):
    return (a + b) * (c + d)

Conceptual bytecode:

LOAD_FAST a
LOAD_FAST b
BINARY_OP +
LOAD_FAST c
LOAD_FAST d
BINARY_OP +
BINARY_OP *
RETURN_VALUE

Stack evolution:

Maximum stack depth is 3 in this conceptual sequence.

The compiler computes this statically.

29.31 Evaluation Order

Python has defined evaluation order. CPython bytecode must preserve it.

For function call arguments:

f(a(), b(), c())

the calls happen left to right.

Conceptually:

load f
call a()
push result of a
call b()
push result of b
call c()
push result of c
call f with three arguments

If b() raises, c() must not run.

The stack machine must preserve this ordering while also cleaning up temporary values on errors.

29.32 Side Effects

Because Python expressions can have side effects, stack execution cannot arbitrarily reorder operations.

Example:

items[i()] = value()

The calls to i() and value() must happen in Python’s specified order for assignment evaluation.

Another example:

f(x, x := 10)

Assignment expressions, function calls, attribute access, and indexing can all affect program state.

The compiler must emit bytecode that respects these side effects. The stack is only an execution mechanism, not a license to rearrange semantics.

29.33 Stack Machine vs Python Call Stack

The evaluation stack and the Python call stack are different.

The evaluation stack is inside one frame:

frame f
    value stack: temporary operands

The Python call stack is a chain of frames:

frame a
    calls frame b
        calls frame c

A function call creates a new frame. That new frame has its own evaluation stack.

Example:

def a():
    return b(1 + 2)

def b(x):
    return x * 10

During a, the expression 1 + 2 uses a’s value stack. When b is called, b gets its own frame and own value stack.

29.34 Stack Machine vs C Stack

The CPython value stack is also different from the native C stack.

A traceback shows the Python call stack, not the full C stack.

The value stack is not normally visible in tracebacks. It is an interpreter-internal execution structure.

29.35 Stack Corruption

The interpreter relies on exact stack discipline.

If an opcode pops too many values, fails to pop enough values, pushes a wrong number of values, or mishandles an error path, the frame becomes invalid.

Possible consequences:

wrong Python result
crash
memory leak
use-after-free
invalid traceback
corrupted exception state
security-sensitive memory bug

This is why CPython bytecode instructions must have well-defined stack effects, and why compiler output must be consistent.

For core development, checking stack effects is not cosmetic. It is a correctness condition.

29.36 Disassembling Stack Behavior

Use dis to study stack execution.

import dis

def f(a, b, c):
    return (a + b) * c

dis.dis(f)

Then manually track the stack:

start: []
LOAD_FAST a       [a]
LOAD_FAST b       [a, b]
BINARY_OP +       [a+b]
LOAD_FAST c       [a+b, c]
BINARY_OP *       [(a+b)*c]
RETURN_VALUE      return

This exercise is useful because it connects source code, bytecode, and frame execution.

29.37 A Small Stack Interpreter

A minimal stack interpreter for arithmetic can show the model.

LOAD_CONST = "LOAD_CONST"
ADD = "ADD"
MUL = "MUL"
RETURN = "RETURN"

def run(code, consts):
    stack = []

    for op, arg in code:
        if op == LOAD_CONST:
            stack.append(consts[arg])

        elif op == ADD:
            right = stack.pop()
            left = stack.pop()
            stack.append(left + right)

        elif op == MUL:
            right = stack.pop()
            left = stack.pop()
            stack.append(left * right)

        elif op == RETURN:
            return stack.pop()

    raise RuntimeError("missing RETURN")

Run:

code = [
    (LOAD_CONST, 0),
    (LOAD_CONST, 1),
    (ADD, None),
    (LOAD_CONST, 2),
    (MUL, None),
    (RETURN, None),
]

consts = [2, 3, 4]

print(run(code, consts))

This computes:

(2 + 3) * 4

The model is much smaller than CPython, but the operand-stack idea is the same.

29.38 Adding Locals to the Toy Interpreter

A slightly richer interpreter can support locals.

LOAD_FAST = "LOAD_FAST"
STORE_FAST = "STORE_FAST"
LOAD_CONST = "LOAD_CONST"
ADD = "ADD"
RETURN = "RETURN"

def run(code, consts, locals_):
    stack = []

    for op, arg in code:
        if op == LOAD_FAST:
            stack.append(locals_[arg])

        elif op == STORE_FAST:
            locals_[arg] = stack.pop()

        elif op == LOAD_CONST:
            stack.append(consts[arg])

        elif op == ADD:
            right = stack.pop()
            left = stack.pop()
            stack.append(left + right)

        elif op == RETURN:
            return stack.pop()

    raise RuntimeError("missing RETURN")

For:

x = a + 1
return x

the bytecode could be:

code = [
    (LOAD_FAST, "a"),
    (LOAD_CONST, 0),
    (ADD, None),
    (STORE_FAST, "x"),
    (LOAD_FAST, "x"),
    (RETURN, None),
]

print(run(code, [1], {"a": 41}))

This demonstrates the same pattern as CPython’s fast locals plus value stack, although CPython uses indexes and object pointers rather than Python dictionaries in the hot path.

29.39 What the Stack Model Explains

The stack model explains many CPython behaviors:

why bytecode instructions are small
why expression evaluation has a natural order
why co_stacksize exists
why local variables can be slot-indexed
why disassembly can be manually simulated
why exception paths must clean temporary values
why function calls have careful stack layouts
why specialization must preserve stack effects
why compiler correctness depends on stack balance

Once you can trace the stack for a function, CPython bytecode becomes much easier to read.

29.40 Common Misunderstandings

29.41 Reading Strategy

To study stack-based execution, use small examples.

Start with:

def f(a, b):
    return a + b

Then:

def g(a, b, c):
    return (a + b) * c

Then:

def h(xs):
    total = 0
    for x in xs:
        total += x
    return total

For each function:

import dis
dis.dis(function_name)

Track:

which instructions push
which instructions pop
where the stack is empty
where values remain across jumps
where calls consume arguments
where returns consume values

This process builds a concrete mental model of the interpreter.

29.42 Chapter Summary

CPython’s bytecode execution is stack-based. Each frame has a value stack used for temporary Python object references. Bytecode instructions push values onto the stack, consume values from the stack, and leave results for later instructions.

The essential pattern is:

load operands
operate on top of stack
push result
store, return, call, branch, or continue

This model explains expression evaluation, local variable access, calls, loops, exception cleanup, container construction, unpacking, specialization, and compiler stack analysis.

The stack machine is simple in shape, but it is central to CPython execution. Understanding it makes bytecode readable and makes the evaluation loop concrete.