構文木の評価=プログラムの実行

字句解析、構文解析を経て構文木ができあがったら、そこからインタプリタの完成まではそう遠くない。というか、構文木を直接評価、実行するタイプ中間コードとか吐かないタイプの、素朴なインタプリタ構文木を直接実行するタイプ)であれば、

できあがった構文木を評価する=プログラムを実行する

ということなので、

構文木が作れた時点でほぼ勝負は決まっている。「いまどきのプログラム言語の作り方」で作ったインタプリタもまさにそのタイプだったし、確か現在の Ruby の処理系もそうだったはず*1だ。だから、とにかく手っ取り早く、実際に動く(自作言語の)インタプリタが作りたいのであれば、要は構文木が作れるところまで到達できればいい。コード生成とか、コード最適化のお話は、とりあえずは必要ない。

ただ、いくら簡単にインタプリタが作れるとはいえ、文を実行するたびに構文木を評価するというやり方は、プログラムの実行速度という点ではかなり分が悪い。

何百回、何千回と回るループがあったとすると、そのループ内の文を表現している構文木は、ループの回数だけ評価されることになるが、その際、関数の再帰呼び出しが一体何回必要になるか*2、というようなことを考えてみれば、その辺の効率の悪さは容易に理解できる。

そんなわけで、最近のインタプリタの多くは、直接構文木を評価、実行するということをせず、プログラムをいったん後置コードなどの(インタプリタでの解釈実行に向いた)中間コードへとコンパイルし、それをその中間コードのインタプリタ仮想マシン)で実行する、というようなことを内部でこっそり行っている。そして、そういうやり方をコンパイラインタプリタ方式とかいう。
  ↑
ここから先はこれから勉強するんで、まだよくわかってないのだが、木という再帰的な構造をフラットでライナーなコード列に置き換えることにより、木をトレースするコストが取り除かれ、その分プログラムの実行を高速にできるとか、そういうことなのかな。

自作言語のインタプリタはできるだけ高速な方がいい! という場合、必然的に中間言語だとか、バイトコードだとか、コード生成、コード最適化、仮想マシン、とかいったことについて、さらに勉強しないといけないわけなんだが……

その先はまだ未習*3なので、今日はここまで。

*1:だから今、Ruby の高速化を目指して YARV とか作ってるんだよね?

*2:関数の呼び出しコストも馬鹿にならない。塵も積もれば何とやらだ。

*3:実はまだ逆ポーランド記法関数電卓しか作ったことがない…… 情けなや。