Python, the stack, and the heap

[eryk sun]

On 12/17/18, Chris Angelico <rosuav at gmail.com> wrote:
>
> Hang on, you're conflating two different things here.

You're probably right that I misinterpreted what the OP meant by
references winding up "on the stack". It's more common for a Python
developer to think of the call stack instead of the implementation
details of local variables and stacks inside frame objects.

>>>> dis.dis(triangle)
>   1           0 LOAD_FAST                0 (x)
>               2 LOAD_CONST               1 (2)
>               4 COMPARE_OP               0 (<)
>               6 POP_JUMP_IF_FALSE       12
>               8 LOAD_FAST                0 (x)
>              10 RETURN_VALUE
>         >>   12 LOAD_FAST                0 (x)
>              14 LOAD_GLOBAL              0 (triangle)
>              16 LOAD_FAST                0 (x)
>              18 LOAD_CONST               2 (1)
>              20 BINARY_SUBTRACT
>              22 CALL_FUNCTION            1
>              24 BINARY_ADD
>              26 RETURN_VALUE
>
> The recursive branch (from line 12 onwards) fetches up x, then calls
> itself recursively, and then adds the return value to what was already
> on the stack. The operand stack quite happily carries from one call to
> another. (CPython has some protections, I believe, to ensure that the
> operand stack doesn't get destroyed by a mismatched load/store or
> something, but conceptually, it's just one stack for all functions.)

CALL_FUNCTION (implemented via call_function in Python/ceval.c)
allocates and evaluates a new frame object when calling a pure Python
function. Inside each CPython frame object is the f_localsplus memory
block, which is divided between local variables and the evaluation
stack. The combination of linked frame objects and their internal
f_localsplus memory blocks is analogous to frames on the native call
stack.

In CPython, the frame-object stack and the native stack are coupled
and grow together, which is why the default recursion limit is
relatively conservative (1000). (Stackless Python severs this
connection.)

Here's what evaluating triangle(2) looks like in terms of the native
call stack in Windows.

Function definition:

    def triangle(x):
        if x < 2:
            return x
        return x + triangle(x - 1)

Statement executed in the REPL:

    >>> triangle(2)

Native call stack (listed from most recent call, in reverse):

    0:000> kc
    Call Site

triangle(1) evaluation:
    python37_d!_PyEval_EvalFrameDefault
    python37_d!function_code_fastcall
    python37_d!_PyFunction_FastCallKeywords
    python37_d!call_function

triangle(2) evaluation:
    python37_d!_PyEval_EvalFrameDefault
    python37_d!function_code_fastcall
    python37_d!_PyFunction_FastCallKeywords
    python37_d!call_function

REPL evaluation:
    python37_d!_PyEval_EvalFrameDefault
    python37_d!_PyEval_EvalCodeWithName
    python37_d!PyEval_EvalCodeEx
    python37_d!PyEval_EvalCode
    python37_d!run_mod
    python37_d!PyRun_InteractiveOneObjectEx
    python37_d!PyRun_InteractiveLoopFlags

Python interpreter startup:
    python37_d!PyRun_AnyFileExFlags
    python37_d!pymain_run_file
    python37_d!pymain_run_filename
    python37_d!pymain_run_python
    python37_d!pymain_main
    python37_d!Py_Main

C runtime startup:
    python_d!wmain
    python_d!invoke_main
    python_d!__scrt_common_main_seh
    python_d!__scrt_common_main
    python_d!wmainCRTStartup

Windows thread startup:
    KERNEL32!BaseThreadInitThunk

NT thread startup:
    ntdll!RtlUserThreadStart