この文書は、The Architecture of Open Source Applications Volume II: Structure, Scale, and a Few More Fearless Hacksに収録されているThe Dynamic Language Runtime and the Iron Languagesの日本語訳です。原文と同様、日本語訳もcc-by unported 3.0によって公開されます。
…半分やったらくたびれたので、とりあえず前半だけで公開 → 後半できました
追記: gist.io あるいは github gist でも読めるようにしました。
動的言語ランタイム（DLR）とIron言語
Jeff Hardy (原文) / Atsushi Eno (日本語訳)
Iron言語は、IronPythonをはじめとして、"Iron"を名前に含む、各種言語実装の非公式な集合体です。これらの言語には、少なくともひとつ共通していることがあります。これらは、共通言語ランタイム（CLR）を対象とする動的言語であり、動的言語ランタイム（DLR）の上に構築されています。CLRは、むしろ.NET Frameworkとして知られているでしょう。（"CLR"はより汎用的な用語です。.NET FrameworkはMicrosoftの実装であり、この他にオープンソースの実装であるMonoがあります。） DLRは、CLR上で動的言語を高度にサポートするための、CLR用ライブラリの集合体です。IronPythonとIronRubyは、何十ものクローズドソースあるいはオープンソースのプロジェクトで使用されており、いずれもアクティブに開発されています。DLRは、オープンソースプロジェクトとして始められましたが、これは.NET FrameworkとMonoの一部となっています。
アーキテクチャとしては、IronPython、IronRuby、DLRは、単純でもあり、悪魔的なまでに複雑でもあります。高水準なところでは、その設計は他の多くの言語実装に似ており、パーサ、コンパイラー、コードジェネレーターから成っています。しかし、少し近寄ってみると、その面白い詳細部分が顔を出してきます。コールサイト（call sites）、バインダー、適用的コンパイル（adaptive compilation）、その他各種技術によって、静的言語用に設計されたプラットフォーム上でも、動的言語が静的言語にほぼ匹敵するパフォーマンスを出せるようになっています。
8.1. 歴史
Iron言語の歴史は2003年に始まります。 Jim Huguninは、この時すでに、Java仮想マシン（JVM）用に、Jythonと呼ばれるPythonの実装を書いていました。一方その頃、.NET Frameworkの共通言語ランタイム（CLR）は、Pythonのような動的言語を実装するのには適していない、と考えられてきました（誰によって、というと定かではありませんが）。既にJVM用にPythonを実装していたJimは、なぜMicrosoftが.NETをJavaよりずっと劣るものに作り上げられるのか、不思議に思っていました。2006年9月のブログの投稿で、彼は次のように書いています:
私は、MicrosoftがどうやってCLRをJVMよりも動的言語の用途に劣るプラットフォームとして作り上げることが出来たのか、理解したかった。私の計画は、CLR上で動作するPython実装のプロトタイプを数週間かけて構築し、それを用いて「CLRが動的言語に全然向かないプラットフォームである理由」とすっぱりと題した記事を書く予定だった。このプロトタイプに着手してほどなく、私の計画は変更となった。Pythonは、CLR上で非常に優れた動作を見せたのだった。多くのケースで、Cベースの実装よりも著しく高速だった。標準のpystoneベンチマークにおいて、CLR上のIronPythonは、Cベースの実装より1.7倍くらい高速だった。
（名前の"Iron"という部分は、Jimの当時の会社名である、Want of a Nail Softwareの名前からの言葉遊びで付けられています。）
[訳注: これは "for want of a nail" という「一本の釘が足りないことで蹄鉄がダメになり、蹄鉄がダメになったことで馬が走らなくなり、馬が走らなくなったことで伝令が動けなくなり、伝令が機能しなかったことで戦に敗れ、戦に敗れたことで国が滅びた。一本の蹄鉄の釘が原因だったのだ」という詩に由来する。]
ほどなく、Jimは、.NETをより動的言語に適したプラットフォームとするべく、Microsoftに雇われることになりました。Jim（そしてその他の多くの人々）は、もとのIronPythonのコードから、言語中立の要素を抜き出して、DLRとしました。DLRは、.NET用の動的言語を実装するための共通のコアを提供するべく設計され、.NET 4の主要な新機能となりました。
（2007年4月に）DLRがアナウンスされた時、Microsoftは、DLR上で動作する新しいバージョンのIronPython（IronPython 2.0）と同時に、DLRの多言語の適用可能性を示すべくIronRubyをDLRに基づいて開発することもアナウンスしました。（2010年10月に、MicrosoftはIronPythonとIronRubyの開発を停止し、これらは独立したオープンソースのプロジェクトとなりました。） DLRを用いた動的言語との統合は、C#およびVisual Basicにとっても主要な部分となり、新しいキーワード（ dynamic ）が、DLRで実装された言語や任意の動的データソースの呼び出しを、簡単に出来るようにしました。CLRはすでに静的言語を実装する良いプラットフォームでしたが、DLRがこれらの言語を一級市民として押し上げたのです。
Microsoft外部でも、IronSchemeやIronJSといった、DLRを使用した言語実装があります。さらに、MicrosoftのPowershellバージョン3では、その独自の動的オブジェクトシステムの代わりにDLRを使用します。
8.2. 動的言語ランタイムの原則
CLRは、静的言語を前提に設計されています。型に関する情報は、ランタイムの奥深くにまで焼き付けられており、そのキーとなるひとつの前提として、型は変化しないということが挙げられます。変数はその型を変更することはなく、また、型はプログラムの実行中にフィールドやメンバーを追加されたり削除されたりすることはありません。これはC#やJavaのような言語においては問題ありませんが、動的言語は、定義上、これらの規則に従いません。また、CLRは、静的な型の共通オブジェクトシステムを提供しており、これによって、いかなる.NET言語も他の.NET言語によって書かれたオブジェクトを、特別な作業を要することなく呼び出すことができます。
DLRが無い場合、すべての動的言語が、独自のオブジェクトモデルを提供しなければならなかったでしょう。各種の動的言語が、他の動的言語で書かれたオブジェクトを呼び出すことはかなわず、C#からIronPythonやIronRubyを等しく扱うこともできなかったはずです。すなわち、DLRの中核は、動的オブジェクトを実装しつつ、バインダーを用いて言語独自の振る舞いをカスタマイズすることを可能にする、標準化された方法なのです。これには、動的な命令を可能な限り高速化できるようにするコールサイトキャッシュと呼ばれるメカニズムや、コードをデータとして簡単に操作できるようにする式ツリーを構築するためのクラス群も含まれます。
CLRは、動的言語を便利にするための機能もいくつか提供しています。高度なガベージコレクター、.NETのコンパイラーが生成する共通中間言語（IL）バイトコードを実行時にマシンコードに変換するジャストインタイム（JIT）コンパイラー、そして最後に、実行時にコードを生成され静的メソッド呼び出しよりもわずかに多いオーバーヘッドのみで実行できる動的メソッド（または軽量コード生成）があります。（JVMは、Java 7で invokedynamic という類似の機能を得ました。）
このDLRの設計の成果として、IronPythonやIronRubyのような言語は、共通の動的オブジェクトモデルを使用することによって、互いの（そして他の任意のDLR言語の）オブジェクトを呼び出せるようになりました。このオブジェクトモデルのサポートは、C# 4で（ dynamic キーワードによって）、またVisual Basic 10で（VBの既存の「遅延バインディング」の手法に加えて）追加され、同様にこれらのオブジェクトに対する動的な呼び出しを実行できるようになりました。こうしてDLRは、動的言語を.NETにおける一級市民としたのです。
面白いことに、DLRは完全に.NET 2.0上でもビルドして実行できるライブラリの集合体として実装されました。これを実装するために、いかなるCLRの変更も必要ではなかったというわけです。
8.3. 言語実装の詳細
どの言語実装にも、ふたつの基本的なステージがあります。パース（フロントエンド）とコード生成（バックエンド）です。DLRにおいては、それぞれの言語が独自のフロントエンドである言語パーサーと文法ツリー生成を実装します。DLRは式ツリーを受け取ってCLRが利用できるような中間言語（IL）を生成する共通のバックエンドを提供します。CLRはこのILを、プロセッサが実行するマシンコードを生成するジャストインタイム（JIT）コンパイラーに渡します。実行時に定義される（および eval を用いて実行される）コードも同様に処理されますが、全てはファイルの読み込み時ではなく eval のコールサイトで行われます。
言語のフロントエンドの主要な部分を実装する方法はいくつかあり、IronPythonとIronRubyが非常に似ているにもかかわらず（実のところこれらは並行して開発されていたわけです）、これらはいくつかの主要な部分を異にしています。IronPythonもIronRubyもきわめて標準的なパーサーの設計を用いており、テキストをトークンに分割するトークナイザー（あるいは lexer ）と、トークンをプログラムを表す抽象構文ツリー（AST）に変換するパーサーを利用しています。しかしながら、これらの言語はそれらの実装を完全に別々にしています。
8.4. パース
IronPythonのトークナイザーは IronPython.Compiler.Tokenizer クラスにあり、パーサーは IronPython.Compiler.Parser クラスにあります。 トークナイザーはPythonのキーワード・演算子・名前を認識して対応するトークンを生成する手書きのステートマシンです。それぞれのトークンには、任意の追加情報（定数値や名前など）と、そのトークンのソース中の位置が、デバッグの補助情報として含まれます。そして、パーサーは、このトークンの集合を受け取って、Python文法に基づいて解読し、正しいPython生成規則に従っているかを判断します。
IronPythonのパーサーはLL(1)の再帰下降構文パーサー（recursive decent parser）です。このパーサーは入力トークンを見て、そのトークンが許容されるか判断する関数を呼び出し、許容されない場合はエラーを返します。再帰下降構文パーサーは、相互に再帰的な関数の集合から構築されます。これらの関数は究極的にはひとつのステートマシンを実装することになり、それぞれの新しいトークンがひとつの状態遷移をトリガーします。トークナイザーと同様に、IronPythonのパーサーは手書きで作られています。
一方、IronRubyは、Gardens Point Parser Generator（GPPG）が生成したトークナイザーおよびパーサーをもっています。パーサーは Parser.y ファイル（ Languages/Ruby/Ruby/Compiler/Parser/Parser.y ）に記述されています。これは、文法を記述する規則に基づいて、IronRubyの文法を高レベルで記述した yacc フォーマットのファイルです。GPPGは Parser.y を受け取って、実際のパーサー関数およびテーブルを作成します。この出力はテーブルに基づくLALR(1)のパーサーとなります。生成されたテーブルは整数の長い配列群で、それぞれの整数が状態を表します。このテーブルは、現在の状態と現在のトークンから、次にどの状態に遷移するかを決定します。IronPythonの再帰下降パーサーは非常に読みやすいものですが、IronRubyの生成されたパーサーはそうではありません。遷移テーブルは膨大なもので（540種類の状態と45,000の遷移）、これを手作業で修正するのはほぼ不可能です。
結局のところ、これはエンジニアリングのトレードオフです。IronPythonのパーサーは手作業で修正するのは簡単ですが、言語の構造を曖昧にしてしまう程度には複雑です。一方、IronRubyのパーサーは、 Parser.y ファイルで言語の構造を理解するのは簡単ですが、サードパーティのツールに依存してカスタムの（とはいえほぼ既知ですが）ドメイン固有言語（DSL）を使用し、それ特有のバグや独自性に悩まされることになります。この場合、IronPythonチームは外部ツール依存性に踏み込みたくはなく、一方でIronRubyチームはそれを気に病まなかったということです。
とはいえ、いかなるフェーズの解析においても、ステートマシンが重要であることは明らかです。いかなる解析タスクにおいても、それがどれだけ簡単なものであっても、ステートマシンが常に正しい解なのです。
どちらの言語についても、パーサーの出力結果は抽象構文ツリー（AST）です。これはプログラムの構造を高レベルで記述するもので、それぞれのノードは言語の生成規則である、文または式に対応します。これらのツリーは、実行時に操作でき、時としてコンパイル前にプログラムの最適化が施されます。しかしながら、言語のASTはその言語に密接に結びついています。DLRは、いかなる言語独自の生成規則も含まない、汎用的なもののみを含むツリーを、操作する必要があります。
8.5.式ツリー
式ツリーもまた、実行時に操作できるプログラムの表現ですが、より低レベルな、言語独立の形式です。.NETでは、ノードの型は System.Linq.Expressions ネームスペースにあり、全てのノードの型は抽象型 Expression クラスから派生します。（このネームスペースには歴史的な背景があります。式ツリーは、もともとは.NET 3.5でLINQこと言語統合クエリを実装するために追加されたもので、DLRの式ツリーはこれを拡張したのです。） これらの式ツリーは、実のところ、単なる式以上のものをカバーしており、 if 文や try ブロックや、ループなどのノードの型もあります。言語によっては（たとえばRubyでは）、これらは式であって、文ではありません。
これらは、ひとつのプログラミング言語で必要とされるであろう、ほぼすべての機能をカバーするノード群です。しかしながら、これらは得てして低レベルに定義されています。 ForExpression や WhileExpression などといったものの代わりに、 LoopExpression がひとつだけ存在しており、 これは GotoExpression と組み合わせることによって、どの種類のループも記述することができます。言語をより高レベルで記述するために、言語では、その独自のノードを、 Expression から派生して、Reduce() メソッドをオーバーライドして別の式ツリーを返すようにすることで、定義できます。IronPythonでは、その解析ツリーもまたDLR式ツリーですが、これはDLRが通常は解さないようなカスタムノードを数多く含んでいます（たとえば ForStatement など）。これらのカスタムノードは、DLRが理解できるようなかたちの式ツリー（ LoopExpression と GotoExpression の組み合わせなど）に解消（reduce）することができます。カスタム式ノードは、別のカスタム式ノード群に解消でき、この解消処理は、DLRに内在するノードのみが残るように、再帰的に行われます。IronPythonとIronRubyの大きな違いの一つは、IronPythonではASTもまた式ツリーであるのに比べ、IronRubyではそうなっていないということです。IronRubyでは、ASTは次のステージに進む前に式ツリーに変換されます。ASTが式ツリーでもあることが実際に有用であるか否かは、議論の余地があり、IronRubyはそのような実装を行わなかったということになります。
各ノードの型は、自身を解消する方法を知っており、そして一方向にのみ解消できます。ツリーの外側のコードによる変換処理、たとえば定数折り畳み（constant folding）最適化や、Python生成系のIronPython実装、においては、 ExpressionVisitor のサブクラスが使用されます。 ExpressionVisitor には Visit() メソッドがあり、これは Expression クラスの Accept() メソッドを呼び出し、その Expression のサブクラスは Accept() をオーバーライドして、VisitBinary() など、 ExpressionVisitor の個別の Visit() のメソッドを呼び出します。これは、訪問（visit）できる限られた型のノード群と、それに対する無限数の操作から成る、教科書的なGammaらのVisitorパターンの実装です。式ビジターは、ノードを訪問して、通常は再帰的にその子ノード群を訪問し、さらにその子ノード群、さらにその子…と、ツリーを下降的に辿ります。しかし、 式ツリーは不変（immutable）なので、ExpressionVisitor は、自らが訪問しているツリーに手を加えることはできません。もしこの式ビジターがノードを修正する必要がある場合は（子を削除する場合など）、その古いノードを置き換える新しいノードと、その（子の）親を同様に生成してやる必要があります。
いったん式ツリーが生成され、解消され、訪問されると、これは最終的に実行される必要があります。 式ツリーは直接ILコードにコンパイルすることができますが、IronPythonとIronRubyでは、これらをまずインタープリターに渡します。直接的なILへのコンパイルはコストがかかるもので、ほんの数回しか実行されないかもしれないコードにはもったいないのです。
8.6. インタープリットとコンパイル
.NETのように、JITコンパイラを使うことの問題点のひとつは、 起動時に、ILバイトコードをプロセッサが実行できるマシンコードに変換するのに時間がかかるということです。JITコンパイルでは、インタープリタに比べると実行速度は非常に速いですが、やろうとしていることによっては、初期コストがひどく高いということがあります。たとえば、Webアプリケーションなど長時間生存するサーバープロセスでは、起動時間はほぼ無関係で、リクエストごとの時間こそがクリティカルであり、同一のコードを反復的に実行する傾向があるので、JITの利益を享受します。一方で、めったに実行することはないが短時間で実行されるプログラム、たとえばMercurialのコマンドラインクライアントなどは、短い起動時間の方が重要であり、僅かなコードを一度だけ実行することが多く、JITされたコードが速いなどという事実は、より長い起動時間がかかるという事実に勝るものではないからです。
.NETは、ILコードを直接実行することは出来ません。常にマシンコードにJITコンパイルされ、これには時間がかかります。特に、プログラム起動時間は、多くのコードがJITコンパイルされなければならない.NET Frameworkの弱点の一つです。静的な.NETのプログラムについては、このJITペナルティを回避する方法がありますが（ネイティブイメージ生成、NGEN）、これは動的プログラムには機能しません。IronRubyとIronPythonでは、常に直接ILにコンパイルする代わりに、JITコンパイルされたコードほど高速ではないけど起動にかかる時間が著しく少ない、自前のインタープリター（ Microsoft.Scripting.Interpreter にあります）を使用します。このインタープリターは、たとえばモバイルプラットフォームなど、動的コード生成が許されていない状況においても有効です。そうでなければ、DLR言語は全く実行できないことになります。
実行前に、式ツリー全体が、実行可能になるように、ひとつの関数の中にラップされなければなりません。DLRでは、関数は LambdaExpression ノードとして表現されます。ほとんどの言語において、ラムダは匿名関数ですが、DLRには名前の概念がありません。全ての関数は匿名です。この LambdaExpression だけが、 Compile() メソッドによってデリゲートにコンバートできるというユニークな特徴を有しています。delegateは、.NETが関数として呼び出すことができる一級市民です。デリゲートは、Cの関数ポインタに近い存在で、実態は呼び出し可能なコードの断片を指す、単なるハンドルです。
最初に、式ツリーは LightLambdaExpression の中にラップされ、これもまた実行可能なデリゲートを生成出来ますが、それはILコードを生成する（従ってJITを呼び出す）代わりに、式ツリーをコンパイルしてインタープリタの簡単なVMで実行できるような命令のリストを生成するものです。このインタープリターは、簡単なスタックベースのものです。命令は、スタックから値を取り出して、演算を実行し、結果をスタックに格納します。それぞれの命令は Microsoft.Scripting.Interpreter.Instruction から派生したクラスのインスタンスであり（たとえば AddInstruction や BranchTrueInstruction ）、それらは、スタックから値をいくつ取り出して、いくつ格納するかを示すプロパティや、スタックから取り出して命令を実行し値を格納して次の命令へのオフセットを返す Run() メソッドを有しています。このインタープリターは、命令のリストを受け取って、それらをひとつずつ実行し、 Run() メソッドの戻り値に応じて前後にジャンプします。
コードの断片が一定回数実行されると、これは LightLambdaExpression.Reduce() を呼び出すことによって完全な LambdaExpression にコンバートされ、そして（ちょっとした並列処理を伴うバックグラウンドスレッド上で） DynamicMethod デリゲートにコンパイルされ、古いデリゲートのコールサイトは、新しい高速なものに置き換えられます。これによって、プログラムのmain関数など、数回だけ実行される実行関数のコストが大幅に減少し、一方で共通的に呼び出される関数は可能な限り高速に実行できるようになります。デフォルトでは、このコンパイルの閾値は32回の実行ですが、これはコマンドラインオプションやホストプログラムによって変更でき、あるいは、コンパイルないしインタープリターを完全に禁止することもできます。
インタープリタで実行するか、あるいはILへコンパイルするかを、これらの言語の命令が、式ツリーコンパイラーによってハードコードされることはありません。むしろ、コンパイラは、動的かもしれない各命令（というのは実のところほぼすべて）について、コールサイトを生成します。これらのコールサイトは、パフォーマンスを高水準に維持しつつ動的な振る舞いを実装する機会を、オブジェクトに与えます。
