How does Python figure out a variable goes in enclosing scope?

I’m curious how Python code generation is able to tell a variable is going to be needed in an inner function and put it in enclosing scope. This is specific to the thinking of compilation and code generation because I am trying to implement similar for a personal project.

Some reference code:

>>> def outer():
...   a = 100
...   def inner():
...     return a + 1
...   b = inner()
...   return b
>>> from dis import dis
>>> dis(outer)
  2           0 LOAD_CONST               1 (100)
              2 STORE_DEREF              0 (a)

  3           4 LOAD_CLOSURE             0 (a)
              6 BUILD_TUPLE              1
              8 LOAD_CONST               2 (<code object inner at 0x000001869788BC90, file "<stdin>", line 3>)
             10 LOAD_CONST               3 ('outer.<locals>.inner')
             12 MAKE_FUNCTION            8 (closure)
             14 STORE_FAST               0 (inner)

  5          16 LOAD_FAST                0 (inner)
             18 CALL_FUNCTION            0
             20 STORE_FAST               1 (b)

  6          22 LOAD_FAST                1 (b)
             24 RETURN_VALUE

Disassembly of <code object inner at 0x000001869788BC90, file "<stdin>", line 3>:
  4           0 LOAD_DEREF               0 (a)
              2 LOAD_CONST               1 (1)
              4 BINARY_ADD
              6 RETURN_VALUE

The interpreter knew to use a STORE_DEREF for the a variable in the outer function. I guess I should also highlight it knows to use LOAD_CLOSURE too. Just to be thorough, this becomes a STORE_FAST if the variable isn’t in enclosing scope:

>>> def outer2():
...   a = 100
...   def inner():
...      return 1
...   b = a + inner()
...   return b
>>> dis(outer2)
  2           0 LOAD_CONST               1 (100)
              2 STORE_FAST               0 (a)

  3           4 LOAD_CONST               2 (<code object inner at 0x0000018697DA2DF0, file "<stdin>", line 3>)
              6 LOAD_CONST               3 ('outer2.<locals>.inner')
              8 MAKE_FUNCTION            0
             10 STORE_FAST               1 (inner)

  5          12 LOAD_FAST                0 (a)
             14 LOAD_FAST                1 (inner)
             16 CALL_FUNCTION            0
             18 BINARY_ADD
             20 STORE_FAST               2 (b)

  6          22 LOAD_FAST                2 (b)
             24 RETURN_VALUE

Disassembly of <code object inner at 0x0000018697DA2DF0, file "<stdin>", line 3>:
  4           0 LOAD_CONST               1 (1)
              2 RETURN_VALUE

All I can really think is that the parser is detecting all the functions underneath the existing on, generating the code for them first, keeping track of the variables involved, and then exploring that from higher levels.

The one strike against this is that code objects aren’t identified first. In outer(), the code object for inner is symbol 2 and not 0. Is it really doing this on the fly and fixing it up afterwards or something?

If you are looking for the exact steps the interpreter takes, you first have to tell us which version of which interpreter (CPython, Jython, IronPython, GraalPython, PyPy, MicroPython, etc).

And then we will answer “Dunno, go read the source code”. wink

The exact steps are implementation details, they are not part of the language. Any two versions of Python might use different steps, so long as the behaviour is the same.

I believe (but could be wrong) that CPython currently parses the source code of a function twice, once to identify which variables are local to the function, and which are not local. So I think the behaviour would be something like this:

  • parse the Abstract Syntax Tree identifying all the names in the function;

  • if the name is declared global (or nonlocal), treat it as global (or nonlocal);

  • otherwise if there is any sort of assignment to that variable inside the function, then treat it as local;

  • otherwise if the name exists in a surrounding function scope, then it is nonlocal;

  • otherwise it is global;

  • parse the function’s AST again and compile the code, using the right STORE or LOAD byte-code depending on whether the variable is global/nonlocal/local.

Whether this is done in two passes, or one, or three, or fifty-three, is an implementation detail; but the rule that assignment to a variable makes it local unless declared global or nonlocal is a language feature.

So in your first example:

def outer():
   a = 100            # a is local to "outer"
   def inner():
       return a + 1   # a exists in surrounding scope, so nonlocal
   b = inner()        # b is local to "outer"
   return b

By the time the code for outer() is compiled on the second pass, the interpreter already knows that names a, b and inner are local to outer, but a is accessed from some inner function and so needs to be in a closure.

I don’t think I care which particular version does, but that is a really weak compromise when I would prefer the simplest, yet most efficient of them. Also, I could really use a unicorn (rainbows).

Regardless, I didn’t think about a two-pass implementation. That’s rough for how I’m managing things right now so I have to churn on that too. If I had just opened the source without considering that, then I think I would have been really puzzled. My plan–assuming no replies–was to see what motivates generating the DEREF opcodes and walk the stack to see what compels the decision to use it. I doubt I would have gotten enough clues into my little mind to figure out it got information from a previous pass.