簡単な式の評価機を作ってみる #golang

## はじめに

皆さんは[goパッケージ](http://golang.org/pkg/go)を使ったことはありますか？私は、Go！Go!言いながら、恥ずかしながら、あまりまともに使ったことがありませんでした。最近は、仕事でもAST（抽象構文木）を弄り倒すことがあるので、今回は`go`パッケージに触れたいと思います。

ここでは、簡単な四則演算などを評価し、結果を返すREPLを作ってみます。一見難しそうですが、ほとんど`go`パッケージの機能を使うので、非常に簡単です。

## ASTへパースする

まずは入力された文字列をパースし、ASTを生成してみます。ここでは、式の評価なので式単位でパースします。パースには、[`parser.ParseExpr`](https://golang.org/pkg/go/parser/#ParseExpr)を用います。
たとえば、以下のように使用できます。

```go
expr, err := parser.ParseExpr("1+1")
if err != nil {
	panic(err)
}

ast.Inspect(expr, func(n ast.Node) bool {
	if n != nil {
		fmt.Printf("%[1]v(%[1]T)\n", n)
	}
	return true
})
```
[Playgroundで動かす](https://play.golang.org/p/OctVDGyvbX)

なお、[`ast.Inspect`](https://golang.org/pkg/go/ast/#Inspect)はASTのノードをトラバースする関数です。この場合、`1+1`をパースすると、以下のようなASTが取得できます。

```
*ast.BinaryExpr (+)
├── *ast.BasicLit (1)
└── *ast.BasicLit (1)
```

このASTを評価することで、式の評価を実現します。さて、具体的に評価とはどうすれば良いのでしょうか？

## `1+1`の評価

上記の例でみたとおり、2項演算を行う式は、[`ast.BinaryExpr`](https://golang.org/pkg/go/ast/#BinaryExpr)で表されます。まずは2項演算式である`1+1`を評価してみましょう。

```go
func eval1pls1(expr *ast.BinaryExpr) (int64, error) {
	xLit, ok := expr.X.(*ast.BasicLit)
	if !ok {
		return 0, errors.New("left operand is not BasicLit")
	}

	yLit, ok := expr.Y.(*ast.BasicLit)
	if !ok {
		return 0, errors.New("right operand is not BasicLit")
	}

	if expr.Op != token.ADD {
		return 0, errors.New("operator is not +")
	}

	x, err := strconv.ParseInt(xLit.Value, 10, 64)
	if err != nil {
		return 0, err
	}

	y, err := strconv.ParseInt(yLit.Value, 10, 64)
	if err != nil {
		return 0, err
	}

	return x + y, nil
}

func main() {
	expr, err := parser.ParseExpr("1+1")
	if err != nil {
		panic(err)
	}

	if be, ok := expr.(*ast.BinaryExpr); ok {
		if v, err := eval1pls1(be); err == nil {
			fmt.Println(v)
		} else {
			fmt.Println("Error:", err)
		}
	}

}
```
[Playgroundで動かす](https://play.golang.org/p/5SOdiy420p)

`parser.Parse`が返す[`ast.Expr`](https://golang.org/pkg/go/ast/#Expr)は式であることを表すインタフェースであるため、具体的に「何の」式なのかという値は型アサーション（まはた型スイッチ）しないと手にはいりません。そのため、今回必要な`ast.BinaryExpr`とその右辺と左辺に設定されている`ast.BasicLit`を取得するために、各々型アサーションを行っています。

[`ast.BasicLit`](https://golang.org/pkg/go/ast/#BasicLit)は基本型のリテラルを表す型で、`1`や`"hoge"`などはこの型で表されます。
一方で、`true`と`false`については、識別子であるため`ast.BasicLit`ではなく、[`ast.Ident`](https://golang.org/pkg/go/ast/#Ident)として[表される](https://play.golang.org/p/o_VGns3vqV)ので注意してください。ちなみに、`true`と`false`は識別子として[使用できます](https://play.golang.org/p/Myk9AhC6xt)。
`BasicLit.Value`はそのリテラルを文字列で表したもので、 `42, 0x7f, 3.14, 1e-9, 2.4i, 'a', "foo"` などです。なお、文字列には`"`などで括られているという点に注意してください。これらを除去するには、[`strconv.Unquote`](https://golang.org/pkg/strconv/#Unquote)が使えます。

## 2項演算式とリテラルの評価

さて、`1+1`は評価できるようになったものの、ここで作りたいのは2項演算式の評価です。そのため、もう少し汎用化が必要そうです。オペランドが数値であるという点とオペレータが`+`であるという点をどうにか汎用化しないといけません。

そこで、2項演算子を簡単に評価するために、`go/constant`パッケージにある[`BinaryOp`](https://golang.org/pkg/go/constant/#BinaryOp)関数を使いましょう。

`BinaryOp`関数は以下のようなシグニチャを持っています。

```go
func BinaryOp(x Value, op token.Token, y Value) Value
```

`op`は`token.ADD`などの演算子のトークンを表すもので、これは`ast.BinaryExpr`の`Op`フィールドから取得できそうです。`x`と`y`に関しては、`Value`フィールドから[`constant.MakeFromLiteral`](https://golang.org/pkg/go/constant/#MakeFromLiteral)を使って取得できます。

`constant.MakeFromLiteral`は以下のような定義になっています。

```go
func MakeFromLiteral(lit string, tok token.Token, zero uint) Value
```

第1引数は`ast.BasicLit`の`Value`フィールドを第2引数を`ast.BasicLit`の`Kind`フィールドを渡せば良さそうです。なお、第3引数は常に`0`を渡す必要があるようです。

まとめると、上記のコードは以下のように変更することができます。

```go
func evalBinaryExpr(expr *ast.BinaryExpr) (constant.Value, error) {

	xLit, ok := expr.X.(*ast.BasicLit)
	if !ok {
		return constant.MakeUnknown(), errors.New("left operand is not BasicLit")
	}

	yLit, ok := expr.Y.(*ast.BasicLit)
	if !ok {
		return constant.MakeUnknown(), errors.New("right operand is not BasicLit")
	}

	x := evalBasicLit(xLit)
	y := evalBasicLit(yLit)
	return constant.BinaryOp(x, expr.Op, y), nil
}

func evalBasicLit(expr *ast.BasicLit) constant.Value {
	return constant.MakeFromLiteral(expr.Value, expr.Kind, 0)
}

func main() {
	expr, err := parser.ParseExpr("1+1")
	if err != nil {
		panic(err)
	}

	if be, ok := expr.(*ast.BinaryExpr); ok {
		if v, err := evalBinaryExpr(be); err == nil {
			fmt.Println(v)
		} else {
			fmt.Println("Error:", err)
		}
	}

}
```
[Playgroundで動かす](https://play.golang.org/p/Q5JdvN6E2u)

なお、2項演算式を評価する関数を`evalBinaryExpr`とし、リテラルの評価をする関数を`evalBasicLit`としました。`1-1`が実行できるか[チェック](https://play.golang.org/p/UhDwf-2N9Q)してみましょう。また、`"hoge"+"hoge"`なども[ちゃんと動く](https://play.golang.org/p/s6zukIknz0)ことが分かると思います。

`constant.MakeUnknown`関数は、エラー時に使われる値を作る関数です。演算が失敗した場合にこの値になるため、ここではエラーが発生した際に返しています。なお、戻り値を`constant.Value`にしている点が重要で、後述の`eval`関数を作る際に効果が出ます。

## 式の評価

2項演算式を評価する関数を作りました。しかし、本当にやりたいのは式の評価です。式には`-1`などの単項演算式もありますし、`1`などのリテラル、`(1+1)*2`などの括弧付きの式もあります。もちろん、Goの文法には関数呼び出しとかもありますが、ここでは四則演算などができれば十分でしょう。

どういう種類の式なのかは、`ast.Expr`を具体的な型に変換することで取得することができ、その種類によって処理を分けてやれば良さそうです。

上記の2項演算式だけをやる関数を少しだけ汎用化してみましょう。
まずは式（`ast.Expr`）を評価する関数を作りましょう。

```go
func evalExpr(expr ast.Expr) (v constant.Value, rerr error) {
	defer func() {
		if r := recover(); r != nil {
			v, rerr = constant.MakeUnknown(), fmt.Errorf("%v", r)
		}
	}()

	switch e := expr.(type) {
	case *ast.BinaryExpr:
		return evalBinaryExpr(e)
	case *ast.BasicLit:
		return constant.MakeFromLiteral(e.Value, e.Kind, 0), nil
	}

	return constant.MakeUnknown(), errors.New("unkown node")
}
```

`evalExpr`関数では、`ast.Expr`を受取り、型によって処理を分岐しています。
ここでは、2項演算式とリテラルだけ処理ができるようになっています。

`defer`で`recover`しているのは、`constant`パッケージの`BinaryOp`などが型が合わなかった場合などに、エラーを返さず、`panic`を起こすためです。

せっかくなので、`evalBinaryExpr`関数で呼び出していた`evalBasicLit`も`evalExpr`におまかせしましょう。

```go
func evalBinaryExpr(expr *ast.BinaryExpr) (constant.Value, error) {
	x, err := evalExpr(expr.X)
	if err != nil {
		return constant.MakeUnknown(), err
	}

	y, err := evalExpr(expr.Y)
	if err != nil {
		return constant.MakeUnknown(), err
	}

	return constant.BinaryOp(x, expr.Op, y), nil
}
```

これでだいぶスッキリしてきました。あとは`evalExpr`に処理できる型をどんどん追加していけば良さそうです。必要そうなものを追加していくと、`evalExpr`は以下のようになりました。

```go
func evalExpr(expr ast.Expr) (v constant.Value, rerr error) {
	defer func() {
		if r := recover(); r != nil {
			v, rerr = constant.MakeUnknown(), fmt.Errorf("%v", r)
		}
	}()

	switch e := expr.(type) {
	case *ast.ParenExpr:
		return evalExpr(e.X)
	case *ast.BinaryExpr:
		return evalBinaryExpr(e)
	case *ast.UnaryExpr:
		return evalUnaryExpr(e)
	case *ast.BasicLit:
		return constant.MakeFromLiteral(e.Value, e.Kind, 0), nil
	case *ast.Ident:
		return evalIdent(e)
	}

	return constant.MakeUnknown(), errors.New("unkown node")
}
```

[`ast.ParenExpr`](https://golang.org/pkg/go/ast/#ParenExpr)は、`()`で括られた式で、単純に中の式(`ParenExpr.X`)を評価してやれば良いでしょう。

[`ast.UnaryExpr`](https://golang.org/pkg/go/ast/#UnaryExpr)は、単項演算子式を表す型で、`ast.BinaryExpr`と同様に`evalUnaryExpr`関数を作り、処理してやります。

```go
func evalUnaryExpr(expr *ast.UnaryExpr) (constant.Value, error) {
	x, err := evalExpr(expr.X)
	if err != nil {
		return constant.MakeUnknown(), err
	}

	return constant.UnaryOp(expr.Op, x, 0), nil
}
```

四則演算には関係ないですが、せっかくなので`true`や`false`も扱えるようにしましょう。`true`や`false`が来た場合に、`ast.Ident`として処理する必要があるため、`evalIdent`を作ります。

```go
func evalIdent(expr *ast.Ident) (constant.Value, error) {
	switch {
	case expr.Name == "true":
		return constant.MakeBool(true), nil
	case expr.Name == "false":
		return constant.MakeBool(false), nil
	}

	return constant.MakeUnknown(), errors.New("unkown ident")
}
```

`true`や`false`は名前が`true`と`false`の識別子として認識されるため、上記のように処理してやれば十分です。

さて、これで完成で良さそうですが、`true`と`false`を扱えるようにしたことで一つ問題があります。`constant.BinaryOp`では`&&`や`>=`などの関係演算子は扱えません。代わりに`constant.Compare`を使ってやる必要があります。そのため、`evalBinaryExpr`関数は以下のように修正する必要があります。

```go
func evalBinaryExpr(expr *ast.BinaryExpr) (constant.Value, error) {
	x, err := evalExpr(expr.X)
	if err != nil {
		return constant.MakeUnknown(), err
	}

	y, err := evalExpr(expr.Y)
	if err != nil {
		return constant.MakeUnknown(), err
	}

	switch expr.Op {
	case token.EQL, token.NEQ, token.LSS, token.LEQ, token.GTR, token.GEQ:
		return constant.MakeBool(constant.Compare(x, expr.Op, y)), nil
	}

	return constant.BinaryOp(x, expr.Op, y), nil
}
```

これで、式を評価できる`evalExpr`ができました。最後にこれをラップして`eval`関数を作り扱いやすくしましょう。

```go
func eval(e string) (string, error) {
	expr, err := parser.ParseExpr(e)
	if err != nil {
		return "", err
	}

	v, err := evalExpr(expr)
	if err != nil {
		return "", err
	}

	return v.String(), nil
}
```

## REPLを作る

式を評価する関数を作れたので、次はREPLを作ります。ここで作るREPLは式の入力を受付け、式が入力されたらそれを評価して表示するというものにします。

標準入力(`os.Stdin`)から`bufio.Scanner`を使って1行ずつ読み取るコードを書きましょう。ここでは`bye`と入力すればREPLを抜けれるようにします。

```go
func repl(r io.Reader) {
	s := bufio.NewScanner(r)
	for {
		fmt.Print(">")
		if !s.Scan() {
			break
		}

		l := s.Text()
		switch {
		case l == "bye":
			return
		default:
			r, err := eval(l)
			if err != nil {
				fmt.Println("Error:", err)
				continue
			}
			fmt.Println(r)
		}
	}

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

うまくできましたね。ここまで作ったコードをまとめて載せておきます。

```go
package main

import (
	"bufio"
	"errors"
	"fmt"
	"go/ast"
	"go/constant"
	"go/parser"
	"go/token"
	"io"
	"os"
)

func eval(e string) (string, error) {
	expr, err := parser.ParseExpr(e)
	if err != nil {
		return "", err
	}

	v, err := evalExpr(expr)
	if err != nil {
		return "", err
	}

	return v.String(), nil
}

func evalExpr(expr ast.Expr) (v constant.Value, rerr error) {
	defer func() {
		if r := recover(); r != nil {
			v, rerr = constant.MakeUnknown(), fmt.Errorf("%v", r)
		}
	}()

	switch e := expr.(type) {
	case *ast.ParenExpr:
		return evalExpr(e.X)
	case *ast.BinaryExpr:
		return evalBinaryExpr(e)
	case *ast.UnaryExpr:
		return evalUnaryExpr(e)
	case *ast.BasicLit:
		return constant.MakeFromLiteral(e.Value, e.Kind, 0), nil
	case *ast.Ident:
		return evalIdent(e)
	}

	return constant.MakeUnknown(), errors.New("unkown node")
}

func evalBinaryExpr(expr *ast.BinaryExpr) (constant.Value, error) {
	x, err := evalExpr(expr.X)
	if err != nil {
		return constant.MakeUnknown(), err
	}

	y, err := evalExpr(expr.Y)
	if err != nil {
		return constant.MakeUnknown(), err
	}

	switch expr.Op {
	case token.EQL, token.NEQ, token.LSS, token.LEQ, token.GTR, token.GEQ:
		return constant.MakeBool(constant.Compare(x, expr.Op, y)), nil
	}

	return constant.BinaryOp(x, expr.Op, y), nil
}

func evalUnaryExpr(expr *ast.UnaryExpr) (constant.Value, error) {
	x, err := evalExpr(expr.X)
	if err != nil {
		return constant.MakeUnknown(), err
	}

	return constant.UnaryOp(expr.Op, x, 0), nil
}

func evalIdent(expr *ast.Ident) (constant.Value, error) {
	switch {
	case expr.Name == "true":
		return constant.MakeBool(true), nil
	case expr.Name == "false":
		return constant.MakeBool(false), nil
	}

	return constant.MakeUnknown(), errors.New("unkown ident")
}

func repl(r io.Reader) {
	s := bufio.NewScanner(r)
	for {
		fmt.Print(">")
		if !s.Scan() {
			break
		}

		l := s.Text()
		switch {
		case l == "bye":
			return
		default:
			r, err := eval(l)
			if err != nil {
				fmt.Println("Error:", err)
				continue
			}
			fmt.Println(r)
		}
	}

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

func main() {
	repl(os.Stdin)
}
```

## まとめ

120行で足らずで結構高性能な式の評価を行うREPLができました。
ちなみに、Goでは複素数が使えるので、今回作ったREPLは複素数も扱えます。

`eval.Expr`に変数(`ast.Ident`）や関数（`ast.CallExpr`）を評価する処理を追加してやれば、もっと高性能なものが作れます。
それにしても、`go`パッケージを使うと案外簡単に作れますね。すばらしいですね。

さて、これが実際の業務で使えるんだろうかと思ってる方もいるかもしれませんが、それは使いようだと思いますので、ぜひ用途を考えてみて下さい。