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

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

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

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

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

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

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

Соответствие шаблонов PS3 Scala = шаблон посетителя на Steroid показывает, насколько проще шаблон посетителя без метода accept. Википедия добавляет к этому утверждению : путем ссылки на статью, показывающую, что « accept()методы не нужны, когда рефлексия доступна; вводит термин« обход »для техники».

Шаблоны 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). Таким образом, Execution войдет в то, что мы планировали 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(), но они обычно включают отражение и, следовательно, могут повлечь за собой довольно большие накладные расходы.

Конечно, это было бы глупо, если бы это был единственный способ реализации 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;
  ....
}

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

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

Изменить: уточнить: Visitметод посетителя содержит логику, применяемую к узлу. Метод узла Acceptсодержит логику перехода к соседним узлам. Случай, когда вы выполняете только двойную отправку, является особым случаем, когда просто нет соседних узлов для перехода.

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

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

Паттерн Посетитель предлагает (по крайней мере) три подхода, позволяющих избежать этой проблемы:

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

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

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

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

Хороший пример в исходном коде компиляции:

interface CompilingVisitor {
   build(SourceFile source);
}

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

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

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

Все сводится к контексту и тем частям системы, которые вы хотите расширить.