The Visitor Design Pattern
EECS3311 A: Software Design Fall 2019
CHEN-WEI WANG
Motivating Problem (1)
Based on the you learned, design classes to model of arithmetic expressions
(e.g., 341, 2, 341 + 2). EXPERSSION*
value: INTEGER
COMPOSITE* left, right: EXPRESSION
composite pattern
structures
2 of 13
CONSTANT+
ADDITION+
Motivating Problem (2)
Extend the composite pattern to support operations such as evaluate, pretty printing (print prefix, print postfix), and type check.
EXPERSSION*
value: INTEGER
evaluate*
print_prefix*
print_postfix*
type_check*
COMPOSITE* left, right: EXPRESSION
3 of 13
CONSTANT+
evaluate+
print_prefix+
print_postfix+
type_check+
ADDITION+
evaluate+
print_prefix+
print_postfix+
type_check+
Problems of Extended Composite Pattern
Distributing the various unrelated operations across nodes of the abstract syntax tree violates the single-choice principle :
To add/delete/modify an operation
Change of all descendants of EXPRESSION
Each node class lacks in cohesion :
A class is supposed to group relevant concepts in a single place. Confusing to mix codes for evaluation, pretty printing, and type checking.
We want to avoid ¡°polluting¡± the classes with these various unrelated operations.
4 of 13
Open/Closed Principle
Software entities (classes, features, etc.) should be open for , but closed for modification .
When the behaviour of a system, we: X May add/modify the open (unstable) part of system.
X May not add/modify the closed (stable) part of system.
e.g., In designing the application of an expression language:
X Alternative 1:
Syntactic constructs of the language may be closed, whereas operations on the language may be open.
X Alternative 2:
Syntactic constructs of the language may be open, whereas operations on the language may be closed.
5 of 13
extension
extending
Visitor Pattern
Separation of concerns :
X Set of language constructs
X Set of operations
Classes from these two sets are decoupled and organized
into two separate clusters. Open-Closed Principle (OCP) :
X Closed, staple part of system: set of language constructs X Open, unstable part of system: set of operations
OCP helps us determine if Visitor Pattern is applicable . If it was decided that language constructs are open and
operations are closed, then do not use Visitor Pattern. 6 of 13
Visitor Pattern: Architecture
expression_language
expression_operations
EXPERSSION*
accept(v: VISITOR)*
accept
VISITOR*
visit_constant(c: CONSTANT)* visit_addition(a: ADDITION)*
PRETTY_PRINTER+
visit_constant(c: CONSTANT)+ visit_addition(a: ADDITION)+
CONSTANT+
accept(v: VISITOR)+
COMPOSITE* left, right: EXPRESSION
ADDITION+
accept(v: VISITOR)+
EVALUATOR+
visit_constant(c: CONSTANT)+ visit_addition(a: ADDITION)+
TYPE_CHECKER+
visit_constant(c: CONSTANT)+ visit_addition(a: ADDITION)+
7 of 13
Visitor Pattern Implementation: Structures
Cluster expression language
X Declare deferred feature in EXPRSSION. X Implement accept feature in each of the descendant classes.
CONSTANT
accept(v: VISITOR)
class inherit EXPRESSION …
accept(v: VISITOR) do
v.visit_ constant (Current) end
end
8 of 13
ADDITION
class
inherit EXPRESSION COMPOSITE …
accept(v: VISITOR) do
v.visit_ addition (Current) end
end
Visitor Pattern Implementation: Operations
Cluster expression operations
X For each descendant class C of EXPRESSION, declare a deferred
feature in the deferred class VISITOR.
visit_c (e: C)
deferred class VISITOR
visit_constant(c: CONSTANT) deferred end visit_addition(a: ADDITION) deferred end
end
X Each descendant of VISITOR denotes a kind of operation.
class EVALUATOR inherit VISITOR : INTEGER
visit_constant(c: CONSTANT) do := c.value end visit_addition(a: ADDITION)
local eval_left, eval_right: EVALUATOR do a.left.accept(eval_left)
a.right.accept(eval_right)
:= eval_left.value + eval_right.value
end end
9 of 13
value
value
value
Testing the Visitor Pattern
1 2 3 4 5 6 7 8 9
10 11
test_expression_evaluation: BOOLEAN
local add, c1, c2: EXPRESSION ; v: VISITOR do
create {CONSTANT} c1.make (1) ; create {CONSTANT} c2.make (2) create {ADDITION} add.make (c1, c2)
create {EVALUATOR} v.make
add.accept(v)
check attached {EVALUATOR} v as eval then Result := eval.value = 3
end end
Double Dispatch in Line 7:
1. DT of add is ADDITION Call accept in ADDITION
2. DT of v is EVALUATOR Call visit addition in EVALUATOR +
v.visit
addition
(add)
10 of 13
visiting result of add.left
visiting result of add.right
To Use or Not to Use the Visitor Pattern
In the architecture of visitor pattern, what kind of extensions is easy and hard? Language structure? Language Operation?
X Adding a new kind of operation element is easy.
To introduce a new operation for generating C code, we only need to introduce a new descendant class of VISITOR, then implement how to handle each language element in that class. Single Choice Principle is obeyed.
X Adding a new kind of structure element is hard.
After adding a descendant class MULTIPLICATION of EXPRESSION, every concrete visitor (i.e., descendant of VISITOR) must be amended to provide a new operation.
is violated.
The applicability of the visitor pattern depends on to what extent the structure will change.
Use visitor if operations applied to structure change often.
Do not use visitor if the structure change often. 11 of 13
C CODE GENERATOR
visit multiplication
Single Choice Principle
Beyond this Lecture. . .
Learn about implementing the Composite and Visitor Patterns, from scratch, in this tutorial series:
https://www.youtube.com/playlist?list=PL5dxAmCmjv_
4z5eXGW-ZBgsS2WZTyBHY2
12 of 13
Index (1)
Motivating Problem (1)
Motivating Problem (2)
Problems of Extended Composite Pattern Open/Closed Principle
Visitor Pattern
Visitor Pattern: Architecture
Visitor Pattern Implementation: Structures Visitor Pattern Implementation: Operations Testing the Visitor Pattern
To Use or Not to Use the Visitor Pattern
Beyond this Lecture. . . 13 of 13