Tuesday, September 16, 2008

Closures and Scoping Rules

Although the concept of a closure in a programming language construct is fairly clear, some of the details are a little fuzzy around the edges. The central ideas are that (a) closures are anonymous functions (b) created as first class values that (c) capture variables in the enclosing lexical scope. Unfortunately, the notions of "variable" and "enclosing lexical scope" vary subtly across languages. These lead to odd edge cases that can be demonstrated with contrived examples, but can also lead to unexpected behaviors in legitimate code in some languages.

Take, for example, the much maligned for loop in C:

    if (x) {
for (int i = 0; i < 10; i++) {
if (i == 2)
/* ... */

if (i < 10) {
/* ... */

This snippet raises two important questions: What is the scope of int i? And what should it be? Early C compilers avoided the question entirely by forcing variables to be declared before the first statement. C++ and ANSI C relaxed those rules to allow variables to be declared within the body of a function.

In a language that doesn't support closures or variable capture, these questions are mostly meaningless, unless you're writing a compiler or trying to out-geek the nerd in the next cube. Now that closures are on the table, the finer points of language design have important and subtle consequences.

There are a few ways to interpret this snippet of C code. One way is to consider the for loop a lexical block, and the lifespan of int i is limited to the loop itself; the precondition, postcondition and increment clauses are merely syntactic sugar that are still tied to the loop itself.

Another way to look at the code is to interpret the int i declaration as appearing immediately before the loop, making it visible to any subsequent point in the same block (the if block in this example). This is useful if you want to inspect the value of the loop index after the loop terminates to check whether the loop exited prematurely.

A third way to look at the code is to have the declaration of int i be visible to any subsequent point in the body of the function that declares it. This would mean that although the declaration may appear within the if statement, the variable could be used after the if statement, even if the body of the if statement were never executed.

A fourth way would be to use the declaration of int i as a kind of guidance for the parser. That is to say, the parser would enforce the desired scoping rules, but the compiler would always allocate space for the variable that is visible for the entire body of the enclosing function.

There are other possible interpretations. Sometimes they are actively chosen as the desired way to handle variable scoping. Other times, they are merely a quirk of a buggy implementation. Ruby (pre-1.9), lets code from an inner block leak into an enclosing block:

     $ ruby --version
ruby 1.8.6 (2008-03-03 patchlevel 114) [universal-darwin9.0]
$ irb
irb> i=0; [1,2,3].each {|i|}; i
=> 3

(from Sam Ruby's presentation on Ruby 1.9 from OSCon 2008)

There are many ways to get lexical scoping wrong. But how should it work?

One of the best examples comes from SICP, using Scheme, of course:

    (define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request -- MAKE-ACCOUNT"

Assigning a variable to the result of (make-account 100) creates a new object that contains a single variable balance with the value of 100, and two local functions which reference that same value. Passing the token 'deposit or 'withdraw to that object updates the shared reference to balance.

With this example in mind, the C# team at Microsoft wrote a specification for their language that defined a clear behavior for all of these dark corners, and got them right (or at least resolved the ambiguity in previous languages). Of course, they got lexical scoping right, so closures work properly.

Yet, even with properly implemented lexical scoping, there are still some odd cases programmers need to be aware of. Erik Meijer recently posted an example in C# that can be confusing:

    var DelayedActions = new List<Func<int>>();

for (var i = 4; i < 7; i++)
DelayedActions.Add(delegate(){ return i; });

When the contents of DelayedActions are evaluated, they will return the values 7, 7 and 7. And believe it or not, this is behavior is correct and proper, even if it is unexpected. Each closure captures a reference to the single variable i. Once the loop terminates, the variable persists, and each closure has a reference to the final value of that variable, 7.

A slight change to the code produces a different result:

    var DelayedActions = new List<Func<int>>();

for (var i = 4; i < 7; i++)
int j = i;
DelayedActions.Add(delegate(){ return j; });

In this code, each iteration through the loop creates a new variable j, which copies the current value of i. The result of evaluating this set of closures are the values 4, 5, and 6. The difference is subtle, but important.

Erik Meijer noticed that with a few minor tweaks, the C# code could be run without translation as valid JavaScript. The first example, when translated, still produces the values 7, 7, 7. However, the second example produces the values 6, 6, 6.

Although JavaScript and C# have a C-like syntax in common, they have very different semantics. In JavaScript, declaring a variable inside a for loop does not create a new variable each time through the loop. Instead, it is allocated at the start of the function body! Oops.

All of a sudden, issues that used to be relegated to language lawyers are becoming relevant to everyday developers. And developers today frequently switch between languages, like, say, C# and JavaScript. You can blame Microsoft for doing a lot of things wrong, but their language research group isn't at fault here. If anything, JavaScript is exposing an optimization of dubious value, and letting it change the semantics of the language.

Incidentally, this kind of misunderstanding simply can't happen in Haskell. That's because closures (lambdas and curried functions) don't capture variables, but rather values. (Remember, variables don't vary in Haskell.) Here is a contrived example (using a Ruby-ish approach) that mimics the first C# snippet:

    each :: [a] -> (a -> b) -> [b]
each = flip map

example1 :: [a -> Int]
example1 = [4, 5, 6] `each` (\i -> (\_ -> i))

map (\f -> f ()) example1 -- [4, 5, 6]

This example seems to implement the behavior of the first C# loop, but actually implements the behavior of the second C# loop. That's because each delayed action is capturing a different unique value. To capture a shared reference takes more work, because shared references are less idiomatic:

    import Data.IORef

eachM :: [a] -> (a -> IO b) -> IO [b]
eachM = flip mapM

example2 :: IO [t -> IO Int]
example2 = do i <- newIORef 0
r <- ([4, 5, 6] `eachM` \j -> do writeIORef i j
return (\_ -> readIORef i))
modifyIORef i (+ 1)
return r

Note the odd type for example2. The outer IO is needed to actually construct the delayed actions using some form of shared state. Once the list of delayed actions is constructed, then pulling out the values requires doing something stateful. (The IO monad was used here for simplicity, but another stateful monad could be used here instead.)

Evaluating the list of delayed actions is also trickier:

    example2 >>= mapM (\f -> f ())  -- [7, 7, 7]

What's the lesson here? Closures are coming, but the rules around scoping still vary across languages. Programmers tend to hop around between languages today, much more than we did 10 or 20 years ago. As we adapt to use closures in our programs, we need to be aware of these arcane issues, and how to avoid them.


George Talbot said...

The JavaScript one sounds like a bug.

Andreas Krey said...

I think most of the puzzlement comes from the idea of closing over iteration variables. With a construct like javas 'for (Type val: collection)' the scoping should be more intuitive: a separate 'val' for each iteration.

C++ has another reason to be careful about scoping rules: They decide when a variable goes out of scope and thus when the destructor has to be called.