В чем смысл метода accept () в шаблоне Visitor?

Question

Существует много разговоров о разделении алгоритмов от классов.Но одна вещь остается в стороне, не объяснил.

Они используют посетителя как этот

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);
  }

Вместо непосредственного вызова посещения (элемента), Посетитель просит элемент вызвать его метод посещения.Это противоречит заявленной идее классовой неосведомленности о посетителях.

PS1 Пожалуйста, объясните своими словами или укажите точное объяснение.Потому что два ответа, которые я получил, относятся к чему-то общему и неопределенному.

PS2 Мое предположение: поскольку getLeft() возвращает базовый Expression, вызов visit(getLeft()) приведет к visit(Expression), тогда как getLeft() вызов visit(this) приведет к другому, более подходящему вызову посещения,Так, accept() выполняет преобразование типов (также называемое приведением).

PS3 Сопоставление с образцом Scala = Образец посетителя на стероиде показывает, насколько проще образец Посетителя без метода accept. Википедия добавляет к этому утверждению : с помощью ссылки на статью, показывающую, что "методы accept() не нужны, когда доступно отражение; вводится термин" Прогулка "для этой техники".

Answer 1

Конструкции visit / accept шаблона посетителя являются необходимым злом из-за семантики C-подобных языков (C #, Java и т. Д.). Цель шаблона посетителя - использовать двойную диспетчеризацию для маршрутизации вашего вызова, как и следовало ожидать от чтения кода.

Обычно, когда используется шаблон посетителя, используется иерархия объектов, в которой все узлы являются производными от базового типа Node, далее именуемого Node. Инстинктивно мы написали бы это так:

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

В этом и заключается проблема. Если наш класс MyVisitor был определен следующим образом:

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

Если во время выполнения, независимо от фактического типа, которым является root, наш вызов перейдет в перегрузку visit(Node node). Это будет верно для всех переменных, объявленных типа Node. Почему это? Поскольку Java и другие C-подобные языки учитывают только статический тип или тип, в котором объявлена ​​переменная, параметра при решении, какую перегрузку вызывать. Java не делает лишних шагов, чтобы спросить для каждого вызова метода во время выполнения: «Хорошо, каков динамический тип root? О, я вижу. Это TrainNode. Давайте посмотрим, есть ли какой-либо метод в MyVisitor, который принимает параметр типа TrainNode ... ". Компилятор во время компиляции определяет, какой метод будет вызван. (Если бы Java действительно проверяла динамические типы аргументов, производительность была бы ужасной.)

Java предоставляет нам один инструмент для учета типа объекта во время выполнения (то есть динамического) при вызове метода - диспетчеризация виртуального метода . Когда мы вызываем виртуальный метод, этот вызов фактически переходит в таблицу в памяти, которая состоит из указателей функций. У каждого типа есть таблица. Если определенный метод переопределен классом, запись таблицы функций этого класса будет содержать адрес переопределенной функции. Если класс не переопределяет метод, он будет содержать указатель на реализацию базового класса. Это по-прежнему приводит к снижению производительности (каждый вызов метода в основном будет разыменовывать два указателя: один указывает на таблицу функций типа, а другой - на саму функцию), но это все же быстрее, чем проверка типов параметров.

Целью шаблона посетителя является выполнение двойной отправки - не только тип рассматриваемой цели вызова (MyVisitor, через виртуальные методы), но также тип параметра (на какой тип Node мы смотрим)? Шаблон Visitor позволяет нам делать это с помощью комбинации visit / accept.

Изменив нашу строку следующим образом:

root.accept(new MyVisitor());

Мы можем получить то, что хотим: с помощью диспетчеризации виртуальных методов мы вводим правильный вызов accept (), реализованный подклассом - в нашем примере с TrainElement мы введем реализацию TrainElement accept()

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

Что знает компилятор на данный момент в пределах TrainNode accept? Он знает, что статический тип this является TrainNode. Это важная дополнительная информация, которую компилятор не знал в области действия нашего вызывающего: там все, что он знал о root, это то, что это Node. Теперь компилятор знает, что this (root) - это не просто Node, а на самом деле TrainNode. Следовательно, одна строка, найденная внутри accept(): v.visit(this), означает что-то еще целиком. Компилятор теперь будет искать перегрузку visit(), которая занимает TrainNode. Если он не может его найти, он скомпилирует вызов с перегрузкой, которая принимает Node. Если ничего не существует, вы получите ошибку компиляции (если у вас нет перегрузки, которая занимает object). Таким образом, выполнение будет соответствовать тому, что мы планировали: реализация MyVisitor visit(TrainNode e). Никаких бросков не было, и, самое главное, не нужно было никакого отражения. Таким образом, издержки этого механизма довольно низки: он состоит только из ссылок на указатели и ничего больше.

Вы правы в своем вопросе - мы можем использовать приведение и получить правильное поведение. Однако часто мы даже не знаем, что это за тип Node. Возьмите случай следующей иерархии:

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; }

И мы писали простой компилятор, который анализирует исходный файл и создает иерархию объектов, соответствующую приведенной выше спецификации. Если бы мы писали интерпретатор для иерархии, реализованной как посетитель:

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;
  }
}

Кастинг не продвинет нас слишком далеко, так как мы не знаем типы left или right в visit() методах. Наш синтаксический анализатор, скорее всего, также просто вернет объект типа Node, который также указывает на корень иерархии, поэтому мы также не можем безопасно его привести. Так что наш простой интерпретатор может выглядеть так:

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

Шаблон посетителя позволяет нам делать что-то очень мощное: с учетом иерархии объектов он позволяет создавать модульные операции, которые работают над иерархией, не требуя помещения кода в сам класс иерархии. Шаблон посетителя широко используется, например, при построении компилятора. Учитывая синтаксическое дерево конкретной программы, написано много посетителей, которые оперируют этим деревом: проверка типов, оптимизация, выдача машинного кода, как правило, реализуются как разные посетители. В случае посетителя оптимизации, он может даже вывести новое синтаксическое дерево с учетом входного дерева.

Конечно, у него есть свои недостатки: если мы добавляем новый тип в иерархию, нам нужно также добавить метод visit() для этого нового типа в интерфейс IVisitor и создать заглушки (или полные) реализации. во всех наших посетителей. Нам также необходимо добавить метод accept() по причинам, описанным выше. Если производительность не так много значит для вас, существуют решения для написания посетителей без необходимости accept(), но они обычно включают рефлексию и, следовательно, могут повлечь за собой довольно большие накладные расходы.

Answer 2

Конечно, было бы глупо, если бы это был только способ реализации Accept.

Но это не так.

Например, посетители действительно очень полезны при работе с иерархиями, и в этом случае реализация нетерминального узла может выглядеть примерно так

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;
  ....
}

Видишь? То, что вы описываете как глупое, является решением для обхода иерархий.

Вот гораздо более длинная и глубокая статья, которая заставила меня понять посетителя .

Edit: Для пояснения: метод посетителя Visit содержит логику, которая будет применена к узлу. Метод узла Accept содержит логику навигации по соседним узлам. Случай, когда вы only double dispatch, является особым случаем, когда просто нет соседних узлов для навигации.

Answer 3

Все классы, которые требуют модификации, должны реализовывать метод accept.Клиенты вызывают этот метод accept для выполнения некоторых новых действий с этим семейством классов, расширяя их функциональность.Клиенты могут использовать этот метод accept для выполнения широкого спектра новых действий, передавая разные классы посетителей для каждого конкретного действия.Класс посетителя содержит несколько переопределенных методов посещения, определяющих, как выполнить одно и то же конкретное действие для каждого класса в семье.Этим методам посещения передается экземпляр, с которым нужно работать.

Посетители полезны, если вы часто добавляете, изменяете или удаляете функциональные возможности в стабильном семействе классов, поскольку каждый функциональный элемент определяется отдельно в каждом классе посетителей исами классы не нуждаются в изменении.Если семейство классов нестабильно, шаблон посетителей может оказаться менее полезным, поскольку многим посетителям необходимо менять каждый раз, когда класс добавляется или удаляется.

Answer 4

A хорошо пример находится в компиляции исходного кода:

interface CompilingVisitor {
   build(SourceFile source);
}

Клиенты могут реализовать JavaBuilder, RubyBuilder, XMLValidator и т. Д., И реализация для сбора и посещения всех исходных файлов в проекте не нуждается в изменении.

Это будет плохой шаблон, если у вас есть отдельные классы для каждого типа исходного файла:

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

Все зависит от контекста и того, какие части системы вы хотите расширить.

Answer 5

Целью паттерна «Посетитель» является обеспечение того, чтобы объекты знали, когда посетитель закончил с ними, и ушли, чтобы классы могли выполнить любую необходимую очистку после этого. Это также позволяет классам выставлять свои внутренние компоненты «временно» как параметры «ref» и знать, что внутренние элементы больше не будут отображаться после того, как посетитель исчезнет. В случаях, когда очистка не требуется, шаблон посетителя не очень полезен. Классы, которые не выполняют ни одну из этих вещей, могут не получить пользу от шаблона посетителя, но код, который написан для использования шаблона посетителя, будет пригоден для использования с будущими классами, которые могут потребовать очистки после доступа.

Например, предположим, что у человека есть структура данных, содержащая много строк, которые должны обновляться атомарно, но класс, содержащий структуру данных, не знает точно, какие типы атомарных обновлений должны быть выполнены (например, если один поток хочет заменить все вхождения «X», в то время как другой поток хочет заменить любую последовательность цифр последовательностью, которая численно на один порядок выше, обе операции потоков должны быть успешными: если каждый поток просто считывает строку, выполняет свои обновления и записывает ее обратно, второй поток, записывающий обратно свою строку, перезапишет первый). Один из способов сделать это состоит в том, чтобы каждый поток получил блокировку, выполнил свою операцию и снял блокировку. К сожалению, если блокировки будут открыты таким образом, структура данных не сможет помешать кому-либо получить блокировку и никогда не снимать ее.

Шаблон Visitor предлагает (как минимум) три подхода, чтобы избежать этой проблемы:

1. Может заблокировать запись, вызвать предоставленную функцию, а затем разблокировать запись; запись может быть заблокирована навсегда, если предоставленная функция попадает в бесконечный цикл, но если предоставленная функция возвращает или выдает исключение, запись будет разблокирована (может быть разумным пометить запись как недействительную, если функция выдает исключение; это заблокировано, вероятно, не очень хорошая идея). Обратите внимание, что важно, что если вызываемая функция пытается получить другие блокировки, это может привести к тупиковой ситуации.
2. На некоторых платформах он может передать место хранения, содержащее строку, в качестве параметра 'ref'. Эта функция может затем скопировать строку, вычислить новую строку на основе скопированной строки, попытаться CompareExchange старой строки на новую и повторить весь процесс в случае сбоя CompareExchange.
3. Он может сделать копию строки, вызвать предоставленную функцию для строки, затем использовать сам CompareExchange, чтобы попытаться обновить оригинал, и повторить весь процесс в случае сбоя CompareExchange.

Без шаблона посетителя выполнение атомарных обновлений потребовало бы раскрытия блокировок и риска сбоя, если вызывающее программное обеспечение не соблюдает строгий протокол блокировки / разблокировки. С помощью шаблона Visitor атомарные обновления можно выполнять относительно безопасно.