Does lexical scope have a dynamic aspect?

Question

It seems to be a commonplace that accesses to lexical scope can be worked out at compile time (or by a static analyzer, since my example is in Python) based simply on location in the source code.

Here is a very simple example where one function has two closures with different values for a.

def elvis(a):
  def f(s):
    return a + ' for the ' + s
  return f

f1 = elvis('one')
f2 = elvis('two')
print f1('money'), f2('show')

I have no problem with the idea that when we are reading the code for the function f, when we see a, it is not defined in f, so we pop up to the enclosing function and find one there, and that is what the a in f refers to. Location in the source code is enough to tell me that f gets a value for a from an enclosing scope.

But as described here, when a function is called, its local frame extends its parent environment. So doing environment lookups at runtime is no problem. But what I am unsure of is that a static analyzer could always work out which closure is referred to at compile time, before the code is ever run. In the example above it is obvious that elvis has two closures and it is easy to keep track of them, but other cases will not be so simple. Intuitively I am nervous that an attempt at static analysis could run into a halting problem in general.

So does lexical scoping really have a dynamic aspect to it, where location in the source code tells us that an enclosing scope is involved but not necessarily which closure is referred to? Or is this a solved problem in compilers, and all references within functions to their closures really can be worked out in detail statically?

Or does the answer depend on the programming language -- in which case lexical scoping is not as strong a concept as I thought it was?

[EDIT @comments:

In terms of my example I can restate my question: I read claims like "Lexical resolution can be determined at compile time," yet wondered how references to the value of a in f1 and f2 could be worked out statically/at compile time (in general).

The solution is, lexical scoping does not claim so much. L.S. can tell us, at compile time, that something called a will be defined whenever I am in f (and this clearly can be worked out statically; this is the definition of lexical scope), but determining what value it actually takes (or, which closure is active) is 1) beyond the L.S. concept, 2) done at runtime (not statically) so is dynamic in a sense, yet of course 3) uses a rule different from dynamic scoping.

The takeaway message, to quote @PatrickMaupin, is "Some dynamic work still has to be done." ]

Answer 1

Closures can be implemented in several ways. One of them is to actually capture environments... in other words consider the example

def foo(x):
    y = 1
    z = 2
    def bar(a):
        return (x, y, a)
    return bar

The env-capturing solution goes like:

1. foo is entered and a local frame is built that contains x, y, z, bar names. The name x is bound to the parameter, the name y and z to 1 and 2, the name bar to a closure
2. the closure assigned to bar actually captures the whole parent frame so when it's called it can lookup the name a in its own local frame and can lookup x and y instead in the captured parent frame.

With this approach (that is not the approach used by Python) the variable z would remain alive as long as the closure remains alive, even if it's not referenced by the closure.

Another option, slightly more complex to implement works instead like:

1. at compile time the code is analyzed and the closure assigned to bar is discovered capturing names x and y from the current scope.
2. these two variables are therefore classified as "cells" and they are allocated separately from the local frame
3. the closure stores the address of these variables and each access to them requires a double indirection (a cell is a pointer to where the value is actually stored)

This requires to pay a little extra time when the closure is created because each single captured cell requires to be copied inside the closure object (instead of just copying a pointer to the parent frame) but has the advantage of not capturing the whole frame so for example z will not remain alive after foo returns, only x and y will.

This is what Python does... basically at compile time when a closure (either a named function or a lambda) is found a sub-compilation is performed. During compilation when there is a lookup that resolves to a parent function the variable is marked as being a cell.

One little annoyance is that when a parameter is captured (like in the foo example) also an extra copy operation needs to be done in the prologue to transform the passed value in a cell. This in Python is not visible in the bytecode but is done directly by the call machinery.

Another annoyance is that each access to a captured variable requires a double indirection even in the parent context.

The advantage is that closures only capture really referenced variables and when they don't capture any the generated code is as efficient as a regular function.

To see how this works in Python you can use the dis module to inspect generated bytecode:

>>> dis.dis(foo)
  2           0 LOAD_CONST               1 (1)
              3 STORE_DEREF              1 (y)

  3           6 LOAD_CONST               2 (2)
              9 STORE_FAST               1 (z)

  4          12 LOAD_CLOSURE             0 (x)
             15 LOAD_CLOSURE             1 (y)
             18 BUILD_TUPLE              2
             21 LOAD_CONST               3 (<code object bar at 0x7f6ff6582270, file "<stdin>", line 4>)
             24 LOAD_CONST               4 ('foo.<locals>.bar')
             27 MAKE_CLOSURE             0
             30 STORE_FAST               2 (bar)

  6          33 LOAD_FAST                2 (bar)
             36 RETURN_VALUE
>>>

as you can see the generated code stores 1 into y with a STORE_DEREF (the operation that writes to a cell, thus using a double indirection) and instead stores 2 into z using a STORE_FAST (z was not captured and is just a local in current frame). When the code of foo begins execution x has been already wrapped into a cell by the call machinery.

bar is just a local variable, so STORE_FAST is used to write to it, but to build the closure x and y need to be copied individually (they're put into a tuple before invoking the MAKE_CLOSURE opcode).

The code for the closure itself is visible with:

>>> dis.dis(foo(12))
  5           0 LOAD_DEREF               0 (x)
              3 LOAD_DEREF               1 (y)
              6 LOAD_FAST                0 (a)
              9 BUILD_TUPLE              3
             12 RETURN_VALUE

and you can see that inside the returned closure x and y are accessed with a LOAD_DEREF. No matter how many levels "up" in the nested functions hierarchy a variable is defined, it really is just a double-indirection away because the price is paid while building the closure. Closed-over variables are only slightly slower to access (by a constant factor) in respect to locals... no "scope chain" needs to be traversed at runtime.

Compilers that are even more sophisticated like SBCL (an optimizing compiler for Common Lisp generating native code) also do an "escape analysis" to detect if the closure can actually survive the enclosing function. When this does not happen (i.e. if bar is used only inside foo and not stored or returned) the cells can be allocated in the stack instead of on the heap, lowering the amount of runtime "consing" (allocation of objects on the heap that require garbage collection to be reclaimed).

This distinction is in literature known as "downward/upward funarg"; i.e. if the captured variables are only visible in lower levels (i.e. in the closure or in deeper closures created inside the closure) or also in upper levels (i.e. if my caller will be able to access my captured locals).

To solve the upward funarg problem a garbage collector is needed, and that's why C++ closures do not provide this ability.

Answer 2

In Python, a variable is determined to be local if it is ever assigned to (appears on the LHS of an assignment) and is not explicitly declared global or nonlocal.

So it is possible to work up the lexical scope chain to statically determine which identifier will be found in which function. Some dynamic work still has to be done, however, because you can arbitrarily nest functions, so if function A includes function B which includes function C, then for function C to access a variable from function A, you have to find the right frame for A. (Same thing for a closure.)

Answer 3

It is a solved problem ... either way. Python uses purely lexical scoping, and the closure is determined statically. Other languages permit dynamic scoping -- and the closure is determined during run time, searching its way up the run-time call stack instead of the parse stack.

Is this sufficient explanation?