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 Var
s, 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}) }) }
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.
3.143.17.128