Proposal: Struct Lambdas

[JosephTremoulet]

Proposal: Struct Lambdas

It would be useful to have a syntax and library support to create and invoke lambda "delegates" without needing heap allocations for their closures/environments. It would also often be useful to statically parameterize code on some "delegate"/action such that the code is specialized for different inputs, each specialization having a direct inlinable call rather than an indirection through a delegate.

This proposal outlines some new library types, parallel to but distinct from delegates, that would have both of these characteristics, and a syntax to allow lambda expressions to be used to create these "value funcs", parallel to the current support for using lambda expressions to create Delegate and Expression objects.

Assumptions

Avoiding heap allocations for lambdas would require the compiler to generate value types for such lambdas' closures, and the value types thus-generated would need to implement a common interface (per signature) to be invokable. This, in turn, means that functions taking these struct lambdas as parameters would be generic over the struct type. A consequence of being generic over structs is that callsites where these lambdas get invoked would be direct, inlinable calls, without the overhead of the run-time indirection that delegates use (at the expense of generating separate code for each instantiation of their callers); it's because of this dependence that these orthogonal concerns (heap allocation and indirect calling) get intertwined in this proposal.

Exposing these struct lambda values to the source code in a way that would allow them to be copied would break the capture-by-reference semantics of C# closures, so they must be wrapped in some abstraction that precludes copying. Since the goal is to avoid requiring heap allocations for closures, the abstraction likewise shouldn't live in the heap, so it should be a value type. To separate copying the abstraction from copying the closure, the abstraction should reference the closure via an indirection. The obvious solution is to encapsulate the closures by wrapping references to them in a byref-like struct type that exposes a way to invoke them but not a way to copy them; source code would deal with this byref-like wrapper rather than the underlying "value funcs" directly.

The restrictions on byref-like types give exactly the assurances we need to prevent references escaping, so exposing them via byref-likes makes it safe to allocate the "value funcs" themselves on the stack. The ref struct proposal describes these restrictions. My understanding is that the proposal as currently written is slightly out-of-date, and that, on one hand, the current design actually precludes creating a byref-like which holds a reference to a stack local, but that, on the other hand, the possibility is still on the table that support for this will be added, with probably some special well-known type that is allowed to wrap a reference to a local (but not subsequently allowed to be returned), which would be created by some special syntax. This proposal depends on all that, and for the sake of discussion I'm going to assume a special type called WrappedReference<T>, with property ref T Value { get {...} }, which can be constructed with a special wrap syntax; e.g. that, given local int x, the expression wrap(ref x) would create a WrappedReference<int> that holds the address of x.

Library Support: New Types

Here's a sketch of what the library types could look like that would support using this abstraction. Shown here are just the variants for methods that take one argument and return a value (corresponding to Func`2), but we'd need similar types corresponding to each Func and Action type.

// Interface that lambdas with this signature will implement
public interface IFunc<T, TResult>
{
    TResult Invoke(T arg);
}

// Struct that itself isn't ever instantiated, but serves as a conceptual
// container for references to value funcs with this signature.
public struct ValueFunc<TArg, TResult>
{
    // Byref-like type that encapsulates a reference to a value func.
    // The type parameter TLambda will be instantiated to a compiler-generated
    // type specific to the individual lambda when one of these is constructed.
    public ref struct Reference<TLambda>  // Conceptually where TLambda : IFunc<TArg, TResult>
    {
        // Reference to the lambda itself
        WrappedReference<TLambda> lambda;

        // Exposed operation: inoke the lambda
        public TResult Invoke(TArg arg)
        {
            // The C# for this would be simply
            //    return lambda.Value.Invoke(arg);
            // But we can't express this in C# without actually specifying the
            // generic constraint on TLambda, and that would require propagating
            // the constraint's specification up through all code using this type.
            // With some magic in the core library, however, we could give this
            // method the following unverifiable IL which would correctly JIT
            // to a direct call to the lambda method:
            //
            //   ldarg.0
            //   ldflda valuetype WrappedRefrence`1<!TResult> valuetype ValueFunc`2/Reference`1<!TArg, !TResult, !TLambda>::lambda
            //   call instance !TResult& valuetype WrappedReference`1<!TLambda>::get_Value()
            //   ldarg.1
            //   constrained. !TLambda   // <--- here's the unsafe bit
            //   callvirt instance !TResult class IFunc`2<!TArg, !TResult>::Invoke(!TArg)
            //   ret
            //
            // Note that the generic constraint *is* specified on the factory
            // method below that is the only publicly accessible way to create
            // a ValueFunc<...>.Reference<TLambda> (other than a default one
            // with null lambda reference), so this unverifiable code is
            // dynamically safe.
        }

        // Constructor is internal; only called by factory method on parent type.
        internal Reference(WrappedReference<TLambda> reference)
        {
            lambda = reference;
        }
    }

    // Factory method for creating a Reference to a specific Lambda
    public static Reference<TLambda> CreateReference<TLambda>(WrappedReference<TLambda> lambda) where TLambda : IFunc<TArg, TResult>
    {
        return new Reference<TLambda>(lambda);
    }
}

Syntax

Two rules would govern the syntax for creating value funcs:

1. An expression struct <lambda-expr> (i.e. the keyword struct followed by a lambda expression) would create a "Value Func". The naming and syntax here are intentionally chosen to parallel the naming of ValueTuple and its syntax in F#, where struct <tuple-expr> creates a ValueTuple.
2. The only legal operation on a "Value Func" is to capture a reference to it, using the ref keyword. The captured reference is of type ValueFunc<...>.Reference<TLambda> or ValueAction<...>.Reference<TLambda>, where ... matches the signature of the lambda, and TLambda is a compiler-generated type specific to this lambda expression, which implements IFunc<...>/IAction<...>.

So, for example,

  // Define variable `isEven`, with type `ValueFunc<int, bool>.Reference<TLambda>` for some compiler-generated `TLambda`
  var isEven = ref struct (int i) => i % 2 == 0;
  // `isEven` is a regular variable, invoking its methods uses normal method call syntax:
  bool tenIsEven = isEven.Invoke(10); // `tenIsEven` gets value `true`.

Code taking a reference to a value func as a parameter would be generic in the lambda type:

  // Method that prints array elements matching a predicate
  void PrintSome<TPredImpl>(int[] ints, ValueFunc<int, bool>.Reference<TPredImpl> predicate)
  {
      foreach (int i in ints)
      {
          if (predicate.Invoke(i))
          {
              Console.WriteLine(i);
          }
      }
  }

  // prints "2" and "4" (using `isEven` as defined in the previous example)
  PrintSome(new int[]{1, 2, 3, 4, 5}, isEven);

Implementation Considerations

This section is effectively a series of thought experiments regarding how this construct could be implemented and how multiple lambdas could coexist in the same method.

Initial Example

For a point of comparison, consider this code using a lambda passed as a delegate:

// What source code looks like today for simple example with a lambda passed as delegate.
static class SourceToday
{
    // Method that takes a delegate
    public static int SumSome(int[] list, Func<int, bool> predicate)
    {
        int result = 0;

        foreach (int i in list)
        {
            if (predicate(i))
            {
                result += i;
            }
        }

        return result;
    }

    // Method that passes a delegate lambda to a callee
    public static int SumAbove(int[] ints, int n)
    {
        Func<int, bool> aboveN = (int i) => i > n;
        int sum = SumSome(ints, aboveN);
        return sum + n;
    }
}

The C# compiler translates that into something roughly like so:

// Roughly what the C# front-end translates "SourceToday" into
static class TransformedToday
{
    class DisplayClass
    {
        public int n;
        public bool TheLambdaFunc(int i) => i > n;
    }

    // This method is unchanged from the source version
    public static int SumSome(int[] list, Func<int, bool> predicate) => SourceToday.SumSome(list, predicate);

    // Method that passes a delegate lambda to a callee
    public static int SumAbove(int[] ints, int n)
    {
        // Allocation of display class gets inserted.
        DisplayClass display = new DisplayClass();
        display.n = n;

        // Lambda expr becomes call to delegate ctor.
        Func<int, bool> aboveN = new Func<int, bool>(display.TheLambdaFunc);

        int sum = SumSome(ints, aboveN);

        // Reference to 'n' gets rewritten to reflect its location in display.
        return sum + display.n;
    }
}

Using a Value Func instead of a delegate, the source would look like this:

// What source code would look like using value func instead of delegate
static class SourceWithValueFunc
{
    // Method that used to take a delegate:
    //    public static int SumSome(int[] list, Func<int, bool> predicate)
    // Now takes a value func and is generic over impl type instead:
    public static int SumSome<TPredImpl>(int[] list, ValueFunc<int, bool>.Reference<TPredImpl> predicate)
    {
        int result = 0;

        foreach (int i in list)
        {
            // Delegate invocation becomes direct method call to ValueFunc<...>.Reference<TPredImpl>.Invoke method,
            // and ValueFunc<...>.Reference<TPredImpl>.Invoke method body is an interface call which will get
            // resolved to a direct method call when jitting since TPredImpl is a struct type.
            //   if (predicate(i))
            if (predicate.Invoke(i))
            {
                result += i;
            }
        }

        return result;
    }

    // Method that passes a lambda uses
    //    var foo = ref struct <lambda-expr>
    // instead of
    //    Func<...> foo = <lambda-expr>
    public static int SumAbove(int[] ints, int n)
    {
        var aboveN = ref struct (int i) => i > n;
        int sum = SumSome(ints, aboveN);
        return sum + n;
    }
}

The transformation would be similar. It would use a display struct rather than a display class, which would have all the same data members for captured state, and which would implement the appropriate IFunc interface:

// Sketch of what source using value func could be transformed into
static class TransformedWithValueFunc
{
    // Display has same fields as display class in TransformedToday, but is a struct.
    struct DisplayStruct
    {
        public int n;
    }

    // Each lambda gets a corresponding struct type with Invoke method generated by the compiler.
    struct AboveNLambda : IFunc<int, bool>
    {
        // Lambda contains state wrapped in display struct.
        public DisplayStruct display;

        public bool Invoke(int i) => i > display.n;
    }

    // Method that takes a value func parameter is unchanged from source.
    public static int SumSome<TPredImpl>(int[] list, ValueFunc<int, bool>.Reference<TPredImpl> predicate) => SourceWithValueFunc.SumSome(list, predicate);

    // Method that passes a value func
    public static int SumAbove(int[] ints, int n)
    {
        // Closures and display get created as structs.
        AboveNLambda _aboveNLambda = new AboveNLambda() { display = new DisplayStruct() };
        ref DisplayStruct display = ref _aboveNLambda.display;
        display.n = n;

        // Lambda expr becomes call to ValueFunc<...>.Reference factory method
        var aboveN = ValueFunc<int, bool>.CreateReference(wrap(ref _aboveNLambda));

        int sum = SumSome(ints, aboveN);

        // Reference to 'n' gets rewritten to reflect its location in display.
        return sum + display.n;
    }
}

Mutiple Struct Lambdas in the Same Method

Display classes are shared across multiple lambdas in the same function. Given source like this:

// Source code with multiple delegate lambdas in one function
static class SourceToday
{
    // Method that takes a delegate (same as previous example)
    public static int SumSome(int[] list, Func<int, bool> predicate) { ... }

    // Method that takes a delegate with a different signature.
    public static int SumMap(int[] list, Func<int, int> f)
    {
        int result = 0;

        foreach (int i in list)
        {
            result += f(i);
        }

        return result;
    }

    // Method that passes various delegate lambdas to callees
    public static int SumAbovePlusKAndBetween(int[] ints, int lo, int hi, int k)
    {
        Func<int, bool> above = (int i) => i > lo;
        Func<int, int> addK = (int i) => i + k;
        Func<int, bool> between = (int i) => lo < i && i < hi;

        int result = SumSome(ints, above) + SumMap(ints, addK) + SumSome(ints, between);
        return result + lo + hi + k;
    }
}

the C# compiler generates something roughly like this:

// Roughly what the C# front-end translates "SourceToday" into
static class TransformedToday
{
    class DisplayClass
    {
        // Captured state
        public int lo;
        public int hi;
        public int k;

        // Methods
        public bool AboveFunc(int i) => i > lo;
        public int AddKFunc(int i) => i + k;
        public bool BetweenFunc(int i) => lo < i && i < hi;
    }

    // These methods are unchanged from the versions in SourceToday
    public static int SumSome(int[] list, Func<int, bool> predicate) => SourceToday.SumSome(list, predicate);
    public static int SumMap(int[] list, Func<int, int> f) => SourceToday.SumMap(list, f);

    // Method that passes various delegate lambdas to callees
    public static int SumAbovePlusKAndBetween(int[] ints, int lo, int hi, int k)
    {
        // Allocation of display class gets inserted.
        DisplayClass display = new DisplayClass();
        display.lo = lo;
        display.hi = hi;
        display.k = k;

        // Lambda exprs become calls to delegate ctors.
        Func<int, bool> above = new Func<int, bool>(display.AboveFunc);
        Func<int, int> addK = new Func<int, int>(display.AddKFunc);
        Func<int, bool> between = new Func<int, bool>(display.BetweenFunc);

        int result = SumSome(ints, above) + SumMap(ints, addK) + SumSome(ints, between);

        // References to captured locals get rewritten to reflect their location in display.
        return result + display.lo + display.hi + display.k;
    }
}

The display class simply has three methods (one for each lambda). For value funcs, we can't just make the DisplayStruct type implement an interface for each lambda, since some of them have the same signature. But we can arbitrarily order the lambdas, and nest the structs inside each other. I.e., given the corresponding source using value funcs:

// Source code with multiple value func lambdas in one function
static class SourceWithValueFunc
{
    // Method that used to take a delegate:
    //    public static int SumSome(int[] list, Func<int, bool> predicate)
    // Now takes a value func and is generic over impl type instead (same as previous example):
    public static int SumSome<TPredImpl>(int[] list, ValueFunc<int, bool>.Reference<TPredImpl> predicate) { ... }

    // Other method that used to take a delegate:
    //    public static int SumMap(int[] list, Func<int, int> f)
    // Now takes a value func and is generic over impl type instead:
    public static int SumMap<TFImpl>(int[] list, ValueFunc<int, int>.Reference<TFImpl> f)
    {
        int result = 0;

        foreach (int i in list)
        {
            // delegate invocation f(i) becomes method call f.Invoke(i)
            result += f.Invoke(i);
        }

        return result;
    }


    // Method that passes various value func lambdas to callees, uses
    //    var foo = ref struct <lambda-expr>
    // instead of
    //    Func<...> foo = <lambda-expr>
    public static int SumAbovePlusKAndBetween(int[] ints, int lo, int hi, int k)
    {
        var above = ref struct (int i) => i > lo;
        var addK = ref struct (int i) => i + k;
        var between = ref struct (int i) => lo < i && i < hi;

        int result = SumSome(ints, above) + SumMap(ints, addK) + SumSome(ints, between);
        return result + lo + hi + k;
    }
}

The C# compiler could generate something like the following:

// Sketch of what source using value func could be transformed into
static class TransformedWithValueFunc
{
    // Display has same fields, but is a struct.
    struct DisplayStruct
    {
        public int lo;
        public int hi;
        public int k;
    }

    // Each lambda gets a corresponding struct type with Invoke method generated by the compiler.
    // Lambda struct types contain state wrapped in the display struct.
    // Multiple lambdas with shared state nest inside each other.
    struct AboveLambda : IFunc<int, bool>
    {
        public DisplayStruct display;

        public bool Invoke(int i) => i > display.lo;
    }
    struct AddKLambda : IFunc<int, int>
    {
        public AboveLambda aboveLambda;

        public int Invoke(int i)
        {
            ref DisplayStruct display = ref aboveLambda.display;

            return i + display.k;
        }
    }
    struct BetweenLambda : IFunc<int, bool>
    {
        public AddKLambda addKLambda;

        public bool Invoke(int i)
        {
            ref DisplayStruct display = ref addKLambda.aboveLambda.display;

            return (display.lo < i && i < display.hi);
        }
    }

    // Methods that take value func parameters are unchanged from source.
    public static int SumSome<TPredImpl>(int[] list, ValueFunc<int, bool>.Reference<TPredImpl> predicate) => SourceWithValueFunc.SumSome(list, predicate);
    public static int SumMap<TFImpl>(int[] list, ValueFunc<int, int>.Reference<TFImpl> f) => SourceWithValueFunc.SumMap(list, f);

    // Method that passes various value func lambdas to callees
    public static int SumAbovePlusKAndBetween(int[] ints, int lo, int hi, int k)
    {
        // Closures and display get created as structs.
        var _betweenLambda = new BetweenLambda() { addKLambda = new AddKLambda() { aboveLambda = new AboveLambda() { display = new DisplayStruct() } } };
        ref AddKLambda _addKLambda = ref _betweenLambda.addKLambda;
        ref AboveLambda _aboveLambda = ref _addKLambda.aboveLambda;
        ref DisplayStruct display = ref _aboveLambda.display;
        display.lo = lo;
        display.hi = hi;
        display.k = k;

        // Lambda exprs become calls to ValueFunc<...>.Reference factory methods
        var above = ValueFunc<int, bool>.CreateReference(wrap(ref _aboveLambda));
        var addK = ValueFunc<int, int>.CreateReference(wrap(ref _addKLambda));
        var between = ValueFunc<int, bool>.CreateReference(wrap(ref _betweenLambda));

        int result = SumSome(ints, above) + SumMap(ints, addK) + SumSome(ints, between);

        // References to captured locals get rewritten to reflect their location in display.
        return result + display.lo + display.hi + display.k;
    }
}

Methods with Value Func Lambdas and Delegate Lambdas Together

Lambdas of different kinds might capture the same variables. Since capture is by-reference, any such variables need to be allocated in a display that the different lambda kinds can both reference. Consider this example, similar to the previous one except that addHi is a delegate lambda (and can't be a value func lambda, since it gets passed to StashAway, from which the delegate escapes) and the other two are value func lambdas:

// Source code with delegate lambda and value func lambdas in the same method
static class SourceWithMixedLambdas
{
    // Method that takes a value func and is generic over impl type (same as previous example):
    public static int SumSome<TPredImpl>(int[] list, ValueFunc<int, bool>.Reference<TPredImpl> predicate) { ... }

    // Method with a delegate parameter that escapes.
    public static void StashAway(Func<int, int> f) { stash = f; }
    volatile static Func<int, int> stash;

    // Method that passes both delegate lambda and value func lambdas to callees
    public static int SumAboveAndBetween(int[] ints, int lo, int hi)
    {
        var above = ref struct (int i) => i > lo;
        Func<int, int> addHi = (int i) => i + hi;
        var between = ref struct (int i) => lo < i && i < hi;

        int result = SumSome(ints, above);
        StashAway(addHi);
        result += SumSome(ints, between);

        return result + lo + hi;
    }
}

The value func lambda types are struct types to allow them to be allocated on the stack, but nothing precludes them being allocated in the heap. Therefore, in mixed cases like this, we can create an outermost display class for any delegate lambdas, with a field which holds the display structs for any value func lambdas, like so:

// Sketch of what source using mixed lambdas could be transformed into
static class TransformedWithMixedLambdas
{
    // Display has captured variables as fields, like previous examples.
    struct DisplayStruct
    {
        public int lo;
        public int hi;
    }

    // Each value func lambda gets a corresponding struct type with Invoke method generated by the compiler.
    // Lambda struct types contain state wrapped in the display struct.
    // Multiple lambdas with shared state nest inside each other.
    struct AboveLambda : IFunc<int, bool>
    {
        public DisplayStruct display;

        public bool Invoke(int i) => i > display.lo;
    }
    // AddHi is not in the chain of struct types, since it needs to
    // become a Func<int, int>, not a T : IFunc<int, int> -- skip
    // straight from Above to Between in the struct types
    struct BetweenLambda : IFunc<int, bool>
    {
        public AboveLambda aboveLambda;

        public bool Invoke(int i)
        {
            ref DisplayStruct display = ref aboveLambda.display;

            return (display.lo < i && i < display.hi);
        }
    }
    // After generating all the struct types, generate a final
    // class type that will hold the delegate lambda(s) (in this
    // case, AddHi is the only delegate lambda).
    class DisplayClass
    {
        // Captured state embedded in struct lambdas
        public BetweenLambda betweenLambda;

        // Methods
        public int AddHiFunc(int i)
        {
            ref DisplayStruct display = ref betweenLambda.aboveLambda.display;

            return i + display.hi;
        }
    }

    // Methods that take delegate and value func parameters are unchanged from source.
    public static int SumSome<TPredImpl>(int[] list, ValueFunc<int, bool>.Reference<TPredImpl> predicate) => SourceWithMixedLambdas.SumSome(list, predicate);
    public static void StashAway(Func<int, int> f) => SourceWithMixedLambdas.StashAway(f);

    // Method that passes both delegate lambda and value func lambdas to callees
    public static int SumAboveAndBetween(int[] ints, int lo, int hi)
    {
        // Closures and display get created in the heap.
        DisplayClass closures = new DisplayClass() { betweenLambda = new BetweenLambda() { aboveLambda = new AboveLambda() { display = new DisplayStruct() } } };
        ref BetweenLambda _betweenLambda = ref closures.betweenLambda;
        ref AboveLambda _aboveLambda = ref _betweenLambda.aboveLambda;
        ref DisplayStruct display = ref _aboveLambda.display;
        display.lo = lo;
        display.hi = hi;

        // Delegate lambda exprs become calls to delegate ctors.
        // Value func lambda exprs become calls to ValueFunc<...>.Reference factory methods
        var above = ValueFunc<int, bool>.CreateReference(wrap(ref _aboveLambda));
        Func<int, int> addHi = new Func<int, int>(closures.AddHiFunc);
        var between = ValueFunc<int, bool>.CreateReference(wrap(ref _betweenLambda));

        int result = SumSome(ints, above);
        StashAway(addHi);
        result += SumSome(ints, between);

        // References to captured locals get rewritten to reflect their location in display.
        return result + display.lo + display.hi;
    }
}

Nested Scopes

The preceding examples all capture variables in the root scope of their method. When variables from different scopes are captured by delegate lambdas, the different scopes need different display classes, and child scope display classes need pointers to their parent scope display classes, in order to preserve capture-by-reference semantics in the face of lambdas escaping the captured variables' scopes. This example demonstrates:

public class NestedScopesWithDelegateLambdas
{
    public static void CreateNestedDisplays()
    {
        var funcs = new List<Func<int>>();

        int sharedValue = 1;

        for (int i = 0; i < 10; ++i)
        {
            int independentValue = i;

            // Each loop iteration creates a lambda.  All lambdas must refer to the same
            // 'sharedValue' since it is captured by reference from the outer scope.
            // Each lambda must refer to its own 'independentValue' since it is captured
            // from the inner scope.
            Func<int> func = () => sharedValue + independentValue;

            // This will use the current values of 'sharedValue' and 'independentValue'.
            UseLatestFunc(func);

            // Modify sharedValue on each loop iteration.  Subsequent calls to this 'func'
            // will see the new value of 'sharedValue'.
            sharedValue *= 2;

            // This is how the lambdas capturing 'independentValue' escape its scope.
            funcs.Add(func);
        }

        // This will invoke each func; they must see the same, final value of 'sharedValue'
        // but use their independent values of 'independentValue'
        UseAllFuncs(funcs);
    }

    public static void UseLatestFunc(Func<int> func) => Console.WriteLine($"Value: {func()}");
    public static void UseAllFuncs(List<Func<int>> funcs)
    {
        foreach (var func in funcs)
        {
            Console.WriteLine($"Value: {func()}");
        }
    }
}

Accordingly, when the C# compiler processes the method above, it creates display classes with the parent/child structure like so:

class OuterScopeDisplay
{
    public int sharedValue;
}

class InnerScopeDisplay
{
    OuterScopeDisplay parent;
    int independentValue;

    int LambdaFunc() => parent.sharedValue + independentValue;
}

An instance of each display class is created on each entry to its scope.

Value func lambdas would require different treatment. If the parent display is a struct, including a reference to it in the child display would be illegal, since then the child display would need to be a byref-like and so couldn't be used as the type argument to LocalFunc<...>.Reference<TLambda>. Including the parent display by value in the child display, on the other hand, would break the capture-by-reference semantics of sibling children sharing the same parent (at least without inserting potentially lots of copying at scope transitions). Fortunately, since value funcs would be exposed to the source only via byref-like references, and the rules for byref-likes preclude escaping their scope, value funcs can only reference captured variables from the current iteration of their scope. This means that the backing storage can be shared across different iterations of a their declaration scope, and thus we can turn things on their head and include the child scope by value in its parent scope (with sibling scopes' displays being included as sibling fields in the parent). Updating the nested scope example to use value funcs, but removing the operations that are illegal on byref-like types, it looks like this:

public class NestedScopesWithValueFuncLambdas
{
    public static void CreateNestedDisplays()
    {
        // This part has to be removed; ValueFunc<...>.Reference<...> is a byref-like
        // type, so it's impossible to instantiate List<ValueFunc<...>.Reference<...>>.
        //    var funcs = new List<ValueFunc<int>.Reference<???>>();

        int sharedValue = 1;

        for (int i = 0; i < 10; ++i)
        {
            int independentValue = i;

            // Each loop iteration creates a lambda.  All lambdas must refer to the same
            // 'sharedValue' since it is captured by reference from the outer scope.
            // Each lambda may refer to the same 'independentValue' since they can only
            // use its value from the current iteration.
            var func = ref struct () => sharedValue + independentValue;

            // This will use the current values of 'sharedValue' and 'independentValue'.
            UseLatestFunc(func);

            // Modify sharedValue on each loop iteration.  Subsequent calls to this 'func'
            // can't happen, since it's about to go out of scope.  Calls to the 'func'
            // created on subsequent iterations will see the new value of 'sharedValue'.
            sharedValue *= 2;

            // This part also has to be removed (no way to copy a byref-like into anything
            // that outlives its scope).
            //   funcs.Add(func);
        }

        // This part also has to be removed; there's no way to use a byref-like from outside
        // its scope.
        //   UseAllFuncs(funcs);
    }

    public static void UseLatestFunc<TFuncImpl>(ValueFunc<int>.Reference<TFuncImpl> func) => Console.WriteLine($"Value: {func.Invoke()}");

    // This, too, has to be removed, since it attempts to use byref-like ValueFunc<int>.Reference<...> as a type argument:
    //   public static void UseAllFuncs<TFuncImpl>(List<ValueFunc<int>.Reference<TFuncImpl>> funcs) { ... }
}

Since the backing storage for subsequent child iterations can be re-used, the compiler could translate this to something like the following:

public class TransformedNestedScopesWithValueFuncLambdas
{
    // Display has captured variables as fields, like previous examples.
    struct DisplayStruct_ChildScope
    {
        // Captured variable(s) at current scope
        public int independentValue;
    }

    // Parent scope's display struct contains child scope's display struct,
    // as well as parent-scoped captured variables.
    struct DisplayStruct_RootScope
    {
        // Captured variable(s) at current scope
        public int sharedValue;

        // Child scope(s)
        public DisplayStruct_ChildScope childDisplay;
    }

    // Each value func lambda gets a corresponding struct type generated by the compiler.
    // These wrap the entire display struct, even when the value func is declared in a child
    // scope, so that the Invoke method will have access to captured state from all enclosing
    // scopes.
    struct ChildScope_FuncLambda : IFunc<int>
    {
        public DisplayStruct_RootScope rootDisplay;

        public int Invoke()
        {
            ref DisplayStruct_ChildScope childDisplay = ref rootDisplay.childDisplay;

            return rootDisplay.sharedValue + childDisplay.independentValue;
        }
    }

    public static void CreateNestedDisplays()
    {
        // Closures and display structs get created in outer scope.
        var childScope_funcLambda = new ChildScope_FuncLambda() { rootDisplay = new DisplayStruct_RootScope() };
        ref DisplayStruct_RootScope rootDisplay = ref childScope_funcLambda.rootDisplay;

        // References to captured variables are updated to reflect their location in their display.
        rootDisplay.sharedValue = 1;

        for (int i = 0; i < 10; ++i)
        {
            // Inner scope display structs are located in their parent displays.
            ref DisplayStruct_ChildScope childDisplay = ref rootDisplay.childDisplay;

            // We could explicitly (re-)initialize child display on entry to its scope, or (maybe?)
            // just rely on definite assignment rules.
            childDisplay = new DisplayStruct_ChildScope();

            // References to captured variables are updated to reflect their location in their display.
            childDisplay.independentValue = i;

            // Value func lambda expressions become calls to ValueFunc<...>.Reference<> factory method
            var func = ValueFunc<int>.CreateReference(wrap(ref childScope_funcLambda));

            // This will use the current values of 'sharedValue' and 'independentValue'.
            UseLatestFunc(func);

            // References to captured variables are updated to reflect their location in their display.
            rootDisplay.sharedValue *= 2;
        }
    }

    // Method that takes a value func parameter is unchanged from source
    public static void UseLatestFunc<TFuncImpl>(ValueFunc<int>.Reference<TFuncImpl> func) => NestedScopesWithValueFuncLambdas.UseLatestFunc(func);
}

Putting these together, trees of mixed lambda types could be constructed according to the following rules:

1. A scope with captured variables may have a display struct created for it (if any of its captured variables are referenced in a value func lambda), or have a display class created for it (if any of its captured variables are referenced in a delegate/expression lambda), or both.
2. A non-root scope which has a display struct but no display class, if it has a parent scope, will be allocated as a field of the parent display struct.
3. Each delegate lambda's body will become a method on the associated display class.
4. Each value func lambda's body will become the Invoke method of a lambda struct type generated for it. These lambda structs will appear as fields of display classes (or other lambda structs) only, never as fields of display structs; the innermost display class enclosing some value func's scope will contain the lambda struct as a field, and the lambda struct will in turn contain the outermost display struct of that display class as a field. When there are multiple such lambdas in the same display class, they will be nested within each other. This ensures that each lambda func has access to any parent scopes whose captured variables it references.
5. Non-root display classes, and the display structs nested inside them, may need pointers to the next-outer display class, to reference captured variables from outer scopes. This pointer will live in the outermost display struct within the display class.

So, for example, with a tree of scopes/variables/lambdas like this:

public void MixedNestedScopes()
{ // root scope
    int var_root;

    { // scope X1
        int var_X1;
        var vf_X1 = ref struct () => var_X1;
        { // scope X2
            int var_X2;
            var vf_X2 = ref struct () => var_X2 + var_X1 + var_root;
            { // scope X3
                int var_X3;
                { // scope X4
                    int var_X4;
                    Func<int> del_X4 = () => var_X4 + var_X3 + var_root;
                }

            }
        }
    }

    { // scope Y1
        int var_Y1;
        Func<int> del_Y1 = () => var_Y1;

        { // scope Y2
            int var_Y2;
            var vf_Y2 = ref struct () => var_Y2 + var_Y1 + var_root;
        }
    }
}

we could generate display classes/structs like this:

// scope X2 needs a DisplayStruct since var_X2 is captured by vf_X2
struct X2_DisplayStruct
{
    // Captured var(s)
    public int var_X2;

    // No children.
}
// scope X1 needs a DisplayStruct since var_X1 is captured by vf_X1 and vf_X2
struct X1_DisplayStruct
{
    // Captured var(s)
    public int var_X1;

    // Child scope X2 has a display struct but not a display
    // class, so it is included as a field of X1 display struct
    public X2_DisplayStruct X2_display;
}
// root scope needs a DisplayStruct since var_root is captured
// by vf_X2
struct root_DisplayStruct
{
    // Captured var(s)
    public int var_root;

    // Child scope X1 has a display struct but not a display
    // class, so it is included as a field of root display struct.
    public X1_DisplayStruct X1_display;
}

// X2 has a display struct but not a display class.
// X2's parent X1 has a display struct but not a display class.
// X1's parent, the root scope, has a display struct and a display class.
// Therefore, the root scope, X1, and X2 become a group.  Their display
// structs include each other by value (outer to inner), and their lambda
// structs get sandwiched between the root display class and the root
// display struct.
// The relative ordering of their lambda structs is arbitrary; in this
// example, vf_X2's lambda is inside vf_X1's lambda.

// value func vf_X2 gets a lambda because it is a value func lambda
struct vf_X2_Lambda : IFunc<int>
{
    // No more inner lambdas, so wrap the display struct for X2's display
    // struct group, which is the root display struct.
    public root_DisplayStruct root_display;

    public int Invoke()
    {
        ref X1_DisplayStruct X1_display = ref root_display.X1_display;
        ref X2_DisplayStruct X2_display = ref X1_display.X2_display;

        return X2_display.var_X2 + X1_display.var_X1 + root_display.var_root;
    }
}
// value fund vf_X1 gets a lambda because it is a value func lambda
struct vf_X1_Lambda : IFunc<int>
{
    // This value func lambda struct type wraps the next-inner one
    public vf_X2_Lambda vf_X2_lambda;

    public int Invoke()
    {
        ref root_DisplayStruct root_display = ref vf_X2_lambda.root_display;
        ref X1_DisplayStruct X1_display = ref root_display.X1_display;

        return X1_display.var_X1;
    }
}
// root scope needs a DisplayClass since var_root is captured
// by del_X4 and del_Y1
class root_DisplayClass
{
    // Since root scope needs both a display class and a display struct,
    // the struct gets wrapped in any lambdas in this group, and the
    // outermost lambda, which in this case is vf_X1's lambda.
    public vf_X1_Lambda vf_X1_lambda;
}

// scope X3 needs a display class because var_X3 is captured by del_X4.
class X3_DisplayClass
{
    // X3 does not need a display struct, so the captured variable can
    // be included directly as a field of the display class.
    public int var_X3;

    // Non-root display classes need pointers to their parent display classes.
    // Just like the field for the captured variable, the field for the parent
    // display class would be in this scope's display struct if it had one, but
    // since X3 doesn't need a display struct, we can put the pointer to its
    // parent display class directly in this display class.
    // Note that the parent display *class* is the root scope's display class,
    // since the intervening scopes have display structs but not display classes.
    public root_DisplayClass rootDisplayClass;

    // No delegate lambdas at this level (just the inner delegate lambda del_X4),
    // so no methods on this class.
}

// scope X4 needs a display class because var_X4 is captured by del_X4.
class X4_DisplayClass
{
    // X4 does not need a display struct, so the captured variable can
    // be included directly as a field of the display class.
    public int var_X4;

    // Non-root display classes need pointers to their parent display classes.
    // Just like the field for the captured variable, the field for the parent
    // display class would be in this scope's display struct if it had one, but
    // since X4 doesn't need a display struct, we can put the pointer to its
    // parent display class directly here.
    public X3_DisplayClass X3_display;

    // Display classes get methods for each delegate lambda defined at their scope;
    // in the case of scope X4, there's exactly one: del_X4.
    public int del_X4()
    {
        // Reach up to get the next-outer display class.
        root_DisplayClass rootDisplayClass = X3_display.rootDisplayClass;
        // Then reach down through its lambdas to get its display struct.
        ref root_DisplayStruct root_display = ref rootDisplayClass.vf_X1_lambda.vf_X2_lambda.root_display;

        // Since this is a delegate lambda, the references to captured variables at different scopes
        // should all reside in different objects, which we can see is the case here.
        return this.var_X4 + X3_display.var_X3 + root_display.var_root;
    }
}

// scope Y2 needs a DisplayStruct since var_Y2 is captured by vf_Y2
struct Y2_DisplayStruct
{
    // Captured var(s)
    public int var_Y2;

    // No children
}
// scope Y1 needs a DisplayStruct since var_Y1 is captured by vf_Y2
struct Y1_DisplayStruct
{
    // Captured var(s)
    public int var_Y1;

    // Child scope Y2 has a display struct but not a display
    // class, so it is included as a field of Y1 display struct.
    public Y2_DisplayStruct Y2_display;

    // This is the outermost display struct in this group, but
    // vf_Y2 needs access to the root display struct, which is
    // in a parent display class.  Therefore the link to the
    // parent display class (the one for the root scope) goes
    // here, in the outermost display struct of this group.
    public root_DisplayClass root_displayClass;
}

// Y2 has a display struct but not a display class.
// Y2's parent Y1 has a display struct and a display class.
// Therefore, Y1 and Y2 become a group.  Their display structs
// include each other by value (outer to inner), and their lone
// lambda struct (for vf_Y1) gets sandwiched between the outermost
// display struct (Y2's display struct) and the display class.

// value func vf_Y2 gets a lambda struct type because it is a value func lambda.
struct vf_Y2_Lambda : IFunc<int>
{
    // This is the innermost lambda struct in this group, so include
    // the outermost display struct as a field.
    public Y1_DisplayStruct Y1_display;

    public int Invoke()
    {
        // Y1's display struct is a field.
        // Reach down from it to get Y2's display struct
        ref Y2_DisplayStruct Y2_display = ref Y1_display.Y2_display;
        // Reach up from it to get the next outer display class
        root_DisplayClass root_displayClass = Y1_display.root_displayClass;
        // Then reach down from that through its lambdas to get its
        // display struct.
        ref root_DisplayStruct root_display = ref root_displayClass.vf_X1_lambda.vf_X2_lambda.root_display;

        // Rewrite the lambda body to reference the captured variables in their
        // home displays.
        return Y2_display.var_Y2 + Y1_display.var_Y1 + root_display.var_root;
    }
}
// scope Y1 needs a DisplayClass since var_Y1 is captured by del_Y1
struct Y1_DisplayClass
{
    // The display class includes the lambda struct type(s) which include
    // the display struct(s)
    public vf_Y2_Lambda vf_Y2_lambda;

    // Display classes get methods for each delegate lambda defined at their scope;
    // in this case that's del_Y1
    public int del_Y1()
    {
        ref Y1_DisplayStruct Y1_display = ref vf_Y2_lambda.Y1_display;

        return Y1_display.var_Y1;
    }
}

Delegate -> Value Func Conversions

It should be possible to obtain a ValueFunc<...>.Reference<...> from a corresponding Func<...>. That way, code which is provided a delegate can call a method that takes a value func. Doing this with a helper type that is allocated whenever such a conversion is performed would be very straightforward:

public struct ValueFunc<TArg, TResult>
{
    //... (as before)

    // Auxiliary struct for expressing a delegate as a LocalFunc
    public struct DelegateHelper : IFunc<TArg, TResult>
    {
        internal Func<TArg, TResult> _delegate;
        public TResult Invoke(TArg arg) => _delegate(arg);
    }
    // The helper struct will need a home that outlives the conversion method, so
    // provide a class representing a strongly-typed box (we need the strong typing
    // because we need to take a ref to the struct inside the box).
    class BoxedHelper { internal DelegateHelper helper; }

    // CreateReference overload that takes a delegate
    public static Reference<DelegateHelper> CreateReference(Func<TArg, TResult> func)
    {
        var box = new BoxedHelper() { helper = new DelegateHelper() { _delegate = func } };
        return CreateReference(wrap(ref box.helper));
    }
}

Of course, it would be nice to avoid the allocation; this could be achieved by changing the internal structure of delegates to have instance fields of some struct type that implements IFunc<...>.

Note that, with this conversion available, any code which wants to call a method that takes a value func has the option of using a delegate lambda, like so:

    Func<int, bool> isEven = (int i) => i % 2 == 0;
    PrintSome(ints, ValueFunc<int, bool>.CreateReference(isEven));

Any callsite using a delegate like this would call instantiation PrintSome<ValueFunc<int, bool>.DelegateHelper>. Note that this instantiation is not using any type particular to the lambda in question, so all such callsites would be calling the same instantiation. In this way, delegates could be used in cases where a callee takes a value func, but the allocation and delegate dispatch overheads are not a concern compared to the code bloat of generating multiple instantiations.

Tradeoffs/Limitations

This section discusses some constraints that limit where this construct can be applied, and also compares to other possible changes with overlapping goals.

Type name availability

Given a statement like var isEven = ref struct (int i) => i % 2 == 0;, the type of local variable isEven will be ValueFunc<int, bool>.Reference<???>. The ??? will be the struct type generated by the compiler for the lambda, but its name isn't available as an identifier in the source code. This means that there's no type expression for the type of variable isEven, and when subsquently calling a method like PrintSome(ints, isEven), inference can determine that this is PrintSome<???>(ints, isEven) (with the same type for ???), but there's no way to explicitly name the type argument. Using var for the variables holding local func references and inference for type arguments covers a lot of use cases, but it doesn't cover, e.g., calling a method with multiple type arguments, where one of the arguments can't be deduced. To cover such use cases, we'd need to make other changes, like using a syntax for defining struct lambdas that includes an identifier to be used as the name of the lambda type, or perhaps having a way to explicitly specify some type arguments while flagging others to be inferred...

Byref-like restrictions

The same restrictions on byref-like types that ensure that allocating the lambda and display structs on the stack is safe also limit the situations where byref-like type ValueFunc<...>.Reference<TLambda> can be used. Notably, it can't be stored to the heap (e.g. via boxing or storing to a class field), so it can exist only as a local or as a field of a local which itself has a byref-like struct type. This means that the various Linq extension methods on IEnumerable<T> which take delegates and return enumerables can't be rewritten to take value funcs, since they embed the delegates passed to them in the enumerables that they return (and even trying to create similar methods with struct enumerable/enumerator types would be problematic, since those struct types would have to be byref-like themselves and thus couldn't implement interfaces like IEnumberable<T>).

Code expansion

Methods with value func parameters need corresponding type parameters to be generic in the lambda struct type. This means that separate instantiations will be generated in the jitted native code, since instantiations aren't shared across struct type arguments (at least on .NET Core and .NET Framework). This code growth may be undesirable and degrade performance.

The upshot of the specialization is that the actual calls to the value funcs will be direct and inlineable, without delegate call overhead. Still, for scenarios where direct calling via specialization is a desired goal but stack allocation is not, the specialization could be achieved without incurring the byref-like type limitations, by introducing struct delegate-like types that can be freely copied. Implementing capture-by-value lambdas, for example, could be done in a way that produces struct-typed copyable lambdas. Likewise, this proposal could be adapted to produce copyable struct lambdas at the expense of heap allocations by putting the display state in display classes rather than display structs, and passing around lambda struct types that include an object reference to their display class (though subsequently trying to write code that returns such a struct lambda from a function would hit the type name availability issues in naming the return type).

As noted above, this code bloat can be mitigated somewhat by opting to use delegate lambdas and delegate-to-value-func conversion at callsites where the code growth is a bigger concern than the heap allocations and delegate calls.

Stack expansion

Switching some code from delegate lambdas to value func lambdas would mean moving the backing storage of the display that's currently heap-allocated to the stack, which is a goal because it reduces GC pressure, but involves a tradeoff because it also, of course, increases the required amount of stack space. Since most of the space in a display class/struct is taken up by captured variables which are locals at source, this typically amounts to allocating locals on the stack, which shouldn't be much of a problem since that's typically where locals are allocated. The nested scopes requirement that child display structs be members of their parent display structs, however, specifically in the case of nested value func lambdas, would mean that captured locals of the inner method get allocated on the stack of the parent method. This is a bit odd, but likely often acceptable.

Overlap with automatic stack allocation

It's possible to recognize non-escaping object allocations and use stack space rather than heap allocations for them, as a compiler optimization. There's a partial implementation of this in RyuJIT currently. Completing a robust implementation of this optimization could avoid heap allocations for delegates and closures in many of the scenarios where value funcs could, without needing to introduce new types and syntax. However, automatic stack allocation has a different set of limitations, which are worth comparing to value func limitations:

• Automatic stack allocation depends on escape analysis. Determining whether an object escapes when a reference to it is passed to a call requires analyzing the callee. This is not a natural fit for the JIT, which compiles callers before callees. Still, a few things could make this an approachable JIT problem:
  • Perhaps if tiered jitting progresses considerably, later tiers could include bottom-up interprocedural analysis.
  • Perhaps IL Link will be expanded to perform escape analysis and record results in metadata, though this approach wouldn't reach across assembly boundaries.
  • Inlining in the JIT can reduce the requisite escape analysis problem to an intraprocedural one. Inlining brings in code duplication costs similar to the value func code expansion cost described above. It also opens the potential for the JIT to rewrite delegate calls as direct ones.
• Regardless of how it is implemented, automatic stack allocation will have limits blocking the analysis or implementation that may be opaque to developers. Some examples:
  • Cross-assembly analysis, if not performed at JIT time or in self-contained deployments, likely won't be available, since it breaks versioning.
  • Virtual calls, except where they can be devirtualized, prevent inlining and pose a greater challenge for interprocedural analysis (in fact, if the type/method is not sealed, escape analysis across virtual calls becomes intractable except in some special closed-universe scenarios). Value funcs can be used (and stack-allocated) across virtual calls, though it's worth noting that value funcs require generic type parameters, and generic virtual methods have some additional overhead compared to non-generic virtual methods.
  • Inlining, on which stack allocation may depend (see first bullet), has various structural blockers. For example
    • At JIT time we can't inline calls from shared generic callers to shared generic callees, beacuse the dictionaries may not be compatible.
    • Until recently, RyuJIT was unable to inline methods with conditional throws.
    • Currently RyuJIT can't inline methods that have try/catch/finally blocks.
  • Automatic stack allocation is likely to back off for large objects, and for objects which are allocated under only one arm of an if/else, for fear of introducing stack overflow.
  • Determining whether an allocation site escapes its loop iteration is a harder problem than determing whether it escapes its method, so automatic stack allocation may back off for allocations in loops.
  • Things like taking a ref of a variable or storing a value in a struct can quickly make the optimizer use conservative analysis that assumes the worst-case, even when the actual value propagation “is obvious” to people reading the code.
  • Those same constructs are sometimes implicit from the source view, like how the sequence for x.field1 is ldloca x; ldfld field1, so there’s a ref to x on the evaluation stack and now the analysis is in an arms race with the MSIL generator to “know” that that’s “not really” having its address taken. For example, you could just have the analysis pattern-match the ldloca + ldfld sequence, but x.field1.field2 is ldloca + ldflda + ldfld, so now you need to pattern match that, and perhaps the next version of the C# compiler will translate x.field1 … x.field2 as ldloca x; dup; ldfld field1; … ldfld field2, so that’s another thing for the analysis to have to see through, etc.
  • The analysis is going to have some sort of internal throughput throttling which can manifest in odd ways, so maybe it treats local x conservatively because it happened to be local number 33, or happened to be in a method with a filter, or happened to be live across a finally handler which wasn’t even in the source but got inserted because the source had a foreach over a type with an IDisposable enumerator, …
• These limitations could hit or miss unpredictably, due to subtle changes in the source code, or in the versions of referenced assemblies or the compilers/runtime.

Ultimately, the main benefit of relying on automatic stack allocation and avoiding value funcs would be that it avoids introducing new types/syntax/concepts, and the main benefit of introducing value funcs over relying on automatic stack allocation would be that value funcs can guarantee stack allocation (so long as they don't share captured state with lambdas of other types) in the face of virtual calls, multiple assemblies, and the various subtle limitations on the compiler's analysis and infrastructure.

[HaloFour]

Related: https://github.com/dotnet/csharplang/blob/master/proposals/static-delegates.md

[gafter]

I believe that type classes (#110) would provide most if not all of the benefits of this proposal.

[svick]

@gafter How do type classes let you convert a lambda (including its closure) to a struct?

[erik-kallen]

I have a feeling that this, as well as many similar issues, would be better if they were fixed by introducing escape analysis (like HotSpot) in the jitter

[benaadams]

@erik-kallen is picked up in section "Overlap with automatic stack allocation"

[JosephTremoulet]

I believe that type classes (#110) would provide most if not all of the benefits of this proposal.

@gafter, I'm afraid I'm not following. One aspect of this proposal is about parameterizing code on logic that will be injected by jit-time specialization rather than run-time indirections, and I totally see how type classes do that in a more general way. The other aspect of this proposal is about being able to use the convenient lambda abstraction without incurring the cost of heap allocations. I don't see at all how type classes are related to this second aspect. Are you asserting that lambdas without heap allocations would provide no real benefit, or that type classes somehow enable that, or ... ?

[wesnerm]

We could allow ref struct lambdas that follow a similar design to Span.

Existing delegates can be easily converted and passed to functions that take ref struct lambdas.
Ref struct lambdas would have similar restrictions as they can only exist on the stack.

readonly ref struct Function<P,R>
{
     object target;
     IntPtr function;
     public R Invoke(P);
}

An implicit conversion of Func<P,R> or similar delegate transfers values of target and function to the struct fields.

A regular closure simply uses a generated struct to hold the captured variables and passes the location of the struct and the address of the compiler generated function to the constructor of the Function struct.

[Thaina]

I was once propose https://github.com/dotnet/roslyn/issues/11882 about sync keyword on lambda and I wish the same thing as you, ability to create function that directly translate into JIT code instead of lambda stack

All in all I think this is already in the realm of metaprogramming

[bartdesmet]

FWIW, I recently had to build a similar mechanism as part of an optimizer in the context of a data processing system, where we're sensitive about allocations. Similar to this proposal, it introduced a notion of "value delegates", and relied on a rewrite pattern for "value delegate" declarations, as well as construction and invocation sites of such delegates. The trick is the same as the one described here, namely forcing the use of a constrained.callvirt.

With "class delegates", one writes this:

delegate T Return<T>();

public static void Demo()
{
    int x = 5;
    int y = Eval(() => x);
}

static T Eval<T>(Return<T> f) => f();

which gets compiled into something like this:

public static class Lowered
{
    delegate T Return<T>();

    public static void Demo()
    {
        var d = new DisplayClass();
        d.x = 5;
        int y = Eval(new Return<int>(d.D));
    }

    static T Eval<T>(Return<T> f) => f.Invoke();

    class DisplayClass
    {
        public int x;

        public int D() => x;
    }
}

The heap allocations are for the DisplayClass closure and the Return<T> delegate.

With "struct delegates", one could write something like this (allowing some hypothetical syntax):

ref struct delegate T Return<T>();

public static void Demo()
{
    int x = 5;
    int y = Eval(() => x);
}

static T Eval<T>(Return<T> f) => f();

possibly with some more ref sprinkled in to decorate the lambda expression (as is the case in the proposal on this thread).

The lowering steps I currently employ for this look like this, which can readily be compiled and run today:

interface Return<TClosure, T>
{
    T Invoke(ref TClosure closure);
}

public static void Demo()
{
    DisplayStruct d = new DisplayStruct();
    d.x = 5;
    int y = Eval<DisplayStruct, ReturnImpl, int>(ref d, new ReturnImpl());
}

static T Eval<TClosure, TDelegate, T>(ref TClosure d, TDelegate f) where TDelegate : struct, Return<TClosure, T>
    => f.Invoke(ref d); // results in a constrained.callvirt to Invoke

struct DisplayStruct
{
    public int x;
}

struct ReturnImpl : Return<DisplayStruct, int>
{
    public int Invoke(ref DisplayStruct d)
    {
        return d.x;
    }
}

That is, struct delegates become interfaces with a (hidden) first type parameter for the closure type, and instances of the delegate are effectively pairs of (aref to) a closure value and the delegate implementation.

Obviously, signatures like Eval become hideous because of the added generic parameters. Type classes inspired by Concept C# could make such witness parameters implicit.

Some performance numbers:

[CLASS]  00:00:05 - 67671005 iterations - 709 gen0
[STRUCT] 00:00:05 - 81015620 iterations - 0 gen0

[acaly]

Fortunately, since value funcs would be exposed to the source only via byref-like references, and the rules for byref-likes preclude escaping their scope, value funcs can only reference captured variables from the current iteration of their scope.

I am not sure what is precluded and how that is to ensure safety. In the original proposal there is a nested scope example:

public class NestedScopesWithValueFuncLambdas
{
    public static void CreateNestedDisplays()
    {
        // This part has to be removed; ValueFunc<...>.Reference<...> is a byref-like
        // type, so it's impossible to instantiate List<ValueFunc<...>.Reference<...>>.
        //    var funcs = new List<ValueFunc<int>.Reference<???>>();

        int sharedValue = 1;

        for (int i = 0; i < 10; ++i)
        {
            int independentValue = i;

            // Each loop iteration creates a lambda.  All lambdas must refer to the same
            // 'sharedValue' since it is captured by reference from the outer scope.
            // Each lambda may refer to the same 'independentValue' since they can only
            // use its value from the current iteration.
            var func = ref struct () => sharedValue + independentValue;

            // This will use the current values of 'sharedValue' and 'independentValue'.
            UseLatestFunc(func);

            // Modify sharedValue on each loop iteration.  Subsequent calls to this 'func'
            // can't happen, since it's about to go out of scope.  Calls to the 'func'
            // created on subsequent iterations will see the new value of 'sharedValue'.
            sharedValue *= 2;

            // This part also has to be removed (no way to copy a byref-like into anything
            // that outlives its scope).
            //   funcs.Add(func);
        }

        // This part also has to be removed; there's no way to use a byref-like from outside
        // its scope.
        //   UseAllFuncs(funcs);
    }

    public static void UseLatestFunc<TFuncImpl>(ValueFunc<int>.Reference<TFuncImpl> func) => Console.WriteLine($"Value: {func.Invoke()}");

    // This, too, has to be removed, since it attempts to use byref-like ValueFunc<int>.Reference<...> as a type argument:
    //   public static void UseAllFuncs<TFuncImpl>(List<ValueFunc<int>.Reference<TFuncImpl>> funcs) { ... }
}

The problem is, even though we cannot instantiate a List<ValueFunc<...>.Reference<...>> to store the reference on heap, we can still store them in an outer-scope stack region, where the referenced closure variables can go out of scope. For example, this is not forbidden by C#:

ValueFunc<...>.Reference<DisplayStruct> outerScopeVar;

{
    DisplayStruct displayStruct = ...;

    //The compiler will translate the following:
    //  var innerScopeVar = ref struct (int i) => ...;
    //to:
    var innerScopeVar = Wrap(ref displayStruct);

    //This is allowed: you can copy it to outer scope:
    outerScopeVar = innerScopeVar;
}

//Here the display struct has become invalid!
outerScopeVar.Invoke(...);

This can easily make unsafe codes.

[CodingMadness]

Any news on this O_o its a really beloved feature I think.

[Trayani]

I think the last time this was addressed was in LDM-2021-04-07

[alrz]

How do type classes let you convert a lambda (including its closure) to a struct?

You can get a slight improvement in @bartdesmet's example by using static abstract members which I believe is how "type classes" would be implemented.

// shape Return<T> {
//   T Invoke();
// }
interface Return<T, TSelf> {
    static abstract T Invoke(ref TSelf self);
}

// compiler generated
struct DisplayStruct {
    public int x;
}

// compiler generated
// generally, this is how `implement Return<int> for DisplayStruct {..}` gets lowered
struct ReturnImpl : Return<int, DisplayStruct> {
   public static int Invoke(ref DisplayStruct self) => self.x;
} 

public static void Demo() {
    // int x = 5;
    // int y = Eval(() => x);
    DisplayStruct d = new DisplayStruct();
    d.x = 5;
    int y = Eval<DisplayStruct, ReturnImpl, int>(ref d);
}

// static T Eval<T>(Return<T> f) => f();
static T Eval<TSelf, TDelegate, T>(ref TSelf d) where TDelegate : struct, Return<T, TSelf>
    => TDelegate.Invoke(ref d);

This is basically how Rust does closures.

[BlinD-HuNTeR]

This is something that I would really like to see incorporated into the language, but in my opinion, if we really want the C# Language Design Team to pick any feature suggestion among a million others, we better make it as simple as possible for them to implement it.

So my question is: What is the point of that WrappedReference thing, and that nested class with unsafe code? Not only the syntax is pretty bad, with the receiving method taking a parameter of type "ValueFunc<T, TResult>.Reference<TLambda>, but it apparently makes the implementation just more complex.

Could we instead have an implementation somewhat similar to this:

public interface IFunc<T, TResult> { TResult Invoke(T arg); }
public ref struct ValueFunc<TLambda, T, TResult> where TLambda : IFunc<T, TResult>
{
    //Since this type will be defined in core library, it will have access to ByReference<T>
    //Also, we are getting ref fields in C# 11 right? So this may even become just "ref TLambda lambda;"
    ByReference<TLambda> lambda;
    public TResult Invoke(T arg) => lambda.Value.Invoke(arg);
}

Then the usage would be just like this:

void PrintSome<TLambda>(int[] ints, ValueFunc<TLambda, int, bool> predicate) where TLambda : IFunc<int, bool>
{
    foreach (int i in ints)
    {
        if (predicate.Invoke(i))
        {
            Console.WriteLine(i);
        }
    }
}

All of this is already valid C# code, the only thing that is needed now is the syntax sugar to transform lambda expression into a "DisplayClass" struct, that implements the corresponding interface.

This approach would still capture variables by reference, and it should work exactly the same way as you proposed, while being much simpler to implement and to use. Am I missing something?

[IS4Code]

Sorry if I have missed it in this discussion, but I hope generic-invoke functional interfaces which are vital to situations with type producers are considered:

public interface IGenericAction
{
    void Invoke<T>(T arg);
}

Some situations are almost impossible to handle without these, but it is still such a hassle to implement them.