😺

Nand2tetrisをGoで実装する ~ 中間言語・VM(コンパイラ・バックエンド)編 ~

2021/12/07に公開

assembly

nand2tetris

tech

1.はじめに

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

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

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

そして、本記事は「コンピュータシステムの理論と実装」の7,8章に該当する中間言語・Virtual Machine編の実装に関する記事です。

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

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

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

そして、ここからは、Nand2tetrisが提供するJackというプログラミング言語をアセンブリに変換するコンパイラの実装に取り組みます。

本記事ではその最初のステップとして、中間言語(Intermediate Language,IL)により記述されたプログラムをアセンブリによるプログラムに変換するVirtual Machineの実装に取り組みます。

3.プログラミング言語・Jack

既に述べた通り、本記事から2つの記事にわたって、高級言語によるプログラムを前の記事で説明したHackアセンブリによるプログラムに変換するコンパイラをGoで実装していきます。

その実装について解説していく前に、コンパイルをする対象である「Jack」というプログラミング言語を簡単に説明していきます。

「Jackがどんな言語なのか？」を直感的に把握してもらうために、Jackで記述されたプログラムを見ていきましょう。以下は「長さlengthを持つ配列aの各要素に標準入力から値を入力していき、その平均値を出力する」という処理を行うJackプログラムです.

class Main {
   function void main() {
     var Array a; 
     var int length;
     var int i, sum;

     let length = Keyboard.readInt("How many numbers? ");
     let a = Array.new(length); 
     
     let i = 0;
     while (i < length) {
        let a[i] = Keyboard.readInt("Enter a number: ");
        let sum = sum + a[i];
        let i = i + 1;
     }
     
     do Output.printString("The average is ");
     do Output.printInt(sum / length);
     return;
   }
}

普段私たちが慣れ親しんでいるプログラミング言語とほとんど同じように見えませんか？文法の解説に関しては、次の記事に譲りますが、今回そのコンパイラを実装していく「Jack」というプログラミング言語には以下のような特徴があります。

オブジェクト指向型言語
静的型付け
コンパイル時、直接実行可能な機械語・アセンブリには変換されず、独自のVirtual Machine上で動作する中間コードに変換される。(like Java,Scala,Kotlin & JVM)

4.Jackによるプログラムが機械語に変換されるまで.

前章で今回コンパイルする「Jack」というプログラミング言語について簡単に紹介しました。しかし、Jackという「高級言語」で記述されたプログラムをハードウェア上で直接動作させることは、当然できません。

高級言語により記述されたプログラムをハードウェア上で実行するためには、プログラムを実行させたいハードウェア・プラットホーム上で動作するような機械語に最終的には変換する必要があります。

それでは、ここで「Jackによるプログラム」が「Nand2tetrisが提供するハードウェア上で動作する16bit機械語」に変換されるまでの全体像を改めて見てみましょう.

Jack言語によるプログラムは「中間言語」「アセンブリ」という二つの形態を経て、最終的に16bit機械語に変換されます。そして本記事で解説するのは中間言語をHackプラットホーム上で動作するようなアセンブリに変換するVirtual MachineのGo言語による実装です。

5.中間言語に変換することのメリット

さて、Jack言語は高級言語から直接アセンブリには変換されず、一旦中間言語に変換されるわけですが、そのことにはどんなメリットがあるでしょうか？「コンピュータシステムの理論と実装」の中では以下のように説明されています。

そのうちの一つは「コードの移植性」についてである。
バーチャルマシンを複数プラットフォームを対象に実装することは比較的容易であろうから、本となるソースコードを修正することなく、バーチャルマシンようのソフトウェアを他のプロセッサとOS上でも実行することができる。

つまり、「中間言語」という層を一つ用意することで、各プラットフォーム(OSやハードウェア)ごとのVirtual Machineの実装を行えば、どんなプラットフォームであっても、Jackプログラムを実行することができるようになるということです。そのため原則、各プラットフォーム用のコンパイラの実装や各プラットフォームに対応したプログラムの構築は不要であるということです。

従って、今回は中間言語をHackプラットフォーム用のVirtual Machineの実装を行いましたが、理論上はWindowsやLinux,Mac用のVirtual Machineを実装すれば、それらのプラットフォームでも同様にJackによるプログラムを動作させることが可能です。

6.中間言語の文法

ここでは、簡単に中間言語の文法について説明していきます。今回実装するVirtual Machineはスタックベースの処理を基本としています。以下に示すのは「7+8の計算結果をlocalセグメントの0番地に格納する」という処理を中間言語で記述したものです。

push constant 7
push constant 8
add // 7 + 8 をスタック上で計算
pop local 0 // popし、localセグメントの0番地にに格納

全てのコマンドについて、ここでは紹介しませんが、条件分岐や関数の定義など、高級言語によるプログラムに近い処理を実行することが可能です。それでは次章以降でVirtual Machineの実装を見ていきましょう。

7.GoによるVirtual Machine(VM変換器)の実装

7.1 中間言語がアセンブリに変換されるまで

それでは、ここからは中間言語をアセンブリに変換するVMの実装をみていきましょう。以下の図は、今回実装したGoによるvmtranslatorパッケージが中間言語をアセンブリに変換するまでの全体像を示したものです。

見ていただくとわかる通り、今回実装したvmtranslatorが中間言語をアセンブリに変換するまでの大まかな流れは、前の記事で実装したassemblyとほとんど同じです。

中間言語によるプログラムを、astノードの配列に変換する構文解析と構文解析により得られたastノードの配列の各要素をアセンブリに変換するアセンブリへの変換という2つのステップに分けられます。それでは詳細な実装を見ていきましょう。

7.2 vmtranslatorパッケージのフォルダ構成

まずは、実装したVirtual Machine(nand2tetris-golang/vmtranslator)のrootで、treeコマンドを実行し、プロジェクトの全体像を把握していきます。

$ tree -L 2
.
├── README.md
├── ast // 中間言語・VMにおけるコマンドの構造をモデル化したastノードを定義
│   ├── ast.go
│   └── ast_test.go
├── codewriter // astノード(ast以下で定義された構造体のオブジェクト)をアセンブリに変換する
│   ├── codewriter.go
│   └── codewriter_test.go
├── go.mod
├── main.go // 各パッケージの関数を呼び出し、中間言語→アセンブリへの変換を行う.
├── main_test.go
├── parser // 中間言語によるプログラムをastノードに変換する
│   ├── parser.go
│   └── parser_test.go
├── value // 定数値の定義
│   └── value.go
└── vm // 中間言語により記述されたVMサンプルコード
    ├── Add
    ├── BasicLoop
    ├── FibonacciElement
    ├── FibonacciSeries
    ├── HelloWorld
    ├── NestedCall
    ├── SimpleFunction
    └── StaticsTest

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

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

astパッケージでは、中間言語がスタックマシンを操作や関数の呼び出しといった処理を行うためのコマンドの文法構造をモデル化したGoの構造体が定義されています。
それでは、その実装の一部を見てみましょう。

ast.go

package ast

import "fmt"

type CommandType string

type CommandSymbol string

type VMCommand interface {
	String() string
}

type ArithmeticCommand struct {
	Command CommandType   // C_ARITHMETIC
	Symbol  CommandSymbol // "add","lt"...
}

func (arithmeticCommand *ArithmeticCommand) String() string {
	return string(arithmeticCommand.Symbol)
}

type SegmentType string

const (
	ARGUMENT SegmentType = "argument"
	LOCAL    SegmentType = "local"
	STATIC   SegmentType = "static"
	CONSTANT SegmentType = "constant"
	THIS     SegmentType = "this"
	THAT     SegmentType = "that"
	POINTER  SegmentType = "pointer"
	TEMP     SegmentType = "temp"
)

type MemoryAccessCommand interface {
	VMCommand
}

type PushCommand struct {
	Comamnd CommandType // C_PUSH
	Symbol  CommandSymbol
	Segment SegmentType
	Index   int
}

func (pushCommand *PushCommand) String() string {
	return fmt.Sprintf("%s %s %d", pushCommand.Symbol, pushCommand.Segment, pushCommand.Index)
}

type PopCommand struct {
	Comamnd CommandType // C_POP
	Symbol  CommandSymbol
	Segment SegmentType
	Index   int
}

func (popCommand *PopCommand) String() string {
	return fmt.Sprintf("%s %s %d", popCommand.Symbol, popCommand.Segment, popCommand.Index)
}


// ...他のコマンドについてもastを定義

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

parserパッケージでは、中間言語によるVMプログラムを解析し、7.3節で紹介したastパッケージで定義されているastノードに変換します。ここでは例として、ParsePushというpushコマンドを解析する関数を見てみましょう。

parser.go

func (p *Parser) ParsePush() (*ast.PushCommand, error) { // pushコマンド(push {segment} {idx})を解析する
	arg1, err := p.Arg1() // pushコマンドのセグメントを取得する.
	if err != nil {
		return nil, err
	}
	arg2, err := p.Arg2() // pushコマンドのセグメント内でのidxを取得する.
	if err != nil {
		return nil, err
	}
	command := &ast.PushCommand{Comamnd: ast.C_PUSH, Symbol: ast.PUSH, Segment: ast.SegmentType(arg1), Index: arg2}
	return command, nil
}

全ての実装については、ここでは触れませんが、nand2tetris/vmtranslator/parser/parser.goに実装があるので、興味がある方はぜひチェックしてみてください.

7.5 アセンブリへの変換・構文木評価(codewriter/codewriter.go)

そして、最後に7.4で説明にあったparserパッケージで生成したastノードを、codewriterパッケージでアセンブリに変換します。pushコマンド・popコマンドのastノードを引数として受け取り、アセンブリに変換するWritePushPopの実装を見てみましょう.

codewriter.go

func (codeWriter *CodeWriter) WritePushPop(command ast.MemoryAccessCommand) error {
	var assembly string
	switch c := command.(type) {
	case *ast.PushCommand:
		pushAssembly, err := codeWriter.getPushAssembly(c) // pushコマンドに対するアセンブリを生成する関数
		if err != nil {
			return err
		}
		assembly = pushAssembly
	case *ast.PopCommand:
		popAssembly, err := codeWriter.getPopAssembly(c) // popコマンドに対するアセンブリを生成する関数
		if err != nil {
			return err
		}
		assembly = popAssembly
	}
	codeWriter.writeAssembly(assembly)
	return nil
}

8.最後に

本記事ではコンパイラ実装の第一ステップとして、Nand2tetrisの中間言語・VM編(7,8章)の実装をGoで行い、それに関する説明を行いました。実装の詳細が気になる方はリポジトリのnand2tetris-golang/vmtranslatorをチェックしてみてください。

さて、次章ではいよいよ、高級言語Jackに対して処理を行い、Jackで構築したプログラムを中間言語に変換します。長かったNand2tetrisの旅もあと少しです。興味がある方はぜひそちらも読んでみてください

9.参考文献

GitHubで編集を提案