Scalaによる Expression Problemの解決 (Visitor編)

参考：ジェネリクスによるVisitorパターン拡張の考察

Scalaは元々は、複数の関連しあったクラス群をうまく再利用可能なことにすることも視野にいれていただけあって、こういうのを(オブジェクト指向モデルの中で)簡単に取り扱えます。

trait VisitorsBase {self =>
  trait Node {
    def accept(v: V)
  }
  case class Add(l: Node, r: Node) extends Node {
    def accept(v: V) {
      v.visit(this)
    }
  }
  case class Sub(l: Node, r: Node) extends Node {
    def accept(v: V) {
      v.visit(this)
    }
  }
  case class Value(value: Int) extends Node {
    def accept(v: V) {
      v.visit(this)
    }
  }
  type V <: Visitor
  trait Visitor {self: V =>
    def visit(node: Add) { 
      println("Add!") 
      node.l.accept(this)
      node.r.accept(this)
    }
    def visit(node: Sub) {
      println("Sub!") 
      node.l.accept(this)
      node.r.accept(this)
    }
    def visit(node: Value) {
      println("Value: " + node.value) 
    }
  }
}

object VisitorsPlus extends VisitorsBase {
  type V = Visitor
  case class Mul(l: Node, r: Node) extends Node {
    def accept(v: V) {
      v.visit(this)
    }
  }
  case class Div(l: Node, r: Node) extends Node {
    def accept(v: V) {
      v.visit(this)
    }
  }
  class Visitor extends super.Visitor {
    def visit(node: Mul) {
      println("Mul") 
      node.l.accept(this)
      node.r.accept(this)
    }
    def visit(node: Div) {
      println("Div") 
      node.l.accept(this)
      node.r.accept(this)
    }
  }
}

object VisitorMain {
  import VisitorsPlus._
  def main(args: Array[String]) {
    val v = new Visitor
    Add(Value(1), Value(2)).accept(v)
    Sub(Value(1), Value(2)).accept(v)
    Mul(Value(1), Value(2)).accept(v)
    Div(Value(1), Value(2)).accept(v)
  }
}

VisitorBaseトレイトが拡張前の「Visitor + 構文木群」、VisitorPlusが、VisitorBaseにMulとDivという二つのノードを足したものです。ここでは、同じファイルにしてしまっていますが、VisitorBaseとVisitorPlusはもちろん別のコンパイル単位にあっても構いません。ともあれ、

• Visitorに対してノードへの処理を追加
• 既存構文木の階層に対して、新しいノードの追加

の２方向の変更を、VisitorBaseへの変更無しに、素直に達成できていることがわかります。

コードの詳しい説明は基本はしょりますが、self-type annotationとabstract type memberがScalaによるExpression Problemの解決法の基本ポイントです。他にもObserver(SubjectとObserverの組)、Interpreterパターンとか多くのパターンにおいて応用が利きます。

…Scalaの場合、そもそもVisitor使うくらいならパターンマッチでやってしまう気がしますが、それは言わない方向で。