Interpreter模式和Visitor模式

本文解决我的某个未解之谜：
http://cloverprince.iteye.com/blog/336641

说一个笑话：请问，Java语言的使用者看到了如下的代码会怎么想：

int calculate(int a, int b, char op)
{
 int c;
 switch(op) {
 case '+':
   c=a+b; break;
 case '-':
   c=a-b; break;
 case '*':
   c=a*b; break;
 case '/':
   if (b==0) {
     errno=1;
     return -1;
   } else {
     c=a/b; break;
   }
 }
 return c;
}

有的人说：阿，多么难看的代码阿，switch-case语句根本无法扩展。于是，用面向对象的方法论写了如下的代码：

abstract class Calculator {
 int calculate(int a, int b);
}

class Adder extends Calculator {
 int calculate(int a, int b) { return a+b; }
}

class Subtracter extends Calculator {
 int calculate(int a, int b) { return a-b; }
}

class Multiplier extends Calculator  {
 int calculate(int a, int b) { return a*b; }
}

class Divider extends Calculator  {
 int calculate(int a, int b) { if(b==0) throw new
DivideByZeroException(); else return a+b; }
}

其实，四人帮也是这样解决问题的。这个设计模式叫做“Interpreter”。

一个算数表达式求值器，如果用Interpreter模式实现，那么，算式中每个元素，包括运算符和常数，都可以继承公共的基类，拥有共同“求值”方法。

public abstract class Expression {
	public abstract double evaluate();
}

常数是一个表达式，所以常数继承Expr类。显然，常数的值是它本身。

class Constant extends Expression {
	private double num;
	public Constant(double num) { this.num = num; }
	public @Override double evaluate() { return num; }
}

我们再增加一个加法运算符。

class AddOperator extends Expression {
	private Expression lhs, rhs;
	public AddOperator(Expression lhs, Expression rhs) {
		this.lhs = lhs;
		this.rhs = rhs;
	}
	public @Override double evaluate() {
		return lhs.evaluate() + rhs.evaluate(); 
	}
}

而对于用户来说，只需要知道，任何表达式都拥有evaluate()方法，就可以了。

Expression expr = new AddOperator (
    new Constant(5.0),
    new AddOperator(
        new Constant(3.0),
        new Constant(2.0)
    ));

expr.evaluate(); // 返回 10

以上代码计算了5+(3+2)的值。

原始的四人帮的Interpreter设计模式中，evalutate方法额外取一个Context参数，可以是表达式的上下文。这样，表达式里面就可以包含由上下文决定的“变量”了。

Interpreter模式的优点是，便于添加新的数据类型。如上，如果我要增加一个“减法运算符”，我只需要增加如下代码：

class SubtractOperator extends Expression {
	private Expression lhs, rhs;
	public SubtractOperator(Expression lhs, Expression rhs) {
		this.lhs = lhs;
		this.rhs = rhs;
	}
	public @Override double evaluate() {
		return lhs.evaluate() - rhs.evaluate(); 
	}
}

注意：SubtractOperator类可以放在新的编译单元（比如SubtractOperator.java）中，原有的代码完全不需要改变。

==================

我们再来看看另一个问题

我现在有一些抽象几何对象，比如“长方形”，“圆”。目前可以计算“周长”和“面积”。显然，用Java语言可以如下实现。

我们先定义公共的抽象基类（当然，接口也可以）：

public abstract class Shape {
	public abstract double getPerimeter();

	public abstract double getArea();
}

长方形和圆分别继承这个基类：

class Rectangle extends Shape {
	private Point topLeft;
	private Point bottomRight;

	public Rectangle(Point topLeft, Point bottomRight) {
		this.topLeft = topLeft;
		this.bottomRight = bottomRight;
	}

	@Override
	public double getArea() {
		return (bottomRight.x - topLeft.x) * (bottomRight.y - topLeft.y);
	}

	@Override
	public double getPerimeter() {
		return 2.0 * ((bottomRight.x - topLeft.x) + (bottomRight.y - topLeft.y));
	}
}

class Circle extends Shape {
	private Point center;
	private double radius;

	public Circle(Point center, double radius) {
		this.center = center;
		this.radius = radius;
	}

	@Override
	public double getArea() {
		return Math.PI * radius * radius;
	}

	@Override
	public double getPerimeter() {
		return 2.0 * Math.PI * radius;
	}
}

这样，我们用Shape类的getArea()和getPerimeter()方法就可以计算出它们的面积和周长，而不用知道具体的几何对象是什么。

这种方法可以很容易地扩展出第三种形状，也就是数据类型。

class Triangle extends Shape {
	private Point p1, p2, p3;

	public Triangle(Point p1, Point p2, Point p3) {
		this.p1 = p1;
		this.p2 = p2;
		this.p3 = p3;
	}

	@Override
	public double getArea() {
		return 0.5 * Math.abs(p1.x * p2.y - p2.x * p1.y + p2.x * p3.y - p3.x
				* p2.y + p3.x * p1.y - p1.x * p3.y);
	}

	@Override
	public double getPerimeter() {
		return Math.hypot(p1.x - p2.x, p1.y - p2.y)
				+ Math.hypot(p2.x - p3.x, p2.y - p3.y)
				+ Math.hypot(p3.x - p1.x, p3.y - p1.y);
	}
}

注意：这个新的Triangle类可以放在一个新的编译单元中，而原有的代码完全不需要改变。

----------------

什么时候，Interpreter模式不再这么优秀？

当我要扩展新的操作的时候，就不太好了。

比如，如果我要对所有的形状增加计算“重心”的操作。于是，我修改了Shape类：

public abstract class Shape {
	public abstract double getPerimeter();

	public abstract double getArea();
	
	public abstract Point getCenter();
}

然后，每个具体的几何对象都需要增加新的代码：

class Rectangle extends Shape {
	/* more methods omitted */

	@Override
	public Point getCenter() {
		return new Point((topLeft.x + bottomRight.x) / 2.0,
				(topLeft.y + bottomRight.y) / 2.0);
	}
}

class Circle extends Shape {
	/* more methods omitted */

	@Override
	public Point getCenter() {
		return center;
	}
}

class Triangle extends Shape {
	/* more methods omitted */

	@Override
	public Point getCenter() {
		return new Point((p1.x + p2.x + p3.x) / 3, (p1.y + p2.y + p3.y) / 3);
	}
}

当然，我可以继续扩展。当对象复杂到如下程度的时候：

class Circle extends Shape {
   Point getCenter() {
      /* .....  */
   }
   public @Override Rect getBound() {
      /* .....  */
   }
   public @Override void draw(CDC dc) {
      /* .....  */
   }
   public @Override void save(OutputStream ost) {
      /* .....  */
   }
   public @Override void onMouseLeftButtonClicked() {
      /* .....  */
   }
   public @Override void onMouseMiddleButtonClicked() {
      /* .....  */
   }
   public @Override void onMouseRightButtonClicked() {
      /* .....  */
   }
   public @Override Response request(Request req) {
      /* .....  */
   }
   public @Override void aMethod() {
      /* .....  */
   }
   public @Override void anotherMethod() {
      /* .....  */
   }
   public @Override void yetAnotherMethod() {
      /* .....  */
   }
   public @Override void yetYetAnotherMethod() {
      /* .....  */
   }
   public @Override void moreMethodHere() {
      /* .....  */
   }
   public @Override void yeahTheLastmethod() {
      /* .....  */
   }
}

也许就是考虑改变设计模式的时候了吧。

===================

引入Visitor模式。

Visitor模式中，有一个Visitor对象。这个对象可以处理所有种类的Shape。

public class ShapeVisitor {
	public void visit(Object obj) {
		if(obj instanceof Rectangle) {
			/* do something */
		} else if(obj instanceof Circle) {
			/* do something */
		} else if(obj instanceof Triangle) {
			/* do something */
		}
	}
}

而在当初C++不具有RTTI(Run-time Type Information)的时候，我们不能像java一样用instanceof判断对象和类的关系。那时候，Visitor模式是这样实现的：

Shape类需要提供一个accept方法。

abstract class Shape {
	public abstract accept(ShapeVisitor visitor);
}

而Visitor如下设计：

public abstract class ShapeVisitor {
	public void visit(Shape shape) {
		shape.accept(this);
	}
	
	public abstract void visitRectangle(Rectangle rect);
	
	public abstract void visitCircle(Circle circle);
	
	public abstract void visitTriangle(Triangle triangle);
}

正是因为语言本身没有RTTI，我们不能在运行时知道对象的具体所属的类，所以我们需要让对象自己告诉visitor自己是什么类。

class Rectangle extends Shape {
	public Point topLeft;    // 改为了public。也可以用getter和setter
	public Point bottomRight;

	public Rectangle(Point topLeft, Point bottomRight) {
		this.topLeft = topLeft;
		this.bottomRight = bottomRight;
	}
	
	@Override
	public void accept(ShapeVisitor visitor) {
		visitor.visitRectangle(this);
	}
}

Rectangle通过调用visitor.visitRectangle(this)，告诉ShapeVisitor，自己是Rectangle。注意到，Rectangle现在不需要计算自己的周长/面积。

同样，Circle和Triangle也增加accept方法，去除具体的计算。

class Circle extends Shape {
	/* more methods omitted */
	
	@Override
	public void accept(ShapeVisitor visitor) {
		visitor.visitCircle(this);
	}
}

class Triangle extends Shape {
	/* more methods omitted */

	@Override
	public void accept(ShapeVisitor visitor) {
		visitor.visitTriangle(this);
	}
}

具体的运算，我们可以通过继承ShapeVisitor类来实现。

class AreaVisitor extends ShapeVisitor {

	private double result; // 线程不安全

	public double calculateArea(Shape shape) {
		visit(shape);
		return result;
	}

	@Override
	public void visitCircle(Circle circle) {
		result = Math.PI * circle.radius * circle.radius;
	}

	@Override
	public void visitRectangle(Rectangle rect) {
		result = (rect.bottomRight.x - rect.topLeft.x)
				* (rect.bottomRight.y - rect.topLeft.y);
	}

	@Override
	public void visitTriangle(Triangle tri) {
		result = 0.5 * Math.abs(tri.p1.x * tri.p2.y - tri.p2.x
				* tri.p1.y + tri.p2.x * tri.p3.y - tri.p3.x
				* tri.p2.y + tri.p3.x * tri.p1.y - tri.p1.x
				* tri.p3.y);
	}

}

当我们需要扩展出一个新的运算的时候，只需要一个新的ShapeVisitor子类即可。

class CenterVisitor extends ShapeVisitor {

	private Point result;

	public Point calculateArea(Shape shape) {
		visit(shape);
		return result;
	}

	@Override
	public void visitCircle(Circle circle) {
		result = circle.center;
	}

	@Override
	public void visitRectangle(Rectangle rect) {
		result = new Point((rect.bottomRight.x + rect.topLeft.x)/2.0,
				(rect.bottomRight.y + rect.topLeft.y)/2.0);
	}

	@Override
	public void visitTriangle(Triangle tri) {
		result = new Point((tri.p1.x + tri.p2.x + tri.p3.x)/3.0,
				(tri.p1.y + tri.p2.y + tri.p3.y)/3.0);
	}

}

注意：这个新的CenterVisitor可以在新的编译单元中实现，而原有的Shape和Visitor完全不需要改变。

-----------------------

什么时候Visitor不再方便？

当需要增加一种数据类型的时候，比如增加Ellipse，那么所有的Visitor都需要修改。

==========================

总结：

当需要在数据类型的方向上扩展（如：有了Rectangle，想增加Circle,Triangle,Ellipse等），而数据操作基本上不需要改变（如：只有面积和周长，不再增加）的时候，Interpreter模式更适合。

当需要在操作方向上扩展（如：可以计算面积了，还想增加周长/重心/绘图功能/鼠标响应/XML输出），但数据类型基本上不需要改变（如：只有Rectangle和Circle，不再增加）的时候，Visitor模式更适合。


开放问题：

如果两个方向都需要扩展的时候，就引发了Expression Problem。这其实是个长期以来困扰人们的问题。


参考文献： The Expression Problem in Scala.  Report by T.N. Esben & al., Aarhus University, May 31, 2005.
下载页面：http://www.scala-lang.org/node/143
链接：http://www.scala-lang.org/docu/files/TheExpressionProblem.pdf