nand2tetris in R

@igjit

• Webアプリケーションエンジニア
• Rで変なものを作る 人

質問

プログラムが動く仕組みを説明できますか？

あなたの書いたコードは単なる文字に過ぎない

a = 40 + 2

どういう仕組みで解釈され、計算されるのか

a = 40 + 2

https://www.oreilly.co.jp/books/9784873117126/

「コンピュータを理解するための最善の方法はゼロからコンピュータを作ることです。」

コンピュータシステムの理論と実装

通称 nand2tetris (Nand to Tetris)

コンピュータの構成要素

• ハードウェア
• ソフトウェア
• コンパイラ
• OS

をひとつずつ実装していく

NANDゲートから始まって

最終的にゲームが動くようになるよ

本に登場する階層のうち

これらをRで実装

順に紹介します。

1. アセンブラ

アセンブラ

アセンブリ言語をバイナリに変換する

アセンブリ言語を

@2
D=A
@3
D=D+A
@0
M=D

バイナリに変換

0000000000000010
1110110000010000
0000000000000011
1110000010010000
0000000000000000
1110001100001000

ハードウェアに対する命令なので低水準

@2
D=A
@3
D=D+A
@0
M=D

Rによるアセンブラの実装

assembler

2. バーチャルマシン

Virtual Machine (VM)

抽象化されたコンピュータ

この本で作るのはVM変換器 (VM translator)

VMコードをアセンブリコードに変換する

2 + 3 を計算するVMコード

push constant 2
push constant 3
add

スタックマシン (stack machine)

という計算モデル

RによるVM変換器の実装

vmtranslator

3. コンパイラ

Jack言語のコード

class Main {
   function void main() {
      do Output.printString("Hello world!");
      do Output.println();
      return;
   }
}

コンパイルの流れ

• 字句解析
• 構文解析
• コード生成

字句解析

トークンに分割する

a = 40 + 2 をトークンに分割

> jackanalyzer::tokenize("a = 40 + 2")
[[1]]
$identifier
[1] "a"

attr(,"class")
[1] "identifier_token" "token"           

[[2]]
$symbol
[1] "="

attr(,"class")
[1] "symbol_token" "token"       

[[3]]
$int_val
[1] 40

attr(,"class")
[1] "int_const_token" "token"          

[[4]]
$symbol
[1] "+"

attr(,"class")
[1] "symbol_token" "token"       

[[5]]
$int_val
[1] 2

attr(,"class")
[1] "int_const_token" "token"          

構文解析

文法にそって解釈する

a = 40 + 2 の構文木

コード生成

ターゲット言語のコードを生成する

(時間がないので詳細は略)

RによるJackコンパイラの実装

jackanalyzer

コンパイル結果のVMコードは、公式サイトで公開されているVMエミュレータで実行できる

demo

実装にかかった行数

強力な抽象は実装が大変

実装のこつ

テストを書こう

楽をするためにテストを書く

パッケージを作ろう

パッケージにすればコードを楽に再利用できる

namespaceを分離できる

assembler::parse()
vmtranslator::parse()
jackanalyzer::parse()

Rパッケージ開発入門を読もう。

原著の第2版がwebで読めるよ。

まとめ

アセンブラ、VM、コンパイラをRで実装した。

自分で作ることで

その仕組みを深く理解できる。

作る

プログラミングは楽しい！

Enjoy!