October 2008 - Posts

Welcome to the first post in my new C# 4.0 Feature Focus series. Today we'll start by taking a look at optional parameters, a long-standing request from the community that made it to C# 4.0. By itself, the feature is definitely useful but in conjunction with the mission to make COM interop easier, there's even more value to it. In this post I'll outline what the feature looks like, how it's implemented and what the important caveats are.

 

The syntax

C# 4.0 can both declare and consume optional parameters. Here's a sample of a very simple method that declares a parameter as optional:

public static class OptionalDemoLib
{
   public static void SayHello(string s = "Hello World!")
   {
      Console.WriteLine(s);
   }
}

This means you can either call Do with one argument or without an argument, in which case the default value is used:

public static class OptionalDemo
{
   public static void Main()
   {
      OptionalDemoLib.SayHello();
      OptionalDemoLib.SayHello("Hello Bart!");
   }
}

Notice all optional parameters need to come at the end of the argument list.

optlib.cs(3,58): error CS1737: Optional parameters must appear after all required parameters

If this weren't the case all sorts of ambiguities would result, e.g.:

public static void SayHello(string s1 = "Hello World!", string s2)

What would a call with a single string argument result in? Would the parameter be bound to s1, overriding the default, or would it bind to s2?

 

The implementation

How does it work? Let's start by taking a look at the definition side. Here's the IL corresponding to the declaration of SayHello above:

.method public hidebysig static void  SayHello([opt] string s) cil managed
{
  .param [1] = "Hello World!"
 
// Code size       9 (0x9)
  .maxstack  8
  IL_0000:  nop
  IL_0001: 
ldarg.0
  IL_0002:  call       void [mscorlib]System.Console::WriteLine(string)
  IL_0007:  nop
  IL_0008:  ret
} // end of method OptionalDemoLib::SayHello

Two things are relevant here. First of all, the parameter is decorated with the [opt]. Second, the method body contains a .param directive. It turns out both of those primitives have been supported in the CLI since the very beginning. Visual Basic is one of the languages that already uses this today. Let's dive a little deeper using the CLI specification (ECMA 335), partition II:

  • 15.4    Defining methods

    opt specifies that this parameter is intended to be optional from an end-user point of view. The value to be supplied is stored using the .param syntax ($15.4.1.4).
  • 15.4.1    Method body

    | .param `[` Int32 `]` [ `=` FieldInit ]          Store a constant FieldInit value for parameter Int32.
  • 15.4.1.4    The .param directive

    This directive stores in the metadata a constant value associated with method parameter number Int32, see $22.9. (...) Unlike CIL instructions, .param uses index 0 to specify the return value of the method, index 1 to specify the first parameter of the method, ...
  • 22.9    Constant : 0x0B

    The Constant table is used to store compile-time, constant values for fields, parameters, and properties. The Constant table has the following columns:
    - Type ...
    - Parent ...
    - Value (an index into the Blob heap)

    Note that Constant information odes not directly influence runtime behavior, although it is visible via Reflection. Compilers inspect this information, at compile time, when importing metadata, but the value of the constant itself, if used, becomes embedded into the CIL stream the compiler emits. There are no CIL instructions to access the Constant table at runtime.

I'll come back to the remark in paragraph 22.9 in just a second. An important thing here is that the value needs to be constant, so no new'ing up of stuff or results of methods calls are allowed:

optlib.cs(3,23): error CS1736: Default parameter value for 's' must be a compile-time constant

What does the call-site look like if the parameter is omitted?

.method private hidebysig static void  Main() cil managed
{
  .entrypoint
  // Code size       24 (0x18)
  .maxstack  8
  IL_0000:  nop
  IL_0001:  ldstr      "Hello World!"
  IL_0006:  call       void [optlib]OptionalDemoLib::Do(string)
  IL_000b:  nop
  IL_000c:  ldstr      "Hello Bart!"
  IL_0011:  call       void [optlib]OptionalDemoLib::Do(string)
  IL_0016:  nop
  IL_0017:  ret
} // end of method OptionalDemo::Main

Notice how remark 22.9 applies here. At the call-site both calls look like a call with one argument. The optional argument is "compiled away" on the side of the caller.

 

The caveat

The remark above quoting the CLI specification is a very important one:

Note that Constant information odes not directly influence runtime behavior, although it is visible via Reflection. Compilers inspect this information, at compile time, when importing metadata, but the value of the constant itself, if used, becomes embedded into the CIL stream the compiler emits. There are no CIL instructions to access the Constant table at runtime.

In human words, default values are burned into the call site. The metadata specified by the .param directive is only used to keep the constant value around, but as soon as a method is called and optional parameters are used in that call (as determined by the compiler), that value gets copied literally to the call site where it sticks. Let's illustrate this:

Step 1: Compile the following (csc /t:library optlib.cs)

using System;

public static class OptionalDemoLib
{
   public static void SayHello(string s = "Hello World!")
   {
      Console.WriteLine(s);
   }
}

Step 2: Compile the following (csc opt.cs /r:optlib.dll)

using System;
using System.Reflection;

public static class OptionalDemo
{
   public static void Main()
   {
      OptionalDemoLib.SayHello();
      Console.WriteLine(typeof(OptionalDemoLib).GetMethod("SayHello").GetParameters()[0].RawDefaultValue);
   }
}

Step 3: Run opt.exe

> opt.exe
Hello World!
Hello World!

Step 4: Change the library and recompile (don't recompile the opt.cs demo caller)

using System;

public static class OptionalDemoLib
{
   public static void SayHello(string s = "Hello Universe!")
   {
      Console.WriteLine(s);
   }
}

Step 5: Run opt.exe

> opt.exe
Hello World!
Hello Universe!

In step 2 we're introducing the use of reflection to get the default value for the optional parameter. This is run-time reflection that actually inspects the metadata associated with the method's parameter. However, as 22.9 mentions: "There are no CIL instructions to access the Constant table at runtime.", so the default value gets burned into the call site by the compiler. This is no different than the same constant-ness encountered in the difference between readonly variables and constants. The key take-away from this: once you expose a default parameter value on a public method, you can never change it without recompiling all clients that depend on it. For library writers, this never means never ever. If you need the flexibility of changing defaults afterwards, consider providing overloads instead:

using System;

public static class OptionalDemoLib
{
   public static void SayHello()
   {
      SayHello("Hello Universe!");
   }

   public static void SayHello(string s)
   {
      Console.WriteLine(s);
   }
}

This way the constant remains on the definition side and can be changed over there at will. Not that you should do so regularly of course, as you're after all changing defaults that are hopefully documented somewhere in the XML comments for your public methods. Yet another way to attack the problem if you have a bunch of parameters is to take in a property "bag" as the argument to the method (in practice and object with properties for all the supported setting "parameters"). That way every value can be optional and the method can examine whether certain omissions can be granted. Dispatching to the internal implementation with the maximum parameter list could use techniques like null-coalescing (??):

public static void ComplexSayHello(Message arg)
{
   ComplexSayHelloInternal(..., arg.Text ?? "Hello Universe!", ...);
}

Use the right approach - all techniques have their benefits.

 

The past

We've talked about the future, but let me point out it was actually possible to declare optional parameters in C# before, using parameter metadata custom attributes:

using System;
using System.Runtime.InteropServices;

public static class
OptionalDemoLib
{
   public static void SayHello([Optional][DefaultParameterValue("Hello Universe!")] string s)
   {
      Console.WriteLine(s);
   }
}

This produces the same IL as the sample shown earlier using C# 4.0 syntax. C# couldn't consume this method though without specifying all parameters, but now it can.

 

Conclusion

Optional parameters are a beautiful feature and will make life easier when dealing with old COM-driven libraries that were designed with this language feature in mind (amongst others such as named parameters, see next post). To keep the picture symmetric, C# 4.0 also provides the ability to define optional parameters, but be well-aware of the call site burning fact mentioned above. Only use optional parameters if the optional value is really constant in the time dimension unless you're never going to expose the optional value to the outside world (but it's damn easy to make a previously internal or private method public and forgetting about this fact, so the first rule should be the strongest decisive factor...). Don't get me wrong: I like the feature a lot, but powerful weapons need safety warnings.

Next time: named parameters. Enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

With the PDC 2008 going on, it's time to start talking about C# 4.0 features. To summarize this next release of the C# language, it's most about the marriage between the static and dynamic world views, or in other words how languages that are known to be statically typed can reach out to the world of the DLR and beyond. But before I start with a blog series on the next version of C#, here are a few pointers to check out:

In the upcoming blog series on C# 4.0 features, I'll cover:

  • Co- and contra-variance
  • Named and optional parameters
  • "Dynamic" features
  • Improved COM Interoperability

As usual, I'll try to find the sweet spot between the use of the various features and how they're implemented internally (put on your IL-glasses if you don't want to get IL-burn). Besides language enhancements, I'll talk a bit about various library enhancements as well.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Visual Studio 2010 & .Net Framework 4.0 Logo

The word is out finally. With the PDC 08 going on as we speak, you can now download the bits of the next-generation .NET Framework and Visual Studio technologies. In the days to come I have a bunch of blog coverage coming up for quite a few of the framework and language related features. I won't give away all the details yet as PDC sessions should have the honor of revealing what we've been up to but here are a few buckets for blog post topics that are in the queue:

  • .NET Framework 4.0 side-by-side
  • C# 4.0 language features
  • New namespaces and BCL libraries
  • Parallel computing

Stay tuned; it's going to be a most exciting ride on the waves (gently referring to our new logo) of .NET 4.0.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

A few days ago I had a derailed conversation on C# languages features once more. It turned out that closures are not well-understood in general, so I wanted to point out a few things in an attempt to clarify the concept and how it’s implemented in the language. By the end of this post you’ll understand what the following dialog is really telling you and why there’s no way around it without what I’d call leaking the closure from the language implementation space into the developer’s code space:

image

 

Cruel lambdas

But first a tale on cruel lambdas. This week I saw the following piece of code in a training manual I got to read somehow (literal color-inclusive bold-exclusive copy):

[TestMethod()]
public void ReadFromSocketTest()
{
    string str = null;

    MockReceiver mockReceiver = new MockReceiver();
    mockReceiver.UpdateImpl = delegate(string text)
    {
        str = text;
    };
   
/* or in C# 3.0 lambda syntax
    mockReceiver.UpdateImpl = text => str = text;
    */

    // send to receiver
    ClassUnderTest cut = new ClassUnderTest();
    cut.Send(“hi there”, mockReceiver);

    Assert.AreEqual<string>(“hi there”, str);
}

By the coloring of the added comment I can tell how the code did not end up in the Word document: copy-paste from VS (the bold line would be green otherwise). In other words, this is a case of lost in (reverse) translation, that even a lambda-geek like me needs a few seconds to stand still and wonder: does this work? But sure enough, it does. Simple assignments (ECMA-334 §14.14.1) are expressions; writing “lhs = rhs” simply takes on the value of what got assigned to lhs:

14.14.1 Simple assignment

The = operator is called the simple assignment operator. In a simple assignment, the right operand shall be
an expression of a type that is implicitly convertible to the type of the left operand. The operation assigns the
value of the right operand to the variable, property, or indexer element given by the left operand.

The result of a simple assignment expression is the value assigned to the left operand. The result has the
same type as the left operand, and is always classified as a value.

This is an interesting thing by itself. Consider the following fragment:

{
   int
a, b, c;
   a = b = c = 0;
}

What do you think the compiler will emit as warnings? Here’s the answer: “warning CS0219: The variable 'c' is assigned but its value is never used”. Remove c altogether and now the warning reads the same but with c substituted by b, and so on. I’ll leave it to the reader to figure out why this happens as a thought experiment (but don’t leave your sleep for it). Also, if there would be a property (or indexer) assignment in the set of assignments above, only the setter would get called, never the getter:

a.Bar = a.Foo = 0;

wouldn’t call a.get_Foo() in order to feed it in to a.set_Bar(int). Instead, the value that got assigned to Foo (i.e. 0) will be fed in to the Bar setter.

But there are more subtle things going on in the innocent-looking comment above. The type of the UpdateImpl property actually is an Action<string>, so it’s void-returning. I’m using the word returning here as lambdas read as if they are to return something by their very functional nature. So the statement made by the Word-document altering person about lambda syntax equivalence is off a little. Why? Consider the following code:

{
   string s = null;

   Action<string> a1 = t => s = t;
   Action<string> a2 = t => { s = t; };
}

There’s a difference here. In the first case we’re discarding the result of the lambda body, while in the second one the lambda has a statement body without a return, so it’s inferred to be void. The first form is the one referred to in the C# comment, while the second one corresponds to the simplified form in the original code without the anonymous method.

All of this still doesn’t cause me to call this lambda “cruel”. There’s nothing wrong with leveraging the expressive power of lambdas to simplify existing anonymous method based code. However, where the cruelty comes in is in the side-effect encoded in the lambda body. Let’s rewrite the lambda a bit and assume we’re using a string-returning function instead (ruling out the implicit discard of the expression value) and introduce another pair of parentheses to make things more readable:

string s = null;
Func<string, string> f = (t => s = t);

Here we’re capturing the outer scope variable s in a closure, so invoking f somewhere will change the s in the outer scope:

private class Closure
{
   public string s;

   public string f(string t)
   {
      return (s = t);
   }
}

Closure c = new Closure();
c.s = null;
Func<string, string> f = c.f;

where all references to s in the original code have been replaced by references to the public field on the closure class instance. So all we’ve created here is another way to perform assignment to a local variable through some function:

f(“Hello”)

assigns “Hello” to the (captured) local variable s and returns the value that got assigned. It’s almost as if f(…) is syntactical sugar for s = …. Notice I’m also avoiding some more complexities by using a reference type instead of a value type, I’ll give you some time to think about this. Consider the (syntactically) reverse lambda:

string s = null;
Func<string, string> f = (t => t = s);

This is a subtle one. Do you think we now have f(…) as a shorthand for … = s? Why (not)?

 

Quiz

If you think you understand all subtleties aforementioned, try to predict the output for the following:

string s1 = "John"; string t1 = "Bart";
Func<string, string> assignRefO = t => s1 = t;
Console.WriteLine("s1 = \"{0}\"; (t => s1 = t)(\"{1}\") = \"{2}\"; s1 = \"{3}\"", s1, t1, assignRefO(t1), s1);

int i1 = 0; int j2 = 1;
Func<int, int> assignValO = j => i1 = j;
Console.WriteLine("i1 = {0}; (j => i1 = j)({1}) = {2}; i1 = {3}", i1, j2, assignValO(j2), i1);

string s2 = "John"; string u = "Lisa";
Func<string, string> assignRefI = t => t = u;
Console.WriteLine("s2 = \"{0}\"; u = \"{1}\"; (t => t = u)(s2) = \"{2}\"; s2 = \"{3}\"", s2, u, assignRefI(s2), s2);

int i2 = 0; int k = 2;
Func<int, int> assignValI = j => j = k;
Console.WriteLine("i2 = {0}; k = {1}; (j => j = k)(i2) = {2}; i2 = {3}", i2, k, assignValI(i2), i2);

 

The key take-away for our short adventure through cruel lambdas: side-effects through closures can be rather subtle to spot (as the capturing of local variables into a closure goes unnoticed, and that by itself deserves whole posts by itself) but have a huge impact. And that brings us back to our first screenshot, brought up by the refactoring “Extract Method” feature in Visual Studio.

 

Closures and refactoring

Back to our first screenshot, but slightly annotated:

image

I’ve used two colors here. Actually all errors are bad, but compile errors in this case are far better than semantic changes that go unnoticed. How did I got to the dialog? It’s really simple: take any piece of code that has a closure in it, either an anonymous method or a lambda expression that captures a local variable, and choose Extract Method:

image

Let’s take a look at both possible error cases the dialog outlines, starting with the worst one: a semantic change. Assume the following piece of code:

static void Main()
{
    int x = 0;
    Func<int> f = () => x;
x = 5;
Console.WriteLine(f());
}

gets refactored into:

static void Main()
{
    int x = 0;
    Func<int> f = GetFunction(x);
x = 5;
Console.WriteLine(f());
} private static Func<int> GetFunction(int x) { Func<int> f = () => x; return f; }

If you’ve understood the way closures work, it should be piece of cake to predict what the first fragment prints. Right: 5. The reason this happens is because the outer local variable ‘x’ gets captured in a closure class, together with the defined lambda expression. When updating x on the third line, we’re really updating the public field on the closure instance, so the call through the delegate f will produce 5 as its result. However, the second fragment will print 0. Why is that? Due to the refactoring, the original value of x, i.e. 0, got copied by-value to a local variable ‘x’ in the GetFunction method, where it got captured by a closure. There’s no way the Main method can ever update a local of a called function, so the copy of x is trapped in the closure forever and the returned function will always print 0. So the assignment on line three doesn’t have any effect whatsoever on the lambda.

What really would need to happen to preserve semantics in this case, is to bubble up the closure to the original method, in order to capture the local variable ‘x’ in the context of the Main method. This what I referred to in the introduction paragraph as “leaking the closure to the developer space”, i.e. take it in your own hands:

static void Main()
{
    Closure c = new Closure();
    c.x = 0;
    Func<int> f = GetFunction(c);
    c.x = 5;
    Console.WriteLine(f());
}

private static Func<int> GetFunction(Closure c)
{
    Func<int> f = () => c.x;
    return f;
}

One way the refactoring could work is by performing all this machinery on behalf of the developer, but that would make refactoring to have non-local effects (i.e. rewriting code other than the selected piece). The original piece of code would get expanded all the way down to the closures (the types of which become visible in the code) and then the real refactoring could work without causing semantical problem. But that’d be also the end of transparent closures…

But let’s move on to the second case where a compile error results after the refactoring. To illustrate this, consider our cruel lambda again:

static void Main()
{
    int x = 0;
    Func<int, int> f = y => x = y;
f(5);
.WriteLine(x); }

Now trying to refactor the second line produces the following dialog. Notice the way the variable y is passed to the method being generated:

image

And here’s the result:

image

What has happened now? The refactor engine has seen that one of the variables in the selected piece of code is being assigned to, so it needs to bubble up that change after the method has returned, hence it feeds in that variable using by-reference parameter passing style. However, in this case this won’t compile:

image

Of course you’re curious to know why this is the case. Well, let’s assume we’d be able to by-ref a parameter in to an anonymous method or lambda expression (query expressions follow as those are simply glue for lambda expressions passed in to certain methods). Consider the following piece of code:

static void M1()
{
    Func<int, int> f = M2();
    f(5);
}

static Func<int, int> M2()
{
    int x = 0;
    return GetFunction(ref x);
}

static Func<int, int> GetFunction(ref int x)
{
    return y => x = y;
}

To see what’s going on, we’ll try to form a picture of the stack behavior when executing this code. In doing so, we’ll simplify quite a bit, ignoring calling convention, stack frame and other details that occur in practice. However, all we need to care about in this case is the behavior of the stack with regards to local variables. Starting with the execution of M1, we notice there’s one local variable containing ‘f’, the delegate retrieved by calling M2. Let’s call this local variable FUNC, a 32-bit pointer to the function in memory. Initially it’s unassigned as we’ve not called M2 yet:

(M1)  FUNC*  -->  ????

Now we’re calling M2, where two variables will live on the stack: one containing the integer value x, called intx, and one containing the return value of the call to GetFunction, again of type Func<int, int>:

      intx
(M2)  FUNC*  -->  ????
(M1)  FUNC*  -->  ????

Time for the real work, the call to GetFunction (abbreviated GF). Here two items appear on the stack: the closure created by the hypothetical lambda expression capturing the outer variable x, and the result of the call, again our delegate type. I’m simplifying here, but the relevant thing is that the (hypothetical) reference parameter for ‘x’ is stored inside the closure as a public field (the whitespace that occurs in the stack is purely for ASCII-art purposes):

      CLOS*  -->  {intx*, func}
                     |      ^
                     |      |
(GF)  FUNC*  --------~------+
      intx   <-------+
(M2)  FUNC*  -->  ????
(M1)  FUNC*  -->  ????

Notice the closure is heap-allocated, which is crucial in the implementation of closures, after all we want them to outlive the scope of the method they’re defined in. Now what happens when GF returns?

                  {intx*, func}
                     |      ^
                     |      |
      intx   <-------+      |
(M2)  FUNC*  ---------------+
(M1)  FUNC*  -->  ????

Our local variable for the return value of M2, the delegate, points at the function in the closure, so the closure is kept alive. At the same time, the hypothetical reference parameter x captured by the closure is pointing at our local variable x. This is where the real problem kicks in, assume M2 now returns:

                  {intx*, func}
                     |      ^
                     |      |
      intx   <-------+      |
                            |
(M1)  FUNC*  ---------------+

Now we have a dangling pointer to a place in the stack that’s post its stack frame’s lifetime. At this point, all bets are off and everything imaginable can happen, for example a subsequent call to another function will overwrite the value of int x by something else that doesn’t necessarily need to be an integer. So all that remains is rotten type safety, no wonder reference and output parameters are a big no-no in lambda expressions.

If you really want to shoot yourself in the foot, it’s possible to do so of course. Here’s a sample using unsafe code:

static void M1()
{
    Func<int, int> f = M2();
    M3(f);
}

static unsafe Func<int, int> M2()
{
    int x = 0;
    return GetFunction(&x);
}

static unsafe Func<int, int> GetFunction(int* x)
{
    return y => *x = y;
}

static void M3(Func<int, int> f)
{
    long x = 123;
    f(5);
    Console.WriteLine(x);
}

Bonus points if you can predict what a call to M1 will print to the screen. Quiz: Can you use this piece of hacking to construct a method called “GetEndianness” to determine whether your computer has a little or big endian architecture? What’s a better (i.e. without unsafe code) alternative to determine this in managed code?

 

TypedReferences and not so secret keywords

Talking about all of this by-reference passing stuff, this is the ideal opportunity to dive into parameter passing on the CLI in more detail. Most, if not all, readers of my blog will be familiar with two of those strategies:

  • by value – the value of an object is passed from caller to callee; for example, an integer is pushed on the stack or the address of a reference type instance is pushed on the stack.
  • by reference – here the address of the data is passed from the caller to the callee; this is what we’ve used in the previous paragraph.

However, there is a third, far less known, parameter passing style supported on the CLI: typed references. It’s very similar to by-ref, but besides of the address of the data also a runtime representation of the data is passed from the caller to the callee. But what’s the use for this? Assume the following scenario: you want to create a function that accepts any type of data in a by-ref fashion, because you want to change it inside the method. In some sense, the function you’re about to write needs to be polymorphic in that specific parameter. One way to accomplish this is to pass the data by-ref as a parameter of type object. What’s wrong with this? For value types, this will cause boxing, thus heap allocation. By-ref would eliminate this problem at the cost of sacrificing the intended flexible nature of the parameter, as we’d need to be specific about the type. Typed reference allow to work around this problem.

A central concept in both by-ref (and hence output parameters in C# which are implemented as by-refs with some additional metadata) and typed parameters is that of a home. A data value’s home is a location where it can be stored for possible reuse, e.g. a local variable, a method’s argument, an array element or a field. In the case of typed references, both the address of the home and information about its type are passed in the typed reference.

It turns out that C# actually supports typed reference to a limited extent, in an official way by means of direct usage of System.TypedReference and compile-time errors for uses that are invalid, but also using undocumented keywords. I’m purely showing this for illustrative purposes, as no-one should rely on this undocumented feature; it turns out there are only a handful of places in the BCL code where this is being used for very specialized tasks. For the interested, I’ve blogged about another of these – __arglist – in my post entitled: “Calling printf from C# - The tale of the hidden __arglist keyword”. Here’s a sample on how to get a typed reference and use it:

static void Main()
{
    int i = 123;
    Do(__makeref(i));
    Console.WriteLine(i);
}

static void Do(TypedReference tr)
{
    Type t = __reftype(tr);
    int i = __refvalue(tr, int);
    __refvalue(tr, int) = -i;
}

Think of those keywords as follows: __makeref has the potential of & (address-of) but does a little more to get the type information, __reftype gets the type that was captured by the typed reference, and __refvalue behaves like a * (dereference) and can be used both as a lhs or rhs.

As you can see, it’s perfectly possible to pass the typed reference as a parameter in a method call. However, trying to use it in ways that are inherently unsafe is prohibited by the compiler. For example, trying to return the typed reference results in the following error:

error CS1599: Method or delegate cannot return type 'System.TypedReference'

Trying to use it in an output parameter or reference parameter (which are intrinsically the same) is prohibited too, for similar reasons as the ones outlined in the previous paragraph:

error CS1601: Method or delegate parameter cannot be of type 'out System.TypedReference'

An finally, trying to use the typed reference as a field in a class won’t work either, as you can’t stick a typed reference on the heap having it point to a stack-allocated object:

error CS0610: Field or property cannot be of type 'System.TypedReference'

What about trying to define a cruel lambda with a captured typed reference in its closure? Here you can outsmart the compiler:

static Func<int, int> Bar()
{
    int i = 0;
    TypedReference tr = __makeref(i);
    return j => __refvalue(tr, int) = j;
}

This produces the following closure class:

image

Notice how the typed reference forced its way in the closure class. However, the runtime knows this is a violation, so trying to execute the following:

int i = Bar()(1);

results (thankfully) in the following nice exception:

image

 

Conclusion

Know you closures! While anonymous methods, lambdas and everything that uses them, like LINQ, are great pieces of technology, you should know a bit about how they’re implemented and why refactoring pieces of code that contain them is a potentially dangerous operation. There are a few things to do here:

  • Avoid mutating state in a lambda expression. Doing so will cause the refactoring to pass the mutated variable by-ref, causing a compile error. As an example, none of the LINQ operators requires you to do so (although you can). Here’s a bad sample on how to use LINQ:

    int i = 0;
    var res = from x in source where select new { Index = i++, x.Name };
    // bad things can happen to i here
    foreach (var item in res)
       …


    I’ll leave it to the reader to figure out the better way to make this numbering work; there are a few ways, but suffice to say: Select might have useful brothers.
  • Try to avoid changing a captured local variable after it has been captured. Doing so puts refactoring efforts at risk, especially when value types are used as they’ll be passed by-value to the refactored method. When the variable in the original method is changed after the point of the call to the refactored method, its mutation won’t become visible to the lambda. If you still need to do this, refactor at least the block of code that contains the declaration and all uses of the variable being captured, so that the closure in the refactored method will have the same reach as the original for that particular variable.

    int i = 0;
    // … 1
    Func<int> f = () => i;
    // … 2
    int j = f();
    // … 3


    Quiz: What is/are the danger zone(s), expressed in terms of the marked blocks, for semantical changes when the “() => i” lambda is refactored behind a GetFunction method, assigning the result to f? How can the type of the variable i (and hence the generic parameter to Func`1) influence this?

Hope this helps to understand closures a bit better.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Introduction

We’ve been talking about functional programming quite a bit already. One of the things used frequently in functional programming is recursion, instead of imperative loop constructs. Both have their advantages, but often recursive techniques can cause significant degradations in performance. The prototypical sample is the computation of the Fibonacci sequence (a typical interview question, too). In mathematical terms, Fibonacci is expressed as:

fib : N –> N

fib 1 = 1
fib 2 = 2
fib n = fib (n – 1) + fib (n – 2), n > 2

Translating this directly into functional style of code yields the following (F#):

let rec fib n =
   if n <= 2 then
      1
   else
      fib (n – 1) + fib (n – 2)

or, in C# 3.0,

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

The reason we need to spread this across two lines is interesting by itself. If we don’t do this, the following error appears:

memoize.cs(17,48): error CS0165: Use of unassigned local variable 'fib'

referring to the highlighted position in the code:

Func<uint, uint> fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

The reason this error pops up is because we’re defining a function in terms of itself, something that’s invalid in a variable declaration/assignment in C#, just like the following is invalid:

int a = a + b;

F# addresses this through the use of the rec keyword, but that’s a separate discussion. But what are we doing really when declaring the following?

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

Here’s the answer:

image

Notice the <>c__DisplayClass1, a closure. When assigning the lambda on the second line to fib, we’re capturing the fib variable itself as it appears in the lambda’s body. In more detail, this happens:

image

On lines IL_0007 to IL_0009 we store null as the value for fib, immediately replacing it on lines IL_000e to IL_001b with a new function retrieved from <Main>b__0. This is where the code becomes self-referential:

image 

As you can see on lines IL_0005 and IL_0013 we’re loading the variable we got assigned to by Main (but this code by itself doesn’t know that) in order to call it 4 lines further on, through the delegate. The rest of this code is a trivial translation of the ternary operator. Why is the interesting at all? It turns out this will be fairly important further on in this article as we’ll want to tweak this function.

 

What’s memoization?

Looking at our Fibonacci sequence sample again, try to imagine the call tree that results from a call like fib(10). Or let’s simplify it, consider Fib(5). Here’s the call tree:

Fib(5)
Fib(4)
  Fib(3)
   Fib(2)
   Fib(1)
  Fib(2)
Fib(3)
  Fib(2)
  Fib(1)

We’re calculating things over and over again. So how can we solve this? First of all, by embracing an imperative style, at the cost of the more declarative natural mapping of the original recursive definition:

uint Fib(uint n)
{
   if (n <= 2)
      return 1;
   else
   {
      uint prev = 1;
      uint curr = 1;
      for (uint i = 0; i < n – 2; i++)
      {
         uint t = curr;
         curr += prev;
         prev = t;
      }

      return curr;
   }
}

You’ll agree that this encoding of the algorithm makes things more cumbersome and far more difficult and less obvious to grasp and understand due to the temporary variables etc. With memoization we’ll be able to keep our original functional definition (using recursion), while improving the performance. To accomplish this, we’re caching the function results and therefore we’re relying on an essential property of mathematical functions: given the same set of inputs, they always yield the same result. This also implies our to-be-memoized function should be side-effect free as we’ll shortcut the function’s computation body whenever we observe the same set of arguments (depending on the underlying caching technique and cache eviction policies, the number of computation invocations might even become unpredictable, therefore we shouldn’t rely on effectful computation).

 

Measuring success

Before we claim things like “10 times better”, we should establish a baseline for comparison and create a mechanism to measure our success. As usual, we’ll rely on the System.Diagnostics.Stopwatch class to do so:

static void Test(Func<uint, uint> fib)
{
   Stopwatch sw = new Stopwatch();
   sw.Start();

   var res = from x in Range<uint>(1, 40, i => i + 1) select new { N = x, Value = fib(x) };
   foreach (var i in res)
      Console.WriteLine("fib(" + i.N + ") = " + i.Value);

   sw.Stop();
   Console.WriteLine(sw.Elapsed);
}

In here I’m using a generalization of Enumerable.Range I find useful (although here there’s no real need to range of uint for the input, our function could well be Func<int, uint>):

static IEnumerable<T> Range<T>(T from, T to, Func<T, T> inc) where T : IComparable<T>
{
   for (T t = from; t.CompareTo(to) <= 0; t = inc(t))
   {
      yield return t;
   }
}

Actually you’d call Range “For” instead and it becomes very apparent what it’s all about, isn’t it? Let’s take a look how our current implementation does:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
Test(fib);

Yes, it’s fine to say it: in one word terrible

image 

Injecting the memoizer

As mentioned before, our strategy to tackle this inefficiency will be to trade instructions for memory, essentially keeping a cache of calculated values in some kind of cache. The built-in collection type that’s ideal for this purpose is obviously the generic Dictionary<K,T> in System.Collections.Generic. But how do we get it in our function definition seamlessly? In other words, given any function of arity 1 (meaning it takes in one argument, we’ll look at extending that further on), how can we sprinkle a little bit of memoization on top without changing the outer contract of the function? Here’s the code that allows us to preserve the signature but slice the memoizer in between the original function and the memoized one:

static Func<T, R> Memoize<T, R>(this Func<T, R> f)
{
   Dictionary<T, R> cache = new Dictionary<T, R>();
   return t => {
      if (cache.ContainsKey(t))
         return cache[t];
      else
         return (cache[t] = f(t));
   };
}

Actually this code can be optimized a little further using the TryGetValue method on the Dictionary class, and if you have more taste than me the else-block statement can be writter in a nicer way (if I was in a real evil mood, I’d have put it in a ternary operator conditional). I’ll leave such rewrites to the reader as an additional opportunity to express personal style :-).

Notice how the signature of the returned function is the same as the original on: that’s what makes our implementation seamless and transparent. I’m writing this as an extension method on Func<T, R>, but there’s no need to do it that way. What’s more important though is how it works internally. Again you can see closures at work, because what we’ve really created here is something that looks like this:

class Memoizer<T, R>
{
   private Dictionary<T, R> _cache = new Dictionary<T, R>();
   private Func<T, R> _f;

   internal Memoizer(Func<T, R> f)
   {
      _f = f;
   }

   internal R Invoke(T t)
   {
      if (cache.ContainsKey(t))
         return cache[t];
      else
         return (cache[t] = _f(t));
   }
}

You can look at it as lifting an existing function into the memoizer (one per function as we need a unique cache on a function-per-function basis). Obviously you’ll need similar implementations for other function arities (including the zero-argument function, typically used for delayed computation scenarios). Here another issue pops up: the lack of Tuple<T1, …, Tn> types (with proper implementations for Equals and GetHashCode) that would be useful in such a case to express the dictionary’s key type. Even more, the debate on how much generic overloads to provide (Action<T1, …, Tn>, Func<T1, …, Tn>, Tuple<T1, …, Tn>, etc) enters the picture again. Unfortunately the type system isn’t rich enough to have a “Tuple<params T[]>”. At runtime there are ways to get around this, but then we enter dynamic meta-grounds again, so let’s not deviate from our path this time and keep that discussion for another time.

 

Putting it to the test

Back to our original code:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
Test(fib);

Easy as it seems you might think the following will do the trick:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
Test(fib.Memoize());

but unfortunately you won’t see any noticeable effect by doing so. Why? Take a closer look at what’s happening. The code above is equivalent to:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

Memoizer<uint, uint> m = new Memoizer<uint, uint>(fib);
Func<uint, uint> fibm = new Func<uint, uint>(m.Invoke);
Test(fibm);

Now we’re calling through fibm, which results in invoking the Invoke method on the (simplified) memoizer’s closure class. But look what we’re passing in to the constructor: the original fib instance, which really is a public field on another closure as explained in the introduction paragraph. So ultimately we’re just memoizing the “outer” fib function, not the “inner” recursive calls. How can we make the thing work as we expect it to? Remember from the introduction paragraph why we needed the following trick?

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

The generated code stores fib in a closure class field <>c__DisplayClass1::fib. In fact, there’s no such thing as a local variable fib in the IL-code; instead all occurrences of fib have been replaced by ldfld and stfld operations on the closure class’s field. But what’s more is that the closure class’s <Main>b__0 method uses the same field for the recursive calls to fib (see the last figure in the introduction paragraph). That’s precisely what we need to know in order to make the memoizer work: if we assign the result of fib.Memoize() to fib again, we’re replacing the field value that’s also used in the recursive calls:

Func<uint, uint> fib = null;
fib = n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
fib = fib.Memoize();
Test(fib);

As a little quiz question: why can’t we write the following instead?

Func<uint, uint> fib = null;
fib = (n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2)).Memoize();
Test(fib);

And here’s the result:

image

Much better, actually much more than “10 times better”.

 

Additional quiz question

Would you be able to do all of this with expression trees, i.e. with the following hypothetical piece of code:

LambdaExpressiion<Func<uint, uint>> fibEx = null;
fibEx = n => n <= 2 ? 1 : fibEx(n - 1) + fibEx(n - 2);
// what now?
Test(fib);

Why (not)?

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

imageRecently I had the opportunity to sync up with Erik Meijer and Charles Torre for a Channel 9 “Going Deep” and “Expert to Expert” interview: Erik Meijer and Bart De Smet: LINQ-to-Anything. In this episode we talk about LINQ’s extensibility mechanisms, all the way from the language integrated side of the story (front-end language syntax) – or fan in – to the implementation of query providers – or fan out – and the depths of IQueryable<T>.

A few useful pointers are LINQ to AD, LINQ to SharePoint, LINQ through PowerShell, LINQ to MSI. Other referenced articles include:

Much more stuff can be found in my LINQ blog post category, and of course there’s always more to come.

 

To elaborate a bit on fan-in and fan-out and my statement on the square infinity possibilities of LINQ, take a look at the following slides from a recent presentation I delivered on the topic:

image image

The number of languages is constantly growing and with growing interesting in DSLs that’s not going to change, whether you like that or not. So embedding LINQ in more of these languages – requiring concepts like first-class functions, closures and expression trees or quotations – is one side of the coin that gives us infinite possibilities. On the other side, we get all of the LINQ to * implementations where LINQification is possible for virtually every type of data model. In quite some cases it comes for free with IEnumerable<T> and LINQ to Objects, but in other cases we need runtime translations based on expression trees. Again, this provides infinite possibilities. Ultimately the LINQ term disappears from the function composition as it becomes “just another daily instrument” that’s taken for granted.

Just think about the composition of both sides, making things like “LINQ to SharePoint through PowerShell” possible, as I was showing in a demo with that particular presentation (apologies for the picture quality – it’s a PrntScrn from the recording replaying in Windows Media Player as I don’t have the setup for the demo here right now):

image

Ultimately I’d say that LINQ should be part of every data source’s DNA:

image

Enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

With a hypothetical next release of the C# language around the corner (more about that after Anders, our language Caesar, has delivered his “Future of C#” talk on the PDC 08), I’ve had the honor to receive an early print of The C# Programming Language Third Edition. As you can guess, this book is the successor to The C# Programming Language Second Edition, now extended with coverage for the C# 3.0 features and based on the unified C# Language Specification 3.0.

So why would you want to buy a language specification in book format? Personally I like to have those things in print on my desk, just like I have The Common Language Infrastructure Annotated Standard on my desk (unfortunately lagging behind a bit on ECMA 335). But there’s more to it with this new edition of the book: it got annotated by a bunch of people, providing additional insights about the different language features, design decisions, consequences of those decisions, best practices on when and how to use certain features, etc. In other words, if you like to have the ultimate coverage of the C# language (not its uses through certain tools using certain libraries) but don’t want to be bored to death by language specification legalese, this book is for you. The annotations are numerous, enlightening and by times funny.

 

Some language history

Talking about language evolution, people often raise the question where the language is going with all those new fancy features. Doesn’t it become too bloated? Well, every new feature definitely ages the language (quoting Anders here) and some of the original features are ready for the graveyard because they got superseded by newer more powerful features. And yes, having more features means there’s more to learn when approaching the language. But at the same time, one shouldn’t forget about the core value of a language: capturing common paradigms and patterns, making them easier to use (expressiveness) and less error-prone. A few samples to illustrate this point.

Starting with C# 1.0, one of the common design themes of the language was what I’d call “honesty and pragmatism”. Programmers were talking all the time about e.g. properties, events and function pointers, so why shouldn’t these concepts become constructs directly available in the language? Such observations not only shaped the language but the underlying runtime as well, resulting in first-class support for metadata everywhere (well, almost everywhere). Pragmatic, yes, but honest? Sure enough. Although strictly speaking concepts like properties are foreign to minimalistic object-oriented programming (yes, you can mimic function pointers by one-method-interfaces, and events can be simulated by likewise means), sprinkling a little bit of syntactical sugar and equally important metadata on top provides great benefits with regards to code understandability, tooling and runtime metadata inspection features (known as reflection). But this was only the beginning, as the “Cool” (C-style object oriented language) language also embraced and captured common patterns such as iteration (foreach), proper handling of resources (using), resource locking (lock), etc. Nevertheless, there have always been features that are very powerful but shouldn’t be abused or misused, such as operator overloading, unsafe code, … And of course, the language doesn’t expose all of the underlying runtime’s features such as – just to name a few, there are many more – tail calls, typed references and arglists (somehow that sounds familiar).

In C# 2.0, generics were introduced, making the “Cup of T” approach for collections (and more) a first-class citizen in the runtime and language, resulting in less errors and various other benefits (performance, richer IntelliSense, etc). At the same time, generics made previous “features” (partially) redundant. To point out one of these cases, refer to section 8.8.4 in the book you’re about to buy, covering the foreach loop. Before we had IEnumerable<T>, foreach had to deal with the non-generic counterpart resulting in quite some interesting complications that have to do with boxing and the use of casts on the iteration variable (as developers typically would like to iterate over the collection using a type more specific than System.Object, but there were no generics to give guarantees about the collection’s element type). This is a sample of where a new feature solves known problems while also opening the gateway to lots of new things that weren’t possible before. One such thing is a generalization of “nullability”, the lack of which has plagued many developers before when dealing with database records where the distinction between value and reference types doesn’t exist typically. Looking at the nullable type feature in C# 2.0, again the common theme of making common tasks easier pops up, while solving subtle shortcomings of previous releases, in this particular case with the unified type system lacking nullability for value types (a more fundamental “issue” that has quite some language impact, e.g. the use of the default keyword when dealing with generics, more cases to consider in the generics constraint mechanism, etc).

Although C# 2.0 was mostly about catching up on original design plans, there was also room for some innovation. I don’t know precisely when the idea about iterators came up, but these were definitely one of the more exotic features in the second release of the language, opening for lots of new possibilities. While standing on the shoulders of giants (in this case generics), newer language features start building again upon these (as you can guess I’m referring to LINQ to Objects, heavily relying on iterators). One especially notable thing about the C# 2.0 release was its dependence on new runtime-level features to support generics (ECMA 335 and TR/89), so there’s no “Lost in translation” C#-2.0-to-1.0 approach possible. And again, the language didn’t expose the underlying empowering runtime mechanism fully, namely with regards to generics variance (ECMA 335 II.9.5).

Our latest release so far, C# 3.0, followed the same principles but was really the first one to innovate or revolutionize the way we develop typical applications, whether it’s in the business domain (first class data querying with LINQ), in a scientific atmosphere (lambda BLOCKED EXPRESSION or to enter the New World of Meta Programming (expression trees). Once more, features from previous releases, such as generics and iterators, become increasingly important to build newer features on. Radically different from C# 1.0 to 2.0, no runtime extensions were needed, allowing for a real “Lost in translation” translation from C# 3.0 onto equivalent C# 2.0 constructs (not saying anything about readability of such a translation’s result though). Again in the realm of simplifying programming, other constructs like auto-implemented properties and local variable type type inference were introduced, giving the language a more dynamic feeling while keeping strong-typing all the way through. Silly complexities to new up objects or collections were eliminated with new initializer syntaxes and specifying functions does no longer require noisy keywords like “delegate” (referring to the use in anonymous methods) thanks to lambda syntax. And while I admit that some of the syntax looks foreign, most of it can be understood straight away (maybe the only exception is the lambda arrow that requires one aha-erlebnis), so readability doesn’t suffer. As usual, features can get abused just like a Swiss knife is a powerful tool but can be used for bad purposes too. Samples include over-use of local variable type inference at the cost of readability, or inappropriate use of extension methods.

 

A changing landscape

Languages (especially general-purpose ones) need to adapt to a changing programming landscape if they want to stay relevant. And while specialized domains hugely benefit from non-general purpose languages (not to use words like DSLs just yet) – and a mixed-language approach to solving problems is entirely possible thanks to the CLS – some concepts that used to be exotic or irrelevant are becoming mainstream for the first time (or again after being doomed dead a while ago). One such first-timer is functional style of programming. I’m deliberately highlighting the word style as I’m not referring to extremist functional programming (lazy evaluation, no side-effects, use of monads) but rather to influences originating from functional languages and all the underlying theory making their way into mainstream languages. C# 2.0 introduced the glue with true closures, C# 3.0 provided easier syntax with lambdas. And those investments have already paid off hugely with the advent of libraries like the Task Parallel Library and various LINQ implementations. In some sense, LINQ’s mission brought more clarity (insider’s joke) to the concurrency domain, almost as a side-effect :-).

Concurrency is huge; Anders called it the elephant in the room in his JAOO talk (actually our hypothetical new version got a name in an interview with Anders on JAOO, I promise you the name won’t be a big surprise…). It has many faces, spreading from one machine to multiple machines, impacting not only the languages but also the way libraries are built and programs are written. Not to talk about tool support, operating system level changes, and the subtle interactions with hypervisor technologies (VM guests that want to benefit from multiple cores, trying not to collide with one another, etc). So there’s lots of work to be done in this domain to shape languages and tackle the beast. It doesn’t come for free though and things will have to give in: shifting from imperative style to a more declarative style, giving up on “mutable data structures everywhere” (notice the placing of the quotes), etc. Essentially sharing knowledge about the problem at hand with the runtime, rather than over-specifying a particular approach to solve the problem.

But there are other things going on as well, more specifically in the camp of dynamic languages and libraries. Call it the Python or Ruby movement if you want. Several years ago it felt as if the importance of dynamic languages was decreasing but several factors have given them a boost once more. First of all there’s the productivity gain by using interactive editors and consoles: fast prototyping, script-driven development, etc. For that same reason, Windows PowerShell has become so popular and all of the benefits from dynamic languages are apparent in PowerShell: interactively investigating the system as you go, scripting support, a rich and extensible type system (ETS, get-member), and more to come with v2.0 (mobile types for remoting to name just one feature). Actually Windows PowerShell proves that reaching out to statically typed libraries from a dynamic world is incredibly easy, and so do F#, IronPython and IronRuby, all bringing the huge .NET Framework libraries in reach within the dynamic world (F# shares some of the dynamic characteristics such as an interactive console, but just has a huge amount of type inferencing that helps to decrease the verbosity of statically typed languages). But what about the reverse operation, calling dynamic libraries from a statically typed world? Why would one want to do such a thing you might wonder? For one, there are huge useful libraries in that camp too, so why should one not be able to reach out to these? But there’s more, with the increasingly popular web/cloud-oriented software approach, code gets surrounded more and more by a dynamic sea: JavaScript, AJAX, REST, etc all have dynamic characteristics while platforms like Silverlight are floating around in that sea, embedded in web pages. Having easy interop facilities between both worlds is therefore becoming increasingly important and relevant. Think of it as reversing the arrow in “talking from DLR to CLR is easy”.

Finally, I’d point out a third source of language potential: the meta-programming paradigm. It’s maybe the least understood and most ill-defined of the three, but domain specific islands within general-purpose environments (not to just say languages) have an enormous potential, if not abused. Environments like PowerShell have first-class support for regular expressions (-match operator), C# 3.0 and VB 9.0 have LINQ, but what about giving developers the means to cook their own DSLs when appropriate? Here we enter the realm of expression, statement and declaration trees (as implemented in the DLR), running compilers as services (CodeDOM and complete-program source compiler invocations – as in ASP.NET code behind – were the first, albeit degenerate and brute force approach, glimpse of this technique; later followed by LambdaExpression.Compile). Fluent interfaces can be seen as the poor man’s DSLs and going beyond that with Internal DSLs is something that might prove useful in the future. Some people have (and still) bet on AOP as the new big paradigm after OO. Well, I’d put more bets on MP if I get to choose. While it’s not incompatible with ideas from OO, it has the potential of adding another dimension to programming. We already have a spatial extent with data-driven (OO) and operation-driven (procedural and functional) decomposition axes; MP could add a dimension to this picture, in the form of specialized problem space islands within a bigger language. Whether or not it’s really orthogonal is a question we’ll leave open for the time being…

Future will tell, and part of that future is coming at PDC 08. Enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

More Posts