title: What's the best way to implement AST using visitor pattern with return value?
body: <p>I'm trying to implement a simple abstract syntax tree (AST) in C++ using the visitor pattern. Usually a visitor pattern does not handle return value. But in my AST there are expressions nodes which care about the return type and value of its children node. For example, I have a Node structure like this:</p>
  
  <pre><code>class AstNode
  {
  public:
      virtual void accept(AstNodeVisitor&amp;) = 0;
  
      void addChild(AstNode* child);
      AstNode* left() { return m_left; }
      AstNode* right() { return m_right; }
  ...
  
  private:
      AstNode* m_left;
      AstNode* m_right;
  };
  
  class CompareNode : public AstNode
  {
  public:
      virtual void accept(AstNodeVisitor&amp; v)
      {
          v-&gt;visitCompareNode(this);
      }
  
      bool eval(bool lhs, bool rhs) const
      {
          return lhs &amp;&amp; rhs;
      }
  };
  
  class SumNode : public AstNode
  {
  public:
      virtual void accept(AstNodeVisitor&amp; v)
      {
          v-&gt;visitSumNode(this);
      }
  
      int eval(int lhs, int rhs) const
      {
          return lhs + rhs;
      }
  };
  
  class AstNodeVisitor
  {
  public:
      ...
      bool visitCompareNode(CompareNode&amp; node)
      {
          // won't work, because accept return void!
          bool lhs = node.left()-&gt;accept(*this);
          bool rhs = node.right()-&gt;accept(*this);
          return node.eval(lhs, rhs);
      }
  
      int visitSumNode(Node&amp; node)
      {
          // won't work, because accept return void!
          int lhs = node.left()-&gt;accept(*this);
          int rhs = node.right()-&gt;accept(*this);
          return node.eval(lhs, rhs);
      }
  };
  </code></pre>
  
  <p>In this case both CompareNode and SumNode are binary operators but they rely on the return type of their children's visit. </p>
  
  <p>As far as I can see to make it work, there are only 2 options:</p>
  
  <ol>
  <li><p>accept can still return void, save the return value in a context object which is passed to each accept and visit function, and use them in the visit function, where I know what type to use. This should work but feels like a hack.</p></li>
  <li><p>make AstNode a template, and accept function a none virtual, but return type depends on template parameter T.But if I do this, I no longer have a common AstNode* class and can't save any AstNode* in the children list.</p></li>
  </ol>
  
  <p>for example:</p>
  
  <pre><code>template &lt;typename T`&gt;
  class AstNode
  {
  public:
      T accept(AstNodeVisitor&amp;);
      ...
  };
  </code></pre>
  
  <p>So is there a more elegant way to do this? This should be a fairly common problem for people implementing AST walking so I'd like to know what's the best practice.</p>
  
  <p>Thanks.</p>