C#, DLR AST, meta programming
Ask the speakerで波村さんとMVPの方々とお話することができました！！
（そーいうとこだからと突っ込まれちゃいますが、、いや、嬉しくて）
そして！
あのid:NyaRuRuさんが
僕だけの為に、ノートPCを開いてコードの説明をしてくれました＞＜
こちらこそありがとうございます．Y Combinator のときは大変勉強になりました，
というわけでお礼もかねてその辺のお話でも．
Expression Trees
ノート PC を開くきっかけは，id:yuji1982 さんが最近 C# 3.0 の新機能，Expression Trees に挑戦されていると仰っていたことです．Expression Trees がどんなものかは，++C++; 管理人さんの記事 を読んでいただくのが分かりやすいかと思いますが，関数型言語で言うところの quote です．
通常 C# コンパイラは，ソースコード中に現れた式に対応する中間コードを (CIL) を出力しますが，特殊な条件が満たされると，式そのものを実行する CIL の代わりに「その式の木構造に対応する式クラスのインスタンスを，実行時に生成する CIL」というのを出力します．一段メタな感じですね．このメモリ上の木構造のことを Expression Trees (式木) と呼んでいます．
式木は実行時に CIL にコンパイルして，デリゲート経由で実行することができます．得られたメソッドを実行するときには当然 JIT コンパイルも行われるため，式木を経由して得られたプログラムには，静的コンパイルと遜色のないパフォーマンスが得られるという特徴があります．
読むのは OK だけど，作るのは意外と大変な Expression Trees
しかしながら，この式木を扱うプログラムというのは結構大変です．
LINQ Provider を自作するときなど，C# コンパイラが作った式木を traverse するコードを書くのはまあ仕方がないと納得も行くのですが，実行時に式木を作り出すようなプログラムを書くのかなり大変で，安易に踏み込むとのたうち回ることになります．これにはいくつか理由があります．
とまあそんな話で id:yuji1982 さんと盛り上がって，「こんなのありますよ」と取り出したのが Dynamic Language Runtime (DLR) というわけです．
DLR
DLR は C# を使って書かれている動的型付け言語向けのライブラリで，主に以下の 3 つの機能からなります．
DLR のこれらの機能は，元々 IronPython のソースコードにあったものからのブランチされたものです．典型的な動的型付け言語を開発する上で再利用性の高い部分と言えるでしょう．
DLR のリリースは恐らく早くても年末で，まだまだ仕様変更の可能性が残っていますが，現時点でもお手軽言語開発を楽しむことができます．そのあたりについてはタイムリーに荒井さんの blog で『簡単な言語の作り方』というシリーズが書かれています．
さて，IronPython の作者で，現在 DLR の開発に取り組んでいる Jim Hugunin ですが，DLR を使った動的言語開発のペストプラクティスは以下の形になるだろうと発言しています．
このうち言語開発者が作るのは，パーサ，新言語用の AST，さらにそのマッピングルールになります．DLR AST に持って行ってしまえば，後の CIL への静的/動的変換は DLR に任せることができます．
パーサが直接 DLR AST を出力すべきでない理由は，恐らく Jim Hugunin の経験から来ているのだと思いますが，セマンティクスが大きく異なるものを一足飛びに変換しない，という点が重要そうです．これによってパーサをシンプルに保つことができますし，一旦 AST に変換したあとは，DLR AST への言語言語変換の問題に集中することができるということなのでしょう．
言語とパーサを作る手間すらもどかしい
一方，C# で主にプログラミングを行いながら，高級インラインアセンブラとしての Expression Trees にもの足らない私のような人間にとって，この DLR AST と DLR AST Compiler はとても魅力的です*2．Expression Tree と比較して，DLR AST には以下のような特徴があります．
- DLR AST はソースコードが公開されていて再利用が可能である
- DLR AST は式だけでなく文を含んだ制御構造のテンプレートを持つ
- コードブロックが使える
- 変数が使える
てなわけでここ最近 DLR AST で遊んでいたのですが，高級 Eval のような使い方をしたい場合，Expression Trees よりも DLR AST の方が明らかに使いやすいと感じています．何より，思い描いた手続きをすぐにそのまま書き下せる書き心地が気に入りました．なにせ，パフォーマンス目的のチューニングなどに実行時メタプログラミングの仕組みが欲しいときというのは，言語とパーサを作る手間すらもどかしいぐらいですから．
DLR AST を直接コンパイルする
今回は IronPython 2.0 A8 のバイナリファイル を元に話を進めます．
- IronPython-2.0A8-Bin.zip のダウンロード
- 上記ページから IronPython-2.0A8-Bin.zip をダウンロードして適当なところに展開します．
- 新規プロジェクトの作成
- C# コンソールプロジェクトを作成します．
- Microsoft.Scripting.dll を参照設定に加えます
これで準備は OK です．
最もメタになる「初心者用 Eval」は DLR AST
実際どんなコードを実行してみたのか見てみましょう．
using System; using System.Collections.Generic; using Microsoft.Scripting; using Microsoft.Scripting.Ast; static class Program { static void Main(string[] args) { var cw = typeof(Console).GetMethod("WriteLine", new[] { typeof(string) }); var cb = Ast.CodeBlock("MyFunc", typeof(void)); cb.Body = Ast.Block( Ast.Call(cw, Ast.Constant("Hello, World!")), Ast.Call(cw, Ast.Constant("Hello, World!")), Ast.Call(cw, Ast.Constant("Hello, World!")) ); var dynamicFunc = TreeCompiler.CompileBlock<Action>(cb); dynamicFunc(); } }
こんな感じでコードブロックに 3 回 MethodCallExpression を並べただけのものです．Block メソッドの引数は可変長引数なので，好きなだけコードを並べることができます．この書き味は，まさに使い慣れた手続き型言語でプログラミングしているのとそっくりです．
引数と変数を使ってみる
さらに引数と変数を使ってみるテストです．
(a, b) =>
{
var add = a+b;
var mult = a*b;
return (mult - add);
}
上のような関数を作ってみましょう．サンプルの Main メソッドを次のように書き換えます．
static void Main(string[] args) { var cb = Ast.CodeBlock("calc", typeof(int)); var Par = new { a = cb.CreateParameter(SymbolId.Empty, typeof(int)), b = cb.CreateParameter(SymbolId.Empty, typeof(int)), }; var Var = new { add = cb.CreateLocalVariable(SymbolId.Empty, typeof(int)), mult = cb.CreateLocalVariable(SymbolId.Empty, typeof(int)), }; cb.Body = Ast.Block( Ast.Write( Var.add, Ast.Add( Ast.Read(Par.a), Ast.Read(Par.b) ) ), Ast.Write( Var.mult, Ast.Multiply( Ast.Read(Par.a), Ast.Read(Par.b) ) ), Ast.Return( Ast.Subtract( Ast.Read(Var.mult), Ast.Read(Var.add) ) ) ); var dynamicFunc = TreeCompiler.CompileBlock<Func<int, int, int>>(cb); Console.WriteLine("result = {0}", dynamicFunc(10, 2)); }
ループ
次．ループいってみます．
Func<int, int> fact = (upto) => { if (upto < 1) return 1; var index = upto; var accumulator = 1; for (; index > 0; index = index - 1) accumulator = index * accumulator; return accumulator; };
こんなのを作ります．サンプルの Main メソッドを次のように書き換えます．
static void Main(string[] args) { var cb = Ast.CodeBlock("fact", typeof(int)); var Par = new { upto = cb.CreateParameter(SymbolId.Empty, typeof(int)), }; var Var = new { index = cb.CreateLocalVariable(SymbolId.Empty, typeof(int)), accumulator = cb.CreateLocalVariable(SymbolId.Empty, typeof(int)), }; cb.Body = Ast.Block( Ast.If( Ast.LessThan(Ast.Read(Par.upto), Ast.Constant(1) ), Ast.Return(Ast.Constant(1)) ), Ast.Write(Var.index, Ast.Read(Par.upto)), Ast.Write(Var.accumulator, Ast.Constant(1)), Ast.Loop( Ast.GreaterThan(Ast.Read(Var.index), Ast.Zero()), Ast.Write( Var.index, Ast.Subtract(Ast.Read(Var.index), Ast.Constant(1)) ), Ast.Write( Var.accumulator, Ast.Multiply(Ast.Read(Var.index), Ast.Read(Var.accumulator)) ), null ), Ast.Return( Ast.Read(Var.accumulator) ) ); var dynamicFunc = TreeCompiler.CompileBlock<Func<int, int>>(cb); Console.WriteLine("result = {0}", dynamicFunc(10)); }
まとめ
以上見てきたように，手続き型言語としての C# 1.x の機能と実行速度は，今やほぼそっくりそのまま実行時に再現が可能です．となると問題は，それができると知った上で何を考えるかということになります．
例えば「LINQ to Object のクエリオプティマイズはできますか？」という質問に対して，「できない」と答える人は恐らく出荷された製品としての「LINQ to Object」の機能のことを念頭に置いてそう答えたことでしょう．一方「できる」と答えた人は，C# や .NET の実行環境のポテンシャルが，それを許すかどうかに注目して答えたと考えられます．
個人的に，回答としては後者を推したいです．実行時にハッシュテーブルから等価なメソッドを作って みたり，LINQ to Object のクエリオプティマイザを自作 したりする方面，きっとまだ見ぬ「その発想はなかったわ」がたくさん待ってるんだと思いますよ．
加えて，Silverlight 2.0 でも，DLR AST とその実行時コンパイルが標準でサポートされる方向にあるようです．これでやっと．Web に置いて URL を示して「こんなの作ったよ」が気楽にできるようになるわけですな．今までは JavaScript の特権みたいなものでしたから．変な Hack の発表が非常にやりやすくなるわけで，とても楽しみです．今のように「これとこれとこれをダウンロードして実行してね」で試してくれる人は少ないですから．
今後は言語サンプルもインタラクティブな方向に向かっていくのかもしれませんね．案外，C# 4.0 の発表と同時に Silverlight を使ったコンソールも公開されて，「まあ使ってみれ」みたいなことすらできたりして．
おまけ
この理由により、プロユースのXNA開発者は'90年代のC++プログラマと同じようなコードレベルの最適化技法を用いることが求められる。Xbox 360のXNAプログラムが、「C#」と「.Net Framework」という環境で動作する以上、システムコールによるタイムロスや、実行時型安全や暗黙の配列チェックなどによる「隠れたパフォーマンスロス」が発生するが、これを明示的に避けようというわけだ。
XNA開発において、プログラマが徹底的に最適化したコードは、そうでないコードに比べて、何倍もの高速化が達成される場合もあるという。しかし、そのためのコーディングは、「C#」の便利さを捨てて処理を分解・手動で再構成するものであり、とてもホビーユースとは言えない作業コストになりそうだ。
という記者の感想とは裏腹に，私は今の .NET プログラミングの雰囲気が 90 年代の C++ のそれとはだいぶ違うように思います．
C++ ではやりづらかったタイプのメタプログラミングが，今ではちょっと手を伸ばせば手が届くところまで来ています．それは確かにアカデミックな世界では遙か以前から存在したものですが，万人にとっての道具も動機も揃いつつある今，その古くて新しいおもちゃのエンジンは確実に回転を速めています．もはや，言語やコンパイラは変更のきかない絶対のルールではなく，必要に応じて作ったり拡張する手段がある．そういう目で見ればだいぶ色々なことの見え方がかわってくるんじゃないでしょうか．
んで，まさにこれですよね？
言語仕様だけではなくて、ライブラリやフレームワーク等の関連するソフトウエアや、ドキュメントやコミュニティのあり方や開発の進め方について、つまり、プログラマとしての自分の経験を形作る「環境」全体について、不満があれば変えることができるということを知る。
関連過去記事
参考記事
変更履歴
- 2008年3月2日
- 荒井さんのエントリ『DLRのASTのみを使う』にあるように，素の Microsoft.Scripting.dll を参照設定に加えれば依然として DLR AST の実行時コンパイルは可能なようです．誤報流してすみませんでした．本記事の文章とサンプルコードも TreeCompiler 使用版に変更しました．また，『I love tree』で紹介されている Martin 氏のエントリも非常に参考になります．
- 荒井さんのコメントを受けて Silverlight 2.0 への言及を追加．
