プログラミング言語の作り方 〜 Go によるアセンブラ、バーチャルマシン、コンパイラの実装

はじめに

• プログラミング言語を作ったことはありますか？
• 私はプログラミング言語の実装なんて難しいことはできないと思っていましたが、コンピュータシステムの理論と実装を読んで理論を学び課題に従って実装していくことで、簡単なものではありますがプログラミング言語を作ることができました。

コンピュータシステムの理論と実装について

• この本ではコンピュータを理解するためにゼロからコンピュータを作っていきます。
• まずはハードウェア記述言語を使って仮想ハードウェアを作り、その仮想ハードウェア上で実行可能なマシン語のためのアセンブラを作り、そのアセンブラで実行可能なコードを生成するバーチャルマシン変換器を作り、そのバーチャルマシンで実行可能なコードを生成するコンパイラを作ります。
• マシン語やアセンブリ言語、バーチャルマシン語やプログラミング言語の仕様はそれぞれ決められており、それぞれの理論について説明を受けながら、それぞれの変換器を実装していくというのがこの本の流れになっています。
• 言語の仕様が決まっているので、設計で悩むことがありませんし、仕様自体が初心者向けに調節されているので、プログラミング言語とはどうやってできているのかを学習するための第一歩としてとても良くできていると感じました。
• この本は仮想ハードウェアの実装から始まっていますが、この記事では任意の言語で実装可能になっているアセンブラの作成のパートからを Go で実装していった内容について記載していきます。

アセンブラを実装する

アセンブラについて

• コンピュータシステムの理論と実装の 6 章に従って、アセンブリ言語を仮想ハードウェア上で実行可能なマシン語に変換するアセンブラを実装します。
• アセンブリ言語の仕様は単純で、二つのレジスタとメモリを対象に二種類の命令を取り扱います。
  • 詳細な仕様については公式サイトに資料があります。
  • 仕様は単純ですが、このアセンブリ言語を使って最終的には高級言語を動かすことができるというのは、抽象化のパワーの偉大さを感じます。

アセンブラの実装

• アセンブラの実装も単純で、基本的にコマンドを読み下しながらバイナリ形式に変換していくだけです。
• 実装したものはこちらになります。

簡単な解説

• アセンブリ言語コマンドの読み取りは正規表現を使ってパースするだけです。

parser.go

	ACommandRegex = regexp.MustCompile(`^@(.*)`)
	CCommandRegex = regexp.MustCompile(`^([ADM]+=)?([\-\+\!\&\|01ADM]+)(;[JGELNMTQP]+)?\s*`)
	LCommandRegex = regexp.MustCompile(`^\((.*)\)`)

• マシン語への変換は定義されている変換テーブルに従ってバイナリ形式に変換するだけです。
• これは代入命令にある代入先のレジスタまたはメモリの変換です。

code.go

func (c *Code) Dest(s string) uint16 {
	var out uint16
	if strings.Index(s, `M`) > -1 {
		out = out | destMBit
	}
	if strings.Index(s, `D`) > -1 {
		out = out | destDBit
	}
	if strings.Index(s, `A`) > -1 {
		out = out | destABit
	}
	return out
}

• ちょっとだけ手間がかかる部分として、シンボルの変換があります。
  • シンボルはメモリ位置への参照で、定義済みのものとユーザー定義のものがあります。
  • シンボルを定義した位置はあとから参照することができるので、ジャンプ先の指定などに利用できます。
• 変換時には先に一度アセンブリ言語のコードを読み下してシンボルの一覧表を作っておき、実際に変換を行う際に一覧表を使ってアドレスに置き換えていきます。

バーチャルマシン変換器を実装する

バーチャルマシン変換器について

• コンピュータシステムの理論と実装の 7, 8 章に従って、バーチャルマシン語をアセンブリ言語に変換するバーチャルマシン変換器を実装します。
• このバーチャルマシン語はスタックベースの言語で、実行環境の変数などの値はスタック上に保持され、すべての命令はスタック上の値を対象に実行されます。
• 言語がスタックベースであることのメリットとして、関数呼び出しをクリーンに行えるというものがあります。
  • FunctionA の実行中に FunctionB を呼び出した場合、それぞれの引数やローカル変数などのメモリ空間が同一であるとしたら、FunctionA の引数やローカル変数などをどこかに退避させてから FuncitonB のための引数やローカル変数などをセットする必要があります。また、FunctionB 終了時には退避させた FunctionA の変数などを元に戻すという手間も必要になります。この値の退避と復帰の処理は煩雑である上に失敗するとそのままバグになるのであまり好ましいものではありません。
  • 実行環境のローカル変数などをスタック上で保持できるようにすることで、FunctionB を呼び出した際には FunctionA のメモリ空間をそのままに、FunctionB のためのメモリ空間をスタック上に積み重ねるだけで利用できるようになるので、それぞれのメモリ空間が分離されてクリーンに取り扱うことができます。FunctionB 終了時にも FunctionB のメモリ空間をスタックから取り除くだけで呼び出し前の状態に戻すことができるので、手軽で安全にネストした関数呼び出しを行うことができます。

バーチャルマシン変換器の実装

• バーチャルマシン変換器は複雑なので 7 章と 8 章でわけて実装していきます。
• 7 章では算術演算とスタック操作を、8 章ではプログラムフローと関数呼び出しを実装します。

算術演算とメモリ操作の実装

• バーチャルマシン変換器の仕組み自体は単純で、バーチャルマシン語を行ごとに読み込んで対応するアセンブリ言語に変換していくだけです。
  • 全体のコードはこちらです。
  • main.go を見れば全体の流れがわかりますが、 parser.go でパースして code_writer.go で対応するアセンブリ言語を出力します。
• 変換器を実装するということは、見方を変えると変換先の言語で変換元の言語を実装するという部分があります。アセンブラ実装時には変換表があったのでこの部分を意識していませんでしたが、バーチャルマシン変換器の実装ではアセンブリ言語でバーチャルマシン語を実装するという部分が多くを占めているため、アセンブリ言語を理解して脳内で実行できるようにしていくまでがちょっと大変でした。
• たとえば 定数をスタックに push する という処理は下記のように実装されています。

code_writer.go

		case "constant":
			c.p("@%s", index) // A = n
			c.p("D=A")        // D = A
			c.p("@SP")        // A = 0
			c.p("A=M")        // A = M[0]
			c.p("M=D")        // M[SP] = n
			c.p("@SP")        // A = 0
			c.p("M=M+1")      // M[0] = M[0] + 1

• アセンブリ言語の 7 命令がバーチャルマシン語の 1 命令になるので、レイヤが上がることでこのケースでは単純に 7 倍の量のコードが書けるようになったということで、レイヤが上がることでより抽象的で生産的にプログラミングができるようになるということが肌で感じられます。

• 算術命令はスタックのすぐ上の値を pop して計算を実行し、結果を push するというものになります。

  • 算術演算には加算などオペランドがふたつのものと、ビット反転などのオペランドがひとつのものがあり、それぞれ必要な数だけスタックから pop して計算を行います。

• メモリ操作はメモリからスタックに値を push するものと、スタックからメモリに値を pop するもののふたつがあります。

  • 前記の push constant N だけ特別に任意の定数を push するというものになります。

プログラムフローと関数呼び出しの実装

• プログラムフローと関数呼び出しを実装したバージョンはこちらです。
• プログラムフローの方は単純なラベル付けと goto と条件付き goto で実装は単純にこんな感じです。
• 関数呼び出しの方はまあまあ複雑なことをしているのでサンプルの擬似コードが記載されており、それを見ながら実装していくという感じでした。アセンブラ側では当然メモリ空間がひとつなので、呼び出し前に古い値をメモリに逃がして、返ってくるときにメモリからもとに戻すという泥臭いことをする必要がありけっこう大変です。実装箇所はこのあたりになります。

高水準言語を実装する

高水準言語 Jack について

• コンピュータシステムの理論と実装の 10, 11 章では Jack と呼ばれるオリジナルの高水準言語を実装していきます。
• Jack はクラスベースの言語で、難易度調整のため冗長な部分はありますが割と本物の言語っぽいものになっています。詳細な仕様は資料をご覧ください。
• 例として Jack でキーボード入力から数字を受け取って 1 からその数字までの合計を出力するプログラムは以下のようなものになります。なんとなく勘で読める程度には一般的な文法だと思います。

class Main {
  /** Sums up 1 + 2 + 3 + ... + n */
  function int sum (int n) {
    var int sum, i;
    let sum = 0;
    let i = 1;
    while (~(i > n)) {
      let sum = sum + i;
      let i = i + 1;
    }
    return sum;
  }
  function void main () {
    var int n;
    let n = Keyboard.readInt("Enter n: ");
    do Output.printString("The result is: ");
    do Output.printInt(sum(n));
    return;
  }
}

Jack コンパイラの実装

• Jack コンパイラも複雑でボリュームがあるので、段階的に実装していきます。
• 10 章では Jack のコードをパースして字句に分割し構文木を作るところまでを行い、11 章ではシンボルテーブルを作り構文木の意味を解釈してバーチャルマシン語に翻訳していきます。

コードをパースして字句に分割する

• コンパイラ実装の第一歩としてソースコードをパースして字句（トークン）に分割していきます。
  • 具体的には class Main { を class, Main, { という単位に分割するということです。
  • これによりコードがファイル形式からトークンのリストとなるので、以後の取り扱いが容易になります。
• 実装方針は細かく提示されているので、それに従って作っていけば完成させられることができます。詰まったときも本文をよく見直せばピンポイントのヒントがあったりするのでよく考えられた教科書であると感じました。
• パースとトークンへの変換は主に tokenizer.go が行います。
• ここでは単純にコードを 1 文字づつ読み込んで、記号であるとか予約後であるとか識別子であるとかのラベルを付けて出力していくだけの実装となります。

トークンをパースして構文木を作る

• 本文中ではゆるい BNF のような形で文法が与えられているので、トークンをパースしてその並びから構文に当てはめて木構造を作っていきます。
• 実際に構文木をつくるのではなく、パースして構文を XML で出力したら最終的に木構造になっている、という感じです。
• 主に処理を行うのは compiler.go で、CompileClass が必ず最初に呼び出されるという決まりになっています。
• Jack 言語はこのパートが簡単になるように LL(1) 文法というものを採用しており、これは構文同士の最初のトークンをユニークにすることで、最初のトークンを読むだけでどの構文であるのかを判断できるようになるというものです。
• 関数呼び出しの前の do や代入文の let が LL(1) ために付与されているトークンで、冗長になりますがコンパイラの作成者には易しい仕様になっています。
• 式の構文だけは最初のトークンだけで判断することができないのでちょっと難しいですが、それでも次のトークンまで読めばユニークに判断できるようになっているので、ちょっとむずかしい程度にちょうどよく難易度が調節されています。

シンボルテーブルを作る

• 11 章にしたがってシンボルテーブルを作っていきます。
• シンボルテーブルとは識別子の種類を表にしたもので、識別子が static 変数であるのか、local 変数であるのか、引数であるのか、メソッド名であるのかなどの種別と、その型、それぞれの種別内での表示順位、などを記録したものです。
• シンボルテーブルの作成は構文木作成時に識別子の宣言がある毎に行われます。
• シンボルテーブル自体は symboltable.go で、これを compiler.go が利用して識別子の宣言毎に登録を行います。

バーチャルマシン語に翻訳する

• バーチャルマシン語への翻訳も構文木作成時に随時行われます。
• このパートでは Jack の言語仕様をよく読み、本文中の実装方針や擬似コードなどを参考にしながら Jack をバーチャルマシン語へ変換していきます。
• バーチャルマシン語の出力は vmwriter.go が行い、これを compiler.go が構文を解釈する毎に呼び出して行きます。
• Jack 言語は今までのバーチャルマシン語などに比べると仕様が大きいためすべてを把握してから実装しだすということができなかったので、書いて間違いながら仕様に合わせて直していくという感じで進めたため、ちょっと終わりが見えづらく地味に大変でした。
  • サブルーチン呼び出しでは、関数とコンストラクタとメソッドで前後の処理が異なり区別する必要が出てきたのでシンボルテーブルにサブルーチンの種別も追加したが、本文中で特に記載もなかったのでこのやり方であっていたかどうかあまり自信がないです。

OS を実装する

• 13 章ではメモリ管理や入出力を管理する機能を Jack 言語で実装していきますが、普通の高級言語のライブラリを作るだけっぽいのであとで余裕あったらやってみます。

おわりに

• 実装したプログラミング言語は実用に耐えるものではなく役には立ちませんが、プログラミング言語を作りしくみを学ぶことでプログラミング言語について以前よりも身近に感じられるようになったのは大きな収穫でした。
• プログラミング言語を作ってみてその大変さを実感することで、既存の言語がいかに多くの人々のはたらきによってつくられたものであるのかを想像できるようになり感謝をおぼえるようになりました。
• とはいえどんな大きな言語も自分と同じ人間の手によって作られているのだという当たり前のことを信じられるようにもなったので、今後のプログラミング言語学習の大きな励みをもらうことができました。