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)
break;
/* ... */
}

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))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch)

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.

Sunday, September 7, 2008

The Closures are Coming

Last month, Chris Lattner at Apple announced support for closures in C for Clang, the llvm-based C compiler Apple has been working on as a potential replacement for the venerable gcc. Because Apple is working on this extension, it means that closures are coming to both C and Objective-C.

This is a sorely needed feature C has been missing for quite a number of years. The need may not have been pressing two decades ago, in the era of smaller programs on early 32-bit CPUs with kilobytes or maybe a couple of megabytes of RAM. But those days are long behind us, and constructing programs without closures feels clunky, cumbersome, and a throwback to the era of 8-bit home "computers" running some quirky BASIC dialect.

Nearly every major general purpose programming language in use today supports closures or soon will. There are a few exceptions, like PHP, Tcl, Cobol and Fortran that don't have them, and it's debatable whether these languages are either "major", or will get closures "soon". (Update: PHP 5.3 has/will have closures. See below.)

C# has them, and has made them easier to use in the most recent version the language by providing lambda expressions. Java is likely to get them, and the BGGA proposal looks pretty strong. And even if these languages didn't, F# (which is basically OCaml by another name) and Scala are merging the functional and object oriented disciplines on the CLR and JVM, bringing features like closures and currying to these platforms.

The only major language that doesn't have closures is C, and thanks to Chris Lattner and the llvm team, this is changing. Hopefully their changes will be accepted widely, and this feature will be added to the next C standardization.

Adding closures to C introduces exposes a few leaky abstractions, though. Local variables in C (including parameter values) live on the stack, which doesn't do much good if a closure doesn't live long enough to be invoked. Therefore, this change adds a few new features that allow closures to be copied to the heap (via persistent = _Block_copy(stack_closure)), reference counted while on the heap, and freed when no longer in use (via _Block_release(persistent)). There are a few other wrinkles, and the usage is slightly cumbersome, but, well, it's C, and you should be used to that by now.

However, the implications of this change are much more profound.

Adding closures to C is tantamount to saying it is unacceptable for a general purpose programming language to omit support for closures. All of the old arguments for withholding them are now void: it can be done in a compiled language. It can be done without using a virtual machine. It can be done in a mainstream language. Closures are useful beyond the functional ghetto where the started (and offering just pointers to functions simply doesn't cut it).

If closures are available in C, one of the oldest and most widely used languages without closures, what's your excuse for not providing them in your pet language? It may be hard to do, but the techniques are proven, well known, and open for inspection. The utility of providing programmers with the means to use idioms like map, filter and fold (or reduce) is too overwhelming to claim it's not worth the time, cost or complexity to implement.

The writing is on the wall. If you intend to develop software in the 21st century, you will be using closures, or going to great lengths to avoid them.

This may sound like a bold statement, but it really isn't. Programming languages have co-evolved in fits and starts for decades. Some feature, like recursion, proves itself in academia, but is wildly regarded as unnecessary in industry. Slowly, industry adapts, and that feature becomes a necessity in all future programming languages.

Recursion may sound like an esoteric feature to require in a programming language. After all, it's not something that you expect to use every day. But what about lexical scoping? Believe it or not, block scoped variables weren't standard practice until the mid-1980s or so; having only global variables or dynamically scoped variables was once deemed "sufficient" until the consensus formed around lexical scoping as simply the right way to do it. A similar history surrounds object oriented programming, and garbage collection.

What's next? Who knows. The jury is still out on static vs. dynamic programming environments, live code vs. dead code, metaprogramming, macros, virtual machines vs. native compilation, type inferencing, strong static typing, prototypes vs. metaclasses, and a dozen other features where languages differ. Closures, at least, are on their way to becoming a required feature for every important programming language.