In this post I want to explore the usage of the visitor pattern in different
programming languages.
The goal is always to represent expression trees, i.e., to have the abstract
syntax tree (AST) of an algebraic expression like 2 * 5 - 3.
Let us start with a simple implementation in Java:
import java.util.HashMap;
import java.util.Map;
public class ExpressionTree {
public static interface Operator {
int eval(int ... args);
}
public static Map<String, Operator> OPERATOR_MAP
= new HashMap<String, Operator>();
static {
OPERATOR_MAP.put("+", new Operator() {
public int eval(int ... args) {
int result = 0;
for (int i : args) {
result += i;
}
return result;
}
});
OPERATOR_MAP.put("*", new Operator() {
public int eval(int ... args) {
int result = 1;
for (int i : args) {
result *= i;
}
return result;
}
});
OPERATOR_MAP.put("-", new Operator() {
public int eval(int ... args) {
if (args.length != 2) {
throw new IllegalArgumentException("wrong arity");
}
return args[0] - args[1];
}
});
OPERATOR_MAP.put("/", new Operator() {
public int eval(int ... args) {
if (args.length != 2) {
throw new IllegalArgumentException("wrong arity");
}
return args[0] / args[1];
}
});
}
public static interface Visitor {
void apply(Node node);
}
public static class Node {
public void visit(Visitor visitor) {
visitor.apply(this);
}
}
public static class Literal extends Node {
private int value;
public Literal(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
public static class Operation extends Node {
private Node[] children;
private String name;
public Operation(Node[] children, String name) {
this.children = children;
this.name = name;
}
public String getName() {
return name;
}
public Node[] getChildren() {
return children;
}
}
public static class EvalVisitor implements Visitor {
private int value;
public int evaluate(Node node) {
apply(node);
return this.value;
}
public void apply(Literal node) {
value = node.getValue();
}
public void apply(Operation operation) {
Node[] children = operation.getChildren();
int[] values = new int[children.length];
for (int i=0; i<children.length; i++) {
EvalVisitor visitor = new EvalVisitor();
children[i].visit(visitor);
values[i] = visitor.getValue();
}
String name = operation.getName();
Operator op = OPERATOR_MAP.get(name);
if (op == null) {
throw new RuntimeException("unknown operation " + name);
}
this.value = op.eval(values);
}
public void apply(Node node) {
if (node instanceof Literal) {
apply((Literal) node);
}
else if (node instanceof Operation) {
apply((Operation) node);
}
else {
throw new RuntimeException("unknown node instance");
}
}
public int getValue() {
return value;
}
}
public static void main(String[] args) {
System.out.println(
new EvalVisitor().evaluate(
new Operation(new Node[] {
new Operation(new Node[] {
new Literal(2),
new Literal(5)},
"*"),
new Literal(3)},
"-")));
}
}
Two things can be observed here: 1) The base class Node has a
method visit() which simply calls the visitor with itself as
the argument. 2) The visitor uses instanceof to delegate to
the according apply() methods. Hence, run time type information
is used. Java's OO system uses single dispatch. Multiple dispatch would
make this delegation apply() method superfluous, as we shall
see later.
Not all languages allow us to use run time type information and we can get
rid of it by modifying the the Visitor interface as follows:
public static interface Visitor<T> {
T apply(Literal node);
T apply(Operation node);
}
This, however, forces us to make the visit() method in
Node abstract and to implement it in Literal
and Operation. The code is always exactly the same. Thus,
we have the same method in every concrete subclass of Node
instead of having it just once. The approach would be required in OCaml
if you want to use objects. Another option would be to use algebraic data
structures, which are very well supported in OCaml.
Let's move on to a language that has multiple dispatch: Groovy.
def OPERATOR_MAP = [
"+": { args ->
int result = 0;
for (int i : args) {
result += i;
}
return result;
},
"*": { args ->
int result = 1;
for (int i : args) {
result *= i;
}
return result;
},
"-": { args ->
if (args.length != 2) {
throw new IllegalArgumentException("wrong arity");
}
return args[0] - args[1];
},
"/": { args ->
if (args.length != 2) {
throw new IllegalArgumentException("wrong arity");
}
return args[0] / args[1];
}]
public interface Visitor {
void apply(Node node);
}
public class Node {
public void visit(Visitor visitor) {
visitor.apply(this);
}
}
public class Literal extends Node {
private int value;
public Literal(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
public class Operation extends Node {
private def children;
private String name;
public Operation(def children, String name) {
this.children = children;
this.name = name;
}
public String getName() {
return name;
}
public def getChildren() {
return children;
}
}
public class EvalVisitor implements Visitor {
private int value;
private def operatorMap;
public EvalVisitor(def operatorMap) {
this.operatorMap = operatorMap;
}
public int evaluate(Node node) {
apply(node);
return this.value;
}
public void apply(Literal node) {
value = node.getValue();
}
public void apply(Operation operation) {
Node[] children = operation.getChildren();
int[] values = new int[children.length];
for (int i=0; i<children.length; i++) {
EvalVisitor visitor = new EvalVisitor(operatorMap);
children[i].visit(visitor);
values[i] = visitor.getValue();
}
String name = operation.getName();
def op = operatorMap[name];
if (op == null) {
throw new RuntimeException("unknown operation " + name);
}
this.value = op(values);
}
public void apply(Node node) {
throw new RuntimeException("unknown node instance");
}
public int getValue() {
return value;
}
}
println(new EvalVisitor(OPERATOR_MAP).evaluate(
new Operation([
new Operation([ new Literal(2), new Literal(5)], "*"),
new Literal(3)],
"-")));
The Java code was taken as the basis for the Groovy code, as one can
clearly see. As mentioned before, the method apply() of the
visitor that delegated.
The method visit() is not really needed, since we use
run time type information, anyway. But let us first look at an implementation
in Common Lisp.
(defpackage :expression-tree
(:use :common-lisp))
(in-package :expression-tree)
(defparameter *operator-map*
`((+ . ,#'+)
(* . ,#'*)
(- . ,#'-)
(/ . ,#'/)))
(defclass visitor () ())
(defgeneric visitor-apply (visitor node))
(defclass node () ())
(defgeneric visit (node visitor))
(defmethod visit ((node node) (visitor visitor))
(visitor-apply visitor node))
(defclass literal (node)
((value :reader literal-value :initarg :value)))
(defclass operation (node)
((name :reader operation-name :initarg :name)
(children :reader operation-children :initarg :children)))
(defclass eval-visitor (visitor)
((value :accessor eval-visitor-value :initform 0)))
(defmethod visitor-apply ((visitor visitor) (node literal))
(setf (eval-visitor-value visitor) (literal-value node)))
(defmethod visitor-apply ((visitor visitor) (node operation))
(let ((operation (cdr (assoc (operation-name node) *operator-map*))))
(when (null operation)
(error "unknown operation ~A" (operation-name node)))
(setf (eval-visitor-value visitor)
(apply operation
(mapcar (lambda (child)
(let ((sub-visitor (make-instance 'eval-visitor)))
(visit child sub-visitor)
(eval-visitor-value sub-visitor)))
(operation-children node)))))
(defun expression-evaluate (node)
(let ((visitor (make-instance 'eval-visitor)))
(visit node visitor)
(eval-visitor-value visitor)))
(expression-evaluate
(make-instance 'operation :name '-
:children
(list
(make-instance 'operation
:name '*
:children
(list
(make-instance 'literal :value 2)
(make-instance 'literal :value 5)))
(make-instance 'literal :value 3))))
The same approach is used here with the visitor class and
the visit method. The fact that visit really
just calls visitor-apply with swapped arguments, makes it
even more obvious that this method is not really needed in dynamic typed
languages. So let us get rid of this extra step. And while we are at it,
let us define a function sexp-to-ast that transforms an
s-expression into a node graph.
(defpackage :expression-tree
(:use :common-lisp))
(in-package :expression-tree)
(defparameter *operator-map*
`((+ . ,#'+)
(* . ,#'*)
(- . ,#'-)
(/ . ,#'/)))
(defclass visitor () ())
(defclass node () ())
(defgeneric visit (node visitor))
(defclass literal (node)
((value :reader literal-value :initarg :value)))
(defclass operation (node)
((name :reader operation-name :initarg :name)
(children :reader operation-children :initarg :children)))
(defclass eval-visitor (visitor)
((value :accessor eval-visitor-value :initform 0)))
(defmethod visit ((node literal) (visitor eval-visitor))
(setf (eval-visitor-value visitor) (literal-value node)))
(defmethod visit ((node operation) (visitor eval-visitor))
(let ((operation (cdr (assoc (operation-name node) *operator-map*))))
(when (null operation)
(error "unknown operation ~A" (operation-name node)))
(setf (eval-visitor-value visitor)
(apply operation
(mapcar (lambda (child)
(let ((sub-visitor (make-instance 'eval-visitor)))
(visit child sub-visitor)
(eval-visitor-value sub-visitor)))
(operation-children node))))))
(defun expression-evaluate (node)
(let ((visitor (make-instance 'eval-visitor)))
(visit node visitor)))
(eval-visitor-value visitor)))
(defclass eval-visitor (visitor) ())
(defmethod visit ((node literal) (visitor visitor))
(literal-value node))
(defmethod visit ((node operation) (visitor visitor))
(let ((operation (cdr (assoc (operation-name node) *operator-map*))))
(when (null operation)
(error "unknown operation ~A" (operation-name node)))
(apply operation
(mapcar (lambda (child)
(let ((sub-visitor (make-instance 'eval-visitor)))
(visit child sub-visitor)))
(operation-children node)))))
(defun sexp-to-ast (sexp)
(if (listp sexp)
(let ((children (mapcar #'sexp-to-ast (cdr sexp))))
(make-instance 'operation :name (car sexp) :children children))
(make-instance 'literal :value sexp)))
(expression-evaluate (sexp-to-ast '(- (* 2 5) 3)))
Visitors can have state. We exploited that fact, but let us redefine
visit to return a value. This way we can get rid of the state and reuse
our visitor.
(defpackage :expression-tree
(:use :common-lisp))
(in-package :expression-tree)
(defparameter *operator-map*
`((+ . ,#'+)
(* . ,#'*)
(- . ,#'-)
(/ . ,#'/)))
(defclass node () ())
(defgeneric visit (node visitor))
(defclass literal (node)
((value :reader literal-value :initarg :value)))
(defclass operation (node)
((name :reader operation-name :initarg :name)
(children :reader operation-children :initarg :children)))
(defclass eval-visitor () ())
(defmethod visit ((node literal) (visitor eval-visitor))
(literal-value node))
(defmethod visit ((node operation) (visitor eval-visitor))
(let ((operation (cdr (assoc (operation-name node) *operator-map*))))
(when (null operation)
(error "unknown operation ~A" (operation-name node)))
(apply operation
(mapcar (lambda (child) (visit child visitor))
(operation-children node)))))
(defun expression-evaluate (node)
(let ((visitor (make-instance 'eval-visitor)))
(visit node visitor)))
(defun sexp-to-ast (sexp)
(if (listp sexp)
(let ((children (mapcar #'sexp-to-ast (cdr sexp))))
(make-instance 'operation :name (car sexp) :children children))
(make-instance 'literal :value sexp)))
(expression-evaluate (sexp-to-ast '(- (* 2 5) 3)))
This, of course, can also be done in Groovy (and in Java). Here it is
(with OPERATOR_MAP omitted):
public interface Visitor {
Object apply(Node node);
}
public class Node {
}
public class Literal extends Node {
private int value;
public Literal(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
public class Operation extends Node {
private def children;
private String name;
public Operation(def children, String name) {
this.children = children;
this.name = name;
}
public String getName() {
return name;
}
public def getChildren() {
return children;
}
}
public class EvalVisitor implements Visitor {
private def operatorMap;
public EvalVisitor(def operatorMap) {
this.operatorMap = operatorMap;
}
public int apply(Literal node) {
return node.getValue();
}
public int apply(Operation operation) {
Node[] children = operation.getChildren();
int[] values = new int[children.length];
for (int i=0; i<children.length; i++) {
values[i] = apply(children[i]);
}
String name = operation.getName();
def op = operatorMap[name];
if (op == null) {
throw new RuntimeException("unknown operation " + name);
}
return op(values);
}
public Object apply(Node node) {
throw new RuntimeException("unknown node instance");
}
}
println(new EvalVisitor(OPERATOR_MAP).apply(
new Operation([
new Operation([ new Literal(2), new Literal(5)], "*"),
new Literal(3)],
"-")));
Here it is in Java (with OPERATOR_MAP omitted):
import java.util.HashMap;
import java.util.Map;
public class ExpressionTree {
public static interface Operator {
int eval(int ... args);
}
public static interface Visitor {
void apply(Node node);
}
public static class Node {
public void visit(Visitor visitor) {
visitor.apply(this);
}
}
public static class Literal extends Node {
private int value;
public Literal(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
public static class Operation extends Node {
private Node[] children;
private String name;
public Operation(Node[] children, String name) {
this.children = children;
this.name = name;
}
public String getName() {
return name;
}
public Node[] getChildren() {
return children;
}
}
public static class EvalVisitor implements Visitor {
private int value;
public int evaluate(Node node) {
apply(node);
return this.value;
}
public void apply(Literal node) {
value = node.getValue();
}
public void apply(Operation operation) {
Node[] children = operation.getChildren();
int[] values = new int[children.length];
for (int i=0; i<children.length; i++) {
EvalVisitor visitor = new EvalVisitor();
children[i].visit(visitor);
values[i] = visitor.getValue();
}
String name = operation.getName();
Operator op = OPERATOR_MAP.get(name);
if (op == null) {
throw new RuntimeException("unknown operation " + name);
}
this.value = op.eval(values);
}
public void apply(Node node) {
if (node instanceof Literal) {
apply((Literal) node);
}
else if (node instanceof Operation) {
apply((Operation) node);
}
else {
throw new RuntimeException("unknown node instance");
}
}
public int getValue() {
return value;
}
}
public static void main(String[] args) {
System.out.println(
new EvalVisitor().evaluate(
new Operation(new Node[] {
new Operation(new Node[] {
new Literal(2),
new Literal(5)},
"*"),
new Literal(3)},
"-")));
}
}
For the sake of completeness
here is the mentioned variant in Java that does not use dynamic type
features (with OPERATOR_MAP omitted):
import java.util.HashMap;
import java.util.Map;
public class ExpressionTree {
public static interface Operator {
int eval(int ... args);
}
public static interface Visitor<T> {
T apply(Literal node);
T apply(Operation node);
}
public static abstract class Node {
public abstract Integer visit(Visitor<Integer> visitor);
}
public static class Literal extends Node {
private int value;
public Literal(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public Integer visit(Visitor<Integer> visitor) {
return visitor.apply(this);
}
}
public static class Operation extends Node {
private Node[] children;
private String name;
public Operation(Node[] children, String name) {
this.children = children;
this.name = name;
}
public String getName() {
return name;
}
public Node[] getChildren() {
return children;
}
public Integer visit(Visitor<Integer> visitor) {
return visitor.apply(this);
}
}
public static class EvalVisitor implements Visitor<Integer> {
public Integer apply(Literal node) {
return node.getValue();
}
public Integer apply(Operation operation) {
Node[] children = operation.getChildren();
int[] values = new int[children.length];
for (int i=0; i<children.length; i++) {
values[i] = children[i].visit(this);
}
String name = operation.getName();
Operator op = OPERATOR_MAP.get(name);
if (op == null) {
throw new RuntimeException("unknown operation " + name);
}
return op.eval(values);
}
}
public static void main(String[] args) {
System.out.println(
new EvalVisitor().apply(
new Operation(new Node[] {
new Operation(new Node[] {
new Literal(2),
new Literal(5)},
"*"),
new Literal(3)},
"-")));
}
}
So, what does all this tell us? Two things are obvious: 1) To get rid of the
method visit() in the target object structure we need dynamic
typing. 2) To get rid of the manual dispatching we need either multiple
dispatch or we have to implement the visit() in every concrete
sub-class of the target object structure (here all sub-classes of
Node).
But there is still more to it. There is a subtle difference between the
Groovy and the Common Lisp version. To emphasise this, in CL the visiting
method is visit, but in Groovy it is apply.
The method apply belongs to the visitor class. In CL a method
does not belong to any class, but it is just a question of specialisation.
