Autonomes SäulenblogThe Visitor Pattern in Differen Languages
Contents
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.