The core essence of the visitor pattern is to implement case distinction on sum types in languages that do not natively support sum types. Double dispatch is merely the mechanism by which the visitor pattern achieves this.
back
1 comments
Double virtual dispatch is the core goal of the visitor pattern. If you don't have two families of types and subtypes (different subtypes of visitors and different subtypes of expressions), there are much simpler alternatives to the Visitor Pattern even in something like Java.
In particular, if you have a single closed sum type, function overloading is the best way to handle distinctions. If you want it to be open, single virtual dispatch is a common option.
It's only when you get two different sum types, with one or both being open, that you start benefitting from the visitor pattern.
The benefit is that you can decouple the implementation of the operation from the implementation of the sum type. For example, a library can provide a sum type, and users of the library can implement their own operations on it. This is often necessary for proper separation of concerns. For example, the sum type may be a domain object, and the operations may be database operations, UI operations, or other I/O or conversion operations. You don’t want the domain layer to have dependencies on the database, UI, I/O, etc., which it would have if those operations were implemented in the sum type itself.
It’s exactly the same benefits provided by language-native sum types with ADT pattern matching (aside from the visitor pattern requiring more boilerplate).
The operation can itself be a polymorphic operation on a different type hierarchy or sum type, which is the scenario you are thinking of, but that’s not necessary for being able to benefit from the visitor pattern.
Read the original description of the visitor pattern in the GoF book. It’s about implementing operations on an existing type hierarchy without having to modify the code of that type hierarchy.
To illustrate how to implement what you are describing without a visitor pattern if we don't care about subtypes:
//library code
sealed class TreeNode{
Object[] children;
}
sealed class LeafNode {
int value
}
//application code
int sumTree(Object o) {
if(o instanceof TreeNode) {
var tn = (TreeNode)o;
sum += sumTree(tn);
} else if (o instanceof LeafNode) {
var ln = (LeafNode) o;
sum += sumTree(ln) ;
}
}
int sumTree(TreeNode a) {
var sum = 0;
for (Object o in a.Children) {
sum += sumTree(o) ;
}
return sum;
}
int sumTree(LeafNode ln) {
return ln.value;
}
Now, if you start adding actual subtypes to TreeNode and LeafNode, this will quickly stop working, especially if you want more than one operation.
For example, if you wanted to add a DictionaryTreeNode that stores its children in a dictionary instead of a list, the visitor-based version would not require any change to the SumTree visitor, as DictionaryTreeNode can just call visitTreeNode in its accept() method.
ADTs and pattern matching don't solve this problem in any way - you can't add a new node subtype, because the operation explicitly decides what to do based on the variant.
Ifs and type checks are not a substitute for the visitor pattern, at least in statically typed languages, because they don't give you compile-time checks (exhaustiveness checking, as you say).
The visitor pattern doesn't require you to have a hierarchy of operations. It doesn't even require the sum type options to form a public type hierarchy. For example, the following Java code implements the typical binary-tree sum type:
public abstract class Tree<V>
{
public abstract <R> R apply(Visitor<? super V, R> visitor);
public interface Visitor<V, R>
{
public R whenLeaf(V value);
public R whenNode(Tree<? extends V> left, Tree<? extends V> right);
}
public static <V> Tree<V> leaf(V value)
{
return new Tree<V>()
{
@Override
public <R> R apply(Visitor<? super V, R> visitor)
{
return visitor.whenLeaf(value);
}
};
}
public static <V> Tree<V> node(Tree<? extends V> left, Tree<? extends V> right)
{
return new Tree<V>()
{
@Override
public <R> R apply(Visitor<? super V, R> visitor)
{
return visitor.whenNode(left, right);
}
};
}
private Tree() { }
}
(Incidentally, that design also allows you to replace the implementation by a tagged-union approach. The result wouldn't be the full visitor pattern anymore, of course.)
EDIT: Another way to put this: The visitor pattern abstracts away the case-distinction mechanism into a single implementation. In your code example, every operation (like sumTree) has to re-implement the case-distinction mechanism, that is, the ifs and the type checks. The visitor pattern decouples the case-distinction mechanism from the concrete case distinctions.
The example you're showing is what I would call over complicated. It does an awful lot of work just to gain a little bit of extra type safety compared to mine. You are introducing an extra type parameter (V is good, I was just lazy, but R is only needed because of the Visitor formalism) and 3 extra methods (accept, whenLeaf and whenNode). This all makes the code much harder to follow, and all it gets you is a little bit of extra type safety. It's true that this code in particular is easily and even better replaced with a discriminated union.
But I maintain my opinion that this is not the purpose of the Visitor pattern. I would go so far as to say that this is an anti-pattern. The visitor pattern is only useful when your model actually needs double dispatch - when you have a hierarchy of types with proper subtypes that need to be handled by a hierarchy of operations. If you do have this problem, the only solutions are the visitor pattern or native multiple dispatch like in CLOS. ADTs and pattern matching can't solve this problem.