Obscure compiler's lambda expression translation

Question

I studied Y Combinator (using C# 5.0) and was quite surprised when this method:

public static  Func<T1, Func<T2, TOut>> Curry<T1, T2, TOut> ( this Func<T1, T2, TOut> f)
{
    return a => b => f(a, b);
}

... was translated by the compiler to this:

public static Func<T1, Func<T2, TOut>> Curry<T1, T2, TOut>(this Func<T1, T2, TOut> f)
{
    first<T1, T2, TOut> local = new first<T1, T2, TOut>();
    local.function = f;
    return new Func<T1, Func<T2, TOut>>(local.Curry);
}

private sealed class first<T1, T2, TOut>
{
    private sealed class second
    {
        public first<T1, T2, TOut> ancestor;
        public T1 firstParameter;
        public TOut Curry(T2 secondParameter)
        {
            return ancestor.function(firstParameter, secondParameter);
        }
    }
    public Func<T1, T2, TOut> function;
    public Func<T2, TOut> Curry(T1 firstParameter)
    {
        second local = new second();
        local.ancestor = this;
        local.firstParameter = firstParameter;
        return new Func<T2, TOut>(local.Curry);
    }
}

So, second class is nested and first class isn't available for garbage collection while we use delegate that references to second.Curry. At the same time all that we need in first class is function. May be we can copy it (delegate) to the second class and then the first class could be collected? Yes, we also should then do second class non-nested but it seems that is ok. As I know delegates are copied "by value" so I can suggest that it is quite slow, but at the same time we copy firstParameter?! So, may be anyone could explain, why the compiler do all this things?) I speak about anything like this:

private sealed class first<T1, T2, TOut>
{
    public Func<T1, T2, TOut> function;
    public Func<T2, TOut> Curry(T1 firstParameter)
    {
        second<T1, T2, TOut> local = new second<T1, T2, TOut>();
        local.function = function;
        local.firstParameter = firstParameter;
        return new Func<T2, TOut>(local.Curry);
    }
}

public sealed class second<T1, T2, TOut>
{
    public T1 firstParameter;
    public Func<T1, T2, TOut> function;
    public TOut Curry(T2 secondParameter)
    {
        return function(firstParameter, secondParameter);
    }
}

Answer 1

The question is difficult to understand. Let me clarify it. Your suggestion is that the compiler could instead generate

public static Func<T1, Func<T2, TOut>> Curry<T1, T2, TOut>(this Func<T1, T2, TOut> f)
{
    first<T1, T2, TOut> local = new first<T1, T2, TOut>();
    local.function = f;
    return new Func<T1, Func<T2, TOut>>(local.Curry);
}
private sealed class first<T1, T2, TOut>
{
    private sealed class second
    {
        //public first<T1, T2, TOut> ancestor;
        public Func<T1, T2, TOut> function;
        public T1 firstParameter;
        public TOut Curry(T2 secondParameter)
        {
            return /*ancestor.*/function(firstParameter, secondParameter);
        }
    }
    // public Func<T1, T2, TOut> function;
    public Func<T2, TOut> Curry(T1 firstParameter)
    {
        second local = new second();
        // local.ancestor = this;
        local.function = function;
        local.firstParameter = firstParameter;
        return new Func<T2, TOut>(local.Curry);
    }
}

Yes?

Your claim is that this is an improvement because of this scenario.

Func<int, int, int> adder = (x, y)=>x+y;
Func<int, Func<int, int>> makeAdder = adder.Curry();
Func<int, int> addFive = makeAdder(5);

• addFive is a delegate of a method on an instance of second
• makeAdder is a delegate of a method on an instance of first
• In the original codegen, second holds on to ancestor, which is that same instance of first

Therefore if we say

makeAdder = null;

then the instance of first cannot be collected. The instance is not reachable via makeAdder anymore, but it is reachable via addFive.

In the proposed codegen, first can be collected in this scenario because the instance is not reachable via addFive.

You are correct that in this particular scenario that optimization would be legal. However it would not in general be legal for the reason that Ben Voigt describes in his answer. If f is mutated inside Curry then local.function has to mutate. But local has no access to an instance of second until the outer delegate is executed.

The C# compiler team could choose to do the optimization you've identified, but the tiny savings has thus far simply not worth the bother.

We were considering for Roslyn making an optimization along the lines that you describe; that is, if the outer variable is known not to mutate then capture its value more aggressively. I do not know whether that optimization made it in to Roslyn or not.

Answer 2

You've used the lambda operator twice, so you will get two anonymous delegates, with captured variables lifted into state types.

The reason that the inner lambda's state type holds the outer lambda's state type by reference is that this is how capturing works in C#: You capture a variable, not its value.

Some other languages (e.g. C++11 lambdas) have alternate syntax to indicate capture by-value vs capture by-reference. C# does not, and simply captures everything by reference. There's not really a good reason to support by-value semantics, because garbage collection avoids the lifetime problems that would exist in C++11 without a capture by-value mode.

---

Could the C# compiler notice that the variable is never written to, and therefore capturing by value is indistinguishable from capturing by reference? Probably, but that's extra logic in the compiler, extra reviews for both the design and the code, extra tests. All for a small, almost trivial improvement in memory footprint and locality. It evidently doesn't meet the cost-benefit bar, which you can find discussed in quite a few of Eric Lippert's blog articles.