Putting Eval In Go
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.