A. 9 新しいビルトイン回路ー 337 新しいビルトイン回路の開発 ハードウェアシミュレータは、 HDL で書かれた回路であればどのような回路で も実行することができる。回路拡張 A 曰を用いることで、 Java で書かれた「新 しいビルトイン回路」を実行することができる ( 図 A-2 に示した一覧に追加する ことができる ) 。ビルトイン回路は Java で書くことができ、新しいハードウェ ア部品や GUI 効果を追加したり、回路の処理速度を向上させたり、 HDLF& けで は実装できないような回路のシミュレーション動作を追加することができる ( 新 しいプラットフォームやハードウェアに関連するプロジェクトを設計する場合、 このような拡張性は重要である ) 。新しいビルトイン回路の開発の詳細について は 13 章を参照してほしい。

44 ー 3 章順序回路 以上の考察から、図 3-1 の右下の図に示される解法ーー正しい解法、そして素晴ら しい解法ーーが導かれる。見てのとおり、入力の曖昧さを取り除くには、回路設計に マルチプレクサを導入するのが自然な方法である。さらに、マルチプレクサへの「選 択ビット (select bit) 」はレジスタ回路への「読み込みビット (load bit) 」の役割を 担うことができる。もしレジスタに新しい値を保持させたいならば、その新しい値を 入力 in に入れ、「読み込みビット」である 1 〇 ad に 1 を設定すればよい。また、もし 内部の値をレジスタに保持させたいならば、 1 oad ビットを 0 にすればよい。 こまでのところ、 1 ビットを記憶する基本的な仕組みは達成できた。続いて、任 意の幅のレジスタについて考える必要があるが、これは簡単に作ることができる。と いうのは、多ビットのレジスタは 1 ビットレジスタを必要な数だけそろえて、それら を配列上に並べて構築することができるからである ( 図 3 - 2 ) 。そのようなレジスタの 設計では、幅 (width) ーーー保持すべきビットの数ーーーをパラメータとして考えなけれ ばならない。このパラメータの値の候補としては、たとえば 16 、 32 、 64 などの数字 が用いられる。そのような多ビットのレジスタの持っ値は、一般的にワード (word) と呼ばれる。 load Bit out Bit if load(t— load ↓ Bit 1 ) then out(t) = in(t-l) out if load(t—l ) then out(t) = in(t—l ) else out(t) = out(t—l ) 1 ビットレジスタ ( Bit ) else out(t) = out(t—l ) w ビットレジスタ 図 3 -2 1 ビットレジスタから多ビットレジスタへ。 w 個の 1 ビットレジスタを用いて、 w ビットレ ジスタが構築される。両方の回路において、「 = 」は代入を意味する。代入が 1 ビットと多ビットのど ちらに対応しているかという点を除けば、それ以外の操作はすべて同じである メモリ ワードを表現できたので、任意の長さのワードを記憶する「メモリ」へ進むことに する。図 3-3 に示すように、レジスタをたくさん積み重ねることで、 RAM (Random AccessMemory) ユニットを構築することができる。「ランダムアクセスメモリ」と いう名前の由来は、ランダムに選ばれたワードに対して、そのワードが位置する場所

ロ 4 ー 7 章バーチャルマシン # 1 : スタック操作 アによる方法、または、 VM プログラムを対象プラットフォームの機械語に変換する 方法によって実現することができる。 本章では一般的なバーチャルマシンのアーキテクチャを示す 。ここで小すバーチャ ルマシンは、 Java バーチャルマシン (JVM) の枠組みを手本としたものである。い つものように、我々は 2 段階で説明を行う。初めにバーチャルマシンについて仕様を 示し、続いてそれを Hack プラットフォーム上で実装する。実装を行うものの中には、 VM 変換器 (VMtranslator) と呼ばれるプログラムが含まれる。このプログラムは VM コードを Hack のアセンプリコードへと変換する。この VM 変換器とは別のアプ ローチとして、本書が提供する VM 工ミュレータを用いることができる。このプログ ラムは Java で実装されたバーチャルマシンであり、手持ちのパソコン上でバーチャ ルマシンをエミュレートすることができる。 一般的なバーチャルマシンは「言語」を持つ。 VM プログラムは、この言語を用い て書くことができる。 こで示す VM 言語には 4 種類のコマンドが含まれる。それは 「算術」「メモリアクセス」「プログラムフロー」「サプルーチン呼び出し」という 4 っ のコマンドである。この言語についての議論と実装はふたつの章に分けて行う ( 本章 と次章で行う ) 。本章では基本となる VM 変換器を作る。このべーシックな変換器は、 バーチャルマシンの「算術」と「メモリアクセス」のためのコマンドを機械語へと変 換する。次章で、「プログラムフロー」と「サプルーチン呼び出し」の機能を備えるよ うに、そのべーシックな変換器を拡張する予定である。結果として完全なバーチャル マシンができあがり、これは 10 ~ 11 章で作るコンパイラのバックエンドとして動く ことになる。 バーチャルマシンはコンピュータサイエンスにおいて重要な位置を占めている。コ ンピュータで別のコンピュータをシミュレートするというアイデアの原型は 1930 年 代のアラン・チューリングまでさかのばる。バーチャルマシンはこれまでに多くの実 用的な使い方が提案されてきた。たとえば、コードの上位互換性を満たすために、新 しいプラットフォーム上で前世代のコンピュータをエミュレートするといった用途で ある。また最近では、 Java プラットフォームと . NET フレームワークというふたつの 主要な実行環境において、バーチャルマシンのモデルが中心的な役割を担っている。 これらの実行環境 (Java プラットフォームと . NET フレームワーク ) は割と複雑であ るから、その内部構成を理解するためには、ます単純な VM を作ることから始めるの がよいであろう。 本章で述べるもうひとつの重要なトピックはスタック処理 (stack processing) に ついてである。スタック (stack) は多くのコンピュータシステムやアルゴリズムで用

164 ー 7 章バーチャルマシン # 1 : スタック操作 7.5.2 テストプログラム こでは 5 つの VM プログラムをリストする。それぞれ、先に説明した実装ステー ジのためのユニットテストとして用いることができる。 ステージ # 1 : スタック算術 SimpIeAdd ふたつの定数を加算し、ブッシュする。 S t a c k T e s t 一連の算術命令と論理命令をスタック上で行う。 ステージ # 2 : メモリアクセス BasicTest 仮想メモリセグメントを用いて、 p 〇 p 命令と push 命令を実行する。 P 〇土 nt e r T e s t p 〇 inter 、 this 、 that セグメントを用いて、 p 〇 p 命令と push 命令を実行 する。 S t at 土 c T e s t static セグメントを用いて、 pop 命令と push 命令を実行する。 たとえば、 xxx というプログラムに対しては、 xxx . ▽ rn 、 XxxVME . tst 、 xxx . tst 、 xxx . cmp という 4 つのファイルが与えられている。 xxx . vm ファイルは VM のプロ グラムコードである。 XxxVME . t st というスクリプトは、本書の VM 工ミュレータ 上でプログラムを実行することができ、プログラムの意図した動作を前もって見るこ とができる。あなたが実装した VM 変換器を用いてプログラムの変換が完了すれば、 与えられた xxx. t st と xxx. cmp スクリプトを用いてテストすることができる。そ の場合、 CPU 工ミュレータを用いて、変換後のアセンプリコードをテストせよ。 7.5.3 助言 初期化 変換後の VM プログラムはどのようなプログラムであれ、それが実行を開始するた

% ー 5 章コンピュータアーキテクチャ と呼ばれる。 Hack の ROM は、図 5 - 3 に示すように、 32K のアドレスを持ち、各ア ドレスには 16 ビットレジスタが配置されている。 回路名 入力 出力 関数 コメント ROM32K address [ 15 ] ou むは 6 ] / / 1 6 ビット読み込み専用の 3 2K メモリ / / ROM のアドレス / / ROM[address] の値 out=ROM[address] / / 16 ビット代入 ムを読み込むための仕掛けを用意しなければならない。 ルトイン回路として取り扱うことができる。シミュレータは、この ROM にプログラ ROM には機械語のプログラムがあらかじめ読み込まれている。この ROM 回路はビ address ROM32K 52.4 データメモリ 図 5 - 3 命令メモリ out Hack のデータメモリ回路は、 3 章で作成したような一般的な RAM ( 図 3 - 3 参照 ) と同じインターフェイスを持つ。データメモリのれ番目のレジスタの値を読み込むた めには、メモリ入力の address にれを設定し、メモリ出力の〇 ut を調べるようにす る。これは「組み合わせ操作」であるから、この命令はクロックとは独立して動作す る。れ番目のレジスタにという値を書き込むためには、入力の in にむを、 addre s s にれを、メモリの load ビットを 1 に設定する。これは「順序操作」であるから、新 しい値であるむがれ番目のレジスタに書き込まれるタイミングは次のクロック周期に おいて行われる。 データメモリは汎用的なデータの格納に用いられるのに加えて、メモリマップを用 いて I/O デバイスと CPU との間のインターフェイスとなる。

266 い 1 章コンバイラ # 2 : コード生成 1 れ 3.1 JackCompiIer モジュール コンパイラは与えられた s 〇 urce に対して処理を行う。 s 〇 urce は、 xxx. jack と いうようなファイル名、もしくは、 . j ack ファイルが含まれるディレクトリ名である。 入力ファイルである各 xxx . jack に対して、コンパイラは JackTokenizer と出力ファ イルである xxx. vm を生成する。続いて、 3 つのモジュールーーーー CompiIationEngine 、 SymbolTabIe 、 VMWriter—を用いて出力ファイルへ書き込みを行う。 1 1 .3.2 JackTokenizer モジュール トークナイザの API は 10.3.2 節で与えたものと同じである。 11.3.3 Symbo 灯åb 厄モジュール このモジュールは、シンポルテープルの作成とそれを使用するためのサービスを提 供する。シンポルはそれぞれにスコープがあり、そのスコープによってソースコード 内で各シンポルの見える範囲が決定される。シンポルテープルはこの抽象化を実装す るために、各シンポルにスコープ内における実行番号 ( インデックス ) を与える。イン デックスは 0 から始まり、テープルに識別子が追加されるたびに 1 すっ加算され、新 しいスコープが始まると 0 にリセットされる。次に示す属性の識別子がシンポルテー プルに現れる ( 可能性がある ) 。 Static スコープ : クラス スコープ : クラス Argument ーチン ( メソッド / ファンクション / コンストラクタ ) スコープ : サプル ーチン ( メソッド / ファンクション / コンストラクタ ) スコープ : サプル 工ラーのない Jack コードをコンパイルした場合、シンボルテープルで見つからない 哉別子があると、それはサプルーチンかクラスの名前のどちらかであると想定するこ とができる。 Jack 言語の構文では、そのふたつの可能性を見分けることができるルー ルがあるため、そして、コンパイラによって " リンク " を行う必要がないため、それ Field Var

62 ー 4 章機械語 4.1.2 0 ロ 機械語のプログラムは一連の符号化された命令である。たとえば、 16 ビットコン ピュータで用いられる一般的な命令は、 1010 0 0110 0 0110 01 のような形式になる だろう。この命令の意味を理解するためには、 " ゲームのルール " を知らなければな らない。ゲームのルールとは、つまり、基板となるハードウェアプラットフォームの 命令セットである。たとえば、その機械語における命令は 4 ビットの領域が 4 っ合わ さって構成されており、一番左の領域が CPU 演算、残りの 3 つの領域がその演算の オペランドになっているとしよう。そうすると、先に例として挙げた機械語のコード は「 R3 に RI + R9 をセットする」という演算に相当するかもしれない。もちろん、 れはハードウェアの仕様と機械語の構文によって決定される。 バイナリコード ( 2 値コード ) はいくぶん暗号めいているため、機械語は通常、バ イナリコードとニーモニックの両方を用いて記される。 ーモニック (mnemonic) は記号や英単語で記され、その名前によって何を行う命令かを把握することができる 我々の場合、ハードウェアの要素と演算をニーモニックで表記する。たとえば、 1010 という命令コードはニーモニックで表すと ADD になり、レジスタは RO 、 RI 、 R2 という記号で表される、といったことを言語の設計者は決めることができる。この ような作法を用いれば、機械語で書かれた命令を「 1010 0 0110 0 0110 01 」のように 直接指定することもでき、さらに、「 ADD R3 ′ RI ′ R9 」のように記号を用いて指定す ることも可能になる。 この記号による抽象化をさらに推し進めると、記号による表記は読むためだけに用 いるのではなく、プログラムを書くためにも用いることができる。つまり、バイナリ コードで書く代わりに、記号によるコマンドを用いてプログラムを書くことができる。 その場合、テキスト処理のプログラムを用いて、その記号コマンドを領域単位 ( ニーモ ニックとオペランド ) へ分解し、領域ごとに対応するバイナリ表現へと変換すればよ い。そして、その結果を組み合わせれば機械語の命令コードが完成する。この記号によ る表記はアセンブリ言語 (assembly language) または、単にアセンブリ (assembly) と呼ばれる。また、アセンプリから機械語であるバイナリへと変換するプログラムはア センブラ (assembler) と呼ばれる。 コンピュータが異なれば、 CPU の命令セット、レジスタの数や種類、アセンプリの 構文ルールなども異なる。そのため、さまざまな機械語が存在し、それぞれに固有の 構文を持っことになる。しかし、この多様性にもかかわらす、どのような機械語であ れ、同じような一般的なコマンドをサポートしている。続いて、そのような一般的に

69 @ぉ 0 ん e バイナリ : 0 v v V 4.2 Hack 機械語の仕様ー / / va 旧 e は非負数の 1 0 進数表記、または 〃そのような数値を参照するシンボル ? 第〃肥 ( v = 00r 1 ) この命令を用いることで、特定の値を A レジスタに格納することができる。たとえ う。ほとんどすべての仕事は、この命令によって行われる。この命令コードは、次の C 命令は、 Hack プラットフォームにおいて、プログラミングの中心的な役割を担 42.3 C 命令 る命令の位置を移動することができる。これらの使い方の具体例は図 4-2 で示した。 むことで、その後に続く移動を行うための C 命令 (jump 命令 ) を用いて、次に実行す は移動命令の用途である。あらかじめ A レジスタに移動先のメモリアドレスを読み込 て、 A レジスタで指定したメモリ位置にあるデータを操作することができる。 3 つ目 かじめ A レジスタにメモリのアドレスを設定することで、その後に続く C 命令におい ジスタを用いる方法しか存在しない。ふたつ目はメモリ操作を行う用途である。あら て定数を代入する用途である。プログラムによって定数を代入する方法は、この A レ A 命令は 3 つの異なる用途で使用することができる。ひとつ目は A レジスタを用い A レジスタに保存することができる。 ば、 @5 という命令は、 0000000000000101 と等しく、 5 の 2 進数で表記した値を 3 つの質問に答えることができるように、その仕様が決められている。 次に何をするか ? 計算した結果をどこに格納するか ? 何を計算するか ? c 命令がこれらの仕様に従えば、 A 命令と一緒に用いる一 うすべての命令を実行することができる。 と 0 、 コンピュ ータで行

370 ー付録 C Nand2tetris software suite の使い方 現在のディレクトリをコンバイルする ・ \projects\09\Ref1ect>JackCompi1er CompiIing "c:\ . ・ \PE0jects\09\RefIectj' 単一のファイルをコンバイルする ・ \projects\09\RefIect>JackCompi1er M 土てて 0 て s . jack Compi1ing "C:\ . ・ \projects\09\Ref1ect\Mirrors . jack'l ・ : ・「 Reflect 」というディレクトリをコンパイルする . \projects\() 9>JackCompi1er Ref1ect Compi1ing 日 C : \ . . \projects\09\Ref1ect" テキスト比較 (TextComparer) テキスト比較ツールを用いれば、与えられた 2 つのファイルを比較し、それらが等 しいかどうかを判定することができる。たとえば、ハードウェアシミュレータでテス トスクリプトを実行し、比較結果が異なったとしよう。その場合は、 TextComparer を使って、次のように問題箇所を特定することができる。 ・ \projects\02>HardwareSimu1ator ALU. tst Comparison failure at line 24 . \projects\02>TextComparer ALU. cmp ALU. out Comparison failure in line 23 : 国 10110111010000 田 000111101101001 田凵新 0 国国印 00111101101001 のの 210110111010000 の 0001111011010010 はは国国印国 00111101101001 の田 ヘルプ Windows では、各バッチファイルの引数に「 / ? 」を与えれば、そのバッチファイ ルの使用方法が表示される (Mac や Unix/Linux の場合はト h 」 ) 。 . \projects\09>JackCompi1er / ? Usage: JackCompiler JackCompiIer D 工 RECTORY Compiles a11 . jack files in the current working directory. Compiles a11 . jack files in D 工 RECTORY .

304 い 2 章 イ丁つ。 オペレーティングシステム Math. sqrt() になるかもしれない。これに対応するためには、土 f 文のロジックを次で示す文に置き 図 12-3 の朝十 2 つ 2 という計算はオーパフローを起こし得るから、結果は負の数 12.1.4 節で説明したように、文字列は配列を用いて実装される。同じように、文字 12.3.2 String then 朝 + 2 つ 2 ミの and ( 朝 + 2 つ 2 > 0 ) 換えればよい。 ″ = ″十ア 棄は、 Memory . deA110c() を用いて明示的に行わなければならない。 Memory . a11〇C() を呼び出して明示的に割り当てる必要がある。同様に、配列の破 すること ( その名前にもかかわらす ) 。そのため、新しい配列のメモリ領域は、 Array . new ( ) はコンストラクタではなく、ファンクションであることに注意 12.3.3 Array に対応する、ということである。 改行、バックスペース、ダブルクオートの ASCII コードは、それぞれ 128 、 129 、 34 このクラスの他のサプルーチンの実装は簡単であろう。ひとつ注意するとすれば、 実装することができる。両方のアルゴリズムとも負の数を扱わない点に注意すること。 このファンクションは図 12-4 と図 12-5 で示したアルゴリズムを用いて、それぞれ String. intVaIue 、 String. setlnt いようにする一一一ということである。 れなければならない。そして、その長さを超える配列要素は文字列の一部と見なさな 装の詳細について重要な箇所は、一一一文字列の実際の長さは、その操作の間中保持さ 列に関連するすべてのサービスは配列の操作を用いて実装することができる。この実