Posso creare un'espressione ricorsiva ottimizzata chiamata coda?

Question

Provo a creare una coda ricorsiva Expression in .NET 4.0.

Posso compilarlo ma, questo metodo compilato non è ottimizzato in coda, nonostante l'indicazione tailCall = true, l'IL generato non ha un'istruzione prefisso tail..

Per favore, dimmi come si costruisce un ricorsivo ottimizzato Expression?

L'espressione di compilazione è riportata di seguito.

using System; 
using System.Linq.Expressions; 

namespace ConsoleApplication2 
{ 
    public delegate int RecursiveFunc(RecursiveFunc function, int acc, int n); 

    internal class Program 
    { 
     private static void Main() 
     { 
      var funcParam = Expression.Parameter(typeof (RecursiveFunc)); 
      var accParam = Expression.Parameter(typeof (int)); 
      var nParam = Expression.Parameter(typeof (int)); 
      var constZero = Expression.Constant(0, typeof (int)); 

      var accumExpr = Expression.Add(accParam, nParam); 
      var decrimentExpr = Expression.Decrement(nParam); 

      var invokeExpr = Expression.Invoke(funcParam, funcParam, 
       accumExpr, decrimentExpr); 

      var testExpr = Expression.Equal(nParam, constZero); 
      var condExpr = Expression.Condition(testExpr, accParam, 
       invokeExpr); 

      var lambda = Expression.Lambda<RecursiveFunc>(condExpr, 
       "TailCall", true, new[] {funcParam, accParam, nParam}); 

      var sumParam = Expression.Parameter(typeof (RecursiveFunc), 
       "Sum"); 

      var method = lambda.Compile(); 

      var ans = method(method, 0, 100); 
      Console.WriteLine(ans); 
     } 
    } 
} 

E questo lambda expresion generato IL è sotto

.method public static int32 EvaluateTarget (
    class [ConsoleApplication2]ConsoleApplication2.RecursiveFunc '', 
    int32 '', 
    int32 '' 
) cil managed 
{ 
    // Method begins at RVA 0x2050 
    // Code size 25 (0x19) 
    .maxstack 7 

    IL_0000: ldarg.2 
    IL_0001: ldc.i4.0 
    IL_0002: ceq 
    IL_0004: brfalse IL_000b 

    IL_0009: ldarg.1 
    IL_000a: ret 

    IL_000b: ldarg.0 
    IL_000c: ldarg.0 
    IL_000d: ldarg.1 
    IL_000e: ldarg.2 
    IL_000f: add 
    IL_0010: ldarg.2 
    IL_0011: ldc.i4.1 
    IL_0012: sub 
    IL_0013: callvirt instance int32 
     [ConsoleApplication2]ConsoleApplication2.RecursiveFunc::Invoke(class 
     [ConsoleApplication2]ConsoleApplication2.RecursiveFunc, int32, int32) 
    IL_0018: ret 
} // end of method AutoGeneratedType::EvaluateTarget 

Answer 1

le seguenti opere in giro:

using System; 
using System.Linq.Expressions; 
using System.Reflection.Emit; 

namespace ConsoleApplication2 
{ 
    public delegate int RecursiveFunc(RecursiveFunc doCall, RecursiveFunc function, int acc, int n); 

    internal class Program 
    { 
     private static void Main() 
     { 
      DynamicMethod dm = new DynamicMethod("DoInvokeWithTailCall", typeof(int), new Type[] { typeof(RecursiveFunc), typeof(RecursiveFunc), typeof(int), typeof(int) }, typeof(Program).Module); 
      ILGenerator il = dm.GetILGenerator(); 
      il.Emit(OpCodes.Ldarg_1); 
      il.Emit(OpCodes.Ldarg_0); 
      il.Emit(OpCodes.Ldarg_1); 
      il.Emit(OpCodes.Ldarg_2); 
      il.Emit(OpCodes.Ldarg_3); 
      il.Emit(OpCodes.Tailcall); 
      il.EmitCall(OpCodes.Callvirt, typeof(RecursiveFunc).GetMethod("Invoke"), null); 
      il.Emit(OpCodes.Ret); 
      RecursiveFunc doCall = (RecursiveFunc)dm.CreateDelegate(typeof(RecursiveFunc)); 

      var doCallParam = Expression.Parameter(typeof(RecursiveFunc)); 
      var funcParam = Expression.Parameter(typeof(RecursiveFunc)); 
      var accParam = Expression.Parameter(typeof(int)); 
      var nParam = Expression.Parameter(typeof(int)); 
      var constZero = Expression.Constant(0, typeof(int)); 

      var accumExpr = Expression.Add(accParam, nParam); 
      var decrimentExpr = Expression.Decrement(nParam); 

      //var invokeExpr = Expression.Invoke(funcParam, funcParam, funcParam, accumExpr, decrimentExpr); 
      var invokeExpr = Expression.Call(dm, doCallParam, funcParam, accumExpr, decrimentExpr); 

      var testExpr = Expression.Equal(nParam, constZero); 
      var condExpr = Expression.Condition(testExpr, accParam, 
       invokeExpr); 

      var lambda = Expression.Lambda<RecursiveFunc>(condExpr, 
       "TailCall", true, new[] { doCallParam, funcParam, accParam, nParam }); 

      var method = lambda.Compile(); 

      var ans = method(doCall, method, 0, 100); 
      Console.WriteLine(ans); 
     } 
    } 
}