プログラミング言語の中間表現って幅広いと思った話
はじめに
言語処理系の仕組みが面白いと思っていろいろと勉強しています。最近、RustのバックエンドをCraneliftに置き換えて動かすみたいな話があったりして、プログラミング言語の中間表現ってとても幅広く重要な存在になっていると感じたので、ポエム的な記事を書いてみようと思いました。
中間表現とは
まず、プログラミング言語における中間表現とは、何かしらのプログラミング言語で書かれたソースコードを最終的にCPUが実行する機械語に変換するまでの間で使われるデータ形式のことを指します。Intermediate Representation、略してIRと呼ばれることも多いです。つまり、
ソースコード → 中間表現 → 機械語
のようなイメージです。中間表現は複数ある場合も多いので、
ソースコード → 中間表現1 → 中間表現2 → 中間表現3 → ... → 機械語
となることも珍しくないでしょう。
もちろん中間表現を使わなくてもソースコードを機械語に変換することはできます。それでもわざわざ中間表現を導入するのは、その方がプログラムの解析や最適化が効率よく行えるからです。
コンパイラとインタプリタ
上記の中間表現の説明は、どちらかというとコンパイラ型言語に焦点が当たった説明になっていました。コンパイラ型言語はコンパイル時にソースコード全体に対する解析や最適化を行うための十分な時間を確保できます。一方、インタプリタ型言語で同じようなことをしようとしたら、処理の時間がそのままプログラムの実行時間となってのしかかってきてしまいます。
では、インタプリタ型言語に中間表現はないのでしょうか。その答えの前に、コンパイラ型言語とインタプリタ型言語の特徴についておさらいしてみましょう。
-
コンパイラ型言語
ソースコードをコンパイルして動作環境に合わせたバイナリ形式を出力する。バイナリ形式はCPUが直接実行できるため速度は出るが、環境ごとにバイナリ形式をコンパイルする必要がある。 -
インタプリタ型言語
インタプリタがソースコードを読み込んで実行する。ソースコードがあれば様々な環境で動作させられるが、実行時にインタプリタがソースコードを解析して実行するため速度は出ない。
表裏一体のようなメリット・デメリットがありますが、これらの改善にも中間表現が大きく関わっています。
例えば、コンパイラ型言語でも環境に依存しない、ポータビリティのあるバイナリ形式が用意できたらうれしいでしょう。Javaはソースコードを環境に依存しないバイトコードにコンパイルします。バイトコードとは仮想的なCPUのための機械語と考えられます。アセンブリ言語のようなテキスト指向の表現でなく、機械語的なバイト指向の表現であるためバイトコードと呼ばれているようです。このバイトコードは実際のCPUが実行する機械語とは異なるため、一種の中間表現と呼ぶことができるでしょう。バイトコードが生成できれば、あとはそれを環境ごとに用意された実行基盤（Java VM）で実行するだけです。そうすればコンパイラ型言語としての十分な解析や最適化の恩恵を享受した上で、環境によらないバイナリ形式の実行が可能になります。
一方、インタプリタ型言語でも実行速度を改善したいという要望があるでしょう。これにも中間表現が大いに役立ちます。プログラミング言語は人間の開発者が書きやすく読みやすいように設計されていますが、このようなプログラミング言語の表現力は機械が実行するときには足かせになってしまいます。人間が扱いやすい表現から機械が扱いやすい表現に変換する必要が出てくるからです。だったらそのような表現力を排除した中間表現に変換し、その中間表現をインタプリタで実行すればいいのです。このような手法は、まるで存在しない仮想的なCPU環境のための機械語を出力し、その機械語を仮想マシンがシュミレーション的に実行していると考えることもできるため、VM型インタプリタと呼ばれます。この手法は大変有効なもののようで、現在の主要なインタプリタ型言語（Python、Rubyなど）はほぼVM型の実装になっているようです。
このように両者の改善手法を見比べると、最初の目的は違っても結果的に同じような方向性に近づいているのが面白いです[1]。言葉的にも、Javaの実行基盤に「VM」と付いていたり、インタプリタ型言語の仮想的な機械語もバイトコードと呼ばれたりして、多くの一致が見られます。
コンパイラ基盤
再びコンパイラに視点を移しましょう。先程の話はプログラムの実行時に使われる中間表現でしたが、今度はバイナリ形式を生成する際の中間表現について考えてみます。上述したようにプログラムをコンパイルすると最終的には機械語が出力されます。機械語はCPUによって異なる体系を持つため、複数のCPUに対応しようとする場合は当然CPUごとに処理を分ける必要があります。例えば、C言語のコンパイラはIntel用の処理、ARM用の処理、PowerPC用の処理、といった感じでサポートする全てのCPUに対する処理を作らなければならないわけです。もちろんC言語のコンパイラはいくつもありますし、別のプログラミング言語であればまた異なるコンパイラが必要です。それぞれのコンパイラにおいて同様に様々なCPUの処理を作っていくことになり、考えただけでも大変です。
こういった課題を解決する手法のひとつが、コンパイラ基盤という考え方です。中でもLLVMは有名で、各所で使用されている話を聞いたことがあるのではないでしょうか。コンパイラ基盤は、それ用の中間表現を入力とします。LLVMであれば、LLVM IRと呼ばれる形式です。中間表現は仮想的なCPUに対応するアセンブリ言語のようになっていて、コンパイラ基盤はその仮想的な命令を実在するCPUの命令に変換する役割を果たします。ついさっき聞いたような話ですね。そのためLLVMも「VM」と付くのかもしれません[2]。ちなみに、コンパイラ基盤の中間表現は機械語のようなバイトコードではなく、アセンブリ言語のようなテキスト指向の形式であるようです。これは、中間表現の使われ方として、実行ではなく解析に重きが置かれているからなのかもしれません。
コンパイラ基盤のおかげで、コンパイラの開発者はソースコードからコンパイラ基盤の中間表現を出力するところまでを受け持つだけでよくなります。無数のCPUに対応する処理をコンパイラごとに実装する必要はないわけです。結果として、コンパイラの開発者は本来やりたかったであろうプログラミング言語そのものの機能やその解析に、十分な開発力をつぎ込むことができます。
コンパイラ基盤を使用したコンパイラでは、ソースコードから中間表現を出力するまでをフロントエンド、中間表現から機械語を出力するまでをバックエンドと呼びます。LLVMをバックエンドとして使っているコンパイラはC言語向けのClang、Rustの公式コンパイラrustcなど、数多く存在しています。
WebAssembly
WebAssemblyとは、Webブラウザ上で動作するバイナリ形式、というのが主な認識ではないでしょうか。現状JavaScriptで記述されている処理において、特に処理が重い部分をより高速に実行するために使われることが想定されます。WebAssemblyはアセンブリと付いていますが特定のCPUの機械語を表すわけではなく、実行時に動作環境に対応する機械語に変換されます。つまりWebAssembly自体は仮想的な機械語となっており、これも中間表現の一つと言って差し支えないでしょう。
さて、WebAssemblyはWebブラウザ上で動作することを最初の目的としていたと思います。それが中心的な目的であることは今も変わらないと思いますが、一方でWebブラウザから離れた使い方への期待も高まっているようです。それは、CPUなどの環境によらない汎用的なバイナリ形式としての使い方です。WebAssemblyは仮想的な機械語であり特定のCPUに依存しないため、WebAssemblyの実行環境さえあれば、ひとつのバイナリ形式を様々な環境で実行することが可能になります。
そのようなWebブラウザではない実行環境も開発が進んでおり、例えばwasmtimeなどがあります。また、wasmtimeのような実行環境においてWebAssemblyからOSへアクセスするインターフェース仕様を定めたWASIという規格も同時に進行中のようです。Webブラウザ上でWebAssemblyを動かす場合、OSの機能へのアクセスはWebブラウザを経由して行えますが、そうでない実行環境の場合は別のアクセス方法を使う必要があるためです。
ここまでを読むと、Webブラウザから離れたWebAssemblyは、Javaと同じような理想を掲げているようにも見えます。WebAssemblyはJavaのバイトコードに対応し、wasmtimeのような実行環境はJava VMに対応します。そして今の所WebAssemblyにおけるこの理想は、Javaよりも順調に進みそうに見えます。WebAssemblyが様々な言語からコンパイルされる前提であることや、複数企業が協力して作ったオープンな規格であることが関係しているのかもしれません[3]。
RustとCranelift
最後に、この記事を書こうと思ったきっかけである、RustとCraneliftの関係についても触れてみたいと思います。Craneliftとは、上述したwasmtimeで使用されている機械語生成器です。WebAssemblyの命令を実際のCPUの機械語に変換する役割を持っています。内部的には、WebAssemblyから直接機械語を生成するのではなく、まずCranelift IRと呼ばれる専用の中間表現に変換した後、機械語への変換を行います。つまりCraneliftは、Cranelift IRから様々なCPUの命令列を出力するコンパイラ基盤と見なすことができ、LLVMと同等の機能を持つと言えます。
RustではデフォルトでLLVMがコンパイラのバックエンドとして使われますが、それをCraneliftに置き換えても使えるようにするという実験的な計画があります。なぜそんなことをするかというと、コンパイル時間の短縮のためです。LLVMは高度に最適化されたバイナリ形式を出力するため、コンパイルに時間がかかるという欠点を持っています。CraneliftはLLVMと比べ単純な作りであるため、コンパイルにかかる時間は短くなります。特に、LLVMは内部でさらに複数の中間表現を持っているのに対して、Craneliftは単一の中間表現しか持っていないことが大きく影響しているようです。
コンパイル時間の短縮は、特にソフトウェアのデバッグや開発のフェイズにおいて、大きなメリットとなります。そういったフェイズでは、小さい変更を行ってコンパイルして動作を確認するというプロセスを何度も繰り返すため、出力されたバイナリ形式の実行速度より、コンパイルの速さのほうが開発効率に及ぼす影響が大きいからです。
RustコンパイラでCranelift IRを出力するモジュールは独立したリポジトリで管理されているようですが、現在はRustコンパイラのソースにも含まれるようになっています。まだ自分では動かせていないのですが、時間があるときに試してみたいと思います。
Discussion