Writing A Compiler In Go を読んでいく Chapter 5 Keeping Track of Names

こんにちは！んだです。

今回も『Writing A Compiler In Go』について、読書録を書いていきます。

Writing A Compiler In Go (English Edition)

5章では、

let x = 5 * 5;
if (x > 10) { 
　let y = x * 2; 
　y;
}

let文を扱っていきます。

興奮してきましたね。

どうやるのか？

こんな式があったとします。

let x = 33; 
let y = 66; 
let z = x + y;

xに33を代入し、yに66を代入。さらに、xとyが呼び出された時に、正しくそのValueが呼び出される必要があります。

どのようにして実現するのでしょう？

アイディアとしてはシンプルです。 SetしてGetです！ 本書p.112より

では、実装をのぞいていきましょう。

TestCase

いつものようにテストケースから見ていきましょう。

func TestGlobalLetStatements(t *testing.T) { 
          tests := []compilerTestCase{
                {
                   input: `
                   let one = 1;
                   let two = 2;
                   `,
                 expectedConstants: []interface{}{1, 2}, 
                 expectedInstructions: []code.Instructions{
                    code.Make(code.OpConstant, 0),
                    code.Make(code.OpSetGlobal, 0),
                    code.Make(code.OpConstant, 1),
                    code.Make(code.OpSetGlobal, 1),
                 }, 
            },

先程の図と同様ですね。

let文の変数の値をSetしています。このテストケースにはありませんが、変数を呼び出す場合には、OpGetGlobalが呼ばれます。

では、この値はどこで管理されるのでしょうか？？

SymbolTable

SymbolTableで管理されます。 では、SymbolTableの実装を確認しましょう。

// compiler/symbol_table.go
type SymbolScope string

const (
    GlobalScope SymbolScope = "GLOBAL"
)

type Symbol struct {
    Name  string
    Scope SymbolScope
    Index int
}

type SymbolTable struct {
    store          map[string]Symbol
    numDefinitions int
}

SymbolTableには、Symbolがmapで格納されます。Symbolには、Name, Scope, Indexがフィールドとしてありますね。

どのように使うのでしょうか？

DefineとResolve

SymbolTableは、DefineとResolveを行うことで機能します。 挙動については、テストを見るとわかりやすいです。

Define

// compiler/symbol_table_test.go
func TestDefine(t *testing.T) {
    expected := map[string]Symbol{
        "a": {Name: "a", Scope: GlobalScope, Index: 0},
        "b": {Name: "b", Scope: GlobalScope, Index: 1},
    }

    global := NewSymbolTable()

    a := global.Define("a")
    if a != expected["a"] {
        t.Errorf("expected a=%+v, got=%+v", expected["a"], a)
    }

    b := global.Define("b")
    if b != expected["b"] {
        t.Errorf("expected b=%+v, got=%+v", expected["b"], a)
    }
}

変数名はNameに、そしてSymbolに変数を格納するたびにIndexをインクリメントしていきます。

// compiler/symbol_table.go
func (s *SymbolTable) Define(name string) Symbol {
    symbol := Symbol{Name: name, Index: s.numDefinitions, Scope: GlobalScope}
    s.store[name] = symbol
    s.numDefinitions++
    return symbol
}

Resolve

さて、DefineされたSymbolをどのようにResolveするのでしょうか？

ここは、nameを与えてあげて、取り出すだけです。

func (s *SymbolTable) Resolve(name string) (Symbol, bool) {
    obj, ok := s.store[name]
    return obj, ok
}

Compile LetStatements

Compilerについては、switchにast.Identifier、ast.LetStatement:を加えるだけなので、特に書くことはないので省略します。

VM

では、最後にVMを眺めていきましょう。

// vm/vm.go
const GlobalsSize = 65536

type VM struct {
    constants    []object.Object
    instructions code.Instructions

    stack   []object.Object
    sp      int
    globals []object.Object
}

func New(bytecode *compiler.Bytecode) *VM {
    return &VM{
        instructions: bytecode.Instructions,
        constants:    bytecode.Constants,

        stack:   make([]object.Object, StackSize),
        sp:      0,
        globals: make([]object.Object, GlobalsSize),
    }
}

VMに新たに、globalsを追加することで変数に代入された値を管理していきます。

OpSetGlobal, OpGetGlobal

VMの実装です。

func (vm *VM) Run() error {
                 // [....]
        case code.OpSetGlobal:
             globalIndex := code.ReadUnit16(vm.instructions[ip+1:])
             ip += 2

             vm.globals[globalIndex] = vm.pop()
        case code.OpGetGlobal:
            globalIndex := code.ReadUnit16(vm.instructions[ip+1:])
            ip += 2

            err := vm.push(vm.globals[globalIndex])
            if err != nil {
                return err
            }

OpSetGlobalの場合は、直前にOpConstant命令をemitしているのでpopして、globalsに値を格納します。

OpGetGlobalの場合は、その値をStackにpushするという実装です。

シンプルですね。

まとめ

LetstatementsについてcompilerもVMも完了です。 さて、次の6章では、String, Array, Hashをやっていきます。

楽しみですね

僕から以上。あったくして寝ろよ。