📚

Nand2Tetris読書会（7章）

2021/12/30に公開

勉強会

読書会

idea

概要

Nand2Tetris読書会を開催しています。
今回取り上げるのは、7章『バーチャルマシン#1:スタック操作』です。

前の記事はこちら。

内容

コンパイラを作る作業を、以下の２段階に分けて学んでいく。

高水準プログラムを中間コードに変換する。
中間コードを機械語へ変換する。

基本のアイデアは、「中間コードはバーチャルマシン(VM)上で実行されるように設計されている」ということ。
この考えにより、VMがあれば複数のプラットフォーム上で同じプログラムを動作させられる

VMプログラムは、そのVMが持っている言語で書ける。
本章で扱うVM言語に含まれるコマンドは以下の4種類。

算術 ← 7章
メモリアクセス ← 7章
プログラムフロー ← 8章
サブルーチン呼び出し ← 8章

「コンパイル」とは、高水準言語で書かれたプログラムをあるコンピュータ上で実行するため、プログラムをそのコンピュータの機械語に変換することである。
つまり、対象とする高水準言語と機械語の組み合わせに依存したプログラムが必要になる。
コンパイラは、高水準言語への依存と機械語への依存の2つの依存性を持つ(依存性の分離)。
そこで、コンパイルが行う変換を以下のような2段階に分けて考える。

高水準言語 → 中間コード: フロントエンドと呼ばれる
中間コード → 機械語: バックエンドと呼ばれる

VM言語を用いるメリット:

別のプラットフォームを対象としてコンパイラを作るとき、コンパイラのバックエンドの置き換えだけで済む。
複数の言語のコンパイラを用意する場合、同じVMのバックエンドを利用できる。

計算モデルのひとつであるスタックマシンでは、以下の2つの操作がよく行われる。

ポップ(pop): スタックからデータを取り出す
プッシュ(push): スタックにデータを置く

例として算術命令では、まずスタックの一番上からオペランドを取り出して、その結果をスタックの一番上に置くという、2回の操作を実行することで計算をする。

スタックへのアクセスにはメモリアクセスといくつかの違いがあるため注意が必要である。

	スタック	メモリ
アクセス可能な場所	スタックの一番上のみ	どこでも
データの読み出し	元のデータは取り除かれる	元のデータは残る
データの書き込み	既存データへの影響はない	書き込む場所にあったデータは上書きされる

スタックのデータ構造の実装のうち、最も単純なのは配列とスタックポインタを使う方法である。
スタックポインタ sp は配列の最後の要素の次の場所を指す。

push 命令
1. 配列の sp 番目にデータを格納する
2. sp を1増やす
pop 命令
1. sp を1減らす
2. 配列の最後(sp 番目)のデータを返す

本書で実装するVMの仕様は以下の通り。

スタックベース: すべての命令はスタック上で行われる。
関数ベース: VMプログラムはプログラムユニット(関数)ごとにまとまっている。
4つのコマンド
- 算術コマンド: スタック上で算術演算と論理演算をする。
- メモリアクセスコマンド: スタックとVM領域の間でデータを転送する。
- プログラムフローコマンド: 条件付き分岐処理あるいは無条件の分岐処理をする。
- 関数呼び出しコマンド: 関数を呼び出してそれからのリターンをする。

VMプログラムの構成は、オブジェクト指向言語における構成と類似している。

VM	説明	オブジェクト指向言語
VMプログラム	ひとつだけ	プログラム
`.vm` ファイル	各プログラムにひとつ以上	クラス
関数	各ファイルにひとつ以上	メソッド

VMコマンドは、.vm ファイルの中に行ごとに分かれて現れ、以下のフォーマットのいずれかとなっている。

<code>command</code>
<code>command arg</code>
<code>command arg1 arg2</code>

実装

VMを実装する場合、対象のプラットフォームでのVMのマッピング方法を示したガイドライン(標準マッピング)が与えられているのでそれに従う。
標準マッピングを与える理由は以下の2つがある。

VMベースのプログラムが、VMを使用しないコンパイラによって生成されるプログラムとやり取りする方法についての仕様が示されているから。
VMの開発者に標準テストを実施させられるから。

VMからHackへの変換器:

入力: .vm ファイルの集合(VMプログラム)
出力: Hackアセンブリ言語で書かれた .asm ファイルひとつ

本章のVM変換器の実装では、以下の2つのモジュールを実装していく。

Parserモジュール: .vm ファイルのパースをして、入力コードへのアクセスをカプセル化する。
- VMコマンドを読んでパース
- コマンドの要素へ簡単にアクセスするメソッドを提供
- 空白文字とコメントを削除
CodeWriterモジュール: VMコマンドをHackアセンブリコードに変換する。
メインプログラム: 変換処理の全てを実行。
- Parserモジュールで、VMの入力ファイルをパース
- VMコマンドを1行ずつ読み進めて、CodeWriterモジュールでVMコマンドをアセンブリコードへ変換

予習メモ

コンパイラに関する追加調査

コンパイラのしくみ

コンパイラの処理は、大きく分けて以下の2つのフェーズからなる。

フロントエンド: 入力側。ソースコードを分析して、プリグラムの内部表現(中間表現)を構築する。
- 字句解析: ソースコードをトークン(キーワード、識別子、シンボル名など)に分割する。
- プリプロセッサ: コンパイル前のすべての処理をする。
- 構文解析: トークン列を解析して構文木を作る。
- 意味解析: 構文木を解析して、型チェックや変数・関数の定義を参照の紐付けなどをする。
バックエンド: 出力側。中間表現を使ってコードの解析・変換をして、最終的な出力となる機械語を生成する。
- 解析部: 中間表現を解析する。コードのある位置における変数の取り得る値の候補などを収集する(データフロー解析)。
- 最適化: 中間表現を機能的に等価でより適切な形式に変換する。参考
- コード生成: 機械語やバイトコードへ変換する。

コンパイラの種類

コンパイラのどの機能に着目するかで、コンパイラを様々に分類できる。

何に変換するか？
- ネイティブコンパイラ: 機械語(ネイティブコード)に直接コンパイルする。
- 中間コードコンパイラ: 中間コードを生成して、別のコンパイラやインタプリタに後続の処理を任せる。
どこでプログラムを実行するか？
- セルフ開発: 開発環境と同じ環境でプログラムを実行する。
- クロス開発: 開発環境と別の環境でプログラムを実行する。
何回でコンパイルできるか？
- ワンパスコンパイラ: 1回でコンパイルが完了する。高速にコンパイルできるが、最適化は難しい。
- マルチパスコンパイラ: ソースコードを複数回に分けて読み込んでコンパイルする。
いつコンパイルするか？
- 事前コンパイラ(AOTコンパイラ): プログラムの実行前にコンパイルをする。
- 実行時コンパイラ(JITコンパイラ): プログラムの実行時にコンパイルをする。

なぜAOTコンパイラよりもJITコンパイラが広く使われているの？

JITコンパイラでは、繰り返し呼ばれるコードブロックのみを機械語にコンパイルして、以降その機械語をVMから呼ぶ。
そうでないコードはVM機械語のまま実行する。
AOTコンパイラの場合、コードの呼び出し回数に関係なく全てのコードをコンパイルする。
コードが1回しか呼ばれない場合、インタープリタでVM機械語のまま実行した方がコンパイル→機械語を実行とするよりも早い。
また、コードの実行時に取得できる情報もコンパイルに利用できるため、AOTコンパイラよりも多くの最適化が可能となる。

コンパイラとインタープリタ

	コンパイラ	インタープリタ
主な役割	プログラミング言語で書かれたコードを、機械語あるいは中間コードに変換する	プログラミング言語で書かれたコードや中間コードを実行する
機械語プログラムの実行	しない	する
実行時の要否	不要(1度コンパイルしたら再実行不要)	必要

こちらにも、コンパイラとインタープリタのメモを残した。

バーチャルマシン言語の例

基本的に、バーチャルマシン言語が生成されるとそのままバーチャルマシン上で実行される。すなわち、「バーチャルマシン言語=バーチャルマシン用の機械語」と考えてよい。

pコード: Pascalコンパイラによって生成され、pコードマシンのエミュレータ(インタープリタ)で実行される。
バイトコード言語(Javaバイトコード): Javaコンパイラによって生成され、Java仮想マシン(JVM)で実行される。
中間言語: .NETフレームワークのコンパイラによって生成され、CLRというバーチャルマシンで実行される。
YARVバイトコード: YARVによってRubyのソースコードから生成され、RubyVMで実行される。

スタックの操作

書籍で取り上げられた push, pop 以外にも以下のような操作がある。

dup(licate): スタックの一番上の要素を pop した後2回 push する。操作後には、元々一番上にあった要素の上に同じものが増える。
e.g. [ a b c] -> [ a b c c]
peek(top): pop した後にスタックポインタを変更しない。スタックの状態を変えずに一番上の要素を参照する。
swap/exchange: スタックの上位2つを入れ替える。
e.g. [ a b c] -> [ a c b]
rotate: 上位 n 個の要素の順番をずらす。
e.g. [ a b c] -> [ b c a] (right rotate), [ a b c] -> [ c a b] (left rotate)

ディスカッションメモ

バーチャルマシン用の言語を用いた場合、別のプラットフォームへ移植するときのデメリットとは？

VM言語のバージョン、OSのバージョンとの整合が取れないことがある
OSにVMをインストールしていないから、組み込み系の場合は逆に移植が大変になるかも？
全体のサイズが大きくなったり、起動に時間がかかったりする

仮想マシンの種類はスタックベース以外にある？

スタックベース
- 例: JVM
- 移植性が高い
- 操作対象が常にスタックの先頭なので、コードの量が少なくて済む
レジスタベース
- 例: Dalvik VM
- レジスタが少ないCPUで実行できないなど、移植性が低い
- メモリよりもレジスタへのアクセスの方が早いため、高速に処理できる
- レジスタの指定が必要になるため、コード量が多くなりやすい

参考：https://stackoverflow.com/questions/164143/registers-vs-stacks

感想

6章よりもさらに演習の手応えがある章でした。
コンパイラの処理をメソッド単位に分けて実装できたので、コンパイラの中で行われる処理をじっくりと考えながら学べました。

最後に

『Nand2Tetris読書会始めました』の記事でも紹介していますが、読み進めているのはこちらの本です。

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

次の記事はこちら。

GitHubで編集を提案

概要

内容

実装