原題 "Modern compiler implementation in ML"
ML(Meta-Language)とは、Algol 系の言語で、高次の視点、すなわちメタ視点から言語を論じる場面に適しているという。本書は、プリンストン大学のコンパイラ講座に沿った教科書だそうな。アンドリュー・エイペルは、自ら提唱する Tiger 言語を ML で実装するストーリーを描いて魅せる。
ちなみに、「Tiger 言語リファレンスマニュアル」を覗いてみると、文脈的な依存関係があまりなく、コンパクトな命令型言語とお見受けする。ソフトウェア工学をプリミティブなレベルから学ぶには、恰好な題材やもしれん...
尚、神林靖、滝本宗宏訳版(翔泳社)を手に取る。
コンパイラと言えば、実行可能なマシン語への翻訳機とでも言おうか。むか～し、おいらが美青年と呼ばれた時代、日本語プログラミング言語に憑かれ、アセンブラ言語のマクロ機能を駆使して翻訳機を書いた頃の記憶がかすかに蘇る。
当時、C言語が主流となりつつあったが、コンパイラ性能はイマイチだし、リソースもしょぼい。リアルタイムシステムでは、まだまだアセンブラ言語に頼らざるを得ない時代であった。
現在、スクリプト言語が華やかに台頭する。言語の分かりやすさや柔軟性は、プログラムのメンテナンスに欠かせないが、人間にとっての分かりやすさと、マシンにとっての効率性は相い反するところがある。実は、根底で密かに活動する翻訳機の存在意義は、以前より増しているのやもしれん。自然言語で機械翻訳が活躍しているように...
コンパイル処理の流れは、お決まりなところがある。字句解析、構文解析、意味解析、データ構造解析、中間言語による抽象化、命令セットの割り当て、レジスタやメモリの割り当て、実行可能なコードの生成... といったところ。
本書は、こうしたトピックに加え、オブジェクト指向型言語のコンパイラ "Object-Tiger" と、関数型言語のコンパイラ "Fun-Tiger" の実装例を紹介してくれる。
まずは、コンパイラの理想像を描いてみるのもいい。抽象レベルでは、無限のレジスタやメモリ、最も効率的な命令セットを想定することもできる。これらを現実のリソースに割り当てるの時、効率的な割り当てがコンパイラの性能にかかってくる。
本書は、こうした視点に付随して、多くの仕掛けやアルゴリズムを紹介してくれる。注目したい話題は、「静的単一代入形式、高階関数、ごみ集め、パイプライニングとスケジューリング」といったところ...
1. 静的単一代入形式
すべてのデータの流れや経緯を単純な代入で組み立てていく記述様式で、集合論的な視点を与えてくれる。人間の思考は言語学的な視点に着目するが、コンピュータは数学的な構造を持っており、集合論的な記述が効率的。データの生存解析にも有効で、ゴミ集めのための情報としても活用できる。
2. 高階関数
関数の入れ子になる仕組みで、引数に関数を渡すことができ、結果に関数を返すこともできる。スコープの入れ子も含めて,,, こうした性質は Tiger 言語の特長でもあり、コンパイラの実装で有用だという。
3. ごみ集め
この機能はコンパイラが持つべきかは微妙だが、ごみ判定のための支援をコンパイラがやってくれると助かる。
そもそも、ごみとは何か？本書では、「ヒープに割り当てられたれコードのうち、プログラム変数からポインタと連鎖を辿って到達できないもの...」と定義される。
お馴染みの静的コンパイルでは、到達可能かどうかの判定をコンパイラ側でやって、あとは、ガベージコレクション側に任せることもできる。
だが、ランタイム時に実行するような動的コンパイルでは、ごみ集めの機能も組み込みたい。ごみ処理機構は人間社会同様、システムの秩序に影響を与え、致命的な問題ともなりかねない。ちなみに、新種のプログラミング言語は多くのごみを出すらしい。
そこでアルゴリズムでは、ガベージコレクションの文献でも見かける「マークスイープ回収法」、「参照カウント」、「Cheney のアルゴリズム」、「世代別回収法」、「Baker アルゴリズム」などが紹介される。
4. パイプライニングとスケジューリング
要するに、時分割並列処理を行うための仕掛け。あらゆるデータや命令セットを完全に平等に配置できれば、並列処理が効率的に分配でき、マルチコア環境をフル活用できるだろう。
だが、データも命令セットも、生存条件や処理順などの依存関係を持っている。データの先読みや先行処理を効率的にやるにしても、レジスタは有限だし、メモリも有限だ。メモリの多重構造までもプログラマに意識させるのも酷だし、キャッシュ構造も考慮したい。
おまけに、対象となる言語仕様との兼ね合いも絡むとなれば、コンパイラの仕事はますます増えるばかり。こうした事を意識せずにプログラムが書けるようになったのも、彼ら縁の下の力持ちのおかげ。ありがたや！ありがたや！
