Qual é o ponto do método accept () no padrão Visitor?

Fala-se muito sobre separar os algoritmos das classes. Mas, uma coisa fica de lado não explicada.

Eles usam visitante assim

abstract class Expr {
  public <T> T accept(Visitor<T> visitor) {visitor.visit(this);}
}

class ExprVisitor extends Visitor{
  public Integer visit(Num num) {
    return num.value;
  }

  public Integer visit(Sum sum) {
    return sum.getLeft().accept(this) + sum.getRight().accept(this);
  }

  public Integer visit(Prod prod) {
    return prod.getLeft().accept(this) * prod.getRight().accept(this);
  }

Em vez de chamar visit (elemento) diretamente, Visitor pede ao elemento para chamar seu método visit. Isso contradiz a ideia declarada de desconhecimento da classe sobre os visitantes.

PS1 Explique com suas próprias palavras ou aponte a explicação exata. Porque duas respostas que obtive referem-se a algo geral e incerto.

PS2 Meu palpite: Como getLeft()retorna o básico Expression, chamandovisit(getLeft()) resultaria em visit(Expression), enquanto a getLeft()chamada visit(this)resultaria em outra invocação de visita mais apropriada. Então, accept()realiza a conversão de tipo (também conhecido como casting).

PS3 Scala's Pattern Matching = Visitor Pattern on Steroid mostra como o padrão Visitor é muito mais simples sem o método accept. A Wikipedia acrescenta a esta afirmação : vinculando um artigo mostrando "que os accept()métodos são desnecessários quando a reflexão está disponível; introduz o termo 'Walkabout' para a técnica."

O padrão do visitante visit/accept construções são um mal necessário devido à semântica das linguagens C-like (C #, Java, etc.). O objetivo do padrão de visitante é usar o despacho duplo para rotear sua chamada como você esperaria da leitura do código.

Normalmente, quando o padrão de visitante é usado, uma hierarquia de objeto está envolvida em que todos os nós são derivados de um Nodetipo base , denominado doravante Node. Instintivamente, escreveríamos assim:

Node root = GetTreeRoot();
new MyVisitor().visit(root);

Aqui está o problema. Se nossa MyVisitorclasse foi definida da seguinte forma:

class MyVisitor implements IVisitor {
  void visit(CarNode node);
  void visit(TrainNode node);
  void visit(PlaneNode node);
  void visit(Node node);
}

Se, em tempo de execução, independentemente do tipo realroot , nossa chamada iria para a sobrecarga visit(Node node). Isso seria verdadeiro para todas as variáveis ​​declaradas do tipo Node. Por que é isso? Porque Java e outras linguagens semelhantes a C consideram apenas o tipo estático , ou o tipo como a variável é declarada, do parâmetro ao decidir qual sobrecarga chamar. Java não dá o passo extra para perguntar, para cada chamada de método, em tempo de execução, "Ok, qual é o tipo dinâmico de root? Ah, entendo. É a TrainNode. Vamos ver se há algum método MyVisitorque aceita um parâmetro do tipoTrainNode... ". O compilador, em tempo de compilação, determina qual é o método que será chamado. (Se o Java realmente inspecionasse os tipos dinâmicos dos argumentos, o desempenho seria péssimo.)

Java nos dá uma ferramenta para levar em consideração o tipo de tempo de execução (ou seja, dinâmico) de um objeto quando um método é chamado - envio de método virtual . Quando chamamos um método virtual, a chamada realmente vai para uma tabela na memória que consiste em ponteiros de função. Cada tipo possui uma mesa. Se um método específico for substituído por uma classe, a entrada da tabela de funções dessa classe conterá o endereço da função substituída. Se a classe não sobrescrever um método, ela conterá um ponteiro para a implementação da classe base. Isso ainda incorre em uma sobrecarga de desempenho (cada chamada de método basicamente desreferencia dois ponteiros: um apontando para a tabela de funções do tipo e outro da própria função), mas ainda é mais rápido do que inspecionar os tipos de parâmetros.

O objetivo do padrão de visitante é realizar o despacho duplo - não apenas o tipo de destino da chamada é considerado ( MyVisitorpor meio de métodos virtuais), mas também o tipo do parâmetro (que tipo Nodeestamos olhando)? O padrão Visitor nos permite fazer isso pela combinação visit/ accept.

Mudando nossa linha para esta:

root.accept(new MyVisitor());

Podemos obter o que queremos: via envio de método virtual, inserimos a chamada aceita () correta conforme implementada pela subclasse - em nosso exemplo com TrainElement, inseriremos TrainElementa implementação de accept():

class TrainNode extends Node implements IVisitable {
  void accept(IVisitor v) {
    v.visit(this);
  }
}

O que faz o know compilador neste momento, dentro do âmbito da TrainNode's accept? Sabe que o tipo estático de thisé aTrainNode . Este é um fragmento adicional importante de informação que o compilador não estava ciente no escopo de nosso chamador: lá, tudo o que ele sabia rootera que era um Node. Agora, o compilador sabe que this( root) não é apenas um Node, mas na verdade é um TrainNode. Em conseqüência, a única linha encontrada dentro de accept():, v.visit(this)significa algo totalmente diferente. O compilador agora procurará por uma sobrecarga de visit()que leva a TrainNode. Se não conseguir encontrar um, ele irá compilar a chamada para uma sobrecarga que leva umNode. Se nenhum dos dois existir, você obterá um erro de compilação (a menos que haja uma sobrecarga object). A execução entrará, portanto, no que pretendíamos o tempo todo: MyVisitora implementação de visit(TrainNode e). Nenhum molde foi necessário e, mais importante, nenhuma reflexão foi necessária. Portanto, a sobrecarga desse mecanismo é bastante baixa: ele consiste apenas em referências de ponteiro e nada mais.

Você está certo em sua pergunta - podemos usar um gesso e obter o comportamento correto. No entanto, muitas vezes, nem sabemos que tipo de nó é. Considere o caso da seguinte hierarquia:

abstract class Node { ... }
abstract class BinaryNode extends Node { Node left, right; }
abstract class AdditionNode extends BinaryNode { }
abstract class MultiplicationNode extends BinaryNode { }
abstract class LiteralNode { int value; }

E estávamos escrevendo um compilador simples que analisa um arquivo de origem e produz uma hierarquia de objetos que está em conformidade com a especificação acima. Se estivéssemos escrevendo um intérprete para a hierarquia implementada como Visitante:

class Interpreter implements IVisitor<int> {
  int visit(AdditionNode n) {
    int left = n.left.accept(this);
    int right = n.right.accept(this); 
    return left + right;
  }
  int visit(MultiplicationNode n) {
    int left = n.left.accept(this);
    int right = n.right.accept(this);
    return left * right;
  }
  int visit(LiteralNode n) {
    return n.value;
  }
}

O casting não nos levaria muito longe, pois não conhecemos os tipos de leftou rightnos visit()métodos. Nosso analisador provavelmente também retornaria um objeto do tipo Nodeque também apontasse para a raiz da hierarquia, portanto, também não podemos lançar isso com segurança. Portanto, nosso intérprete simples pode ser semelhante a:

Node program = parse(args[0]);
int result = program.accept(new Interpreter());
System.out.println("Output: " + result);

O padrão de visitante nos permite fazer algo muito poderoso: dada uma hierarquia de objeto, ele nos permite criar operações modulares que operam sobre a hierarquia sem a necessidade de colocar o código na própria classe da hierarquia. O padrão de visitante é amplamente usado, por exemplo, na construção do compilador. Dada a árvore de sintaxe de um programa específico, muitos visitantes são escritos para operar nessa árvore: verificação de tipo, otimizações, emissão de código de máquina são geralmente implementados como visitantes diferentes. No caso do visitante de otimização, ele pode até gerar uma nova árvore de sintaxe dada a árvore de entrada.

Isso tem suas desvantagens, é claro: se adicionarmos um novo tipo à hierarquia, precisamos também adicionar um visit()método para esse novo tipo na IVisitorinterface e criar implementações stub (ou completas) em todos os nossos visitantes. Também precisamos adicionar o accept()método, pelas razões descritas acima. Se desempenho não significa muito para você, existem soluções para escrever visitantes sem precisar do accept(), mas normalmente envolvem reflexão e, portanto, podem incorrer em uma grande sobrecarga.

Claro que isso seria idiota se essa fosse a única maneira de o Accept ser implementado.

Mas não é.

Por exemplo, os visitantes são realmente úteis ao lidar com hierarquias, caso em que a implementação de um nó não terminal pode ser algo como este

interface IAcceptVisitor<T> {
  void Accept(IVisit<T> visitor);
}
class HierarchyNode : IAcceptVisitor<HierarchyNode> {
  public void Accept(IVisit<T> visitor) {
    visitor.visit(this);
    foreach(var n in this.children)
      n.Accept(visitor);
  }

  private IEnumerable<HierarchyNode> children;
  ....
}

Entende? O que você descreve como estúpido é a solução para atravessar hierarquias.

Aqui está um artigo muito mais longo e aprofundado que me fez entender o visitante .

Editar: Para esclarecer: O Visitmétodo do visitante contém lógica a ser aplicada a um nó. O Acceptmétodo do nó contém lógica sobre como navegar para nós adjacentes. O caso em que você só faz o despacho duplo é um caso especial em que simplesmente não há nós adjacentes para os quais navegar.

O objetivo do padrão Visitor é garantir que os objetos saibam quando o visitante terminou com eles e partiu, para que as classes possam realizar qualquer limpeza necessária posteriormente. Ele também permite que as classes exponham seus internos "temporariamente" como parâmetros 'ref' e saibam que os internos não serão mais expostos quando o visitante se for. Nos casos em que nenhuma limpeza é necessária, o padrão do visitante não é extremamente útil. As classes que não fazem nenhuma dessas coisas podem não se beneficiar do padrão de visitante, mas o código que é escrito para usar o padrão de visitante poderá ser usado com classes futuras que podem exigir limpeza após o acesso.

Por exemplo, suponha que se tenha uma estrutura de dados contendo muitas strings que devem ser atualizadas atomicamente, mas a classe que contém a estrutura de dados não sabe exatamente quais tipos de atualizações atômicas devem ser realizadas (por exemplo, se uma thread deseja substituir todas as ocorrências de " X ", enquanto outro encadeamento deseja substituir qualquer sequência de dígitos por uma seqüência numericamente superior, as operações de ambos os encadeamentos devem ser bem-sucedidas; se cada encadeamento simplesmente ler um string, realizar suas atualizações e escrevê-lo de volta, o segundo encadeamento escrever de volta sua string sobrescreveria a primeira). Uma maneira de fazer isso seria fazer com que cada thread adquira um bloqueio, execute sua operação e libere o bloqueio. Infelizmente, se os bloqueios forem expostos dessa forma,

O padrão Visitante oferece (pelo menos) três abordagens para evitar esse problema:

1. Ele pode bloquear um registro, chamar a função fornecida e, em seguida, desbloquear o registro; o registro pode ser bloqueado para sempre se a função fornecida cair em um loop infinito, mas se a função fornecida retornar ou lançar uma exceção, o registro será desbloqueado (pode ser razoável marcar o registro como inválido se a função lançar uma exceção; deixando provavelmente não é uma boa ideia). Observe que é importante que, se a função chamada tentar adquirir outros bloqueios, pode ocorrer um deadlock.
2. Em algumas plataformas, ele pode passar um local de armazenamento contendo a string como um parâmetro 'ref'. Essa função poderia então copiar a string, calcular uma nova string com base na string copiada, tentar CompararExchange a string antiga para a nova e repetir todo o processo se CompareExchange falhar.
3. Ele pode fazer uma cópia da string, chamar a função fornecida na string, usar o próprio CompareExchange para tentar atualizar o original e repetir todo o processo se o CompareExchange falhar.

Sem o padrão de visitante, a execução de atualizações atômicas exigiria a exposição de bloqueios e o risco de falha se o software de chamada não seguir um protocolo de bloqueio / desbloqueio estrito. Com o padrão Visitor, as atualizações atômicas podem ser feitas com relativa segurança.

Todas as classes que requerem modificação devem implementar o método 'aceitar'. Os clientes chamam esse método de aceitação para realizar alguma nova ação naquela família de classes, estendendo assim sua funcionalidade. Os clientes podem usar este método de aceitação para executar uma ampla gama de novas ações, passando uma classe de visitante diferente para cada ação específica. Uma classe de visitante contém vários métodos de visita substituídos que definem como alcançar a mesma ação específica para cada classe dentro da família. Esses métodos de visita passam uma instância na qual trabalhar.

Os visitantes são úteis se você frequentemente adiciona, altera ou remove funcionalidade de uma família estável de classes, porque cada item de funcionalidade é definido separadamente em cada classe de visitante e as próprias classes não precisam ser alteradas. Se a família de classes não for estável, o padrão do visitante pode ser menos útil, porque muitos visitantes precisam ser alterados sempre que uma classe é adicionada ou removida.

Um bom exemplo está na compilação do código-fonte:

interface CompilingVisitor {
   build(SourceFile source);
}

Os clientes podem implementar um JavaBuilder, RubyBuilder,XMLValidator , etc. e a implementação de coleta e visitar todos os arquivos de origem em um projeto não precisa de mudança.

Este seria um padrão ruim se você tivesse classes separadas para cada tipo de arquivo de origem:

interface CompilingVisitor {
   build(JavaSourceFile source);
   build(RubySourceFile source);
   build(XMLSourceFile source);
}

Tudo se resume ao contexto e às partes do sistema que você deseja que sejam extensíveis.