原文鏈接：https://gopl-zh.github.io/ch7/ch7-09.html

7.9. 示例: 表達(dá)式求值

在本節(jié)中，我們會(huì)構(gòu)建一個(gè)簡(jiǎn)單算術(shù)表達(dá)式的求值器。我們將使用一個(gè)接口Expr來(lái)表示Go語(yǔ)言中任意的表達(dá)式?，F(xiàn)在這個(gè)接口不需要有方法，但是我們后面會(huì)為它增加一些。

// An Expr is an arithmetic expression.
type Expr interface{}

我們的表達(dá)式語(yǔ)言包括浮點(diǎn)數(shù)符號(hào)（小數(shù)點(diǎn)）；二元操作符+，-，*， 和/；一元操作符-x和+x；調(diào)用pow(x,y)，sin(x)，和sqrt(x)的函數(shù)；例如x和pi的變量；當(dāng)然也有括號(hào)和標(biāo)準(zhǔn)的優(yōu)先級(jí)運(yùn)算符。所有的值都是float64類(lèi)型。這下面是一些表達(dá)式的例子：

sqrt(A / pi)
pow(x, 3) + pow(y, 3)
(F - 32) * 5 / 9

下面的五個(gè)具體類(lèi)型表示了具體的表達(dá)式類(lèi)型。Var類(lèi)型表示對(duì)一個(gè)變量的引用。（我們很快會(huì)知道為什么它可以被輸出。）literal類(lèi)型表示一個(gè)浮點(diǎn)型常量。unary和binary類(lèi)型表示有一到兩個(gè)運(yùn)算對(duì)象的運(yùn)算符表達(dá)式，這些操作數(shù)可以是任意的Expr類(lèi)型。call類(lèi)型表示對(duì)一個(gè)函數(shù)的調(diào)用；我們限制它的fn字段只能是pow，sin或者sqrt。

gopl.io/ch7/eval

// 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
}

為了計(jì)算一個(gè)包含變量的表達(dá)式，我們需要一個(gè)environment變量將變量的名字映射成對(duì)應(yīng)的值：

type Env map[Var]float64

我們也需要每個(gè)表達(dá)式去定義一個(gè)Eval方法，這個(gè)方法會(huì)根據(jù)給定的environment變量返回表達(dá)式的值。因?yàn)槊總€(gè)表達(dá)式都必須提供這個(gè)方法，我們將它加入到Expr接口中。這個(gè)包只會(huì)對(duì)外公開(kāi)Expr，Env，和Var類(lèi)型。調(diào)用方不需要獲取其它的表達(dá)式類(lèi)型就可以使用這個(gè)求值器。

type Expr interface {
    // Eval returns the value of this Expr in the environment env.
    Eval(env Env) float64
}

下面給大家展示一個(gè)具體的Eval方法。Var類(lèi)型的這個(gè)方法對(duì)一個(gè)environment變量進(jìn)行查找，如果這個(gè)變量沒(méi)有在environment中定義過(guò)這個(gè)方法會(huì)返回一個(gè)零值，literal類(lèi)型的這個(gè)方法簡(jiǎn)單的返回它真實(shí)的值。

func (v Var) Eval(env Env) float64 {
    return env[v]
}

func (l literal) Eval(_ Env) float64 {
    return float64(l)
}

unary和binary的Eval方法會(huì)遞歸的計(jì)算它的運(yùn)算對(duì)象，然后將運(yùn)算符op作用到它們上。我們不將被零或無(wú)窮數(shù)除作為一個(gè)錯(cuò)誤，因?yàn)樗鼈兌紩?huì)產(chǎn)生一個(gè)固定的結(jié)果——無(wú)限。最后，call的這個(gè)方法會(huì)計(jì)算對(duì)于pow，sin，或者sqrt函數(shù)的參數(shù)值，然后調(diào)用對(duì)應(yīng)在math包中的函數(shù)。

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))
}

一些方法會(huì)失敗。例如，一個(gè)call表達(dá)式可能有未知的函數(shù)或者錯(cuò)誤的參數(shù)個(gè)數(shù)。用一個(gè)無(wú)效的運(yùn)算符如!或者<去構(gòu)建一個(gè)unary或者binary表達(dá)式也是可能會(huì)發(fā)生的（盡管下面提到的Parse函數(shù)不會(huì)這樣做）。這些錯(cuò)誤會(huì)讓Eval方法panic。其它的錯(cuò)誤，像計(jì)算一個(gè)沒(méi)有在environment變量中出現(xiàn)過(guò)的Var，只會(huì)讓Eval方法返回一個(gè)錯(cuò)誤的結(jié)果。所有的這些錯(cuò)誤都可以通過(guò)在計(jì)算前檢查Expr來(lái)發(fā)現(xiàn)。這是我們接下來(lái)要講的Check方法的工作，但是讓我們先測(cè)試Eval方法。

下面的TestEval函數(shù)是對(duì)evaluator的一個(gè)測(cè)試。它使用了我們會(huì)在第11章講解的testing包，但是現(xiàn)在知道調(diào)用t.Errof會(huì)報(bào)告一個(gè)錯(cuò)誤就足夠了。這個(gè)函數(shù)循環(huán)遍歷一個(gè)表格中的輸入，這個(gè)表格中定義了三個(gè)表達(dá)式和針對(duì)每個(gè)表達(dá)式不同的環(huán)境變量。第一個(gè)表達(dá)式根據(jù)給定圓的面積A計(jì)算它的半徑，第二個(gè)表達(dá)式通過(guò)兩個(gè)變量x和y計(jì)算兩個(gè)立方體的體積之和，第三個(gè)表達(dá)式將華氏溫度F轉(zhuǎn)換成攝氏度。

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("\n%s\n", 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("\t%v => %s\n", test.env, got)
        if got != test.want {
            t.Errorf("%s.Eval() in %v = %q, want %q\n",
            test.expr, test.env, got, test.want)
        }
    }
}

對(duì)于表格中的每一條記錄，這個(gè)測(cè)試會(huì)解析它的表達(dá)式然后在環(huán)境變量中計(jì)算它，輸出結(jié)果。這里我們沒(méi)有空間來(lái)展示Parse函數(shù)，但是如果你使用go get下載這個(gè)包你就可以看到這個(gè)函數(shù)。

go test(§11.1) 命令會(huì)運(yùn)行一個(gè)包的測(cè)試用例：

$ go test -v gopl.io/ch7/eval

這個(gè)-v標(biāo)識(shí)可以讓我們看到測(cè)試用例打印的輸出；正常情況下像這樣一個(gè)成功的測(cè)試用例會(huì)阻止打印結(jié)果的輸出。這里是測(cè)試用例里fmt.Printf語(yǔ)句的輸出：

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

幸運(yùn)的是目前為止所有的輸入都是適合的格式，但是我們的運(yùn)氣不可能一直都有。甚至在解釋型語(yǔ)言中，為了靜態(tài)錯(cuò)誤檢查語(yǔ)法是非常常見(jiàn)的；靜態(tài)錯(cuò)誤就是不用運(yùn)行程序就可以檢測(cè)出來(lái)的錯(cuò)誤。通過(guò)將靜態(tài)檢查和動(dòng)態(tài)的部分分開(kāi)，我們可以快速的檢查錯(cuò)誤并且對(duì)于多次檢查只執(zhí)行一次而不是每次表達(dá)式計(jì)算的時(shí)候都進(jìn)行檢查。

讓我們往Expr接口中增加另一個(gè)方法。Check方法對(duì)一個(gè)表達(dá)式語(yǔ)義樹(shù)檢查出靜態(tài)錯(cuò)誤。我們馬上會(huì)說(shuō)明它的vars參數(shù)。

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
}

具體的Check方法展示在下面。literal和Var類(lèi)型的計(jì)算不可能失敗，所以這些類(lèi)型的Check方法會(huì)返回一個(gè)nil值。對(duì)于unary和binary的Check方法會(huì)首先檢查操作符是否有效，然后遞歸的檢查運(yùn)算單元。相似地對(duì)于call的這個(gè)方法首先檢查調(diào)用的函數(shù)是否已知并且有沒(méi)有正確個(gè)數(shù)的參數(shù)，然后遞歸的檢查每一個(gè)參數(shù)。

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}

我們?cè)趦蓚€(gè)組中有選擇地列出有問(wèn)題的輸入和它們得出的錯(cuò)誤。Parse函數(shù)（這里沒(méi)有出現(xiàn)）會(huì)報(bào)出一個(gè)語(yǔ)法錯(cuò)誤和Check函數(shù)會(huì)報(bào)出語(yǔ)義錯(cuò)誤。

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方法的參數(shù)是一個(gè)Var類(lèi)型的集合，這個(gè)集合聚集從表達(dá)式中找到的變量名。為了保證成功的計(jì)算，這些變量中的每一個(gè)都必須出現(xiàn)在環(huán)境變量中。從邏輯上講，這個(gè)集合就是調(diào)用Check方法返回的結(jié)果，但是因?yàn)檫@個(gè)方法是遞歸調(diào)用的，所以對(duì)于Check方法，填充結(jié)果到一個(gè)作為參數(shù)傳入的集合中會(huì)更加的方便。調(diào)用方在初始調(diào)用時(shí)必須提供一個(gè)空的集合。

在第3.2節(jié)中，我們繪制了一個(gè)在編譯期才確定的函數(shù)f(x,y)。現(xiàn)在我們可以解析，檢查和計(jì)算在字符串中的表達(dá)式，我們可以構(gòu)建一個(gè)在運(yùn)行時(shí)從客戶(hù)端接收表達(dá)式的web應(yīng)用并且它會(huì)繪制這個(gè)函數(shù)的表示的曲面。我們可以使用集合vars來(lái)檢查表達(dá)式是否是一個(gè)只有兩個(gè)變量x和y的函數(shù)——實(shí)際上是3個(gè)，因?yàn)槲覀優(yōu)榱朔奖銜?huì)提供半徑大小r。并且我們會(huì)在計(jì)算前使用Check方法拒絕有格式問(wèn)題的表達(dá)式，這樣我們就不會(huì)在下面函數(shù)的40000個(gè)計(jì)算過(guò)程（100x100個(gè)柵格，每一個(gè)有4個(gè)角）重復(fù)這些檢查。

這個(gè)ParseAndCheck函數(shù)混合了解析和檢查步驟的過(guò)程：

gopl.io/ch7/surface

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
}

為了編寫(xiě)這個(gè)web應(yīng)用，所有我們需要做的就是下面這個(gè)plot函數(shù)，這個(gè)函數(shù)有和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})
    })
}

這個(gè)plot函數(shù)解析和檢查在HTTP請(qǐng)求中指定的表達(dá)式并且用它來(lái)創(chuàng)建一個(gè)兩個(gè)變量的匿名函數(shù)。這個(gè)匿名函數(shù)和來(lái)自原來(lái)surface-plotting程序中的固定函數(shù)f有相同的簽名，但是它計(jì)算一個(gè)用戶(hù)提供的表達(dá)式。環(huán)境變量中定義了x，y和半徑r。最后plot調(diào)用surface函數(shù)，它就是gopl.io/ch3/surface中的主要函數(shù)，修改后它可以接受plot中的函數(shù)和輸出io.Writer作為參數(shù)，而不是使用固定的函數(shù)f和os.Stdout。圖7.7中顯示了通過(guò)程序產(chǎn)生的3個(gè)曲面。

練習(xí) 7.13： 為Expr增加一個(gè)String方法來(lái)打印美觀(guān)的語(yǔ)法樹(shù)。當(dāng)再一次解析的時(shí)候，檢查它的結(jié)果是否生成相同的語(yǔ)法樹(shù)。

練習(xí) 7.14： 定義一個(gè)新的滿(mǎn)足Expr接口的具體類(lèi)型并且提供一個(gè)新的操作例如對(duì)它運(yùn)算單元中的最小值的計(jì)算。因?yàn)镻arse函數(shù)不會(huì)創(chuàng)建這個(gè)新類(lèi)型的實(shí)例，為了使用它你可能需要直接構(gòu)造一個(gè)語(yǔ)法樹(shù)（或者繼承parser接口）。

練習(xí) 7.15： 編寫(xiě)一個(gè)從標(biāo)準(zhǔn)輸入中讀取一個(gè)單一表達(dá)式的程序，用戶(hù)及時(shí)地提供對(duì)于任意變量的值，然后在結(jié)果環(huán)境變量中計(jì)算表達(dá)式的值。優(yōu)雅的處理所有遇到的錯(cuò)誤。

練習(xí) 7.16： 編寫(xiě)一個(gè)基于web的計(jì)算器程序。