Implementando o padrão de visitante para uma árvore de sintaxe abstrata

Estou no processo de criar minha própria linguagem de programação, o que faço para fins de aprendizado. Eu já escrevi o lexer e um analisador de descida recursiva para um subconjunto da minha linguagem (atualmente, suporte expressões matemáticas, como + - * /parênteses e). O analisador devolve uma Árvore de Sintaxe Abstrata, na qual chamo o Evaluatemétodo para obter o resultado da expressão. Tudo funciona bem. Aqui está aproximadamente minha situação atual (exemplos de código em C #, embora isso seja praticamente independente do idioma):

public abstract class Node
{
    public abstract Double Evaluate();
}

public class OperationNode : Node
{
    public Node Left { get; set; }
    private String Operator { get; set; }
    private Node Right { get; set; }

    public Double Evaluate()
    {
        if (Operator == "+")
            return Left.Evaluate() + Right.Evaluate();

        //Same logic for the other operators
    }
}

public class NumberNode : Node
{
    public Double Value { get; set; }

    public Double Evaluate()
    {
        return Value;
    }
}

No entanto, eu gostaria de desacoplar o algoritmo dos nós da árvore, porque quero aplicar o Princípio Aberto / Fechado, para não precisar reabrir todas as classes de nós quando desejar implementar a geração de código, por exemplo. Eu li que o Padrão do Visitante é bom para isso. Eu tenho um bom entendimento de como o padrão funciona e que usar o envio duplo é o caminho a seguir. Mas, devido à natureza recursiva da árvore, não tenho certeza de como devo abordá-la. Aqui está a aparência do meu visitante:

public class AstEvaluationVisitor
{
    public void VisitOperation(OperationNode node)
    {
        // Here is where I operate on the operation node.
        // How do I implement this method?
        // OperationNode has two child nodes, which may have other children
        // How do I work the Visitor Pattern around a recursive structure?

        // Should I access children nodes here and call their Accept method so they get visited? 
        // Or should their Accept method be called from their parent's Accept?
    }

    // Other Visit implementation by Node type
}

Então esse é o meu problema. Quero abordá-lo imediatamente, enquanto meu idioma não suporta muita funcionalidade para evitar problemas maiores posteriormente.

Não publiquei isso no StackOverflow porque não quero que você forneça uma implementação. Eu só quero que você compartilhe idéias e conceitos que eu possa ter perdido, e como devo abordar isso.

Cabe à implementação do visitante decidir se os nós filhos devem ser visitados e em que ordem. Esse é o objetivo do padrão de visitantes.

Para adaptar o visitante a mais situações, é útil (e bastante comum) usar genéricos como este (é Java):

public interface ExpressionNodeVisitor<R, P> {
    R visitNumber(NumberNode number, P p);
    R visitBinary(BinaryNode expression, P p);
    // ...
}

E um acceptmétodo ficaria assim:

public interface ExpressionNode extends Node {
    <R, P> R accept(ExpressionNodeVisitor<R, P> visitor, P p);
    // ...
}

Isso permite passar parâmetros adicionais ao visitante e recuperar um resultado dele. Portanto, a avaliação da expressão pode ser implementada assim:

public class EvaluatingVisitor
    implements ExpressionNodeVisitor<Double, Void> {
    public Double visitNumber(NumberNode number, Void p) {
        // Parse the number and return it.
        return Double.valueOf(number.getText());
    }
    public Double visitBinary(BinaryNode binary, Void p) {
        switch (binary.getOperator()) {
        case '+':
            return binary.getLeftOperand().accept(this, p)
                + binary.getRightOperand().accept(this, p);
        // More cases for other operators here.
        }
    }
}

O acceptparâmetro method não é usado no exemplo acima, mas acredite: é bastante útil ter um. Por exemplo, pode ser uma instância do Logger para a qual relatar erros.

Eu implementei o padrão de visitante em uma árvore recursiva antes.

Minha estrutura de dados recursiva específica era extremamente simples - apenas três tipos de nós: o nó genérico, um nó interno que tem filhos e um nó folha que possui dados. Isso é muito mais simples do que eu esperava que o seu AST, mas talvez as idéias possam ser ampliadas.

No meu caso, deliberadamente, não permiti que o Accept de um nó com filhos chamas Accept em seus filhos ou chamas visitor.Visit (child) de dentro do Accept. É de responsabilidade da implementação correta do membro "Visit" do visitante delegar Aceites para filhos do nó que está sendo visitado. Eu escolhi esse caminho porque queria permitir que diferentes implementações do Visitor pudessem decidir a ordem da visitação independentemente da representação em árvore.

Um benefício secundário é que quase não há artefatos do padrão Visitor nos meus nós da árvore - cada "Accept" chama apenas "Visit" no visitante com o tipo de concreto correto. Isso facilita a localização e a compreensão da lógica da visita, tudo dentro da implementação do visitante.

Para maior clareza, adicionei alguns pseudocódigos em C ++. Primeiro os nós:

class INode {
  public:
    virtual void Accept(IVisitor& i_visitor) = 0;
};

class NodeWithChildren : public INode {
  public:
     virtual void Accept(IVisitor& i_visitor) override {
        i_visitor.Visit(*this);
     }
     // Plus interface for getting the children, exercise for the reader ;-)
 };

 class LeafNode : public INode {
   public:
     virtual void Accept(IVisitor& i_visitor) override {
       i_visitor.Visit(*this);
     }
 };

E o visitante:

class IVisitor {
  public:
     virtual void Visit(NodeWithChildren& i_node) = 0;
     virtual void Visit(LeafNode& i_node) = 0;
};

class ConcreteVisitor : public IVisitor
  public:
     virtual void Visit(NodeWithChildren& i_node) override {
       // Do something useful, then...
       for(Node * p_child : i_node) {
         child->Accept(*this);
       }
     }

     virtual void Visit(LeafNode& i_node) override {
        // Just do something useful, there are no children.
     }

};

Você trabalha o padrão de visitante em torno de uma estrutura recursiva da mesma maneira que faria qualquer outra coisa com sua estrutura recursiva: visitando os nós em sua estrutura recursivamente.

public class OperationNode
{
    public int SomeProperty { get; set; }
    public List<OperationNode> Children { get; set; }
}

public static void VisitNode(OperationNode node)
{
    ... Visit this node

    foreach(var node in Children)
    {
         VisitNode(node);
    }
}

public static void VisitAllNodes()
{
    VisitNode(rootNode);
}