Nand2Tetrisを受講した

The Elements of Computing Systems, second edition: Building a Modern Computer from First Principles

Courseraで2つのNand2Tetrisコースを受講した。

このコースはNoam NisanとShimon Schockenが講師を務め、Gatewayチップの実装から(Nand)、アセンブラ、Compiler、OSを作成し、最終的には自作の言語であるJackを用いてTetrisのようなアプリケーションを作る内容となっている。これらのコースは400以上の大学、高校、ブートキャンプ等で教育に使用されているとのこと。

使用したレポジトリはこちらで。他人が読んでも得をしないノートも一応ここに置いている。 また、このコースを進める上で、The Elements of Computing Systems, second edition: Building a Modern Computer from First Principlesという書籍も合わせて参考にした。

感想

What I hear, I forget; What I see, I remember; What I do; I understand.　- Confucius (551-479 b.c)

序文に挙げられた引用にもあるように、本コースは実際に手を動かして学ぶことを重視した構成となっている。また、テストやエミュレータが完備されているため、開発をスムーズに進めることが可能。各章を進めることでインクリメンタルに開発することができ、コンスタントに達成感を得られるのも良い。基本的には最適化については扱わないので、それにより複雑性を排除してシンプルに概念理解に専念できる。 普段の仕事では、抽象化によって下のレイヤーを意識することは少ないけれど、普段扱わないレイヤーを手を動かして触ることでソフトウェア開発の深みというものを改めて認識することができた。
全体を通して、とても満足度が高いコースだったので、多くの人におすすめしたい。下記に取り組んだ内容を簡単に書き出してみている。

Part1 Hardware

Chapter 1 Boolean Logic

与えられたNandチップを使ってプリミティブなAndやOr、もしくはそれらを組み合わせてMuxなどを実装するなど。Verilogに似た、シンプルな独自HDL(Hardware Description Language)を使う。

Chapter 2 Boolean Arithmetic

チャプター1で作ったチップをもとにシンプルなALU(Arithmetic Logic Unit)を作成。

Chapter 3 Memory

与えられたDFF(Data Flip-Flop)を使って、1bit registerを作り、それを元に16bit register->RAMを作っていく。

Chapter 4 Machine Language

Hackアセンブリ言語仕様の理解。

Chapter 5 Computure Architecture

CPU, Memory, Computerを構築する。

Chapter 6 Assembler

Hackアセンブリ(Symbolic machine language)をバイナリ表現に置き換えるHackアセンブラを作る。

Part2 Hardware

Chapter 7 Virtual Machine I: Processing

このチャプターではCompilerのバックエンドを実装。(Jack Compilerは2Tier Compilcation) Stack MachineをベースにしたVMが読むVMコマンドをHackアセンブリに置き換えるtranslatorを作る。

Chapter 8 Virtual Machine II: Control

VM translatorを作るつづき。 if, gotoなどControl flowの実装。

Chapter 9 High-Level Language

Jack言語を使ってサンプルアプリを作ってみる。 自分は、キープレスに応じてブロックが移動するシンプルなアプリケーションを作った。

Chapter 10 Compiler I: Syntax Analysis

Compilerフロントエンド(Jack言語をVMコードに変換する)を作成。 このチャプターではTokenizerとParserを実装する。 エラーハンドリングなどはないので、シンプルに実装可能。

Chapter 11 Compiler II: Code Generation

Compilerフロントエンドを完成させる。 Chapter10で作ったParserを元に実装する。SymbolTableを使って、変数を取り扱ったり、各Statement, Expressionをよしなにコンパイルする。

Chapter 12 Operation System

OSの実装。ほとんどが標準API(Math, Stringなど)の実装だけれど、Efficiencyについても取り上げる。 Multiply(x,y)はxをy回addするのではなく、bitwise operatorで実装することで、O(n)のコストで実装できるなど。(n = bit width of y)

Chapter 13 More Fun to Go

ラップアップ、Hackマシーンの拡張アイデアなど。

今後

今回Assembler、VM Translator, CompilerなどはC++で書いてみたが、雰囲気+ChatGPTで書いたので、次はProgramming: Principles and Practice Using C++などを読んでC++に慣れたいと思う。 コースの最後に、Jack Computerを実際のハードウェアに乗せて動かすコースをPart3として用意したいとShimon教授が言及していたので、Part3にも期待したい。