Putting Eval In Go

16 Nov 2016

Over the past year I’ve spent a significant amount of time reading through Go’s go packages, the packages used by the Go compiler and other Go tools. But only recently did it occur to me that these are real, public packages. I can actually import and use them! So then I started to wonder what I could do with them when it suddenly struck me: “I can… I can put Eval in Go! Using Go!”

Let me explain. There’s the scanner package, which contains the lexer (or scanner, or tokenizer, …) that turns Go source code into tokens. These tokens are defined in their own package, token. And then there’s the parser, which takes the tokens and builds an AST. The definitions of the AST nodes can be found in the perfectly named AST package. And then there’s also a printer package to print these AST nodes.

In other words: we have all the necessary pieces here to build an Eval function that evaluates Go code. In fact, with these packages we could build a complete Go interpreter in Go. If you’re really interested in doing that, check out the go-interpreter project, which aims to do just that. Instead, let’s start small and write an Eval function that evaluates mathematical Go expressions.

The first thing we need is a driver, a REPL:

package main

import (
	"bufio"
	"fmt"
	"os"
)

const PROMPT = "go>> "

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	for {
		fmt.Printf(PROMPT)
		scanned := scanner.Scan()
		if !scanned {
			return
		}

		line := scanner.Text()
		fmt.Println(line)
	}
}

This allows us to input Go expressions and have them printed back to us:

% go run eval.go
go>> 1 * 2 * 3 * 4
1 * 2 * 3 * 4
go>> 8 / 2 + 3 - 1
8 / 2 + 3 - 1
go>>

So far, so dull.

The next step would be to initialize Go’s scanner with these input lines and turn them into tokens. Luckily, the parser package has a ParseExpr function that does exactly that. It initializes the scanner and reads in the tokens for us. It then parses the tokens and builds an AST. We can use it to parse the input in our REPL:

package main

import (
	"bufio"
	"fmt"
	"go/parser"
	"os"
)

const PROMPT = "go>> "

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	for {
		fmt.Printf(PROMPT)
		scanned := scanner.Scan()
		if !scanned {
			return
		}

		line := scanner.Text()
		exp, err := parser.ParseExpr(line)
		if err != nil {
			fmt.Printf("parsing failed: %s\n", err)
			return
		}
	}
}

The result of our call to ParseExpr, exp, is an AST that represents the entered Go expression, without such details as comments, whitespace or semicolons. We can use the printer package to print it. We just have to use token.NewFileSet() to make the printer believe that we got our Go source code from a file:

import (
	"bufio"
	"fmt"
	"go/parser"
	"go/printer"
	"go/token"
	"os"
)

func main() {
// [...]

	for {
// [...]

		exp, err := parser.ParseExpr(line)
		if err != nil {
			fmt.Printf("parsing failed: %s\n", err)
			return
		}

		printer.Fprint(os.Stdout, token.NewFileSet(), exp)
		fmt.Printf("\n")
	}
}

Now would you look at that:

% go run eval.go
go>> 1 * 2 * 3 * 4
1 * 2 * 3 * 4
go>> 5 * 6 * 7 * 8
5 * 6 * 7 * 8

Okay, yes, you’re right. That looks exactly like our “printing back the input” mechanism we had before. But there’s more to it. What we’re actually doing here is parsing the input and pretty-printing the AST produced by the parser. See for yourself:

% go run eval.go
go>> 1           * 2           *       3 * (((5 + 6)))
1 * 2 * 3 * (5 + 6)
go>>

The whitespace has been removed, just like the superfluous parentheses around the last sub-expression. We’ve built our own crude version of gofmt in around 35 lines of Go code:

% go run eval.go
go>> func (name   string) { return name }
func(name string) {
        return name
}
go>>

But we want more than just pretty-printing the AST. We want an Eval function that evaluates mathematical Go expressions. What Eval has to do is to traverse each node in the AST and evaluate it. Granted, this definition is kinda recursive, but that’s perfect, because Eval itself is a recursive function:

import (
	"bufio"
	"fmt"
	"go/ast"
	"go/parser"
	"go/token"
	"os"
	"strconv"
)

func Eval(exp ast.Expr) int {
	switch exp := exp.(type) {
	case *ast.BinaryExpr:
		return EvalBinaryExpr(exp)
	case *ast.BasicLit:
		switch exp.Kind {
		case token.INT:
			i, _ := strconv.Atoi(exp.Value)
			return i
		}
	}

	return 0
}

func EvalBinaryExpr(exp *ast.BinaryExpr) int {
	left := Eval(exp.X)
	right := Eval(exp.Y)

	switch exp.Op {
	case token.ADD:
		return left + right
	case token.SUB:
		return left - right
	case token.MUL:
		return left * right
	case token.QUO:
		return left / right
	}

	return 0
}

As you can see, Eval takes an ast.Expr as argument, which is what we get back from parser.ParseExpr. It then traverses this part of the AST but only stops at *ast.BinaryExpr and *ast.BasicLit nodes. The former is an AST node that represents binary expressions (expressions with one operator and two operands) and the latter represents literals, like the integer literals we used in our REPL.

What Eval has to do in the case of an integer literal is easy. Integer literals evaluate to themselves. If I type 5 into the REPL then 5 is what should come out. Eval only needs to convert the parsed integer literal to a Go int and return it.

The case of *ast.BinaryExpr is more complex. Here Eval has to call itself two times to evaluate the operands of the binary expression. Each operand can be another binary expression or an integer literal. And in order to evaluate the current expression, both operands need to be fully evaluated. Only then, depending on the operator of the expression, is the correct evaluating result returned.

All that’s left for us now is to use Eval in our REPL:

func main() {
// [...]

	for {
// [...]

		exp, err := parser.ParseExpr(line)
		if err != nil {
			fmt.Printf("parsing failed: %s\n", err)
			return
		}

		fmt.Printf("%d\n", Eval(exp))
	}
}

Now our REPL can do this:

% go run eval.go
go>> 1 + 2 * 3 + 4 * 5
27
go>> 1000 - 500 - 250 - 125 - 75 - 25
25

We’ve successfully put a working Eval function in Go! And it only took us around 70 lines of code, because we used Go’s internal compiler tools.