夏から秋にかけて、会社の仕事が大変アレな状態でして、 ずいぶん長いこと放置してしまいましてすみません。
さて、ここまで、型なし・解析木実行型の「crowbar」 という言語を作ってきましたが、 crowbarは(実用言語としてはさておき)サンプルプログラムとしては 一通りの機能が揃ったと思いますので、 放置明けで唐突ではありますが、今回から新しい言語を作ります。
言語の名前は「Diksam」です。
この名前は、「パールのようなもの」とかいったネタではなく、 私が好きな紅茶の名前です。 コーヒー言語のJavaがあるのだから、紅茶言語があってもよいのではないかと ※1。 Diksamはアッサム系の紅茶で、 コクのある重めの紅茶です。
crowbarは、変数が型を持たず、解析木を直接実行するタイプの言語でしたが、 Diksamは、静的な型付けがあり、バイトコードを実行する言語とします。
そのような言語は、crowbarのような言語に比べ、 以下のような利点があります。
バイトコードとは、 仮想マシン(Virtual Machine)という仮想的なCPUが実行する 機械語のようなものです。機械語はCPUが直接実行しますが、 バイトコードは、仮想マシンというプログラムが実行します。
バイトコードは、機械語同様、その実体は単なる数字の並びですが、 (これまた機械語同様)人間にとってわかりやすくするために、 各命令にニモニックという文字列表現を与えた形で表現します。
たとえばJavaの仮想マシン(JVM)が実行するバイトコードは 以下のようになります (この企画の最初の記事から再掲)。
0: bipush 10 2: istore_1 3: iload_1 4: bipush 10 6: if_icmpne 20 9: getstatic 12: ldc 14: invokevirtual 17: goto 28 20: getstatic 23: ldc 25: invokevirtual
人間にとってわかりやすくするために文字列表現を与えたものでさえ、 こんなワケのわからん代物では、ソースをもとにこれを生成するなど 夢のまた夢、バイトコードを生成するコンパイラなんか作れるはずがない ――と思ってしまうかもしれませんが、 実際はそんなに難しいものでもありません。 具体的にどのようにするかは以下で説明します。
crowbarはver.0.2から演算途中の値をスタックに積むようになりました (GCがポインタを確実に追跡するため)。 この時点で、バイトコードを実行する言語とほぼ同じことを実現していました。 こちらで以下のように書いた通りです。
実のところこれは、JVMのようなスタックマシンが、 バイトコードを実行していく際のスタックの動きと同じです。 つまり、ここまでやってしまえば、バイトコードインタプリタまでもう一歩です。
具体的には、解析木を深さ優先で辿って、以下のようなコードを生成します。
たとえば、
1 + 2 * 3 - 4
という式は、以下のような解析木に展開されます。
この解析木を帰りがけ順で辿りながら、 定数のノードでは「push 値」というバイトコードを、 演算子のノードではその値のバイトコードを出力すると、 以下のようなコードとなります(これは説明用の擬似コードです。 JavaのバイトコードでもDiksamのバイトコードでもありません)。
1: push 1 # 「1」をスタックに積む 2: push 2 # 「2」をスタックに積む 3: push 3 # 「3」をスタックに積む 4: mul # スタックのてっぺんのふたつの要素を掛け、結果をスタックに積む 5: add # スタックのてっぺんのふたつの要素を足し、結果をスタックに積む 6: push 4 # 「4」をスタックに積む 7: sub # スタックのふたつめの要素からてっぺんの要素を引き、結果をスタックに積む
式に出てくるのは二項演算子だけではありませんが、 たとえば単項演算子でも考え方は同じです。 単項マイナス演算子であれば、「スタックのてっぺんの値を取り出し、 符号を逆転させてまたスタックに積む」という操作になります。
ところで、上記の例では整数しか扱いませんでした。 実際の言語では実数も必要ですし、「整数と実数を足す」といった 混合演算が可能です。 このような場合は、整数の側をいったん実数に変換してから 実数同士で加算を行ないます。 文字列と整数の加算もできる ※2言語では、 整数をいったん文字列に変換してから文字列の連結を行うことになります。
このようなことを行なう場合、アプローチの方法はふたつあります。
ひとつは、スタックに積む値についてそれぞれ型タグを付け、 実行時に判定を行う方法です。 crowbarはこの方法です。 CRB_Value構造体には型タグ(typeメンバ)が付いており、 実行時にそれを見て型変換や演算を行なっていました。
もうひとつは、型の判定はすべてコンパイル時に行なってしまう方法です。
型変換が必要なら、型変換処理をコンパイル時に挟みます。 これは、下図のように解析木にキャストを挟むことで実現できます (例は、2.5と3の加算)。
この解析木から生成されるバイトコードでは、 以下のようにキャストの命令が登場します。 この例での「cast_int_to_double」という命令は、 スタックの先頭のint型の要素をdouble型に変換します。
1: push_double 2.5 2: push_int 3 3: cast_int_to_double 4: add_double
この方法では、たとえば加算であれば、それが整数同士の加算であるのか、 実数同士の加算であるのか、あるいは文字列連結であるのかは、 コンパイルが済んだ段階で完全にわかっています。 そのため、実行時に余計な判定を入れる必要がなく、 高速な実行が期待できます。 ただし、コンパイル時に変数の型がわからなければいけないので ※3、 ユーザ(プログラマ)に、変数を型付きで宣言してもらう必要があります。
ifやwhileのような制御構造は、バイトコード上では、 gotoのようなジャンプ命令で表現できます。
たとえば以下のようなif文は、
if (a = 10) {
条件が成立した場合の処理
条件が成立した場合の処理
条件が成立した場合の処理
条件が成立した場合の処理
}
続きの処理
以下のようなバイトコードで表現できます。
1: 変数aの値をpush 2: push_int 10 3: eq_int # int同士の値を比較(==)し、結果をスタックに積む 4: jump_if_false 9 # スタックの先頭の値がfalseなら9行目にジャンプ 5: 条件が成立した場合の処理 6: 条件が成立した場合の処理 7: 条件が成立した場合の処理 8: 条件が成立した場合の処理 9: 続きの処理 # 4行目から、ここにジャンプする
crowbarでは、制御構造も解析木で表現し、 それを再帰で下りながらプログラムを実行していましたので、 breakやcontinueを実現するためには、再帰の深いところから (特別な戻り値を使用して)復帰する必要がありました。 バイトコード実行型の言語では、 breakやcontinueをより簡単に実現できますし、 (必要とあれば)gotoも簡単に実装可能です。
C等では、通常、関数呼び出しもスタックを使用します。
このあたりのことは「C言語 ポインタ完全制覇」あたりに詳しく書いたので そちらを参照してください ――と言いたいところですが一応軽く説明すると、 Cの場合、(素朴な実装では)関数呼び出しは以下の手順を踏みます。
Cが引数を「後ろから」スタックに積むのは、 printf()のような可変長引数を実現するためで、 今回作る言語Diksamには可変長引数はないので、 後ろから積む必然性は特にありません(実際、 Diksamでは前から積んでいます)。
リターンアドレスというのは、文字通り関数が終了した時に 復帰するアドレスを指します。 関数というものはプログラムのあちこちから呼び出されますから、 このように戻り先をスタックに積んでおかないと戻る先が わからなくなってしまうわけです。
ローカル変数を積み終わった時点でのスタックのトップを、 図では「base」という矢印で指しています。 この「base」からのオフセットで、ローカル変数や 引数を指定できます。
先程のif文のバイトコードの例において、 「変数aの値をpush」と日本語で書いたところをバイトコードにするなら、 以下のようになるでしょう(aがローカル変数の場合)。
push_stack_int 0 # 0はその変数のbaseからのオフセット
宣言のある言語では、 グローバル変数もコンパイル時にすべて決定していますから、 番号で指定できます。 たとえばint型のグローバル変数の値をスタックに積むコードは、 以下のようになるでしょう。
push_static_int 0 # 0はそのグローバル変数のインデックス