LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@garudakai

【書評】コンピュータシステムの理論と実装 第2版（Nand2Tetris）

Last updated at Posted at 2025-04-09

O'Reilly Japan - コンピュータシステムの理論と実装 第2版を読んだので，その書評を書きます．合計でかかった時間は113時間でした．まだ最後の12章の実装課題は終わっていませんが，それ以外の章は全て実装を終えました．

6章以降の実装はGo言語で行い，そのコードはこちらにあります．

本書の概要

公式サイトの紹介文を引用します。

コンピュータシステムをゼロから作って学ぶベストセラー書の改訂第2版。コンピュータを理解するための最善の方法はゼロからコンピュータを作ることです。コンピュータの構成要素は、ハードウェア、ソフトウェア、コンパイラ、OSに大別できます。本書では、これらコンピュータの構成要素をひとつずつ組み立てます。具体的には、NANDという電子素子からスタートし、論理ゲート、加算器、CPUを設計します。そして、アセンブラ、仮想マシン、コンパイラ、OSなどを実装しコンピュータを完成させて、最後にその上でアプリケーション（テトリスなど）を動作させます。

第一部はハードウェア，第二部はソフトウェアについて扱っており，それぞれ6章と最後の章の合計13章からなります．各章はおよそ30ページ前後で，各章の終わりに実装課題が設けられています．各トピックが綺麗にまとまっており，読みやすい構成になっています．

前提

筆者について

  • 情報系（数理）の大学院生だが，コンピュータサイエンスについてはあまり詳しくない
    • プログラミングの経験，数理とその関連分野（グラフ理論，最適化，アルゴリズムなど）の知識はある
    • 一方，ネットワーク，データベース，OS, etc.については勉強中．
  • PythonやJuliaなど、いくつかのプログラミング言語を学んだことがある

読書の背景

  • 情報系の大学院への進学が決まり、春休みに少し時間があったため、コンピュータサイエンスを基礎から学んでみることにしました．

本書を選んだ理由

  • 本書の想定読者は「（言語を問わない）プログラミング経験者」だった
    • 特別な知識がなくても読めるという点が魅力的だった
  • それでいて，CPU、アセンブリ言語、コンパイラ、OSなどの幅広い分野をカバーしているため、コンピュータサイエンスの全体像を捉えるのに適していると考えた
  • 「Nand2Tetris」という名前が面白そうだった
  • 世界中で高い評価を受けている教材だった

感想

各章の読書と実装にかかった時間は以下の通りです。合計では94h程度かかりました。実装時間はあくまで目安であり、個人差があると思いますので、参考程度にしてください。特に私は，テストを通すように実装したり，適宜リファクタリングを行ったりしたため，時間がかかりました．

章 読書時間 実装時間
1 1h 1.5h
2 1h 2h
3 1h 3h
4 4h 3h
5 2h 3h
6 2.5h 8h
7 1.5h 15h
8 3h 10h
9 1.5h 3h
10 2h 22h
11 3h 17h
12 1.5h 0h
13 0.5h 0h
合計 24.5h 88.5h

良かった点

全体を通じて、まず文章が非常にわかりやすく、読みやすかったです。読んでいるだけでも、つい面白くて読み進めてしまいました。また、「最適化には全く立ち入らない」という方針が素晴らしいと感じました。現実のコンピュータを題材にすると、本質的でない仕様や機能に時間を割かれてしまい、理解も難しくなりますが、本書では教育専用にHackコンピュータやJack OSが設計されているため、本質的な部分に集中することができました。

第一部のトピックはハードウェアですが、実装はソフトウェアで完結している点も素晴らしいと思いました。電子工作を実際にするとなるとハードルが高いですが、本書ではシミュレータを使ってハードウェアを理解することができます。

実装課題については、指示が具体的でありながら丁寧すぎず、ちょうど良く自分で作る楽しみを味わえるようになっています。この塩梅が絶妙で、素晴らしいと感じました。ただし、6章のアセンブラなど、ある程度のプログラミング経験がないと自走するのは難しいかもしれません。そのため、あらかじめ不安がある方は、何人かで取り組むと良いかもしれません。

ただ，後半7章以降（第二部ソフトウェアのセクション）の実装課題から，急激に難易度とボリュームが上がったように感じました．本での指示・指定もかなりざっくりしたものになり，読者は設計から計画して，実装を行う必要があります．そのため，かかる時間も急激に増えました．その一方で，実装課題の質は高く，どんどん理解が深まるのを実感できました．逆に言うと，7章以降は特に，前の章の実装課題をしっかりと理解していないと，次の章を読んで理解することが難しくなります．

最後に、Web IDEは非常に使いやすかったです。エディタとして必要な機能も十分に揃えており、視覚的にもわかりやすいようにデザインされています。ただし、後述しますが、CPU Emulatorに関しては挙動がやや不安定で、いくつかissueも報告されているため、その点は注意が必要です。

イマイチだった点

非常に満足度が高かったのですが、強いて挙げるとすれば、Web IDEのCPU Emulatorの挙動が不安定だった点です．仕様なのかバグなのかがわからないこともありました。最近、いくつかのissueも報告されているので、改善されることを期待しています。自分が直面した問題と関連するGitHub issueを以下に示します。

問題1

Web IDEのROMでは，@xのように変数を命名することができない
解決策：ローカルでアセンブリ（.asmファイル）を編集し，それをROMに読み込んで利用する

問題2

ローカルファイルを読み込むとテストファイルが使えない，および，既存のテストファイルを読み込むと，ROMが初期化される．つまりテストを通せない．

解決策：ローカルファイルを読み込んだのち，自分でRAMにデータを書き込んでユニットテストを行う

問題3

selelct local fileで一度ファイルを読み込んだ後に，もう一度読み込もうとすると失敗する．

解決策：ページをリロードする

次に読みたい本

本書ではかなり幅広い分野が扱われていたおかげで、様々な分野に興味を持てるようになりました。

TODO: 次に読みたい本を書く

こんな人におすすめ

  • プログラミング経験があり、コンピュータサイエンスの基礎を学びたい方
  • 情報系出身で、大学で学んだ経験はあるが、いまいち理解が深まらなかった方
    • 点と点が線で繋がるような感覚が得られると思います
  • プログラミングを習いたて（または学びたて）の情報系の1,2回生
    • 実習やより高度な内容の講義への接続に役立つと思います

他の方の書評

自分が参考にさせていただいた書評を以下に示します。

各章ごとの自分のメモ

一応、各章ごとの自分のメモも残しておきます。もしかしたら実装課題のヒントになるかもしれません。

各章ごとの自分のメモ # コンピュータシステムの理論と実装 第2版 ―モダンなコンピュータの作り方 - 1/23開始 ## まえがき - まえがきからドラマチックでワクワクさせてくれる - 最近の学生は，「木を見て森を見ず」らしい - 低レイヤの世界を熟知しているかどうかが，平凡なプログラマと優れた開発者とを分ける試金石になる． - 説明が丁寧．指示が明瞭．各部，各章の初めにこれからすることを明示してくれる

第一部 ハードウェア

  • nand to tetrisではなぜ独自のコンピュータとプログラミング言語を使うか？
    • 既存のコンピュータのモデルは，いずれ時代遅れになるから．プログラミング言語も同じ．
    • 実際に使用されているコンピュータやプログラミング言語には，教育的に重要でない仕様が多くあり，実装に時間がかかる
    • 制御，理解，拡張が容易なハードウェアとソフトウェアを作ることで，コンピュータの基本的な原理を理解しやすくなる
    • →「Hack」と「Jack」が生まれた
  • 下層のモジュールを使用するときはいつでも，そのモジュールを既製のブラックボックスとして扱うことができる．必要なのはモジュールのインターフェースに関するドキュメントだけ．
  • 芸術の域に達するほどのモジュール設計のセンスは，多くの優れた実例を見ながら実践することで磨かれる

1章 ブール論理

読む：約60min
実装：約80min

  • ブール論理
    • 演算子
      • And: $x \dot y$
      • Or: $x + y$
      • Not: $\bar{x}$
    • 全ての論理演算は，And, Or, Notの組み合わせで表現できる
    • And, Or, NotはどれもNandで表現できる
    • つまり任意の論理演算はNandで表現できる
      • 証明は付録Aにある
  • 論理ゲート
    • ゲート：ブール関数を実装する物理デバイスのこと．ほとんどが電気で実装されるが，必ずしもそうでなくてもよい．
    • チップとしてパッケージ化される
    • ゲートのインターフェースと実装
      • インターフェース：入力と出力の数と，それらの間の論理関係
      • 実装：And, Or, Notを使って，インターフェースに従った論理関係を実現する方法
    • 今の時代，ハードウェア設計者はものを作るために手を汚さなくて良い
  • ハードウェア記述言語（Hardware Description Language:HDL）
    • 内部ピン
    • テストスクリプトもある
  • マルチプレクサ
    • 2つの入力a,b（データビット）を持ち，制御入力sel（選択ビット，セレクタ）によってどちらかの入力を出力する
      • sel=0のとき，aを出力
      • sel=1のとき，bを出力
    • 信号の多重化（Multiplexing，Siriアライズともいう）から来ている
    • 複数ビットver.
      • $m$本ある$n$ビット入力のマルチプレクサは$k=\log_2 m$ビットのselを持ち，$n$ビットの出力を持つ
  • デマルチプレクサ
    • 1つの入力inを受け取って，sel（選択ビット）に従って，二つの出力a,bのどちらかに振り分ける
      • sel=0のとき，aに振り分ける．bは0
      • sel=1のとき，bに振り分ける．aは0
    • 複数ビットver.
      • $n$ビットの入力を持つデマルチプレクサは$k=\log_2 m$ビットのselを持ち，$m$本の$n$ビットの出力を持つ
  • 複数ビット
    • HDLでは右から左にインデックスがつけられ，右端のビットが0ビット目
  • ビルトインチップのおかげで，途中でつまづいても，次のステップに進める
    • 次に進むときにはファイル名を少し変えればOK

実装

  • 代入のようなことをしたいなら，「 0 or x」もしくは「1 and x」を使うとよい
  • if x then yは，not x or yと等価
  • sel[0..1]のようにスライスできる
    • HDLサバイバルガイドに書いてた
  • デマルチプレクサは入力を分岐していく
    • DMux4Wayならまず二つに道を分けて，その後さらに二つに分ける

2章 ブール算術

読む：約70min
実装：約110min

  • ワードサイズ：基本的な処理単位のビット数
    • 通常は8,16,32,64ビットのレジスタ
  • 最下位ビット（Least Significant Bit; LSB）
  • 最上位ビット（Most Significant Bit; MSB）
  • MSBの桁上がり（Carry）はオーバーフローとして無視する
  • 負の数：2の補数表現
    • 正負の数の加算・減算が整合的になるように設計されている
    • -xを表現するのに2^n - xを使う
    • mod 2^nの世界で考える
  • 半加算器（Half Adder）
    • 二つの半加算器で全加算器が作れるから，「半」加算器
    • 入力:a,b，出力:sum,carry
    • carryは桁上がり
    • 2bitの加算器と見れば，sumはLSB，carryはMSB
  • 全加算器(Full Adder)
    • 3つの1bit入力a,b,cを持つ
    • 半加算器を2回使って実装
      • carry1とcarry2が桁上がりすることはない
  • 加算器
    • オーバーフローは無視
    • 本書の加算器は効率は悪い．効率化したバージョンとして，Carry Lookahead Adderがある
  • インクリメンタ
    • 加算器でも実装できるが，インクリメンタがあればより効率的に実装できる
  • ALU(Arithmetic Logic Unit; 算術論理演算器)
    • Hack専用の仕様
    • ALUで0を反転させると-1になる
      • 00000→11111
  • 展望
    • ALUとOSとの間で，どのように必要な機能を割り当てるか，という問題は，本質的に「コストとパフォーマンス」の問題になる
      • 原則，算術演算と論理演算を直接ハードウェアに実装したほうが効率的だが，その分コストがかかる

実装

  • HDL付録を読む
    • 定数を扱うには，trueとfalseを使う
    • 部分的に入力を指定した場合，指定していない残りの値はデフォルトのfalseになる
    • 「スタブ」とは、テスト対象から見た下位モジュール(呼び出される側)に成り代わる中身をもたないテスト専用のダミー部品
  • Add16(a=in , b[0..0]=true,b[1..15]=false, out=out );のような感じで入力を部分的に指定できる
  • 半加算器（Half Adder）
    • 2bitの加算器と見れば，sumはLSB，carryはMSB
  • 全加算器(Full Adder)
    • 半加算器を2回使って実装
      • carry1とcarry2が桁上がりすることはない
  • 加算器
    • オーバーフローは無視
    • 本書の加算器は効率は悪い．効率化したバージョンとして，Carry Lookahead Adderがある
    • 加算器は，ゴリゴリ脳筋で実装してしまったけど良いのか？
  • インクリメンタ
    • 半加算器だけでゴリゴリ実装した．
    • 一応，半加算器を使う回数が半分になったが，さらに効率化できるかもしれない
  • ALU(Arithmetic Logic Unit; 算術論理演算器)
    • zrの実装につまる
      • Or8Wayを使いたいが，Internal Pins cannot be subscripted or indexedと怒られる
      • Or16Wayを定義したいが，「ヘルパーチップ」の実装は推奨されていない
      • outを入力にしたいが，Cannot use output pin as inputと怒られる
      • p.387に解決策あり．outを分けて出せばOK

3章 メモリ

読む：約60min
実装：約180min

  • 組み合わせ回路（Combinational）：時間を気にせず，入力に対して常に同じ出力を返す
  • 組み合わせチップ（or 非同期チップ）：現在のクロックサイクル中の変化に対して即座に反応する
  • 順序回路（Sequentioal）：現在の入力と以前の入出力に基づいて，出力を返す
  • 順序チップ（or 同期チップ）：DFFなど．
  • クロック
    • tick：クロックの立ち上がり
    • tock：クロックの立ち下がり
    • サイクル（cycle）：tickからtockまでの時間
      • 時間を離散化したときの各区切り．これ以上小さい間隔の時間は扱えない
      • 論理演算における，信号の入出力や演算にかかる時間よりは長く設定されている
      • サイクルはシステムで起きうる遅延の最大値よりも大きくないといけない
      • 一方，サイクルが小さいほどコンピュータは高速に動作する
      • 現在は10億分の1秒（1GHz）が一般的
    • マスタークロック：全てのチップに接続されたクロックのこと
  • DFF（Data-Flip-Flop; Dフリップフロップ）
    • out(t)=in(t-1)
  • Bit：1bitのレジスタ
  • Register：16bitを持つレジスタ
  • ランダムアクセスメモリ（RAM）
    • n個のレジスタを集めたもの
      • コンピュータでは，レジスタとメモリは別物では？？
    • アドレス入力のサイズは$k=\log_2 n$ビット
    • Hackアーキテクチャでは16K（16,384）の16ビットレジスタを必要とする
    • 読み出しの時にはマルチプレクサを，書き込みの時にはデマルチプレクサを使えば瞬時にアドレスを選択できる
  • カウンタ(プログラムカウンタ；PC)
    • reset(t)==1のとき，out(t+1)=0
    • load(t)==1のとき，out(t+1)=in(t)
    • inc(t)==1のとき，out(t+1)=out(t)+1
    • その他のとき，out(t+1)=out(t)
  • データ競合（Data Race）

実装

  • Bit：1bitのレジスタ
    • DFFの使い勝手がわからない
      • Project 3 - 1-bit register HDL implementationを見て，コードをコピペ＆改変してAC
        • Muxにいきなり未定義変数を入れてもOK．宣言型言語だから，順番は関係ない...?
        • outを二つ用意できる．out=out1, out=out2とか
      • HDLの仕様がイマイチわからない
  • PCの実装にも結構苦労した
    • reset, load, inc, 何もしない，という条件分岐を先にselとして処理してマルチプレクサに入力しておく．マルチプレクサの出力で毎回outを更新する（更新しない場合も含んで，load=trueにしておく）ようにしたら，比較的スッキリ実装できた
    • 人の回答も気になるところ．
    • 2bit同士の加算にAdd16を使ってしまっていて美しくない

4章 機械語

読む：約220min
実装：約180min
（バグとの格闘．．．）

  • 機械語（Machine Language）：特定のハードウェアで直接実行され，そのハードウェアを完全に制御できるよう設計されている
    • 一方，高水準言語：表現力や，プラットーフォーム間の互換性を目標に設計される
    • コンピュータにおける最も奥深いインターフェース
  • 機械語はプロセッサとレジスタを用いてメモリを操作するように設計されている．
    • メモリ：データや命令を保存する連続したセルの列．
      • 各セルは，メモリレジスタ（or メモリ位置）といい，固有のアドレスを持つ
    • プロセッサ：通常，CPUのこと．
    • レジスタ：プロセッサの内部にある．
      • メモリとプロセッサは独立していて，それらの間でデータをやり取りするには比較的時間がかかる．
      • →レジスタをプロセッサ内部に置くことで，高速なローカルメモリとして機能させる
      • データレジスタ（D）とアドレスレジスタ（A）の2種類ある
  • 機械語はバイナリと記号の2種類で書くことができる．
    • 記号による機械語をアセンブリ言語という．アセンブラによって，記号がバイナリに変換される．
      • アセンブラは6章で開発する
    • アセンブリ言語はハードウェアに依存する．
  • シンボル参照を仕様するコードは，書きやすい．加えて，任意のメモリ位置にロード命令を生成できる←？
    • 再配置可能なコード（Relocatable Code）
  • Hack 機械語
    • Hackコンピュータはノイマン型アーキテクチャの16bitコンピュータ
    • Hack命令で扱うレジスタは，アドレスレジスタ（A），データレジスタ（D），メモリレジスタ（M）である．
      • A, Dはプロセッサに内蔵されているレジスタのこと
      • Mは（プロセッサとは独立したチップである）メモリの各セルのこと
      • Aは次の3つの使い方ができる
        • 1．データレジスタとして使う
        • 2．アドレスレジスタとして，データメモリのアドレスを指定する
        • 3．アドレスレジスタとして，命令メモリのアドレスを指定する
        • だからこそ，扱いが複雑
      • Dはデータを保存しておくだけ
    • データメモリ（RAM）：読み書き可能
    • 命令メモリ（ROM;Read Only Memory）：読み出し専用
    • address：メモリのアドレス
    • @xxx：Aレジスタの値をxxxにセット．
      • アドレスがxxxであるRAMレジスタが「選択されたメモリレジスタM」になる
      • アドレスがxxxであるROMレジスタが「選択された命令」になる
      • どちらを無視するかは以降の命令に依存
      • つまりAレジスタは同時に二つの異なるアドレス指定を行っている
    • @xのように変数を命名すれば，その変数をメモリ内のどこに置くかをアセンブラに決めさせることができる．
    • R0,...,R15：16個のビルトインシンボル．仮想レジスタという．
    • アドレス命令（A命令）
      • 定数なら，Aレジスタにその値をセットする．
      • 変数なら，Aレジスタにその変数のアドレスをセットする．
      • 記号：@xxx xxxは0~2^15-1の整数
      • バイナリ：0vvv vvvv vvvv vvvv
        • 0：A命令のオペコード
    • 計算命令（C命令）
      • 記号：dest=comp;jump
      • バイナリ：111a cccc ccdd djjj
        • a：0（Aレジスタを使う）か1（Mレジスタを使う）
        • comp：computation;ALU演算
          • ALUは二つの入力を受け取る．一つはDレジスタから，もう一つはAレジスタかMレジスタから（aの値による）
          • accccccの7bitで計算を指定するので，128種類使えるが，実際には28種類しか定義されていない．
        • dest：destination; 出力先
          • dddの各桁は，それぞれAレジスタ，Dレジスタ，Mレジスタの出力を指定する．
            • 同時に複数に保存することもできるし，何もしないこともできる．
        • jump：条件分岐
          • jjj:の各桁はALU出力が負，0，正の場合にジャンプするかどうかを指定する
            • 000：ジャンプしない
            • 001：null
            • 010：JGT：ALU出力が正のときジャンプ
            • 100：JLT：ALU出力が負のときジャンプ
            • ...
            • 111：常にジャンプ
    • Aレジスタの競合防止
      • @nを使うと，RAM[n]とROM[n]がどちらも選択される．その後の命令としては，
          1. RAM[n]として指定されたMレジスタを操作するC命令
          1. ROM[n]として指定された命令にジャンプするC命令
      • この競合を防ぐために本書では以下のルールを定める．
        • 1．Mを参照するC命令ではジャンプしない
        • 2．ジャンプするC命令ではMを参照しない
    • シンボル
      • 定義済みシンボル（ビルトインシンボル）
        • R0,...,R15は単に0,...,15にバインドされている
          • これはコードを読みやすくするため
          • これらを用いた時には，データメモリのアドレス選択に使用されることを示唆する．
          • 逆に，これらを使わず単に@7のように書いた時には，Aがデータレジスタとして使われることを示唆する．
        • SP：0
        • LCL：1
        • ARG：2
        • THIS：3
        • THAT：4
        • SCREEN：16384
        • KBD：24576
      • ラベルシンボル
      • 変数シンボル
        • 変数は16から始まる固有の番号にバインドされる
    • 入出力
      • スクリーン
        • スクリーンは横512×縦256のビットマップ
        • スクリーンの左上隅はRAM[SCREEN]に対応
      • キーボード
        • キーが押されると，キーに対応する16ビットの文字コードがRAM[KBD]に書き込まれる
          コード例
// メモリアクセス
// D=17
@17 // Aレジスタに17をセット
D=A // DレジスタにAレジスタの値をセット

// RAM[100]=17
@17
D=A

@100 // Mレジスタの番地に100をセット
M=D // Mレジスタの100番地にDレジスタの値をセット

// RAM[200]=RAM[100]
@200
D=M // DをRAM[200]（Mの200番地の値）にセット．
@100
M=D // RAM[100]（Mの100番地の値）をDにセット．

// 条件分岐
// goto 29
@29
0;JMP // 29番地にジャンプ

// if (D>0) goto 63
@63
D;JGT // Dが0より大きいとき，63番地にジャンプ
// D;JEQなら Dが0と等しいとき，63番地にジャンプ

// 変数
@x
M=-1 // Mのx番地に-1という値をセット．x番地が実際どこにあるかは知らなくてOK．

// count = count-1
@count
M=M-1

// sum=sum+x
@x
D=M
@sum
M=M+D
  • Hackプログラミング
// RAM[2]=RAM[0]+RAM[1]+17

@17
D=A

@R0
D = D+M

@R1
D =D+M

@R2
M=D

// 無限ループに入ることで終了する
(END)
	@END
	0;JMP

例2


@i
M=0

@sum
M=0
(LOOP)

@i
D=M

@R0
D=D-M

@STOP
D;JGT

@sum
D=M

@i
D=D+M

@sum
M=D

@i
M=M+1

@LOOP
0;JMP

(STOP)
@sum
D=M
@R1
M=D
(END)
@END
0;JMP

実装

Mult.asm

@i
M=1

// RAM[R2]=0
@R2
M=0

(LOOP)
// if i>RAM[R1], then stop
@i
D=M

// i-R1
@R1
D=D-M

// if D>0, then jump
@END
D;JGT

@R0
D=M
@R2
M=D+M
@i
M=M+1
@LOOP
0;JMP

(END)
@END
0;JMP

Fill.asm

(MAIN)
@KBD
D=M

@WHITE
D;JEQ

@BLACK
D;JNE

(BLACK)
@color
M=-1
@FILL
0;JMP

(WHITE)
@color
M=0
@FILL
0;JMP

(FILL)
// i = 0
@i
M=0
@LOOP
0;JMP

(LOOP)
// if  8191-i<0 , then jump to MAIN
@8191
D=A
@i
D=D-M
@MAIN
D;JLT

// fill screen
// color -1: BLACK, 0: WHITE
// @color
// D=M

@SCREEN
D=A
@i
D=D+M
@i_offset
M=D

@color
D=M
@i_offset
A=M
M=D

// increment i and loop again
@i
M=M+1

@LOOP
0;JMP

(END)
@END
0;JMP

5章 コンピュータアーキテクチャ

読む：約135min
実装：約190min

  • プログラム内蔵方式（Stored Program）：プログラムのロジックがハードウェアに埋め込まれたものではなく，メモリに保存された命令に基づいて動作するように設計されたもの
    • 現代のCSにおいて，最も重要な発明の一つとされている
  • メモリ
    • データメモリ（Data Memory）
    • 命令メモリ（Instruction Memory）
      • 高水準の文（Statement）は一つ以上の低水準の命令に変換されて，バイナリ値としてファイルに書き込まれる．
        • このファイルは，バイナリプログラムor実行可能なプログラムと呼ばれる
      • プログラムの実行の際には，記憶装置からバイナリプログラムをロードし，それを命令メモリにシリアライズする
  • CPU
    • ALU
      • 組み合わせ計算を行うので超高速（瞬時）
      • ALUにどの程度の機能を持たせるかは設計次第
      • ALUがサポートしていない機能はソフトウェアとして実装する．
      • ハードウェア実装：効率は良い．コストがかかる
      • ソフトウェア実装：効率は悪い．コストがかからない
    • レジスタ
      • CPUが計算を実行する過程で中間値を一時的に保存する必要がある
      • いちいちメモリとデータをやりとりしていると遅いので，レジスタを使う
      • スタベーション（Starvation）：高速なプロセッサが低速なメモリアクセスのために待たされる状態
      • データレジスタ
      • アドレスレジスタ
      • プログラムカウンタ：次にフェッチされ，実行される命令のアドレスを格納
      • 命令レジスタ：現在の命令を格納する
      • Hackでは3つのレジスタを使う
    • 制御ユニット（Control Unit）
      • 命令は「マイクロコード」からなる
      • 命令を実行するには，命令をマイクロコードへとデコードする必要がある
      • 命令のデコードを行うのが制御ユニット
    • フェッチと実行
      • フェッチ・実行サイクル
  • 入出力（I/O）
    • メモリマップドI/O
      • I/Oデバイスは多様で複雑．かつ，それぞれ独自の機能を持つ
      • そのようなI/Oデバイスがコンピュータにとって全く同じように見えるようにするための技術
    • I/Oデバイスは，メモリ領域を確保して，メモリマップを使って，メモリを読み書きする
    • メモリマップを実現するには規格が必要になる
      • 例：キーとバイナリコードとの対応
  • Hackハードウェアの仕様
    • CPU
      • ALU
      • Dレジスタ
      • Aレジスタ
      • プログラムカウンタ
      • 入力
        • inM[16]：現在のRAM[A]の値
        • instruction[16]：現在の命令
          • A命令なら0vvv vvvv vvvv vvvv
          • C命令なら111a cccc ccdd djjj
        • reset：1ならpcを0にリセット，0なら次にどの命令をフェッチするか決める←？
      • 出力
        • outM[16]：レジスタMに何かが格納されれば，その値が入る．
        • addressM[15]：次のRAM[A]のアドレス
        • writeM：RAM[A]に書き込むかどうか
      • outMとwriteMは組み合わせゲートで実装されるので，瞬時．
      • addressMとpcはクロックで制御される
    • 命令メモリ：ROM32K
      • 32K個の16bitレジスタを持っている
      • address[15]：次の命令のアドレス
    • I/O
      • スクリーン：SCREEN
        • RAM[SCREEN]からRAM[SCREEN+8191]までがスクリーンのビットマップ
          • 8K個の16ビットレジスタ
        • 16ビットの8KのRAMと全く同じ機能を持つ
      • キーボード：KBD
        • 読み取り専用の16ビットのレジスタと全く同じ機能を持つ
        • 出力：out[16]：押されているキーの16ビット文字コード
    • データメモリ：Memory：RAM16KとScreenとKBD
      • アドレス空間の上位16K+8K+1ワードのみが使用できる
        • 32K=2^15, 16K=2^14, 8K=2^13なので，A命令で指定できるアドレス15ビットで表現できる
      • 上位16K：RAM16K
      • 次の8K：Screen
      • 最後の1ワード：KBD
    • Computer：最上位のチップ．resetを受け取る
      • resetが1にセットした後，0にすると現在ROMにロードされてるプログラムが実行される
      • これを「コンピュータをブートする」という
        • OSのカーネルをRAMにロードし，実行する
  • 展望
    • Hackコンピュータは現代のコンピュータと質的には同じノイマン型アーキテクチャを持っている
      • 量は違う
    • 独立したアドレス空間か？単一のアドレス空間か？
      • Hackは独立したアドレス空間を持つ
        • これはHarvardアーキテクチャと呼ばれる
      • 通常は，プログラムとデータの両方を格納するために単一のアドレス空間を持つ
      • 独立したアドレス空間：
        • 構築が簡単で安価
        • 高速
        • プログラムのサイズが事前にわかっていれば，命令メモリのサイズを最適化できる
        • 組み込みシステム
      • 単一のアドレス空間：
        • 動作は2サイクル単位で行われる
          • 1サイクル目（フェッチサイクル）：命令をフェッチ
          • 2サイクル目（実行サイクル）：命令をデコードして実行
        • パソコンや携帯電話などの多くのコンピュータはこの方式
    • CISCとRISC
      • プロセッサのパフォーマンスを向上させるための二つのハードウェア設計アプローチ
      • CISC（Complex Instruction Set Computer）：多くの複雑な命令を持つ
        • 一つの命令で多くのことを行う
        • プログラムが短くなる
        • プログラムが短くなると，メモリアクセスが少なくなる
        • メモリアクセスが少なくなると，高速に動作する
        • しかし，複雑な命令を実装するためには，ハードウェアが複雑になる
      • RISC（Reduced Instruction Set Computer）：少ない命令を持つ
        • 一つの命令で少ないことを行う
        • プログラムが長くなる
        • プログラムが長くなると，メモリアクセスが多くなる
        • メモリアクセスが多くなると，遅くなる
        • しかし，シンプルな命令を実装するためには，ハードウェアがシンプルになる

実装

  • Memory
    • RAM16K
      • address=0xx xxxx xxxx xxxx
    • Screen: RAM4Kを二つ使う
      • 1つ目：address=100 xxxx xxxx xxxx
      • 2つ目：address=101 xxxx xxxx xxxx
    • KBD: Register(16bit)
      • address=110 0000 0000 0000
    • DMux8Wayでloadを分岐させる
    • Mux8Way16でoutをまとめる
    • 前パターン計算しておいて，使うものだけ選択して残すスタイルなので，無駄が多いように感じる．
      • これが最適化の範疇か
  • CPU
    • 厄介．配線が複雑
    • ALUの命令とC命令のcompの命令は完全に対応しているので，順序通りそのまま繋げばOK
    • destination
      • 「命令がC命令である」かつ，「C命令によって選ばれている」
    • jump
      • 「命令がC命令である」かつ，「条件式が満たされている」
    • PC
      • inc：true
      • reset：load=trueのときにresetする
    • pc, addressMなどは適宜ケタを合わせる
  • Computer
    • 図に従って実装するだけ．一番簡単

6章 アセンブラ

読む：約150min
実装：約480min

  • アセンブラ：記号形式のプログラムをバイナリコードに変換するプログラム
    • この章では，Hackアセンブラを開発する
  • ニーモニック（mnemonic）
    • ラテン語で「何かを覚えるのに役立つ文字のパターン」
  • Hack機械語の仕様
    • アセンブリ版HACKプログラム
      • アセンブリ命令：A命令orC命令
      • ラベル宣言：(LABEL)
      • コメント：//...
    • アセンブリで使うシンボル
      • 1．ラベル：LOOP, ENDなど，コード内の位置を示す
        • (xxx)は一度だけ定義できる
        • プログラムのどこでも使用できる．
          • そのラベルが定義される前に使われることもある．これがアセンブラ開発を難しくする
      • 2．変数：i, sumなどのシンボル変数
        • xxxというシンボルがあったとき，それが「定義済みのシンボルでなく」，「ラベル宣言(xxx)がない」なら，それは変数として扱う
        • RAMアドレスの16から始まる連続した番号にマッピングされる
      • 3．定義済みシンボル：R0, SCREENなど．
      • これらのシンボルを覚えておく”誰か”がアセンブラ
        • シンボルテーブル：シンボルとそのアドレスの対応表
      • 構文規則
        • 定数：@xxx xxxは0~2^15-1の整数が10進数表記される
        • 空白・空行：無視される
  • アセンブリからバイナリへの変換
    • 2パス・アセンブラ
      • 第1パス．シンボルの解決
        • ラベルを見つけて，それに対応するアドレスをシンボルテーブルに登録する
        • アセンブリプログラム全体を一行ずつ処理する
        • 行番号をカウントする
          • コメント，ラベル宣言，空行は無視
        • ラベル宣言(xxx)を見つけたら，それに対応するアドレスをシンボルテーブルに登録
          • ラベルxxxに対応するアドレスは，現在の行番号に1を加えた値（プログラムの次の命令のROMアドレス）
      • 第2パス．コードの生成
        • アセンブリプログラム全体をもう一度一行ずつ処理する
        • シンボル参照を持つA命令@xxxを見つけたら，シンボルテーブルでxxxに対応するラベルがないかを確認する
          • あれば，そのアドレスで置き換える
          • なければ，xxxを新しい変数として扱う
            • シンボルテーブルに<xxx value>を登録する
              • valueはRAMアドレス
            • valueを用いて@xを@valueに置き換える
  • 展望
    • 実際のアセンブラは，もっと多くの機能をサポートしている
      • 例：定数演算@i+1，マクロ命令
    • 機械語プログラムが人間によって描かれることは滅多にない．通常コンパイラがそれを生成する
      • 効率性と最適性を追求するC/C++プログラマなどは，コンパイラの生成したアセンブリを見て，最適化の余地があるかどうかを判断することがある

実装

  • 第一段階：「基本版アセンブラ」：シンボル参照を含まない
    • Add.asm, MaxL.asm, PongL.asmを変換して，差分がないことを確認
  • 第ニ段階：「完全版アセンブラ」
  • ※エラーの処理は省略

第二部ソフトウェアまえがき

読む：24min

Hackを，あなたのお気に入りのアプリケーションに変身できる「魔法のボックス」に仕立て上げるのだ．
10章，11章：コンパイラ．構文解析とコード生成
Jackコンパイラは二層式．つまり，抽象的な仮想マシン上で動作するVMコードを生成したのち，それをHackアセンブリに変換する．
7, 8章：仮想マシンの設計と実装
Jackでは，OSは標準クラスライブラリとしてパッケージ化されている
←「プログラミング言語を実現するはずのソフトウェアを，その言語自体で実装できるのか？」：ブートストラッピング（Unix OSもClangで書かれた）．
12章：OS
OSが提供するシステムサービスを全て実装する．ランタイムメモリの管理システムを実装する．OSがどのようにハードウェアやコンパイラと連携し，RAMを効率的に割り当て，再利用するかを学ぶ．
複雑な舞台裏を学ぶ理由
1.低水準のシステム内部に深入りすればするほど，より洗練された高水準プログラマになれる．ハードウェアやOSを巧みに活用できるようになり，メモリリークなどのバグも回避・対処できる．
2．システム内部を自分の手で開発することで，「最も美しく強力なアルゴリズムやデータ構造を目の当たりにできる」．これらのアイデアはOSやコンパイラに限定されない．

7章 VM I：スタック操作

読む：約80min
実装：約15h

  • WriteArithmetic：算術コマンドを処理する
    • add は push/pop で表せるが，そのためには一時的な変数が必要
      • この一時的な変数は，スタックの一番上に置かれる
      • この一時的な変数は，SPを使ってアクセスする
  • WritePushPop：メモリアクセスコマンドを処理する

CPU Emulatorでのテストの仕方

  1. 自前のVMTranslatorで.asmファイルを生成し，それをCPU Emulatorに読み込む．
  2. CPU Emulator上で7章のテストファイルBasicTest.tstを読み込む．これは，RAMの初期設定をしてくれるテストファイル．
  3. CPU Emulator上で自分のアセンブリコードを実行し，期待通りの結果が得られるか確認する．
    ただし，CPU Emulatorの不具合により，local fileの読み込みをするには毎回，ページのリロードが必要．よって，テストファイルも読み込み直さねばならない．

実装

  • VMファイルのファイルパスをそのままstaticセグメントの変数に使ってしまっていた．
  • eqなどを2回使うと，eqのラベルが被るので，ラベルをユニークにする必要がある．
    • CodeWriterにcommandCountを持たせて，それをラベルに使うことで解決．
      • 使うたびにcommandCountをインクリメントする
    • 効率性を考えると，一度登場したラベルを使いまわしたいが，ユニットテストしづらくなる，変えるべきコードの範囲が広がる，ので，ひとまずやめた
      nand 7章終わり！
  • アセンブリとほぼ同じだろう，と思ってかかっていたが，死ぬほど時間かかって大変だった．
  • 正直，綺麗なコード，良い設計，テストも書くことにこだわって，時間を浪費してしまったことも多いので，愚直に書けばもっと短縮できたかも

8章 VM II：プログラム制御

読む：約150min
実装：約?h

  • 7章の実装課題を終える前に読んだが，半分以降あたりから全くわからなくなったので，7章の実装課題を終えてから読むことをおすすめする．
    ある関数（呼び出し側）が別の関数（呼び出される側）を呼び出すときには，
  • 呼び出される側が実行を終えたら，呼び出し側に戻る必要がある
  • 呼び出される側のメモリリソースを割り当てる．
  • 引数を渡す
    呼び出される側が終了して値を返すときにも
  • 呼び出される側の戻り値を呼び出し側のコードで利用できるようにする
  • 呼び出される側が利用したメモリリソースを解放する
  • 以前に保存した呼び出し側のメモリリソースを復元する
  • returnアドレスを取り出す
  • 8.2 分岐
    • 無条件分岐：goto symbol
    • 条件分岐：if-goto symbol
      • 値をpushして，それがtrueならジャンプ
  • 8.3 関数呼び出し
    • 関数呼び出し：call func
      • 関数はローカル変数と引数変数を利用して関数実行を行う
      • フレーム：関数の状態を復元するために必要なポインタの集合
      • 作業スタック：関数が実行中に使われるスタック
      • グローバルスタック：全ての関数の作業スタックとフレームを保持する唯一のスタック
      • 関数を呼び出す直前に，呼び出し側の状態を保存する
        • 引数：呼び出し側の引数の値
        • ARG：呼び出し側のARGの値
        • LCL：呼び出し側のLCLの値
        • THIS：呼び出し側のTHISの値
        • THAT：呼び出し側のTHATの値
        • リターンアドレス：呼び出し側のコードに戻るためのアドレス
        • ローカル変数：呼び出し側のローカル変数の値
      • 関数を処理し終わったら，返り値を返す
        • returnコマンドは現在の関数を呼び出したcallコマンドの次のメモリ位置にプログラムの実行を移す
          • 呼び出し側のarg 0の位置に返り値をコピーする
    • 関数名はfileName.functionName
  • 8.6 展望
    • 中間のVM言語を使用するメリット
      • コンパイラの開発タスクを，「高水準言語→VM言語へのコンパイラの開発タスク」と，「VM言語→アセンブリ言語へのコンパイラの開発タスク」に分割できる
      • VMコードは十分簡素で可読性が高い．そのため，変換部の開発効率が高まる．
      • 中間コードを管理できる．
        • 悪意のあるプログラムの監視など
    • デメリット
      • 効率性は下がる．VM言語の生成するコードは，直接，高級言語から生成されるコードよりも効率が悪い．
      • よって， OSや組み込み用のアプリケーションでは，直接アセンブリ言語にコンパイルすることが多い．（C言語など）

実装

  • FibonacchiSeries.asmで，またラベル名の衝突が起きた．
    • 最後に無限ループで終わるために作っていたラベルENDが，FibonacchiSeries.asmのENDと被っていた
    • 自動でラベル名を生成する機構を作りたい

9章

読む：約90min
実装：約3h

実装

  • 各文の文末に；が必要
  • 関数の最後には必ずreturn文が必要
  • 変数はvar type varNameで宣言したのち，let varName = val
  • 型のキャストについてはかなりプリミティブ
  • online IDEでjackファイルは快適に編集できる．

10章 コンパイラI

読む：約90min
実装：約22h

  • 構文解析
    • トークナイズ
    • パース
      • 文法：メタ言語で書かれる．文法は再帰的である
        • 終端要素
        • 非終端要素
        • 修飾子：
          • *: 0回以上
          • |: or
          • ?: 0回or1回
          • (, ): グループ化
        • 入力テキストと文法規則が認める構文パターンとの対応関係：パース木

実装

  • 逐一テストを通していくのはマジで大切
  • stringについて，tokenに"を含めるかどうかでバグる
    • tokenとしては"付きで，compileの時にはずす
  • tokenizerがめちゃくちゃバグってたけど，直した．
    • advanceでscanを読んでおらずtextだけ読んでた．
    • 読めるだけ読む，ループをすり抜けていた
  • XMLの仕様書が曖昧
    • static int i,j;のようなクラス変数宣言ではstatic int i;static int j;と同じXMLを出力すればいいのかどうか→否．これらのXML表現は別．
  • 簡単な順序と逆順に実装していかないといけない
    • term→expression→expressionlist, statements→subroutinebody→subroutine
  • keywordのパースに穴が見つかる．boolXのような変数はboolがパースされてしまっていた．

11章 コンパイラII

読む：約?min
実装：約?h

  • Javaではintは32bitの整数を，longは64bitの整数を表す
    • もしRAMが32ビット幅ならintは1ワード，longは2ワードを占める
    • でもJackでは全てのプリミティブ型は16ビット幅の整数を表すので，全て1ワード
      • ポインタも
  • コンストラクタが何をしているか：var p = Point.new(2,3)が実行されると．．．
    • 新しいPointインスタンスを表現するため，必要な2ワード分のメモリブロックをヒープ上に確保する
    • 確保されたメモリブロックの2ワードが2,3で初期化される
    • pに新しく確保されたメモリブロックのベースアドレスを設定する
    • コンストラクタnewはサブルーチン．ただ特別な点は次の2点
      • 1．新しいオブジェクトを生成すること
      • 2．新しいオブジェクトを現在のオブジェクト（this）にすること
    • 内部的にはconstructorの処理に，OSのMemory.alloc(size)をcallすることで解決する
  • メソッド呼び出しのコンパイル：p1.distance(p2)が呼び出されると
    • p1, p2はPointクラスのインスタンス
    • VM言語はp1.distance(p2)を見ると，push p1, push p2, call distance 2とする．
    • 二つのポインタを受け取って，処理を行う関数distanceはメソッド定義の時点で作っておく
    • メソッド呼び出しの規約により，argument 0にはメソッドが呼び出されて動作するオブジェクトのベースアドレスが格納されている．
    • →メソッドのTHISポインタをargument 0の値に設定すれば，メソッドのthisセグメントはターゲットオブジェクトのベースアドレスになり，うまくいく
  • Jack では配列はOSのArrayクラスとして実装される．
    • let x = arr[i];は，*(arr+i)という番地の値を取得して，x（の指す番地）の値を書き換える．

実装

  • do文：関数の返り値をpop temp 0などで捨てる
  • void : push constant 0, returnで形式上0を返す
  1. symbol tableを作る
    • class, subroutine周りの処理はとりあえず適当で．
  2. do, 整数定数，return
    • a

✅1. Symbol Table

  • field count
  • static count
  • var count
  • kind
    • field
    • static
    • var
    • none
      • subroutine
      • class
      • 今はclass, subroutineも一応シンボルテーブルに追加する仕様にして，きちんと補足できているかをみているが，最終的には除くこと．p308 識別子の扱い参照．
      • arg ✅ 2025-04-22
  • type
    • bool
    • int
    • Array
    • String
    • 定義されたクラス
  • SymbolTableEntry構造体
  • コンパイラ
    • name=className, T=className, kind=NONEで登録しておく．ステージ1はおそらくおおよそOK
    • class, subroutine周りの処理はまだよくわかっていない
      • compileClassのたびにシンボルテーブルを
    • ProcessIdentifierメソッド内で「宣言されているのか」「使用されているのか」を判定するロジックは作った
      • シンボルテーブルに追加する前にProcessIdentifierすることで実現

✅2. Do, 整数定数，return

  • 目標：Seven テストケースを通す ✅ 2025-04-26

  • 整数定数

    • *: call Math.multiply 2 (p.309)
    • /: call Math.divide 2

  • do

    • 関数呼び出し：expressionとして処理
      • compile termでpushする．expression, expression listではpushはしない．

  • return: VM commandのreturnを書くだけ

  • void

    • returnの前にpush constant 0してreturnしないといけない
    • でもvoid関数であるかどうかの情報をどう渡すか？→subroutine シンボルテーブルに持たせることに
      • isVoidSubroutineという変数を持たせて，
        symbol tableにcurrentScopeを作る

  • class STにはclass name

  • subroutine ST にはsubroutine name
    "currentScope"→T:void/notvoid , kind:class/function/method/constructor

  • この方法だとcurrentScopeという名前の変数を書けなくなる→STに変数追加

✅3. 配列と文字列やメソッド呼び出しを含まない式，関数，if While, Do, Let return

  • 目標：ConvertToBin テストケースを通す ✅ 2025-04-26
    配列，文字列，コンストラクタ，メソッド呼び出しを含まない
  • 関数定義
    • function className.functionName nVars
    • parameter listのargument はargument
  • expression
    • ✅整数定数
    • ✅整数以外の定数：null, true/false
      • null,falseはpush constant 0
      • trueはpush constant 1, neg
    • 文字列，配列
    • ✅他の変数
  • ✅let
  • ✅if, while

4. オブジェクト指向の機能（コンストラクタ，メソッド，field，static）

  • ✅目標：Squareテストを通す ✅ 2025-04-27
  • method
    • シンボルテーブルに<this,className, arg, 0>を追加 p.310 ✅ 2025-04-27
  • field/ static変数のマッピングp.307 ✅ 2025-04-27
  • コンストラクタ ✅ 2025-04-27
  • メソッド ✅ 2025-04-27
    • 呼び出しp.309
      • Term: varName.methodName()とmethodName()（これはthis.methodName()と同じ）
        • push varName
          • 省略された場合はpush pointer 0?
        • compileExpression
        • call className.methodName nArgs+1
        • className.functionName()とうまく処理を切り分ける
  • 定数のthis p.308 ✅ 2025-04-27
    • compileTermの中でpush pointer 0
  • エラーチェックが厳しいと，テストがしづらい問題
  • バグ：メソッド呼び出しの時の引数がきちんとpushされていない
    • varName.methodName(type arg1)

5. 配列と文字列

  • 目標：Averageテストを通す ✅ 2025-04-27
  • 文字列の実装 ✅ 2025-04-27
  • 配列 ✅ 2025-04-27
    • expの返り値は普通に配列のその値になるように
      • tempとか使わない
    • let varName '[' exp1 ']' = exp2
push varName
compile(exp1)
add
compile(exp2)
pop temp 0
pop pointer 1
push temp 0
pop that 0

6. 最終チェック

  • 目標：Pongテストを通す ✅ 2025-04-27
  • 目標：ComplexArraysテストを通す ✅ 2025-04-27
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?