nand2tetris (コンピュータシステムの理論と実装) を最後までやりました
nand2tetris という nand 回路からテトリス (アプリケーション) までを実際に手を動かしながら作成する教材があります。論理回路から CPU、アセンブラ、VM、コンパイラ、OS (部分的) まで、いわゆる「低レイヤー」と呼ばれる領域を概観できるものです。
- Home | nand2tetris
- Build a Modern Computer from First Principles: From Nand to Tetris (Project-Centered Course) | Coursera
オライリーから日本語訳も出ており自分はこれをやりました。
コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方 | Noam Nisan, Shimon Schocken, 斎藤 康毅 |本 | 通販 | Amazon
成果物のリポジトリはこちらです。
楽しかった
とにかく楽しかったです。
- 手を動かせる
- 解説は少なめで、手を動かして理解することにこだわりが感じられる構成になっていました
- 読むだけだと魅力が半減するというか、それならそれぞれの分野の、例えばコンパイラだったらコンパイラの、教科書を読んだほうがよいので、この本は手を動かしてこそだと思います
- そのためのお膳立てが素晴らしい
- 演習の設計がよく練られていて、スムーズに進めることができました
- 問題の分割
- 例えばコンパイラの実装について、VM を導入すること、字句解析、構文解析、コード生成とステップを踏んで進めるようになっているので、一度にあつかう複雑性が一定以下におさえられていた
- ハードウェア、言語などの設計の工夫
- 総じて「ユーザーには不親切だが処理系実装者にはやさしい」設計に倒してある
- 実用上必要な最適化が思いきって省かれているので、概念の理解に集中できる
- テストケース、エミュレーター
- コーナーケースもちゃんと突いてくれるテストケースや、動作確認用のエミュレーターが準備されているので、実装に集中できる
- 普通のプロジェクトだとこうした部分に大変な労力がかかるので、そこを準備しておいてもらえてスムーズだった
- 高速道路に乗っている感覚が得られた
- 結果として、問題がハードすぎて足が遠のいてしまうといったことは起こらず、コンスタントにすすめることができた
あいだをつなぐ教材
前述のように、理論の解説はさらっとしているので、それぞれの分野を深めるにはそれぞれの教科書などで各自対応する必要があります。
この本はそれぞれのトピックの間をつないでいるところに勝ちがあると思いました。多層に重なる各レイヤーの概念を、実際に手を動かしながらよく理解できます。
可処分時間の少ない中堅Webエンジニアにはおすすめ
自分がそうなのですが、可処分時間が減ってきていて、かつ手なりだとあれなので領域を広げたい Web エンジニアにはよいテーマだったと思います。
- この本の特徴
- 細切れの時間でも進められる
- 細かく達成感が得られる
- 人気教材だけあって学習効率が高まるようよく設計されている
- 時間の投資対効果が高い
- 有名なのでリソースがある
- 公式のフォーラム があったり
- jack 言語の VS Code シンタックスハイライト もあったりした
- 細切れの時間でも進められる
- なので、例えばこういう人におすすめ
- 技術の幅を広げるために低レイヤーにも興味がでてきた
- マネジメントの役割が増えてきてコードを書く時間が減ってきた
- 育児などライフスタイルの変化によって可処分時間が減ってきた
- 自分の場合
- 早朝や子供の寝かしつけのあとなどにこつこつやった
- コミットログ によると二ヶ月弱かかった
- 平均すると1時間/日くらいだったと思います
各章のメモ
ハードウェア、コンピュータ、機械語 (1-5 章)
- ハードウェアは hdl という言語でシミュレータ上で実装する
- nand 回路だけから論理回路を作っていく
- nand 回路は所与のものとして与えられ、どう実装されているかは扱われない
- 最終的に ALU ができる
- こいつの設計が CPU の提供する命令の設計に深く関わっていた
- 単純なビット演算は普通のプログラミングでも登場するので良かったが、マルチプレクサ・デマルチプレクサを使ったフロー制御は普通の手続き型言語と考え方がことなり難儀した
- 順序回路 (フリップフロップ回路) で状態保持
- 実はフリップフロップ回路も所与のものとして与えられている
- なので厳密には nand & フリップフロップ to テトリスか
- 論理回路はまだイメージがついたが、フリップフロップ回路は現実にはどのようなものなのかわからず、イメージしづらかった
- 最終的に RAM ができる
- 実はフリップフロップ回路も所与のものとして与えられている
- 機械語
- レジスタは 2 つしかなく、命令も ALU が対応している限定的なもののみ
- 現実の機械語を知らないのでイメージだが、かなり限定的な機能しか持たない設計になっていると思われる
- レジスタが 2 つというところで実装の感覚を掴むのに難儀した
- レジスタは 2 つしかなく、命令も ALU が対応している限定的なもののみ
- コンピュータ
- プログラム内蔵方式、入出力部分は所与という設計なので、実装は簡便化されていた
- レジスタ
- プログラムカウンタ
- フロー制御 (goto) を実現する
- アドレスレジスタ
- メモリ位置を指定する
- ポインタっぽい感覚になる
- データレジスタ
- プログラムカウンタ
- 当たり前だが、高水準言語で書けばなんともないものを、hdl で書くことは頭の体操だった
アセンブラ (6 章)
- アセンブリを読み込み、機械語を出力する
- シンボルテーブル
- 変数、ラベルをプログラム位置に変換するためにテーブルを作る
- 2 パス (二度コードを読む) の実装方針
- コンピュータのレジスタ数の少なさや命令の少なさは不便だったが、そのおかげでアセンブラは簡潔に書くことができた
VM (7-8 章)
- 高水準の言語をアセンブリに置き換える作業
- 今回は VM とコンパイラに分かれている
- VM コードと言う中間表現を VM はアセンブラに置き換える
- JVM でいうバイトコード
- コンパイラは高水準言語を読んで VM コードを出力する
- VM コードと言う中間表現を VM はアセンブラに置き換える
- スタックマシン
- スタック一つで算術演算と関数呼び出しをエレガントに解決できるのは爽快
- 関数呼び出し
- 現在の状態をスタック上に保存し、その関数へジャンプ
- 呼び出された関数は新たな環境内で動作する
- return でもとの関数の環境を再現する
- ローカル変数はスタック / malloc はヒープのような話とか、スタックオーバーフローの実感が得られてよかった
- メモリセグメント
- 複数の VM コードファイルは最終的にひとつの機械語ファイルに変換される
- 機械語のラベルをどうつけるかによって static 変数などのスコープを調整している
- VM を導入することで、一息にコンパライラを書く複雑性を分割していて、教材として良い設計だなと思った
コンパイラ (9-11 章)
- 9 章はとばした
- jack 言語に精通しても実りが少なそうなので
- ただこのあとにコンパイラを書くにあたってその対象言語に慣れていたほうが楽だったので、もしかしたらやったほうが早かったかも
- コンパイラは 2 ステップで作る
- 構文解析器を作って構文木を生成する
- 構文木を読み込んで VM コードを生成する
- 構文解析器
- 字句解析をしてから構文木を構築する
- 文脈自由文法で構文を定義
- 再帰的
- そのまま実装しやすい
- 再帰下降構文解析
- LL(1) 文法
- 最初のトークンだけから種類を特定でき、コンパイラの実装が楽 (利用者は面倒になるが)
- 種類を特定できない場合、先読みが必要になり複雑化する
- コード生成
- シンボルテーブル
- 変数名等をメモリ位置に置き換えるため
- 構文解析時に作成できるように設計されていた (二度読まなくて良い)
- 逆ポーランド記法
- スタックマシンを実感
- この時点では
main関数が呼ばれる仕組みや、ヒープをallocする仕組みなどは、所与のものを使う- 次章でここを扱う
- シンボルテーブル
- 最終的に Pong というゲームが動いた
- テトリスではなかった…
- 振り返るとこの 10, 11 章に一番時間がかかった
OS (12 章)
- OSとは言っても標準ライブラリプラスアルファ程度
- プロセス管理とかシェルとか etc はまったくない
- それぞれの典型的な実装方針や CS 的なトピックの紹介
- あわせてコンパイラの追加テストケースにもなっている
- 最初はスキップしようかと思った
- jack 言語で書くことのつらさ
- 自分でコンパイラを書いたゆえ、コンパイルエラー時にどこが悪いのかわかりづらい
- ビルドツールなどが揃っていないので、書いて検証のサイクルが面倒 (GUI を操作しないといけない)
- 学べることが少なそう
- jack 言語で書くことのつらさ
- 最終的にはやってよかった
- プログラミング言語周辺のトピックについて補完的に学べるように設計されていた
- プログラムの初期化とエントリポイント呼び出しの仕組み、ヒープのメモリ確保、O 記法、配列や文字列の内部実装、画像処理の計算量の多さの実感、などなど
- ナイーブだが大まかにどういう考え方で設計されているかイメージが付く