Scala Hosts a Friendly Visitor

GOF tells us that the intent of the Visitor design pattern is to

Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

The focus is on defining new operations, and not on allowing a flexible hierarchy of the elements themselves. In fact, the Consequences section of the Visitor pattern mentions that Visitor makes adding new operations easy and Adding new ConcreteElement classes is hard, since adding every new ConcreteElement forces a change in the Visitor interface and hence in all Visitor implementations. Thus the vanilla Visitor implementation in today's mostly used object oriented languages like Java and C++ violates the Open Closed Principle.

What's special in Scala ?

Scala offers three features which enable a Visitor implementation to have piecemeal growth. Both the visitor and the visited hierarchy can be enhanced incrementally resulting in flexible inheritance hierarchies for both of them.

• Modular Mixin Composition


• Abstract Type Members


• Self Type Annotations

The nuances of the Visitor implementation in Scala is part of the more general Expression Problem, which has been dscribed in the Scala context by Zenger and Odersky.

Let us review the above claim using an example. The following snippet illustrates a sample combination of the Visited and Visitor hierarchy. Here we have only one level of specialization for the Visited and the Visitor abstractions, along with the base contracts for each of them.

trait Base {

  trait Node { // Element base of the hierarchy
    def accept(v: visitor): unit;
  }

  // ConcreteElement specialization
  class File(name: String) extends Node {
    def accept(v: visitor): unit = v.visitFile(name);
  }

  type visitor <: Visitor;
  trait Visitor { // Visitor base of the hierarchy
    def visitFile(name: String): unit;
  }

  // ConcreteVisitor specialization
  trait PrintingVisitor requires visitor extends Visitor {
    def visitFile(name: String): unit =
    Console.println("printing file: " + name);
  }
}

Figure 1 - The Base

Let us see how the above implementation differs from the standard Java Visitor boilerplate. The main problem with the Java/C++ implementation is the fact that the visitor interface has to change with the addition of a ConcreteElement (the visited). This is where we violate the Open Closed Principle - we need to make invasive changes at the contract level, which forces a recursive change down the inheritance hierarchy for all concrete visitor implementations. The Scala implementation above addresses this problem by allowing us to abstract over the concrete visitor type. In order to keep the set of Visited classes open, the Abstract Type visitor is used. Every concrete implementation of Visitor interface such as PrintingVisitor above, implements its bound Visitor. And every Visited element uses the same abstract type visitor for the accept() methods. It is this magic combination of abstract type and mixin composition which allows us to enrich the dual hierarchies incrementally.

In the following sections we will look at how the Scala implementation allows a seamless adding of concrete members to the Visited as well as Visitor hierarchies.


Adding a ConcreteElement (the Visited hierarchy)

// data extension : add Link
trait BaseLink extends Base {

  type visitor <: Visitor;

  trait Visitor extends super.Visitor {
    def visitLink(subject: Node): unit;
  }

  class Link(subject: Node) extends Node {
    def accept(v: visitor): unit = v.visitLink(subject);
  }

  trait PrintingVisitor requires visitor
      extends super.PrintingVisitor
      with Visitor {
    def visitLink(subject: Node): unit =
      subject.accept(this);
  }
}

Figure 2 - Adding a ConcreteElement

Override the abstract type visitor with the extended Visitor trait and include the new visitLink() method - completely non-invasive, yet extensible! The concrete implementation of the new PrintingVisitor extends the trait from the superclass and compose with the extended Visitor trait using Scala mixin composition.

In the above, we claimed that the abstract type visitor allows us to abstract over the concrete visitor types. In the above method visitLink() of PrintingVisitor, the call to accept() has the argument this. But the type PrintingVisitor is not a subtype of the abstract visitor type visitor. The above implementation handles this by the statement requires visitor in the definition of the trait PrintingVisitor. This is called Self Type Annotation, which provides an alternative way of associating a class with an abstract type. The self type specified above is taken as the type of this within the class. Without this feature, the type of this is the usual type of the class itself. In the above implementation, the usage of the self type annotation ensures that the type of this, specified in the argument of accept() is of the abstract type visitor as demanded by the declaration of the Node trait.

Combining Independent Element Extensions

Similar to BaseLink extension above, we can have similar independent extensions in the Visited hierarchy. e.g. we can have a BaseDirectory trait which extends Base with Directory as another Node. I do not go into the details of this implementation, but it will be exactly along the same lines as BaseLink. The important part is the ability to combine independent Element extensions through composition. Scala's powerful modular mixin composition is the answer to all these as the following example demonstrates:

// compose all
trait BaseAll extends BaseDirectory with BaseLink {

  type visitor <: Visitor;
  trait Visitor extends super[BaseDirectory].Visitor
      with super[BaseLink].Visitor;

  trait PrintingVisitor requires visitor
      extends super[BaseDirectory].PrintingVisitor
      with super[BaseLink].PrintingVisitor
      with Visitor;
}

Figure 3 - Composing all Extensions

The abstraction above combines the two independent extensions through mixin composition. In case of such mixin composition, the Scala type system requires that abstract types have to be refined covariantly. Hence BaseAll has to redefine the bounds of the the abstract type visitor through explicit overriding, such that the bound of the new visitor is a subtype of both old bounds.

This is not all - we will see how adding new visitors in the hierarchy combines with the extensibility of the BaseAll trait, resulting in a complete implementation of the Visitor Design Pattern.


Adding a New Visitor to the Hierarchy

Adding new visitors is easy, as the pattern claims - every new operation added simply adds up to the Visitor hierarchy, implementing all the visitor interfaces.

// function extension
trait BaseExt extends BaseAll {
  class RemoveVisitor requires visitor extends Visitor {
    def visitFile(name: String): unit =
    Console.println("removing file: " + name);

  def visitDirectory(name: String): unit =
    Console.println("cannot remove directory: " + name);

  def visitLink(subject: Node): unit =
    subject.accept(this);
  }
}

Figure 4 - Extending the Visitor Interface


Compose Them All - The Grand Visitor

We now have the grand Visitor in place where we can add to Visited and Visitor hierarchies seamlessly ensuring piecemeal growth. The abstractions are open for extension but closed for invasive changes.

Here goes the final usage ..

object VisitorTest extends BaseExt with Application {
  type visitor = Visitor;

  val f = new File("foo.txt");
  val nodes = List(
    f,
    new Directory("bar"),
    new Link(f)
  );

  class PrintingVisitor extends super.PrintingVisitor;
  nodes.elements foreach { x => x.accept(new PrintingVisitor()); }

  class RemoveVisitor extends super.RemoveVisitor;
  nodes.elements foreach { x => x.accept(new RemoveVisitor()); }
}