Go語言表示式求值器

在本節中，我們將建立簡單算術表示式的一個求值器。我們將使用一個介面 Expr 來代表這種語言中的任意一個表示式。現在，這個介面沒有任何方法，但稍後我們會逐個新增。

// Expr：算術表示式
type Expr interface{}

我們的表示式語言套件括浮點數位面量，二元操作符 +、-、*、/，一元操作符 -x 和 +x，函數呼叫 pow(x,y)、sin(x) 和 sqrt(x)，變數（比如 x 和 pi），當然，還有圓括號和標準的操作符優先順序。所有的值都是 float64 型別。下面是幾個範例表示式：

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

下面 5 種具體型別代表特定型別的表示式。Var 代表變數應用（很快我們將了解到為什麼這個型別需要導岀）。literal 代表浮點數常數。unary 和 binary 型別代表有一個或者兩個運算元的操作符表示式，而運算元則可以任意的 Expr。call 代表函數呼叫，這裡限制它的 fn 欄位只能是 pow、sin 和 sqrt。

// Var 表示一個變數，比如 x
type Var string
// literal 是一個數位常數，比如 3.141
type literal float64
// unary 表示一元操作符表示式，比如-x
type unary struct {
    op rune // '+', '-' 中的一個
    x Expr
}
// binary 表示二元操作符表示式，比如 x+y
type binary struct {
    op rune // '+', '-', '*', '/' 中的一個
    x, y Expr
}
// call 表示函數呼叫表示式，比如 sin(x)
type call struct {
    fn string // one of "pow", "sin", "sqrt" 中的一個
    args []Expr
}

要對包含變數的表示式進行求值，需要一個上下文 (environment) 來把變數對映到數值：

type Env map[Var]float64

我們還需要為每種型別的表示式定義一個 Eval 方法來返回表示式在一個給定上下文下的值。既然每個表示式都必須提供這個方法，那麼可以把它加到 Expr 介面中。這個包只匯出了型別 Expr、Env 和 Var。用戶端可以在不接觸其他表示式型別的情況下使用這個求值器。

type Expr interface {
// Eval 返回表示式在 env 上下文下的值
Eval(env Env) float64
}

下面是具體的 Eval 方法。Var 的 Eval 方法從上下文中查詢結果，如果變數不存在則返回 0 literal 的 Eval 方法則直接返冋本身的值。

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

unary 和 binary 的 Eval 方法首先對它們的運算元遞迴求值，然後應用 op 操作。我們不把除以 0 或者無窮大當做錯誤（儘管它們生成的結果顯然不是有窮數）。最後，call 方法先對 pow、sin 或者 sqrt 函數的引數求值，再呼叫 math 包中的對應函數。

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 '*1:
        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(erw))
    case "sqrt":
        return math.Sqrt(c.args[0].Eval(env))
    }
    panic(fmt.Sprintf("unsupported function call: %s", c.fn))
}

某些方法可能會失敗，比如 call 表示式可能會遇到未知的函數，或者引數數量不對。也有可能用“!”或者“<”這類無效的操作符構造了一個 unary 或 binary 表示式（儘管後面的 Parse 函數不會產生這樣的結果）。這些錯誤都會導致 Eval 崩潰。

其他錯誤（比如對一個上下文中沒有定義的變數求值）僅會導致返回不正確的結果。所有這些錯誤都可以在求值之前做檢查來發現。後面的 Check 方法就負責完成這個任務，但我們先測試 Eval。

下面的 TestEval 函數用於測試求值器，它使用 testing 包。我們知道呼叫 t.Errorf 來報告錯誤。這個函數遍歷一個表格，表格中定義了三個表示式並為每個表示式準備了不同上下文。第一個表示式用於根據圓面積 A 求半徑，第二個用於計算兩個變數 x 和 y 的立方和，第三個把華氏溫度 F 轉為攝氏溫度。

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 {
        // 僅在表示式變更時才輸出
        if test.expr != prevExpr {
            fmt.Printf("n%sn", test.expr)
            prevExpr = test.expr
        }
        expr, err := Parse(test.expr)
        if err != nil {
            t.Error(err) // 解析出錯
            continue
        }
        got := fmt.Sprintf("%.6g", expr.Eval(test.env))
        fmt.Printf("t%v => %sn", test.env, got)
        if got != test.want {
            t.Errorf("%s.Eval() in %v = %q, want %qn", test.expr, test.env, got, test.want)
        }
    }
}

對於表格中的每一行記錄，該測試先解析表示式，在上下文中求值，再輸出表示式。這裡沒有足夠的空間來顯示 Parse 函數，但可以通過 go get 來下載原始碼，自行檢視。

go test 命令可用於執行包的測試：

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

啟用 -v 選項後可以看到測試的輸出，通常情況下對於結果正確的測試輸出就不顯示了。下面就是測試中 fmt.Printf 語句輸岀的內容。

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

幸運的是，到現在為止所有的輸入都是合法的，但這種幸運是不能持久的。即使在解釋性語言中，通過語法檢查來發現靜態錯誤（即不用執行程式也能檢測出來的錯誤）也是很常見的。通過分離靜態檢查和動態檢查，我們可以更快發現錯誤，也可以只在執行前檢查一次，而不用在表示式求值時每次都檢查。

讓我們給 Expr 方法加上另外一個方法。Check 方法用於在表示式語法樹上檢查靜態錯誤。它的 vars 引數將稍後解釋。

type Expr interface {
    Eval(env Env) float64
    // Check 方法報告表示式中的錯誤，並把表示式中的變數加入 Vars 中
    Check(vars map[Var]bool) error
}

具體的 Check 方法如下所示。literal 和 Var 的求值不可能出錯，所以 Check 方法返回 nil。unary 和 binary 的方法首先檢查操作符是否合法，再遞回地檢查運算元。類似地，call 的方法首先檢查函數是否是已知的，然後檢查引數個數是否正確，最後遞回檢查每個引數。

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}

下面分兩列展示了一些有錯誤的輸入，以及它們觸發的錯誤。Parse 函數（沒有顯示）報告了語法錯誤，Check 方法報告了語意錯誤。

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 的輸入引數是一個 Ver 集合，它收集在表達中發現的變數名。要讓表示式能成功求值，上下文必須包含所有的這些變數。從邏輯上來講，這個集合應當是 Check 的輸出結果而不是輸入引數，但因為這個方法是遞迴呼叫的，在這種情況下使用引數更為方便。呼叫方在最初呼叫時需要提供一個空的集合。

既然我們可以對字串形式的表示式進行解析、檢查和求值，那麼就可以構建一個 Web 應用，在執行時從用戶端接收一個表示式，並繪製函數的曲面圖。可以使用 vars 集合來檢查表示式是一個只有兩個變數 x、y 的函數（為了簡單起見，還提供了半徑 r，所以實際上是 3 個變數）。使用 Check 方法來拒絕掉不規範的表示式，避免了在接下來的 40000 次求值中重複檢查（4 個象限中 100 x 100 的格子）。

下面的 parseAndCheck 函陣列合了解析和檢查步驟：

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
}

要構造完這個 Web 應用，僅需要增加下面的 plot 函數，其函數簽名與 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/syg+xml")
    surface(w, func(x, y float64) float64 {
        r := math.Hypot(x, y)   // 與(0,0)之間的距離
        return expr.Eval(eval.Env{"x": x, "y": y, "r" : r})
    })
}

plot 函數解析並檢查 HTTP 請求中的表示式，並用它來建立一個有兩個變數的匿名函數。這個匿名函數與原始曲面圖繪製程式中的f有同樣的簽名，且能對使用者提供的表示式進行求值。上下文定義了 x、y 和半徑 r。

最後，plot 呼叫了 surface 函數，surface 函數來自 gop1.io/ch3/surface 中的 main 函數，略做修改，加了引數用於接受繪製函數和輸出用的 io.Writer，原始版本直接使用了函數 f 和 os.Stdout。下圖顯示了用這個程式繪製的三張曲面圖。

（a）

(b)