Scala 筆記15 - The expression problem

The expression problem

如果要做一個compiler，通常會有以下的class hierarchy：一個base class Expr:

trait Expr {
  def isNumber: Boolean
  def isSum: Boolean
  def numValue: Int
  def leftOp: Expr
  def rightOp: Expr
}

兩個subclasses:

class Number(n: Int) extends Expr {
  def isNumber: Boolean = true  def isSum: Boolean = false  def numValue: Int = n
  def leftOp: Expr = throw new Error(”Number.leftOp”)
  def rightOp: Expr = throw new Error(”Number.rightOp”)
}

class Sum(e1: Expr, e2: Expr) extends Expr {
  def isNumber: Boolean = false  def isSum: Boolean = true  def numValue: Int = throw new Error(”Sum.numValue”)
  def leftOp: Expr = e1
  def rightOp: Expr = e2
}

再來是一個evaluation function：

def eval(e: Expr): Int = {
  if (e.isNumber) e.numValue
  else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
  else throw new Error("Unknown expression " + e)
}

OK，如果要再加新的Expr的subclass：

class Prod(e1: Expr, e2: Expr) extends Expr // e1 * e2class Var(x: String) extends Expr // Variable ‘x’

我們需要定義多少個methods來讓這兩個subclasses加入體系？

• 1. Expr/Number/Sum要加入 isProd 和 isVar, total = 3*2 = 6 (type classifiers)
• 2. Prod/Var要implement Expr trait，總共7*2 = 14
• 3, Var需要一個name method，而這個必須定義在Expr trait裡面，因為我們的eval function只接受Expr當作input參數（我們先不討論可以type casting）。total = 5 (accessors)

所以至少要implement 25個methods。

所以這邊可以看到的是，如果要加入一個新的subclass X，所有其他的class都必須要加入 isX這個判別type用的method，而如果X必須定義新的method，所有的其他class也必須定義。這在現實生活中會遇到很多問題，特別是可能我們沒有access to base traits以及other classes。

Solution1 : 改造eval，使用runtime type check

def eval(e: Expr): Int =
  if (e.isInstanceOf[Number])
    e.asInstanceOf[Number].numValue
  else if (e.isInstanceOf[Sum])
    eval(e.asInstanceOf[Sum].leftOp) +
      eval(e.asInstanceOf[Sum].rightOp)
  else throw new Error(”Unknown expression ” + e)

Scala並不鼓勵這個方式，因為這個其實是low-level thinking，不過這其實有解決了問題，我們只要修改eval增加新的isInstanceOf判斷式就好。

Solution2 : 把eval定義在Expr中，每個subclass負責自己怎麼被eval

這個稱作object decomposition，就是把某件事情的responsibility分給各自的class去定義，外人不管。

所以如果要加入新的subclass Prod和Var，並不會改動到Expr以及其subclass的定義，這解決了問題。

不過如果我們要在Expr加入一個新的method show，OOP的先天設計無法避免的要修改每一個subclass definition來加入新的method。

另外一個問題是，這個show method如果需要refer到其他Expr instance（例如以下：）

這個就不能在各自subclass中的show method完成，因為欠缺global view。

Solution3 : Pattern Matching

下回分解。