DynamicMethodで末尾再帰 - aharisuのごみ箱

唐突ですがC#にはDynamicMethodというクラスがあります。
このクラスではILを直接指定することによって、プログラム実行時に動的にメソッドを作成することができます。

さっそく例

DynamicMethod method = new DynamicMethod("DynamicMethod", typeof(void), Type.EmptyTypes);
ILGenerator il = method.GetILGenerator();

il.Emit(OpCodes.Ldstr, "DynamicMethod!!");
il.Emit(OpCodes.Call, typeof(Console).GetMethod("WriteLine",
	 BindingFlags.Static | BindingFlags.Public, null, new Type[] { typeof(String) }, null));
il.Emit(OpCodes.Ret);

Action action = (Action)method.CreateDelegate(typeof(Action));
action();

実行結果はなんとなく予想がつくと思いますが一応、

DynamicMethod!!

と表示されます。当たり前ですね。

コードの詳細解説は省きます。理由はただ単に面倒くさいからです。
どうしても知りたいという方はmsdnのこの辺を読めばなんとなく感じは掴めるかと。

とまあこんな感じでプログラム実行中に動的にメソッドを作れるわけです。
しかもメソッドを作る際にILを直接使うことによってC#では実現できないこともできたりします。
そのひとつに末尾呼び出しの最適化があります。

まず例題。階乗を求めるどこにでもある関数とそれを呼び出すMainメソッド。

class Program
{
	static void Main(string[] args)
	{
		Console.WriteLine(Fact(5, 1));
	}

	public static int Fact(int num, int acc)
	{
		Console.WriteLine(new StackTrace().FrameCount);

		if (num == 0)
			return acc;
		else
			return Fact(num - 1, num * acc);
	}

}

実行結果

このFactメソッド中の二つ目のreturn、
return Fact(num - 1, num * acc);
という部分が末尾呼び出し（今回は末尾再帰でもある）にあたります。

実行結果の120より前の2〜7の部分は現在のメソッド呼び出しでたまっているスタックフレーム数を表示しているものです。
末尾呼び出しの場合スタックを消費せずにメソッド呼び出しができるのですが、実行結果からわかるとおり一度呼び出すたびにスタックフレームがたまっているのが分かります。
これを最適化しスタック消費なしでメソッド呼び出しを行うのが末尾呼び出しの最適化になるのですが、これをしようと思ってもC#からは明示的に指定する方法がありません。
普通ならメソッド呼び出しで積まれていくスタックフレームはたかが知れているので問題がないのですが、今回の場合メソッドの再帰呼び出しを行っているので大きな数を指定してやった場合スタックのオーバーフローが起こってしまいます。（スタックのオーバーフローよりも先に数字のオーバーフローが起こるということを今は気にしない）

これは由々しき事態です。
さぁどうしましょう。
C#ではできません。
よろしい。ならばILだ。

はい。というわけでDynamicMethodを使い、直接ILを指定して前述のFactと同じ働きをするメソッドを作ってみます。

class Program
{
	static Func<int, int,int> fact;

	static void Main(string[] args)
	{
		DynamicMethod method = new DynamicMethod(
			"factorial", typeof(int), new Type[] { typeof(Program), typeof(int), typeof(int) }, typeof(Program));
		ILGenerator il = method.GetILGenerator();
		Label label = il.DefineLabel();

		il.Emit(OpCodes.Newobj, typeof(StackTrace).GetConstructor(Type.EmptyTypes));
		il.Emit(OpCodes.Callvirt, typeof(StackTrace).GetProperty("FrameCount",
			BindingFlags.Instance | BindingFlags.Public).GetGetMethod());
		il.Emit(OpCodes.Call, typeof(Console).GetMethod("WriteLine", 
			BindingFlags.Public | BindingFlags.Static, null, new Type[] { typeof(int) }, null));

		//引数のnumを読み込む
		il.Emit(OpCodes.Ldarg_1);

		//num != 0 なら再帰呼び出しの方へジャンプ
		il.Emit(OpCodes.Brtrue_S, label);

		//return acc;
		il.Emit(OpCodes.Ldarg_2);
		il.Emit(OpCodes.Ret);

		il.MarkLabel(label);

		//Programクラスの静的フィールドのfactを読み込み
		il.Emit(OpCodes.Ldsfld, typeof(Program).GetField("fact", 
			BindingFlags.NonPublic | BindingFlags.Static));

		//(num - 1)
		il.Emit(OpCodes.Ldarg_1);
		il.Emit(OpCodes.Ldc_I4_1);
		il.Emit(OpCodes.Sub);

		//(num * acc)
		il.Emit(OpCodes.Ldarg_1);
		il.Emit(OpCodes.Ldarg_2);
		il.Emit(OpCodes.Mul);

		//メソッド呼び出し
		il.Emit(OpCodes.Tailcall);
		il.Emit(OpCodes.Callvirt, typeof(Func<int,int,int>).GetMethod("Invoke",
			BindingFlags.Public | BindingFlags.Instance, null, new Type[] { typeof(int), typeof(int) }, null));
		il.Emit(OpCodes.Ret);

		//DynamicMethodの生成
		fact = (Func<int, int,int>)method.CreateDelegate(typeof(Func<int, int,int>), new Program());
		
		//呼び出し
		Console.WriteLine(fact(5, 1));
	}
}

実行結果

前回の結果と見比べてわかるとおり、今回はスタックフレームを消費せずに再帰呼び出しがおこなえていることが分かります。
これを行うために重要なILの命令は、コードの中のメソッド呼び出しというコメントのすぐ下にあるTailcallという命令です。
この命令に続けてメソッド呼び出しを行う命令を指定すれば、そのメソッド呼び出しはスタックフレームを消費しません。

一応ですが注釈。
正確には呼び出しにスタックフレームを消費しないのではなく、現在のスタックフレームを破棄してから新しい呼び出し先のスタックフレームを積む。という作業が行われます。

さらに注釈。
Tailcallの命令はどんな状況でもとにかくメソッド呼び出し命令の前につければいいというわけではありません。Tailcall命令が不正な箇所にある場合は実行時に例外が投げられるので要注意。

今回の方法を使えばC#でも再帰関数を書くのが怖くないですね。
と、言いたいところだが。。。

メンドクせぇ。

それに階乗を求める関数をわざわざ実行時に動的に作る意味なんてない。

と、いうわけで結論。
今回の記事にたいした意義などない。

じゃオワリ。