表达式问题
模块化和可扩展性是开发复杂软件系统的重要基础。而表达式问题（Expression Problem）则是检验编程语言对模块化和可扩展性支持程度的根本问题。表达式问题要求在不修改和重复既有代码、保障类型安全、分离编译和模块化类型检查的前提下同时扩展数据结构及其操作。传统的面向对象和函数式编程范式仅支持单一维度的扩展性。
我们将以皮亚诺（Peano）数及其扩展为例贯穿本文。一开始只支持零（Zero）和后继（Succ）来构造自然数和将皮亚诺表示转换为数字表示的求值操作（eval）。例如eval作用在Succ(Zero)上的结果是1。以下的Scala代码分别用面向对象和函数式实现了皮亚诺数：
//面向对象式
trait Tm { def eval: Int }
object Zero extends Tm {
def eval = 0
}
class Succ(t: Tm) extends Tm {
def eval = t.eval + 1
}
//函数式
sealed trait Tm
case object Zero extends Tm
case class Succ(t: Tm) extends Tm
def eval(t: Tm): Int = t match {
case Zero => 0
case Succ(t1) => eval(t1) + 1
}
面向对象式是操作优先，先以接口描述数据结构所支持的操作，再用类实现接口来定义数据结构。在面向对象式中，添加数据结构易而添加新的操作难。添加数据结构仅需定义新的子类比如前驱（Pred）：
class Pred(t: Tm) extends Tm {
def eval = t.eval - 1
}
而添加新的操作则需修改接口及其所有子类。
相反，函数式是数据结构优先，先以代数数据类型来定义数据结构，再用模式匹配定义操作。在函数式中，添加操作易而添加新的数据结构难。添加操作仅需定义一个新的函数比如打印（print）：
def print(t: Tm): String = t match {
case Zero => "Zero"
case Succ(t1) => "(Succ " + print(t1) + ")"
}
而添加数据结构则需修改代数数据类型定义以及给已有函数增加一条新的模式匹配语句。
访问者模式
那么如何在面向对象语言中实现操作扩展呢？这就需要借助访问者设计模式（Visitor pattern）了。访问者模式将操作从类层次结构中分离出来从而允许添加新的操作而不修改既有的类层次结构，如下所示：
//类层次结构
trait Tm {
def accept[A](v: Visitor[A]): A
}
object Zero extends Tm {
def accept[A](v: Visitor[A]) = v.zero
}
class Succ(val t: Tm) extends Tm {
def accept[A](v: Visitor[A]) = v.succ(this)
}
//访问者接口
trait Visitor[A]{
def zero: A
def succ(x: Succ): A
}
访问者接口声明的访问方法（zero和succ）与类层次结构的每个子类（Zero和Succ）一一对应，用来实现类层次结构中的accept方法。类型参数A抽象了访问方法的返回类型。
操作通过实现访问者接口定义：
//求值访问者
class Eval extends Visitor[Int] {
def zero = 0
def succ(x: Succ) = x.t.accept(this) + 1 //递归调用accept方法遍历子表达式
}
重复实现访问者接口即可添加新的操作，比如打印：
//打印访问者
class Print extends Visitor[String]{
def zero = "Zero"
def succ(x: Succ) = "(Succ " + x.t.accept(this) + ")"
}
然而，传统的访问者模式只是转换了扩展维度并没有解决表达式问题：当我们想添加一个新的子类时，访问者接口并没有对应的访问方法来实现其accept方法。因此，需要修改访问者接口及已有的访问者。此外，访问者模式引入了样板代码（boilerplate code），使用起来较为繁琐。为解决上述缺陷，本文将分别介绍基于Java和Scala两种语言的可扩展访问者模式元编程框架EVF1和Castor2。
第一部分：EVF1
一种基于Java的可扩展访问者模式
让访问者模式可扩展的关键在于如何解耦访问者接口和类层次结构。用可扩展访问者模式定义的皮亚诺数访问者接口如下：
interface Visitor<Tm,A> {
A Zero();
A Succ(Tm t);
A visitTm(Tm t);
}
通过新增类型参数Tm来抽象数据结构类型以及从Tm转换到返回值类型A的方法visitTm来解耦访问者接口和类层次结构。求值访问者的定义如下：
interface Eval<Tm> extends Visitor<Tm,Integer> {
default Integer Zero() {
return 0;
}
default Integer Succ(Tm t) {
return visitTm(t) + 1; //递归调用visitTm方法遍历子表达式
}
}
在定义具体的访问者时，Tm保持抽象并通过递归调用visitTm方法实现对子表达式的遍历。这里运用Java 8引入的default methods使得访问者不仅可以扩展还能利用接口多重继承来组合访问者。
扩展
现在，前驱可以模块化地定义了：
//扩展访问者接口
interface ExtVisitor<Tm,A> extends Visitor<Tm,A> {
A Pred(Tm t);
}
//扩展求值访问者
interface ExtEval<Tm> extends ExtVisitor<Tm,Integer>, Eval<Tm> {
default Integer Pred(Tm t) {
return visitTm(t) - 1;
}
}
这些接口定义是为了复用而非使用，因此需要额外定义一些类来实体化这些接口才能创建对象：
//数据结构类型
interface CTm {
<A> A accept(ExtVisitor<CTm, A> v);
}
interface VisitTm<A> extends ExtVisitor<CTm,A> {
default A visitTm(CTm tm) {
return tm.accept(this);
}
}
//工厂模式
class Factory implements ExtVisitor<CTm,CTm>, VisitTm<CTm> {
public CTm Zero() {
return new CTm() {
public <A> A accept(ExtVisitor<CTm, A> v) {
return v.Zero();
}};}
public CTm Succ(CTm t) {
return new CTm() {
public <A> A accept(ExtVisitor<CTm, A> v) {
return v.Succ(t);
}};}
public CTm Pred(CTm t) {
return new CTm() {
public <A> A accept(ExtVisitor<CTm, A> v) {
return v.Pred(t);
}};}
}
class EvalImpl implements ExtEval<CTm>, VisitTm<Integer> {}
至此，我们可以用工厂创建表达式并用访问者对其进行遍历：
Factory f = new Factory();
CTm t = f.Pred(f.Succ(f.Zero()));
t.accept(new EvalImpl()); // 0
用EVF框架简化代码
可以看到可扩展访问者模式使用起来更加繁琐（例如为实例化所定义的类）。所幸，这些样板代码大多可以通过EVF框架自动生成。用户仅需在描述数据结构的接口上加上@Visitor注解，例如：
@Visitor interface Peano<Tm> {
Tm Zero();
Tm Succ(Tm t);
}
在IDE中（如Eclipse）保存后即可生成包括访问者接口，数据结构类型，工厂等在内的源文件:
访问者的实现跟先前所示的手写几乎一致，唯一的区别在于使用了生成的代码：
interface Eval<Tm> extends GPeano<Tm,Integer> { /*同上*/ }
这里GPeano是生成的扩展访问者接口。类似地，扩展访问者的EVF定义如下：
@Visitor interface ExtPeano<Tm> extends Peano<Tm> {
Tm Pred(Tm t);
}
interface ExtEval<Tm> extends GExtPeano<Tm,Integer>, Eval<Tm> { /*同上*/ }
由于EVF生成了包括数据结构、工厂等繁琐代码，用户只需要定义一些类来实体化访问者即可：
class EvalImpl implements ExtEval<CTm>， ExtPeanoVisitor<Integer> {}
ExtPeano<CTm> f = new ExtPeanoFactory();
CTm t = f.Pred(f.Succ(f.Zero()));
new EvalImpl().visitTm(t); // 0
遍历模版
另一大部分样板代码来源于遍历复杂的抽象语法树（AST）。很多情况下我们只关心某些特定节点，而其它大部分节点什么也不做或是只做简单地递归调用。遍历模版预定义了AST遍历，通过继承遍历模版，我们仅需重写（override）所关心的节点。遍历可以粗略地分为：查询（query）和变换（transformation）—— 前者遍历AST计算一个值，后者构造一个新的AST。EVF生成了多种遍历模版供用户灵活选择。
查询
假设我们要为一个复杂的语言定义一些操作:
@visitor interface ComplexLang<Exp> {
Exp Var(String x);
... // 其它许多语言结构省略
}
首先是一个查询操作，收集一个表达式中用到的所有变量名集合。其定义如下：
interface CollectVars<Exp> extends ComplexLangQuery<Exp, Set<String>> {
default Monoid<Set<String>> m() {
return new SetMonoid<>();
}
@Override default Set<String> Var(String x) {
return Collections.singleton(x);
}
}
通过继承生成的ComplexLangQuery模版，我们只需要重写Var访问方法以及提供一个SetMonoid对象作为m方法的实现即可。ComplexLangQuery调用了Monoid接口定义了两个方法empty和join来为各访问方法提供了缺省定义。其中empty表示缺省值，用于实现Var这类不包含子表达式的访问方法而join是一个二元操作符用来结合子表达式的计算结果。这里集合就是幺半群（monoid）的一个实例，其中empty是空集而join是并集操作。其它的幺半群实例包括加、乘、列表等。
变换
接下来是一个变换的例子，将表达式中的某个变量替换成另一个一个表达式的操作定以如下：
interface Subst<Exp> extends ComplexLangTransform<Exp> {
String x(); //变量名
Exp y(); //替换成的表达式
@Override default Exp Var(String z) {
return z.equals(x()) ? y() : alg().Var(z);
}
}
通过继承生成的ComplexLangTransform模版，我们只需要重写Var访问方法ComplexLangTransform模版实现访问方法的方式是对子表达式递归调用访问者并用抽象工厂alg重新构造遍历后的表达式。
EVF的实现
EVF运用Java注解处理器（Java Annotation Processor）在编译期生成一系列源文件。主要用到了javax.annotation.processing和javax.lang.model两个库。前者提供了包括AbstractProcessor在内的注解处理器基础设施，后者用于分析Java AST。EVF的实现约800行代码。
第二部分：Castor2
受限于Java注解处理器和Java语言本身，EVF有如下局限性：
- 不支持对用户代码的直接简化
- 对模式匹配支持不佳
- 仅支持函数式、树结构的访问者
针对这些缺陷，我们在EVF基础之上开发了基于Scala语言的Castor框架。作为一个同时支持函数式和面向对象范式的语言，Scala有着更简洁的语法，原生的模式匹配支持，更强大的类型系统以及更好的元编程支持。
一种基于Scala的可扩展访问者模式
trait Peano {
type TmV <: TmVisit
trait Tm {
def accept(v: TmV): v.OTm
}
case object Zero extends Tm {
def accept(v: TmV) = v.zero
}
case class Succ(t: Tm) extends Tm {
def accept(v: TmV) = v.succ(this)
}
trait TmVisit { _: TmV =>
type OTm
def zero: OTm
def succ: Succ => OTm
def apply(t: Tm) = t.accept(this)
}
trait Eval extends TmVisit { _: TmV =>
type OTm = Int
def zero = 0
def succ = x => this(x.t) + 1
}
}
相较于Java版，Scala版可扩展访问者的编码有几大不同之处：
- 用嵌套的trait来定义，通过mixin-composition实现扩展和组合。
- 不同于Java版从访问者接口角度出发，Scala版从类层次结构角度出发，将
accept方法的参数类型声明为类型成员TmV来实现和特定的访问者接口的解耦。通过将TmV限制为TmVisit的子类型（subtype），我们可以调用TmVisit声明的访问方法来实现Zero和Succ的accept方法。 Zero和Succ前面加上了case关键字来获得Scala原生模式匹配的支持。TmVisit中访问方法的返回值类型也声明为类型成员。这么做的好处是当访问者被继承时，返回值类型不必重复实例化。TmVisit定义了apply语法糖，将x.t.accept(this)简化为this(x.t)。注意到这里可以将this作为参数传给accept的原因是用self-type annotation声明了自身类型是TmV。
扩展
下面的代码同时扩展的数据结构和操作：
trait ExtPeano extends Peano {
type TmV <: TmVisit
case class Pred(t: Tm) extends Tm {
def accept(v: TmV) = v.pred(this)
}
trait TmVisit extends super.TmVisit { _: TmV =>
def pred: Pred => OTm
}
trait Eval extends super.Eval with TmVisit { _: TmV =>
def pred = x => this(x.t) - 1
}
}
ExtPeano中定义了一个新的case类Pred。相应地，我们扩展了访问者接口，声明了pred访问方法。通过covariant refinement将TmV约束为扩展访问者接口的子类型我们得已调用pred来实现Pred的accept方法。可以看到，使用嵌套的trait的一个好处是不必为扩展的访问者起新名字。
类似于Java版本中将interface实体化为class的步骤，Scala版本需要将trait实体化为object，定义如下：
object ExtPeano extends ExtPeano {
type TmV = TmVisit
object eval extends Eval
}
类型成元TmV绑定为TmVisit而eval实体化了访问者Eval。
导入ExtPeano即可构造和求值表达式，例如：
import ExtPeano._
val t = Pred(Succ(Zero))
eval(t) // 0
用Castor框架简化代码
用Castor框架简化后的代码如下：
@family trait Peano {
@adt trait Tm {
case object Zero
case class Succ(t: Tm)
}
@visit(Tm) trait Eval {
type OTm = Int
def zero = 0
def succ = x => this(x.t) + 1
}
}
最外层的trait用@family注解，数据结构使用@adt trait定义，而其case写在trait里面并且不必显示地写出extends语句（类似的语法在最近发布的Scala 3中的enum采纳）。Eval是Tm的访问者上用注解@visit(Tm)表明。可以看到，访问者接口和其它高级的语言特性如带有类型约束的类型成员、self-type annotation等均由Castor隐式地生成，使得Castor容易上手使用。
类似地，扩展的定义如下：
@family trait ExtPeano extends Peano {
@adt trait Tm extends super.Tm {
case class Pred(t: Tm)
}
@visit(Tm) trait Eval extends super.Eval {
def pred = x => this(x.t) - 1
}
@visit(Tm) trait Print {
type OTm = String
def zero = "Zero"
def succ = x => "(Succ " + this(x.t) + ")"
def pred = x => "(Pred " + this(x.t) + ")"
}
}
Castor为带有@family注解的trait自动生成了伴生对象，可以直接导入用户代码。
GADT和模式匹配
假设我们想进一步扩展我们的例子让它支持布尔值和if表达式:
case object TmTrue
case object TmFalse
case class TmIf(t1: Tm, t2: Tm, t3: Tm)
合法的if表达式要求t1为布尔类型且t2和t3类型相同。类似TmIf(TmZero,TmTrue,TmFalse)这样的非法表达式一般通过定义类型检查访问者来剔除。
GADT
一种更好的做法是用GADT（Generalized Algebraic Data Types，泛化代数数据类型）嵌入类型约束，通过宿主语言的类型系统来阻止非法表达式的构建。这一点特别适用于实现EDSL（Embedded Domain-Speicific Languages，嵌入式领域特地语言）。用GADT定义的数据结构如下（注：可以模块化地定义两个子语言再合并，为节省篇幅将其定义在一起）：
@adt trait Tm[A] {
case object Zero extends Tm[Int]
case class Succ(t: Tm[Int]) extends Tm[Int]
case class Pred(t: Tm[Int]) extends Tm[Int]
case object TmTrue extends Tm[Boolean]
case object TmFalse extends Tm[Boolean]
case class TmIf[A](t1: Tm[Boolean], t2: Tm[A], t3: Tm[A]) extends Tm[A]
}
Tm的定义引入了类型参数A。通过显示的extends语句对A不同的实例化来区隔出表达式的类型。可以看到TmIf的定义约束了合法的if表达式的形式，即t1 是Tm[Boolean]且t2和t3类型一致为Tm[A]。现在TmIf(Zero,TmTrue,TmFalse)将不被类型系统接受因为TmZero的类型是Tm[Int]。
模块化的大步（big-step）语义
布尔值和if表达式的扩展带来的第二个问题是如何定义大步语义求值访问者。已有的Eval定义需要修改否则无法复用：
@visit(Tm) trait Eval {
type OTm = Int | Boolean
def zero = 0
def succ = x => this(x.t) match {
case v: Int => v + 1
case _ => throw new RuntimeException
}
...
}
访问者的返回值类型修改为联合类型（union types）Int | Boolean来表示返回值类型既可能是Int也可能是Boolean。此外，子表达式的遍历结果需要额外的处理来识别出期待的返回值类型。
这种方式定义的大步语义是不模块化的，因为每当有新的表达式类型引入时（比如浮点数）时，既有的求值访问者需要修改返回类型否则不兼容。
而GADT使得大步语义访问者的定义变得简洁且模块化：
@visit(Tm) trait Eval {
type OTm[A] = A
def zero = 0
def succ = x => this(x.t) + 1
def pred = x => this(x.t) - 1
def tmTrue = true
def tmFalse = false
def tmIf[A] = x => if (this(x.t1)) this(x.t2) else this(x.t3)
}
返回值类型与表达式携带的类型参数一致，即类型为Tm[Int]的表达式将返回Int而Tm[Boolean]的表达式返回Boolean。子表达式的遍历不需要做额外处理且既有的访问者不受新引入的表达式类型影响。
模块化的小步（small-step）语义
Castor的优势进一步地反映在小步语义的定义上：
@default(Tm) trait Eval1 {
type OTm[A] = Tm[A]
def tm[A] = x => throw NoRuleApplies
override def tmIf[A] = {
case TmIf(TmTrue,t2,_) => t2
case TmIf(TmFalse,_,t3) => t3
case TmIf(t1,t2,t3) => TmIf(this(t1),t2,t3)
}
...
}
小步语义逐步地改写表达式直到其不能再被改写，因此访问者返回类型就是表达式本身。一个表达式的小步语义可能有多条规则，比如if表达式，若t1为真则改写为t2，若t1为假则改写为t3，否则继续改写t1。而访问方法仅揭露当前表达式最外层的形式，要识别出子表达式的形式一般需要定义额外的访问者写起来比较繁琐。所幸Castor使用了case class定义层次结构，可以用Scala原生的模式匹配来识别子表达式。tmIf的定义用三条case语句分别对应上述三种情形。注意到Eval1的注解是default，表示它使用了带有缺省实现的模版。其缺省定义抛出一个异常，表示表达式要么已经是个值了要么是非法的。
除了GADT和模式匹配，Castor还提升了一些EVF所欠缺的表达能力，比如图结构，命令式访问者等。受限于篇幅就不一一展开说明了。
Castor的实现
Castor使用了Scalameta元编程库来分析、变换和生成Scala程序。不同于Java，Scala提供了一种更简洁、安全的操纵Scala语法树的方式称为quasiquotes。Quasiquotes既可用于构建也可用于匹配AST。例如， q"trait Tm"等价于如下AST定义：
Defn.Trait(Nil, Type.Name("Tm"),
Nil, Ctor.Primary(Nil, Ctor.Ref.Name("this"), Nil),
Template(Nil, Nil, Term.Param(Nil, Name.Anonymous(), None, None), None))
相较于EVF，Castor注解处理器的代码行仅是其1/4。
案例分析
我们分别用EVF和Castor重构了《Types and Programming Languages》这一编程语言经典书籍中的解释器实现。该书逐步新的语言特性，从一开始的数值、布尔慢慢扩展无类型lambda演算、简单类型lambda演算、let表达式、record等。其解释器的实现是将原始语言特性的实现复制黏贴到新的扩展语言实现中，因而是不模块化的。我们将语言特性分离出来，使其能够模块化的扩展和复用，如下图所示：
灰色方框代表10个原始语言，白色方框代表抽取出来的语言特性，箭头代表依赖。可以看到这些特性在这些语言中被广泛复用。
下面的表格比较这10个解释器分别用EVF、Castor以及Scala的实现：
可以看到代码行数显著下载，同为Scala语言的实现，Castor实现的代码量不到其一半。受限于Java语言，EVF实现比Castor多用了400多行，但依然比非模块化的Scala代码少1000多行。
当然模块化带来了间接性，对性能造成影响。为了评估这个影响我们比较了同为Scala语言的两个实现，用随机生成10000个表达式计算10次求值的平均时间得出下图：
Castor比Scala慢1.35x (arith)至3.92x (fullsub)，越复杂的语言性能下降得越多，但还在可接受的范围内。
结语
表达式问题是检验模块化和可扩展性的根本问题。可扩展访问者模式给出了表达式问题的一种解决方案。可扩展访问者模式的复杂性在很大程度上可以通过元编程自动生成代码来消除。当然元编程不是万灵丹，可能会造成调试的困难并且要求用户对生成的代码有所了解。
- Weixin Zhang and Bruno C. d. S. Oliveira . EVF: An Extensible and Expressive Visitor Framework for Programming Language Reuse
In 31st European Conference on Object-Oriented Programming (ECOOP), 2017.↩ - Weixin Zhang and Bruno C. d. S. Oliveira. Castor: Programming with extensible generative visitors , In Science of Computer Programming, 2020↩