Writing A Compiler In Go を読んでいく Chapter 4 Conditionals

こんにちわ、んだです！本日も『Writing A Compiler In Go』の読書録を進めていきます。

Writing A Compiler In Go (English Edition)

作者:Ball, Thorsten

Amazon

Chapter 4では、Conditionals、条件分岐を処理していきます。
どうやって処理するんでしょうか？

楽しみですね。

IfExpression
Jumps
テストケース
let’s just put garbage in there and fix it later
let result = if (5 > 3) { 5 } else { 3 };にどう対応するか？
changeOprands
まとめ

IfExpression

まずは、MonkeyのIf文についてみていきましょう。

if (5 > 2) { 
   30 + 20
} else { 
   50 - 25
}

パーツに分解してみると、5 > 2や30 + 20は中置式なので前章でコンパイラを書いています。

問題は、それぞれの式にどう飛ばしてあげるかです。

※本書p84より

Jumps

それぞれの式にどう飛ばしてあげるか？についてですが、Jump命令を使うことによって、条件分岐を処理します。

※本書p86より

では、実際にコードで確認していきましょう。

テストケース

まずは、いつものようにテストケースから眺めていきましょう。

func TestConditionals(t *testing.T) {
    tests := []compilerTestCase{
        {
            input: `
            if (true) { 10 }; 3333;
            `,
            expectedConstants: []interface{}{10, 3333},
            expectedInstructions: []code.Instructions{
                // 0000
                code.Make(code.OpTrue),
                // 0001
                code.Make(code.OpJumpNotTruthy, 7),
                // 0004
                code.Make(code.OpConstant, 0),
                // 0007
                code.Make(code.OpPop),
                // 0012
                code.Make(code.OpConstant, 1),
                // 0015
                code.Make(code.OpPop),
            },
        },
    }

    runCompilerTests(t, tests)
}

前章までのテストケースであれば、眺めて終了でしたが、今回はテストケースをみると２つの疑問が湧きます。

① 3333ってなんだ？
② code.Make(code.OpJumpNotTruthy, 7),とあるが、どうやってジャンプ先が0007であることを知るのか？

です。

let’s just put garbage in there and fix it later

”とりあえずゴミを入れて、後で修正しよう”

code.Make(code.OpJumpNotTruthy, 7),とあるが、どうやってジャンプ先が0007であることを知るのか？に対する答えです。

コードで確認しましょう。

// compiler/compiler.go

func (c *Compiler) Compile(node ast.Node) error {
    switch node := node.(type) {

        // 中略
    case *ast.IfExpression:
        err := c.Compile(node.Condition)
        if err != nil {
            return err
        }

        jumpNotTruthyPos := c.emit(code.OpJumpNotTruthy, 9999)

        err = c.Compile(node.Consequence)
        if err != nil {
            return err
        }

”とりあえずゴミを入れて”は、この一行です。9999という数値をオフセットに一旦ぶち込んでいるわけです。

jumpNotTruthyPos := c.emit(code.OpJumpNotTruthy, 9999)

let result = if (5 > 3) { 5 } else { 3 };にどう対応するか？

さて、一旦、どうやってジャンプ先を知るのか？については処置できたということで、次に処理していくのは

let result = if (5 > 3) { 5 } else { 3 };

この式についてです。

現状では、

$ go test ./compiler
   --- FAIL: TestConditionals (0.00s)
    compiler_test.go:195: testInstructions failed: wrong instructions length.
     want="0000 OpTrue\n0001 OpJumpNotTruthy 7\n0004 OpConstant 0\n\
       0007 OpPop\n0008 OpConstant 1\n0011 OpPop\n"
     got ="0000 OpTrue\n0001 OpJumpNotTruthy 9999\n0004 OpConstant 0\n\
       0007 OpPop\n0008 OpPop\n0009 OpConstant 1\n0012 OpPop\n"
   FAIL
   FAIL    monkey/compiler 0.010s

となっており、OpPopが実行されて評価された値がresultに入れることができません。

この問題に対処するためには、compilerに新しいフィールドを加えます。

// compiler/compiler.go
type EmittedInstruction struct {
    Opcode   code.Opcode
    Position int
}

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

    lastInstruction     EmittedInstruction
    previousInstruction EmittedInstruction
}

まずは、lastInstructionとpreviousInstructionを加えてあげて、前後の命名を保持します。

で、さらに

// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
    switch node := node.(type) {
         // [....]
    case *ast.IfExpression:
                 // [....]
        err = c.Compile(node.Consequence)
        if err != nil {
            return err
        }

        if c.lastInstructionIsPop() {
            c.removeLastPop()
        }

としてあげて、Consequenceを処理した後に最後の命令がPopである場合には、removeしてあげるという感じです。

ここまで来ると、あとは9999を正しいジャンプ先に指定してあげるだけですね。

$ go test ./compiler
   --- FAIL: TestConditionals (0.00s)
    compiler_test.go:195: testInstructions failed: wrong instruction at 2.
     want="0000 OpTrue\n0001 OpJumpNotTruthy 7\n0004 OpConstant 0\n\
       0007 OpPop\n 0008 OpConstant 1\n0011 OpPop\n"
     got ="0000 OpTrue\n0001 OpJumpNotTruthy 9999\n0004 OpConstant 0\n\
       0007 OpPop\n 0008 OpConstant 1\n0011 OpPop\n"
   FAIL
   FAIL    monkey/compiler 0.008s

changeOprands

では、最後にどのようにして9999を正しいジャンプ先に指定しているか？についてみていきましょう。

// compiler/compiler.go
func (c *Compiler) Compile(node ast.Node) error {
    switch node := node.(type) {
         // [....]

    case *ast.IfExpression:
        err := c.Compile(node.Condition)
        if err != nil {
            return err
        }

        jumpNotTruthyPos := c.emit(code.OpJumpNotTruthy, 9999)

        err = c.Compile(node.Consequence)
        if err != nil {
            return err
        }

        if c.lastInstructionIsPop() {
            c.removeLastPop()
        }

        jumpPos := c.emit(code.OpJump, 9999)

        afterConsequencePos := len(c.instructions)
        c.changeOperand(jumpNotTruthyPos, afterConsequencePos)

最後の２行で処理しています。

まずは、afterConsequencePosを取得します。

afterConsequencePos := len(c.instructions)

続いて、jumpNotTruthyPosと置き換えます。

c.changeOperand(jumpNotTruthyPos, afterConsequencePos)

シンプルですね！

まとめ

Jump先を一旦ダミーでいれておいて後から置き換えるっていう実装は、泥臭いことやっとんなーという思いでした。

逆にですが、これ以外の方法でJump先を設定する方法ってあるんでしょか。ありそうですな。

ということで、以上で、Conditionalsのcompiler編は完了です。次回は、VMでどう処理していくのかについて追っかけていきたいと思います。

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

github.com

んだ日記

ndaDayoの技術日記です