# How shall I resolve a nonlocal name in a language with deep binding?

Figure 3.14 Deep binding in Python. At right is a conceptual view of the run-time stack. Referencing environments captured in closures are shown as dashed boxes and arrows. When B is called via formal parameter P, two instances of I exist. Because the closure for P was created in the initial invocation of A, B’s static link (solid arrow) points to the frame of that earlier invocation. B uses that invocation’s instance of I in its print statement, and the output is a 1.

The catch is that a running program may have more than one instance of an object that is declared within a recursive subroutine. A closure in a language with static scoping captures the current instance of every object, at the time the closure is created. When the closure’s subroutine is called, it will ﬁnd these captured instances, even if newer instances have subsequently been created by recursive calls.

So basically, the quote tries to explain that the following program (which is the same as the one in the screenshot) prints out 1:

def A(I, P):
def B():
print(I)
# body of A:
if I > 1:
P()
else:
A(2, B)

def C():
pass # do nothing

A(1, C) # main program


I don't quite understand the reason being "because the closure for P was created in the initial invocation of A, B’s static link (solid arrow) points to the frame of that earlier invocation", and "When the closure’s subroutine is called, it will ﬁnd these captured instances". So I modify the example, and then the new example prints out 2 instead of 1:

def A(I, P):
def B():
print(I)
if I > 2:
P()
elif I > 1:
A(3, B)
else:
A(2, B)

def C():
pass

A(1, C)


Another modified example prints 1:

def A(I, P):
def B():
print(I)
if I > 2:
P()
elif I > 1:
A(3, P)
else:
A(2, B)

def C():
pass

A(1, C)


So how can I know which closure matters when resolving a nonlocal name in a language with deep binding?

Generally, is a closure created whenever a function is passed as an argument to another function?

Thanks.

• Questions about particular programming languages are off-topic here, though perhaps this question is more about the concept of closures than about its particular implementation in python. – Yuval Filmus Aug 25 '17 at 12:58
• Thanks, it is about the concepts of deep binding and closures. I updated. – Tim Aug 25 '17 at 13:03
• The closure is created at the time the function is defined. – Andrej Bauer Aug 25 '17 at 13:11
• I personally don't recommend trying to (initially) understand this concept in terms of "stack frames" and "static links". For a pure functional program, like this particular program is (ignoring the print), you can simply imagine substituting in the parameters. That won't work in general in Python. However, if you didn't have higher-order functions, what might you do? You may use the Strategy Pattern. Figuring out what that would look like in this case will be more enlightening and won't involve implementation details. – Derek Elkins Aug 25 '17 at 21:21

Roughly put, every time you define a function, as in def B(): ... you define B to be a closure. This is a pair contains a representation of the body of the function (possibly compiled to a simpler language), and a reference to the current environment (possibly restricted to what B actually needs). The current environment is the one we are in when we run def B(): ....

In the example you provide, B is defined inside A, so its associated closure gets a reference the the current call frame of A. This is why, if you pass P=B in the recursive call, after the call running P prints the value of I in the previous call frame.

Note that, in many languages, closures can be returned, which makes the current call frame to be not freed after the return. For example,

def A(I):
def B():
print(I)
def C():
nonlocal I  # Python for "use A's I, don't create a fresh local I"
I += 1
return (B,C)

# main
(b,c) = A(10)
b() # 10
c()
b() # 11
c()
b() # 12


Above, we can see that, even if A returned, its local variable I is still live! It can be accessed through the two returned closures, which contain a reference to the A's call frame, even if A is now finished.

• Thanks. (1) i am still not clear why the three examples (one from the book and two I gave) print different things. Could you explain each of them individually? (2) "The current environment is the one we are in when we run def B(): ...." . Since A is called recursively, there are more than one stack frames for calls to A. Since B is defined within A, how can I know which stack frame of A is associated with B's closure when B is run? – Tim Aug 25 '17 at 20:13
• @Tim Just pretend that def B() is a statement like B = closure(...). Every call of A defines its own local B. So, every stack frame has its own B closure. There is only one A since we run def A once, but there are many B's since we run def B many times. See if you can figure it out now, otherwise I can provide more details. – chi Aug 25 '17 at 20:34
• Thanks. More details please. Do you mean every stack frame of A contain a local B? Then when B is called inside the innermost stack frame of A, how does B not use the same local I in the same stack frame of A? – Tim Aug 25 '17 at 20:36
• Also note that the book doesn't say every stack frame of A has a local B. In the diagram on the right hand side, there is only one stack frame of B, and two frames of A which don't show to have a local B each. – Tim Aug 25 '17 at 20:41
• @Tim Saying "when B is called..." is misleading you, I think. There is no "B", there are many. Which B is called? The one which was defined on which stack frame of A? You can't see this directly from the picture, but there you can see that P==B has a pointer to the stack frame where that B was defined. The point is, P==B on its own tells us only half of the closure: you have to think of the arrow starting from B as a part of the value of P. P contains the code of B & the reference, i.e. a closure. When P is run, the code of B is run relatively to that frame. – chi Aug 25 '17 at 22:24