Visitor Design Pattern

Intent

Intent

The Visitor Pattern enables to add new behavior to existing classes in a fixed class hierarchy without changing this hierarchy.

Intent of the Visitor in Context

Recall the problems of inheritance with modeling variations at the level of multiple objects (object composites).

DP Visitor ModelingVariations

Problems:

Solution

Solution Idea

Represent the additional operations to be performed on the elements of an object structure (additional features) as objects (of type Visitor).

Structure

DP Visitor Structure

Example Usage:

Element e = new ConcreteElementA(...);
Visitor v = new ConcreteVisitor1(...);
e.accept(v);

The Visitor interface declares a visit method per element type in the object structure.

A Visitor interface describes how to “treat” the element types.

Concrete visitor classes implement the interface specifically, i.e., treat elements differently.

A concrete visitor class corresponds to a particular feature to be added to the object structure.

Elements in the object structure provide the method accept(Visitor).

On being asked to accept a visitor passed to it as a parameter, an element asks the visitor to visit it.

Structure (Long Version)

DP Visitor Structure Complete

Case-Study: Arithmetic Expressions

Case-Study: Arithmetic Expressions

DP Visitory Expr(Naive)

Which are the potential design issues?

Requirements:

Design Issues:

Visitor-Based Design

DP Visitory Expr Visitor

The dispatch of the operations defined in the Element hierarchy depends on two parameters:

  1. Dynamic type of the receiver Element determines the class that has the needed method look-up table.
  2. Name of the operation being called determines the entry in that table.

For operations that are outsourced to visitors, we need to simulate the same dispatch semantics.
We need to select an implementation of an operation based on both

  1. the dynamic type of the element on which to apply the operation,
  2. the dynamic type of the visitor object representing the operation.

Reflections on the Visitor Structure

Reflections on the Visitor Structure

Can we move the implementation of accept higher up the Element hierarchy?

DP Visitor Structure Question

Answer: No. The method that is called by v.visit(this) is determined at compile-time.

Case-Study: Calculating Shape Intersection

Case-Study: Calculating Shape Intersection

DP Visitor ShapeIntersection Start ClassHierarchy

Task: Implement an intersect operation that calculates whether two given shapes intersect.

TODO Enable: "anim-step:1"

Case-Study: Calculating Shape Intersection

DP Visitor ShapeIntersection Start ClassHierarchy

Task: Implement an intersect operation that calculates whether two given shapes intersect.

Sketch of the solution:

Shape t = new Triangle(…);
Shape r = new Rectangle(…);
if (t.intersect(r)) {…}

For the proposed solution, the implementation of intersect depends on the dynamic type of both the receiver (t) and parameter (r) shapes. Hence, we need to simulate double dispatch in Java.

Case-Study: Calculating Shape Intersection

Simulating Double Dispatch

DP Visitor ShapeIntersection Start WithIntersectMethods

Do you see how this design simulates double dispatch?

Case-Study: Calculating Shape Intersection

Simulating Double Dispatch

Shape t = new Triangle(…);
Shape r = new Rectangle(…);
if (t.intersect(r)) {…}

DP Visitor ShapeIntersection Start WithIntersectMethodsWithDoubleDispatchVisualization

How do you judge this design?

External call t.intersect(r) is dispatched based on dynamic type of t.

Internal call s.intersect(this) is dispatched based on dynamic type of r.

Assessment:

Case-Study: Shape Intersection Using Visitor

DP Visitor ShapeIntersection Visitor

The Visitor Pattern can be used to eliminate the cross-reference in each shape derivative to each other shape derivative. The key idea is to move the intersect functionality to visitors and to implement one intersection visitor (e.g., CircleIntersection or RectangleIntersector) per Shape type.

Case-Study: Shape Intersection Using Visitor

Shape c = new Circle(…);
Shape r = new Rectangle(…);
if (c.intersect(r)) {…}

DP Visitor ShapeIntersection VisitorInteraction

Assessment of the Visitor Design Pattern

Advantages of the Visitor Design Pattern

  • New operations are easy to add without changing element classes (add a new concrete visitor).
    Different concrete elements do not have to implement their part of a particular algorithm.

  • Related behavior focused in a single concrete visitor.

  • Visiting across hierarchies: Visited classes are not forced to share a common base class.

  • Accumulating state: Visitors can accumulate state as they visit each element, thus, encapsulating the algorithm and all its data.

Issues of the Visitor-Based Design

Adding Elements

Scenario: DP Visitor Problem AddingElements Start

What happens if we want to add a new element?

Description:

Issues of the Visitor-Based Design

E.g., adding Chart (adding Elements)

DP Visitor Problem AddingElements Chart

Problem: Since Visitor has no method for Chart, it’s objects won’t be processed by any visitor. Our design is not closed against this kind of change.

Issues of the Visitor-Based Design

E.g., adding Chart and updating Visitor

DP Visitor Problem AddingElements ChangingVisitors

What are the issues?

Issues:

Issues of the Visitor-Based Design

E.g., adding Chart and keeping Visitor unchanged

DP Visitor Problem AddingElements VisitorUnchanged

What are the issues?

Issues of the Visitor-Based Design

E.g., adding Chart and keeping Visitor unchanged

DP Visitor Problem AddingElements VisitorUnchanged Conclusion

What are the issues?

Try to avoid such visitors as these implementations are extremely fragile; they are maintenance nightmares when more elements are added.

Issues of the Visitor-Based Design

Partial Visiting Is Not Supported

Visitor is like a matrix (cross product of all Visitor and Element classes):

DP Visitor Problem PartialVisiting

Partial visiting is not supported!

To provide a common abstract Visitor interface to Element, every derivative of Element need to be addressed by every derivative of Visitor; even if this might not make sense or is not needed. We have seen this for SpellChecker.visit(Chart)

Takeaway

Takeaway

  • Visitor brings functional-style decomposition to OO designs.

  • Use Visitor for stable element hierarchies.
    Visitor works well in data hierarchies where new elements are never or at least not very often added.

  • Do not use it, if new elements are a likely change.

  • Visitor only makes sense if we have to add new operations often! In this case Visitor closes our design against these changes.

Solving the Expression Problem in Scala

Recommended reading: Matthias Zenger and Martin Odersky, Independently Extensible Solutions to the Expression Problem, FOOL 2005

The code shown in the following can be downloaded here.

Using "Standard" Object-Oriented Features

Solving the Expression Problem in Scala

The base trait.

trait Expressions {

    type expression <: Expression
    trait Expression {
        def eval: Double
    }

    trait Constant extends Expression {
        val v: Double
        def eval = v
    }
}

Resembles the solution that we have studied as part of the implementation of the SmartHome Scenario.

To make it possible to extend the Expression trait (i.e., to enable an independently developed extension to contribute functionality to Expressions ) we have to abstract over the concrete type of Expression.

Solving the Expression Problem in Scala

Adding a new data-type.

trait AddExpressions extends Expressions {
    trait Add extends Expression {
        val l: Expression
        val r: Expression
        def eval = l.eval + r.eval
    }
}

Resembles the solution that we have studied as part of the implementation of the SmartHome Scenario.

Solving the Expression Problem in Scala

Adding new functionality.

trait PrefixNotationForExpressions extends AddExpressions {

  type expression <: Expression
  trait Expression extends super.Expression {
    def prefixNotation: String
  }

  trait Constant extends super.Constant with Expression {
    def prefixNotation = v.toString
  }

  trait Add extends super.Add with Expression {
    def prefixNotation = "+"+l.prefixNotation + r.prefixNotation
  }
}

Resembles the solution that we have studied as part of the implementation of the SmartHome Scenario.

Solving the Expression Problem in Scala

Bringing everything together.

object ExpressionsFramework
    extends PrefixNotationForExpressions
    with PostfixNotationForExpressions {
		
  type expression = Expression
  trait Expression
    extends super[PrefixNotationForExpressions].Expression
    with super[PostfixNotationForExpressions].Expression

  case class Constant(v: Double)
    extends super[PrefixNotationForExpressions].Constant
    with super[PostfixNotationForExpressions].Constant
    with Expression

  case class Add(val l: expression, val r: expression)
    extends super[PrefixNotationForExpressions].Add
    with super[PostfixNotationForExpressions].Add
    with Expression
}

Resembles the solution that we have studied as part of the implementation of the SmartHome Scenario.

Assessment:

Using the Visitor-Design Pattern

Solving the Expression Problem in Scala

The base trait.

trait Expressions {
    
  trait Expression { def accept[T](visitor: visitor[T]): T }

  class Constant(val v: Double) extends Expression {
    def accept[T](visitor: visitor[T]): T = visitor.visitConstant(v)
  }

  type visitor[T] <: Visitor[T]
  trait Visitor[T] {
    def visitConstant(v: Double): T
  }

  trait EvalVisitor extends Visitor[Double] {
    def visitConstant(v: Double): Double = v
  }
}

This solution does not support adding methods/functionality to an expression at runtime or by a third-party extension, i.e., an independently developed extension of the Expressions trait cannot contribute to the Expression trait.

Solving the Expression Problem in Scala

Adding a new data-type.

trait AddExpressions extends Expressions {

  class Add(
    val l: Expression,
    val r: Expression) extends Expression {
				
    def accept[T](visitor: visitor[T]): T = visitor.visitAdd(l, r)
  }

  type visitor[T] <: Visitor[T]
  trait Visitor[T] extends super.Visitor[T] {
    def visitAdd(l: Expression, r: Expression): T
  }

  trait EvalVisitor extends super.EvalVisitor with Visitor[Double] { 
  this: visitor[Double] ⇒
  def visitAdd(l: Expression, r: Expression): Double =
    l.accept(this) + r.accept(this)
  }
}

Solving the Expression Problem in Scala

Bringing everything together:

trait ExtendedExpressions extends AddExpressions with MultExpressions {

  type visitor[T] = Visitor[T] 
  trait Visitor[T]
    extends super[AddExpressions].Visitor[T]
    with super[MultExpressions].Visitor[T]

  object EvalVisitor
    extends super[AddExpressions].EvalVisitor
    with super[MultExpressions].EvalVisitor
    with Visitor[Double] { 
	  this: visitor[Double] ⇒ }
}

By making the type visitor concrete (type visitor[T] = Visitor[T]) the data-type hierarchy is now fixed; extension is only possible w.r.t. new functionality.

Solving the Expression Problem in Scala

Adding new functionality.

trait PrefixNotationForExpressions extends ExtendedExpressions {

  object PrefixNotationVisitor extends super.Visitor[String] { 
    this: visitor[String] ⇒

    def visitConstant(v: Double): String = v.toString+" "

    def visitAdd(l: Expression, r: Expression): String = 
      "+ "+l.accept(this) + r.accept(this)

    def visitMult(l: Expression, r: Expression): String = 
      "* "+l.accept(this) + r.accept(this)

  }
}

Assessment: