8/15/2011 Delegates vs. Function Pointers, Addendum: Multicast Delegates

Until now, I've been focusing on only one of the differences between delegates and function pointers; namely, associated state.
Delegates have one other capability that function pointers do not.  A single function pointer can only point to one function.  .Net, on the other hand, supports multicast delegates – delegates that point to multiple functions.  You can combine two existing delegates using the + operator (or by calling Delegate.Combine) to create a single new delegate instance that points two all of the methods in the original two delegates.  This new delegate stores all of the methods from the original two delegates in a private array of delegates called InvocationList (the delegates in this array are ordinary non-multicast delegates that each only point to a single method). 

Note that delegates, like strings, are immutable.  Adding two delegates together creates a third delegate containing the methods from the first two; the original delegate instances are not affected.  For example, writing delegateField += SomeMethod creates a new delegate instance containing the methods originally in delegateField as well as SomeMethod, then stores this new instance in delegateField.

Similarly, the - operator (or Delegate.Remove) will remove the second operand from the first one (again, returning a new delegate instance).  If the second operand has multiple methods, all of them will be removed from the final delegate.  If some of the methods in the second operand appear multiple times in the original delegate, only the last occurrence of each one will be removed (the one most recently added).  The RemoveAll method will remove all occurrences.  If all of the methods were removed, it will return null; there is no such thing as an empty delegate instance.

Multicast delegates are not intended to be used with delegates that return values.  If you call a non-void delegate that contains multiple methods, it will return the return value of the last method in the delegate.  If you want to see the return values of all of the methods, you’ll need to loop over GetInvocationList() and call each delegate individually.

Multicast delegates also don’t play well with the new covariant and contravariant generic delegates in .Net 4.0.  You cannot combine two delegates unless their types match exactly, including variant generic parameters.

Function pointers cannot easily be combined the way multicast delegates can.  The only way to combine function pointers without cooperation from the code that calls the pointer is to make a function that uses a closure to call all of the function pointers you want to call.

In Javascript, that would look like this:

function combine() {
    var methods = arguments;

    return function() { 
        var retVal;
        for(var i = 0; i < methods.length; i++) 
            retVal = methods[i].apply(this, arguments);
        return retVal;
    };
}

6/19/2011 Delegates vs. Function Pointers, part 4: C# 2.0+

This is part 4 in a series about state and function pointers; part 1 is here.

Last time, we saw that it is possible to pass local state with a delegate in C#.  However, it involves lots of repetitive single-use classes, leading to ugly code.

To alleviate this tedious task, C# 2 supports anonymous methods, which allow you to embed a function inside another function.  This makes my standard example much simpler:

//C# 2.0
int x = 2;
int[] numbers = { 1, 2, 3, 4 };

int[] hugeNumbers = Array.FindAll(
    numbers, 
    delegate(int n) { return n > x; }
);



//C# 3.0
int x = 2;
int[] numbers = { 1, 2, 3, 4 };

IEnumerable<int> hugeNumbers = numbers.Where(n => n > x);

Clearly, this is much simpler than the C# 1.0 version from last time.  However, anonymous methods and lambda expressions are compile-time features; the CLR itself is not aware of them.  How does this code work? How can an anonymous method use a local variable from its parent scope?

This is an example of a closure – a function bundled together with external variables that the function uses.  The C# compiler handles this the same way that I did manually last time in C# 1: it generates a class to hold the function and the variables that it uses, then creates a delegate from the member function in the class.  Thus, the local state is passed as the delegate’s this parameter.

To see how the C# compiler implements closures, I’ll use ILSpy to decompile the more-familiar C# 3 version: (I simplified the compiler-generated names for readability)

[CompilerGenerated]
private sealed class ClosureClass {
    public int x;
    public bool Lambda(int n) {
        return n > this.x;
    }
}
private static void Main() {
    ClosureClass closure = new ClosureClass();
    closure.x = 2;
    int[] numbers = { 1, 2, 3, 4 };
    IEnumerable<int> hugeNumbers = numbers.Where(closure.Lambda);
}

The ClosureClass (which was actually named <>c__DisplayClass1) is equivalent to the GreaterThan class from my previous example.  It holds the local variables used in the lambda expression.  Note that this class replaces the variables – in the original method, instead a local variable named x, the compiler uses the public x field from the ClosureClass.  This means that any changes to the variable affect the lambda expression as well.

The lambda expression is compiled into the Lambda method (which was originally named <Main>b__0).  It uses the same field to access the local variable, sharing state between the original outer function and its lambda expression.

Next time: Javascript

6/14/2011 Open Delegates vs. Closed Delegates

.Net supports two kinds of delegates: Open delegates and closed delegates.

When you create a delegate that points to an instance method, the instance that you created it from is stored in the delegate’s Target property.  This property is passed as the first parameter to the method that the delegate points to.  For instance methods, this is the implicit this parameter; for static methods, it's the method's first parameter.  These are called closed delegates, because they close over the first parameter and bring it into the delegate instance.

It is also possible to create open delegates which do not pass a first parameter.  Open delegates do not use the Target property; instead, all of the target method’s parameters are passed from the delegate’s formal parameter list, including the first parameter.  Therefore, an open delegate pointing to a given method must have one parameter more than a closed delegate pointing to the same method.  Open delegates are usually used to point to static methods.  When you make a delegate pointing to a static method, you (generally) don't want the delegate to hold a first parameter for the method. 

In addition to these two normal cases, it is also possible (in .Net 2.0 and later) to create open delegates for instance methods and to create closed delegates for static methods.  With one exception, C# doesn’t have any syntactical support for these unusual delegates, so they can only be created by calling the CreateDelegate method.

Open delegates by calling the CreateDelegate overload that doesn’t take a target parameter.  Before .Net 2.0, this function could only be called with a static method.   In .Net 2.0, you can call this function with an instance method to create an open delegate.  Such a delegate will call use its first parameter as this instead of its Target field. 

As a concrete example, consider the String.ToUpperInvariant() method.  Ordinarily, this method takes no parameters, and operates on the string it’s called on.  An open delegate pointing to this instance method would take a single string parameter, and call the method on that parameter.

For example:

Func<string> closed = new Func<string>("a".ToUpperInvariant);
Func<string, string> open = (Func<string, string>)
    Delegate.CreateDelegate(
        typeof(Func<string, string>),
        typeof(string).GetMethod("ToUpperInvariant")
    );

closed();     //Returns "A"
open("abc");  //Returns "ABC"

Closed delegates are created by calling the CreateDelegate overload that takes a target parameter.  In .Net 2.0, this can be called with a static method and an instance of that method’s first argument type to create a closed delegate that calls the method with the given target as its first parameter.  Closed delegates curry the first parameter from the target method.  For example:

Func<object, bool> deepThought = (Func<object, bool>)
    Delegate.CreateDelegate(
        typeof(Func<object, bool>),
        2,
        typeof(object).GetMethod("Equals", BindingFlags.Static | BindingFlags.Public)
    );

This code curries the static Object.Equals method to create a delegate that calls Equals with 2 and the delegate’s single parameter).  It’s equivalent to x => Object.Equals(2, x).  Note that since the method is (generally) not a member of the target object’s type, we need to pass an actual MethodInfo instance; a name alone isn’t good enough.

Note that you cannot create a closed delegate from a static method whose first parameter is a value type, because, unlike all instance methods, static delegates that take value types receive their parameters by value, not as a reference.   For more details, see here and here.

C# 3 added limited syntactical support for creating closed delegates.  You can create a delegate from an extension method as if it were an instance method on the type it extends.  For example:

var allNumbers = Enumerable.Range(1, Int32.MaxValue);
Func<int, IEnumerable<int>> countTo = allNumbers.Take;

This code creates an IEnumerable<int> containing all positive integers, then creates a closed delegate that curries this sequence into the static Enumerable.Take<T>(IEnumerable<T>) method.

Except for extension methods, open instance delegates and closed static delegates are rarely used in actual code.  However, it is important to understand how ordinary open and closed delegates work, and where the target object ends up for instance delegates.

6/13/2011 Delegates vs. Function Pointers, part 3: C# 1.0

This is part 3 in a series about state and function pointers; part 1 is here.

Last time, we saw that it is impossible to bundle context along with a function pointer in C.

In C#, it is possible to fully achieve my standard example.  In order to explain how this works behind the scenes, I will limit this post to C# 1.0 and not use a lambda expression.  This also means no LINQ, generics, or extension methods, so I will, once again, need to write the filter method myself.

delegate bool IntFilter(int num);

static ArrayList Filter(IEnumerable source, IntFilter filter) {
    ArrayList retVal = new ArrayList();

    foreach(int i in source)
        if (filter(i))
            retVal.Add(i);
            
    return retVal;
}

class GreaterThan {
    public GreaterThan(int b) {
        this.bound = b;
    }
    int bound;
    public bool Passes(int num) {
        return num > bound;
    }
}

int x = 2;
int[] numbers = { 1, 2, 3, 4 };
Filter(numbers, new IntFilter(new GreaterThan(x).Passes));

Please excuse the ugly code; in order to be true to C# 1.0, I can’t just write an iterator, and I can’t implicitly create the delegate.

This code creates a class called GreaterThan that holds the Passes method and the state used by the method.  I create a delegate to pass to Filter out of the Passes method for an instance of the GreaterThan class from the local variable.

To understand how this works, we need to delve further into delegates.  .Net delegates are more than just type-safe function pointers. Unlike the function pointers we've looked at, delegates include state – the Target property. This property stores the object to pass as the hidden this parameter to the method (It's actually somewhat more complicated than that; I will describe open and closed delegates at a later date).  My example creates a delegate instance in which the Target property points to the GreaterThan instance.  When I call the delegate, the Passes method is called on the correct instance from the Target property, so it can read the bound field.

Next time, we'll see how the C# 2.0+ compilers generate all this boilerplate for you using anonymous methods and lambda expressions.