9 章: 高水準言語 高水準言語 Jack から VM 言語への変換を行うにあたって、ここで Jack 言語 (Java の簡易版みたいなもの) の仕様を一通りみておく。 変数の種類とスコープ 変数には以下の 3 つのほか、サブルーチン宣言のときのパラメータリストなどがある。 スタティック変数: あるクラスのすべてのオブジェクトで共有される変数。static で宣言。 フィール...

前章で作成した VM translator に追加して、本章ではプログラム制御 (サブルーチンの呼び出しやメモリ割り当てなど) を実装していく。 8 章 バーチャルマシン #2: プログラム制御 プログラムフローコマンド まず面倒なのが if go-to コマンドのコンパイルである。これはスタックトップの値を pop して (これは前章までの内容でいける) 0 でなければ (TRUE であ...

前章でアセンブリ言語からバイナリへの変換ができるようになったため、次は一段階上がってコンパイラを書いていく。本書では Jack という簡易版 Java みたいな高水準言語の処理系を実装していくことになるのだが、これはまず中間コード (VM コード) を経てアセンブリ言語に変換される形式を採っている。7 章および 8 章では、VM コードをアセンブリ言語に変換する VM translator ...

久々に競プロ環境を整備し直したのでメモしておく。以下、WSL2 (Ubuntu 18.04.1) と VSCode という環境下で、C++17 を用いて問題を解く際の環境設定を記載する。 VSCode のエディタ設定 昨年 9 月のアップデートから公式で提供されるようになった editor.bracketPairColorization.enabled を用いれば対応する括弧の色付け...

6 章 アセンブラ 前章までで CPU や Computer の実装が終わり、ハードウェアは完成した。次はソフトウェア部分ということで、一番下のレイヤであるアセンブラを書いていく。この章以降は HDL から離れて好きな言語でコードを書けることになるため、文字列操作に慣れた Python を使うことにした。 コマンドの判別 本書で用いられている機械語は 1 行 1 コマンドであり、@ で開...

5 章 コンピュータアーキテクチャ 本章ではついにメモリ、CPU を実装していく。 メモリの実装 基本的に p99 の仕様に従って書いていけばよい。まずは入力として与えられたアドレスがどのメモリマップに位置するかを判定する必要があるが、0-16383 が RAM に、16384-24575 がスクリーンに、24576 以降がキーボードに割り振られていることを考慮すると以下のような...

4 章 機械語 本章では Hack 機械語 というアセンブリ言語を書いていく。A がそのとき指しているアドレスの値、M がアドレス A が指しているメモリワードの値、D は値を格納できる変数のようなものと考えるとわかりやすい。 基本的に 1 や 0 以外の定数をそのまま計算に使うことはできないので、例えば定数を D に代入したい場合は @5 D = M などとするしかない...

3 章 順序回路 今回は前章まで作成した「組み合わせ回路」と違って「順序回路」を作っていく。フリップフロップ (1 ビットの入力とクロック入力を受け取り、前のタイムポイントでの入力を出力する) は所与のものとして扱う。 まずは 1 bit レジスタを作成する。1 ビットの入力と load ビットを受け取り、load ビットが 1 の場合値を更新、0 の場合入力は無視される。これも...

あけましておめでとうではあるが、特に新年感もなく粛々と復習を続けていく。今日は第 2 章、ブール算術から。 2 章 ブール算術 加算器 $n$ ビットの 2 進数加算をする場合を考える。2 つのビットの和を求める半加算器 (half adder) が必要なのはまあ当たり前である。足し算の筆算的に最下位ビットから計算していくことを考えると、2 つのビットと繰り上がり (キャ...

年末年始を利用して、2 年くらい前に買ったこの本を読んでいく。 コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方 | Noam Nisan, Shimon Schocken, 斎藤 康毅 |本 | 通販 | Amazon NAND ゲートのみが与えられた状態で、論理回路、加算器、ALU、C...