Programming Language Beauty: Look Closure

In the past year I have been passionately fighting what Simon Peyton Jones calls "the effects monster", although often it feels like I am fighting windmils instead. No useful programs can be written without effects, but effects turn bad when they are observable from within the program itself. Instead we should strive for encapsulating effects such that they become harmless first class pure values, but more on that in the future. In this first installment in a longer series on the perils of side-effects, we will look at one of the most beautiful examples of observable effects, namely closures and variable capture in imperative languages.

The semantics and differences in variable capture mechanisms for closures between various programming languages is a fascinating topic. One of my favorite examples is was Ruby’s scoping mechanism for blocks. The problem is acknowledged and eloquently explained on page 105 in the second edition of the pickaxe book. I am particularly amused by the proposed pragmatic solution; keep your code small so that it is easy to spot any potential problem, and use some form of Hungarian notation to put local variables and block parameters in a different lexical namespace. Fortunately, this issue is fundamentally fixed in Ruby 1.9; Matz does not have to fear my wrath anymore (thanks to Dave Remy for bringing the remark at around 7:54 minutes into the video to my attention, which of course might not at all be a side-effect of my rants).

To understand the semantic subtleties of variable capture in closures, consider a variation of the example from section 14.5.15.3.2 of the C# 2.0 language specification with a first loop that creates a list of closures DelayedActions, and a second loop that executes the resulting list of closures to accumulate the results into a single string:

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

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

for (var k = 0; k < DelayedActions.Count; k++)
{
   s += DelayedActions[k]();
}

Console.WriteLine(s);

According to the C# language semantics, the "outer" variable i in the closure delegate(){ return i; } is captured as an lvalue so that its lifetime properly extends its static scope. Each iteration of the first loop updates the same reference to variable i that is captured in each of the closures, hence running this program prints 777 on the console.

If you are really geeky, as I am, besides having the C# language spec as nighttime reading, you might enjoy using .NET Reflector to figure out what code the C# compiler generates to make this work.

What you see is that the variable i is lifted into a display class Scoping.Program/<>c__DisplayClass3 that holds the reference to the variable i: 

[CompilerGenerated]
private sealed class <>c__DisplayClass3
{
    public int i;
    public int <Main>b__0()
    {
        return this.i;
    }
}

Each use of the local variable i in the loop is indirected to the instance CS$<>8__locals4 of this display class: 

var DelayedActions = new List<Func<int>>();
string s = "";
 
Func<int> CS$<>9__CachedAnonymousMethodDelegate2 = null;
var CS$<>8__locals4 = new <>c__DisplayClass3();
CS$<>8__locals4.i = 4;
 
while (CS$<>8__locals4.i < 7)
{
   if (CS$<>9__CachedAnonymousMethodDelegate2 == null)
   {
       CS$<>9__CachedAnonymousMethodDelegate2 = new Func(CS$<>8__locals4.
b__0);
   }
   DelayedActions.Add(CS$<>9__CachedAnonymousMethodDelegate2);
   CS$<>8__locals4.i++;
}
int k;
for (k = 0; k < DelayedActions.Count; k++)
{
   s = s + DelayedActions[k]();
}
Console.WriteLine(s);

Interestingly, the DelayedAction list contains just references to exactly one delegate, in other words, the following expression DelayedActions.All(f => f == DelayedActions[0]) evaluates to true. According to section 14.9.8 of the C# 2.0 language specification, this is permitted, but not required, and indeed, when we unroll the loop into three separate statements, three non-equal delegates are created. This is a problem since removing event handlers in C# relies on delegate equality (using the button.Click -= handler idiom) and as a result in many cases it becomes impossible to remove event handlers that are created as anonymous methods or lambda expressions.

var pitifulbutton = new Button();
pitifulbutton.Click += delegate{ Console.WriteLine("Hello World!"); };
...
pitifulbutton.Click -= delegate{ Console.WriteLine("Hello World!"); }; // does not remove handler

Now consider the slightly different program. The only difference is that inside the first loop, the local variable i is now copied into the local variable j that is captured as an outer variable by the closure delegate(){ return j; }. As the C# 2.0 specification warns, closures make the effect of instantiating local variables observable. A new local variable j is instantiated for each repetition of the first loop:

DelayedActions = new List<Func<int>>(); 
s = ""; 
for (var i = 4; i < 7; i++) 
{ 
  int j = i; 
  DelayedActions.Add(delegate(){ return j; }); 
} 
for (var k = 0; k < DelayedActions.Count; k++) 
{ 
  s += DelayedActions[k](); 
} 
Console.WriteLine(s);

However, the semantic effect is much more profound that this small syntactic change. Instead of printing 777, the program now prints 456 since the lvalues captured in each closure are not shared in this case.

Looking at the generated code, we see that the generated code is much simpler than for the previous example. Again there is a display class, now called <>c__DisplayClass5, that instead of the variable i now holds the variable j: 

[CompilerGenerated]
private sealed class <>c__DisplayClass5
{
   public int j;
   public int <Main>b__1()
   {
      return this.j;
   }
}

Inside the loop nothing special is happening to variable i anymore, since it is not captured by the closure, but this time all access to the variable j is indirected to the instance <>c__DisplayClass5 CS$<>8__locals6 of that class: 

DelayedActions = new List<Func<int>>();
s = "";
for (int i = 4; i < 7; i++)
{
   var CS$<>8__locals6 = new <>c__DisplayClass5();
   CS$<>8__locals6.j = i;
   DelayedActions.Add(new Func(CS$<>8__locals6.
b__1));
}
 
for (k = 0; k < DelayedActions.Count; k++)
{
   s = s + DelayedActions[k]();
}
Console.WriteLine(s);

If we would move the declaration of j out of the loop, each closure will capture the same lvalue to a single instantiation of j and the program would print 666 instead of 777 or 456.

Now let's transliterate this sample into JavaScript. It is astonishing how close the two programs are after a little monkey patching to add the method Add to the Array prototype and defining a static class Console. The only remaining difference is creating a new array var DelayedActions = new Array(); in JavaScript versus creating a new list var DelayedActions = new List<func<int>>() in C#. You have to admit that is pretty wicked.

var Console = { WriteLine : alert };
Array.prototype.Add = function(x){ return this.push(x); };

var DelayedActions = new Array();
var s = "";

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

var s = "";
for (var k = 0; k < DelayedActions.length; k++) 
{
   s += DelayedActions[k]();
}
Console.WriteLine(s);

//////////////////////////////////////////////////////

DelayedActions = [];
s = "";

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

for (var k = 0; k < DelayedActions.length; k++) 
{
   s += DelayedActions[k]();
}
Console.WriteLine(s);

However, despite the syntactic likeness, the semantics of the two programs are completely different. In JavaScript, the first output is 777, but the second output is 666. The reason is that in JavaScript, the scope of variable j is limited to the body of the first loop, but all local variables are instantiated at the start of a routine. Another difference between the two program is that now DelayedActions.All(f => f == DelayedActions[0]) evaluates to false, where the routine All could be monkey-patched as: 

Array.prototype.All = function(p)
                      {
                         for(var i=0; i < this.length; i++)
                         {
                           if(!p(this[i])) return false;
                         }
                         return true;                      
                      };

As an aside, the syntactic likeness of C# and JavaScript makes it tempting to pursue a shallow embedding of C# into JavaScript, that is to syntactically transliterate C# programs directly into "natural" JavaScript equivalents. This is contrast to deep embedding where the C# semantics, as defined by its compilation into MSIL, is meticulously encoded in completely unreadable, but correct wrt to the C# semantics, JavaScript. Shallow embedding of one language into another semantically different language as a rule results in a Frankenlanguage that is neither adheres to the source nor target language semantics.

Variable capture and substition in pure mathematics already is a hairy topic which, according to Cardone and Hindley's History of Lambda-calculus and Combinatory Logic, can be traced back to 1889. Add mutable variables to the mix and things become even more complex. Of course the best solution is to just surrender to the mathematicians and remain pure by making the effects of instantiating and mutating imperative variables explicit using the state monad.