7.9 Example: Expression Evaluator
In this section, we’ll build an evaluator for simple arithmetic
expressions.
We’ll use an interface, Expr, to represent any expression in
this language.
For now, this interface needs no methods, but we’ll add some later.
// An Expr is an arithmetic expression.
type Expr interface{}
Our expression language consists of floating-point literals;
the binary operators +, -, *, and /;
the unary operators -x and +x;
function calls pow(x,y), sin(x), and sqrt(x);
variables such as x and pi;
and of course parentheses and standard operator precedence.
All values are of type float64.
Here are some example expressions:
sqrt(A / pi) pow(x, 3) + pow(y, 3) (F - 32) * 5 / 9
The five concrete types below represent particular kinds of expression.
A Var represents a reference to a variable.
(We’ll soon see why it is exported.)
A literal represents a floating-point constant.
The unary and binary types represent operator
expressions with one or two operands, which can be any kind of
Expr.
A call represents a function call;
we’ll restrict its fn field to pow, sin, or
sqrt.
// A Var identifies a variable, e.g., x.
type Var string
// A literal is a numeric constant, e.g., 3.141.
type literal float64
// A unary represents a unary operator expression, e.g., -x.
type unary struct {
op rune // one of '+', '-'
x Expr
}
// A binary represents a binary operator expression, e.g., x+y.
type binary struct {
op rune // one of '+', '-', '*', '/'
x, y Expr
}
// A call represents a function call expression, e.g., sin(x).
type call struct {
fn string // one of "pow", "sin", "sqrt"
args []Expr
}
To evaluate an expression containing variables, we’ll need an environment that maps variable names to values:
type Env map[Var]float64
We’ll also need each kind of expression to define an Eval
method that returns the expression’s value in a given environment.
Since every expression must provide this method, we add it to the
Expr interface.
The package exports only the types Expr, Env, and
Var; clients can use the evaluator without access to the other
expression types.
type Expr interface {
// Eval returns the value of this Expr in the environment env.
Eval(env Env) float64
}
The concrete Eval methods are shown below.
The method for Var performs an environment lookup, which
returns zero if the variable is not defined, and
the method for literal simply returns the literal value.
func (v Var) Eval(env Env) float64 {
return env[v]
}
func (l literal) Eval(_ Env) float64 {
return float64(l)
}
The Eval methods for unary and binary recursively
evaluate their operands, then apply the operation op to them.
We don’t consider divisions by zero or infinity to be errors, since
they produce a result, albeit non-finite.
Finally, the method for call evaluates the arguments to the
pow, sin, or sqrt function, then calls the
corresponding function in the math package.
func (u unary) Eval(env Env) float64 {
switch u.op {
case '+':
return +u.x.Eval(env)
case '-':
return -u.x.Eval(env)
}
panic(fmt.Sprintf("unsupported unary operator: %q", u.op))
}
func (b binary) Eval(env Env) float64 {
switch b.op {
case '+':
return b.x.Eval(env) + b.y.Eval(env)
case '-':
return b.x.Eval(env) - b.y.Eval(env)
case '*':
return b.x.Eval(env) * b.y.Eval(env)
case '/':
return b.x.Eval(env) / b.y.Eval(env)
}
panic(fmt.Sprintf("unsupported binary operator: %q", b.op))
}
func (c call) Eval(env Env) float64 {
switch c.fn {
case "pow":
return math.Pow(c.args[0].Eval(env), c.args[1].Eval(env))
case "sin":
return math.Sin(c.args[0].Eval(env))
case "sqrt":
return math.Sqrt(c.args[0].Eval(env))
}
panic(fmt.Sprintf("unsupported function call: %s", c.fn))
}
Several of these methods can fail.
For example, a call expression could have an unknown function
or the wrong number of arguments.
It’s also possible to construct a unary or binary
expression with an invalid operator such as ! or <
(although the Parse function mentioned below will never do this).
These errors cause Eval to panic.
Other errors, like evaluating a Var not present in the environment,
merely cause Eval to return the wrong result.
All of these errors could be detected by inspecting the
Expr before evaluating it.
That will be the job of the Check method,
which we will show soon, but first let’s test Eval.
The TestEval function below is a test of the evaluator.
It uses the testing package, which we’ll explain in Chapter 11, but for now it’s enough to know that calling
t.Errorf reports an error.
The function loops over a table of inputs that defines three
expressions and different environments for each one.
The first expression computes the radius of a circle given its area
A, the second computes the sum of the cubes of two variables
x and y, and the third converts a Fahrenheit temperature
F to Celsius.
func TestEval(t *testing.T) {
tests := []struct {
expr string
env Env
want string
}{
{"sqrt(A / pi)", Env{"A": 87616, "pi": math.Pi}, "167"},
{"pow(x, 3) + pow(y, 3)", Env{"x": 12, "y": 1}, "1729"},
{"pow(x, 3) + pow(y, 3)", Env{"x": 9, "y": 10}, "1729"},
{"5 / 9 * (F - 32)", Env{"F": -40}, "-40"},
{"5 / 9 * (F - 32)", Env{"F": 32}, "0"},
{"5 / 9 * (F - 32)", Env{"F": 212}, "100"},
}
var prevExpr string
for _, test := range tests {
// Print expr only when it changes.
if test.expr != prevExpr {
fmt.Printf("
%s
", test.expr)
prevExpr = test.expr
}
expr, err := Parse(test.expr)
if err != nil {
t.Error(err) // parse error
continue
}
got := fmt.Sprintf("%.6g", expr.Eval(test.env))
fmt.Printf(" %v => %s
", test.env, got)
if got != test.want {
t.Errorf("%s.Eval() in %s = %q, want %q
",
test.expr, test.env, got, test.want)
}
}
}
For each entry in the table, the test parses the expression,
evaluates it in the environment, and prints the result.
We don’t have space to show the Parse function here, but
you’ll find it if you download the package using go get.
The go test command (§11.1)
runs a package’s tests:
$ go test -v gopl.io/ch7/eval
The -v flag lets us see the printed output of the test, which
is normally suppressed for a successful test like this one.
Here is the output of the test’s fmt.Printf statements:
sqrt(A / pi)
map[A:87616 pi:3.141592653589793] => 167
pow(x, 3) + pow(y, 3)
map[x:12 y:1] => 1729
map[x:9 y:10] => 1729
5 / 9 * (F - 32)
map[F:-40] => -40
map[F:32] => 0
map[F:212] => 100
Fortunately the inputs so far have all been well formed, but our luck is unlikely to last. Even in interpreted languages, it is common to check the syntax for static errors, that is, mistakes that can be detected without running the program. By separating the static checks from the dynamic ones, we can detect errors sooner and perform many checks only once instead of each time an expression is evaluated.
Let’s add another method to the Expr interface.
The Check method checks for static errors in an expression
syntax tree.
We’ll explain its vars parameter in a moment.
type Expr interface {
Eval(env Env) float64
// Check reports errors in this Expr and adds its Vars to the set.
Check(vars map[Var]bool) error
}
The concrete Check methods are shown below.
Evaluation of literal and Var cannot fail, so the
Check methods for these types return nil.
The methods for unary and binary first check that the
operator is valid, then recursively check the operands.
Similarly, the method for call first checks that the function
is known and has the right number of arguments, then recursively
checks each argument.
func (v Var) Check(vars map[Var]bool) error {
vars[v] = true
return nil
}
func (literal) Check(vars map[Var]bool) error {
return nil
}
func (u unary) Check(vars map[Var]bool) error {
if !strings.ContainsRune("+-", u.op) {
return fmt.Errorf("unexpected unary op %q", u.op)
}
return u.x.Check(vars)
}
func (b binary) Check(vars map[Var]bool) error {
if !strings.ContainsRune("+-*/", b.op) {
return fmt.Errorf("unexpected binary op %q", b.op)
}
if err := b.x.Check(vars); err != nil {
return err
}
return b.y.Check(vars)
}
func (c call) Check(vars map[Var]bool) error {
arity, ok := numParams[c.fn]
if !ok {
return fmt.Errorf("unknown function %q", c.fn)
}
if len(c.args) != arity {
return fmt.Errorf("call to %s has %d args, want %d",
c.fn, len(c.args), arity)
}
for _, arg := range c.args {
if err := arg.Check(vars); err != nil {
return err
}
}
return nil
}
var numParams = map[string]int{"pow": 2, "sin": 1, "sqrt": 1}
We’ve listed a selection of flawed inputs and the errors they
elicit, in two groups.
The Parse function (not shown) reports syntax errors and
the Check function reports semantic errors.
x % 2 unexpected '%' math.Pi unexpected '.' !true unexpected '!' "hello" unexpected '"' log(10) unknown function "log" sqrt(1, 2) call to sqrt has 2 args, want 1
Check’s argument, a set of Vars, accumulates the set
of variable names found within the expression.
Each of these variables must be present in the environment for
evaluation to succeed.
This set is logically the result of the call to Check,
but because the method is recursive, it is more convenient for Check
to populate a set passed as a parameter.
The client must provide an empty set in the initial call.
In Section 3.2, we plotted a function f(x,y) that
was fixed at compile time.
Now that we can parse, check, and evaluate expressions in strings, we can
build a web application that receives an expression at run time from the
client and plots the surface of that function.
We can use the vars set to check that the expression is a
function of only two variables, x and y—three,
actually, since we’ll provide r, the radius, as a convenience.
And we’ll use the Check method to reject ill-formed expressions
before evaluation begins so that we don’t repeat those checks during
the 40,000 evaluations (100×100 cells, each with four corners) of the
function that follow.
The parseAndCheck function combines these parsing and checking
steps:
import "gopl.io/ch7/eval"
func parseAndCheck(s string) (eval.Expr, error) {
if s == "" {
return nil, fmt.Errorf("empty expression")
}
expr, err := eval.Parse(s)
if err != nil {
return nil, err
}
vars := make(map[eval.Var]bool)
if err := expr.Check(vars); err != nil {
return nil, err
}
for v := range vars {
if v != "x" && v != "y" && v != "r" {
return nil, fmt.Errorf("undefined variable: %s", v)
}
}
return expr, nil
}
To make this a web application, all we need is the plot
function below, which has the familiar signature of an
http.HandlerFunc:
func plot(w http.ResponseWriter, r *http.Request) {
r.ParseForm()
expr, err := parseAndCheck(r.Form.Get("expr"))
if err != nil {
http.Error(w, "bad expr: "+err.Error(), http.StatusBadRequest)
return
}
w.Header().Set("Content-Type", "image/svg+xml")
surface(w, func(x, y float64) float64 {
r := math.Hypot(x, y) // distance from (0,0)
return expr.Eval(eval.Env{"x": x, "y": y, "r": r})
})
}
Figure 7.7.
The surfaces of three functions:
(a) sin(-x)*pow(1.5,-r);
(b) pow(2,sin(y))*pow(2,sin(x))/12;
(c) sin(x*y/10)/10.
The plot function parses and checks the expression specified in
the HTTP request and uses it to create an anonymous function of two
variables.
The anonymous function has the same signature as the fixed function
f from the original surface-plotting program, but it evaluates
the user-supplied expression.
The environment defines x, y, and the radius r.
Finally, plot calls surface, which is just the
main function from gopl.io/ch3/surface, modified to take
the function to plot and the output io.Writer as parameters,
instead of using the fixed function f and os.Stdout.
Figure 7.7 shows three surfaces produced by
the program.
Exercise 7.13:
Add a String method to Expr to pretty-print the syntax
tree.
Check that the results, when parsed again, yield an equivalent tree.
Exercise 7.14:
Define a new concrete type that satisfies the Expr interface
and provides a new operation such as computing the minimum value of
its operands.
Since the Parse function does not create instances of this new
type, to use it you will need to construct a syntax tree directly (or
extend the parser).
Exercise 7.15: Write a program that reads a single expression from the standard input, prompts the user to provide values for any variables, then evaluates the expression in the resulting environment. Handle all errors gracefully.
Exercise 7.16: Write a web-based calculator program.