Visitor pattern - AbsoluteAstronomy.com

Object-oriented programming

Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...

and software engineering

Software engineering

Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...

, the visitor design pattern is a way of separating an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

from an object structure on which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those structures. It is one way to easily follow the open/closed principle

Open/closed principle

In object-oriented programming, the open/closed principle states "software entities should be open for extension, but closed for modification";...

.

In essence, the visitor allows one to add new virtual function

Virtual function

In object-oriented programming, a virtual function or virtual method is a function or method whose behaviour can be overridden within an inheriting class by a function with the same signature...

s to a family of classes without modifying the classes themselves; instead, one creates a visitor class that implements all of the appropriate specializations of the virtual function. The visitor takes the instance reference as input, and implements the goal through double dispatch

Double dispatch

In software engineering, double dispatch is a special form of multiple dispatch, and a mechanism that dispatches a function call to different concrete functions depending on the runtime types of two objects involved in the call...

.

While powerful, the visitor pattern is more limited than conventional virtual functions. It is not possible to create visitors for objects without adding a small callback method inside each class. In naive implementations, the callback method in each of the classes is not inheritable.

Details

A user object receives a pointer to another object which implements an algorithm.
The first is designated the "element class" and the latter the "visitor class."
The idea is to use a structure of element classes, each of which has an accept method taking a visitor object for an argument. visitor is a protocol

Protocol (object-oriented programming)

In object-oriented programming, a protocol or interface is a common means for unrelated objects to communicate with each other. These are definitions of methods and values which the objects agree upon in order to cooperate....

(interface

Interface (Java)

An interface in the Java programming language is an abstract type that is used to specify an interface that classes must implement. Interfaces are declared using the interface keyword, and may only contain method signature and constant declarations...

in Java) having a visit method for each element class. The accept method of an element class calls back the visit method for its class. Separate concrete visitor classes can then be written to perform some particular operations, by implementing these operations in their respective visit methods.

One of these visit methods of a concrete visitor can be thought of as a method not of a single class, but rather a method of a pair of classes: the concrete visitor and the particular element class. Thus the visitor pattern simulates double dispatch

Double dispatch

in a conventional single-dispatch object-oriented language such as Java

Java (programming language)

Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

, Smalltalk

Smalltalk

Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...

, and C++

C++

C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

. For an explanation of how double dispatch differs from function overloading, see Double dispatch is more than function overloading in the double dispatch article. In the Java language, two techniques have been documented that use reflection to simplify the mechanics of double dispatch simulation in the visitor pattern: getting rid of accept methods (the Walkabout variation), and getting rid of extra visit methods / A time for reflection: Java 1.2's reflection capabilities eliminate burdensome accept methods from your Visitor pattern. Despite the advantage using a reflective visitor gives of code syntax simplification it should be noted that the reflective visitor pattern may be unsuitable for iterating over a large number of visitable objects - there is a significant performance overhead of between two to fifty times per reflective method invocation compared to regular method invocation.

The visitor pattern also specifies how iteration occurs over the object structure. In the simplest version, where each algorithm needs to iterate in the same way, the accept method of a container element, in addition to calling back the visit method of the visitor, also passes the visitor object to the accept method of all its constituent child elements.

Because the visitor object has one principal function (manifested in a plurality of specialized methods) and that function is called visit, the visitor can be readily identified as a potential function object

Function object

A function object, also called a functor, functional, or functionoid, is a computer programming construct allowing an object to be invoked or called as though it were an ordinary function, usually with the same syntax.-Description:...

. Likewise, the accept function can be identified as a function applicator, a mapper, which knows how to traverse a particular type of object and apply a function to its elements. Lisp's object system with its multiple dispatch does not replace the Visitor pattern, but merely provides a more concise implementation of it in which the pattern all but disappears.

Java example

The following example is in the Java programming language, and shows how the contents of a tree of nodes (in this case describing the components of a car) can be printed. Instead of creating "print" methods for each subclass (Wheel, Engine, Body, and Car), a single class (CarElementPrintVisitor) performs the required printing action. Because different subclasses require slightly different actions to print properly, CarElementDoVisitor dispatches actions based on the class of the argument passed to it.

Diagram

Source

interface CarElementVisitor {
void visit(Wheel wheel);
void visit(Engine engine);
void visit(Body body);
void visit(Car car);
}

interface CarElement {
void accept(CarElementVisitor visitor); // CarElements have to provide accept.
}

class Wheel implements CarElement {
private String name;

public Wheel(String name) {
this.name = name;
}

public String getName {
return this.name;
}

public void accept(CarElementVisitor visitor) {
visitor.visit(this);
}
}

class Engine implements CarElement {
public void accept(CarElementVisitor visitor) {
visitor.visit(this);
}
}

class Body implements CarElement {
public void accept(CarElementVisitor visitor) {
visitor.visit(this);
}
}

class Car implements CarElement {
CarElement[] elements;

public CarElement[] getElements {
return elements.clone; // Return a copy of the array of references.
}

public Car {
this.elements = new CarElement[]
{ new Wheel("front left"), new Wheel("front right"),
new Wheel("back left") , new Wheel("back right"),
new Body, new Engine };
}

public void accept(CarElementVisitor visitor) {
for(CarElement element : this.getElements) {
element.accept(visitor);
}
visitor.visit(this);
}
}

class CarElementPrintVisitor implements CarElementVisitor {
public void visit(Wheel wheel) {
System.out.println("Visiting " + wheel.getName
+ " wheel");
}

public void visit(Engine engine) {
System.out.println("Visiting engine");
}

public void visit(Body body) {
System.out.println("Visiting body");
}

public void visit(Car car) {
System.out.println("Visiting car");
}
}

class CarElementDoVisitor implements CarElementVisitor {
public void visit(Wheel wheel) {
System.out.println("Kicking my " + wheel.getName + " wheel");
}

public void visit(Engine engine) {
System.out.println("Starting my engine");
}

public void visit(Body body) {
System.out.println("Moving my body");
}

public void visit(Car car) {
System.out.println("Starting my car");
}
}

public class VisitorDemo {
static public void main(String[] args) {
Car car = new Car;
car.accept(new CarElementPrintVisitor);
car.accept(new CarElementDoVisitor);
}
}

Note: A more flexible approach to this pattern is to create a wrapper class implementing the interface defining the accept method. The wrapper contains a reference pointing to the CarElement which could be initialized through the constructor. This approach avoids having to implement an interface on each element. [see article Java Tip 98 article below]

Output



Visiting front left wheel

Visiting front right wheel

Visiting back left wheel

Visiting back right wheel

Visiting body

Visiting engine

Visiting car

Kicking my front left wheel

Kicking my front right wheel

Kicking my back left wheel

Kicking my back right wheel

Moving my body

Starting my engine

Starting my car

Source

(defclass auto
((elements :initarg :elements)))

(defclass auto-part
((name :initarg :name :initform "")))

(defmethod print-object ((p auto-part) stream)
(print-object (slot-value p 'name) stream))

(defclass wheel (auto-part) )

(defclass body (auto-part) )

(defclass engine (auto-part) )

(defgeneric traverse (function object other-object))

(defmethod traverse (function (a auto) other-object)
(with-slots (elements) a
(dolist (e elements)
(funcall function e other-object))))

do-something visitation

catch al

(defmethod do-something (object other-object)
(format t "don't know how ~s and ~s should interact~%" object other-object))

visitation involving wheel and intege

(defmethod do-something ((object wheel) (other-object integer))
(format t "kicking wheel ~s ~s times~%" object other-object))

visitation involving wheel and symbo

(defmethod do-something ((object wheel) (other-object symbol))
(format t "kicking wheel ~s symbolically using symbol ~s~%" object other-object))

(defmethod do-something ((object engine) (other-object integer))
(format t "starting engine ~s ~s times~%" object other-object))

(defmethod do-something ((object engine) (other-object symbol))
(format t "starting engine ~s symbolically using symbol ~s~%" object other-object))

(let ((a (make-instance 'auto
:elements `
,(make-instance 'wheel :name "front-right-wheel")
,(make-instance 'wheel :name "rear-right-wheel")
,(make-instance 'wheel :name "rear-right-wheel")
,(make-instance 'body :name "body")
,(make-instance 'engine :name "engine")))))
;; traverse to print elements
;; stream *standard-output* plays the role of other-object here
(traverse #'print a *standard-output*)

(terpri) ;; print newline

;; traverse with arbitrary context from other object
(traverse #'do-something a 42)

;; traverse with arbitrary context from other object
(traverse #'do-something a 'abc))

Output

"front-left-wheel"

"front-right-wheel"

"rear-right-wheel"

"rear-right-wheel"

"body"

"engine"

kicking wheel "front-left-wheel" 42 times

kicking wheel "front-right-wheel" 42 times

kicking wheel "rear-right-wheel" 42 times

kicking wheel "rear-right-wheel" 42 times

don't know how "body" and 42 should interact

starting engine "engine" 42 times

kicking wheel "front-left-wheel" symbolically using symbol ABC

kicking wheel "front-right-wheel" symbolically using symbol ABC

kicking wheel "rear-right-wheel" symbolically using symbol ABC

kicking wheel "rear-right-wheel" symbolically using symbol ABC

don't know how "body" and ABC should interact

starting engine "engine" symbolically using symbol ABC

State

Aside from potentially improving separation of concerns

Separation of concerns

In computer science, separation of concerns is the process of separating a computer program into distinct features that overlap in functionality as little as possible. A concern is any piece of interest or focus in a program. Typically, concerns are synonymous with features or behaviors...

, the visitor pattern has an additional advantage over simply calling a polymorphic method: a visitor object can have state. This is extremely useful in many cases where the action performed on the object depends on previous such actions.

An example of this is a pretty-printer in a programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

implementation (such as a compiler

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

or interpreter). Such a pretty-printer object (implemented as a visitor, in this example), will visit nodes in a data structure that represents a parsed and processed program. The pretty-printer will then generate a textual representation of the program tree. To make the representation human-readable, the pretty-printer should properly indent program statements and expressions. The current indentation level can then be tracked by the visitor as its state, correctly applying encapsulation, whereas in a simple polymorphic method invocation, the indentation level would have to be exposed as a parameter and the caller would rely on the method implementation to use and propagate this parameter correctly.

External links

The Visitor Family of Design Patterns by Robert C. Martin - a rough chapter from The Principles, Patterns, and Practices of Agile Software Development, Robert C. Martin, Prentice Hall
Visitor pattern in UML and in LePUS3 (a Design Description Language)
Article "Componentization: the Visitor Example by Bertrand Meyer
Bertrand Meyer
Bertrand Meyer is an academic, author, and consultant in the field of computer languages. He created the Eiffel programming language.-Education and academic career:...

and Karine Arnout, Computer (IEEE), vol. 39, no. 7, July 2006, pages 23-30.
Article A Type-theoretic Reconstruction of the Visitor Pattern
Article "The Essence of the Visitor Pattern" by Jens Palsberg and C. Barry Jay. 1997 IEEE-CS
IEEE Computer Society
The IEEE Computer Society is a professional society of IEEE. Its purpose and scope is “to advance the theory, practice, and application of computer and information processing science and technology” and the “professional standing of its members.” The CS is the largest of 38 technical societies...

COMPSAC
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...

paper showing that accept methods are unnecessary when reflection is available; introduces term 'Walkabout' for the technique.
Article "A Time for Reflection" by Bruce Wallace - subtitled "Java 1.2's reflection capabilities eliminate burdensome accept methods from your Visitor pattern"
Visitor Patterns as a universal model of terminating computation.
Visitor Pattern using reflection(java).
PerfectJPattern Open Source Project, Provides a context-free and type-safe implementation of the Visitor Pattern in Java based on Delegates.
Visitor Design Pattern
Article Java Tip 98: Reflect on the Visitor design pattern

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Details

Java example

Diagram

Source

Output

Source

Output

State

See also

External links