もっと楽して式の評価器を作る #golang

  • 14
    Like
  • 0
    Comment

はじめに

Go Advent Calendar 2016にて、「簡単な式の評価機を作ってみる」という記事を書きました。
そこでは、抽象構文木(AST)を解析し、go/constantパッケージの機能を使って式の評価器を作るという話を書きました。

この記事では、go/typesパッケージの機能を使うことで、もっと楽して式の評価を行うプログラムを作ってみたいと思います。

なお、この記事を書いた時点におけるGoの最新バージョンは1.7.4です。

定数の評価

Goのスコープについて考えてみよう」という記事でも触れましたが、go/typesパッケージには、以下のような機能が提供されています。

  • 識別子の解決(identifier resolution)
  • 型推論(type deduction)
  • 定数の評価(constant evaluation)

go/types: The Go Type Checker」にも書いてありますが、これらは、go/typesパッケージが型チェックを行う上で、切ってもきれない機能です。
このうち、定数の評価については、types.Eval関数で単体で行うことができます。
types.Eval関数は以下のようなシグニチャを持ちます。

func Eval(fset *token.FileSet, pkg *Package, pos token.Pos, expr string) (TypeAndValue, error)

第1引数は、お馴染みのtoken.FileSet構造体のポインタです。
token.NewFileSet関数によって取得することができ、go/parserパッケージのParse系の関数によってファイル情報を追加していきます。
なお、パースについては、「ASTを取得する方法を調べる」という記事で解説しています。

第2引数は、types.Pacakge構造体のポインタです。
*types.Config型のCheckメソッドを使うと、指定したファイルのASTを解析し、それらを1つのパッケージとし、スコープの情報やインポートしたパッケージの情報などを設定します。

第3引数は、ソースコード上の位置を表すtoken.Pos型の値です。
同じスコープ内でも位置によって、定義されている識別子が違う可能性があるため、位置を指定する必要があります。

第4引数はいよいよ、式を表す文字列です。
これは、定数自体がコンパイル時に評価されるため、コンパイル時に解決できるものでしか構成できません。
つまり、他の定数やリテラル、組み込み関数などしか使えません。

戻り値ですが、第1戻り値は、types.TypeAndValue型という、その名の通り型と値の情報を持つ構造体で、第2戻り値はエラーです。

さて、types.Evalを使って、式の評価を行っていきます。
引数のfsetについては、特にパースする必要もないため、token.NewFileSet関数で新しく作ったものをそのまま渡せば良さそうです。
pkgについても、今回はユニバーススコープだけで十分なのでtypes.NewPacakgeで返ってくる値をそのまま渡せば良さそうです。
また、第3引数のposについても、1つの式を評価したいだけなので、ゼロ値であるtoken.NoPosでも渡しておけば良いでしょう。
そして、第4引数はお好きな式を渡せば良いでしょう。

つまり、以下のようかコードで式の評価が行えるということです。

package main

import (
    "fmt"
    "go/token"
    "go/types"
    "log"
)

func eval(expr string) (types.TypeAndValue, error) {
    return types.Eval(token.NewFileSet(), types.NewPackage("main", "main"), token.NoPos, expr)
}

func main() {
    tv, err := eval(`(100 + 1) * len("hoge")`)
    if err != nil {
        log.Fatal(err)
    }

    fmt.Println(tv.Value)
}

あれ。。eval関数が1行になりました。
というか、types.Eval関数を呼び出しているだけになりましたね。
ちゃんと組み込み関数のlenも使えていることが分かると思います。
上記のコードは、The Go Playgroundでも動かせるので、ぜひ動かしてみて下さい。

他のパッケージの定数を参照する

これだけでは面白くないので、mathパッケージの定数を参照できるように改造してみましょう。
ここではtypes.Eval関数に渡す、*types.Pacakge型の値に対して、いくつか操作をすることでmathパッケージをインポートしたことにしましょう。

まず、なにもインポートしておらず、ユニバーススコープの識別子しかアクセスできないパッケージを作ります。

pkg := types.NewPackage("main", "main")

次に、mathパッケージをtypes.Importer型のImportメソッドを使ってインポートします。
ここでは、go/importerパッケージのimport.Default関数が返すデフォルトのtypes.Importerを使います。

mathPkg, err := importer.Default().Import("math")

つづいて、インポートしたmathパッケージをpkgのインポートリストに追加します。
ここでは、他にインポートしてないので、新しくリスト作ってを設定しています。

pkg.SetImports([]*types.Package{
    mathPkg,
})

最後にpkgのスコープに対して、mathパッケージとmathという識別子を関連付けるために、type.PkgName構造体のポインタ型の値を差し込みます。

pkg.Scope().Insert(types.NewPkgName(token.NoPos, pkg, "math", mathPkg))

なお、自前の定数を定義したい場合は、以下のように*types.Const型の値をスコープに差し込みます。

pkg.Scope().Insert(types.NewConst(token.NoPos, pkg, "hoge", types.Typ[types.Float64], constant.MakeFloat64(100)))

ここまでの処理をまとめると、以下のようなコードになります。
なお、このコードで使っているimporter.Default関数の返すインポーターがThe Go Playground上では動作しないので、注意してください。

package main

import (
    "fmt"
    "go/constant"
    "go/importer"
    "go/token"
    "go/types"
    "log"
)

func eval(expr string) (types.TypeAndValue, error) {
    pkg := types.NewPackage("main", "main")
    mathPkg, err := importer.Default().Import("math")
    if err != nil {
        return types.TypeAndValue{}, err
    }

    pkg.SetImports([]*types.Package{
        mathPkg,
    })

    pkg.Scope().Insert(types.NewPkgName(token.NoPos, pkg, "math", mathPkg))
    pkg.Scope().Insert(types.NewConst(token.NoPos, pkg, "hoge", types.Typ[types.Float64], constant.MakeFloat64(100)))

    return types.Eval(token.NewFileSet(), pkg, token.NoPos, expr)
}

func main() {
    tv, err := eval(`(hoge + 1) * math.Pi`)
    if err != nil {
        log.Fatal(err)
    }

    fmt.Println(tv.Value)
}

実行結果は以下のようになります。

実行結果
317.301

うまく外部の定数や自前の定数も評価できることが分かります。

REPLを作る

今回も、REPLも作ってみましょう。
せっかくなので、前の評価結果を次の式で使えるようにしてみます。

*type.Scope型のInsertメソッドを使って、評価結果をスコープに定数として追加してやり、次の式の評価で同じパッケージ情報を使うことで実現することができます。

コードは以下のようになります。

package main

import (
    "bufio"
    "errors"
    "fmt"
    "go/token"
    "go/types"
    "os"
)

type Evaluator struct {
    pkg         *types.Package
    fset        *token.FileSet
    outputCount int
}

func NewEvaluator() *Evaluator {
    return &Evaluator{
        pkg:  types.NewPackage("main", "main"),
        fset: token.NewFileSet(),
    }
}

func (e *Evaluator) Count() int {
    return e.outputCount
}

func (e *Evaluator) Eval(expr string) (string, error) {
    pos := e.pkg.Scope().End()
    tv, err := types.Eval(e.fset, e.pkg, pos, expr)
    if err != nil {
        return "", err
    }

    if tv.Type == nil || tv.Value == nil {
        return "", errors.New("cannot eval expr")
    }

    e.outputCount++

    outputName := fmt.Sprintf("o%d", e.outputCount)
    e.pkg.Scope().Insert(types.NewConst(pos, e.pkg, outputName, tv.Type, tv.Value))

    return tv.Value.ExactString(), nil
}

func main() {
    e := NewEvaluator()
    s := bufio.NewScanner(os.Stdin)
    for {
        fmt.Print(">")
        if !s.Scan() {
            break
        }

        expr := s.Text()
        if expr == "bye" {
            break
        }

        o, err := e.Eval(expr)
        if err != nil {
            fmt.Println("Error:", err)
        } else {
            fmt.Printf("[o%d]=%s", e.Count(), o)
            fmt.Println()
        }
    }

    if err := s.Err(); err != nil {
        fmt.Println("Error:", err)
    }
}

パッケージ情報などを保持するために、構造体を定義し、Evalメソッドとして式の評価を定義してやります。
評価結果は、o1o2のような定数として、*types.Pacakge型のScopeメソッドから取得できるスコープの末尾に挿入されていきます。

実行すると以下のようになります。
constant.Value型のExactStringメソッドから返ってくる文字列は定数を文字列で表したものですが、実数などは近似値で表されず分数で表されます。

実行結果
>1 + 1
[o1]=2
>o1 / 3
[o2]=0
>o1 / 3.0
[o3]=2/3
>o3 * (3 + 2i)
[o4]=(2 + 4/3i)
>bye

おわりに

この記事では、types.Eval関数を使うことで簡単に式の評価器を作る方法について解説しました。
以前の「簡単な式の評価機を作ってみる」を参考にして、式の評価器を組み込んだ方は申し訳ありません。
しかし、変数や関数の機能を入れる際はASTを自前で解析する方法を取らざる得ないのでご容赦下さい!