Simplified visitor pattern

447 views Asked by At

Here is a visitor pattern implemented in Java to evaluate an expression like (1 + 2) + 3. The code here is inspired by the code example at: https://en.wikipedia.org/wiki/Visitor_pattern#Sources.

interface Node
{
    public int accept(Visitor v);
}

class ConstantNode implements Node
{
    public int constant;

    public ConstantNode(int constant)
    {
        this.constant = constant;
    }

    public int accept(Visitor v) {
        return v.visit(this);
    }
}

class SumNode implements Node
{
    public Node left;
    public Node right;

    public SumNode(Node left, Node right)
    {
        this.left = left;
        this.right = right;
    }

    public int accept(Visitor v) {
        return v.visit(this);
    }
}

interface Visitor
{
    public int visit(ConstantNode n);
    public int visit(SumNode n);
}

class EvalVisitor implements Visitor
{
    public int visit(ConstantNode n) {
        return n.constant;
    }

    public int visit(SumNode n) {
        return n.left.accept(this) + n.right.accept(this);
    }
}

public class VisitorDemo
{
    public static void main(String[] args)
    {
        // First make an expression tree to represent the following.
        //
        //        +
        //       / \
        //      +   3
        //     / \
        //    1   2
        Node a = new ConstantNode(1);
        Node b = new ConstantNode(2);
        Node c = new ConstantNode(3);
        Node d = new SumNode(a, b);
        Node e = new SumNode(d, c);

        Visitor visitor = new EvalVisitor();
        int result = e.accept(visitor);
        System.out.println(result);
    }
}

I understand that at each level of recursion, which visit() method to invoke depends on the type of the visitor (in this case evalVisitor) as well as on the type of the node (ConstantNode or SumNode), hence the need for double dispatch. But this kind of coding to implement double dispatch using accept() and visit() methods seem too convoluted to me. But almost all examples of visitor pattern I have seen use this approach of passing the visitor to the node via accept() which in turn calls the visitor's visit() method to perform double-dispatch.

Why can't the code examples be simpler like this?

interface Node
{
}

class ConstantNode implements Node
{
    public int constant;

    public ConstantNode(int constant)
    {
        this.constant = constant;
    }
}

class SumNode implements Node
{
    public Node left;
    public Node right;

    public SumNode(Node left, Node right)
    {
        this.left = left;
        this.right = right;
    }
}

interface Visitor
{
    public int visit(Node n) throws Exception;
}

class EvalVisitor implements Visitor
{
    public int visit(Node n) throws Exception {
        if (n instanceof ConstantNode) {
            return ((ConstantNode) n).constant;
        } else if (n instanceof SumNode) {
            return this.visit(((SumNode) n).left) + this.visit(((SumNode) n).right);
        } else {
            throw new Exception("Unsupported node");
        }
    }
}

public class SimpleVisitorDemo
{
    public static void main(String[] args) throws Exception
    {
        // First make an expression tree to represent the following.
        //
        //        +
        //       / \
        //      +   3
        //     / \
        //    1   2
        Node a = new ConstantNode(1);
        Node b = new ConstantNode(2);
        Node c = new ConstantNode(3);
        Node d = new SumNode(a, b);
        Node e = new SumNode(d, c);

        Visitor visitor = new EvalVisitor();
        int result = visitor.visit(e);
        System.out.println(result);
    }
}

In this code sample, I have completely eliminated the need to implement apply() in each node and the total logic of visiting including the logic for double dispatch is now contained within the visitor class only.

I have the following question:

Can you objectively enumerate the problems with the simplified visitor pattern in terms of maintanability or efficiency of the code?

1

There are 1 answers

4
Sergey Kalinichenko On BEST ANSWER

Why can't the code examples be simpler, [...]

Because your example replaces a virtual dispatch with a switch dispatch (which you implemented as a chain of ifs on the object subtype). This approach is extremely hard to maintain, because you get no help from the compiler in detecting changes to your inheritance hierarchy.

The specific problem with the simplified implementation is in that last else, where you return zero. A more common solution is to throw an exception there, because you really don't know what kind of node you've got.

Now imagine extending the hierarchy with, say, a SubtractNode. This would naturally require an addition of a method to Visitor interface, making sure that all visitors are forced to handle the new node subtype at compile time.

Simplified example, on the other hand, would continue to compile, and in your case, it would also continue to run, returning a wrong result for SubtractNode.