Visitor Pattern in Scala

There is a good survey of that question in the paper Matching Objects with Patterns by Burak Emir, Martin Odersky, and John Williams


Recently (2019) the Visitor Pattern got quite some attention in the Scala World.

See here for example 2 Blogs to the subject:

https://meta.plasm.us/posts/2019/09/23/scala-and-the-visitor-pattern/ by Travis Brown

https://medium.com/@supermanue/gof-design-patterns-in-scala-visitor-f3b8c91e0488 by Manuel Rodríguez


Yes, you should probably start off with pattern matching instead of the visitor pattern. See this interview with Martin Odersky (my emphasis):

So the right tool for the job really depends on which direction you want to extend. If you want to extend with new data, you pick the classical object-oriented approach with virtual methods. If you want to keep the data fixed and extend with new operations, then patterns are a much better fit. There's actually a design pattern—not to be confused with pattern matching—in object-oriented programming called the visitor pattern, which can represent some of the things we do with pattern matching in an object-oriented way, based on virtual method dispatch. But in practical use the visitor pattern is very bulky. You can't do many of the things that are very easy with pattern matching. You end up with very heavy visitors. And it also turns out that with modern VM technology it's way more innefficient than pattern matching. For both of these reasons, I think there's a definite role for pattern matching.

EDIT: I think this requires a bit of a better explanation, and an example. The visitor pattern is often used to visit every node in a tree or similar, for instance an Abstract Syntax Tree (AST). Using an example from the excellent Scalariform. Scalariform formats scala code by parsing Scala and then traversing the AST, writing it out. One of the provided methods takes the AST and creates a simple list of all of the tokens in order. The method used for this is:

private def immediateAstNodes(n: Any): List[AstNode] = n match {
  case a: AstNode                ⇒ List(a)
  case t: Token                  ⇒ Nil
  case Some(x)                   ⇒ immediateAstNodes(x)
  case xs @ (_ :: _)             ⇒ xs flatMap { immediateAstNodes(_) }
  case Left(x)                   ⇒ immediateAstNodes(x)
  case Right(x)                  ⇒ immediateAstNodes(x)
  case (l, r)                    ⇒ immediateAstNodes(l) ++ immediateAstNodes(r)
  case (x, y, z)                 ⇒ immediateAstNodes(x) ++ immediateAstNodes(y) ++ immediateAstNodes(z)
  case true | false | Nil | None ⇒ Nil
}

def immediateChildren: List[AstNode] = productIterator.toList flatten immediateAstNodes

This is a job which could well be done by a visitor pattern in Java, but much more concisely done by pattern matching in Scala. In Scalastyle (Checkstyle for Scala), we use a modified form of this method, but with a subtle change. We need to traverse the tree, but each check only cares about certain nodes. For instance, for the EqualsHashCodeChecker, it only cares about equals and hashCode methods defined. We use the following method:

protected[scalariform] def visit[T](ast: Any, visitfn: (Any) => List[T]): List[T] = ast match {
  case a: AstNode                => visitfn(a.immediateChildren)
  case t: Token                  => List()
  case Some(x)                   => visitfn(x)
  case xs @ (_ :: _)             => xs flatMap { visitfn(_) }
  case Left(x)                   => visitfn(x)
  case Right(x)                  => visitfn(x)
  case (l, r)                    => visitfn(l) ::: visitfn(r)
  case (x, y, z)                 => visitfn(x) ::: visitfn(y) ::: visitfn(z)
  case true | false | Nil | None => List()
}

Notice we're recursively calling visitfn(), not visit(). This allows us to reuse this method to traverse the tree without duplicating code. In our EqualsHashCodeChecker, we have:

private def localvisit(ast: Any): ListType = ast match {
  case t: TmplDef     => List(TmplClazz(Some(t.name.getText), Some(t.name.startIndex), localvisit(t.templateBodyOption)))
  case t: FunDefOrDcl => List(FunDefOrDclClazz(method(t), Some(t.nameToken.startIndex), localvisit(t.localDef)))
  case t: Any         => visit(t, localvisit)
}

So the only boilerplate here is the last line in the pattern match. In Java, the above code could well be implemented as a visitor pattern, but in Scala it makes sense to use pattern matching. Note also that the above code does not require a modification to the data structure being traversed, apart from defining unapply(), which happens automatically if you're using case classes.

Tags:

Design Patterns

Scala

Recent Posts