カテゴリー: LINQ

---

式木とは

.NET 3.5で「Expression Tree」というライブラリが追加されました。C# 3.5ではこのライブラリを使用して、「式木」と呼ばれる機能をサポートしました。
式木とは、例えばC#で記述した式を実行時に解析出来るようなフレームワークです。とは言っても、C#のソースコード文字列を解析できるわけではなく、あくまで式の構造を表現するものです。例えば：

// 普通のラムダ式をデリゲートとして保持
Func<int, string> stringFunc = value => string.Format("Value = {0}", value);

// 例：デリゲートを実行
var result = stringFunc(123);
Debug.Assert(result == "Value = 123");

// ラムダ式を式木として保持
Expression<Func<int, string>> stringExpr = value => string.Format("Value = {0}", value);

// 例：ラムダ式の構造を調べる
Debug.Assert(stringExpr.Parameters[0].Name == "value");
Debug.Assert(stringExpr.Parameters[0].Type == typeof(int));
Debug.Assert(stringExpr.ReturnType == typeof(string));
var mcExpr = stringExpr.Body as MethodCallExpression;
Debug.Assert(mcExpr.Method.DeclaringType == typeof(string));
Debug.Assert(mcExpr.Method.Name == "Format");
Debug.Assert(mcExpr.Arguments[0].Type == typeof(string));

デリゲートと異なり、式木（Expressionクラス）としてラムダ式を受けるように書くことで、ラムダ式の構造を動的に探索することが可能となります。
また、以下のように、それを「コンパイル」して、実際に呼び出すことが出来ます。

// 式木を動的にコンパイルする
Func<int, string> compiledFunc = stringExpr.Compile();

// 出来上がったデリゲートを実行する
var compiledFuncResult = compiledFunc(123);
Debug.Assert(compiledFuncResult == "Value = 123");

わざわざ式木で受けておいて、動的にコンパイルするぐらいなら、初めからデリゲートで良いじゃないか！と思うかもしれませんが、逆なのです。式木を手で構築すれば、同じようにコンパイルが可能となり、高速実行可能なコードを動的に扱うことが出来ます。

// 式木を動的に構築する

// ラムダ式のパラメータに相当する式木
var pValueExpr = Expression.Parameter(typeof(int), "value");

// string.FormatメソッドのMethodInfo
var stringFormatMethod = typeof(string).
	GetMethod("Format", new[] { typeof(string), typeof(object) });

// ラムダ式の本体に相当する式木 「string.Format("Value = {0}", value)」
// Convertが必要なのは、引数の型はobjectなのでintから変換が必要なため（暗黙変換が行われない）
var bodyExpr = Expression.Call(
	stringFormatMethod,
	Expression.Constant("Value = {0}"),
	Expression.Convert(pValueExpr, typeof(object)));

// ラムダ式に相当する式木 「value => string.Format("Value = {0}", value)」
Expression<Func<int, string>> dynamicStringExpr =
	Expression.Lambda<Func<int, string>>(
		bodyExpr,
		pValueExpr);

// 式木を動的にコンパイルする
Func<int, string> compiledFunc = dynamicStringExpr.Compile();

// 出来上がったデリゲートを実行する
var compiledFuncResult = compiledFunc(123);
Debug.Assert(compiledFuncResult == "Value = 123");

そもそもの動機

前置きはこのぐらいで、要するに動的コード生成技術の一つの道具として、式木を使うことが出来ます。インタプリタ的に処理すると動作速度に難があるような場合、コンパイルして実行出来るというのは、非常に大きなアドバンテージです。内部ではILが生成されるので、C#で普通にソースコードを書いてコンパイルして実行したのとそん色ない速度を達成出来ます。

動的にコードを実行する手段として、Emitライブラリを使用してILで書くこともできますが、個人的なメリットとデメリットを挙げると：

式木（Expression Tree）

• メリット：使用可能なCLRが多い。.NET 3.5以降・Silverlight・Silverlight for Windows Phone・Store App・Universal Windows Platform
• デメリット：式木の論理構造について色々知っておく必要がある。.NET 3.5と.NET 4.0以降で機能面に差異がある。

IL by Emit （System.Reflection.Emit）

• メリット：ILで許されるどんなコードでも書ける。ILのルールは比較的単純なので、ある意味習得は容易。新たなクラスやインターフェイス等も自由に定義できる。また、C#では書けないようなコードでも書ける。
• デメリット：Emitが使えない環境が多い。特にStore AppとUniversal Windows Platformで使えないのが大きい。

Emitが使えないのは、本当に深刻な問題だと個人的には思っているのですが、こればっかりは仕方がない。こういうわけで、式木をメインに考えるのですが…

「.NET 3.5と.NET 4.0以降で機能面に差異がある」（本当はSliverlight for WP辺りにも同じような差がある）

という問題があり、特に.NET 3.5を切り捨てるかどうかで悩む局面がまだあります。3.5なんて古代文明だと言い切れれば無問題なんですが。それで、どうやって.NET 3.5と.NET 4.0の差を埋めるかと言う事を考えるわけです。

---

例1: Expression.Assignがない

問題点

Expression.Assignとは、代入式を示す式木の事です。

// 代入させたいフィールド
static int _fieldValue;

// ...

// 代入式の概念（C#ソースコードとしてコンパイルは不可）
Expression<Func<int, int>> assignExpr = value => _fieldValue = value;

var assignmentExpr = assignExpr.Body as BinaryExpression;
Debug.Assert(assignmentExpr.Type == typeof(int));
var fieldExpr = assignmentExpr.Left as MemberExpression;
Debug.Assert(fieldExpr.Member.Name == "_fieldValue");
Debug.Assert(fieldExpr.Type == typeof(int));
var valueExpr = assignmentExpr.Right as ParameterExpression;
Debug.Assert(valueExpr.Name == "value");
Debug.Assert(valueExpr.Type == typeof(int));

assignExprの行はコンパイルエラーになる（代入式を含むラムダ式はNGのため）ので、上記のコードは実行出来ませんが、仮に上記コードが成立した場合はこのように式木を探索できます。
C#のラムダ式としてコンパイル出来ないため、.NET 3.5でこの式木を表現可能にすることを見送ったのかもしれません。しかし、結局.NET 4.0では上記のようなコードをExpression.Assignを使って実現出来るようになりました。

// 動的に式木を構築すれば可能

// パラメータの式木
var pValueExpr = Expression.Parameter(typeof(int), "value");

// フィールドを示す式木
var fieldValueExpr = Expression.Field(null, typeof(Program).GetField("_fieldValue"));

// Expression.Assignを使って代入式を示す式木を作り、それをbodyにラムダ式木を生成
Expression<Func<int, int>> assignExpr =
	Expression.Lambda<Func<int, int>>(
		Expression.Assign(fieldValueExpr, pValueExpr),
		pValueExpr);

さて、これをどうやって.NET 3.5で実現するかという話ですが、Assignがない以上、どうやっても素で代入する式木は実現できません。また別の問題として、代入式には2種類あり、代入対象が「フィールド」なのか「プロパティ」なのかによって、生成されるはずのコードが大きく異なる事です。

フィールドへの代入は上記に示したような式で、最終的にはILのstfld命令に落ちます。しかし、プロパティの場合は（見えない）setterメソッドがあり、代入式と言いつつ実はsetterメソッドの呼び出しコードが生成されるのです。したがって、これらを分けて考えることにします。

フィールド代入のシミュレート

このような、.NET 3.5の式木で表現できないコードは、表現できるところでアウトソース的に実行させるようにすれば良いのです。フィールドの場合、「指定されたフィールドに値を代入させる」ようなメソッドがあったとして、そのメソッドを呼び出す式木を構築すれば実現できます。

このような戦略で考えたヘルパーメソッドが、以下のようなものです。

// フィールドに値を代入させるためのヘルパーメソッド
public static TValue FieldSetter<TValue>(out TValue field, TValue newValue)
{
	field = newValue;	// outなので、対象に代入される
	return newValue;	// ちゃんと値を返すことで、式の体を成す
}

このようなメソッドがあれば、次のようなコードで「間接的」にフィールドに値が代入できます。

// _fieldValue = 123; のシミュレート
var result = FieldSetter<int>(out _fieldValue, 123);

あとはこれを式木で表現します。

// FieldSetterのクローズジェネリックメソッド
var fieldSetterMethod = typeof(Program).
	GetMethod("FieldSetter").
	MakeGenericMethod(fieldValueExpr.Type);

// FieldSetterを呼び出す式木から、ラムダ式木を生成
var assignExpr =
	Expression.Lambda<Func<int, int>>(
		Expression.Call(fieldSetterMethod,
			fieldValueExpr, 	// outでもうまいことやってくれる
			pValueExpr),
		pValueExpr);

面白いのは、メソッド引数がoutパラメータであっても、式木上は特に何もしなくてもライブラリ内でよしなにやってくれることです。頭の中で考えていた時は、ここをどうするかが問題だなと思っていましたが、無問題でした。

プロパティ代入のシミュレート

プロパティへの代入が、実際にはsetterメソッドの呼び出しである事は前に述べたとおりです。では、それをそのままFieldSetterのように呼び出してしまえば目的が達成出来そうですが、厄介な問題があります。

// 代入させたいプロパティ
public static int TestProperty { get; set; }

// ...

// resultの値は？
var result = TestProperty = 123;
Debug.Assert(result == 123);

// プロパティのsetterメソッドの戻り値はvoidなので、以下はNG（疑似コード）
// （プロパティのsetterメソッド名は実際には異なる可能性があります）
var result = set_TestProperty(123);

上記のように、代入式の結果は、代入された値となるはずです。なので、Expression.Assignの結果はintの123になります。しかし、単にsetterメソッドを呼び出した場合、そのメソッドの戻り値はvoidであるため、異常な式木となってしまいます。

結局、ここでもヘルパーメソッドの登場となるわけです。

// プロパティに値を代入させるためのヘルパーメソッド
public static TValue PropertySetter<TValue>(Action<TValue> setter, TValue newValue)
{
	setter(newValue);	// デリゲートに設定させる
	return newValue;	// ちゃんと値を返すことで、式の体を成す
}

このヘルパーメソッドは、指定されたデリゲートを実行して、値を返します。フィールドの時のようにoutパラメータが使えれば良いのですが、プロパティメンバに対してoutパラメータを適用することは出来ないので、同じ方法では実現できません。

そこで、「プロパティに代入するラムダ式」を指定させ、デリゲートとして実行することで、間接的にvoid（を返す式木）の問題を回避しようというわけです。つまり：

// TestProperty = 123; のシミュレート
var result = PropertySetter<int>(innerValue => TestProperty = innerValue, 123);

// 更に生っぽく
var result = PropertySetter<int>(innerValue => set_TestProperty(innerValue), 123);

実はExpression.Lambda<T>は、FuncだけではなくActionデリゲートでも定義できます。つまり、値を返さない（void）なラムダ式を示す式木は作ることが出来ます。上記のように、PropertySetterの引数に指定するラムダ式の式木は作成できるのです。

// プロパティを示す式木
var testProperty = typeof(Program).GetProperty("TestProperty");
var testPropertyExpr = Expression.Property(null, testProperty);

// PropertySetterの引数に渡すラムダ式
// innerValue => set_TestProperty(innerValue);
var pInnerValueExpr = Expression.Parameter(typeof(int), "innerValue");
var setterExpr =
	Expression.Lambda(
		typeof(Action<>).MakeGenericType(testPropertyExpr.Type),
		Expression.Call(
			null,
			testProperty.GetSetMethod(false),	// プロパティのsetterメソッドを取得する
			pInnerValueExpr),
		pInnerValueExpr);

// PropertySetterのクローズジェネリックメソッド
var propertySetterMethod = typeof(Program).
	GetMethod("PropertySetter").
	MakeGenericMethod(testPropertyExpr.Type);

// PropertySetterを呼び出す式木から、ラムダ式木を生成
var assignExpr =
	Expression.Lambda<Func<int, int>>(
		Expression.Call(propertySetterMethod,
			setterExpr,
			pValueExpr),
		pValueExpr);

ちょっと式木として大きくなってしまいましたね。.NET 3.5ではパフォーマンスが低下する要因となるかもしれませんが、同じインフラが使える妥協点としては良いんじゃないでしょうか。

---

例2: Expression.Blockがない

.NET 4.0以降では、Assign同様、以下のようなブロックを含む式を「Expression.Block」を使って作ることが出来ます。

// ブロックを含む式の概念（C#ソースコードとしてコンパイルは不可）
Expression<Action<int, int>> blockedExpr = (a, b) =>
{
	Console.WriteLine("{0}+{1}", a, b);
	Console.WriteLine("{0}*{1}", a, b);
};

// 動的に式木を構築すれば可能

// パラメータの式木
var paExpr = Expression.Parameter(typeof(int), "a");
var pbExpr = Expression.Parameter(typeof(int), "b");

// Console.WriteLineのメソッド
var consoleWriteLineMethod = typeof(Console).
	GetMethod("WriteLine", new[] {typeof(string), typeof(object), typeof(object)});

// ブロック内のそれぞれの式
var innerExpr1 = Expression.Call(consoleWriteLineMethod,
	Expression.Constant("{0}+{1}"),
	Expression.Convert(paExpr, typeof(object)),
	Expression.Convert(pbExpr, typeof(object)));
var innerExpr2 = Expression.Call(consoleWriteLineMethod,
	Expression.Constant("{0}*{1}"),
	Expression.Convert(paExpr, typeof(object)),
	Expression.Convert(pbExpr, typeof(object)));

var blockedExpr = Expression.Lambda<Action<int, int>>(
	Expression.Block(
		innerExpr1,
		innerExpr2),
	paExpr,
	pbExpr);

さて、Blockがない.NET 3.5でこれをどう調理するか。

Expression.Blockがやる事

Blockは、n個の任意の式を順番に実行します。NGKのスライドでは、n個の式を逐次実行する方法として、それぞれの式が常にtrueを返す式と見なせたとすれば、Expression.AndAlsoを使って数珠つなぎにすることで、逐次実行が出来ることを示しました。

// それぞれの式が常にtrueを返すと仮定すれば、以下の式で逐次実行できる
var dummy = ((true && expr0) && expr1) && expr2;

ここの部分をTruenizeメソッドを呼び出すように書けばよい的に紹介したんですが、AndAlsoがどこにもない (;´Д｀) 実際はこんな感じです。

// 結果を受け取るが、常にtrueを返すヘルパーメソッド
public static bool Truenize<TValue>(TValue result)
{
	return true;
}

// Truenizeを使って式の結果を常にtrue化し、それをAndAlsoで連結する
var dummy = ((true && Truenize(expr0)) && Truenize(expr1)) && Truenize(expr2);

しかし、スライドで示したTruenizeでも連結実行出来てますね… あれも方法としてはアリでしょう。多分風邪にやられてトチ狂った結果ってことで勘弁。

もう一つ、式が値を返さない（void）場合は、上記TruenizeではTValueがダメなので、PropertySetter同様、ラムダ式を使って間接的に実行させるTruenizeが必要になります。以下のような感じです：

// 結果を受け取るが、常にtrueを返すヘルパーメソッド
public static bool Truenize(Action action)
{
	// デリゲートを実行
	action();
	return true;
}

// Truenizeを使って式の結果を常にtrue化し、それをAndAlsoで連結する
var dummy = ((true && Truenize(() => expr0)) && Truenize(() => expr1)) && Truenize(() => expr2);

非ジェネリックTruenizeでデリゲートを実行させて、voidな式木をラムダ式として実行させるようにします。実際の実装はPropertySetterと同様なので省略。

スコープセパレーション

もう一つの重要な特徴も忘れてました（やばい、これかなり大きなトピックだった）。それは、「スコープを狭める役割」もある事です。ブロック内で宣言された変数はブロック外では使えません。以下は疑似コード：

// 外側のスコープ
var localVariable = 123;

{
	// 内側のスコープ（実際にはコンパイル不可）
	var localVariable = 456;
	Debug.Assert(localVariable == 456);
}

// 影響ない
Debug.Assert(localVariable == 123);

スコープの問題は、式木全体としてちゃんと考えれば影響ないかもしれませんが、式木がどのように組み立てられるか分からない場合は、相互に影響を与えなくてすむ方法があれば、それに越したことはありません。

これのシミュレートはかなり悩みました。色々考えた結果、同じようにスコープを制限しているという特徴を利用したらどうか、と言うものです。それは何か？ ラムダ式ですよ。

// ラムダ式の「引数」は、スコープ内のローカル変数と見なせる（疑似コード・実際にはコンパイル不可）
Action<int> localBlockExpr = localVariable =>
{
	// 外側に影響を与えない
	localVariable = 456;
	Debug.Assert(localVariable == 456);
};

// 外側のスコープ
var localVariable = 123;

// デリゲートを実行
localBlockExpr(default(int));

// 影響ない
Debug.Assert(localVariable == 123);

ラムダ式を使ってラップすることで、引数をローカル変数としてみなし、スコープを強制することが出来ます。これと同じことを動的に式木を組み立てて実現すれば良いわけです。但し、まだ問題もあります。上記のままだと、スコープ内のローカル変数が増えると、Actionデリゲートのジェネリック引数を増やす必要があり、実装上も上限的にも辛い香りが漂います。代替案として思いつく方法は：

// ローカル変数としての受け皿を保持するクラスを動的に生成する（疑似コード）
public sealed class LocalVariableClosure
{
	public int localVariable1;
	public int localVariable2;
	public int localVariable3;
	// ...
}

// これを引数にする
Action<LocalVariableClosure> localBlockExpr = localVariableClosure =>
{
	// LocalVariableClosureをクロージャ的に扱う
	localVariableClosure.localVariable1 = 111;
	localVariableClosure.localVariable2 = 222;
	localVariableClosure.localVariable3 = 333;
	// ...
};

// LocalVariableClosureを生成して渡す
localBlockExpr(new LocalVariableClosure());

アイデアとしては良いんですが、お手付きですね。LocalVariableClosureクラスを「動的」に作るには、Emitが必要です。そんなわけで、Emitしなくても同じような事が出来ないか頭をひねるとこうなります：

// object配列の引数を渡し
Action<object[]> localBlockExpr = localVariables =>
{
	// 配列の各要素をローカル変数と見なす
	localVariables[0] = 111;
	localVariables[1] = 222;
	localVariables[2] = 333;
	// ...
};

// object配列を生成して渡す（要素数が分かる必要がある）
localBlockExpr(new object[3]);

しかし、まだ足りない。上記コードのように配列に代入したり参照したりするためには、objectとの型の変換が常に必要になります。式木として扱う場合、式木の各要素は基底クラスの「Expressionクラス」から継承しているわけですが、この代入を成立させるには型変換（Convert）も式木に盛り込まなければなりません。また、その変換は左辺側の式木内で吸収出来る必要があります。段々気絶級になってきた…

// object配列の引数を渡し
Action<object[]> localBlockExpr = localVariables =>
{
	// 型変換（Expression.Convert）が必要。しかも本当は左辺での実現が必要
	localVariables[0] = (object)111;
	otherVariable = (int)localVariables[0];
};

# C++なら参照使って左辺で表現出来るんですが…

結論の前に、ローカルスコープ内の式木を、例1のフィールドへの代入式の例で表現するとこうなります：

// ローカル変数パラメータ
var localVariablesExpr = Expression.Parameter(typeof(object[]), "localVariables");

// 代入式
var assignerExpr = Expression.Call(fieldSetterMethod,
	fieldValueExpr,
	Expression.Convert(	// どう頑張っても右辺でしか表現できない
		Expression.ArrayIndex(
			localVariablesExpr,
			Expression.Constant(0)),
		typeof(int)));

// ラムダ式にしてテスト
var testExpr = Expression.Lambda<Action<object[]>>(
	assignerExpr,
	localVariablesExpr);
var compiledAction = testExpr.Compile();

var testLocalVariables = new object[] {123};
compiledAction(testLocalVariables);
Debug.Assert(_fieldValue == 123);

Blockのシミュレートアイデアとしてはこれで全てです。が、これを使って.NET 3.5でも.NET 4.0でも同じように記述可能にするには、Expressionクラスをラップするエミュレーションレイヤーが必要になります。特に左辺をローカル変数式木としてだまして（.NET 4.0ではExpression.Variable）置きながら、実際に生成される式木では配列参照とConvertを挟む必要があるため、ユーティリティメソッドレベルの対応ではたぶん無理だろうと考えました。

そんなわけで、上記の全てを組み合わせたコードはあまりにも大きいため、ここでは示しません。エミュレーションレイヤーとしてExpressionクラスを再定義した例を以下のコードに示します。

.NET 3.5での実装：
CenterCLR.ExaSerializers/ExpressionCompatibilityLayer_Strict.cs

.NET 4.0での実装：
CenterCLR.ExaSerializers/ExpressionCompatibilityLayer_Extended.cs

文中のサンプルコードはここ：
CenterCLR.ExpressionTreeCompatibility

---

まとめ

.NET 3.5の式木サポートで不足しているものは他にも色々あると思います。ループとかもそうですね。.NET 3.5に欠けているものは、C# 3.0の式木として受け入れられないもの、のように思います。そこから慎重にドリルダウンすることで、シミュレートするアイデアが得られるのではないかなと思います。とはいえ、やってみて分かったのは、想像以上に沼地だったと言う事です ( ´Д｀)=3 ﾌｩ

最後にサンプルで紹介したコードは、高速バイナリシリアライザです。テストはかなり通してあるので、興味があればいじってみて下さい。特に逆シリアル化でストリーミング出来るようにしたのはイケてると、勝手に思ってます。

GitHub: CenterCLR.ExaSerializers

次はvarmilさん、よろしくお願いします！

Final LINQ Extensions – 第二回Center CLR勉強会
Final LINQ Extensions II – 第三回Center CLR勉強会