Nand2Tetris読書会（11章）

概要

Nand2Tetris読書会 を開催しています。
今回取り上げるのは、11章『コンパイラ#2：コード生成』です。

前の記事は こちら。

内容

今回開発するコンパイラはふたつの要素から構成される。

• バックエンド: バーチャルマシン(7, 8章)
• フロントエンド: 構文解析器(10章) + コード生成器(11章) ← 高水準言語とVM言語を繋ぐ

構文解析器とコード生成器はひとつのプログラムにまとめられることが多い。
本章では、10章で開発した構文解析器を完全なコンパイラに拡張する。

• 10章: Jack言語を理解できる(パースできる)構文解析器
• 11章: 理解した高水準言語をVM命令に変換するコンパイラ

プログラムが実行されるプラットフォームの構成は、ストレージのためのレジスタ一式 + 単純な命令セット という最小限の要素からなる。
→ 高水準から低水準へのプログラムの変換は難しい。
プラットフォームをバーチャルマシンとすると問題が多少簡単になるが、やはり変換は大変。

プログラム = データを操作する一連の命令 であり、コンパイル作業ではデータ変換とコマンド変換のふたつの変換が行われる。

データ変換では、プログラムの各変数の型を対象のプラットフォームに適合する表現にマッピングする。
同時に、変数のライフサイクルとスコープを管理する。

データ変換で扱うのは、以下のふたつ。

• 変数の型(type): 整数、ブーリアン、配列、オブジェクト etc.
• 変数の属性(kind): ライフサイクルとスコープ → ローカル変数、グローバル変数、引数、フィールド変数

シンボルテーブルは、プログラムに含まれるすべての識別子について、以下を記録する。

• その識別子がソースプログラムで何を表しているのか
• その識別子が対象言語でどの構成要素に対応するか

ハッシュテーブルのリストというデータ構造で表現される。

• リストの各要素のハッシュテーブルは単一のスコープを表わす。
• リストの要素は次の要素の中にネスト化されていることを意味する。
  → 「内部のスコープで定義された識別子は外側からは見えない」状態を表現できる。

変数操作では、ソースプログラム内で宣言される変数を、対象のプラットフォーム上へどう対応づけるかという問題を解決しないといけない。
このときに考えないといけない問題として、次のようなものがある。

• 変数の型によって、必要なメモリサイズは異なる
  → メモリと変数のマッピングは1体1対応しない
• 変数の属性によって、変数が存在しなければならない期間が異なる

本書で扱うコンパイラの場合、2段階構成のアーキテクチャを採用して、変数のメモリ割り当てをVMに任せている。
そのため、どのような言語でもVM言語にさえ変換できれば低レベルのメモリ管理を機にすることなくコンパイルできる。

配列は連続したメモリ領域に保存される。
配列名 = ポインタ = 配列が格納されたRAMのベースアドレス と考えられる。

• 静的メモリ割り当て: 配列の宣言時に、その配列を格納するのに必要なメモリ領域を割り当てる。
• 動的メモリ割り当て: 配列の宣言時に、ポインタひとつ分のメモリ領域を割り当てる。実際の配列のメモリ領域は、実行時に配列が生成されたときに割り当てる。

一般的にOSに備えられている alloc(size) 関数では、size で指定した大きさの利用可能なメモリを探して、戻り値としてそのベースアドレスを返す。
これは、配列の宣言文をコンパイルしたときに生成される低水準な命令で使われる関数である。

配列のベースアドレスを使って配列の k 番目の要素にアクセスする操作を実現するためには、間接アドレス指定のメカニズムが必要。
つまり、y 番目のメモリ位置に値を格納する代わりに、y 番目に格納されている値をアドレスとして解釈して、そのアドレスの場所に値を格納するという処理ができなければならない。

オブジェクト操作も、配列操作と似ている。
オブジェクトのフィールドは連続したメモリ空間に格納される。
オブジェクト指向の言語の多くは、クラス型の変数の宣言時にポインタ分のメモリ領域を割り当てる(動的メモリ割り当て)。
コンストラクタが呼ばれて実際のデータが生成された段階で、オブジェクトのメモリが割り当てられる。
Xxx というクラスのコンストラクタをコンパイルする場合、次のような手順でオブジェクト操作が行われる。

1. クラスのフィールドの数と属性を調べて、RAM上で Xxx 型のインスタンスの生成に必要なメモリ領域の大きさを計算する。
2. 新しく生成されたオブジェクトに必要なメモリ領域を確保するコードを生成する。

オブジェクトでカプセル化されたデータにアクセスする場合、オブジェクトのベースアドレスからの相対的なインデックスが使われる。

メソッドを呼び出す場合、インスタンスのコピーは複数存在するが、メソッドのコピーはひとつだけしかないため、メソッド呼び出しのときは隠れ引数として操作対象のオブジェクトの参照を渡すことで解決できる。
クラスメソッドの名前は他のクラスのメソッドと同じことを許容するため、メソッド呼び出しにおいては正しいオブジェクトに対して正しいメソッドが適用されることを補償しないといけない。
サブクラスでメソッドを上書きできるので、オブジェクト指向のコンパイラはプログラムの実行時にオブジェクトとメソッドの紐付けが保証しないといけない。

コマンド変換については、高水準のコマンドが目的とする言語へ変換する方法を説明する。

高水準言語の式は、以下のような手順で評価される。

1. 式の構文構造を"理解する"
   例：構文木への変換(10章)
2. 構文木の走査をしてVMコードを生成する

コード生成のアルゴリズムは、変換先のコードに依存して決まる。
例えば、スタックベースのプラットフォームの場合、構文木を後置表記法(逆ポーランド表記法(RPN))で出力すればよい。

フロー制御では、高水準言語の処理を低水準言語のプリミティブな命令だけで表現しなければならない。

• 高水準言語のフロー制御: if, while, switch, etc.
• 低水準言語のフロー制御: 条件付き goto, 無条件 goto のみ
  このとき、以下のような課題を解決することになる。
• プログラムには複数の if, while 文が含まれる可能性があるため、ラベル名を一意に決定しないといけない
• 制御の構造がネスト化されているので、再起的にコンパイスする必要がある

実装

本章では、コンパイラ全体を5つのモジュールから構成する。

• JackCompiler: セットアップや他モジュールの呼び出し
  • 入力ファイル Xxx.jack を受け付けて、 出力ファイル Xxx.vm を作成する。
• JackTokenizer: トークナイザ
• SymbolTable: シンボルテーブル
  • シンボルテーブルの作成
  • シンボルテーブルの使用
• VMWriter: VMコードを生成して出力
• CompilationEngine: 再帰によるトップダウン式解析器
  • JackTokenizer から入力を受け取り、VMWriter で出力を書き出す。

Jackコンパイラでは無視できるが、一般的な言語のコンパイラに必要な処理がある。

• 型付け
  • 式をコンパイルして評価するときに型を決めないといけない。
  • 変数の方に応じて適切なメモリサイズを割り当てる。
  • 型を別のものに変換する。
  • 式内の変数の型が適切か判定する。
• 継承
  • メソッドを仮想的に扱い、メソッドの場所は実行時のオブジェクトの型によって決定する。
  • どのクラスに属するメソッドが呼び出されるかは、実行するまで分からない。
• パブリックなクラスフィールド
  • クラスのプロパティにはgetメソッドを使ってアクセスする。

予習メモ

動的メモリ割り当て

メモリ領域には、以下の種類がある(C言語の場合)。

• 静的領域(スタティック領域)
  • プログラムが開始されて終了するまで確保される固定的な領域。
  • グローバル変数が宣言されると、ここに確保される。
• スタック領域
  • 関数が実行されると使われる領域。
  • グローバル変数以外の変数がここに確保される。
  • 関数の終了により、この領域に確保されていた変数が自動的に解放される。
• ヒープ領域
  • 必要に応じて、変数への割り当てや解放ができる領域。

スタック領域はヒープ領域に比べて容量が小さいため、多くのメモリを確保するケースには向いていない。
また、スタック領域は関数が終了すると解放されるため、複数の関数を跨いで共通のデータを利用する場合にも不向き。

そこで、動的メモリ割り当てによってヒープ領域にデータを確保することで、上のような問題を解決する。

https://www.gavo.t.u-tokyo.ac.jp/~dsk_saito/lecture/software2/resource/lecture3.html

逆ポーランド表記法(後置記法)

式を表現する際に、演算子を非演算子の後に置く書き方。
次のような例がある。

• a + b (a と b の加算) → a b +
• x = 1 - 2 + 3 (計算結果を x に代入) → x 1 2 - 3 + =
• x + g(2, y, -z) * 5 → x 2 y z - g 5 * +

逆ポーランド表記法は、計算機に計算を指示するときのスタック処理と相性が良い。

http://www.sci.kanagawa-u.ac.jp/info/kaiya/2003/mc/arch/rpolish.html
https://ponsuke-tarou.hatenablog.com/entry/2018/02/19/230759

ディスカッションメモ

継承の機能を追加する場合、どのような課題が生まれる？

メソッドの呼び出しがあった場合、それが子クラスのものか親クラスのものかを判別しないといけない。
子クラスでメソッドが上書きされたら子クラスのメソッドを、そうでなければ親クラスのメソッドを呼び出すことになる。
どのクラスのメソッドを呼び出すかはコンパイル時には決定できないため、プログラム実行時に動的にメソッドを決定する。

そのときに使われるのが、仮想関数テーブル (vtable) である。

https://ja.wikipedia.org/wiki/仮想関数テーブル

Java でこの問題をどのように解決しているかは、こちらで分かりやすく説明されていた。

https://www.oracle.com/webfolder/technetwork/jp/javamagazine/Java-SO17-MethodInvoc.pdf

感想

前章に引き続き、演習が重かったです。
しかし、10章と11章を通して学ぶことで、コンパイラがどのような処理を行っていたかを理解でき、今までコンピュータに任せていた何気ない処理の裏側を知ることができました。

Jack 言語はかなり機能を絞ったシンプルな仕様となっていますが、それがこの辺りの章の理解しやすさ、演習の取り組みやすさに繋がっていますね。
読書会では、継承が実装されていた場合にどのような面倒くささが生じるかもディスカッションしたので、普段使っている言語のコンパイラのありがたみを改めて感じました。

最後に

『Nand2Tetris読書会始めました』の記事でも紹介していますが、読み進めているのはこちらの本です。
https://www.oreilly.co.jp/books/9784873117126/

初学者なりに書籍やその他に調べた内容をまとめていますが、理解が足りておらず間違ったことを書いているかもしれません。
そのような箇所を見つけた場合はコメントなどで指摘していただけると助かります。

次の記事は こちら。