Expression Tree Programming

id:NyaRuRu:20070216:p1 と id:NyaRuRu:20070416:p1 の続き．さらに腐りかけてる書きかけの資料の処分．

例えばクイックソートの Expression Tree と，比較関数の Expression Tree を実行時に合成，つまり手動で Expression Tree 上のインライン展開を行い，それを動的にコンパイルすることで，完全にインライン展開された JIT コードを手に入れられるものと考えられます．現在ネットワーク的に僻地なので今回例は示しませんが，Orcas CTP の 2 月版が出た頃に可能ならもう一度取り上げてみたいと思います．

これですが，実際あの後すぐに Orcas CTP が出たので試してみたところ，非常に単純なポイントを見落としていたことに気付きました．そうです．Expression Tree にはループが無いのです．まあ世が世なら末尾再帰とかそれらしい方法でカバーするのでしょうが，Expression Tree の範囲内でクイックソートを書くにはどうしたものかと．結局のところ，ループを使うコードは LCG のお世話になりそうというという結論に至りました．

---

というだけだとアレなので，Func<T,T> なラムダ式を受け取って，T 型配列の要素を全て変換するというコードを動的生成してみたりしていました．作りかけなんですが，そろそろ HDD フォーマットするしまあいいやと．まあたぶん無いと思いますが，需要があればそのうちまとめなおすかもしれません．
やっていることは Expression Tree を Transverse しながらひたすら IL Emit しているだけです．

using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Linq.Expressions;
using System.Reflection.Emit;
using System.Reflection;

public static class Algorithm
{
    public static void GenerateIL<T>(ILGenerator ilgen, Expression<Func<T,T>> lambda, LocalBuilder arg0)
    {
        GenerateIL(ilgen, lambda.Body, arg0);
    }
    public static void GenerateIL(ILGenerator ilgen, ConstantExpression constant)
    {
        if(constant.Type == typeof(int))
        {
            ilgen.Emit(OpCodes.Ldc_I4, (int) constant.Value );
        }
        else if (constant.Type == typeof(byte))
        {
            ilgen.Emit(OpCodes.Ldc_I4, (byte)constant.Value);
        }
        else if (constant.Type == typeof(short))
        {
            ilgen.Emit(OpCodes.Ldc_I4, (short)constant.Value);
        }
        else if (constant.Type == typeof(long))
        {
            ilgen.Emit(OpCodes.Ldc_I8, (long)constant.Value);
        }
        else if(constant.Type == typeof(float))
        {
            ilgen.Emit(OpCodes.Ldc_R4, (float)constant.Value);
        }
        else if (constant.Type == typeof(double))
        {
            ilgen.Emit(OpCodes.Ldc_R8, (double)constant.Value);
        }
        else
        {
            Debugger.Break();
        }
    }
    public static void GenerateIL(ILGenerator ilgen, ParameterExpression constant, LocalBuilder arg0)
    {
        ilgen.Emit(OpCodes.Ldloc, arg0);
    }
    public static void GenerateIL(ILGenerator ilgen, MemberExpression member, LocalBuilder arg0)
    {
        if (member.Member is FieldInfo)
        {
            FieldInfo info = member.Member as FieldInfo;
            if( !info.IsStatic )
                GenerateIL(ilgen, member.Expression, arg0);
            ilgen.Emit(OpCodes.Ldfld, member.Member as FieldInfo);
        }
        else if (member.Member is PropertyInfo)
        {
            MethodInfo info = (member.Member as PropertyInfo).GetGetMethod() ;
            if (!info.IsStatic)
                GenerateIL(ilgen, member.Expression, arg0);
            ilgen.Emit(OpCodes.Call, info);
        }
        else
        {
            Debugger.Break();
        }
    }
    public static void GenerateIL(ILGenerator ilgen, Expression expr, LocalBuilder arg0)
    {
        if (expr is BinaryExpression)
        {
            GenerateIL(ilgen, expr as BinaryExpression, arg0);
        }
        else if (expr is ParameterExpression)
        {
            GenerateIL(ilgen, expr as ParameterExpression, arg0);
        }
        else if (expr is ConstantExpression)
        {
            GenerateIL(ilgen, expr as ConstantExpression);
        }
        else if (expr is MemberExpression)
        {
            GenerateIL(ilgen, expr as MemberExpression, arg0);
        }
    }
    public static void GenerateIL(ILGenerator ilgen, BinaryExpression binary, LocalBuilder arg0)
    {
        switch (binary.NodeType)
        {
            case ExpressionType.Add:
                GenerateIL(ilgen, binary.Left, arg0);
                GenerateIL(ilgen, binary.Right, arg0);
                ilgen.Emit(OpCodes.Add);
                break;
            case ExpressionType.Divide:
                GenerateIL(ilgen, binary.Left, arg0);
                GenerateIL(ilgen, binary.Right, arg0);
                ilgen.Emit(OpCodes.Div);
                break;
            case ExpressionType.Multiply:
                GenerateIL(ilgen, binary.Left, arg0);
                GenerateIL(ilgen, binary.Right, arg0);
                ilgen.Emit(OpCodes.Mul);
                break;
            case ExpressionType.Subtract:
                GenerateIL(ilgen, binary.Left, arg0);
                GenerateIL(ilgen, binary.Right, arg0);
                ilgen.Emit(OpCodes.Sub);
                break;
            default:
                break;
        }
    }
    public static Func<T[], T[]> Transform<T>(Expression<Func<T,T>> expr)
    {
        DynamicMethod dm = new DynamicMethod("Transform", typeof(T[]), new Type[] { typeof(T[]) });
        ILGenerator ilgen = dm.GetILGenerator();

        LocalBuilder i = ilgen.DeclareLocal(typeof(int));
        LocalBuilder value = ilgen.DeclareLocal(typeof(T));
        LocalBuilder array = ilgen.DeclareLocal(typeof(T[]));

        Label loopBegin = ilgen.DefineLabel();
        Label beforeCheck = ilgen.DefineLabel();

        // array = $arg0;
        ilgen.Emit(OpCodes.Ldarg_0);
        ilgen.Emit(OpCodes.Stloc, array);

        // i = 0;
        ilgen.Emit(OpCodes.Ldc_I4_0);
        ilgen.Emit(OpCodes.Stloc, i);

        // goto beforeCheck;
        ilgen.Emit(OpCodes.Br_S, beforeCheck);

        ilgen.MarkLabel(loopBegin);

        // value = array[i];
        ilgen.Emit(OpCodes.Ldloc, array);
        ilgen.Emit(OpCodes.Ldloc, i);
        ilgen.Emit(OpCodes.Ldelem, typeof(T));
        ilgen.Emit(OpCodes.Stloc, value);

        // value = expr(value)
        GenerateIL(ilgen, expr, value);
        ilgen.Emit(OpCodes.Stloc, value);

        // array[i] = value;
        ilgen.Emit(OpCodes.Ldloc, array);
        ilgen.Emit(OpCodes.Ldloc, i);
        ilgen.Emit(OpCodes.Ldloc, value);
        ilgen.Emit(OpCodes.Stelem, typeof(T));

        // ++i
        ilgen.Emit(OpCodes.Ldloc, i);
        ilgen.Emit(OpCodes.Ldc_I4_1);
        ilgen.Emit(OpCodes.Add);
        ilgen.Emit(OpCodes.Stloc, i);

        ilgen.MarkLabel(beforeCheck);

        // if( i >= array.Length ) goto loopBegin;
        ilgen.Emit(OpCodes.Ldloc, i);
        ilgen.Emit(OpCodes.Ldloc, array);
        ilgen.Emit(OpCodes.Ldlen);
        ilgen.Emit(OpCodes.Conv_I4);
        ilgen.Emit(OpCodes.Blt_S, loopBegin);

        // return array;
        ilgen.Emit(OpCodes.Ldloc, array);
        ilgen.Emit(OpCodes.Ret);

        return dm.CreateDelegate(typeof(Func<T[], T[]>)) as Func<T[], T[]>;
    }
}

使い方はこんな感じ．

var array = new int[1024];
......
var trans = Algorithm.Transform<int>(i => i * 2 + 1);
trans(array);

上のコードは，次のような処理を行う delegate を生成しています．trans という変数で受けているのがそれです．

for (int i = 0; i < array.Length; ++i)
{
    array[i] = (array[i] * 2 + 1);
}

ラムダ式を IL に変換して埋め込んでいる (インライン展開する) ので，Array.ConvertAll<T> よりは多分速いというのがポイントですが，はっきり言ってまだまだ未完成です．
どの辺が作りかけかというと，Expression Tree のノードのうち四則演算ぐらいにしか対応していないというのが問題で，Lexical Scope に含まれるオブジェクトへの参照やメソッド呼び出しがあるとアウトです．
一応テスト目的で静的プロパティの呼び出しぐらいには対応させてみましたが，先月波村さんが言われていた「アクセシビリティ絡みややこしい問題」の意味がよく分かりました．ラムダ式を記述した場所ではアクセス可能なprivateなフィールド/プロパティ/メソッドでも，LCG で生成するモジュールから見ればアクセス不可だったりするので，実行時コード生成時には特別な対応が必要と．Expression<TDelegate>.Compile の特殊さというのはつまりそういうところです．
なんだかんだで，実行時に IL をいじるなら ILX が未だに最強なのかもしれません．