Visitor with the Return Value

• Download source - 1.2 KB

Introduction

Conventional implementation of Visitor interface looks like this:

class IVisitor
{
    virtual void Visit(Type1& o) = 0;
    virtual void Visit(Type2& o) = 0;
    virtual void Visit(Type3& o) = 0;
    /*...*/
};

All the methods are void, so there is no straightforward way to return value when visiting the object from the class hierarchy. This tip shows the generic way to implement visitors that can return values without the need to change the visited hierarchy.

Example: Evaluating the Expression

Let's have a very simple expression tree class hierarchy with just two types of node - Number, representing the integral value, and Plus, representing the addition of two expressions (Nodes):

// root of the class hierarchy
class Node
{
};
using NodePtr = shared_ptr<Node>;

// integer
class Number : public Node
{
public:
    Number(int value_) : value{ value_ } {}

    int value;
};

// addition
class Plus : public Node
{
public:
    Plus(NodePtr left_, NodePtr right_) : left{ left_ }, right{ right_ }{}

    NodePtr left, right;
};

//////////////////////////////////////////////////////////////////////////
// helper free functions for creating the expression tree
shared_ptr<plus> plus(NodePtr left, NodePtr right) { return make_shared<plus>(left, right); }
shared_ptr<number> number(int value) { return make_shared<number>(value); }

So we can create an expression e.g. like this:

auto expr = plus(number(3), plus(number(5), number(7))); // (3 + (5 + 7))

Now we want to evaluate this expression. The easiest and most natural way to do it is to traverse the expression recursively and compute the partial values of every subtree, so the value of the Plus node is the sum of the values of both of its subnodes and the value of the Number node is the number associated to it.

It's a good practice to decouple the operation (evaluation) from the data (expression tree) as much as possible. Visitor pattern will help us do it. Let's make our expression tree objects visitable (changes are bold):

// root of the class hierarchy
class Node
{
public:
    virtual void Accept(INodeVisitor& vis) = 0;
};
// helper macro for easy definition of visitor pattern bouncing function
#define MAKE_VISITABLE virtual void Accept(INodeVisitor& vis) override { vis.Visit(*this);}

using NodePtr = shared_ptr<Node>;
 // integer
class Number : public Node
{
public:
    Number(int value_) : value{ value_ } {}
    int value;
    MAKE_VISITABLE
};

 // addition
class Plus : public Node
{
public:
    Plus(NodePtr left_, NodePtr right_) : left{ left_ }, right{ right_ }{}

    NodePtr left, right;
    MAKE_VISITABLE
};

But here we need to return the value from the evaluation of subtree so that we can combine them. How to do that without invading the tree hierarchy definition?

Enter ValueGetter

We will define ValueGetter, generic helper class for visitor to store computed values in local objects and to retrieve them on demand:

template<typename VisitorImpl, typename VisitablePtr, typename ResultType>
class ValueGetter
{
public:
    static ResultType GetValue(VisitablePtr n)
    {
        VisitorImpl vis;
        n->Accept(vis); // this call fills the return value
        return vis.value;
    }

    void Return(ResultType value_)
    {
        value = value_;
    }
private:
    ResultType value;
};

The GetValue static function does the following:

• Creates a new instance of a visitor
• Lets the visitor process given node via standard Accept -> Visit bounce
• Returns value stored by this processing

The Return method allows concrete visitor (the class derived from ValueGetter) to store the result.

The template parameters of the class are concrete implementation of the visitor, pointer to the visitable class hierarchy and result type of the visitation. We'll see this on the concrete example later.

Using the ValueGetter to Create Evaluator

Now, we can derive from ValueGetter to create our Evaluator visiting class:

class Evaluator : public ValueGetter<Evaluator, NodePtr, int>, public INodeVisitor
{
public:
    virtual void Visit(Number& n)
    {
        // Store the return value in the ValueGetter member
        Return(n.value);
    }

    virtual void Visit(Plus& n)
    {
        // GetValue visits children and returns computed values
        Return(GetValue(n.left) + GetValue(n.right));
    }
};

It derives from ValueGetter by Curiously Recurring Template Pattern so that the ValueGetter can instantiate the Evaluator itself. It also implements INodeVisitor interface the conventional way - overriding all overloads of Visit virtual method for every type of supported node.

Another Visitor: Serializator

With the help of ValueGetter template class, it is now very easy to implement more visitors with any return type. Let's make one more for the expression tree: Serializator. The job of Serializator is to return the textual representation of the expression, e. g. "(3 + (5 + 7))". While this would be also possible with cannonical visitor, with ValueGetter it is even easier and instructive for our case:

class Serializer : public ValueGetter<Serializer, NodePtr, string>, public INodeVisitor
{
public:
    virtual void Visit(Number& n)
    {
        Return(to_string(n.value));
    }

    virtual void Visit(Plus& n)
    {
        Return("(" + GetValue(n.left) + " + " + GetValue(n.right) + ")");
    }
};

The number is simply converted to the string, while the Plus is serialized as "(<left_subtree_value> + <right_subtree_value>)". And this is it. If we use it in the program:

auto expr = plus(number(3), plus(number(5), number(7))); // (3 + (5 + 7))
cout << Serializer::GetValue(expr) << " = " << Evaluator::GetValue(expr) << endl;

we get the following output:

(3 + (5 + 7)) = 15

References

• Visitor Pattern on Wikipedia
• Curiously Recurring Template Pattern on Wikipedia