Zenn
📚

Nand2Tetris読書会（8章）

2022/02/06に公開
勉強会
読書会
idea

概要

Nand2Tetris読書会 を開催しています。
今回取り上げるのは、8章『バーチャルマシン#2:プログラム制御』です。

前の記事は こちら。

内容

スタック処理は様々な仕事をこなせる。

  • 算術計算
  • ブール計算
  • ネスト化されたサブルーチン呼び出し
  • 引数の受け渡し
  • 再帰処理
  • メモリ割り当て
  • etc.

サブルーチンとは、ユーザーによって実装された命令(=関数、メソッド)のことである。
高水準言語では、以下の事項を可能にして高い表現力をサポートしている。

  1. 高水準な命令(ルーチン)(例：sqrt, power)を自由に定義できる
  2. 定義したルーチンをいつでも呼び出せる
  3. サブルーチンを呼び出すとそれが実行され、実行終了後はサブルーチンからリターンされて次のコマンドが実行される

上記のような表現ができるということは、低レイヤでサブルーチンの呼び出し側と呼び出し先のやりとりを処理しているということ。
このような、「サブルーチンが呼び出されると何が起こる？」という中身の処理は「ハウスキーピング処理」と呼ばれる。

  1. 呼び出し元から呼び出し先へ引数を渡す
  2. 呼び出し先のサブルーチン実行前に、呼び出し元の状態を保存
  3. 呼び出し先で、ローカル変数のためのメモリ空間を確保
  4. 呼び出し先のサブルーチンの実行へ移行(jump)
  5. 呼び出し先から呼び出し元へ値を返す(return)
  6. 呼び出し先で使ったメモリ空間を再利用できるようにする
  7. 呼び出し元の状態を復帰
  8. サブルーチンの次の場所の実行へ移行(jump)

スタック構造のおかげで、上記の処理を簡単に実装できる。

通常はプログラムの上から順に命令が実行されるが、分岐コマンドによってその順番が変更されることもある。
低水準言語の場合、「goto 移動先」コマンドで任意の場所の命令を実行すれば分岐を実現できる。
goto の移動先を指定する方法として、以下のような形式がある。

  • 次の命令の物理アドレスを指定
  • シンボルラベルで次の命令の位置を指定

分岐コマンドをスタックで実現すると、以下のような処理になる。

  1. スタックの最上位にある値を見る
  2. 0でなければ(true)指定された場所にjump、0(false)なら次のコマンドを実行

命令の呼び出し側にとっては、サブルーチンとビルトインのコマンドの間に違いはない。
唯一の違いは、呼び出しで call を付けるかどうかのみである。
そのほか、以下のような点は同じである。

  • 引数の設定が必要
  • 引数はスタックから取り出す
  • 結果をスタックの最上位に格納して値を返す

サブルーチンでは、一時記憶に置かれるローカル変数を用いる。
ローカル変数の寿命は、サブルーチンを開始してからリターンコマンドが実行されるまでの間である。
ネスト化されたサブルーチンだと、ローカル変数の寿命は複雑な問題となる。

しかし、このハウスキーピング処理はcall-returnロジックが持つ階層的な性質によって簡単に扱える。
サブルーチン中に別のサブルーチンを呼び出す場合、先に実行していたサブルーチンの環境をスタックにプッシュして、別のサブルーチンの実行に切り替える、そのサブルーチンからリターンされるときに、先のサブルーチンの環境をスタックからポップして実行を再開する。
つまり、この後入れ先だし(LIFO)の処理モデルがスタックのデータ構造と合致するため、call-returnm処理とスタックの相性は非常に良い。

「フレーム」とは、サブルーチンのローカル変数や引数、ワーキングスタックや他のメモリセグメントのことであり、「グローバルスタック」は現在のサブルーチンとそのリターンを待つ他のすべてのサブルーチンのためのフレームを含むメモリ領域のことである。現サブルーチンのワーキングスタックはグローバルスタックの一番上に置かれる。

call xxx の実装をまとめると以下のようになる。

  1. 呼び出し側のフレームをスタックに格納
  2. 呼び出された側のローカル変数用のメモリ領域を確保
  3. サブルーチンのコマンドの場所へ移動: call コマンドの後にあるサブルーチン名をメモリアドレスに変換して、そこに移動する

一方、return コマンドでサブルーチンから呼び出し元の場所に戻るときは、サブルーチンの call コマンドの次のコマンドの場所(リターンコマンド)へ移動する。
call xxx に遭遇したら、リターンアドレスをスタックにプッシュしておき、サブルーチンのコードを実行する。
その後 return コマンドに遭遇したらスタックからリターンアドレスをポップして、その値が示す場所に goto する。

実装

本章では、7章で示されたVM仕様を拡張し、以下の2つのコマンドを追加する。

  • プログラムフローコマンド
    • label xxx: 現在の位置を xxx という名前でラベル付け。
    • goto xxx: xxx のラベルの場所へ無条件で移動。
    • if-goto xxx: xxx のラベルの場所へ条件付きで移動。スタックの最上位の値をポップし、0でなければ移動、そうでなければ次のコマンドを実行。
  • 関数呼び出しコマンド
    関数名のスコープはグローバル。
    VMではすべてのファイルのすべての関数は互いに見えて呼び出せる。
    • function f n: n 個のローカル変数を持つfという名前の関数を定義。
    • call f m: f という関数を呼ぶ。m 個の引数はスタックにプッシュ済みである。
    • return: 呼び出し元へリターン。

関数を呼び出し、その関数から戻ることを、呼び出し元と呼び出し先の視点から見る。

  • 呼び出し元視点
    • 関数呼び出し前に必要な個数の引数をスタックにプッシュ。
    • call コマンドで関数呼び出し。
    • 関数がリターンされると、プッシュした引数は取り除かれて戻り値がスタックの最上位に格納される。
    • リターン後に、呼び出し側のメモリセグメント(argument, local, static, this, that, pointer)に変化はない。temp は未定義。
  • 呼び出し先視点
    • argument セグメントを実際の引数の値に初期化。
    • local 変数のセグメントを割り当てて0に初期化。
    • static セグメントはVMファイルで共有されるため初期化不要。
    • this, that, pointer は未定義のまま。
    • リターン前に呼び出し先の関数はスタックに値をプッシュしないとだめ。

VM関数が実行されると、メモリセグメントやスタックはその関数のためのプライベートな環境が用意される。

VM実装の実行開始/リセット(初期化)が起こると、Sys.init という引数なしVM関数を実行するのが慣例。
この関数はユーザープログラムの main 関数を呼ぶ。
したがって、VMコードを生成するコンパイラは、返還後のVMプログラムがそのような Sys.init 関数を一つだけ持つことを保証する必要がある。

VMで使用するメモリは、グローバルスタックに保存される形で実現できる。
関数呼び出しの度に、グローバルスタックに新しいブロックが追加される。
ブロックの構成は以下の通り。

  • 引数: 関数の呼び出し先のために、呼び出し元が設定
  • ポインタ: 関数の呼び出し元の状態を格納するためにVM実装が使用
  • ローカル変数: 呼び出し先のため、0に初期化される
  • ワーキングスタック: 呼び出し先のため、いわゆる"スタック"として一時的に値を保持したりする

VM関数から見えないグローバルスタックは、リターンアドレス、保存されたLCL, ARG, THIS, THATとARG, LCL, SPポインタであり、これらはcall-returnプロトコル実現のためのものである。

予習メモ

「呼び出し先で使ったメモリ空間を再利用できるようにする」とは具体的に何をするの？

  • LOCALなどのポインタを呼び出し前の値に戻す
  • スタックポインタを呼び出し前の値に戻す

これにより、呼び出し先で使ったメモリがクリアされたことになり、メモリ空間を再利用できる。

手続き型言語とオブジェクト指向言語

  • 手続き型言語
    • 処理の手続きを上から順に記述する。
    • 例：C言語
  • オブジェクト指向言語
    • 処理の対象をオブジェクト単位に分割、データとそれを扱う処理をオブジェクト（クラス）単位で記述する。
    • 例：Java

オブジェクト指向でコードを綺麗に整理していく過程を、例を挙げて説明しているページ。
なぜオブジェクト指向が必要なのか、どうすれば分かりやすいコードになるかが書かれている。

https://qiita.com/br_branch/items/2aa9859d4da41991bbb7

ディスカッションメモ

関数には「戻り値が常に存在する」とあるが、高水準言語の void みたいなものはないの？

今回実装するコンパイラでは、戻り値のない関数というものは存在しない。
void 関数は戻り値を無視すれば良いだけなので、今回は関数の戻り値の有無を考える必要はない。

感想

今まで使っていた言語では特に何も考えずに関数を定義したり呼び出したりしていましたが、その裏ではかなり複雑な処理がなされていることを学べる回でした。

演習問題も骨の折れる内容で、実装が大変でした。
演習のガイドが丁寧だったので、それに従って進めることでなんとかクリアできました。

最後に

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

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

次の記事は こちら。

GitHubで編集を提案

Discussion