從Java走進Scala:構建計算器 case類和模式匹配
上個月的文章發表后，我又收到了一些抱怨/評論，說我迄今為止在本系列中所用的示例都沒涉及到什么實質性的問題。當然在學習一個新語言的初期使用一些小例子是很合理的，而讀者想要看到一些更 “現實的” 示例，從而了解語言的深層領域和強大功能以及其優勢，這也是理所當然的。因此，在這個月的文章中，我們來分兩部分練習構建特定于領域的語言（DSL）— 本文以一個小的計算器語言為例。
特定于領域的語言
可能您無法（或沒有時間）承受來自于您的項目經理給您的壓力，那么讓我直接了當地說吧：特定于領域的語言無非就是嘗試（再一次）將一個應用程序的功能放在它該屬于的地方 — 用戶的手中。
通過定義一個新的用戶可以理解并直接使用的文本語言，程序員成功擺脫了不停地處理 UI 請求和功能增強的麻煩，而且這樣還可以使用戶能夠自己創建腳本以及其他的工具，用來給他們所構建的應用程序創建新的行為。雖然這個例子可能有點冒險（或許會惹來幾封抱怨的電子郵件），但我還是要說，DSL 的最成功的例子就是 Microsoft® Office Excel “語言”，用于表達電子表格單元格的各種計算和內容。甚至有些人認為 SQL 本身就是 DSL，但這次是一個旨在與關系數據庫相交互的語言（想象一下如果程序員要通過傳統 API read()/write() 調用來從 Oracle 中獲取數據的話，那將會是什么樣子）。
這里構建的 DSL 是一個簡單的計算器語言，用于獲取并計算數學表達式。其實，這里的目標是要創建一個小型語言，這個語言能夠允許用戶來輸入相對簡單的代數表達式，然后這個代碼來為它求值并產生結果。為了盡量簡單明了，該語言不會支持很多功能完善的計算器所支持的特性，但我不也不想把它的用途限定在教學上 — 該語言一定要具備足夠的可擴展性，以使讀者無需徹底改變該語言就能夠將它用作一個功能更強大的語言的核心。這意味著該語言一定要可以被輕易地擴展，并要盡量保持封裝性，用起來不會有任何的阻礙。
換句話說，（最終的）目標是要允許客戶機編寫代碼，以達到如下的目的：
清單 1. 計算器 DSL：目標
- // This is Java using the Calculator
- String s = "((5 * 10) + 7)";
- double result = com.tedneward.calcdsl.Calculator.evaluate(s);
- System.out.println("We got " + result); // Should be 57
我們不會在一篇文章完成所有的論述，但是我們在本篇文章中可以學習到一部分內容，在下一篇文章完成全部內容。
從實現和設計的角度看，可以從構建一個基于字符串的解析器來著手構建某種可以 “挑選每個字符并動態計算” 的解析器，這的確***誘惑力，但是這只適用于較簡單的語言，而且其擴展性不是很好。如果語言的目標是實現簡單的擴展性，那么在深入研究實現之前，讓我們先花點時間想一想如何設計語言。
根據那些基本的編譯理論中最精華的部分，您可以得知一個語言處理器（包括解釋器和編譯器）的基本運算至少由兩個階段組成：
解析器，用于獲取輸入的文本并將其轉換成 Abstract Syntax Tree（AST）。
代碼生成器（在編譯器的情況下），用于獲取 AST 并從中生成所需字節碼；或是求值器（在解釋器的情況下），用于獲取 AST 并計算它在 AST 里面所發現的內容。
擁有 AST 就能夠在某種程度上優化結果樹，如果意識到這一點的話，那么上述區別的原因就變得更加顯而易見了；對于計算器，我們可能要仔細檢查表達式，找出可以截去表達式的整個片段的位置，諸如在乘法表達式中運算數為 “0” 的位置（它表明無論其他運算數是多少，運算結果都會是 “0”）。
您要做的***件事是為計算器語言定義該 AST。幸運的是，Scala 有 case 類：一種提供了豐富數據、使用了非常薄的封裝的類，它們所具有的一些特性使它們很適合構建 AST。
關于 DSL 的更多信息
DSL 這個主題的涉及面很廣；它的豐富性和廣泛性不是本文的一個段落可以描述得了的。想要了解更多 DSL 信息的讀者可以查閱本文末尾列出的 Martin Fowler 的 “正在進展中的圖書”；特別要注意關于 “內部” 和 “外部” DSL 之間的討論。Scala 以其靈活的語法和強大的功能而成為***有力的構建內部和外部 DSL 的語言。更加具體的介紹，可參考51CTO之前發布的DSL領域特定語言初探一文。
#p#
case類
在深入到 AST 定義之前，讓我先簡要概述一下什么是 case類。case類是使 scala 程序員得以使用某些假設的默認值來創建一個類的一種便捷機制。例如，當編寫如下內容時：
清單 2. 對 person 使用 case類
- case class Person(first:String, last:String, age:Int)
- {
- }
Scala 編譯器不僅僅可以按照我們對它的期望生成預期的構造函數 — Scala 編譯器還可以生成常規意義上的 equals()、toString() 和 hashCode() 實現。事實上，這種 case類很普通（即它沒有其他的成員），因此 case 類聲明后面的大括號的內容是可選的：
清單 3. 世界上最短的類清單
- case class Person(first:String, last:String, age:Int)
這一點通過我們的老朋友 javap 很容易得以驗證：
清單 4. 神圣的代碼生成器，Batman！
- C:\Projects\Exploration\Scala>javap Person
- Compiled from "case.scala"
- public class Person extends java.lang.Object implements scala.ScalaObject,scala.
- Product,java.io.Serializable{
- public Person(java.lang.String, java.lang.String, int);
- public java.lang.Object productElement(int);
- public int productArity();
- public java.lang.String productPrefix();
- public boolean equals(java.lang.Object);
- public java.lang.String toString();
- public int hashCode();
- public int $tag();
- public int age();
- public java.lang.String last();
- public java.lang.String first();
- }
如您所見，伴隨 case 類發生了很多傳統類通常不會引發的事情。這是因為 case 類是要與 Scala 的模式匹配（在 “集合類型” 中曾簡短分析過）結合使用的。
使用 case 類與使用傳統類有些不同，這是因為通常它們都不是通過傳統的 “new” 語法構造而成的；事實上，它們通常是通過一種名稱與類相同的工廠方法來創建的：
清單 5. 沒有使用 new 語法?
- object App
- {
- def main(args : Array[String]) : Unit =
- {
- val ted = Person("Ted", "Neward", 37)
- }
- }
case 類本身可能并不比傳統類有趣，或者有多么的與眾不同，但是在使用它們時會有一個很重要的差別。與引用等式相比，case 類生成的代碼更喜歡按位（bitwise）等式，因此下面的代碼對 Java 程序員來說有些有趣的驚喜：
清單 6. 這不是以前的類
- object App
- {
- def main(args : Array[String]) : Unit =
- {
- val ted = Person("Ted", "Neward", 37)
- val ted2 = Person("Ted", "Neward", 37)
- val amanda = Person("Amanda", "Laucher", 27)
- System.out.println("ted == amanda: " +
- (if (ted == amanda) "Yes" else "No"))
- System.out.println("ted == ted: " +
- (if (ted == ted) "Yes" else "No"))
- System.out.println("ted == ted2: " +
- (if (ted == ted2) "Yes" else "No"))
- }
- }
- /*
- C:\Projects\Exploration\Scala>scala App
- ted == amanda: No
- ted == ted: Yes
- ted == ted2: Yes
- */
case 類的真正價值體現在模式匹配中，本系列的讀者可以回顧一下模式匹配（參見 本系列的第二篇文章，關于 Scala 中的各種控制構造），模式匹配類似 Java 的 “switch/case”，只不過它的本領和功能更加強大。模式匹配不僅能夠檢查匹配構造的值，從而執行值匹配，還可以針對局部通配符（類似局部 “默認值” 的東西）匹配值，case 還可以包括對測試匹配的保護，來自匹配標準的值還可以綁定于局部變量，甚至符合匹配標準的類型本身也可以進行匹配。
有了 case 類，模式匹配具備了更強大的功能，如清單 7 所示：
清單 7. 這也不是以前的 switch
- case class Person(first:String, last:String, age:Int);
- object App
- {
- def main(args : Array[String]) : Unit =
- {
- val ted = Person("Ted", "Neward", 37)
- val amanda = Person("Amanda", "Laucher", 27)
- System.out.println(process(ted))
- System.out.println(process(amanda))
- }
- def process(p : Person) =
- {
- "Processing " + p + " reveals that" +
- (p match
- {
- case Person(_, _, a) if a > 30 =>
- " they're certainly old."
- case Person(_, "Neward", _) =>
- " they come from good genes...."
- case Person(first, last, ageInYears) if ageInYears > 17 =>
- first + " " + last + " is " + ageInYears + " years old."
- case _ =>
- " I have no idea what to do with this person"
- })
- }
- }
- /*
- C:\Projects\Exploration\Scala>scala App
- Processing Person(Ted,Neward,37) reveals that they're certainly old.
- Processing Person(Amanda,Laucher,27) reveals that Amanda Laucher is 27 years old
- .
- */
清單 7 中發生了很多操作。下面就讓我們先慢慢了解發生了什么，然后回到計算器，看看如何應用它們。
首先，整個 match 表達式被包裹在圓括號中：這并非模式匹配語法的要求，但之所以會這樣是因為我把模式匹配表達式的結果根據其前面的前綴串聯了起來（切記，函數性語言里面的任何東西都是一個表達式）。
其次，***個 case 表達式里面有兩個通配符（帶下劃線的字符就是通配符），這意味著該匹配將會為符合匹配的 Person 中那兩個字段獲取任何值，但是它引入了一個局部變量 a，p.age 中的值會綁定在這個局部變量上。這個 case 只有在同時提供的起保護作用的表達式（跟在它后邊的 if 表達式）成功時才會成功，但只有***個 Person 會這樣，第二個就不會了。第二個 case 表達式在 Person 的 firstName 部分使用了一個通配符，但在 lastName 部分使用常量字符串 Neward 來匹配，在 age 部分使用通配符來匹配。
由于***個 Person 已經通過前面的 case 匹配了，而且第二個 Person 沒有姓 Neward，所以該匹配不會為任何一個 Person 而被觸發（但是，Person("Michael", "Neward", 15) 會由于***個 case 中的 guard 子句失敗而轉到第二個 case）。
第三個示例展示了模式匹配的一個常見用途，有時稱之為提取，在這個提取過程中，匹配對象 p 中的值為了能夠在 case 塊內使用而被提取到局部變量中（***個、***一個和 ageInYears）。***的 case 表達式是普通 case 的默認值，它只有在其他 case 表達式均未成功的情況下才會被觸發。
簡要了解了 case類和模式匹配之后，接下來讓我們回到創建計算器 AST 的任務上。
#p#
計算器 AST
首先，計算器的 AST 一定要有一個公用基類型，因為數學表達式通常都由子表達式組成；通過 “5 + (2 * 10)” 就可以很容易地看到這一點，在這個例子中，子表達式 “(2 * 10)” 將會是 “+” 運算的右側運算數。
事實上，這個表達式提供了三種 AST 類型：
◆基表達式
◆承載常量值的 Number 類型
◆承載運算和兩個運算數的 BinaryOperator
想一下，算數中還允許將一元運算符用作求負運算符（減號），將值從正數轉換為負數，因此我們可以引入下列基本 AST：
清單 8. 計算器 AST（src/calc.scala）
- package com.tedneward.calcdsl
- {
- private[calcdsl] abstract class Expr
- private[calcdsl] case class Number(value : Double) extends Expr
- private[calcdsl] case class UnaryOp(operator : String, arg : Expr) extends Expr
- private[calcdsl] case class BinaryOp(operator : String, left : Expr, right : Expr)
- extends Expr
- }
注意包聲明將所有這些內容放在一個包（com.tedneward.calcdsl）中，以及每一個類前面的訪問修飾符聲明表明該包可以由該包中的其他成員或子包訪問。之所以要注意這個是因為需要擁有一系列可以測試這個代碼的 JUnit 測試；計算器的實際客戶機并不一定非要看到 AST。因此，要將單元測試編寫成 com.tedneward.calcdsl 的一個子包：
清單 9. 計算器測試（testsrc/calctest.scala）
- package com.tedneward.calcdsl.test
- {
- class CalcTest
- {
- import org.junit._, Assert._
- @Test def ASTTest =
- {
- val n1 = Number(5)
- assertEquals(5, n1.value)
- }
- @Test def equalityTest =
- {
- val binop = BinaryOp("+", Number(5), Number(10))
- assertEquals(Number(5), binop.left)
- assertEquals(Number(10), binop.right)
- assertEquals("+", binop.operator)
- }
- }
- }
到目前為止還不錯。我們已經有了 AST。
再想一想，我們用了四行 Scala 代碼構建了一個類型分層結構，表示一個具有任意深度的數學表達式集合（當然這些數學表達式很簡單，但仍然很有用）。與 Scala 能夠使對象編程更簡單、更具表達力相比，這不算什么（不用擔心，真正強大的功能還在后面）。
接下來，我們需要一個求值函數，它將會獲取 AST，并求出它的數字值。有了模式匹配的強大功能，編寫這樣的函數簡直輕而易舉：
清單 10. 計算器（src/calc.scala）
- package com.tedneward.calcdsl
- {
- // ...
- object Calc
- {
- def evaluate(e : Expr) : Double =
- {
- e match {
- case Number(x) => x
- case UnaryOp("-", x) => -(evaluate(x))
- case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
- case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
- case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
- case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
- }
- }
- }
- }
注意 evaluate() 返回了一個 Double，它意味著模式匹配中的每一個 case 都必須被求值成一個 Double 值。這個并不難：數字僅僅返回它們的包含的值。但對于剩余的 case（有兩種運算符），我們還必須在執行必要運算（求負、加法、減法等）前計算運算數。正如常在函數性語言中所看到的，會使用到遞歸，所以我們只需要在執行整體運算前對每一個運算數調用 evaluate() 就可以了。
大多數忠實于面向對象的編程人員會認為在各種運算符本身以外 執行運算的想法根本就是錯誤的 — 這個想法顯然大大違背了封裝和多態性的原則。坦白說，這個甚至不值得討論；這很顯然違背 了封裝原則，至少在傳統意義上是這樣的。
在這里我們需要考慮的一個更大的問題是：我們到底從哪里封裝代碼？要記住 AST 類在包外是不可見的，還有就是客戶機（最終）只會傳入它們想求值的表達式的一個字符串表示。只有單元測試在直接與 AST case 類合作。
#p#
但這并不是說所有的封裝都沒有用了或過時了。事實上恰好相反：它試圖說服我們在對象領域所熟悉的方法之外，還有很多其他的設計方法也很奏效。不要忘了 Scala 兼具對象和函數性；有時候 Expr 需要在自身及其子類上附加其他行為（例如，實現良好輸出的 toString 方法），在這種情況下可以很輕松地將這些方法添加到 Expr。函數性和面向對象的結合提供了另一種選擇，無論是函數性編程人員還是對象編程人員，都不會忽略到另一半的設計方法，并且會考慮如何結合兩者來達到一些有趣的效果。
從設計的角度看，有些其他的選擇是有問題的；例如，使用字符串來承載運算符就有可能出現小的輸入錯誤，最終會導致結果不正確。在生產代碼中，可能會使用（也許必須使用）枚舉而非字符串，使用字符串的話就意味著我們可能潛在地 “開放” 了運算符，允許調用出更復雜的函數（諸如 abs、sin、cos、tan 等）乃至用戶定義的函數；這些函數是基于枚舉的方法很難支持的。
對所有設計和實現的來說，都不存在一個適當的決策方法，只能承擔后果。后果自負。
但是這里可以使用一個有趣的小技巧。某些數學表達式可以簡化，因而（潛在地）優化了表達式的求值（因此展示了 AST 的有用性）:
◆任何加上 “0” 的運算數都可以被簡化成非零運算數。
◆任何乘以 “1” 的運算數都可以被簡化成非零運算數。
◆任何乘以 “0” 的運算數都可以被簡化成零。
不止這些。因此我們引入了一個在求值前執行的步驟，叫做 simplify()，使用它執行這些具體的簡化工作：
清單 11. 計算器（src/calc.scala）
- def simplify(e : Expr) : Expr =
- {
- e match {
- // Double negation returns the original value
- case UnaryOp("-", UnaryOp("-", x)) => x
- // Positive returns the original value
- case UnaryOp("+", x) => x
- // Multiplying x by 1 returns the original value
- case BinaryOp("*", x, Number(1)) => x
- // Multiplying 1 by x returns the original value
- case BinaryOp("*", Number(1), x) => x
- // Multiplying x by 0 returns zero
- case BinaryOp("*", x, Number(0)) => Number(0)
- // Multiplying 0 by x returns zero
- case BinaryOp("*", Number(0), x) => Number(0)
- // Dividing x by 1 returns the original value
- case BinaryOp("/", x, Number(1)) => x
- // Adding x to 0 returns the original value
- case BinaryOp("+", x, Number(0)) => x
- // Adding 0 to x returns the original value
- case BinaryOp("+", Number(0), x) => x
- // Anything else cannot (yet) be simplified
- case _ => e
- }
- }
還是要注意如何使用模式匹配的常量匹配和變量綁定特性，從而使得編寫這些表達式可以易如反掌。對 evaluate() 惟一一個更改的地方就是包含了在求值前先簡化的調用：
清單 12. 計算器（src/calc.scala）
- def evaluate(e : Expr) : Double =
- {
- simplify(e) match {
- case Number(x) => x
- case UnaryOp("-", x) => -(evaluate(x))
- case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
- case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
- case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
- case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
- }
- }
還可以再進一步簡化；注意一下：它是如何實現只簡化樹的***層的？如果我們有一個包含 BinaryOp("*", Number(0), Number(5)) 和 Number(5) 的 BinaryOp 的話，那么內部的 BinaryOp 就可以被簡化成 Number(0)，但外部的 BinaryOp 也會如此，這是因為此時外部 BinaryOp 的其中一個運算數是零。
我突然犯了作家的職業病了，所以我想將它留予讀者來定義。其實是想增加點趣味性罷了。如果讀者愿意將他們的實現發給我的話，我將會把它放在下一篇文章的代碼分析中。將會有兩個測試單元來測試這種情況，并會立刻失敗。您的任務（如果您選擇接受它的話）是使這些測試 — 以及其他任何測試，只要該測試采取了任意程度的 BinaryOp 和 UnaryOp 嵌套 — 通過。
結束語
顯然我還沒有說完；還有分析的工作要做，但是計算器 AST 已經成形。我們無需作出大的變動就可以添加其他的運算，運行 AST 也無需大量的代碼（按照 Gang of Four 的 Visitor 模式），而且我們已經有了一些執行計算本身的工作代碼（如果客戶機愿意為我們構建用于求值的代碼的話）。
更重要的是，您已經看到了 case 類是如何與模式匹配合作，使得創建 AST 并對其求值變得輕而易舉。這是 Scala 代碼（以及大多數函數性語言）很常用的設計，而且如果您準備認真地研究這個環境的話，這是您應當掌握的內容之一。
【相關閱讀】
