はじめに

この記事はGo2 Advent Calendar 2018 23日目の記事です。

タイトルの通りWritten A Compiler In Go (以下Compiler本)を読んで、とても面白かったので、その内容を紹介したいと思います。

Writing An Interpreter In Go

Compiler本の話をする前に、まずWriting An Interpretor In Go(以下Interpreter本)の説明をする必要があります。なぜなら、Compiler本は実質Interpreter本の続編であり、そこに書かれている内容を理解していることが前提となっているためです。

interpreterbook.com

Interpreter本(Compiler本でも同様、後述)では、Monkey というjavascriptやRubyっぽい独自言語(作者はC言語風と称しています)に関して

Source Code > (Lexer & Parser) > AST > (Evaluator) > Print(REPL)

これらの流れをGoで実装し、REPLという形で、Goのランタイム上で実行できるようにしていきます。 Parserを独自に実装するなど色々興味深い点はあるのですが、今回の主題はInterpreter本ではなくCompiler本ですので深くは触れません。 Interpreter本に関しては他にも書評を書いている方がいらっしゃいますのご紹介しておきます。よろしければ併せてご覧ください。

https://deeeet.com/writing/2017/01/12/go-interpreter/deeeet.com

medium.com

razokulover.hateblo.jp

そうしてなんやかんやあって、最終的には、たとえばこんな感じのことがREPLを通して実行できるようになります。

let foo = "bar";
puts(foo);

>> bar

let myArray = [1, 2, 3, 4, 5];

let fibonacci = fn(x) {
  if (x == 0) {
    0
  } else {
    if (x == 1) {
      return 1;
    } else {
      fibonacci(x - 1) + fibonacci(x - 2);
    }
  }
};

fibonacci(myArray[4]);

>> 5

third party libraryは一切使いません。200ページちょっとの内容でここまでのものができるのって、結構すごくないでしょうか。

Writing An Compiler In Go

さて、ようやく本題です。 Compiler本において見た目上できること(REPL)は同じだったりするのですが、 Interpreter本とは当然そのアプローチ、アーキテクチャが異なります。

具体的には、ASTをそのまま即Evaluateするのではなく、 Compilerを通して Bytecodeに変換し、Virtual machine (VM) 上で実行(Execute)します。・・というのをInterpreter本と同じくGoのランタイム上で行います。

Source Code > (Lexer & Parser) > AST > (Compiler) > Bytecode > (VM) > Print(REPL)

実装に入る前に、そもそも Compiler、VM(Process Virtual MaicheCode)とはなにか？なぜVMか？なぜ独自Bytecodeを使用するか？など、きちんと説明してくれています。

例えばVMを導入することに関して、要はまあ学習コスパが一番良いってことになると思うのですが、その辺を懇切丁寧に説明してくれており、もやもやしながらとりあえず読み進める、ということはありません。

最終系がREPL上で一通り動作するまでにいくつかの技術スタックが登場しますが、 Compiler、VMに関して、それぞれをどのように実装していくかをご紹介したいと思います。

Stack Machine

本著のVMの計算モデルではスタックマシンを採用しています。レジスタマシンに比べてシンプルで学習しやすい、というのがその理由です。

まずCompilerにおいては、以下のような構造体を擬似的なIR(中間表現)として実装します (以下、コードスニペットは説明の為局所化・簡略化します。完全な内容を知りたい方は本著を御覧ください)

type Compiler struct {
    constants    []Object
    instructions []Instruction
}

constants は、JVMなどでも採用されているconstant poolです。 instructions には独自の命令コードである Instruction (Opecode: stackへのpushやpop、四則演算など 1byte + オペランド: constant poolのアドレス 0-2byte)のリストが入ります命令コードにはオペランドが存在しないものもあるため、オペランドのサイズは可変長となっています。

ざっくり言ってしまうと、この構造体がASTを処理して、constantsやinstructionsへと変換していく、という流れとなります。

func (c *Compiler) Compile(node ast.Node) error {
    switch node := node.(type) {
    case Integer:
        i := Integer{Value: node.Value}
        c.emit(OpConstant, i)
    case Add:
        c.emit(code.OpAdd)
    }

雰囲気伝わりましたでしょうか・・？続いて、VMです

type VM struct {
    constants    []Object
    instructions []Instruction
    stack        []Object
}

VMでは、Compilerが出力したBytecodeを入力としてconstantsやinstructionsを受け取り、 stackに積みつつ fetch-decode-execute cycle のloop処理を実行していきます。

func (vm *VM) Run() error {
    for ip := 0; ip < len(vm.instructions); ip++ {
        op := Opcode(vm.instructions[ip])
        switch op {
        case code.OpConstant:
            constIndex := ReadUint16(vm.instructions[ip+1:])
            vm.push(vm.constants[constIndex])
        case code.OpAdd:
            left := vm.Pop()
            right := vm.Pop()
            result := add(left, right)
            vm.push(result)
        }

大分簡略化しましたが、スタックマシンを実装する上でのCompilerとVMの動きをご紹介しました。

Conditionals

各命令をシーケンシャルに実行するスタックマシン上で、 Ifなど条件分岐(Conditionals)は、どのように実現するのでしょうか。

JUMP命令 を用いて、特定の命令を呼び飛ばすことで実現します。以下はif-elseを含むInstructionsのイメージ図です。

OpJumpNotTruthy 直前の命令の結果がFALSEなら所定の位置までの命令を読み飛ばす
OpJump 無条件で所定の位置までの命令を読み飛ばす

Keeping Track of Names

letキーワードを使っての変数束縛や、変数の値の取り出しには OpSet や OpGet 命令を使用します。さて、CompilerやVMはこれらの命令に関して、何を行うのでしょうか。

まず、Compilerにおいては symbol table を使って変数の管理を行います。

type Symbol struct {
    Name  string
    Index int
}

type SymbolTable struct {
    Store          map[string]Symbol
    NumDefinitions int
}

Symbol は自身を示す Name と SymbolTable 内の Index を保持します。 SymbolTable はSymbolを名前で引くためのmapと、Symbolの総数を保持します。

あれ、変数自体の値は？と思うかもしれません。値は式を評価した結果ですので Compile時点では決定していません。(もちろん自明なものはありますが) したがってSymbolは値を持たないのです。

こちらを前述のOpSetなどの命令で使用します。雰囲気だけですが以下のような感じです。

func (c *Compiler) Compile(node ast.Node) error {
    switch node := node.(type) {
    ・
    ・
    case LetStatement:
        symbol := c.symbolTable.Define(node.Name)
        c.emit(OpSetGlobal, symbol.Index)

    case Identifier:
        symbol := c.symbolTable.Resolve(node.Value)
        c.emit(code.OpGetGlobal, symbol.Index)
    }

続いてVMです。VMにおいては変数名にはもはや関心が無く、必要なのはその定義された順番(Index)のみです。 VMでは、Compilerで定義されたSymbol.Index(がOpSetなどのオペランドに入っている)を使って変数をリストで管理します。

type VM struct {
    ・
    ・
    variables []Object
}

評価、実行はこのような感じで行います。

func (vm *VM) Run() error {
    for ip := 0; ip < len(vm.instructions); ip++ {
        op := Opcode(vm.instructions[ip])
        switch op {
        ・
        ・
        case OpSet:
            variableIndex := ReadUint16(vm.instructions[ip+1:])
            vm.variables[variableIndex] = vm.pop()

        case OpGet:
            variableIndex := ReadUint16(vm.instructions[ip+1:])
            vm.push(vm.variables[variableIndex])
        }

なお本著では、最終的には上記に加えてスコープ(Global/local)の概念を取り入れ、スコープごとに変数を管理するようになります。その際には、もっとも内側のスコープから順に探索し、見つかった最初の値を返す、という動きになります。

let foo = 1;
let bar = 10;
let buzz = 100;

let innerOne = fn() {
    let foo = 2;
    let bar = 20;
    let innnerTwo = fn() {
        let foo = 3;
        puts(foo);
        puts(bar);
        puts(buzz);
    }
    innnerTwo();
}

innerOne();

>> 3
>> 20
>> 100

Others

FunctionやClousureをどう実装するか？ stack frame とは？などなど、他にも技術的な学びはたくさんあるのですが、疲れたので今回はこの辺にしておきたいと思います。ここから先は君自身の目で確かめてくれ！！

おわりに

文中で作者が

私が欲しかったのは、900ページにも及ぶコンパイラについての書籍と、50行のRubyコードでLisp インタプリタを実装する方法に関するブログ記事との間にあるものだ

と述べていますが、Goをある程度読み書きできて、かつ同じ想いを持っている方(私もそうでした)にはぜひ読んでみることをオススメします。

また、少し本題からは外れますが、Compiler本は2018年12月現在、英語版しかありません。しかし、日本語版が出ているInterpreter本の続編ということもあり、そちらの内容を理解していればそれほど苦もなく読み進めることができましたので、原著を読む練習としても良さそうです。

Interpreter本とCompiler本、合わせても500ページちょっとくらいですし、年末年始のお供にいかがでしょうか。以上です。

技術備忘記

日々調べたこととかとりとめなく

Written A Compiler In Go を読んだ