232 い O 章コンバイラ # 1 : 構文解析 10.2.1 Jack 言語の文法 9 章で定義した Jack 言語の機能的な仕様は Jack プログラマーを対象としたもので あった。ここでは、 Jack コンパイラの開発者を対象として、言語の公式な仕様を定義 する。ここで示す文法の仕様は次の記法に基づく。 XXX クオート付きの太文字は「文字どおりのトークン」であり、終端記号として用 いられる。 通常フォントは「言語構成物」であり、非終端記号として用いられる。 カッコは言語構成物をグループ化するために用いられる。 x または y が現れることを示す。 x が 0 回または 1 回現れることを示す。 x が 0 回以上現れることを示す。 これらの記法を用いて、 Jack 言語のシンタックスを以下に示す。 字句要素 Jack 言語には 5 種類の終端記号が含まれる。 XXX X ?

186 ー 8 章バーチャルマシン # 2 : プログラム制御 実装した VM 変換器はアセンプリプログラムを生成し、 CPU 工ミュレータを使用す れば、そのアセンプリプログラムを実行することができる これにより間接的にテ ストを行うことができる。また、別のツールとして、本書が提供する VM ェミュレー タも利用することができるであろう。この VM 工ミュレータは正しく動作するため、 VM 変換器を実装する前に、 いろいろ実験することができる。このツールについての 詳細は、「 VM 工ミュレータ・チュートリアル」を参照してほしいす 1 規約 完全版の「 VM から Hack へ」の変換器を書くこと。この変換器は、 7 章で開発した 変換器を拡張し、 8.2 節の「 VM 仕様 ( 第 2 部 ) 」と 8.3.1 節の「 Hack プラットフォー ムの標準 VM マッピング ( 第 2 部 ) 」を満たさなければならない。実装が完了したら、 その変換器を使って以下で挙げる VM プログラムを変換し、 Hack のアセンプリ言語 で書かれたプログラムを生成せよ。本書の CPU 工ミュレータで実行するときは、テ ストスクリプトと比較ファイルを用いてテストを行うこと。 8.5.1 テストプログラム 変換器の実装は 2 段階に分けて行うことを推奨する。初めに「プログラムフロー」 を行うコマンドを実装し、続いて「関数呼び出し」を実装する。こうすることで、本 章で提供するテストプログラムを用いて、段階的にユニットテストを用いて作業を進 めることができる。 本プログラムでは、 xxx というプログラムに対して、 xxxVME . t st という名前の スクリプトが与えられている。これは VM 工ミュレータ上でそのプログラム (xxx) を実行するために用意されており、プログラムの意図する動きを把握するために利用 することができる。各自が実装した VM 変換器を用いてプログラムを変換した後は、 本書が提供する xxx . t st と xxx . cmp スクリプトを用いて、 CPU 工ミュレータ上 tutoriaIs/PDF/VM%20EmuIator%20Tutorial.pdf 訳注 : 「 VM 工ミュレータ・チュートリアル」は次より取得できる。 http://www ・ nand2tetris.org/ で、その変換後のアセンプリコードをテストすることができる。 す 1

310 ー 12 章オペレーティングシステム 材料 本プロジェクトで主に必要なツールは Jack である。我々は Jack を用いて os を開 発する。さらに、本書が提供する Jack コンパイラと VM 工ミュレータが必要である。 コンパイラを用いて、あなたが実装した OS をコンパイルし、テストプログラムと VM 工ミュレータを使って、そのコンパイルされた OS コードをテストすることができる。 こで、本書の VM 工ミュレータにはすべての OS の機能が備わっていることに注意 する必要がある。しかし、もし VM 工ミュレータが、 VM コードの形でコンパイルさ れた OS のコードを見つけた場合、ビルトイン版の OS コードの代わりに、そのコンパ イルされたコードを使用する。これを行うには、この後で説明する方法に従えばよい。 規約 JackOS を実装し、こで述べるテストプログラムとテスト方法に従ってテストす る。テストプログラムでは OS のサービスを使用する。 12.5.1 テスト方法 本プロジェクトの開発とテストはクラスごとに分けてを行うことを推奨する。そう するためには、あなたが実装した OS のクラスとそれに対応するテストプログラムを 同じディレクトリに置くようにする。具体的には、次の手順に従って進めることを推 奨する。 1. 2. 3. 4. あなたが実装した OS クラスにれを xxx. jack とする ) とそれに対応する本書 が提供するテストプログラムを同じディレクトリに置く。 本書の Jack コンパイラを用いて、そのディレクトリを対象としてコンパイルを 行う。結果として、 OS クラスの xxx. jack とテストプログラムがコンパイルさ れ、新たに xxx . vm ファイルが生成される。この xxx . vm には、あなたの os ク ラスの実装が含まれる。これが我々の望むことである。 VM 工ミュレータをこの ディレクトリに適用した場合、 VM 工ミュレータは xxx という ()S クラス以外は ビルトイン版を用い、 xxx はあなたの実装 (xxx . (m) を用いる。 VM 工ミュレータにそのディレクトリにあるコード ()S とテストプログラム ) を 読み込ませる。 コードを実行する。 OS のサービスが、下に示すガイドラインに従って適切に実 行されているか確認を行う。

74 ー 4 章機械語 A レジスタを使用する場合、移動を伴う C 命令 (j ビットが 0 でない場合 ) において は M を参照すべきではない、と言える ( その逆も同様 ) 。 424 シンボル アセンプラによるコマンドは、定数もしくはシンポル (symbol) を用いてメモリ位 置 ( アドレス ) を参照することができる。シンポルは、アセンプリプログラムにおい て次の 3 つの方法によって用いられる。 定義済みシンボル RAM アドレスの特別なものについては、どのようなアセンプリプログラムからで も、次に示す定義済みシンポルを用いて参照することができる。 仮想レジスタ アセンプラによるプログラミングを単純化するために、 R0 から RI 5 までのシ ンポルが RAM アドレスの 0 から 15 をそれぞれ参照するように、あらかじめ 定義されている。 定義済みポインタ sp 、 LCL 、 ARG 、 TH 工 s というシンボルは RAM アドレスの 0 から 4 をそれぞ れ参照するように定義されている。こで、これらのメモリ位置に対してふた うつのラベル名が与えられていることに注意されたい。たとえば、アドレスの 2 番目の位置は R2 もしくは ARG というシンポル名で参照することができる。 このように命名した理由は「バーチャルマシン」を扱う 7 章と 8 章で明らかに なる。 入出力ポインタ ( レ 0 ポインタ ) SCREEN と KBD というシンポルは、 RAM アドレスの 16384 ( 0X4000 ) と 24576 ( 0X6000 ) をそれぞれ参照するように定義されている。これらのアドレスはス クリーンとキーポードのメモリマップにおけるべースアドレスを示す。 ラベルシンボル これはユーザーが定義するシンポルであり、 goto コマンドの行き先のラベルとして ( xxx ) " という形式のコマンドで宣言される。このコ 用いられる。このシンポルは、

2.5 プロジェクトー 39 ルとしては、算術演算と論理演算をハードウェアで実装するにはコストは高くつくが、 パフォーマンスは良くなる。このトレードオフの関係を考慮して、ハードウェアであ る ALU は設計される。本書で設計した ALU は、機能性を限定して、できるかぎり ソフトウェア側で他の操作を実装するような設計を採用した。たとえば、我々の ALU は、「乗算」も「除算」も「浮動小数点演算」の機能も提供していない。これらの操作 は、 OS レベルで実装される ( 詳細は 12 章で述べる ) 。このように、どのようなコン ピュータであれ、ハードウェアとソフトウェアの機能は、 ALU とオペレーティングシ ステム ( それは ALU の上で実行される ) がタッグを組んで提供するものである。 プール演算と ALU 設計の詳細については、「コンピュータアーキテクチャ」に関す る書籍などで論じられている。興味のある読者は、そのような書籍を参照してほしい。 2.5 プロジェクト 目標 本章で取り上げた回路をすべて実装する。使うことのできる構成要素は、前章まで に構築した回路である。本章で作った回路については、それ以降用いることができる。 本プロジェクトで読者が実装する HDL プログラムは、先のプロジェクトで構築し た回路を内部的に用いることだろう。その場合、自分で実装した回路を用いる代わり に、ビルトイン版の回路の使用を推奨する。ビルトイン版回路を用いれば、その回路 の動作は正しいことが保証でき、さらにハードウェアシミュレータの実行速度を最適 化できる。これを行うのは簡単である。あなたのプロジェクトのディレクトリに、そ のプロジェクトで取り組んでいる . hdl ファイルだけを含むようにすればよい。 手順については、前章のプロジェクトで示した「手順」と同じである。ただし、プ ロジェクトのディレクトリは、 pro j e ct s / 0 2 にある。

7.1 背景ー 139 スタックへのアクセスは、これまで見てきたメモリアクセスとはいくつかの点におい て異なる。ひとつ目の相違点は、スタックでアクセス可能な場所は一番上の場所に限 られるという点である。ふたつ目は、スタックのデータを読み出すための命令は " 損失 を伴う " という点である。つまり、一番上のデータを取り出す唯一の方法は、スタック からそのデータを取り除かなければならない。これと比べて、通常のメモリからデー タを読み込む操作には、メモリの状態に影響を与えるような副作用は存在しない。 3 つ目の相違点は、スタックへのデータ書き込みは、スタックの一番上にデータを追加 することによって行われ、その下のデータには影響を与えないという点である。これ と比較すると、通常のメモリにおけるデータ書き込みの操作は " 損失を伴う " 命令で ある。なぜなら、メモリにデータを書き込むには、メモリの前の値に対して上書きを することになるからである。 スタックのデータ構造はさまざまな方法で実装することができる。最も単純なアプ ローチは、配列とスタックポインタを用いる方法である。スタックポインタは配列の要 素に対して最後の要素の次の場所を指す。ここで、配列を stack 、スタックポインタ を sp という名前で表すとしよう。そうすれば、「 pus h x 」というコマンドは、配列の sp で指される場所に x を格納し、 sp を 1 だけインクリメントすることで実装すること ができる ( コードで表すと、 stack[sp]=x; sp=sp + 1 、または、 stack[sp + + ])。 p 〇 p 命令は、最初に sp を 1 だけ減らし、それから配列の最後 ( 末尾 ) に格納された値 を返す (sp=sp-l; return stack[sp] 、または、 return stack[--sp])o コンピュータサイエンスという分野においては、「シンプルさと優美さを兼ね備えた ものは表現力も豊かである」というのが常である。単純なスタックモデルはコンピュー タシステムやアルゴリズムのいたるところで用いられるデータ構造である。我々が作 ろうとしているバーチャルマシンのアーキテクチャにおいても、スタックを用いる。 我々はスタックを主にふたつの目的で用いる。ひとつは、 VM におけるすべての算術 命令と論理命令を扱うため。もうひとつは、サプルーチン呼び出しとメモリ配置を行 スタックへ戻される。たとえば、加算 (add) がどのように行われるかを次に示そう。 からポップされ、所望の命令がそのオペランドに対して実行される。そして、結果が スタックベースによる算術計算は簡単に行うことができる。オペランドはスタック スタック算術 うために用いる ( これは次章のテーマである ) 。

C. 2 表 C - 1 Nand2tetris ソフトウェアツール Nand2tetris ソフトウェアツールー 363 CPU 工ミュレータ ツーノレ ドウェアシミュ VM 工ミュレータ アセンプラ Jack コンパイラ オペレーティングシス (TextComparer) テキスト比較 論理ゲート、論理回路のシミュレーションとテストを行う。 論理ゲートは、本書で説明した HDL で実装されているこ とを想定する。本ツールは、ハードウェアを構築するとき に使用する Hack コンピュータシステムの動作をエミュレートする。 Hack 機械語で書かれたプログラム ( バイナリ版とアセン プリ版の両方に対応 ) を実行しテストするために用いる 本書で説明するバーチャルマシンの動作をエミュレートす る。 VM 言語で書かれたプログラムを実行しテストするた めに用いる Hack アセンプリ言語で書かれたプログラムを Hack バイ ナリコードへ変換する。結果として生成されるコードは、 Computer 回路 ( または、本書の CPU 工ミュレータ ) で 直接実行することができる Jack プログラミング言語で書かれたプログラムを VM コー ドへ変換する。結果として生成されるコードは、 VM ェ ミュレータで実行することができる。また、本書が提供す る VM 変換器とアセンプラを用いて、その VM コードを Hack バイナリコードへ変換することができる (Hack バイ ナリコードは CPU 工ミュレータで実行することができる ) Jack OS は Jack 言語を拡張する。本書が提供する Jack OS 実装には「 Jack で書かれた 8 つの . vm クラスファイ ル」と「本書の VM 工ミュレータに埋め込まれた高速版の 実装」の 2 つのバージョンがある。 本ツールは 2 つの入力テキストが等しいかどうかをテスト する。本ツールはいくつかのプロジェクトで用いることが できる。 Mac や Unix/Linux では、代わりに d 土 ff コマ ンドを用いてもよい ありす 1 ありす 2 ありす 3 ありす 4 なし なし 参考リンク なし す 1 す 2 す 3 す 4 http://www.nand2tetris.org/tutorials/PDF/Hardware%20Simulator%20Tutorial.pdf http://www.nand2tetris.org/tutorials/PDF/CPU%20EmuIator%2()Tutorial.pdf http://www.nand2tetris.org/tutoriaIs/PDF/VM%20EmuIator%2()Tutorial.pdf http://www.nand2tetris.org/tutorials/PDF/Assembler%20Tutorial.pdf

296 い 2 章オペレーティングシステム readChar( ) : / / 単一文字の読み込みと出力 カーソルを表示 while キーが何も押されていない 何もしない / / キーが押されるまで待つ c= 現在押されたキー while キーが押されている / / ユーザーがキーを離すのを待つ 何もしない readLine( ) : このロジックは図 12-15 のように実装することができる。 図 12 -14 単一文字の読み込み ret urn C カーソルを右へ 1 つ移動する 現在のカーソル位置に c を出力する 図 12-15 文字列の読み込み = ・ append(c) / / s に c を追加する else カーソルを 1 つ前に戻す s から最後の文字を取り除く バックスペース文字 else if c 1 ℃ tur Ⅱ S 改行を出力 if c = 改行文字 0 = read Char ( ) 1 ℃ peat s = 空の文字列 / / 読み込みど、行”の出力 ( Enter キーが押されるまで ) ルーチンを用いる。さらに readChar は keyPressed という抽象化されたルーチ という抽象化されたルーチンを用い、 readLine は readChar という抽象化された これまでと同じように、入力操作も抽象化を用いている一一高水準言語は readLine

仕 五ロ 9 例 9 - 7 オブジェクト型 ( 例 ) / / このコードでは car クラスと EmpIoyee クラスがあると想定する。 / / Car オブジェクトは model と licensePIate フィールドを持つ。 / / Employee オブジェクトは name と car フィールドを持つ。 / / null を参照する e 、 f という変数を宣言する。 var EmpIoyee e, f; / / null を参照する c という変数を宣言する。 var Car c; / / 新しい Car オブジェクトを生成する。 Car . new("Jaguar'l / / 新しい EmpIoyee オブジェクトを Emp10yee . new("Bond", c) / / 生成する。 / / この時点で、 c と e は、そのふたつのオブジェクトに割り当てられたメモリセグメントの / / べースアドレスを持つ。 / / 参照 ( ポインタ ) だけがコピーされる ( オブジェクトは生成されない ) 。 1 e t f Jack 標準ライプラリはビルトインのオプジェクト型 ( クラス ) として、 Array と string のふたつを提供する。 1et c Ie e Array 配列の宣言には、ビルトインのクラスである Array を用いる。 Array は 1 次 元の配列であり、最初のインデックスは 0 から始まる ( 多次元配列は、配列の配 列によって実現できる ) 。配列の要素に対しての型宣言はなく、同じ配列の要素 に別の異なる型のデータが格納されている可能性はある。配列の宣言を行うと、 それを参照する変数だけが作られる。実際の配列は、 Array ・ new(length) というコンストラクタが呼ばれるときに作られる。配列の要素へのアクセスは a [ j ] のような記法を用いる。例 9 - 2 では配列を操作する例を示した。 String 文字列の宣言には、ビルトインのクラスである st r ing を用いる。 Jack コン パイラは " xxx " というシンタックスを認識し、それを st r ing オプジェクト として扱う。 str 土 ng オプジェクトの中身は、 ( その API のドキュメントで示 すとおり ) st ring クラスのメソッドを用いてアクセスでき、また修正もでき る。具体例を次に示す。

2.2 仕様ー 31 えてみよう。 2 の補数を用いると、 4 ビット表現の 2 進数では ( 1110 ) 。十 ( 1101 ) 。 こでの計算は、対象とする数が正か負か気にすることなく を計算する必要がある。 行える。ビット単位の加算を行うと、川 11 という結果になる ( オーパフロービットは 取り除いてある ) 。図 2 - 1 が示すとおり、実際、この結果は一 5 である。 以上をまとめると、 2 の補数を用いることで、単純なビット単位の加算が行えるハー ドウェアがあれば、特別なハードウェアを用いることなく正と負のどちらの加算も行 える、ということになる。それでは、「引き算」はどうなるだろうか ? 2 の補数を用い る方式では、符号付き数字ェを反転する、つまり一ェにするには、ェのすべてのビッ トを反転させ 1 を足せばよいことは先ほど示した。したがって、エー″ = 工十 ( ーので あるから、引き算は足し算として扱うことができる。これにより、ハードウェアの複 雑さを最小限に保つことができる。 こまでの理論的考察から、ひとつの結論にたどり着く。それは、ひとつの回路に この回路は算術論理演算器 (Arithmetic Logical Unit 、 ALU) と呼ばれる 初歩的な算術演算と論理演算のすべてをまとめることができる ( できそうである ) と いうことである。それでは、これからそのような ALU を定義していこう。まずは加 算器回路の仕様から始める。 22 仕様 2.2.1 加算器 (Adder) こでは次の 3 つの加算器の仕様を示す。 2 進数の加算を行うための初めの一歩は、ふたつのビットに対して、 も、その仕様を示す。インクリメンタは与えられた数字に 1 を加算するように設計さ これに加えて、インクリメンタ (incrementer) と呼ばれる特殊な加算器について 加算器 (adder) : ふたつのれビットの和を求める 全加算器 (full adder) : 3 つのビットの和を求める 半加算器 (halfadder) : ふたつのビットの和を求める 半加算器 その和を求め