NAND2テトリス本「ソフトウェア編」まとめ

NAND2テトリス本「ハードウェア編」まとめの続編である。

前回のハードウェアパートでは、Hack機械語で動作する計算機を実装した。続くソフトウェアパートでは、プログラミング言語Jackを定義し、コンパイルすることで、Hack機械語を生成する。

Hackアセンブラ

アセンブラはアセンブリ言語で書かれたコードを機械語に翻訳するソフトウェアのことである。

シンボル解決

アセンブラは、対応表（機械語仕様という）に沿って変換するだけでなく、シンボル解決を行う必要がある。シンボル解決とは、アセンブリ上に登場するシンボルに対して、適切にアドレスを与えることである。

例：

ラベルについては、LOOPが4、ENDが18に置き換わっていることがわかる。また、sumやiのような変数には16番地から順にアドレスが与えられる。

特殊なシンボル

特殊なシンボルとして、

SP: スタックのアドレス
LCL: 現在のVM関数におけるlocalセグメントのベースアドレス
ARG: 現在のVM関数におけるargumentセグメントのベースアドレス

がある。これらはメモリ上にマップされる。

THIS, THATについてはヒープ上の構造体や配列にアクセスするためのベースアドレスであるが、最小限の説明には不要なため省略する。

マクロコマンド

Hackアセンブリはすべての命令で必ずAレジスタかDレジスタへの代入を必要とする。しかし、これを手で書くことは必ずしも直感的とはいえない。これに対して、D=M[xxx]のようなマクロコマンドを定義し、@xxx; D=Mの2つにアセンブラのレベルで分解するような拡張が考えられる。

2パスのアセンブラ

実装を簡単にするため、アセンブラを以下2つのフェーズに分割する。

シンボルテーブルを作る
アセンブリ中のシンボルを番地で置き換え、バイナリを出力する

Hack VM言語

コンパイラからHackアセンブリを直接出力するのではなく、実装を簡単にする目的で、一度VM言語を吐くことにする。

スタックマシン

VMにはスタックマシンを採用する。スタックマシンは、レジスタマシンとは異なり、計算の際に（逆ポーランド記法のように）スタックを利用する方法である。

有名なところでは、JVMやRubyのYARVはスタックマシンを採用しており、LLVMやLUAのVMはレジスタマシンを採用している。LUAは初期にはスタックマシンを採用していたが、のちにレジスタマシンへの書き換えを行った。

関数のコンテキスト

コンパイラは以下のようなVMコード生成を行う。

1
2
3
4
5
6
7
8
int mult(int x, int y) {
  int sum;
  sum = 0;
  for (int j = y; j !=0; j--) {
    sum += x;
  }
  return sum;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function mult 2
  push constant 0
  pop local 0
  push argument 1
  pop local 1
label LOOP
  push constant 0
  push local 1
  Eq
  if-goto END
  push local 0
  push argument 0
  Add
  pop local 0
  push local 1
  push constant 1
  Sub
  pop local 1
  goto LOOP
label END
  push local 0
  return

このVMコードを実行するためには、popやpushの番地管理のためのSP、local, argumentのためにLCL, ARGと言ったコンテキストが正しくセットアップされていることが条件となる。このセットアップをするコマンドは、VMによって生成される。

関数コール

関数コールを行うためには、呼び出し元のコンテキストを保存・復帰させる仕組みを必要とする。このために、スタックをこのように設計する。

関数呼び出しに関するVMコマンドに対応するコード生成は以下のようにすればよい。

特殊なシンボル生成

スタティック変数: X.vmというVMファイル内にstatic jというアドレス指定が存在する場合、@X.jというスタティック変数をコード生成する。これはアセンブリによってシンボル解決される
関数名ラベル: 関数名に対しては(f)というラベルを生成する
関数内ラベル: 関数f内のラベルLに対して、f$Lというラベルを生成する
リターンアドレスラベル: 関数呼び出しから返ったあとに移動するアドレスとして、(return-address)というラベルを生成する

Jackコンパイラ

プログラミング言語の文法は通常、文脈自由文法というルールによって定義される。これは、言語のある構文要素が、より単純な要素からどのように構成されるかを再帰的に示したルールである。

コンパイラの処理は以下の2つのフェーズに分割出来る。

ソース言語（ここではJack言語）に対して構文解析を行い、構文木を作る
構文木を元にしてターゲット言語（ここではVM言語）を生成する

構文解析

構文解析のアルゴリズムとしては、再帰下降構文解析がある。これは、構文要素に相当する関数を再帰的に呼び出していくことによって実装出来る。特に、1つのトークンを先読みすれば次に呼び出す関数を決定出来る場合、LL(1)文法であるという。

構文解析については、独自に実装することも出来るが、通常はlexやyaccなどのソフトウェアを使う。

コード生成

シンボルテーブル

変数にアクセスする時、それが一体メモリ上のどの番地にあるデータなのかを解決しなければいけない。そのために、シンボルテーブルを管理し、登場した変数をメモしていく。

シンボルテーブルは、スコープにも対応しなければいけない。これは、同名の変数であっても、スタティック変数なのかローカル変数なのかを区別しなければならないからである。そのために、シンボルテーブルはリンクリストによって管理される。

変数のスコープがわかれば、それに応じたメモリセグメント（static, local, argument）に応じたコード生成をすることが出来る。

コマンド変換

VMにスタックマシンを採用した理由は、コード生成がしやすいからである。

コード生成には、式の評価とフロー制御があるが、このうち式の評価は、スタックマシンを使っている限りは木構造を逆ポーランド表記の順でVMコマンドを出力すればよい。

もう１つのフロー制御は、以下のように、単純なルールに基づいて変換すればよい。

1
2
3
4
if (cond)
  s1
else
  s2

1
2
3
4
5
6
7
8
  (cond)を計算する
  if-goto L1
  s1を計算する
  goto L2
label L1
  s2を計算する
label L2
  ...

あとがき

有名なNAND2テトリス本を読み始めてはみたものの、実装するのはだるいということで、どこで一段落させるかと思いついたのが、まとめ記事を書くということであった。まとめ記事を書くには、本をちゃんと読み込む必要があるし、実際に分厚い本をもう一度高速で読み直すことになった。

この作業によって、貴重な土日がほぼ完全に消失したが、優雅な時間ではあった。

とにかく要点だけをストレートにまとめることに努めたため、ハードウェア編とソフトウェア編の2つをあわせて10分程度で読めるほどコンパクトにすることが出来たが、本質的でないと判断したものについては大胆に削った。もし全体に興味がある場合は、本を買って読んでほしい。

内容に間違いがある場合はメールでお知らせください。