Goでインタプリタ実装本を読んで3 evaluator

Evaluationまで読み、実際にインタプリタとして実行出来るようになった。

evaluator

ソースコードをlexerによって字句解析し、parserによってASTを構築した後、evaluatorによって演算を行う。 この章を読む前は、とても面倒くさい実装をしなければいけないのではないか・・みたいな不安があり、最後まで読み進められるか不安だったけど、意外と簡単に実装出来て驚いた。

本書では、tree-working interpreter と呼ばれる、ASTをコンパイルして実行するのではなく、順に辿りながら計算結果を得る手法が解説されている。これは恐らく他のどのアプローチより演算が遅くなるけれど、ホストマシンのOSの違いを考慮しなくてよいし、ポータブルで実装が簡単。とのこと。

オブジェクトを定義する

evaluatorで重要なのは、言語が内部でどのようなオブジェクト(型)を持っているかを定義すること。本書では “internal object” と呼んでいたけど、例えば本書のMonkey言語だと、この時点では以下の型以外は無い。

const (
    INTEGER_OBJ      = "INTEGER"
    BOOLEAN_OBJ      = "BOOLEAN"
    NULL_OBJ         = "NULL"
    RETURN_VALUE_OBJ = "RETURN_VALUE"
    ERROR_OBJ        = "ERROR"
    FUNCTION_OBJ     = "FUNCTION"
)

本書のevaluatorは、ASTを順に読んでいき上記のオブジェクトに変換して演算をするというもの。実際の実装は、AST nodeのタイプを以下のようにswitch caseで読み取り、 Eval() という実行関数を再帰的に呼び出してASTを解決するという感じ。

(以下の例は、読んでもわかるというものでは無いけれど、雰囲気が伝わると嬉しい。)

func Eval(node ast.Node, env *object.Environment) object.Object {
    switch node := node.(type) {

    // Statements
    case *ast.Program:
        return evalProgram(node, env)

    case *ast.ExpressionStatement:
        return Eval(node.Expression, env)

    case *ast.PrefixExpression:
        right := Eval(node.Right, env)
        if isError(right) {
            return right
        }
        return evalPrefixExpression(node.Operator, right)

    case *ast.InfixExpression:
        left := Eval(node.Left, env)
        if isError(left) {
            return left
        }
        right := Eval(node.Right, env)
        if isError(right) {
            return right
        }
        return evalInfixExpression(node.Operator, left, right)

    case *ast.BlockStatement:
        return evalBlockStatement(node, env)

    case *ast.IfExpression:
        return evalIfExpression(node, env)

    case *ast.LetStatement:
        val := Eval(node.Value, env)
        if isError(val) {
            return val
        }
        env.Set(node.Name.Value, val)

    case *ast.Identifier:
        return evalIdentifier(node, env)

    case *ast.ReturnStatement:
        val := Eval(node.ReturnValue, env)
        if isError(val) {
            return val
        }
        return &object.ReturnValue{Value: val}

    // Expressions
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}

    case *ast.Boolean:
        return nativeBoolToBooleanObject(node.Value)

    case *ast.FunctionLiteral:
        params := node.Parameters
        body := node.Body
        return &object.Function{Parameters: params, Body: body, Env: env}

    case *ast.CallExpression:
        function := Eval(node.Function, env)
        if isError(function) {
            return function
        }
        args := evalExpressions(node.Arguments, env)
        if len(args) == 1 && isError(args[0]) {
            return args[0]
        }
        return applyFunction(function, args)
    }

    return nil
}

Eval() の第二引数である env は、変数をバインドしておくためのmap。関数スコープごとに作られ、親スコープのenvも保持している。 こうすることで、クロージャが表現出来るという寸法。

GCの話

本書のMonkey言語は、GCを実装しないので以下のようなケースに問題になる。

let counter = fn(x) { 
    if (x > 100) { 
        return true; 
    } else { 
        let foobar = 9999; 
        counter(x + 1); 
    }
};

counter(0);

counter() の引数 x が 101 になるまで再帰的に counter() を呼び出している。注目すべきは、 let foobar = 9999; の部分で、これは未使用ではあるがintをアロケートしている(Monkey言語は全ての型が内部的にはオブジェクトであり、都度instanciateしている)。要するにMonkey言語のruntime(evaluator)はGCも無ければfreeも無いのでメモリがリークする。ただ、今回はGoでevaluatorを書いているので、GoのGCがそのまま使える。ホスト言語がGCを持っている場合はGCを実装しなくても実質的にはこの辺りを解決してくれる。本書では、本来であればGoのGCを使わずに何か別の方法を実装すべきであるという警告がしてある。これは言うは易く行うは難し。本書の範疇を超えてしまう。とも。僕はGCについても知見が無い状態なので、こういった話も興味深い内容だった。

感想

本書の主なトピックはこれで読み切ったことになる(lexer, parser, evaluator)。 まだ続きはあって、文字列、配列やハッシュなどの型を追加したり、組み込み関数の実装をしたりする模様。まだ読んでいないけど、これらも基本的には lexer を実装し、それをparseしてASTを構築、実行という流れになるはずなので、なんとなくイメージは湧いている。

理解が間違っているかもしれないけど、例えばここでASTをLLVM IRやJVMで扱える形式に変換するコンパイラを書けば、SwiftあるいはKotlinみたいな感じになるのかな?と思った。LLVMにはGoバインディングパッケージがあるっぽいのでこれを使うとGoで書けるのかもしれない。以下が参考になる。

LLVM IRにコンパイルすることで、Monkey言語で課題になっていた

などの恩恵を受けられそうだなという感じで、LLVMに少し興味が沸いてきた。 この辺のことは一切何も知らなかったので、こういった想像が出来るようになったのは良かった。

ただ他にもやりたいことがたくさんあるのでいつ触るかは未定、、