😺

Nand2tetrisをGoで実装する ~ アセンブラ編(6章) ~

2021/12/03に公開

Golang

assembly

nand2tetris

tech

この記事は、自作OS Advent Calendar 2021.12.03 の記事として書かれました。

1.はじめに

「コンピュータの中では何が起こっているのか？」

近年、ソフトウェア開発を取り巻く技術は急速に発展し、ほとんどの人にとって、コンピュータの内部構造はブラックボックス化しているのではないでしょうか。かくいう私もその一人。コンピュータの内部構造を知らずとも、「技術の使い方」さえ知っていれば、プロダクションレベルのアプリケーションが実装できてしまう時代です。

しかし、仮にもソフトウェアエンジニアを名乗るのであれば、基本的な構造くらいは理解しておきたいもの。そう思った私は、低レイヤーの勉強のために、書籍「コンピュータシステムの理論と実装」が提供するNand2tetrisというプロジェクトに取り組みました。以下は実装したリポジトリです。

そして、本記事は「コンピュータシステムの理論と実装」の6章に該当するアセンブラ編の実装に関する記事です。

2.コンピュータシステムの理論と実装(Nand2tetris)

本章では「コンピュータシステムの理論と実装」という書籍、またその書籍が提供するプロジェクトであるNand2tetrisについて簡単に説明していきます。

本書の目的はコンピュータシステムを実際に作り、その作業を通して、コンピュータシステムを深く理解すること。Nand2tetrisというプロジェクト名はNANDゲートを最小素子として、機械語が動作するようなハードウェアを構築し、アセンブラやコンパイラを実装し、最終的にはテトリスが動作するようなコンピュータを構築するという特徴から名付けられています。

そして、本記事・アセンブラ編では、Nand2tetrisが提供するHackアセンブリというオリジナルのアセンブリ言語を、前の記事・ハードウェア編で実装したCPU(CPU.hdl)上で動作するような機械語に変換するアセンブラをGo言語で実装します。

3.アセンブラとは？

前の記事(ハードウェア編)では、16bit機械語が動作するようなコンピュータ・CPUを作成しました。ここで、CPU上で実行することができる16bit機械語によるプログラムを見てみましょう。

0000000000000010
1110110000010000
0000000000000011
1110000010010000
0000000000000000
1110001100001000

上の機械語プログラムは「2+3の計算結果をデータメモリの0番地に格納する」という単純な処理を実行するプログラムなのですが、一目見ただけではそのことが全くわからないかと思います。(少なくとも、私にはわかりませんでした)

このように機械語というのは直感的には理解しづらく、それを直接記述して、プログラムを組んでいく、というのは人間的な作業とは言い難い上に、効率が悪いです。

そこで開発されたのがアセンブリ言語(アセンブリ)です。アセンブリは機械語に対応する命令を"Add R2,R1,R3"のような記号の組み合わせで表現します。そして、アセンブリによるプログラムを機械語に変換するソフトウェアのことをアセンブラと呼びます。

4.Hackアセンブリの文法

文法に関して、事細かに説明していく前に、前章で提示した「2+3の計算結果をデータメモリの0番地に格納する」プログラムのHackアセンブラバージョンを例としてみてみましょう。

@2  // Aレジスタに2を格納
D=A // DレジスタにA(=2) を格納
@3
D=D+A  // D レジスタにD+A(=2 + 3)の計算結果を格納
@0 
M=D // RAM[0]にdレジスタの値を格納

多くの人にとって、機械語で書かれたプログラムよりも、幾分、実行される処理の内容が読み解きやすくなっているのではないでしょうか？

Hackアセンブリでは、各行に記述された命令・ラベルである「コマンド」を最小単位として、それらを組み合わせていくことによってプログラムを構築していきます。ここで、Hackアセンブリには

Aコマンド(A命令)
Cコマンド(C命令)
Lコマンド(ラベル)

という3つの文法が存在します。

Aコマンド

Aコマンドは@{定数 or 変数名}という文法で表されるコマンドです。このコマンドを実行することによって、Aレジスタ内に任意の値を格納することができます。

さて、Aレジスタに格納された値はどんな用途に用いられるのでしょうか？大きく分けて

演算処理で用いられる定数の格納
データメモリの特定のアドレスへのアクセス
Jump命令のジャンプ先の格納

という3つが挙げられます。

たとえば、先ほど示した「2+3の計算結果をデータメモリの0番地に格納する」プログラムの中ではこのうち、1つ目(2+3を計算する際に利用)と2つ目(RAM[0]にアクセスする際に利用)の用途で用いられています。

Cコマンド

Cコマンドでは、加算や減算、条件分岐といった「演算処理」を記述するHackアセンブリの中心的コマンドです。Cコマンドの文法を一般化すると、以下のような構造をしています。

dest=comp;jump

Cコマンドを構成する要素の各役割は以下の通りです。

dest:compの代入先となるレジスタ(ex:D,M)
comp:計算式(ex:D+1)やレジスタ名
jump:jump命令であった時、その命令(ex:JGT)

先ほどのプログラムの中に登場するCコマンドD=D+AをCコマンドを構成する要素に分解してみると

dest:D
comp:D+A
jump:なし

となります。

Lコマンド

最後にLコマンドです。LコマンドはJump命令がJumpする先であるラベルの役割を果たします。

(ADD_FUNCTION) // Lコマンド
...
...
...
@ADD_FUNCTION
0;JMP // Aレジスタに格納されているアドレス(＝ADD_FUNCTIONラベルが貼られているアドレス)にジャンプ
...

以上がHackアセンブリの文法に関する説明です。それでは次章以降では、いよいよそれらを機械語に変換するアセンブラを実装していきます。

5.HackアセンブラのGoによる実装

5.1 アセンブリが機械語に変換されるまで

詳細な実装についてみていく前にまずは全体像です。今回実装したGoによるHackアセンブラが「アセンブリを機械語に変換する」プロセスを図示すると以下の通りになります。

アセンブリを機械語に変換するまでのプロセスはアセンブリ言語によるプログラムを、3種類あるコマンドのそれぞれの文法をモデル化したastノードの配列に変換する「構文解析」と 構文解析により得られたastノードの配列の各要素を機械語に変換する「機械語への変換」という2つのステップに分けられます。それでは詳細な実装を見ていきましょう。

5.2 assemblerパッケージのフォルダ構成

まずは、実装したHackアセンブラ(nand2tetris/assembler)のrootで、treeコマンドを実行し、プロジェクトの全体像を把握していきます。

$ tree -L 2
.
├── README.md
├── asm // Hackアセンブリのサンプルプログラム
│   ├── add
│   ├── max
│   ├── pong
│   └── rect
├── ast // 3種類のコマンドの文法構造をGoの構造体により定義・モデル化
│   ├── ast.go
│   └── ast_test.go
├── code // astノード(ast以下で定義された構造体のオブジェクト)を機械語に変換する
│   ├── code.go
│   └── code_test.go
├── go.mod
├── main.go // 各パッケージの関数を呼び出し、アセンブリ→機械語への変換を行う.
├── main_test.go
├── parser // Hackアセンブリのソースコードをastノードに変換する
│   ├── parser.go
│   └── parser_test.go
├── symboltable // 「LCommadのラベル名とそれに対応する機械語命令のアドレス」・「ACommandの変数名とそれに対応するRAMアドレス(>16)」といったアセンブリプログラム内の変数を管理する。
│   ├── symboltable.go
│   └── symboltable_test.go
└── value // 定数値の定義
    └── value.go

それでは、機械語に変換する上で特にポイントになるパッケージをピックアップして、次章以降で見ていきましょう。

5.3 抽象構文木(AST)ノードの定義(ast/ast.go)

astパッケージでは、Hackアセンブリに存在する3種類のコマンドの文法構造をモデル化したGoの構造体が定義されています。

4章でHackアセンブリには

Aコマンド
Cコマンド
Lコマンド

という3種類のコマンドが存在することを説明しました。この中で、たとえば、Cコマンドはその構造を一般化すると、dest=comp;jumpという構造をしており、dest,comp,jumpという3つの要素から構成されます(4章で説明ずみ)。それではここで、Cコマンドの文法構造を定義した構造体CCommandの実装を見てみましょう。

type CCommand struct {
	Comp string
	Dest string
	Jump string
}

構造体CCommandはComp,Dest,Jumpという3つのフィールドを持つ構造体です。dest=comp;jumpという構造を持つアセンブリのCコマンドを解析し、構造体CCommandのインスタンスを生成した場合、そのフィールドDest,Comp,Jumpには、それぞれdest,comp,jumpの文字列データが入ります。このようにして、他のLコマンド・Aコマンドについてもコマンドを構成する要素をフィールドとして持つような構造体をそれぞれ定義しました。

それでは、Lコマンド・Aコマンドの実装および各構造体のStringメソッドの実装を含んだ、ast/ast.go全体の実装を見てみましょう。

package ast

import (
	"assembler/value"
	"fmt"
	"strings"
)

type CommandType string

const (
	A_COMMAND CommandType = "A_COMMAND"
	C_COMMAND CommandType = "C_COMMAND"
	L_COMMAND CommandType = "L_COMMAND"
)

type Command interface {
	String() string
}

type ACommand struct {
	Value    int
	ValueStr string
}

func (aCommand *ACommand) String() string {
	return fmt.Sprintf("@%s", aCommand.ValueStr) + value.NEW_LINE
}

type CCommand struct {
	Comp string
	Dest string
	Jump string
}

func (cCommand *CCommand) String() string {
	commandStr := fmt.Sprintf("%s=%s;%s", cCommand.Dest, cCommand.Comp, cCommand.Jump) + value.NEW_LINE
	if cCommand.Jump == "" {
		commandStr = strings.Replace(commandStr, ";", "", 1)
	} else if cCommand.Dest == "" {
		commandStr = strings.Replace(commandStr, "=", "", 1)
	}
	return commandStr
}

type LCommand struct {
	Symbol string
}

func (lCommand *LCommand) String() string {
	return fmt.Sprintf("(%s)", lCommand.Symbol)
}

以上がastパッケージに関する説明です。

5.4 構文解析(parser/parser.go)

parserパッケージでは、アセンブリ言語で書かれたプログラムを5.3章で定義したastノードの配列に変換します。構文解析を行う処理の細かい実装を見ていく前に、まずはその挙動を確認していきましょう。D=D+Aというコマンドを、Hackアセンブリのコマンドの解析し、5.3章で定義したastのノードに変換するParseCommandという関数で解析してみます。

func main() {
	// st := symboltable.New() // シンボルテーブルの定義。本来は必要だが、今回は変数が登場しないのでコメントアウトする。
	p := parser.New("D=D+A", nil) // parserの初期化。解析対象となるアセンブリプログラムを渡す。
	ast, err := p.ParseCommand() // アセンブリプログラムの一行分を構文解析し、その解析結果をreturnする。
	if err != nil {
		panic(err)
	}
	fmt.Printf("%#v", ast)
}

そして、上のコードを実行すると以下のような出力が得られます。

$ go run main.go
&ast.CCommand{Comp:"D+A", Dest:"D", Jump:""}

D=D+Aは「compがD+A,destがD,jumpがなし」という構造のCコマンドなので、正しく構文解析できていることがわかります。

それでは、ParseCommandの実装を見てみましょう.

func (p *Parser) ParseCommand() (ast.Command, error) {
	p.removeWhiteSpace() // コマンド文字列から空白を削除する。Ex:'D=D+A     ' → 'D=D+A'
	switch p.CommandType() { // コマンドのタイプ(Aコマンド,Cコマンド,Lコマンド)に応じて実行する処理を区別。
	case ast.A_COMMAND:
		aCommand, err := p.parseACommand()
		if err != nil {
			return nil, err
		}
		return aCommand, nil
	case ast.C_COMMAND:
		cCommand, err := p.parseCCommand()
		if err != nil {
			return nil, err
		}
		return cCommand, nil
	case ast.L_COMMAND:
		lCommand, err := p.parseLCommand()
		if err != nil {
			return nil, err
		}
		return lCommand, nil
	default:
		return nil, fmt.Errorf("%s is invalid Command Type ", p.commandStrList[p.currentCommandIdx])
	}
}

3種類存在するコマンドそれぞれに対する構文解析用の関数は、長くなるのでここでは触れませんが、nand2tetris-golang/assembler/parser/parser.goに実装があるので、興味がある方はぜひチェックしてみてください。

5.5 機械語への変換・構文木評価(code/code.go)

5.4節では、アセンブリプログラムを解析し、astノードの配列に変換するparserパッケージに関する説明を行いました。

そして、本節で説明するcodeパッケージでは、parserパッケージの処理を通して、得られたastノードを当初の目標であった16bit機械語に変換します。

「機械語への変換」は難しそうな気もしますが、やっていることは非常にシンプルです。

ここでは例として、D=D+Aというコマンドを対象に、対応する機械語を導出します。D=D+Aは5.4節でも説明した通り、「compがD+A,destがD,jumpがなし」というCコマンドです。ここで、Cコマンドに対応する16bit機械語の構造を見てみましょう

Cコマンドである場合、先頭3bitは必ず'111'で、残りの13bitはCコマンドにおけるcomp,dest,jumpの値に応じて、一意に決定します。そして、繰り返しになりますが、D=D+Aは「compがD+A,destがD,jumpがなし」というCコマンドになるため、comp,dest,jumpのそれぞれの値に対応するbit列を組み合わせると、機械語を導出することが可能です。

compがD+Aに対応する6bitは0000010、destがDに対応する3bitは010,jumpがなしに対応する3bitは000なので、これらを組み合わせるとD=D+Aの機械語は1110000010010000となります。

Aコマンドに関してはここでは触れませんが、Cコマンドより簡単に機械語に変換することが可能です。ここで一点注意すべきなのが、Lコマンドに対応する機械語は存在しないということです。Lコマンドはjump命令の記述を容易にするために存在する、単なるラベルに過ぎず、そこでCPUを操作するような処理はされないためです。

さて、以上のことを踏まえて、astノードを機械語に変換するcode.goの実装を見てみましょう。

package code

import (
	"assembler/ast"
	"fmt"
)

// astノードを機械語(string)に変換する。
func Binary(command ast.Command) string { 
	switch c := command.(type) {
	case *ast.ACommand:
		return fmt.Sprintf("%016b", c.Value)
	case *ast.CCommand:
		cCommandBinaryPrefix := "111"
		return cCommandBinaryPrefix + Comp(c.Comp) + Dest(c.Dest) + Jump(c.Jump) // "111" + "xxxxxx"(comp) + "xxx"(dest) + "xxx"(jump)
	}
	return ""
}

func Dest(dest string) string {
	if dest == "" {
		return "000"
	}
	destBinaryMap := map[string]string{"M": "001", "D": "010", "MD": "011", "A": "100", "AM": "101", "AD": "110", "AMD": "111"} // destの値に対応した3bitのバイナリを連想配列で管理
	destBinary := destBinaryMap[dest]
	return destBinary
}

func Jump(jump string) string {
	if jump == "" {
		return "000"
	}
	jumpBinaryMap := map[string]string{"JGT": "001", "JEQ": "010", "JGE": "011", "JLT": "100", "JNE": "101", "JLE": "110", "JMP": "111"} // jumpの値に対応した3bitのバイナリを連想配列で管理
	jumpBinary := jumpBinaryMap[jump]
	return jumpBinary
}

func Comp(comp string) string {
	compBinaryMap := map[string]string{ // compの値に対応した3bitのバイナリを連想配列で管理
		// a = 0
		"0":   "0101010",
		"1":   "0111111",
		"-1":  "0111010",
		"D":   "0001100",
		"A":   "0110000",
		"!D":  "0001101",
		"!A":  "0110001",
		"-D":  "0001111",
		"-A":  "0110011",
		"D+1": "0011111",
		"A+1": "0110111",
		"D-1": "0001110",
		"A-1": "0110010",
		"D+A": "0000010",
		"D-A": "0010011",
		"A-D": "0000111",
		"D&A": "0000000",
		"D|A": "0010101",
		// a = 1
		"M":   "1110000",
		"!M":  "1110001",
		"-M":  "1110011",
		"M+1": "1110111",
		"M-1": "1110010",
		"D+M": "1000010",
		"D-M": "1010011",
		"M-D": "1000111",
		"D&M": "1000000",
		"D|M": "1010101",
	}
	return compBinaryMap[comp]
}

以上がcodeパッケージに関する説明になります。

5.6 Add.asmを機械語に変換する.

それでは、最後に先ほどから例として挙げている「2+3の計算結果をデータメモリの0番地に格納する」プログラムであるasm/add/Add.asmを今回実装したassemblerで機械語に変換してみましょう！

機械語に変換したいアセンブリプログラム(*.asm)へのPathを引数として、assembler/main.goを実行します。すると、アセンブリプログラムが存在するディレクトリと同じディレクトリに機械語ファイルが生成されます。

すなわち、asm/add/Add.asmを機械語に変換するには以下のコマンドを実行します。

$ go run main.go asm/add/Add.asm

実行すると、asm/addに、Add.hackという機械語ファイルが作成されます。それではAdd.hackの中身を見てみましょう.

0000000000000010
1110110000010000
0000000000000011
1110000010010000
0000000000000000
1110001100001000

これは、3章の「アセンブラとは？」で例として示した機械語と全く同じものです。実装したアセンブラによって、アセンブリプログラムが機械語プログラムに変換されることが確認できました。

6.最後に

本記事ではNand2tetrisのアセンブラ編(6章)の実装をGoで行い、それに関する説明を行いました。実装の詳細が気になる方はリポジトリのnand2tetris-golang/assemblerをチェックしてみてください。

本記事で実装したアセンブラによって、アセンブリ言語によって、プログラムを組むことができるようになりました。0と1の組み合わせでプログラムを構築することと比べると、大分人間的な作業に近づきましたが、それでもCPUやメモリの構造を熟知していなくてはならず、まだまだ難易度は高いです。ということで、次の記事以降ではいよいよコンパイラを実装していきます。使用言語はアセンブラと同様、Goです。興味がある方はぜひそちらもチェックしてみてください。

7.参考文献

GitHubで編集を提案