Scala构建计算器，第1 一部分(代码学习第8天)

Scala构建计算器，第1 部分(代码学习第8天)
特定于领域的语言

可能您无法（或没有时间）承受来自于您的项目经理给您的压力，那么让我直接了当地说吧：特定于领域的语言无非就是尝试（再一次）将一个应用程序的功能放在它该属于的地方 — 用户的手中。

通过定义一个新的用户可以理解并直接使用的文本语言，程序员成功摆脱了不停地处理 UI 请求和功能增强的麻烦，而且这样还可以使用户能够自己创建脚本以及其他的工具，用来给他们所构建的应用程序创建新的行为。虽然这个例子可能有点冒险（或许会惹来几封抱怨的电子邮件），但我还是要说，DSL 的最成功的例子就是 Microsoft? Office Excel “语言”，用于表达电子表格单元格的各种计算和内容。甚至有些人认为 SQL 本身就是 DSL，但这次是一个旨在与关系数据库相交互的语言（想象一下如果程序员要通过传统 API read()/write() 调用来从 Oracle 中获取数据的话，那将会是什么样子）。

这里构建的 DSL 是一个简单的计算器语言，用于获取并计算数学表达式。其实，这里的目标是要创建一个小型语言，这个语言能够允许用户来输入相对简单的代数表达式，然后这个代码来为它求值并产生结果。为了尽量简单明了，该语言不会支持很多功能完善的计算器所支持的特性，但我不也不想把它的用途限定在教学上 — 该语言一定要具备足够的可扩展性，以使读者无需彻底改变该语言就能够将它用作一个功能更强大的语言的核心。这意味着该语言一定要可以被轻易地扩展，并要尽量保持封装性，用起来不会有任何的阻碍。

关于 DSL 的更多信息DSL 这个主题的涉及面很广；它的丰富性和广泛性不是本文的一个段落可以描述得了的。想要了解更多 DSL 信息的读者可以查阅本文末尾列出的 Martin Fowler 的 “正在进展中的图书”；特别要注意关于 “内部” 和 “外部” DSL 之间的讨论。Scala 以其灵活的语法和强大的功能而成为最强有力的构建内部和外部 DSL 的语言。
.换句话说，（最终的）目标是要允许客户机编写代码，以达到如下的目的：


清单 1. 计算器 DSL：目标

// This is Java using the CalculatorString 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。

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 PersonCompiled 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 AppProcessing 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 的任务上。

计算器 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 类合作。

但这并不是说所有的封装都没有用了或过时了。事实上恰好相反：它试图说服我们在对象领域所熟悉的方法之外，还有很多其他的设计方法也很奏效。不要忘了 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 代码（以及大多数函数性语言）很常用的设计，而且如果您准备认真地研究这个环境的话，这是您应当掌握的内容之一。

查看更多 下一篇