Wandering Thoughts archives

Arranging scopes for for loops

Suppose that you have a language where for loop index variables are local to the for loop; they aren't visible outside it. What I'll call the 'for loop closure problem' is that in a straightforward implementation of their lifetime, the following pseudo-code doesn't work the way people think it will:

nums := [];
for (var i = 0; i < 100; i++)
  nums.append(func(x) {i+x});

In straightforward scope and variable lifetime semantics, every lambda returns the same result because each lambda captured the same i (and after the loop finishes, the value of i is 100). When I was discussing what Python closures close over, I mentioned that you could fix this with careful use of how scopes are defined.

First, let's rewrite this for loop to show the scope explicitly:

{var i;
 for (i = 0; i < 100; i++)
   nums.append(func(x) {i+x});
}

If we want each iteration of the loop (and thus each lambda) to get a different version of i, we need to explicitly create a scope for each of them. However, we need all of the following to be true:

• the for loop condition has a single sustained scope, in which its version of i is the same over all iterations of the loop. This creates an outer version of i.
• the for loop body has a per-iteration scope which contains an inner version of i.
• the inner version of i is initialized from the outer version of i.

Of these the only tricky requirement is the third one.

You could fix this with specific rules for scopes in for loops, but as it happens we don't have to bother with this; the language already has a way of expressing this outcome within the existing scoping rules. We just say that the loop body acts as if it was an anonymous function (well, closure) that is invoked on each loop iteration. This effectively rewrites the loop as:

{var i;
 for (i = 0; i < 100; i++)
   func(i) {
     nums.append(func(x) {i+x});
   }(i);
}

Anonymous functions already create new scopes when invoked and function calls are the general method for passing variables into a scope, so we're done.

(Various sorts of optimizations can and generally are applied in languages that define for loops this way, because you really don't want to be creating a call frame for every loop iteration.)

I believe that doing this sort of conceptual rewriting is especially popular in languages (like many versions of Lisp) that consider lambdas and closures to be fundamental building blocks of the language. In these languages, rewriting loops as invocation of anonymous functions makes a lot of sense even if you don't care about the scoping rules. The extreme version is to not even have loop iteration as such in the language's core; instead you transform loops into recursive function calls. (Full tail call optimization is required for obvious reasons.)