Thinking about a closure confusion

December 26, 2005

Consider the following Python code, which is a very simplified version of certain sorts of real code that people write:

ll = []
for i in range(1,10):
  ll.append(lambda z: i+z)

print ll[0](0), ll[8](0)

A lot of people writing Python code like this for the first time expect to see it print '1 9', when in fact it prints '9 9'.

What I think is going on here is that people are thinking of closures as doing 'value capture' instead of what I will call 'slot capture'. In value capture the closure would capture i's current value, and things would work right. In 'slot capture' the closure captures i's slot in the stack frame and uses it to fish out the actual value when the closure runs. Since i always uses the same slot on every go through the for loop, every lambda captures the same slot value and thus afterwards will evaluate to the same thing.

Slot capture is harder to think about because you have to know more about language implementation; in this case, you need to know what does and doesn't create a new, unique stack frame. For example, this slightly more verbose version of the code does work right:

def make(i):
  return lambda z: i+z

ll = []
for i in range(1,10):
  ll.append(make(i))

Here the make function is needed for nothing more than magically forcing the creation of a new unique stack frame, with the net effect of capturing the value of each i in the lambdas. Is it any wonder that people scratch their heads and get this wrong every so often?

You can think about this not as stack frames but as scopes. This may make the make() example clearer: functions have a different scope from their callers, but the inside of a loop is in the same scope as outside it. (There are some languages where this is not true, so you can define variables inside a loop that aren't visible after it finishes. Even then, you may or may not get a new stack frame every time through the loop. Aren't closures fun?)

This sort of closure confusion is not restricted to Python; here is an example of the same issue coming up in Javascript, in a real version of my Python example.

Scope rules can get quite interesting and complicated, and of course they interact with closures in fun ways. For example, Javascript Closures has a long writeup of the Javascript scope rules, which are somewhat more exciting than the Python ones. (It also has nice examples of the (abstract) implementation details.)


Comments on this page:

From 70.231.184.201 at 2005-12-29 04:44:17:

I don't know python, so this example is particuarly confusing: why isn't the output '10 10' (or even '11 11', but I guess that's a separate oddity)? Indeed, why isn't the output 'exception, variable unbound'?

That is, in a C-like language I'm used to the idea that you can look in the 'i' slot after using it in a for loop and see it having the succeeding value; it seems weird to have a higher-level-language than C that allows the variable to have a meaningful value afterwards, and indeed this sort of bug seems like exactly the reason you wouldn't want it to (it's almost certainly never what you want, at least if used in a closure). Perhaps one should flag it (as much as possible, which probably isn't very much) at compile time: "loop index variable escapes the loop through closures".

"Stack frames" is of course exactly the wrong term, since with closures your variables can't be bound to stack frames anyway, since they can escape!

The javascript link you post to seems to actually indicate that the problem is really that var x = array[i]; doesn't actually create a new variable x with whatever values is in array[i] at that instant, but rather a reference to array[i] indirected through both of those slots!

I say this because what's described in that article is exactly what I would recommend to explain the "scope" answer and to solve the problem, rather than going through another function. Using some hypothetical language:

  for i in 1..10 do {
     ll.append(func(x){i+x;});
  }

should reasonably report "10 10" or possibly "11 11", and

  for i in 1..10 do {
     var j = i;
     ll.append(func(x){j+x;});
  }

should reasonably report "1 10".

A language for which the j-declaration-and-assignment inside the loop doesn't have the effect of ML/Lisp's let, of creating a brand new slot every time through the loop, yet supports closures, is just broken. It's the only sane semantic.

Note that this whole mess is clearer if, if you're going to allow index variables to escape their loops, you either:

  • Make each iteration generate a new copy of the variable, a la my comment above about LET, in which case the "you are a dumb idiot with your naive solution" works correctly (and this is actually a perfectly reasonable semantic from a high-level language semantics POV; the traditional semantic follows from implementation issues of "how do you iterate, producing the values 1 to 10 sequentially").
  • Require index variables to be declared outside the loop so the duration of the slot-sharing follows unambiguously from the lexical scoping. E.g., C++-style loop declarations are misleading for loops in languages with closures.

I imagine the first of those points has been addressed in the literature, but I don't know where to look.

--nothings

By cks at 2005-12-29 15:39:25:

I need to write a longer proper reply, but to cover the quick stuff:

range(i,j) generates a list from i to j-1, so range(1,10) generates a list of 1 to 9. Then the for loop iterates through this list, leaving i set to the list's last element when it terminates. The combination leaves i set to 9 after the loop is over.

(Thus Python for is more like awk's foreach than C's for. C style for loops are generally written with while in Python.)

From 70.231.184.201 at 2005-12-29 23:58:03:

I'd assumed that, it still just seems strange.

For example, mathematics has a notation for 'open' and 'closed' intervals: (0,10) on the integers is the same as [1,9] on the integers, so you could view this as saying that 'range(i,j)' specifies [i,j). And that just seems weird to me, because I can't think of any context in which that's natural. The mathematical notation for that, [i,j), is asymmetric. It matches the traditional C loop style 'for(x=i; x<j; ++x)', so I can see why it might be convenient when expressing things, e.g. adjacent non-overlapping intervals, but it seems to me one of the worst possible choices for plausibility and intelligibility. In the C for() loop the two are not referenced symmetrically, so it's not as surprising.

(Of course, you didn't help matters by using 'range(1,10)' where the traditional thing along those lines would be 'range(1,11)', but I dunno, maybe this is a really common example range in python to help beat into people's skull what it means.)

--nothings

By cks at 2005-12-30 00:16:23:

I suspect that range() has the semantics it does so that 'range(0, len(lst))' works right to create a list of indexes that exactly covers all elements of the list. In fact, the start value is optional and defaults to 0, so you can just write 'range(len(lst))'.

A fair amount of things in Python seem to be carefully designed to combine well with lists and sequences. (I wrote about another one of these in SmallDetailsMatter.)

Written on 26 December 2005.
« Weekly spam summary on December 24th, 2005
A thought about free software licenses »

Page tools: View Source, View Normal.
Search:
Login: Password:

Last modified: Mon Dec 26 00:07:27 2005
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.