В чем смысл метода 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);
  }

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

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

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

PS3 Шаблон соответствия Scala = Шаблон посетителя на стероиде показывает, насколько проще шаблон Посетителя без метода принятия. Википедия добавляет к этому утверждению: связывая документ, показывающий, что 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 "s 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;
  ....
}

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

Answer 5

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

interface CompilingVisitor {
   build(SourceFile source);
}

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

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

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

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